Class ExtensionalSupportSTR

All Implemented Interfaces:
Stateful, UsesQueueVariable

public class ExtensionalSupportSTR extends Constraint implements UsesQueueVariable, Stateful
Extensional constraint assures that one of the tuples is enforced in the relation.

This implementation uses technique developed/improved by Christophe Lecoutre. Paper presented at CP2008. We would like to thank him for making his code available, which helped to create our own version of this algorithm.

Version:
4.8
  • Field Details

    • store

      Store store
    • list

      public IntVar[] list
      It stores variables within this extensional constraint, order does matter.
    • tuples

      public int[][] tuples
    • idNumber

      static AtomicInteger idNumber
    • debugAll

      static final boolean debugAll
      See Also:
    • views

    • first

      public int first
      Gives the position of the first tuple (in the current list) or -1 if the current list is empty.
    • last

      public int last
      Gives the position of the last tuple (in the current list) or -1 if the current list is empty.
    • nexts

      public int[] nexts
      Gives the position of the next tuple wrt the position given in index, or -1.
    • headsOfEliminatedTuples

      public TimeStamp<Integer> headsOfEliminatedTuples
      Gives the first position of the eliminated tuple at a given level.
    • tailsOfEliminatedTuples

      public TimeStamp<Integer> tailsOfEliminatedTuples
      Gives the last position of the eliminated tuple at a given level.
    • nbGlobalValuesToBeSupported

      public int nbGlobalValuesToBeSupported
      The number of variable-value pairs which need to have support.
    • nbValuesToBeSupported

      public int[] nbValuesToBeSupported
      The number of variable-value pairs which need to have support per variable.
    • firstResidue

      public int firstResidue
      It stores the position of the first residue.
    • lastResidue

      public int lastResidue
      It stores the position of the last residue.
    • nbValidityVariables

      public int nbValidityVariables
      It specifies the number of variables for which validity check within a tuple must be performed.
    • validityVariablePositions

      public int[] validityVariablePositions
      The positions of the variables for which validity of any tuple must be checked.
    • nbSupportsVariables

      public int nbSupportsVariables
      It specifies the current number of variables for which it is required to check if their values from the domains are supported.
    • supportsVariablePositions

      public int[] supportsVariablePositions
      The positions of the variables for which GAC must be checked. It does not contain variables which were singletons in previous invocation of the consistency function.
    • valuesInFocus

      IntervalDomain[] valuesInFocus
    • domainSizeAfterConsistency

      int[] domainSizeAfterConsistency
    • varToIndex

      public Map<Var,Integer> varToIndex
      It specifies the mapping of the variable into its index.
    • lastAssignedVariablePosition

      public int lastAssignedVariablePosition
    • reinsertBefore

      public boolean reinsertBefore
      It specifies if the tuples previously removed are re-inserted at the beginning.
    • residuesBefore

      public boolean residuesBefore
      It specifies if the residues are moved at the beginning of the list.
    • firstConsistencyCheck

      public boolean firstConsistencyCheck
      It specifies if there was no first consistency check yet.
    • firstConsistencyLevel

      int firstConsistencyLevel
    • backtrackOccured

      public boolean backtrackOccured
      It specifies if there was a backtrack and no yet consistency function execution after backtracking.
  • Constructor Details

    • ExtensionalSupportSTR

      @Deprecated public ExtensionalSupportSTR(IntVar[] list, boolean reinsertBefore, boolean residuesBefore)
      Deprecated.
      Partial constructor which stores variables involved in a constraint but does not get information about tuples yet. The tuples must set separately.
      Parameters:
      list - the variables in the scope of the constraint.
      reinsertBefore - it specifies if the tuples which were removed and are reinstatiated are inserted at the beginning.
      residuesBefore - it specifies if the residue tuples are moved to the beginning.
    • ExtensionalSupportSTR

      public ExtensionalSupportSTR(IntVar[] list, int[][] tuples, boolean reinsertBefore, boolean residuesBefore)
      It constructs an extensional constraint.
      Parameters:
      list - the variables in the scope of the constraint.
      tuples - the tuples which are supports.
      reinsertBefore - it specifies if the tuples which were removed and are reinstatiated are inserted at the beginning.
      residuesBefore - it specifies if the residue tuples are moved to the beginning.
    • ExtensionalSupportSTR

      public ExtensionalSupportSTR(IntVar[] variables, int[][] tuples)
      It creates an extensional constraint.
      Parameters:
      variables - the variables in the scope of the constraint.
      tuples - the support tuples.
  • Method Details

    • remove

      public void remove(int previous, int current)
      It removes the tuple which is no longer valid.
      Parameters:
      previous - the tuple pointing at removed tuple.
      current - the removed tuple.
    • storeResidue

      public void storeResidue(int previous, int current)
      It moves the residue to the beginning of the list.
      Parameters:
      previous - the tuple pointing at tuple residue.
      current - the residue tuple.
    • 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.
    • 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 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.
    • smaller

      boolean smaller(int[] tuple1, int[] tuple2)
    • toString

      public String toString()
      Description copied from class: Constraint
      It produces a string representation of a constraint state.
      Overrides:
      toString in class Constraint