Class Geost

  • All Implemented Interfaces:
    RemoveLevelLate, Stateful, UsesQueueVariable

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

    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 Detail

      • 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:
        Constant Field Values
      • 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 java.util.concurrent.atomic.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 java.util.Map<Var,​GeostObject> variableObjectMap
        It maps any variable in the scope of the geost constraint to the object it belongs to.
      • variableQueue

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

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

        java.util.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<java.lang.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.
      • 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 java.util.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

        java.util.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:
        Constant Field Values
      • 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 Detail

      • 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 Detail

      • checkInvariants

        public java.lang.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.
      • 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​(java.util.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)
      • 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 java.lang.String toString()
        Description copied from class: Constraint
        It produces a string representation of a constraint state.
        Overrides:
        toString in class Constraint
      • getStatistics

        public java.util.List<java.lang.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.