Class GCC

    • Field Detail

      • firstConsistencyCheck

        boolean firstConsistencyCheck
        TODO An improvement to increase the incrementality even further.

        1. The first matching uses minimal values. Remember which minimal value has changed which removed from the domain the value which was used in the matching. Reuse from old matching 1 all values smaller than the minimal which has changed.

        Similar principle applies to matching 2 (skip the positions (variables) until the first index for which m1 did change or for which the m2 value is no longer in the domain.

        2. Use IndexDomainView instead of local solution.

        3. boolean variable first - is it only once in the consistency function? Then this functionality can be moved out of the while(newPropagation), if it should be executed every time consistency is executed then (it should be setup to true somewhere).

      • idNumber

        static java.util.concurrent.atomic.AtomicInteger idNumber
      • match1

        private int[] match1
        The array which stores the first computed matching, which may not take into account the lower bound of count variables.
      • match2

        private int[] match2
        The array which stores the second computed matching, which may not take into account the upper bound of count variables.
      • match3

        private int[] match3
        The array which stores the third proper matching, constructed from the first one and second one so both lower and upper bounds are respected.
      • match1XOrder

        private int[] match1XOrder
      • match2XOrder

        private int[] match2XOrder
      • nbOfMatchPerY

        private int[] nbOfMatchPerY
      • compOfY

        private int[] compOfY
      • yDomain

        private int[][] yDomain
      • xSize

        private int xSize
      • ySize

        private int ySize
      • S1

        private java.util.ArrayDeque<java.lang.Integer> S1
      • pFirst

        private java.util.PriorityQueue<GCC.XDomain> pFirst
      • pSecond

        private java.util.PriorityQueue<GCC.XDomain> pSecond
      • pCount

        private java.util.PriorityQueue<java.lang.Integer> pCount
      • domainHash

        private int[] domainHash
      • xNodesHash

        private java.util.Map<IntVar,​java.lang.Integer> xNodesHash
      • xVariableToChange

        private java.util.Set<IntVar> xVariableToChange
      • stampValue

        private int stampValue
      • firstConsistencyLevel

        int firstConsistencyLevel
      • x

        public IntVar[] x
        It specifies variables x whose values are counted.
      • counters

        private IntVar[] counters
        It species variables counters for counting occurences of each possible value from the intial domain of x variables.
      • compareLowerBound

        private java.util.Comparator<GCC.XDomain> compareLowerBound
      • sortPriorityMinOrder

        private java.util.Comparator<GCC.XDomain> sortPriorityMinOrder
      • sortPriorityMaxOrder

        private java.util.Comparator<java.lang.Integer> sortPriorityMaxOrder
      • zeroCounters

        private java.util.Set<IntVar> zeroCounters
      • changedVariables

        private java.util.Set<Var> changedVariables
        Fix suggested by Radek: a set that keeps track of the variables that have changed and need to be revisited in the consistency method
    • Constructor Detail

      • GCC

        public GCC​(IntVar[] x,
                   IntVar[] counters)
        It constructs global cardinality constraint.
        Parameters:
        x - variables which values are counted.
        counters - variables which count the values.
      • GCC

        public GCC​(java.util.List<? extends IntVar> x,
                   java.util.List<? extends IntVar> counters)
        It constructs global cardinality constraint.
        Parameters:
        x - variables which values are counted.
        counters - variables which count the values.
    • Method Detail

      • removeZeroCounters

        private IntVar[] removeZeroCounters​(IntVar[] x,
                                            IntVar[] counters)
      • 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.
      • 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.
      • checkXorder

        private boolean checkXorder()
        A method to be called in asserts that checks whether all grounded X variables are correctly put at the end of the list
        Returns:
        false if the X variable order is inconsistent
      • 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.
      • queueVariable

        public void queueVariable​(int level,
                                  Var var)
        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.
        var - variable which has changed.
      • satisfied

        public boolean satisfied()
        Description copied from interface: SatisfiedPresent
        It checks if the constraint is satisfied. It can return false even if constraint is satisfied but not all variables in its scope are grounded. It needs to return true if all variables in its scope are grounded and constraint is satisfied.

        Implementations of this interface for constraints that are not PrimitiveConstraint may require constraint imposition and consistency check as a requirement to work correctly.

        Specified by:
        satisfied in interface SatisfiedPresent
        Returns:
        true if constraint is possible to verify that it is satisfied.
      • 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
      • FindGeneralizedMatching

        private void FindGeneralizedMatching()
      • checkFirstPass

        private boolean checkFirstPass()
      • checkSecondPass

        private boolean checkSecondPass()
      • checkThirdPass

        private boolean checkThirdPass()
      • firstPass

        private void firstPass()
      • secondPass

        private void secondPass()
      • thirdPass

        private void thirdPass()
      • SCCs

        private void SCCs()
      • SCCsWithoutS

        private int SCCsWithoutS​(int[] compReachesLeft,
                                 int[] compReachesRight,
                                 int[] yReachesLeft,
                                 int[] yReachesRight)
      • ReachedFromY

        private void ReachedFromY​(int[] yReachesLeft,
                                  int[] yReachesRight)
      • putToTheEnd

        private void putToTheEnd​(IntVar[] list,
                                 int element)
      • countBoundConsistency

        private void countBoundConsistency​(Store store)
      • upperCount

        private void upperCount​(int[] max_u)
      • lowerCount

        private void lowerCount​(int[] min_l)
      • sortXByDomainMin

        private void sortXByDomainMin()
      • findPosition

        private int findPosition​(int value,
                                 int[] values)