Package weka.core

Class 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: 1.2 $
    Author:
    fracpete (fracpete at waikato dot ac dot nz)
    See Also:
    Serialized Form

    • 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

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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

      • Methods inherited from interface java.util.Collection

        parallelStream, removeIf, spliterator, stream, toArray

      • Methods inherited from interface java.lang.Iterable

        forEach

    • 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
        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.util.Collection<java.lang.String>
        Specified by:
        iterator in interface java.lang.Iterable<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