Package org.tweetyproject.commons.util

Class SetTrie<T extends Comparable<T>>

java.lang.Object
org.tweetyproject.commons.util.SetTrie<T>
Type Parameters:
T - the type of elements in the sets of the trie
public class SetTrie<T extends Comparable<T>> extends Object
This class provides a general implementation of a set-trie as defined in [Iztok Savnik: Index Data Structure for Fast Subset and Superset Queries. CD-ARES 2013: 134-148]. It is a data structure for storing sets that supports fast queries regarding subset containment (removal not allowed though).
Author:
Matthias Thimm

  • Constructor Details

    • SetTrie

      public SetTrie()
      Creates a new set-trie

    • SetTrie

      public SetTrie(boolean onlyForSubsetTests)
      Creates a new set-trie
      Parameters:
      onlyForSubsetTests - if set to true, then this trie does not store all sets, but (basically) only minimal ones. Whenever a set is added and there is already a superset of that set contained, the larger is deleted.

  • Method Details

    • size

      public int size()

    • actualSize

      public int actualSize()

    • numberOfNodes

      public int numberOfNodes()

    • add

      public boolean add(Collection<T> set)
      Inserts the given set into this set-trie
      Parameters:
      set - some set
      Returns:
      "true" if indeed a set has been added

    • contains

      public boolean contains(Collection<T> set)
      Checks whether the given set is contained in this set-trie.
      Parameters:
      set - some set
      Returns:
      "true" iff the given set is contained in this set-trie.

    • containsSubsetOf

      public boolean containsSubsetOf(Collection<T> set)
      Checks whether there is a subset of the given set contained.
      Parameters:
      set - some set
      Returns:
      true if there is a subset of the given set