Module dev.civl.mc
Package dev.civl.mc.util.IF

Class SeqSet

java.lang.Object
dev.civl.mc.util.IF.SeqSet
public class SeqSet extends Object
A SeqSet represents a set of sequences of nonnegative integers. By sequence, we mean finite sequence of integers. Only certain sets are representable. If p and q are sequences, write pinvalid input: '<'=q if p is a prefix of q. (This includes the case p=q.) If p is a sequence, let [p] = {q|pinvalid input: '<'=q}. A SeqSet represents a finite union of sets of the form [p]. If pinvalid input: '<'=q then [p] contains [q], so any SeqSet S can be represented as a finite union of sets of the form [p] where p is a minimal element of S.

If () is the empty sequence then [()] consists of all sequences. It is represented by the SeqSet {()}.

{(1,2),(1,3,4),(2)} is a SeqSet.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    (package private) class 
    SeqSet.Node
    A node in the tree representation.

  • Constructor Summary

    Constructors
    Constructor
    Description
    SeqSet()
    Creates new empty set.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(int... seq)
    Adds the set represented by the given sequence to this set.
    boolean
    addAll(SeqSet that)
    Adds everything in the given set to this set.
    void
    clear()
    Makes this set empty.
    SeqSet
    clone()
     
    boolean
    contains(int... seq)
    Does this set contain the set [s] of sequences which extend a given sequence s?
    boolean
    containsAll(SeqSet that)
    Does this set contain the given set?
    boolean
    disjoint(SeqSet that)
    Are this set and the given set disjoint?
    boolean
    equals(Object obj)
    Do this set and the given set represent the same set of sequences?
    LinkedList<int[]>
    getLeaves()
     
    SeqSet
    intersectionWith(SeqSet that)
     
    boolean
    isEmpty()
     
    void
    makeFull()
    Makes this the full set (consisting of all tuples).
    String
    toString()
     

    Methods inherited from class java.lang.Object

    finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • SeqSet

      public SeqSet()
      Creates new empty set. The root node will be created but will be inactive.

  • Method Details

    • isEmpty

      public boolean isEmpty()

    • add

      public boolean add(int... seq)
      Adds the set represented by the given sequence to this set. No part of the given sequence object will be shared with this set.
      Parameters:
      seq - a non-null (but possibly empty) sequence of nonnegative integers
      Returns:
      true if this operation resulted in a change to this set

    • getLeaves

      public LinkedList<int[]> getLeaves()

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • intersectionWith

      public SeqSet intersectionWith(SeqSet that)

    • addAll

      public boolean addAll(SeqSet that)
      Adds everything in the given set to this set. In the post-state, this SeqSet will represent the union of the set represented by this SeqSet in the pre-state and the set represented by that. SeqSet that is not modified.

      Perform DFS of that while walking through this in tandem with the search. Specifically:

      Let u be the current node for this and v for that. If u is a leaf then backtrack. If v is leaf than prune the children of u and backtrack. Otherwise, iterate over the edges of v. For an edge on int a, see if u has an edge on a. If u does have an edge on a, proceed to the target node in both trees. If u does not have an edge on a, copy the branch starting with a from v to u.

      Parameters:
      that - a non-null SeqSet
      Returns:
      true iff this operation results in a change to this SeqSet

    • clone

      public SeqSet clone()
      Overrides:
      clone in class Object

    • contains

      public boolean contains(int... seq)
      Does this set contain the set [s] of sequences which extend a given sequence s?
      Parameters:
      seq - a non-null (but possibly empty) sequence of nonnegative integers; note that if s is the empty sequence the [s] is the universal set consisting of all sequences
      Returns:
      true iff this set contains all sequences which extend seq (including seq itself)

    • containsAll

      public boolean containsAll(SeqSet that)
      Does this set contain the given set?
      Parameters:
      that - a non-null (but possibly empty) SeqSet
      Returns:
      true iff the set of sequences represented by this SeqSet contains the set of sequences represented by that

    • disjoint

      public boolean disjoint(SeqSet that)
      Are this set and the given set disjoint?
      Parameters:
      that - a non-null SeqSet
      Returns:
      true iff the two sets are disjoint

    • equals

      public boolean equals(Object obj)
      Do this set and the given set represent the same set of sequences?
      Overrides:
      equals in class Object
      Parameters:
      obj - any object to be compared with this one
      Returns:
      true iff obj is a SeqSet representing the same set as this SeqSet

    • clear

      public void clear()
      Makes this set empty.

    • makeFull

      public void makeFull()
      Makes this the full set (consisting of all tuples).