JaCoP.core
Class Store

java.lang.Object
  JaCoP.core.Store

public class Store
extends java.lang.Object

It is an abstract class to describe all necessary functions of any store.

Version:

3.1

Author:

Radoslaw Szymanek and Krzysztof Kuchcinski

Field Summary

java.util.ArrayList<Var>	auxilaryVariables It contains all auxilary variables created by decomposable constraints.
SimpleHashSet<Constraint>[]	changed It stores constraints scheduled for reevaluation.
BooleanVar[]	changeHistory4BooleanVariables It stores boolean variables as soon as they change (become grounded or number of constraints being attached is changed).
static java.util.ArrayList<Constraint>	constraintsToTrace It stores all constraints for which reevaluation should be traced.
Constraint	currentConstraint It stores constraint which is currently re-evaluated.
int	currentQueue It stores current queue, which is being evaluated.
static boolean	debug It specifies if some debugging information is printed.
java.lang.String	description It specifies long description of the store.
static FailException	failException It stores standard fail exception used when empty domain encountered.
java.lang.String	id Id string of the store.
int	level It specifies the time point in the search.
TimeStamp<java.lang.Integer>	pointer4GroundedBooleanVariables It specifies the current pointer to put next changed boolean variable.
boolean	propagationHasOccurred This variable specifies if there was a new propagation.
int	queueNo It stores number of queues used in this store.
boolean	raiseLevelBeforeConsistency Some constraints maintain complex data structure based on function recentDomainPruning of a variable, this function for proper functioning requires to raise store level after imposition and before any changes to variables of this constraint occur.
java.util.ArrayList<Constraint>	removeLevelLateListeners More advanced constraints may require to be informed of a backtrack to be able to recover the older versions of the data structures.
java.util.ArrayList<Constraint>	removeLevelListeners More advanced constraints may require to be informed of a backtrack to be able to recover the older versions of the data structures.
SparseSet	sparseSet It is used by Extensional MDD constraints.
int	sparseSetSize It is used by Extensional MDD constraints.
BacktrackableManager	trailManager It allows to manage information about changed variables in efficient/specialized/tailored manner.
java.util.HashMap<java.lang.String,Var>	variablesHashMap It may be used for faster retrieval of variables given their id.
static java.util.ArrayList<Var>	variablesToTrace It stores all variables for which changes should be traced.
boolean	variableWeightManagement It specifies if the weight of variables which are in the scope of the failure constraint should be increased.
Var[]	vars It stores integer variables created within a store.
java.util.HashMap<Var,java.util.HashSet<Constraint>>	watchedConstraints This keeps information about watched constraints by given variable.

Constructor Summary

Store()
It specifies the default constructor of the store.

Store(int size)
It specifies the constructor of the store, which allows to decide what is the initial size of the Variable list.

Method Summary

