Package org.jacop.constraints

Class GCC

java.lang.Object
org.jacop.constraints.DecomposedConstraint<Constraint>
org.jacop.constraints.Constraint
org.jacop.constraints.GCC
All Implemented Interfaces:
SatisfiedPresent, Stateful, UsesQueueVariable
public class GCC extends Constraint implements UsesQueueVariable, Stateful, SatisfiedPresent
GCC constraint counts the number of occurences of given values in x variables. The counters are specified by y's. The occurence of all values in the domain of xs is counted.

We would like to thank Irit Katriel for making the code of GCC in C she wrote available to us.

Version:
4.10

  • Field Details

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

    • xDomain

      private GCC.XDomain[] xDomain

    • yDomain

      private int[][] yDomain

    • xSize

      private int xSize

    • ySize

      private int ySize

    • S1

      private ArrayDeque<Integer> S1

    • S2

      private ArrayDeque<GCC.Component> S2

    • pFirst

      private PriorityQueue<GCC.XDomain> pFirst

    • pSecond

      private PriorityQueue<GCC.XDomain> pSecond

    • pCount

      private PriorityQueue<Integer> pCount

    • debug

      private static final boolean debug
      See Also:

    • domainHash

      private int[] domainHash

    • xNodesHash

      private Map<IntVar,Integer> xNodesHash

    • xVariableToChange

      private Set<IntVar> xVariableToChange

    • stamp

      TimeStamp<Integer> stamp

    • stampValue

      private int stampValue

    • firstConsistencyLevel

      int firstConsistencyLevel

    • x

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

    • counters

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

    • compareLowerBound

      private Comparator<GCC.XDomain> compareLowerBound

    • sortPriorityMinOrder

      private Comparator<GCC.XDomain> sortPriorityMinOrder

    • sortPriorityMaxOrder

      private Comparator<Integer> sortPriorityMaxOrder

    • zeroCounters

      private Set<IntVar> zeroCounters

    • changedVariables

      private 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 Details

    • 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(List<? extends IntVar> x, List<? extends IntVar> counters)
      It constructs global cardinality constraint.
      Parameters:
      x - variables which values are counted.
      counters - variables which count the values.

  • Method Details

    • 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

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

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