Class Geost
- All Implemented Interfaces:
RemoveLevelLate
,Stateful
,UsesQueueVariable
- Version:
- 4.9
1) DONE. FlushAndQueue function should be changed and some functionality moved to firstConsistencyCheck.
2) DONE. No propagation inside queueVariable function.
3) DONE. How to incorporate GUI code within Geost constraint.
4) DONE. Move part of the functionality of onObjectUpdate to consistency function.
5) Refactor use of TimeBoundConstraint 5b) DONE. remove runTimeConstraint boolean variable.
6) DONE. asserts for Shape register 6b) asserts about possible values of MaxInt and MinInt.
7) DONE. Use simpleHashSet instead of LinkedHashSet for objectQueue.
8) DONE. Discuss pruning events, do we really need ANY for all variables? For example, maybe time variables always BOUND pruning event.
9) DONE. Simplify queueObject by removing if statements and make sure that this function is being called properly (avoid non-asserts checks inside it).
10) DONE. Discuss the possible implementation of satisfied function.
11) Introduce time switch so geost can work without time dimension.
12) Lessen the feature of geost that it does not work with variables used multiple times within different objects 12b) DONE. (at least for singleton variables).
13) DONE. Verify fix to address bug in case of multiple level removals, or level removals for which no consistency function has been called. Functionality around variable currentLevel. It is still needed.
14. DONE. Fixing a bug connected with timestamps and multiple remove levels calls. 14b Check lastLevelVar (possibly needs to be done similarly as setStart).
Future Work :
1. InArea should support subset of objects and dimensions.
2. Reuse previously generated outboxes. Create a function to create a hashkey from points coordinates for which an outbox is required. Later, for each new point we check if we have proper outbox for a given hash-key generated from this outbox.
3. Not always finishing at consistency fixpoint, speculative fixpoint.
4. consider polymorphism due to rotations only, and see if better performance can be reached under this assumption.
5. If objects have the same shape, and they are indistingushable then symmetry breaking can be employed.
-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescription(package private) boolean
If equal to true then modifying one object implies that all objects have to be added to object queue.boolean
It defines whether outbox generation should always rely on overlapping frames.boolean
It is a flag set to true during remove level late function execution so objects which are being updated upon backtracking can be handled properly.(package private) final int[]
A preallocated array of ints used extensively within sweeping algorithm.(package private) boolean
It is used to signal that some shape ID was pruned.private int
(package private) static final boolean
It specifies different debugging switches to print out diverse information about execution of the geost constraint.(package private) static final boolean
(package private) static final boolean
(package private) static final boolean
(package private) static final boolean
(package private) static final boolean
(package private) static final boolean
(package private) static final boolean
(package private) static final boolean
(package private) final int
It specifies the number of dimensions of each object given to the geost constraint.(package private) final DomainHoles[]
It stores the special constraints responsible for the handling of holes in the domain.boolean
if set to true, a variable will never be skipped, even if grounded and not in queuefinal ExternalConstraint[]
It stores the reference to the collection of external constraints which must be satisfied within this constraint.(package private) long
It counts how many constraints we discounted in outbox generation procedure as not useful ones.final boolean
It specifies that filtering of useless internal constraint takes place before an object is being pruned.(package private) long
It counts number of executions of outboxes generation.(package private) boolean
It remembers if it is the first time the consistency check is being performed.(package private) int
It remembers the level at which the consistency function was applied for the first time.(package private) final boolean[]
If running a complete sweep for each shape is costly, because some shapes may require a significant sweep, even though a weaker bound has already been found.(package private) static final boolean
(package private) final SimpleArrayList
<Var> It stores all variables which have been grounded.(package private) static AtomicInteger
It specifies the unique number used to differentiate geost constraints.(package private) boolean
It indicates whether we are currently running the consistency function or not.It stores all generated internal constraints for all objects/constraints.(package private) long
It counts how many times the feasibility check is being performed by internal constraint on a supplied point.(package private) int
It specifies the last useful constraint in the array of useful internal constraints.It stores the position of the last variable grounded in the previous level.(package private) final int[]
A preallocated array of ints used extensively within sweeping algorithm.(package private) Set<InternalConstraint>[]
For each object, the set of constraint that apply to it we use object ids as keys, and can thus use an array to store the map.(package private) SimpleArrayList
<GeostObject> It contains all the objects which have been updated in the previous levels.(package private) SimpleArrayList
<GeostObject> It is used inside flushQueue function to separate timeconsistency execution from object update (potentially expensive if for example object frame is recomputed).(package private) SimpleHashSet
<GeostObject> It contains objects that need to be checked in the next sweep.final GeostObject[]
It stores the reference to the collection of objects provided to the constructor.private boolean
It is set by queueVariable after a time variable has been changed.(package private) long
It counts the number of object updates.final LexicographicalOrder
It specifies the order between dimensions which is used by the pruning algorithm.boolean
set to false to disable relaxed shape pruning(package private) final boolean[]
It specifies for each object if consistency function should be run if this object becomes grounded.(package private) long
It counts the number of times the minimum values of geost objects origins are being examined for pruning.(package private) long
It counts the number of times the minimum values of geost objects origins are being examined for pruning.(package private) long
It counts how many times the object has been queued.private int
It specifies the first position of the variables being removed from grounded list upon backtracking.it stores the index of the first object which have changed at current level.(package private) final int[]
It is a locally used array which stores the enumeration of values for the current shape variable.final Shape[]
It stores information about shapes used by objects within this geost constraint.(package private) InternalConstraint[]
It contains all not filtered out, useful internal constraints which should be used to generate outboxes.protected Store
It keeps a reference to the store.(package private) final SimpleHashSet
<GeostObject> It stores temporarily objects for which pruning is suggested by external constraints.(package private) Set
<GeostObject> It contains all the objects which have been updated at current level.(package private) final Map
<Var, GeostObject> It maps any variable in the scope of the geost constraint to the object it belongs to.(package private) LinkedHashSet
<Var> It stores all variables which have changed outside the consistency function of this constraint.(package private) final SimpleArrayList
<DBox> A temporary list to collect bounding boxes for each shape of the given object to compute one bounding box whatever the shape of the object.Fields inherited from class org.jacop.constraints.Constraint
atomicExecution, consistencyPruningEvents, constraintScope, earlyTerminationOK, increaseWeight, numberId, scope, trace
Fields inherited from class org.jacop.constraints.DecomposedConstraint
queueIndex
-
Constructor Summary
ConstructorsConstructorDescriptionGeost
(Collection<GeostObject> objects, Collection<ExternalConstraint> constraints, Collection<Shape> shapes) Geost
(GeostObject[] objects, ExternalConstraint[] constraints, Shape[] shapes) It creates a geost constraint from provided objects, external constraints, as well as shapes. -
Method Summary
Modifier and TypeMethodDescriptionIt checks that this constraint has consistent data structures.void
consistency
(Store store) It is a (most probably incomplete) consistency function which removes the values from variables domains.protected DBox
findForbiddenDomain
(GeostObject o, int currentShape, int[] point, Geost.SweepDirection dir, LexicographicalOrder order) protected void
flushQueue
(Collection<Var> variables) It does the processing needed given the set of variables that was updated between two consecutive calls to the consistency function.protected void
int
It retrieves the pruning event which causes reevaluation of the constraint.int
final Shape
getShape
(int id) It returns the shape with a given id if such exists.It returns all the statistics gathered by geost constraint during the search.void
It imposes the constraint in a given store.void
It increases the weight of the variables in the constraint scope.protected void
It performs the necessary operations for a given changed object.protected int
pruneMax
(Store store, GeostObject o, int currentShape, int d, int limit) the sweeping routine for minimal bounds.protected int
pruneMin
(Store store, GeostObject o, int currentShape, int d, int limit) the sweeping routine for minimal bounds.final void
It puts the object into the queue if it can be still pruned or cause failure.void
queueVariable
(int level, Var v) This is a function called to indicate which variable in a scope of constraint has changed.void
removeLevel
(int level) This function is called in case of the backtrack, so a constraint can clear the queue of changed variables which is no longer valid.void
removeLevelLate
(int level) This function is called in case of the backtrack.toString()
It produces a string representation of a constraint state.protected void
It is called whenever the object currently being pruned changes.Methods inherited from class org.jacop.constraints.Constraint
afc, arguments, cleanAfterFailure, decompose, getGuideConstraint, getGuideValue, getGuideVariable, grounded, grounded, id, impose, imposeDecomposition, intArrayToString, long2int, numberArgs, removeConstraint, requiresMonotonicity, setConsistencyPruningEvent, setConstraintScope, setScope, setScope, setScope, setScope, setScope, setWatchedVariableGrounded, supplyGuideFeedback, updateAFC, watchedVariableGrounded
Methods inherited from class org.jacop.constraints.DecomposedConstraint
auxiliaryVariables, checkInput, checkInput, checkInputForDuplication, checkInputForDuplicationSkipSingletons, checkInputForNullness, checkInputForNullness, checkInputForNullness, derivative, getDubletonsSkipSingletons, imposeDecomposition
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface org.jacop.api.Stateful
isStateful
-
Field Details
-
DEBUG_ALL
static final boolean DEBUG_ALLIt specifies different debugging switches to print out diverse information about execution of the geost constraint.- See Also:
-
DEBUG_MAIN
static final boolean DEBUG_MAIN- See Also:
-
DEBUG_SUBSETS
static final boolean DEBUG_SUBSETS- See Also:
-
DEBUG_DOUBLE_LAYER
static final boolean DEBUG_DOUBLE_LAYER- See Also:
-
DEBUG_SHAPE_SKIP
static final boolean DEBUG_SHAPE_SKIP- See Also:
-
DEBUG_VAR_SKIP
static final boolean DEBUG_VAR_SKIP- See Also:
-
DEBUG_OBJECT_GROUNDING
static final boolean DEBUG_OBJECT_GROUNDING- See Also:
-
DEBUG_BACKTRACK
static final boolean DEBUG_BACKTRACK- See Also:
-
GATHER_STATS
static final boolean GATHER_STATS- See Also:
-
DEBUG_REORDER
static final boolean DEBUG_REORDER- See Also:
-
filteredConstraintCount
long filteredConstraintCountIt counts how many constraints we discounted in outbox generation procedure as not useful ones. -
pruneMinCount
long pruneMinCountIt counts the number of times the minimum values of geost objects origins are being examined for pruning. -
pruneMaxCount
long pruneMaxCountIt counts the number of times the minimum values of geost objects origins are being examined for pruning. It may be different (smaller than) prunedMinCount as constraint may have failed during min domain pruning. -
findForbiddenDomainCount
long findForbiddenDomainCountIt counts number of executions of outboxes generation. -
onObjectUpdateCount
long onObjectUpdateCountIt counts the number of object updates. -
isFeasibleCount
long isFeasibleCountIt counts how many times the feasibility check is being performed by internal constraint on a supplied point. -
queuedObjectCount
long queuedObjectCountIt counts how many times the object has been queued. -
idNumber
It specifies the unique number used to differentiate geost constraints. -
inConsistency
boolean inConsistencyIt indicates whether we are currently running the consistency function or not. -
allLinked
boolean allLinkedIf equal to true then modifying one object implies that all objects have to be added to object queue. -
changedShapeID
boolean changedShapeIDIt is used to signal that some shape ID was pruned. It is required because pruning skip condition (var grounded, and not in the queue) can only be safely used if no shape id field was pruned. Indeed, if some shape ID was pruned, feasibility can change, thus a check is needed. -
enforceNoSkip
public boolean enforceNoSkipif set to true, a variable will never be skipped, even if grounded and not in queue -
firstConsistencyCheck
boolean firstConsistencyCheckIt remembers if it is the first time the consistency check is being performed. If not, then the initial consistency checks which have to be done only once will be done during the first consistency check. This flag is set back to true if the remove level function is removing the level onto which the changes caused by the initial consistency were applied to. -
firstConsistencyLevel
int firstConsistencyLevelIt remembers the level at which the consistency function was applied for the first time. If that level is being removed then the initial consistency function must be executed again. -
pruneIfGrounded
final boolean[] pruneIfGroundedIt specifies for each object if consistency function should be run if this object becomes grounded. It is set to true if the object was grounded outside consistency function call or after a shape variable has been changed. It is set to false only after exactly one consistency check during which the object was grounded. -
variableObjectMap
It maps any variable in the scope of the geost constraint to the object it belongs to. -
variableQueue
LinkedHashSet<Var> variableQueueIt stores all variables which have changed outside the consistency function of this constraint. -
lastLevelLastVar
It stores the position of the last variable grounded in the previous level. -
objectList
SimpleArrayList<GeostObject> objectListIt contains all the objects which have been updated in the previous levels. -
updatedObjectSet
Set<GeostObject> updatedObjectSetIt contains all the objects which have been updated at current level. The objects from this set are moved to the array objectList as soon as level is increased. If level is being removed then for every object in this set we inform the external constraints that their state in connection to this object may have changed. -
setStart
it stores the index of the first object which have changed at current level. It allows to inform the external constraints about objects being changed due to backtracking. -
objectQueue
SimpleHashSet<GeostObject> objectQueueIt contains objects that need to be checked in the next sweep. -
shapeIdsToPrune
final int[] shapeIdsToPruneIt is a locally used array which stores the enumeration of values for the current shape variable. The enumeration is lexicographical with one exception the previously found best shape is put on the first position. -
partialShapeSweep
public boolean partialShapeSweepset to false to disable relaxed shape pruning -
internalConstraints
It stores all generated internal constraints for all objects/constraints. It is used to speed up some visualization functions. If not for that reason it could have been a local variable within a function generating internal constraints. -
objectConstraints
Set<InternalConstraint>[] objectConstraintsFor each object, the set of constraint that apply to it we use object ids as keys, and can thus use an array to store the map. This is the input set to the filtering process before pruning any object. -
domainHolesConstraints
It stores the special constraints responsible for the handling of holes in the domain. It is indexed by object id. -
order
It specifies the order between dimensions which is used by the pruning algorithm. The order may have influence on the algorithm efficiency. The geost constraint chooses the order based on average length of objects in the particular dimension. The dimension with higher average length in this dimension will have the preference. -
c
final int[] cA preallocated array of ints used extensively within sweeping algorithm. -
n
final int[] nA preallocated array of ints used extensively within sweeping algorithm. -
store
It keeps a reference to the store. -
groundedVars
It stores all variables which have been grounded. It is used to upon backtracking to update objects to their previous state. -
stillUsefulInternalConstraints
InternalConstraint[] stillUsefulInternalConstraintsIt contains all not filtered out, useful internal constraints which should be used to generate outboxes. The initial array of internal constraints associate with a given object being pruned can be significantly shrank and the remaining objects (still useful) are store in this array. -
lastConstraintToCheck
int lastConstraintToCheckIt specifies the last useful constraint in the array of useful internal constraints. -
filterUseless
public final boolean filterUselessIt specifies that filtering of useless internal constraint takes place before an object is being pruned. It may be costly for small instances.- See Also:
-
alwaysUseFrames
public boolean alwaysUseFramesIt defines whether outbox generation should always rely on overlapping frames. For problems that contain objects that have small domains compared to their size, then using only frames may provide a better performance (up to 50% faster). It can only be changed before impose() function, changing it afterwards will lead to improper behavior. -
backtracking
public boolean backtrackingIt is a flag set to true during remove level late function execution so objects which are being updated upon backtracking can be handled properly. -
fullyPruned
final boolean[] fullyPrunedIf running a complete sweep for each shape is costly, because some shapes may require a significant sweep, even though a weaker bound has already been found. However, to be able to prune shapes, such a costly sweep needs to be done. A tradeoff solution consists in running a complete sweep for each shape once per node, and optimize the following runs. This implies remembering which object have already been fully pruned. -
temporaryObjectSet
It stores temporarily objects for which pruning is suggested by external constraints. The geost constraint checks every object from this set to see if that is actually necessary to invoke the pruning for that object. -
workingList
A temporary list to collect bounding boxes for each shape of the given object to compute one bounding box whatever the shape of the object. It is made as a member of the geost constraint to avoid multiple memory allocations. -
dimension
final int dimensionIt specifies the number of dimensions of each object given to the geost constraint. -
oneTimeVarChanged
private boolean oneTimeVarChangedIt is set by queueVariable after a time variable has been changed. It indicates that we should run the consistency function of the time constraint. -
objectList4Flush
SimpleArrayList<GeostObject> objectList4FlushIt is used inside flushQueue function to separate timeconsistency execution from object update (potentially expensive if for example object frame is recomputed). -
objects
It stores the reference to the collection of objects provided to the constructor. It does not perform cloning so the collection can not change after geost constraint was imposed. -
externalConstraints
It stores the reference to the collection of external constraints which must be satisfied within this constraint. This is a reference to the collection provided within the constructor. No copying is employed therefore the collection can not change even after the constraint is imposed. -
shapeRegister
It stores information about shapes used by objects within this geost constraint. It is based on shapes information provided in the constructor. -
currentLevel
private int currentLevel -
removeLimit
private int removeLimitIt specifies the first position of the variables being removed from grounded list upon backtracking.If there is no change in lastLevelVar.value between removeLevel ( stored in removeLimit) and removeLevelLate then this indicates that no variable was grounded at removed level.
-
-
Constructor Details
-
Geost
public Geost(Collection<GeostObject> objects, Collection<ExternalConstraint> constraints, Collection<Shape> shapes) -
Geost
It creates a geost constraint from provided objects, external constraints, as well as shapes. The construct parameters are not cloned so do not reuse them in creation in other constraints if changes are necessary. Make sure that the largest object id is as small as possible to avoid unnecessary memory cost.- Parameters:
objects
- objects in the scope of the geost constraint.constraints
- the collection of external constraints enforced by geost.shapes
- the list of different shapes used by the objects in scope of the geost.
-
-
Method Details
-
checkInvariants
It checks that this constraint has consistent data structures.- Returns:
- a string describing the consistency problem with data structures, null if no problem encountered.
-
getShape
It returns the shape with a given id if such exists.- Parameters:
id
- the unique id of the shape we are looking for.- Returns:
- the shape of a given id previously provided.
-
genInternalConstraints
protected void genInternalConstraints() -
pruneMin
the sweeping routine for minimal bounds. Since in the polymorphic case, it is run for each possible shape, and only the weakest result is used, it cannot have side-effects. In particular, it cannot directly update domain values. If any data structure is updated here, make sure that it is done carefully enough.- Parameters:
store
- the storeo
- the object to prunecurrentShape
- the shape of the objectd
- the current most significant dimensionlimit
- stop pruning if going beyond this value- Returns:
- the bound found if there is one, and Constants.MaxInt if there is no feasible placement.
-
pruneMax
the sweeping routine for minimal bounds. Since in the polymorphic case, it is run for each possible shape, and only the weakest result is used, it cannot have side-effects. In particular, it cannot directly update domain values. If any data structure is updated here, make sure that it is done carefully enough.- Parameters:
store
- the storeo
- the object to prunecurrentShape
- the shape of the objectd
- the current most significant dimensionlimit
- stop pruning if going beyond this value- Returns:
- the bound found if there is one, and Constants.MinInt if there is no feasible placement.
-
findForbiddenDomain
protected DBox findForbiddenDomain(GeostObject o, int currentShape, int[] point, Geost.SweepDirection dir, LexicographicalOrder order) -
consistency
Description copied from class:Constraint
It is a (most probably incomplete) consistency function which removes the values from variables domains. Only values which do not have any support in a solution space are removed.- Specified by:
consistency
in classConstraint
- Parameters:
store
- constraint store within which the constraint consistency is being checked.
-
updateInternalConstraintsGeneratingOutboxes
It is called whenever the object currently being pruned changes. useful for constraint pruning version of Geost.- Parameters:
o
- the object currently being pruned for which internal constraints are being filtered.
-
flushQueue
It does the processing needed given the set of variables that was updated between two consecutive calls to the consistency function.- Parameters:
variables
- variables in the queue
-
queueObject
It puts the object into the queue if it can be still pruned or cause failure.- Parameters:
o
- the object which is possibly put into the queue.
-
onObjectUpdate
It performs the necessary operations for a given changed object.If the change occurred due to backtracking then only external constraints are being informed about the change, so they can restore proper state in connection to the object. If this function is not called during backtracking then also the following is executed.
If the change occurs due to search progress downwards then it stores the information about object change as well as schedules pruning check for all connected objects.
- Parameters:
o
- the object which had a domain change
-
getConsistencyPruningEvent
Description copied from class:Constraint
It retrieves the pruning event which causes reevaluation of the constraint.- Overrides:
getConsistencyPruningEvent
in classConstraint
- Parameters:
var
- variable for which pruning event is retrieved- Returns:
- it returns the int code of the pruning event (GROUND, BOUND, ANY, NONE)
-
getDefaultConsistencyPruningEvent
public int getDefaultConsistencyPruningEvent()- Specified by:
getDefaultConsistencyPruningEvent
in classConstraint
-
impose
Description copied from class:Constraint
It imposes the constraint in a given store.- Overrides:
impose
in classConstraint
- Parameters:
store
- the constraint store to which the constraint is imposed to.
-
increaseWeight
public void increaseWeight()Description copied from class:Constraint
It increases the weight of the variables in the constraint scope.- Overrides:
increaseWeight
in classConstraint
-
queueVariable
Description copied from class:Constraint
This is a function called to indicate which variable in a scope of constraint has changed. It also indicates a store level at which the change has occurred.- Overrides:
queueVariable
in classConstraint
- Parameters:
level
- the level of the store at which the change has occurred.v
- variable which has changed.
-
removeLevel
public void removeLevel(int level) Description copied from interface:Stateful
This function is called in case of the backtrack, so a constraint can clear the queue of changed variables which is no longer valid. This function is called *before* all timestamps, variables, mutablevariables have reverted to their previous value.- Specified by:
removeLevel
in interfaceStateful
- Parameters:
level
- the level which is being removed.
-
removeLevelLate
public void removeLevelLate(int level) Description copied from interface:RemoveLevelLate
This function is called in case of the backtrack. It is called after all timestamps, variables, mutablevariables have reverted to their values *after* removing the level.- Specified by:
removeLevelLate
in interfaceRemoveLevelLate
- Parameters:
level
- the level which is being removed.
-
toString
Description copied from class:Constraint
It produces a string representation of a constraint state.- Overrides:
toString
in classConstraint
-
getStatistics
It returns all the statistics gathered by geost constraint during the search.- Returns:
- an array list consisting of different statistics collected during search.
-