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 stored in the trie. Elements must be comparable.

public class SetTrie<T extends Comparable<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.

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	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.
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.

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.