Class IntTrie<N extends IntTrie.Node<N>>

java.lang.Object
org.jacop.jasat.utils.structures.IntTrie<N>
Type Parameters:
N - the type of the nodes of the Trie
Direct Known Subclasses:
IntSet

public class IntTrie<N extends IntTrie.Node<N>> extends Object
A class that implements, (hopefully) efficiently, a Trie on integers. It is parametrized by the type of the nodes to carry useful data. implementation based on Trie (or Radix Tree, see http://en.wikipedia.org/wiki/Radix_tree).

It can be used directly as a (simple) set.

Version:
4.10
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    class of nodes of the Trie.
    static final class 
    The most simple node possible
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final N
     
    private int
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    IntTrie(N root)
    initializes the Trie with a root node
  • Method Summary

    Modifier and Type
    Method
    Description
    final N
    add(int i)
    add i to the Trie
    final void
    empty the Trie, removing all elements from it
    final boolean
    contains(int i)
    does the Trie contains i ?
    final N
    getNode(int i)
    get the node associated with i, or maybe the node that would be associated with i if i was in the Trie (*optional* feature)
    final N
     
    final boolean
     
    final boolean
    remove(int i)
    remove the int i.
    final int
     
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • root

      private final N extends IntTrie.Node<N> root
    • size

      private int size
  • Constructor Details

    • IntTrie

      public IntTrie(N root)
      initializes the Trie with a root node
      Parameters:
      root - the root node.
  • Method Details

    • add

      public final N add(int i)
      add i to the Trie
      Parameters:
      i - the int to add to the Trie
      Returns:
      the node corresponding to i
    • contains

      public final boolean contains(int i)
      does the Trie contains i ?
      Parameters:
      i - the int
      Returns:
      true if the Trie contains i, false otherwise
    • getNode

      public final N getNode(int i)
      get the node associated with i, or maybe the node that would be associated with i if i was in the Trie (*optional* feature)
      Parameters:
      i - the int
      Returns:
      the node associated with i if it exists, null otherwise
    • getRoot

      public final N getRoot()
      Returns:
      the root node
    • remove

      public final boolean remove(int i)
      remove the int i.
      Parameters:
      i - the int to remove from the Trie
      Returns:
      true if i was in the Trie (and has been removed), false if it was not
    • clear

      public final void clear()
      empty the Trie, removing all elements from it
    • isEmpty

      public final boolean isEmpty()
      Returns:
      true if and only if the trie does not contain anything
    • size

      public final int size()
      Returns:
      the number of elements in the Trie
    • values

      public Set<Integer> values()
      Returns:
      the set of values that the Trie contains (quite inefficient)