org.abora.white.spaces.integers
Class IntegerRegion

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

public class IntegerRegion

extends XnRegion

An IntegerRegion can be thought of as the disjoint union of intervals and inequalities. The interesting cases to look at are:
The distinctions:

• 1) The empty region
• 2) The full region
• 3) A "left" inequality -- e.g., everything less that 3.
• 4) A "right" inequality -- e.g., everything greater than or equal to 7

The non-distinction simple regions:

• 5) An interval -- e.g., from 3 inclusive to 7 exclusive

The non-simple regions:

• 6) A disjoint union of (in order) an optional left inequality, a set of intervals, and an optional right inequality.

If a non-empty region has a least element, then it "isBoundedLeft". Otherwise it extends leftwards indefinitely. Similarly, if a non-empty region has a greatest element, then it "isBoundedRight". Otherwise it extends rightwards indefinitely. (We may figuratively speak of the region extending towards + or - infinity, but we have purposely avoided introducing any value which represents an infinity.)

Looking at cases again:

• 1) "isBoundedLeft" and "isBoundedRight" since it doesn't extent indenfinitely in either direction. (A danger to watch out for is that this still has neither a greatest nor a least element).
• 2) niether.
• 3) "isBoundedRight"
• 4) "isBoundedLeft"
• 5) "isBoundedLeft" and "isBoundedRight"
• 6) "isBoundedLeft" iff doesn''t include a left inequality,
  "isBoundedRight" iff doesn''t include a right inequality.

An efficiency note: Currently many of the method which could be doing an O(log) binary search (such as hasMember) are instead doing a linear search. This will be fixed if it turns out to be a problem in practice.

IntegerRegions are immutable.

Implementation

Zero or more transition points, from entering to exiting the region and visa-versa. Transitions are ordered from negative infinity through positive infinity and stored in myTransitions, together with a myTransitionCount of the the first transitions that should be considered. The count appears to be just a performance improvement in place of continually requesting the count of myTransition. myStartsInside indicates whether the first transition points is an entering, or exiting transition.

Empty Region: myStartsInside = false, myTransitions={}
Full Region: myStartsInside = true, myTransitions={}
Before 10: myStartsInside = true, myTransitions={10}
After 10: myStartsInside = false, myTransitions={10}
Between 5 & 10: myStartsInside = false, myTransitions={5, 10}

Statics cache the Empty and Full regions. There are additionally a number of less obvious statics that are more dynamic, and reflect the assumption that there will be a significant number of consequitive repeated requests for the same regions.

See OrderedRegion.

Field Summary

protected static IntegerRegion	AllIntegers
protected static IntegerRegion	EmptyIntegerRegion
protected static IntegerRegion	LastAfterRegion
protected static IntegerValue	LastAfterStart
protected static IntegerValue	LastBeforeEnd
protected static IntegerRegion	LastBeforeRegion
protected static IntegerRegion	LastInterval
protected static IntegerValue	LastLeft
protected static IntegerValue	LastRight
protected static IntegerValue	LastSingleton
protected static IntegerRegion	LastSingletonRegion
protected boolean	myStartsInside
protected int	myTransitionCount
protected IntegerVarArray	myTransitions

Constructor Summary

protected	IntegerRegion(boolean startsInside, int count, IntegerVarArray transitions)
protected	IntegerRegion(Rcvr receiver)

Method Summary

