Package 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: 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 triestatic 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 collectionvoid
clear()
Removes all of the elements from this collectionjava.lang.Object
clone()
returns a deep copy of itselfboolean
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 trieboolean
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 nodesjava.lang.String
getRevision()
Returns the revision string.Trie.TrieNode
getRoot()
returns the root node of the triejava.util.Vector<java.lang.String>
getWithPrefix(java.lang.String prefix)
returns all stored strings that match the given prefixint
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 collectionboolean
retainAll(java.util.Collection<?> c)
Retains only the elements in this collection that are contained in the specified collectionint
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
-
-
-
Method Detail
-
add
public boolean add(java.lang.String o)
Ensures that this collection contains the specified element.- Specified by:
add
in interfacejava.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 interfacejava.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 interfacejava.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 interfacejava.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 interfacejava.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 interfacejava.util.Collection<java.lang.String>
- Overrides:
equals
in classjava.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 interfacejava.util.Collection<java.lang.String>
- Overrides:
hashCode
in classjava.lang.Object
- Returns:
- the hash code
-
isEmpty
public boolean isEmpty()
Returns true if this collection contains no elements.- Specified by:
isEmpty
in interfacejava.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 interfacejava.util.Collection<java.lang.String>
- Specified by:
iterator
in interfacejava.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 interfacejava.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 interfacejava.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 interfacejava.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 interfacejava.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 interfacejava.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 interfacejava.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 classjava.lang.Object
- Returns:
- the trie as string
-
getRevision
public java.lang.String getRevision()
Returns the revision string.- Specified by:
getRevision
in interfaceRevisionHandler
- 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
-
-