Index - All Packages - All Categories - All Classes
Class XnRegion
The design of a new coordinate space consists mostly in the design of the XuRegions which can be used to describe (possibly infinite) sets of positions in that coordinate space. It will generally not be the case (for a given coordinate space) that all mathematically describable sets of positions will be representable by an XuRegion in that space. This should not be seen as a temporary deficiency of the current implementation of a space, but rather part of the design of what a given space *means*.
For example, in IntegerSpace, one cannot form the XuRegion whose members are exactly the even numbers. If this were possible, other desirable properties which are part of the intent of IntegerSpaces would no longer be possible. For example, any XuRegion should be able to break itself up into a finite number of simple XuRegions ("simple" is described below). Were an even number region possible, this would have undesirable consequences for the definition of "simple" in this space. If you want (for example) to be able to have a XuRegion which can represent all the even numbers, it probably makes more sense to define a whole new space in which these new XuRegions apply.
XuRegions should be closed under a large set of operations, such as intersection, unionWith, complement and minus. ("closed" means that the result of performing this operation on XuRegions of a given space is another valid XuRegion in the same space.) Additional guarantees are documented with each operation.
A XuRegion may be classified at one of three levels of "simplicity":
1) The simplest are the *distinctions*. Distinctions are those that answer with (at most) a single set containing themselves in response to the message "distinctions". (The reason I say "at most" is that a full region (one that covers the entire coordinate space) may answer with the empty set.) Distinctions are the simplest XuRegions of a given space out of which all other XuRegions of that space can be finitely composed. There should probably be a message "isDistinction" for which exactly the distinctions answer "true". The complement of a distinction is a distinction. Three examples of distinctions in spaces are:
a) in IntegerSpace, any simple inequality. For example, all integers < 37.
b) in one kind of 3-space, any half space (all the space on one side of some plane)
c) in another kind of 3-space, any sphere or spherical hole.
Note that "c" could not just have spheres as the distinction because distinctions must be closed under complement. (We are here ignoring the quite substantial problems that arise in dealing with approximate (eg., floating point) which would almost necessarily have to arise in doing any decent 3-space. 3-space is nevertheless a good intuition pump.)
2) Next are the *simple regions*. Simple regions are exactly those that say "true" to "isSimple". All distinctions are also simple regions. In response to the message "distinctions", and simple region must return a finite set of distinctions which, when intersected together, yield the original simple region. Generally, one tries to define the simple regions for a space to correspond to some notion of locality in the space. For example, it may be good for a simple region not to be able to have a hole in it. Or perhaps a simple region is which must be connected (whatever that means in a given space). Example non-distinction simple regions for the above example spaces would be:
a) The interval from 3 inclusive to 17 exclusive (intersection of all integers >= 3 and all < 17)
b) A convex hull (intersection of half spaces)
c) Whatever you get by intersecting a bunch of spheres and sherical holes.
The simple regions for both "a" and "b" would be connected, without holes, and even convex. This follows directly from the definition of our distinctions. None of these nice properties holds for "c", and this also follows directly from our decision to start with spheres. "c" is still perfectly valid, just less preferable by some criteria.
3) Finally, there are the regions of a space in general. Any region must respond to the message "simpleRegions" with a stepper which will produce a finite number of simple regions that, when unioned together, yields the original region. A simple region will return a stepper that will return at most itself ("at most" because an empty region (which covers no positions) may return an empty stepper). Example non-simple regions are:
a) all integers < 3 and all integers >= 17
b) two convex hulls
c) two disjoint spheres
Note that "a" is the complement of the earlier "a" example, thereby showing why the complement of a simple region isn`t necessarily simple. Even though the "c" space is so unconstrained in the properties of its simple regions, there is no way to interect a finite number of spheres and spherical holes to produce a pair of disjoint spheres. Therefore the pair is non-simple. Not all spaces must have non-simple regions (or even non-distinctions). It is interesting to observe for "b" and "c" that even though there is a natural conversion between their respective positions, (except for the empty and full regions) there is no conversion at all between their respective regions. The kinds of sets of positions representable in one space is completely different than those representable in the other space.
We will use these three example spaces repeatedly in documenting the protocol.
Package: Udanax-Gold
All Superclasses: Object Heaper
Immediate Subclasses: CrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
Protocols: Object
Categories: Xanadu-Spaces-Basic
Class MethodsimmuSetmake: region
Make a set containing all the positions in the region
infostProtocol
Overridden by: CrossRegion class Filter class IDRegion class IntegerRegion class RealRegion class SequenceRegion class
Instance MethodsactualHashForEqual
Overridden by: CrossRegion GenericCrossRegion Filter AndFilter ClosedFilter NotSubsetFilter NotSupersetFilter OpenFilter OrFilter SubsetFilter SupersetFilter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
actualStepper: order
Only called if I've already said I'm enumerable in the originally stated order. Also, if the originally stated order was nil, I get a guaranteed non-nil order. Subclasses which override 'stepper' to a method which doesn't send 'actualStepper' may override 'actualStepper' to a stub method which always BLASTs.
Overridden by: CrossRegion GenericCrossRegion Filter ClosedFilter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
asArray: order
Returns all the Positions in the region in order according to 'order'. If the region isn't finite, then this BLASTs.
asSimpleRegion
Return a simple region containing all positions contained by myself.
If I am simple, then the result must be me. Otherwise,
the resulting region will contain more positions than I do, but it
must contain all those that I do. It would be good for the resulting
simple region to not contain many more points than it needs in order
to satisfy these constraints; but this is a preference, not a
specification. Particular spaces may specify stronger guarantees,
but as far as class XuRegion is concerned it is correct (though silly)
for this message to always return the full region for the space.
Overridden by: CrossRegion GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
chooseMany: n
chooseMany: n with: order
If an OrderSpec is given, return the first n elements according to that OrderSpec. If no OrderSpec is given, then iff I contain at least n positions, return n of them; otherwise BLAST. This should be implemented even by regions that aren't enumerable. Inspired by the axiom of choice.
chooseOne
chooseOne: order
Essential. If an OrderSpec is given, return the first element according to that OrderSpec. If no OrderSpec is given, then iff I contain at least one position, return one of them; otherwise BLAST. This should be implemented even by regions that aren't enumerable. Inspired by the axiom of choice.
Overridden by: IntegerRegion
complement
Essential. Return a region of containing exactly those positions not in this region. The complement of a distinction must be a distinction.
Overridden by: CrossRegion GenericCrossRegion Filter AndFilter ClosedFilter NotSubsetFilter NotSupersetFilter OpenFilter OrFilter SubsetFilter SupersetFilter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
coordinateSpace
Essential. The coordinate space in which this is a region
Overridden by: CrossRegion GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion HeaperRegion
count
How many positions do I contain? If I am not 'isFinite', then this message will BLAST.
Overridden by: CrossRegion GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
delta: region
The region where they differ.
a->delta(b) ->isEqual (a->minus(b)->unionWith(b->minus(a)))
disjointSimpleRegions
emulate default argument of nil
disjointSimpleRegions: order
break it up into a set of non-empty simple regions which don't
overlap. This message satisfies all the specs of 'simpleRegions', and
in addition provides for lack of overlap. It may be significantly more
expensive than 'simpleRegions' which is why they both exist.
distinctions
Break it up into a set of non-full distinctions. It is an error to send
this to a non-simple region. A full region will respond with the nil
set. Other distinctions will respond with a singleton set containing
themselves, and simple regions will respond with a set of distinctions
which, when intersected together, yield the original region.
Overridden by: CrossRegion GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
do: aBlock
hasMember: atPos
Do I contain this position? More than anything else, the behavior of this message is the defining characteristic of an XuRegion. All other messages (except for the simplicity characterization) should be specifiable in terms of the behavior of this message. What an XuRegion *is* (mostly) is a finite decision procedure for accepting or rejecting any given position.
Overridden by: CrossRegion GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
intersect: other
Essential. The intersection of two simple regions must be simple. The intersection of two distinctions must therefore be a simple region. The result has exactly those members which both the original regions have.
Overridden by: CrossRegion GenericCrossRegion Filter ClosedFilter OpenFilter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
intersects: other
Essential. tell whether it has any points in common
Overridden by: GenericCrossRegion IntegerRegion SetRegion
isDistinction
Am I a distinction. See XuRegion class comment for implications of being a distinction.
Overridden by: GenericCrossRegion
isEmpty
Every coordinate space has exactly one empty region. It is the one containing no positions. It and only it responds 'true' to this message.
Overridden by: CrossRegion GenericCrossRegion Filter AndFilter ClosedFilter NotSubsetFilter NotSupersetFilter OpenFilter OrFilter SubsetFilter SupersetFilter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
isEnumerable
emulate default argument of nil
isEnumerable: order
See comment in XuRegion::stepper.
a->stepper(os) won't BLAST iff a->isEnumerable(os)
Overridden by: CrossRegion GenericCrossRegion Filter ClosedFilter IntegerRegion RealRegion SequenceRegion SetRegion HeaperRegion
isEqual: other
Two regions are equal iff they contain exactly the same set of positions
Overridden by: CrossRegion GenericCrossRegion Filter AndFilter ClosedFilter NotSubsetFilter NotSupersetFilter OpenFilter OrFilter SubsetFilter SupersetFilter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
isFinite
Essential. Do I contain a finite number of positions? If I do, then the 'count' message will say how many, and I will gladly provide a stepper which will step over all of them. Ie., isFinite implies isEnumerable.
Overridden by: CrossRegion GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
isFull
true if this is the largest possible region in this space -- the region that contains all positions in the space. Note that in a space which has no positions (which is perfectly valid), the one XuRegion would be both empty (since it has no positions) and full (since it has all the positions in the space).
Overridden by: GenericCrossRegion Filter AndFilter ClosedFilter NotSubsetFilter NotSupersetFilter OpenFilter OrFilter SubsetFilter SupersetFilter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
isSimple
Am I a simple region. See XuRegion class comment for implications of being simple.
Overridden by: CrossRegion GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
isSubsetOf: other
I'm a subset of other if I don't have any positions that he doesn't. Note that if we are equal, then I am still a subset of him. If you want to know if I'm a strict subset, you can ask
a->isSubsetOf(b) && ! a->isEqual(b)
Overridden by: GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
mapping: data
minus: other
The region containing all my position which aren't in other.
Overridden by: ClosedFilter OpenFilter SetRegion
simpleRegions
emulate default argument of nil
simpleRegions: order
Break myself up into a finite set of non-empty simple regions which, when
unionWith'ed together will yield me. May be sent to any region. If I
am isEmpty, I will respond with the empty stepper. Otherwise, if I am
simple I will respond with a stepper producing just myself.
Please only use nil for the 'order' argument for now unless the
documentation for a particular region or coordinate space says that
it will deal with the 'order' argument meaningfully. When no order is
specified then I may return the simple regions in any order. When the
ordering functionality is implemented, then I am constrained to
produce the simple regions in an order consistent with the argument's
ordering of my positions. When the simple regions don't overlap, and
don't surround each other in the ordering, then the meaning is clear.
Otherwise, there are several plausible options for how we should
specify this message.
Overridden by: CrossRegion GenericCrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
simpleUnion: other
The result must contain all positions contained by either of the two
original regions, and the result must be simple. However, the result
may contain additional positions. See the comment on
'XuRegion::asSimpleRegion'. a->simpleUnion(b) satisfies the same specification
as (a->unionWith(b))->asSimpleRegion(). However, the two results do
not have to be the same region.
Overridden by: CrossRegion Filter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
stepper
emulate default argument of nil
stepper: order
Essential. If my positions are enumerable in the order specified, then return a stepper which will so enumerate them. If 'order' is nil, then I may treat this as a request to enumerate according to any order I choose, except that if I am enumerable in ascending order, then I must be enumerable given nil. For example, if I choose to regard nil as implying ascending order, and I am only enumerable in descending order, then given nil, I may blast even though there is an order in which I am enumerable.
In fact, right now the ability to respond to an 'order' argument is in such a to-be-implemented state that it should only be considered safe to provide a nil argument, unless the documentation on a particular space or region says otherwise.
The eventual specification of this message is clear, and is upwards compatible from the current behavior: If I can enumerate in an order consistent with 'order', do so. If 'order' is nil, then if I can be enumerated at all (if there is any counting sequence), then I still do so. For example, I should be able to get an (infinite) stepper for stepping through all the integers, but not all the reals. As the above example shows, being enumerable doesn't imply being finite.
Also, being able to produce a stepper that continues to yield more positions in the specified order is not sufficient to imply being enumerable. To be enumerable, it must be the case that any given position which is a member of the region will eventually be reached by the stepper. Not all implementations currently succeed in guaranteeing this (See UnionCrossRegion::isEnumerable).
See ScruTable::stepper.
Overridden by: RealRegion SequenceRegion
theOne
Iff I contain exactly one position, return it. Otherwise BLAST. The idea for this message is taken from the THE function of ONTIC (reference McAllester)
Overridden by: GenericCrossRegion IDRegion SetRegion
unionWith: other
The result has as members exactly those positions which are members of either of the original two regions. No matter how simple the two original regions are, the result may be non-simple.
The only reason this is called 'unionWith' instead of 'union' is that the latter is a C++ keyword.
Overridden by: CrossRegion GenericCrossRegion Filter ClosedFilter OpenFilter IDRegion IntegerRegion RealRegion SequenceRegion SetRegion
with: pos
the region with one more position. Actually, if I already contain pos, then the result is just me.
Overridden by: IDRegion IntegerRegion SequenceRegion SetRegion
without: pos
the region with one less position. Actually if I already don't contain pos, then the result is just me.
Overridden by: SetRegion
Index - All Packages - All Categories - All Classes