static IntegerRegion	above(IntegerValue start, boolean inclusive) Essential.
int	actualHashForEqual() Defined by subclasses to produce the value returned by hashForEqual.
Stepper	actualStepper(OrderSpec order) Iff I am bounded left am I enumerable in ascending order.
static IntegerRegion	after(IntegerValue start) The region containing all position greater than or equal to start
static IntegerRegion	allIntegers() The full region of this space
XnRegion	asSimpleRegion() Will always return the smallest simple region which contains all my positions
static IntegerVarArray	badlyViolatePrivacyOfIntegerRegionTransitions(IntegerRegion reg) used for an efficiency hack in PointRegion.
static IntegerRegion	before(IntegerValue end) The region of all integers less than end.
XnRegion	beforeLast() the region before the last element of the set.
static IntegerRegion	below(IntegerValue stop, boolean inclusive) Make a region that contains all integers less than (or equal if inclusive is true) to stop.
Position	chooseOne(OrderSpec order) Essential.
XnRegion	compacted() transform the region into a simple region with left bound 0 (or -inf if unbounded below).
Mapping	compactor() A mapping to transform the region into a simple region with left bound 0 (or -inf if unbounded).
XnRegion	complement() Essential.
CoordinateSpace	coordinateSpace() Essential.
IntegerValue	count() How many positions do I contain? If I am not 'isFinite', then this message will BLAST.
void	destroy()
ScruSet	distinctions() Break it up into a set of non-full distinctions.
protected IntegerEdgeStepper	edgeStepper() Do not send from outside the module.
boolean	hasIntMember(IntegerValue key) Unboxed version.
boolean	hasMember(Position pos) Do I contain this position? More than anything else, the behavior of this message is the defining characteristic of an XuRegion.
static IntegerRegion	integerExtent(IntegerValue start, IntegerValue n) The region of all integers which are >= start and < start + n
XnRegion	intersect(XnRegion region) Essential.
boolean	intersects(XnRegion region) Essential.
static IntegerRegion	interval(IntegerValue left, IntegerValue right) The region of all integers which are >= left and < right
Stepper	intervals()
Stepper	intervals(OrderSpec order) Essential.
boolean	isBoundedAbove() Either I extend indefinitely to plus infinity, or I am bounded above, not both.
boolean	isBoundedBelow() Either I extend indefinitely to minus infinity, or I am bounded below, not both.
boolean	isCompacted() Return true if this region is either empty or a simple region with lower bound of either 0 or -infinity.
boolean	isEmpty() Every coordinate space has exactly one empty region.
boolean	isEnumerable(OrderSpec order) Actually uses the 'order' argument correctly to enumerate the positions.
boolean	isEqual(Heaper other) Two regions are equal iff they contain exactly the same set of positions
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.
boolean	isInterval() Whether this Region is a non-empty interval, i.e.
boolean	isSimple() Inequalities and intervals are both simple.
boolean	isSubsetOf(XnRegion other) I'm a subset of other if I don't have any positions that he doesn't.
static IntegerRegion	make() No integers, the empty region
static IntegerRegion	make(IntegerValue singleton) The region with just this one position.
static IntegerRegion	make(IntegerValue left, IntegerValue right) The region of all integers which are >= left and < right.
IntegerValue	nearestIntHole(IntegerValue index) This is a hack for finding the smallest available index to allocate that is not in a particular region (a table domain, for example).
void	printOn(java.io.PrintWriter oo) This should rarely be overridden.
IntegerRegion	runAt(IntegerValue pos) Return the region starting from pos (inclusive) and going until the next transition.
protected IntegerVarArray	secretTransitions() The actuall array.
void	sendSelfTo(Xmtr xmtr)
protected IntegerRegion	simpleRegionAtIndex(int i) the simple region at the given index in the transition array
Stepper	simpleRegions(OrderSpec order) Treats NULL the same as ascending.
XnRegion	simpleUnion(XnRegion otherRegion) The result is the smallest simple region which satisfies the spec in XuRegion::simpleUnion
IntegerValue	start() I have a start only if I'm not empty and I am isBoundedBelow.
IntegerValue	stop() I have a stop only if I'm not empty and I am isBoundedAbove.
protected int	transitionCount() Do not send from outside the module.
XnRegion	unionWith(XnRegion region) The result has as members exactly those positions which are members of either of the original two regions.
protected static IntegerRegion	usingx(boolean startsInside, int transitionCount, IntegerVarArray transitions)
XnRegion	with(Position position) the region with one more position.
XnRegion	withInt(IntegerValue pos)

Methods inherited from class org.abora.white.spaces.basic.XnRegion

chooseMany, chooseMany, chooseOne, delta, disjointSimpleRegions, disjointSimpleRegions, immuSet, isDistinction, isEnumerable, minus, simpleRegions, stepper, stepper, theOne, without

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

destruct, equals, hashForEqual, printContentsOn, toString

Methods inherited from class java.lang.Object

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

Field Detail

myStartsInside

protected final boolean myStartsInside

myTransitionCount

protected final int myTransitionCount

myTransitions

protected final IntegerVarArray myTransitions

AllIntegers

protected static IntegerRegion AllIntegers

EmptyIntegerRegion

protected static IntegerRegion EmptyIntegerRegion

LastAfterRegion

protected static IntegerRegion LastAfterRegion

LastAfterStart

protected static IntegerValue LastAfterStart

LastBeforeEnd

protected static IntegerValue LastBeforeEnd

LastBeforeRegion

protected static IntegerRegion LastBeforeRegion

LastInterval

protected static IntegerRegion LastInterval

LastLeft

protected static IntegerValue LastLeft

LastRight

protected static IntegerValue LastRight

LastSingleton

protected static IntegerValue LastSingleton

LastSingletonRegion

protected static IntegerRegion LastSingletonRegion

Constructor Detail

IntegerRegion

