Class IntTrie<N extends IntTrie.Node<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 java.lang.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.7
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  IntTrie.Node<E>
      class of nodes of the Trie.
      static class  IntTrie.SimpleNode
      The most simple node possible
    • Field Summary

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

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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      N add​(int i)
      add i to the Trie
      void clear()
      empty the Trie, removing all elements from it
      boolean contains​(int i)
      does the Trie contains i ?
      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)
      N getRoot()  
      boolean isEmpty()  
      boolean remove​(int i)
      remove the int i.
      int size()  
      java.util.Set<java.lang.Integer> values()  
      • Methods inherited from class java.lang.Object

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

      • size

        private int size
    • Constructor Detail

      • IntTrie

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

      • 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 java.util.Set<java.lang.Integer> values()
        Returns:
        the set of values that the Trie contains (quite inefficient)