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.8
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
GCC.Component
private static class
GCC.XDomain
-
Field Summary
Fields Modifier and Type Field Description 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 methodprivate java.util.Comparator<GCC.XDomain>
compareLowerBound
private int[]
compOfY
protected IntVar[]
counters
It species variables counters for counting occurences of each possible value from the intial domain of x variables.private static boolean
debug
private int[]
domainHash
(package private) boolean
firstConsistencyCheck
TODO An improvement to increase the incrementality even further.(package private) int
firstConsistencyLevel
(package private) static java.util.concurrent.atomic.AtomicInteger
idNumber
private int[]
match1
The array which stores the first computed matching, which may not take into account the lower bound of count variables.private int[]
match1XOrder
private int[]
match2
The array which stores the second computed matching, which may not take into account the upper bound of count variables.private int[]
match2XOrder
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.private int[]
nbOfMatchPerY
private java.util.PriorityQueue<java.lang.Integer>
pCount
private java.util.PriorityQueue<GCC.XDomain>
pFirst
private java.util.PriorityQueue<GCC.XDomain>
pSecond
private java.util.ArrayDeque<java.lang.Integer>
S1
private java.util.ArrayDeque<GCC.Component>
S2
private java.util.Comparator<java.lang.Integer>
sortPriorityMaxOrder
private java.util.Comparator<GCC.XDomain>
sortPriorityMinOrder
(package private) TimeStamp<java.lang.Integer>
stamp
private int
stampValue
IntVar[]
x
It specifies variables x whose values are counted.private GCC.XDomain[]
xDomain
private java.util.Map<IntVar,java.lang.Integer>
xNodesHash
private int
xSize
private java.util.Set<IntVar>
xVariableToChange
private int[][]
yDomain
private int
ySize
private java.util.Set<IntVar>
zeroCounters
-
Fields inherited from class org.jacop.constraints.Constraint
afcWeight, atomicExecution, consistencyPruningEvents, constraintScope, earlyTerminationOK, increaseWeight, numberId, scope, trace, watchedVariableGrounded
-
Fields inherited from class org.jacop.constraints.DecomposedConstraint
queueIndex
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private boolean
checkFirstPass()
private boolean
checkSecondPass()
private boolean
checkThirdPass()
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 listvoid
consistency(Store store)
It is a (most probably incomplete) consistency function which removes the values from variables domains.private void
countBoundConsistency(Store store)
private void
FindGeneralizedMatching()
private int
findPosition(int value, int[] values)
private void
firstPass()
int
getDefaultConsistencyPruningEvent()
void
impose(Store store)
It imposes the constraint in a given store.private void
lowerCount(int[] min_l)
private void
putToTheEnd(IntVar[] list, int element)
void
queueVariable(int level, Var var)
This is a function called to indicate which variable in a scope of constraint has changed.private void
ReachedFromY(int[] yReachesLeft, int[] yReachesRight)
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.private IntVar[]
removeZeroCounters(IntVar[] x, IntVar[] counters)
boolean
satisfied()
It checks if the constraint is satisfied.private void
SCCs()
private int
SCCsWithoutS(int[] compReachesLeft, int[] compReachesRight, int[] yReachesLeft, int[] yReachesRight)
private void
secondPass()
private void
sortXByDomainMin()
private void
thirdPass()
java.lang.String
toString()
It produces a string representation of a constraint state.private void
upperCount(int[] max_u)
-
Methods inherited from class org.jacop.constraints.Constraint
afc, arguments, cleanAfterFailure, decompose, getConsistencyPruningEvent, getGuideConstraint, getGuideValue, getGuideVariable, grounded, grounded, id, impose, imposeDecomposition, increaseWeight, intArrayToString, long2int, numberArgs, removeConstraint, requiresMonotonicity, setConsistencyPruningEvent, setConstraintScope, setScope, setScope, setScope, setScope, setScope, setWatchedVariableGrounded, supplyGuideFeedback, toInt, toInt, 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 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
-
xDomain
private GCC.XDomain[] xDomain
-
yDomain
private int[][] yDomain
-
xSize
private int xSize
-
ySize
private int ySize
-
S1
private java.util.ArrayDeque<java.lang.Integer> S1
-
S2
private java.util.ArrayDeque<GCC.Component> S2
-
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
-
debug
private static final boolean debug
- See Also:
- Constant Field Values
-
domainHash
private int[] domainHash
-
xNodesHash
private java.util.Map<IntVar,java.lang.Integer> xNodesHash
-
xVariableToChange
private java.util.Set<IntVar> xVariableToChange
-
stamp
TimeStamp<java.lang.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 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
-
-
Method Detail
-
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.
-
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 classConstraint
- 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 classConstraint
-
impose
public void impose(Store store)
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.
-
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 classConstraint
- 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 interfaceSatisfiedPresent
- 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 classConstraint
-
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)
-
-