org.abora.white.spaces.basic
Class XnRegion

java.lang.Object
  |
  +--org.abora.white.xpp.basic.Heaper
        |
        +--org.abora.white.spaces.basic.XnRegion

Direct Known Subclasses:

CrossRegion, Filter, IntegerRegion, RealRegion, SequenceRegion, SetRegion

public abstract class XnRegion

extends Heaper

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 (e.g., 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.

Constructor Summary

protected	XnRegion()
protected	XnRegion(Rcvr rcvr)

Method Summary

int	actualHashForEqual() Defined by subclasses to produce the value returned by hashForEqual.
abstract Stepper	actualStepper(OrderSpec order) Only called if I've already said I'm enumerable in the originally stated order.
XnRegion	asSimpleRegion() Return a simple region containing all positions contained by myself.
XnRegion	chooseMany(IntegerValue n)
XnRegion	chooseMany(IntegerValue n, OrderSpec order) If an OrderSpec is given, return the first n elements according to that OrderSpec.
Position	chooseOne()
Position	chooseOne(OrderSpec order) Essential.
abstract XnRegion	complement() Essential.
abstract CoordinateSpace	coordinateSpace() Essential.
abstract IntegerValue	count() How many positions do I contain? If I am not 'isFinite', then this message will BLAST.
XnRegion	delta(XnRegion region) The region where they differ.
Stepper	disjointSimpleRegions() emulate default argument of NULL
Stepper	disjointSimpleRegions(OrderSpec order) break it up into a set of non-empty simple regions which don't overlap.
abstract ScruSet	distinctions() Break it up into a set of non-full distinctions.
abstract boolean	hasMember(Position atPos) Do I contain this position? More than anything else, the behavior of this message is the defining characteristic of an XuRegion.
static ImmuSet	immuSet(XnRegion region) Make a set containing all the positions in the region
abstract XnRegion	intersect(XnRegion other) Essential.
boolean	intersects(XnRegion other) Essential.
boolean	isDistinction() Am I a distinction.
abstract boolean	isEmpty() Every coordinate space has exactly one empty region.
boolean	isEnumerable() emulate default argument of NULL
abstract boolean	isEnumerable(OrderSpec order) See comment in XuRegion::stepper.
abstract boolean	isEqual(Heaper other) Two regions are equal iff they contain exactly the same set of positions
abstract boolean	isFinite() Essential.
boolean	isFull() true if this is the largest possible region in this space -- the region that contains all positions in the space.
abstract boolean	isSimple() Am I a simple region.
boolean	isSubsetOf(XnRegion other) I'm a subset of other if I don't have any positions that he doesn't.
XnRegion	minus(XnRegion other) The region containing all my position which aren't in other.
Stepper	simpleRegions() emulate default argument of NULL
abstract Stepper	simpleRegions(OrderSpec order) Break myself up into a finite set of non-empty simple regions which, when unionWith'ed together will yield me.
abstract XnRegion	simpleUnion(XnRegion other) The result must contain all positions contained by either of the two original regions, and the result must be simple.
Stepper	stepper() emulate default argument of NULL
Stepper	stepper(OrderSpec order) Essential.
Position	theOne() Iff I contain exactly one position, return it.
abstract XnRegion	unionWith(XnRegion other) The result has as members exactly those positions which are members of either of the original two regions.
XnRegion	with(Position pos) the region with one more position.
XnRegion	without(Position pos) the region with one less position.

Methods inherited from class org.abora.white.xpp.basic.Heaper

destroy, destruct, equals, hashForEqual, printContentsOn, printOn, sendSelfTo, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

XnRegion

protected XnRegion()

XnRegion

protected XnRegion(Rcvr rcvr)

Method Detail

immuSet

public static ImmuSet immuSet(XnRegion region)

Make a set containing all the positions in the region

asSimpleRegion

public XnRegion 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.

coordinateSpace

public abstract CoordinateSpace coordinateSpace()

Essential. The coordinate space in which this is a region

complement

public abstract XnRegion complement()

Essential. Return a region of containing exactly those positions not in this region. The complement of a distinction must be a distinction.

delta

public XnRegion delta(XnRegion region)

The region where they differ. a->delta(b) ->isEqual (a->minus(b)->unionWith(b->minus(a)))

intersect

public abstract XnRegion intersect(XnRegion 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.

minus

public XnRegion minus(XnRegion other)

The region containing all my position which aren't in other.

simpleUnion

public abstract XnRegion simpleUnion(XnRegion 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.

unionWith

public abstract XnRegion unionWith(XnRegion 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.

with

public XnRegion with(Position pos)

the region with one more position. Actually, if I already contain pos, then the result is just me.

without

public XnRegion without(Position pos)

the region with one less position. Actually if I already don't contain pos, then the result is just me.

actualHashForEqual

public int actualHashForEqual()

Description copied from class: Heaper

Defined by subclasses to produce the value returned by hashForEqual.

Overrides:

actualHashForEqual in class Heaper

hasMember

public abstract boolean hasMember(Position 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.

intersects

public boolean intersects(XnRegion other)

Essential. tell whether it has any points in common

isDistinction

public boolean isDistinction()

Am I a distinction. See XuRegion class comment for implications of being a distinction.

isEmpty

public abstract boolean 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.

isEqual

public abstract boolean isEqual(Heaper other)

Two regions are equal iff they contain exactly the same set of positions

Specified by:

isEqual in class Heaper

isFinite

public abstract boolean 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. I.e., isFinite implies isEnumerable.

isFull

public boolean 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).

isSimple

public abstract boolean isSimple()

Am I a simple region. See XuRegion class comment for implications of being simple.

isSubsetOf

public boolean isSubsetOf(XnRegion 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)

chooseMany

public XnRegion chooseMany(IntegerValue n)

chooseOne

public Position chooseOne()

disjointSimpleRegions

public Stepper disjointSimpleRegions()

emulate default argument of NULL

isEnumerable

public boolean isEnumerable()

emulate default argument of NULL

simpleRegions

public Stepper simpleRegions()

emulate default argument of NULL

stepper

public Stepper stepper()

emulate default argument of NULL

chooseMany

public XnRegion chooseMany(IntegerValue n,
                           OrderSpec 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

public Position chooseOne(OrderSpec 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.

count

public abstract IntegerValue count()

How many positions do I contain? If I am not 'isFinite', then this message will BLAST.

disjointSimpleRegions

public Stepper disjointSimpleRegions(OrderSpec 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

public abstract ScruSet 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 null 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.

simpleRegions

public abstract Stepper simpleRegions(OrderSpec 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 NULL 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.

stepper

public Stepper stepper(OrderSpec order)

Essential. If my positions are enumerable in the order specified, then return a stepper which will so enumerate them. If 'order' is NULL, 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 NULL. For example, if I choose to regard NULL as implying ascending order, and I am only enumerable in descending order, then given NULL, 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 NULL 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 NULL, 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.

theOne

public Position 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)

actualStepper

public abstract Stepper actualStepper(OrderSpec order)

Only called if I've already said I'm enumerable in the originally stated order. Also, if the originally stated order was NULL, I get a guaranteed non-null order. Subclasses which override 'stepper' to a method which doesn't send 'actualStepper' may override 'actualStepper' to a stub method which always BLASTs.

isEnumerable

public abstract boolean isEnumerable(OrderSpec order)

See comment in XuRegion::stepper. a->stepper(os) won't BLAST iff a->isEnumerable(os)