void	addChanged(Constraint c) This function schedules given constraint for re-evaluation.
void	addChanged(Var var, int pruningEvent, int info) This function schedules all attached (not yet satisfied constraints) for given variable for re-evaluation.
static void	addTracedConstraint(Constraint C) It adds a constraint to traced constraints.
static void	addTracedVariable(Var V) It adds a variable to traced variables.
java.lang.String	checkInvariants() It checks invariants to see if the execution went smoothly.
void	clearChanged() It clears the queue of constraints which need to be reevaluated usefull if different scheme propagation scheme needs to be implemented.
void	clearWatchedConstraint() It removes all watches to constraints, therefore constraints are no longer watched, no longer part of the model.
boolean	consistency() This function computes the consistency function.
void	countConstraint() This function is called when a counter of constraints should be increased.
void	countConstraint(int n) This function is called when a counter of constraints should be increased by given value.
int	countWatches() It returns number of watches which are used to watch constraints.
boolean	deRegisterRemoveLevelListener(Constraint C) This function deregisters a constraint from the listeners queue.
void	deregisterWatchedLiteralConstraint(Constraint C) Watched constraint given as parameter is being removed, no variable will be watching it.
void	deregisterWatchedLiteralConstraint(Var v, Constraint C) Variable given as a parameter no longer watches constraint given as parameter.
int	findPositionForInsert(int[] tuple) searches for the position of the tuple in the tuple list.
Var	findVariable(java.lang.String id) This function looks for a variable with given id.
boolean	getCheckSatisfiability() If a constraint is checked for satisfiability and it is satisfied then it will not be attached to a variable anymore.
Constraint	getCurrentConstraint() This function returns the constraint which is currently reevaluated.
java.lang.String	getDescription() This function returns the long description of the store.
Constraint	getFirstChanged() This function returns the constraint scheduled for re-evaluation.
java.lang.String	getName() This function returns the id of the store.
java.lang.String	getVariableIdPrefix() This function returns the prefix of the automatically generated names for noname variables.
void	impose(Constraint c) This function imposes a constraint to a store.
void	impose(Constraint C, int queueIndex) This function imposes a constraint to a store.
void	imposeDecomposition(DecomposedConstraint C) This function imposes a decomposable constraint to a store.
void	imposeDecomposition(DecomposedConstraint C, int queueIndex) This function imposes a constraint decomposition to a store.
void	imposeDecompositionWithConsistency(DecomposedConstraint C) In some special cases it may be beneficial to compute consistency of constraint store immediately after the decomposed constraint is imposed.
void	imposeWithConsistency(Constraint C) In some special cases it may be beneficial to compute consistency of constraint store immediately after the constraint is imposed.
boolean	isGround() This function checks if all variables within a store are grounded.
int	numberConstraints() This function returns the number of constraints.
void	print() This function prints the information of the store to standard output stream.
int	putMutableVar(MutableVar value) Any constraint may have their own mutable variables which can be register at store and then store will be responsible for calling appropriate functions from MutableVar interface to keep the variables consistent with the search.
int	putMutableVar(TimeStamp<?> value) Any entity (for example constraints) may have their own mutable variables (timestamps) which can be register at store and then store will be responsible for calling appropriate functions from TimeStamp class to keep the variables consistent with the search.
int	putVariable(Var var) This function is used to register a variable within a store.
void	recordBooleanChange(BooleanVar recordedVariable) Any boolean variable which is changed must be recorded by store, so it can be restored to the previous state if backtracking is performed.
void	recordChange(Var recordedVariable) Any change of finite domain variable must also be recorded, so intervals denoting changed variables can be updated.
int[][]	recordTuples(int[][] ts) It recordTuples to store so tuples can be reused across multiple extensional constraints.
boolean	registerRemoveLevelLateListener(Constraint C) Any constraint in general may need information what variables have changed since the last time a consistency was called.
boolean	registerRemoveLevelListener(Constraint C) Any constraint in general may need information what variables have changed since the last time a consistency was called.
void	registerWatchedLiteralConstraint(Var v, Constraint C) It register variable to watch given constraint.
void	removeLevel(int rLevel) This important function removes all changes which has been recorded to any variable at given level.
static void	removeTracedConstraint(Constraint C) It removes a constraint from traced constraints.
static void	removeTracedVariable(Var V) It removes a variable from traced variables.
java.util.ArrayList<Constraint>	select(java.lang.Class<Constraint> classname) It selects constraints of a given type from queue changed.
void	setCheckSatisfiability(boolean value) It decides if constraints are checked for satisfiability.
void	setDescription(java.lang.String description) This function sets the long description of the store.
void	setID(java.lang.String id) This function sets the id of the store.
void	setLevel(int l) This function allows to proceed with the search, create new layer at which new values for variables will be recorded.
void	setVariableIdPrefix(java.lang.String idPrefix) This function sets the prefix of the automatically generated names for noname variables.
int	size() It returns number of variables in a store.
boolean	smallerEqualTuple(int[] left, int[] right) It compares tuples.
int[][]	sortTuples(int[][] ts)
void	sortTuplesWithin(int[][] ts) It sorts tuples.
void	throwFailException(Var X) It throws an exception after printing trace information if tracing is switched on.
java.lang.String	toString() This function returns a string a representation of the store.
java.lang.String	toStringChangedEl() This function returns a string representation of the constraints pending for re-evaluation.
void	trim() This function trims the store.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

constraintsToTrace

public static java.util.ArrayList<Constraint> constraintsToTrace

It stores all constraints for which reevaluation should be traced.

failException

public static final FailException failException

It stores standard fail exception used when empty domain encountered.

debug

public static final boolean debug