protected IntegerRegion(boolean startsInside,
                        int count,
                        IntegerVarArray transitions)

IntegerRegion

protected IntegerRegion(Rcvr receiver)

Method Detail

usingx

protected static IntegerRegion usingx(boolean startsInside,
                                      int transitionCount,
                                      IntegerVarArray transitions)

above

public static IntegerRegion above(IntegerValue start,
                                  boolean inclusive)

Essential. Make a region that contains all integers greater than (or equal if inclusive is true) to start.

after

public static IntegerRegion after(IntegerValue start)

The region containing all position greater than or equal to start

allIntegers

public static IntegerRegion allIntegers()

The full region of this space

before

public static IntegerRegion before(IntegerValue end)

The region of all integers less than end. Does not include end.

below

public static IntegerRegion below(IntegerValue stop,
                                  boolean inclusive)

Make a region that contains all integers less than (or equal if inclusive is true) to stop.

integerExtent

public static IntegerRegion integerExtent(IntegerValue start,
                                          IntegerValue n)

The region of all integers which are >= start and < start + n

interval

public static IntegerRegion interval(IntegerValue left,
                                     IntegerValue right)

The region of all integers which are >= left and < right

make

public static IntegerRegion make()

No integers, the empty region

make

public static IntegerRegion make(IntegerValue singleton)

The region with just this one position. Equivalent to using a converter to convert this position to a region.

make

public static IntegerRegion make(IntegerValue left,
                                 IntegerValue right)

The region of all integers which are >= left and < right.

badlyViolatePrivacyOfIntegerRegionTransitions

public static IntegerVarArray badlyViolatePrivacyOfIntegerRegionTransitions(IntegerRegion reg)

used for an efficiency hack in PointRegion. Don't use.

asSimpleRegion

public XnRegion asSimpleRegion()

Will always return the smallest simple region which contains all my positions

Overrides:

asSimpleRegion in class XnRegion

beforeLast

public XnRegion beforeLast()

the region before the last element of the set.

