Class SetTrie<T>

java.lang.Object
org.tweetyproject.commons.util.SetTrie<T>
Type Parameters:
T - The type of elements in the sets stored in the trie. Elements must be comparable or a comparator must be provided.
public class SetTrie<T> extends Object
This class implements a set-trie, a data structure for storing sets efficiently. It supports fast queries for subset containment and can be configured to store only minimal sets when used for subset testing. The implementation is based on the set-trie as defined in the paper:
Iztok Savnik: "Index Data Structure for Fast Subset and Superset Queries." CD-ARES 2013: 134-148.

The set-trie allows the addition of sets and supports queries for checking whether a specific set or a subset of a given set is contained within the trie. Note that the removal of sets is not supported in this implementation.
Author:
Matthias Thimm

  • Constructor Summary

    Constructors
    Constructor
    Description
    SetTrie()
    Creates a new empty set-trie.
    SetTrie(boolean onlyForSubsetTests)
    Creates a new empty set-trie, optionally configured for minimal subset storage.
    SetTrie(boolean onlyForSubsetTests, Comparator<T> comp)
    Creates a new empty set-trie, where elements are compared wrt.
    SetTrie(Comparator<T> comp)
    Creates a new empty set-trie, where elements are compared wrt.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    actualSize()
    Returns the number of sets actually stored in the trie (i.e., the number of unique sets).
    boolean
    add(Collection<T> set)
    Adds a set to the trie.
    boolean
    contains(Collection<T> set)
    Checks if a set is contained in the trie.
    boolean
    containsElement(T elem)
    Checks if the trie contains a set with the given element.
    boolean
    containsSubsetOf(Collection<T> set)
    Checks if the trie contains a subset of the given set.
    int
    numberOfNodes()
    Returns the total number of nodes in the trie, which includes all intermediate nodes.
    Collection<Collection<T>>
    sets()
    Returns the set of all sets represented by this set trie
    int
    size()
    Returns the number of sets currently stored in the trie.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • SetTrie

      public SetTrie()
      Creates a new empty set-trie.

    • SetTrie

      public SetTrie(boolean onlyForSubsetTests)
      Creates a new empty set-trie, optionally configured for minimal subset storage.
      Parameters:
      onlyForSubsetTests - If true, the trie only stores minimal sets. Sets that have supersets in the trie will not be added, and supersets will be replaced by smaller sets.

    • SetTrie

      public SetTrie(Comparator<T> comp)
      Creates a new empty set-trie, where elements are compared wrt. the given comparator
      Parameters:
      comp - a comparator for elements of type T.

    • SetTrie

      public SetTrie(boolean onlyForSubsetTests, Comparator<T> comp)
      Creates a new empty set-trie, where elements are compared wrt. the given comparator, optionally configured for minimal subset storage.
      Parameters:
      onlyForSubsetTests - If true, the trie only stores minimal sets. Sets that have subsets in the trie will not be added, and supersets will be replaced by smaller sets.
      comp - a comparator for elements of type T.

  • Method Details

    • size

      public int size()
      Returns the number of sets currently stored in the trie.
      Returns:
      The number of sets stored in the trie.

    • actualSize

      public int actualSize()
      Returns the number of sets actually stored in the trie (i.e., the number of unique sets).
      Returns:
      The number of sets stored in the trie.

    • numberOfNodes

      public int numberOfNodes()
      Returns the total number of nodes in the trie, which includes all intermediate nodes.
      Returns:
      The total number of nodes in the trie.

    • add

      public boolean add(Collection<T> set)
      Adds a set to the trie.
      Parameters:
      set - The set to add.
      Returns:
      true if the set was successfully added, false if the set was already in the trie.

    • contains

      public boolean contains(Collection<T> set)
      Checks if a set is contained in the trie.
      Parameters:
      set - The set to check for.
      Returns:
      true if the set is contained in the trie, false otherwise.

    • containsSubsetOf

      public boolean containsSubsetOf(Collection<T> set)
      Checks if the trie contains a subset of the given set.
      Parameters:
      set - The set to check for subset containment.
      Returns:
      true if a subset of the given set is contained in the trie, false otherwise.

    • containsElement

      public boolean containsElement(T elem)
      Checks if the trie contains a set with the given element.
      Parameters:
      elem - some element
      Returns:
      true iff the trie contains a set with the given element.

    • sets

      public Collection<Collection<T>> sets()
      Returns the set of all sets represented by this set trie
      Returns:
      the set of all sets represented by this set trie