It specifies if some debugging information is printed.

See Also:

Constant Field Values

variablesToTrace

public static java.util.ArrayList<Var> variablesToTrace

It stores all variables for which changes should be traced.

changed

public SimpleHashSet<Constraint>[] changed

It stores constraints scheduled for reevaluation. It does not register constraints which are already scheduled for reevaluation.

changeHistory4BooleanVariables

public BooleanVar[] changeHistory4BooleanVariables

It stores boolean variables as soon as they change (become grounded or number of constraints being attached is changed). Later each level remembers the part of the array which contains variables changed at this level (efficient backtracking).

removeLevelListeners

public java.util.ArrayList<Constraint> removeLevelListeners

More advanced constraints may require to be informed of a backtrack to be able to recover the older versions of the data structures. For example, the constraints can clear their queue of changed variables if a backtracks has occurred. It holds the list of constraints which want to be informed about level being removed before it has actually began.

removeLevelLateListeners

public java.util.ArrayList<Constraint> removeLevelLateListeners

More advanced constraints may require to be informed of a backtrack to be able to recover the older versions of the data structures. For example, the constraints can clear their queue of changed variables if a backtracks has occurred. It holds the list of constraints which want to be informed about level being removed after it has been removed.

auxilaryVariables

public java.util.ArrayList<Var> auxilaryVariables

It contains all auxilary variables created by decomposable constraints. They have to be grounded by search for a solution to be valid.

currentConstraint

public Constraint currentConstraint

It stores constraint which is currently re-evaluated.

currentQueue

public int currentQueue

It stores current queue, which is being evaluated.

description

public java.lang.String description

It specifies long description of the store.

id

public java.lang.String id

Id string of the store.

level

public int level

It specifies the time point in the search. Every time this variable is increased a new layer of changes to the variables are recorded. This is the most important variable. It is assumed that initially this value is equal to zero. Use setLevel function if you want to play with it.

propagationHasOccurred

public boolean propagationHasOccurred

This variable specifies if there was a new propagation. Any change to any variable will setup this variable to true. Usefull variable to discover the idempodence of the consistency propagator.

pointer4GroundedBooleanVariables

public TimeStamp<java.lang.Integer> pointer4GroundedBooleanVariables

It specifies the current pointer to put next changed boolean variable. It has to be maintained manually (within removeLevel function).

queueNo

public int queueNo

It stores number of queues used in this store. It has to be at least 1. No constraint can be imposed with queue index greater or equal this number.

raiseLevelBeforeConsistency

public boolean raiseLevelBeforeConsistency

Some constraints maintain complex data structure based on function recentDomainPruning of a variable, this function for proper functioning requires to raise store level after imposition and before any changes to variables of this constraint occur. This flag is set by constraints at imposition stage.

variableWeightManagement

public boolean variableWeightManagement

It specifies if the weight of variables which are in the scope of the failure constraint should be increased.

watchedConstraints

public java.util.HashMap<Var,java.util.HashSet<Constraint>> watchedConstraints

This keeps information about watched constraints by given variable. Watched constraints are active all the time. Use this with care and do not be surprised if some constraints stay longer than you expect. It can be directly manipulated in any way (including setting to null if no watched constraints are being in the queue system).

vars

public Var[] vars

It stores integer variables created within a store.

trailManager

public BacktrackableManager trailManager

It allows to manage information about changed variables in efficient/specialized/tailored manner.

variablesHashMap

public java.util.HashMap<java.lang.String,Var> variablesHashMap

It may be used for faster retrieval of variables given their id. However, by default this variable is not created to reduce memory consumption. If it exists then it will be used by functions looking for a variable given the name.

sparseSet

public SparseSet sparseSet

It is used by Extensional MDD constraints. It is to represent G_yes.

sparseSetSize

public int sparseSetSize

It is used by Extensional MDD constraints. It is to represent the size of G_yes.

Constructor Detail

Store

public Store()

It specifies the default constructor of the store.

Store

public Store(int size)

It specifies the constructor of the store, which allows to decide what is the initial size of the Variable list.

Parameters:

size - specifies the initial number of variables.

Method Detail

addTracedConstraint

public static void addTracedConstraint(Constraint C)

It adds a constraint to traced constraints.