What on earth is this for? (Yes, I've looked at senders)

compacted

public XnRegion compacted()

transform the region into a simple region with left bound 0 (or -inf if unbounded below).

What on earth is this for? (Yes, I've looked at senders)

compactor

public Mapping compactor()

A mapping to transform the region into a simple region with left bound 0 (or -inf if unbounded). The domain of the mapping is precisely this region.

This is primarily used in XuText Waldos, which only deal with contiguous zero-based regions of data.

coordinateSpace

public CoordinateSpace coordinateSpace()

Description copied from class: XnRegion

Essential. The coordinate space in which this is a region

Specified by:

coordinateSpace in class XnRegion

isCompacted

public boolean isCompacted()

Return true if this region is either empty or a simple region with lower bound of either 0 or -infinity.

Equivalent to this->compacted()->isEqual (this)

nearestIntHole

public IntegerValue nearestIntHole(IntegerValue index)

This is a hack for finding the smallest available index to allocate that is not in a particular region (a table domain, for example).

runAt

public IntegerRegion runAt(IntegerValue pos)

Return the region starting from pos (inclusive) and going until the next transition. If this contains pos, then return the longest contiguous region starting at pos of positions it contains. If this don't contain pos, then return the longest contiguous region starting at pos of positions it does not contain.

start

public IntegerValue start()

I have a start only if I'm not empty and I am isBoundedBelow. I report as my start the smallest position I *do* contain, which is one greater than the largest position I do not contain. The lower bound of the interval from 3 inclusive to 7 exclusive is 3. See 'stop', you may be surprised.

stop

public IntegerValue stop()

I have a stop only if I'm not empty and I am isBoundedAbove. I report as my stop the smallest position I *do not* contain, which is one greater than the largest position I do contain. The ustop of the interval from 3 inclusive to 7 exclusive is 7. See 'start', you may be surprised.

destroy

public void destroy()

Overrides:

destroy in class Heaper

printOn

public void printOn(java.io.PrintWriter oo)

Description copied from class: Heaper

This should rarely be overridden. In Tofu, it prints ClassName(...), where ... is either produced by printInsideOn or is ??? if printInsideOn it not overridden.

Overrides:

printOn in class Heaper

actualHashForEqual

public int actualHashForEqual()

Description copied from class: Heaper

Defined by subclasses to produce the value returned by hashForEqual.

Overrides:

actualHashForEqual in class XnRegion

hasIntMember

public boolean hasIntMember(IntegerValue key)

Unboxed version. See class comment for XuInteger

hasMember

public boolean hasMember(Position pos)

Description copied from class: XnRegion

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.

Specified by:

hasMember in class XnRegion

intersects

public boolean intersects(XnRegion region)

Description copied from class: XnRegion

Essential. tell whether it has any points in common

Overrides:

intersects in class XnRegion

isBoundedAbove

public boolean isBoundedAbove()

Either I extend indefinitely to plus infinity, or I am bounded above, not both. The empty region is bounded above despite the fact that it has no upper edge.

isBoundedBelow

public boolean isBoundedBelow()

Either I extend indefinitely to minus infinity, or I am bounded below, not both. The empty region is bounded below despite the fact that it has no lower bound.

isEmpty

public boolean isEmpty()

Description copied from class: XnRegion

Every coordinate space has exactly one empty region. It is the one containing no positions. It and only it responds 'true' to this message.

Specified by:

isEmpty in class XnRegion

isEqual

public boolean isEqual(Heaper other)

Description copied from class: XnRegion

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

Specified by:

isEqual in class XnRegion

isFinite

public boolean isFinite()

Description copied from class: XnRegion

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.

Specified by:

isFinite in class XnRegion

isFull

public boolean isFull()

Description copied from class: XnRegion

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

Overrides:

isFull in class XnRegion

isSimple

public boolean isSimple()

Inequalities and intervals are both simple. See class comment

Specified by:

isSimple in class XnRegion

isSubsetOf

public boolean isSubsetOf(XnRegion other)

Description copied from class: XnRegion

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)

Overrides:

isSubsetOf in class XnRegion

complement

public XnRegion complement()

Description copied from class: XnRegion

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

Specified by:

complement in class XnRegion

intersect

public XnRegion intersect(XnRegion region)

Description copied from class: XnRegion

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.

Specified by:

intersect in class XnRegion

simpleUnion

public XnRegion simpleUnion(XnRegion otherRegion)

The result is the smallest simple region which satisfies the spec in XuRegion::simpleUnion

Specified by:

simpleUnion in class XnRegion

unionWith

public XnRegion unionWith(XnRegion region)

Description copied from class: XnRegion

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.

Specified by:

unionWith in class XnRegion

with

public XnRegion with(Position position)

Description copied from class: XnRegion

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

Overrides:

with in class XnRegion

withInt

public XnRegion withInt(IntegerValue pos)

intervals

public Stepper intervals()

count

public IntegerValue count()

Description copied from class: XnRegion

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

Specified by:

count in class XnRegion

intervals

public Stepper intervals(OrderSpec order)

Essential. Break this into an ascending sequence of disjoint intervals (which may be unbounded).

isEnumerable

public boolean isEnumerable(OrderSpec order)

Actually uses the 'order' argument correctly to enumerate the positions. Treats null the same as ascending. Iff I am bounded left am I enumerable in ascending order. Similarly, only if I am bounded right am I enumerable in descending order.

Specified by:

isEnumerable in class XnRegion

isInterval

public boolean isInterval()

Whether this Region is a non-empty interval, i.e. if A, B in the Region and A <= C <= B then C is in the Region. This includes inequalities (e.g. {x | x > 5}) and the fullRegion in addition to ordinary two-ended intervals.

distinctions

public ScruSet distinctions()

Description copied from class: XnRegion

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.

Specified by:

distinctions in class XnRegion

simpleRegions

public Stepper simpleRegions(OrderSpec order)

Treats NULL the same as ascending. For the moment, will only work with an ascending OrderSpec. If a descending OrderSpec is provided, it will currently BLAST, but later will work correctly. Returns a stepper on a disjoint set of simple regions in ascending order. No difference with disjointSimpleRegions

Specified by:

simpleRegions in class XnRegion

secretTransitions

protected IntegerVarArray secretTransitions()

The actuall array. DO NOT MODIFY

simpleRegionAtIndex

protected IntegerRegion simpleRegionAtIndex(int i)

the simple region at the given index in the transition array

edgeStepper

protected IntegerEdgeStepper edgeStepper()

Do not send from outside the module. This should not be exported outside the module, but to not export it in this case is some trouble.

transitionCount

protected int transitionCount()

Do not send from outside the module. This should not be exported outside the module, but to not export it in this case is some trouble. It is used for an efficiency hack in PointRegion.

chooseOne

public Position chooseOne(OrderSpec order)

Description copied from class: XnRegion

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.

Overrides:

chooseOne in class XnRegion

actualStepper

public Stepper actualStepper(OrderSpec order)

Iff I am bounded left am I enumerable in ascending order. Similarly, only if I am bounded right am I enumerable in descending order.

Specified by:

actualStepper in class XnRegion

sendSelfTo

public void sendSelfTo(Xmtr xmtr)

Overrides:

sendSelfTo in class Heaper