Class Geost

All Implemented Interfaces:
RemoveLevelLate, Stateful, UsesQueueVariable

public class Geost extends Constraint implements UsesQueueVariable, Stateful, RemoveLevelLate
Version:
4.8

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.

  • Field Details

    • DEBUG_ALL

      static final boolean DEBUG_ALL
      It 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 filteredConstraintCount
      It counts how many constraints we discounted in outbox generation procedure as not useful ones.
    • pruneMinCount

      long pruneMinCount
      It counts the number of times the minimum values of geost objects origins are being examined for pruning.
    • pruneMaxCount

      long pruneMaxCount
      It 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 findForbiddenDomainCount
      It counts number of executions of outboxes generation.
    • onObjectUpdateCount

      long onObjectUpdateCount
      It counts the number of object updates.
    • isFeasibleCount

      long isFeasibleCount
      It counts how many times the feasibility check is being performed by internal constraint on a supplied point.
    • queuedObjectCount

      long queuedObjectCount
      It counts how many times the object has been queued.
    • idNumber

      static AtomicInteger idNumber
      It specifies the unique number used to differentiate geost constraints.
    • inConsistency

      boolean inConsistency
      It indicates whether we are currently running the consistency function or not.
    • allLinked

      boolean allLinked
      If equal to true then modifying one object implies that all objects have to be added to object queue.
    • changedShapeID

      boolean changedShapeID
      It 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 enforceNoSkip
      if set to true, a variable will never be skipped, even if grounded and not in queue
    • firstConsistencyCheck

      boolean firstConsistencyCheck
      It 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 firstConsistencyLevel
      It 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[] pruneIfGrounded
      It 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

      final Map<Var,GeostObject> variableObjectMap
      It maps any variable in the scope of the geost constraint to the object it belongs to.
    • variableQueue

      LinkedHashSet<Var> variableQueue
      It stores all variables which have changed outside the consistency function of this constraint.
    • lastLevelLastVar

      TimeStamp<Integer> lastLevelLastVar
      It stores the position of the last variable grounded in the previous level.
    • objectList

      It contains all the objects which have been updated in the previous levels.
    • updatedObjectSet

      Set<GeostObject> updatedObjectSet
      It 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

      TimeStamp<Integer> 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

      It contains objects that need to be checked in the next sweep.
    • shapeIdsToPrune

      final int[] shapeIdsToPrune
      It 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 partialShapeSweep
      set to false to disable relaxed shape pruning
    • internalConstraints

      public Collection<InternalConstraint> 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>[] objectConstraints
      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. This is the input set to the filtering process before pruning any object.
    • domainHolesConstraints

      final DomainHoles[] domainHolesConstraints
      It stores the special constraints responsible for the handling of holes in the domain. It is indexed by object id.
    • order

      public final LexicographicalOrder 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[] c
      A preallocated array of ints used extensively within sweeping algorithm.
    • n

      final int[] n
      A preallocated array of ints used extensively within sweeping algorithm.
    • store

      protected Store store
      It keeps a reference to the store.
    • groundedVars

      final SimpleArrayList<Var> groundedVars
      It stores all variables which have been grounded. It is used to upon backtracking to update objects to their previous state.
    • stillUsefulInternalConstraints

      InternalConstraint[] stillUsefulInternalConstraints
      It 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 lastConstraintToCheck
      It specifies the last useful constraint in the array of useful internal constraints.
    • filterUseless

      public final boolean filterUseless
      It 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 alwaysUseFrames
      It 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 backtracking
      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.
    • fullyPruned

      final boolean[] fullyPruned
      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. 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

      final SimpleHashSet<GeostObject> 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

      final SimpleArrayList<DBox> 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 dimension
      It specifies the number of dimensions of each object given to the geost constraint.
    • oneTimeVarChanged

      private boolean oneTimeVarChanged
      It 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> objectList4Flush
      It is used inside flushQueue function to separate timeconsistency execution from object update (potentially expensive if for example object frame is recomputed).
    • objects

      public final GeostObject[] 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

      public final ExternalConstraint[] 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

      public final Shape[] 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 removeLimit
      It 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

      public Geost(GeostObject[] objects, ExternalConstraint[] constraints, Shape[] shapes)
      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

      public String 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

      public final Shape getShape(int id)
      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

      protected int pruneMin(Store store, GeostObject o, int currentShape, int d, int limit)
      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 store
      o - the object to prune
      currentShape - the shape of the object
      d - the current most significant dimension
      limit - 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

      protected int pruneMax(Store store, GeostObject o, int currentShape, int d, int limit)
      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 store
      o - the object to prune
      d - the current most significant dimension
      currentShape - the shape of the object
      limit - 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

      public void consistency(Store store)
      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 class Constraint
      Parameters:
      store - constraint store within which the constraint consistency is being checked.
    • updateInternalConstraintsGeneratingOutboxes

      protected void updateInternalConstraintsGeneratingOutboxes(GeostObject o)
      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

      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.
      Parameters:
      variables - variables in the queue
    • queueObject

      public final void queueObject(GeostObject o)
      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

      protected void onObjectUpdate(GeostObject o)
      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

      public int getConsistencyPruningEvent(Var var)
      Description copied from class: Constraint
      It retrieves the pruning event which causes reevaluation of the constraint.
      Overrides:
      getConsistencyPruningEvent in class Constraint
      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 class Constraint
    • impose

      public void impose(Store store)
      Description copied from class: Constraint
      It imposes the constraint in a given store.
      Overrides:
      impose in class Constraint
      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 class Constraint
    • queueVariable

      public void queueVariable(int level, Var v)
      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 class Constraint
      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 interface Stateful
      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 interface RemoveLevelLate
      Parameters:
      level - the level which is being removed.
    • toString

      public String toString()
      Description copied from class: Constraint
      It produces a string representation of a constraint state.
      Overrides:
      toString in class Constraint
    • getStatistics

      public List<Long> getStatistics()
      It returns all the statistics gathered by geost constraint during the search.
      Returns:
      an array list consisting of different statistics collected during search.