Parameters:

C - constraint which is being traced.

addTracedVariable

public static void addTracedVariable(Var V)

It adds a variable to traced variables.

Parameters:

V - variable which is being traced.

removeTracedConstraint

public static void removeTracedConstraint(Constraint C)

It removes a constraint from traced constraints.

Parameters:

C - constraint to be traced.

removeTracedVariable

public static void removeTracedVariable(Var V)

It removes a variable from traced variables.

Parameters:

V - variable to be traced.

deregisterWatchedLiteralConstraint

public void deregisterWatchedLiteralConstraint(Var v,
                                               Constraint C)

Variable given as a parameter no longer watches constraint given as parameter. This function will be called when watch is being moved from one variable to another.

Parameters:

v - variable at which constraint is no longer watching.

C - constraint which is no longer watched by given variable.

deregisterWatchedLiteralConstraint

public void deregisterWatchedLiteralConstraint(Constraint C)

Watched constraint given as parameter is being removed, no variable will be watching it.

Parameters:

C - constraint for which all watches are removed.

countWatches

public int countWatches()

It returns number of watches which are used to watch constraints.

Returns:

returns the number of watches attached to variables.

registerWatchedLiteralConstraint

public void registerWatchedLiteralConstraint(Var v,
                                             Constraint C)

It register variable to watch given constraint. This function is called either by impose function of a constraint or by consistency function of a constraint when watch is being moved.

Parameters:

v - variable which is used to watch the constraint.

C - the constraint being used.

clearWatchedConstraint

public void clearWatchedConstraint()

It removes all watches to constraints, therefore constraints are no longer watched, no longer part of the model.

addChanged

public void addChanged(Constraint c)

This function schedules given constraint for re-evaluation. This function will most probably be rarely used as constraints require reevaluation only when a variable changes.

Parameters:

c - constraint which needs reevaluation.

addChanged

public void addChanged(Var var,
                       int pruningEvent,
                       int info)

This function schedules all attached (not yet satisfied constraints) for given variable for re-evaluation. This function must add all attached constraints for reevaluation but it will do it any order which suits it.

Parameters:

var - variable for which some pruning event has occurred.

pruningEvent - specifies the type of the pruning event.

info - it specifies detailed information about the change of the variable domain. the inputs of the currentConstraint in the manner that would validate another execution.

clearChanged

public void clearChanged()

It clears the queue of constraints which need to be reevaluated usefull if different scheme propagation scheme needs to be implemented.

consistency

public boolean consistency()

This function computes the consistency function. It evaluates all constraints which are in the changed queue.

Returns:

returns true if all constraints which were in changed queue are consistent, false otherwise.

countConstraint

public void countConstraint()

This function is called when a counter of constraints should be increased. It is most probable that this function will called from the impose function of the constraint.

countConstraint

public void countConstraint(int n)

This function is called when a counter of constraints should be increased by given value. If for some reason some constraints should be counted as multiple ones than this function could be called.

Parameters:

n - integer by which the counter of constraints should be increased.

deRegisterRemoveLevelListener

public boolean deRegisterRemoveLevelListener(Constraint C)

This function deregisters a constraint from the listeners queue. The constraint will know that it has to re-execute its consistency function, but it will not be informed which variables has changed.

Parameters:

C - constraint which no longer needs to be removed when level is removed.

Returns:

true if constraint was listening beforehand, otherwise false.

findVariable

public Var findVariable(java.lang.String id)

This function looks for a variable with given id. It will first check the existence of a hashmap variablesHashMap to get the variable from the hashmap in constant time. Only if the variable was not found or hashmap object was not created a linear algorithm scanning through the whole list of variables will be employed.

Parameters:

id - unique identifier of the variable.

Returns:

reference to a variable with the given id.

getCheckSatisfiability

public boolean getCheckSatisfiability()

If a constraint is checked for satisfiability and it is satisfied then it will not be attached to a variable anymore.

Returns:

true if constraints are checked for satisfiability.

getCurrentConstraint

public Constraint getCurrentConstraint()

This function returns the constraint which is currently reevaluated. It is an easy way to discover which constraint caused a failure right after the inconsistency is signaled.

Returns:

constraint for which consistency method is being executed.

getDescription

public java.lang.String getDescription()

