edu.ksu.cis.viewer
Class Trie

java.lang.Object
  edu.ksu.cis.viewer.Trie

All Implemented Interfaces:

BSTInterface, TreeInterface

public final class Trie

extends Object

implements BSTInterface, TreeInterface

An immutable trie that can draw itself. The trie is immutable in the sense that any Trie returned by a public constructor or method cannot subsequently be changed. A trie is comprised of a nonempty tree containing all of the characters used in the strings that it stores. The root of the tree stores null, and its children store the first characters of all of the strings stored. Characters occurring in subsequent positions of a string are stored in children of the characters they follow. Nodes that end contained strings are colored red, and other nodes are colored black. Thus a string is contained in the trie if its first character is a child of the root, its second character is a child of that character, and so on until its last character is reached, and this character is red. If the empty string is to be stored, the root will be drawn red. The children of a given node will be drawn in order of their Unicode values.

Author:

Rod Howell (howell@cis.ksu.edu)

Constructor Summary

Trie()
Constructs an empty Trie.

Method Summary

Object	clone() Because this structure is immutable, this method simply returns this Trie.
TreeInterface[]	getChildren() Returns the children of this Trie.
JComponent	getDrawing() Returns a drawing of this Trie.
JComponent	getDrawing(Font fnt) Returns a drawing of this tree using the given Font.
Object	getRoot() Returns the root of this Trie.
boolean	isEmpty() Always returns false.
BSTInterface	put(String key) Returns the Trie resulting from the insertion of key into this Trie.
BSTInterface	remove(String key) Returns the Trie resulting from the removal of key from this Trie.

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Trie

public Trie()

Constructs an empty Trie.

Method Detail

put

public BSTInterface put(String key)
                 throws NullPointerException

Returns the Trie resulting from the insertion of key into this Trie. If key is already in this Trie, an identical Trie will be returned.

Specified by:

put in interface BSTInterface

Throws:

NullPointerException - If key is null

remove

public BSTInterface remove(String key)
                    throws NullPointerException

Returns the Trie resulting from the removal of key from this Trie. If key is not in this Trie, an identical Trie is returned.

Specified by:

remove in interface BSTInterface

Throws:

NullPointerException - If key is null

getDrawing

public JComponent getDrawing()

Returns a drawing of this Trie.

Specified by:

getDrawing in interface BSTInterface

getDrawing

public JComponent getDrawing(Font fnt)
                      throws NullPointerException

Returns a drawing of this tree using the given Font.

Specified by:

getDrawing in interface BSTInterface

Throws:

NullPointerException - if fnt is null.

clone

public Object clone()

Because this structure is immutable, this method simply returns this Trie.

Specified by:

clone in interface BSTInterface

getRoot

public Object getRoot()

Returns the root of this Trie. This method is intended for use by the TreeDrawing class.

Specified by:

getRoot in interface TreeInterface

See Also:

Object.toString()

getChildren

public TreeInterface[] getChildren()

Returns the children of this Trie. This method is intended for use by the TreeDrawing class.

Specified by:

getChildren in interface TreeInterface

isEmpty

public boolean isEmpty()

Always returns false. This method is intended for use by the TreeDrawing class.

Specified by:

isEmpty in interface TreeInterface