>It seems like it would be relatively easy to implement a Sage class
>for real intervals that represents finite unions of open, closed, half
>open, and unbounded intervals and implements union() and
>intersection() methods.
I did it. I attach my piece of code. This is only python, but it is
going to make the job.
Technically I define a class Interval that represent an interval (closed
or open at each extremities). This class has the important
__contrain__() method that tests if a number is contained in the interval.
Then class ContinuousSet that represent finite union and intersections
of intervals. Its main attribute is a list of disjoint intervals. These
intervals represent the set.
For the moment, I have working union() and __contain__() methods; the
delicate part is to express the union of two lists of disjoints
intervals as a new list of disjoint intervals. I'm working on
intersections and I plan to be able to test inclusion.
doctest of the working methods are included in the code.
Up to writing better documentation and finishing the work, do one think
that it can be included in some place in Sage ?
Have a good day
Laurent
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
#! /usr/bin/python
# -*- coding: utf8 -*-
import doctest
def constructorContinuouSet(A):
if type(A)==ContinuousSet:
return A
if type(A)==Interval:
return ContinuousSet([A],[])
def EmptySet():
return ContinuousSet([],[])
class Interval(object):
"""
Represent the real interval between a and b.
By default, the interval is closed : [a,b]
if low_open is false, the interval is lower opened
if up_open is false, the interval is upper opened.
Examples
DEFINITION OF INTERVALS
>>> I=Interval(0,2,low_open=False,up_open=True)
>>> J=Interval(-2,-1)
>>> K=Interval(1,3,low_open=False,up_open=True)
>>> print I
[0 , 2[
>>> print J
[-2 , -1]
>>> print K
[1 , 3[
INTERSECTION
>>> X = I.intersection(K)
>>> print X
[1 , 2[
>>> print 1 in X
True
>>> print 2 in X
False
FUSION
The intervals I and J have no intersection, so the union is disjoint :
>>> Y=I.fusion(J)
>>> for a in Y:
... print a
[0 , 2[
[-2 , -1]
The intervals I and K have intersection, so the union is one interval:
>>> Y=I.fusion(K)
>>> for a in Y:
... print a
...
[0 , 3[
UNION
Asking the union of two intervals returns an object ContinuousSet
>>> import math
>>> I=Interval(1,4,low_open=False,up_open=False)
>>> J=Interval(0,2,low_open=True,up_open=True)
>>> M=Interval(7,8,low_open=True,up_open=False)
>>> print I.union(J)
]0 , 4]
>>> print I.union(M)
]7 , 8] U [1 , 4]
>>> 7 in I.union(M)
False
>>> math.pi in I.union(M)
True
"""
def __init__(self,a,b,low_open=False,up_open=False):
self.low_bound=a
self.up_bound=b
self.low_open=low_open
self.up_open=up_open
def contains_oo(x):
if x>a and x<b :
return True
return False
def contains_oc(x):
if x>a and x<=b :
return True
return False
def contains_co(x):
if x>=a and x<b :
return True
return False
def contains_cc(x):
if x>=a and x<=b :
return True
return False
if self.low_open and self.up_open:
self.contains=contains_oo
elif self.low_open and not self.up_open:
self.contains=contains_oc
elif not self.low_open and self.up_open:
self.contains=contains_co
elif not self.low_open and not self.up_open:
self.contains=contains_cc
def intersection(self,A):
if self.low_bound in A or self.up_bound in A or A.low_bound in self or A.up_bound in self :
low_bound=self.low_bound
up_bound=self.up_bound
low_open=self.low_open
up_open=self.up_open
if A.low_bound>self.low_bound:
low_bound=A.low_bound
low_open=A.low_open
if A.low_bound==self.low_bound:
low_open = self.low_bound and A.low_bound
if A.up_bound<self.up_bound:
up_bound=A.up_bound
up_open=A.up_open
if A.up_bound==self.up_bound:
up_open = self.up_open and A.up_open
if low_bound == up_bound:
return ContinuousSet([],[low_bound])
else:
return ContinuousSet([Interval(low_bound,up_bound,low_open=low_open,up_open=up_open)],[])
else :
return EmptySet()
def fusion(self,A):
"""
Return the fusion of self and A where A is supposed to be an interval.
If the union of self and A is an interval B, return the tuple (B).
Else, return the tuple (self,A)
"""
a=self.low_bound
b=self.up_bound
c=A.low_bound
d=A.up_bound
if (a in A) or (b in A) or (c in self) or (d in self):
m=min(a,c)
M=max(b,d)
low_open=True
up_open=True
if m==a and self.low_open==False:
low_open=False
if m==c and A.low_open==False:
low_open=False
if M==b and self.up_open==False:
up_open=False
if M==d and A.up_open==False:
up_open=False
return tuple([Interval(m,M,low_open=low_open,up_open=up_open)])
return (self.copy(),A.copy())
def fusion_with_list(self,intervals_list):
"""
Return the fusion of self with the interval list. That is a tuple of disjoints intervals (I_1, ... ,I_n) such that
I_1 union I_2 union ... union I_n = self union intervals_list
The intervals_list is supposed to be composed of disjoint intervals. If not, see the function SimplificationIntervalsIntervals
Examples :
>>> I=Interval(1,4,low_open=False,up_open=False)
>>> J=Interval(0,2,low_open=True,up_open=True)
>>> K=Interval(3,5,low_open=False,up_open=True)
>>> L=Interval(6,7,low_open=False,up_open=False)
>>> X=I.fusion_with_list([J,K,L])
>>> for a in X:
... print a
[6 , 7]
]0 , 5[
The result does not depend on the order of the list:
>>> X=I.fusion_with_list([L,K,J])
>>> for a in X:
... print a
[6 , 7]
]0 , 5[
"""
new_list=[]
happend_fusion=False
for I in intervals_list:
a = self.fusion(I)
if len(a)==1:
if happend_fusion == False:
new_guy=a[0]
happend_fusion=True
else :
new_list.append(a[0])
if len(a)==2:
new_list.append(I)
if happend_fusion :
return new_guy.fusion_with_list(new_list)
else :
new_list.append(self)
return tuple(new_list)
def union(self,A):
return constructorContinuouSet(self).union(constructorContinuouSet(A))
def copy(self):
"""
Return a copy of the interval which is a new object.
>>> I=Interval(1,4,low_open=False,up_open=False)
>>> X=I.copy()
>>> I.low_open=True
>>> print X.low_open
False
"""
A=Interval(self.low_bound,self.up_bound,self.low_open,self.up_open)
return A
def __str__(self):
a=[]
if self.low_open :
a.append("]")
else :
a.append("[")
a.append(str(self.low_bound))
a.append(" , ")
a.append(str(self.up_bound))
if self.up_open :
a.append("[")
else :
a.append("]")
return "".join(a)
def __contains__(self,x):
return self.contains(x)
def DiscreteSet(Points):
r"""
Return ContinuousSet representing the set containing only the points given in Points.
Example
"""
def contains(x):
if x in Points:
return True
return False
return ContinuousSet(contains)
class WeakSet(object):
"""
Represent a set given by its __contains__ function.
It is easy to build union, intersection, symmetric differences of that kind of set, but one cannot test inclusion.
"""
def __init__(self,contains):
self.contains=contains
def __contains__(self,x):
return self.contains(x)
def intersection(self,A):
def contains(x):
return x in A and x in self
return GeneralSet(contains)
def union(self,A):
def contains(x):
return x in A or x in self
return GeneralSet(contains)
def complement(self):
def contains(x):
return x not in self
return GeneralSet(contains)
def setminus(self,B):
def contains(x):
return x in self and x not in A
return GeneralSet(contains)
def SimplificationIntervalPoint(intervals_list,points_list):
# We close the intervals where we have points, and we remove the points
# that belong to an interval.
to_be_removed=[]
for P in points_list:
for I in intervals_list:
if P==I.low_bound:
I.low_open=False
to_be_removed.append(P)
if P==I.up_bound:
I.up_open=False
to_be_removed.append(P)
if P in I:
to_be_removed.append(P)
to_be_removed=list(set(to_be_removed))
for P in to_be_removed :
points_list.remove(P)
return intervals_list,points_list
def SimplificationIntervalsIntervals(intervals_list):
"""
Return a tuple of disjoint intervals that represent the same set.
>>> I=Interval(1,4,low_open=False,up_open=False)
>>> J=Interval(0,2,low_open=True,up_open=True)
>>> K=Interval(3,5,low_open=False,up_open=True)
>>> L=Interval(6,7,low_open=False,up_open=False)
>>> M=Interval(7,8,low_open=True,up_open=False)
>>> X=SimplificationIntervalsIntervals([I,J,K,L,M])
>>> for a in X:
... print a
[6 , 8]
]0 , 5[
"""
new_list=[]
l=len(intervals_list)
new_list=intervals_list[0].fusion_with_list(intervals_list[1:])
if len(new_list)==len(intervals_list):
return tuple(new_list)
else :
return SimplificationIntervalsIntervals(new_list)
class ContinuousSet(object):
r"""
Represent a set that can be the union of some intervals and isolated points.
UNION
Union is supported with intervals and can be nested :
>>> I=Interval(1,4,low_open=False,up_open=True)
>>> J=Interval(4,5,low_open=False,up_open=True)
>>> M=Interval(7,8,low_open=True,up_open=False)
>>> print I.union(J).union(M)
]7 , 8] U [1 , 5[
"""
def __init__(self,intervals_list,points_list):
self.intervals_list=intervals_list
self.points_list=points_list
def __contains__(self,x):
for I in self.intervals_list:
if x in I :
return True
for A in self.points_list :
if x in A :
return True
def union(self,A):
A=constructorContinuouSet(A)
intervals_list=[]
intervals_list.extend(self.intervals_list)
intervals_list.extend(A.intervals_list)
points_list=[]
points_list.extend(self.points_list)
points_list.extend(A.points_list)
intervals_list,points_list=SimplificationIntervalPoint(intervals_list,points_list)
intervals_list=SimplificationIntervalsIntervals(intervals_list)
return ContinuousSet(intervals_list,points_list)
def __str__(self):
li=[str(a) for a in self.intervals_list]
li.extend(["{%s}"%str(x) for x in self.points_list])
return " U ".join(li)
doctest.testmod()