This function returns the long description of the store.

Returns:

store description.

getFirstChanged

public Constraint getFirstChanged()

This function returns the constraint scheduled for re-evaluation. It returns constraints based on criteria first-in-first out. It is simple, easy, fair, and efficient way of getting constraints for reevaluation. The constraint is _removed_ from the queue, since it is assumed that they are reevaluated right away.

Returns:

first constraint which is being marked as the one which needs to be checked for consistency.

getName

public java.lang.String getName()

This function returns the id of the store.

Returns:

id of store.

getVariableIdPrefix

public java.lang.String getVariableIdPrefix()

This function returns the prefix of the automatically generated names for noname variables.

Returns:

he prefix of the automatically generated names for noname variables.

impose

public void impose(Constraint c)

This function imposes a constraint to a store. The constraint is scheduled for evaluation for the next store consistency call. Therefore, the constraint is added to queue of changed constraints.

Parameters:

c - constraint to be imposed.

impose

public void impose(Constraint C,
                   int queueIndex)

This function imposes a constraint to a store. The constraint is scheduled for evaluation for the next store consistency call. Therefore, the constraint is added to queue of changed constraints.

Parameters:

C - constraint to be added to specified queue.

queueIndex - specifies index of the queue for a constraint.

imposeWithConsistency

public void imposeWithConsistency(Constraint C)
                           throws FailException

In some special cases it may be beneficial to compute consistency of constraint store immediately after the constraint is imposed. This function will impose a constraint and call the consistency function of the store immediately.

Parameters:

C - constraint to be imposed.

Throws:

FailException - failure exception.

imposeDecomposition

public void imposeDecomposition(DecomposedConstraint C)

This function imposes a decomposable constraint to a store. The decomposition is scheduled for evaluation for the next store consistency call. Therefore, the constraints are added to queue of changed constraints.

Parameters:

C - constraint to be imposed.

imposeDecomposition

public void imposeDecomposition(DecomposedConstraint C,
                                int queueIndex)

This function imposes a constraint decomposition to a store. The decomposition constraints are scheduled for evaluation for the next store consistency call. Therefore, the constraints are added to queue of changed constraints.

Parameters:

C - constraint to be added to specified queue.

queueIndex - specifies index of the queue for a constraint.

imposeDecompositionWithConsistency

public void imposeDecompositionWithConsistency(DecomposedConstraint C)

In some special cases it may be beneficial to compute consistency of constraint store immediately after the decomposed constraint is imposed. This function will impose constraint decomposition and call the consistency function of the store immediately.

Parameters:

C - decomposed constraint to be imposed.

isGround

public boolean isGround()

This function checks if all variables within a store are grounded. It is advised to make sure that after search all variables are grounded.

Returns:

true if all variables are singletons, false otherwise.

numberConstraints

public int numberConstraints()

This function returns the number of constraints.

Returns:

number of constraints.

print

public void print()

This function prints the information of the store to standard output stream.

putMutableVar

public int putMutableVar(MutableVar value)

Any constraint may have their own mutable variables which can be register at store and then store will be responsible for calling appropriate functions from MutableVar interface to keep the variables consistent with the search.

Parameters:

value - MutableVariable to be added and maintained by a store.

Returns:

the position of MutableVariable at which it is being stored.

putMutableVar

public int putMutableVar(TimeStamp<?> value)

Any entity (for example constraints) may have their own mutable variables (timestamps) which can be register at store and then store will be responsible for calling appropriate functions from TimeStamp class to keep the variables consistent with the search.

Parameters:

value - timestamp to be added and maintained by a store.

Returns:

the position of timestamp at which it is being stored.

putVariable

public int putVariable(Var var)

This function is used to register a variable within a store. It will be most probably called from variable constructor. It returns the current position of fdv in a store local data structure.

Parameters:

var - variable to be registered.

Returns:

position of the variable at which it is being stored.

recordBooleanChange

public void recordBooleanChange(BooleanVar recordedVariable)

Any boolean variable which is changed must be recorded by store, so it can be restored to the previous state if backtracking is performed.

Parameters:

recordedVariable - boolean variable which has changed.

recordChange

public void recordChange(Var recordedVariable)

Any change of finite domain variable must also be recorded, so intervals denoting changed variables can be updated.

