Package weka.core

Class Trie

java.lang.Object
weka.core.Trie
All Implemented Interfaces:
Serializable, Cloneable, Iterable<String>, Collection<String>, RevisionHandler
public class Trie extends Object implements Serializable, Cloneable, Collection<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:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    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
    Description
    Trie()
    initializes the data structure

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(String o)
    Ensures that this collection contains the specified element.
    boolean
    addAll(Collection<? extends String> c)
    Adds all of the elements in the specified collection to this collection
    void
    clear()
    Removes all of the elements from this collection
    Object
    clone()
    returns a deep copy of itself
    boolean
    contains(Object o)
    Returns true if this collection contains the specified element.
    boolean
    containsAll(Collection<?> c)
    Returns true if this collection contains all of the elements in the specified collection.
    boolean
    containsPrefix(String prefix)
    checks whether the given prefix is stored in the trie
    boolean
    equals(Object o)
    Compares the specified object with this collection for equality.
    String
    getCommonPrefix()
    returns the common prefix for all the nodes
    String
    getRevision()
    Returns the revision string.
    Trie.TrieNode
    getRoot()
    returns the root node of the trie
    Vector<String>
    getWithPrefix(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.
    Iterator<String>
    iterator()
    Returns an iterator over the elements in this collection.
    static void
    main(String[] args)
    Only for testing (prints the built Trie).
    boolean
    remove(Object o)
    Removes a single instance of the specified element from this collection, if it is present.
    boolean
    removeAll(Collection<?> c)
    Removes all this collection's elements that are also contained in the specified collection
    boolean
    retainAll(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.
    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.
    String
    toString()
    returns the trie in string representation

    Methods inherited from class java.lang.Object

    getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.util.Collection

    parallelStream, removeIf, spliterator, stream, toArray

    Methods inherited from interface java.lang.Iterable

    forEach

  • Constructor Details

    • Trie

      public Trie()
      initializes the data structure

  • Method Details

    • add

      public boolean add(String o)
      Ensures that this collection contains the specified element.
      Specified by:
      add in interface Collection<String>
      Parameters:
      o - the string to add
      Returns:
      true if the structure changed

    • addAll

      public boolean addAll(Collection<? extends String> c)
      Adds all of the elements in the specified collection to this collection
      Specified by:
      addAll in interface Collection<String>
      Parameters:
      c - the collection to add

    • clear

      public void clear()
      Removes all of the elements from this collection
      Specified by:
      clear in interface Collection<String>

    • clone

      public Object clone()
      returns a deep copy of itself
      Returns:
      a copy of itself

    • contains

      public boolean contains(Object o)
      Returns true if this collection contains the specified element.
      Specified by:
      contains in interface Collection<String>
      Parameters:
      o - the object to check for in trie
      Returns:
      true if found

    • containsAll

      public boolean containsAll(Collection<?> c)
      Returns true if this collection contains all of the elements in the specified collection.
      Specified by:
      containsAll in interface Collection<String>
      Parameters:
      c - the collection to look for in the trie
      Returns:
      true if all elements were found

    • containsPrefix

      public boolean containsPrefix(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(Object o)
      Compares the specified object with this collection for equality.
      Specified by:
      equals in interface Collection<String>
      Overrides:
      equals in class Object
      Parameters:
      o - the object to check for equality

    • getCommonPrefix

      public 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 Vector<String> getWithPrefix(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 Collection<String>
      Overrides:
      hashCode in class Object
      Returns:
      the hash code

    • isEmpty

      public boolean isEmpty()
      Returns true if this collection contains no elements.
      Specified by:
      isEmpty in interface Collection<String>
      Returns:
      true if empty

    • iterator

      public Iterator<String> iterator()
      Returns an iterator over the elements in this collection.
      Specified by:
      iterator in interface Collection<String>
      Specified by:
      iterator in interface Iterable<String>
      Returns:
      returns an iterator over all the stored strings

    • remove

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

    • removeAll

      public boolean removeAll(Collection<?> c)
      Removes all this collection's elements that are also contained in the specified collection
      Specified by:
      removeAll in interface Collection<String>
      Parameters:
      c - the collection to remove
      Returns:
      true if the collection changed

    • retainAll

      public boolean retainAll(Collection<?> c)
      Retains only the elements in this collection that are contained in the specified collection
      Specified by:
      retainAll in interface Collection<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 Collection<String>
      Returns:
      the number of nodes in the tree

    • toArray

      public Object[] toArray()
      Returns an array containing all of the elements in this collection.
      Specified by:
      toArray in interface Collection<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 Collection<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 String toString()
      returns the trie in string representation
      Overrides:
      toString in class Object
      Returns:
      the trie as string

    • getRevision

      public String getRevision()
      Returns the revision string.
      Specified by:
      getRevision in interface RevisionHandler
      Returns:
      the revision

    • main

      public static void main(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