weka.core

## Class Trie

- java.lang.Object
- - weka.core.Trie

- All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<java.lang.String>, java.util.Collection<java.lang.String>, RevisionHandler

      public class Trie
      extends java.lang.Object
      implements java.io.Serializable, java.lang.Cloneable, java.util.Collection<java.lang.String>, RevisionHandler

  A class representing a Trie data structure for strings. See also Trie on WikiPedia.
  Version:
    $Revision: 10203 $
  Author:
    fracpete (fracpete at waikato dot ac dot nz)
  See Also:
    Serialized Form

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `static class` | `Trie.TrieIterator` Represents an iterator over a trie
    `static class` | `Trie.TrieNode` Represents a node in the trie.

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Trie()` initializes the data structure

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `boolean` | `add(java.lang.String o)` Ensures that this collection contains the specified element.
    `boolean` | `addAll(java.util.Collection<? extends java.lang.String> c)` Adds all of the elements in the specified collection to this collection
    `void` | `clear()` Removes all of the elements from this collection
    `java.lang.Object` | `clone()` returns a deep copy of itself
    `boolean` | `contains(java.lang.Object o)` Returns true if this collection contains the specified element.
    `boolean` | `containsAll(java.util.Collection<?> c)` Returns true if this collection contains all of the elements in the specified collection.
    `boolean` | `containsPrefix(java.lang.String prefix)` checks whether the given prefix is stored in the trie
    `boolean` | `equals(java.lang.Object o)` Compares the specified object with this collection for equality.
    `java.lang.String` | `getCommonPrefix()` returns the common prefix for all the nodes
    `java.lang.String` | `getRevision()` Returns the revision string.
    `Trie.TrieNode` | `getRoot()` returns the root node of the trie
    `java.util.Vector<java.lang.String>` | `getWithPrefix(java.lang.String prefix)` returns all stored strings that match the given prefix
    `int` | `hashCode()` Returns the hash code value for this collection.
    `boolean` | `isEmpty()` Returns true if this collection contains no elements.
    `java.util.Iterator<java.lang.String>` | `iterator()` Returns an iterator over the elements in this collection.
    `static void` | `main(java.lang.String[] args)` Only for testing (prints the built Trie).
    `boolean` | `remove(java.lang.Object o)` Removes a single instance of the specified element from this collection, if it is present.
    `boolean` | `removeAll(java.util.Collection<?> c)` Removes all this collection's elements that are also contained in the specified collection
    `boolean` | `retainAll(java.util.Collection<?> c)` Retains only the elements in this collection that are contained in the specified collection
    `int` | `size()` Returns the number of elements in this collection.
    `java.lang.Object[]` | `toArray()` Returns an array containing all of the elements in this collection.
    `<T> T[]` | `toArray(T[] a)` Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.
    `java.lang.String` | `toString()` returns the trie in string representation

    - ### Methods inherited from class java.lang.Object

      `getClass, notify, notifyAll, wait, wait, wait`

- - ### Constructor Detail

    - #### Trie

          public Trie()

      initializes the data structure

  - ### Method Detail

    - #### add

          public boolean add(java.lang.String o)

      Ensures that this collection contains the specified element.
      Specified by:
        `add` in interface `java.util.Collection<java.lang.String>`
      Parameters:
        `o` - the string to add
      Returns:
        true if the structure changed

    - #### addAll

          public boolean addAll(java.util.Collection<? extends java.lang.String> c)

      Adds all of the elements in the specified collection to this collection
      Specified by:
        `addAll` in interface `java.util.Collection<java.lang.String>`
      Parameters:
        `c` - the collection to add

    - #### clear

          public void clear()

      Removes all of the elements from this collection
      Specified by:
        `clear` in interface `java.util.Collection<java.lang.String>`

    - #### clone

          public java.lang.Object clone()

      returns a deep copy of itself
      Overrides:
        `clone` in class `java.lang.Object`
      Returns:
        a copy of itself

    - #### contains

          public boolean contains(java.lang.Object o)

      Returns true if this collection contains the specified element.
      Specified by:
        `contains` in interface `java.util.Collection<java.lang.String>`
      Parameters:
        `o` - the object to check for in trie
      Returns:
        true if found

    - #### containsAll

          public boolean containsAll(java.util.Collection<?> c)

      Returns true if this collection contains all of the elements in the specified collection.
      Specified by:
        `containsAll` in interface `java.util.Collection<java.lang.String>`
      Parameters:
        `c` - the collection to look for in the trie
      Returns:
        true if all elements were found

    - #### containsPrefix

          public boolean containsPrefix(java.lang.String prefix)

      checks whether the given prefix is stored in the trie
      Parameters:
        `prefix` - the prefix to check
      Returns:
        true if the prefix is part of the trie

    - #### equals

          public boolean equals(java.lang.Object o)

      Compares the specified object with this collection for equality.
      Specified by:
        `equals` in interface `java.util.Collection<java.lang.String>`
      Overrides:
        `equals` in class `java.lang.Object`
      Parameters:
        `o` - the object to check for equality

    - #### getCommonPrefix

          public java.lang.String getCommonPrefix()

      returns the common prefix for all the nodes
      Returns:
        the result of the search

    - #### getRoot

          public Trie.TrieNode getRoot()

      returns the root node of the trie
      Returns:
        the root node

    - #### getWithPrefix

          public java.util.Vector<java.lang.String> getWithPrefix(java.lang.String prefix)

      returns all stored strings that match the given prefix
      Parameters:
        `prefix` - the prefix that all strings must have
      Returns:
        all strings that match the prefix

    - #### hashCode

          public int hashCode()

      Returns the hash code value for this collection.
      Specified by:
        `hashCode` in interface `java.util.Collection<java.lang.String>`
      Overrides:
        `hashCode` in class `java.lang.Object`
      Returns:
        the hash code

    - #### isEmpty

          public boolean isEmpty()

      Returns true if this collection contains no elements.
      Specified by:
        `isEmpty` in interface `java.util.Collection<java.lang.String>`
      Returns:
        true if empty

    - #### iterator

          public java.util.Iterator<java.lang.String> iterator()

      Returns an iterator over the elements in this collection.
      Specified by:
        `iterator` in interface `java.lang.Iterable<java.lang.String>`
      Specified by:
        `iterator` in interface `java.util.Collection<java.lang.String>`
      Returns:
        returns an iterator over all the stored strings

    - #### remove

          public boolean remove(java.lang.Object o)

      Removes a single instance of the specified element from this collection, if it is present.
      Specified by:
        `remove` in interface `java.util.Collection<java.lang.String>`
      Parameters:
        `o` - the object to remove
      Returns:
        true if this collection changed as a result of the call

    - #### removeAll

          public boolean removeAll(java.util.Collection<?> c)

      Removes all this collection's elements that are also contained in the specified collection
      Specified by:
        `removeAll` in interface `java.util.Collection<java.lang.String>`
      Parameters:
        `c` - the collection to remove
      Returns:
        true if the collection changed

    - #### retainAll

          public boolean retainAll(java.util.Collection<?> c)

      Retains only the elements in this collection that are contained in the specified collection
      Specified by:
        `retainAll` in interface `java.util.Collection<java.lang.String>`
      Parameters:
        `c` - the collection to use as reference
      Returns:
        true if this collection changed as a result of the call

    - #### size

          public int size()

      Returns the number of elements in this collection.
      Specified by:
        `size` in interface `java.util.Collection<java.lang.String>`
      Returns:
        the number of nodes in the tree

    - #### toArray

          public java.lang.Object[] toArray()

      Returns an array containing all of the elements in this collection.
      Specified by:
        `toArray` in interface `java.util.Collection<java.lang.String>`
      Returns:
        the stored strings as array

    - #### toArray

          public <T> T[] toArray(T[] a)

      Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.
      Specified by:
        `toArray` in interface `java.util.Collection<java.lang.String>`
      Parameters:
        `a` - the array into which the elements of this collection are to be stored
      Returns:
        an array containing the elements of this collection

    - #### toString

          public java.lang.String toString()

      returns the trie in string representation
      Overrides:
        `toString` in class `java.lang.Object`
      Returns:
        the trie as string

    - #### getRevision

          public java.lang.String getRevision()

      Returns the revision string.
      Specified by:
        `getRevision` in interface `RevisionHandler`
      Returns:
        the revision

    - #### main

          public static void main(java.lang.String[] args)

      Only for testing (prints the built Trie). Arguments are added to the Trie. If not arguments provided then a few default strings are uses for building.
      Parameters:
        `args` - commandline arguments