Parameters:

recordedVariable - variable which has changed.

registerRemoveLevelListener

public boolean registerRemoveLevelListener(Constraint C)

Any constraint in general may need information what variables have changed since the last time a consistency was called. This function is called just *before* removeLevel method is executed for variables, mutable variables, and timestamps.

Parameters:

C - constraint which is no longer interested in listening to remove level events.

Returns:

true if constraint C was watching remove level events.

registerRemoveLevelLateListener

public boolean registerRemoveLevelLateListener(Constraint C)

Any constraint in general may need information what variables have changed since the last time a consistency was called. This function is called just *after* removeLevel method is executed for variables, mutable variables, and timestamps.

Parameters:

C - constraint which is no longer interested in listening to remove level events.

Returns:

true if constraint C was watching remove level events.

removeLevel

public void removeLevel(int rLevel)

This important function removes all changes which has been recorded to any variable at given level. Before backtracking to earlier level all levels after earlier level must be removed. The removal order must be reversed to the creation order.

Parameters:

rLevel - Store level to be removed.

setCheckSatisfiability

public void setCheckSatisfiability(boolean value)

It decides if constraints are checked for satisfiability. If a constraint is satisfied then it will not be attached to a variable anymore.

Parameters:

value - boolean value specifying if check for satisfiability should be performed.

setDescription

public void setDescription(java.lang.String description)

This function sets the long description of the store.

Parameters:

description -

setID

public void setID(java.lang.String id)

This function sets the id of the store. This id is used when saving to XML file.

Parameters:

id - store id.

setLevel

public void setLevel(int l)

This function allows to proceed with the search, create new layer at which new values for variables will be recorded. This function is also used during backtracking, after removing current level the store can be set to the previous level.

Parameters:

l - level number to which store is changing to.

setVariableIdPrefix

public void setVariableIdPrefix(java.lang.String idPrefix)

This function sets the prefix of the automatically generated names for noname variables.

Parameters:

idPrefix - prefix of all variables with automatically generated names.

size

public int size()

It returns number of variables in a store.

Returns:

number of variables in a store.

throwFailException

public void throwFailException(Var X)

It throws an exception after printing trace information if tracing is switched on.

Parameters:

X - variable causing the failure exception.

Throws:

FailException - is always thrown.

toString

public java.lang.String toString()

This function returns a string a representation of the store. Whatever seems important may be included here.

Overrides:

toString in class java.lang.Object

toStringChangedEl

public java.lang.String toStringChangedEl()

This function returns a string representation of the constraints pending for re-evaluation.

Returns:

string description of changed constraints.

trim

public void trim()

This function trims the store. It will most probably removed constraints which are satisfied. It may also remove all variables which do not have any not yet satisfied constraints attached to them. Use with care, since this function has a mandate to change CSP at previous time points. This function will be most probably used before search to obtain consize model.

select

public java.util.ArrayList<Constraint> select(java.lang.Class<Constraint> classname)

It selects constraints of a given type from queue changed.

Parameters:

classname - specifies the classname.

Returns:

array of constraints given class type.

recordTuples

public int[][] recordTuples(int[][] ts)

It recordTuples to store so tuples can be reused across multiple extensional constraints. It can potentially save memory.

Parameters:

ts - tuples to be recorded.

Returns:

two-dimensional array with tuples.

findPositionForInsert

public int findPositionForInsert(int[] tuple)

searches for the position of the tuple in the tuple list.

Parameters:

tuple - to be compared to.

Returns:

position at which the tuple is stored in tuple list array.

sortTuples

public int[][] sortTuples(int[][] ts)

Parameters:

ts - tuples to be sorted.

Returns:

sorted tuples.

sortTuplesWithin

public void sortTuplesWithin(int[][] ts)

It sorts tuples.

Parameters:

ts - tuples to be sorted.

smallerEqualTuple

public boolean smallerEqualTuple(int[] left,
                                 int[] right)

It compares tuples.

Parameters:

left - tuple to be compared to.

right - tuple to compar with.

Returns:

true if the left tuple is larger than right tuple.

checkInvariants

public java.lang.String checkInvariants()

It checks invariants to see if the execution went smoothly.

Returns:

description of the violated invariant, null otherwise.