edu.ksu.cis.viewer
Class PatriciaTrie

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

All Implemented Interfaces:

BSTInterface, TreeInterface

public final class PatriciaTrie

extends Object

implements BSTInterface, TreeInterface

An immutable Patricia trie that can draw itself. The trie is immutable in the sense that any PatriciaTrie returned by a public constructor or method cannot subsequently be changed. A Patricia trie contains a set of strings. Each subtree stores in its root the longest common prefix of all strings contained within that subtree. For each string stored in the subtree, a suffix is computed by removing the prefix stored in the root. If there is more than one such suffix, each of the suffixes is stored in one of the children, a different child for each distinct character beginning a suffix, plus a child for the empty suffix if it is present. Note that according to these rules, no node other than the root or a leaf will store an empty string.

Author:

Rod Howell (howell@cis.ksu.edu)

Constructor Summary

PatriciaTrie()
Constructs an empty PatriciaTrie.

Method Summary

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

Methods inherited from class java.lang.Object

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

Constructor Detail

PatriciaTrie

public PatriciaTrie()

Constructs an empty PatriciaTrie.

Method Detail

put

public BSTInterface put(String key)
                 throws NullPointerException

Returns the PatriciaTrie resulting from the insertion of key into this PatriciaTrie. If key is already in this PatriciaTrie, 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 PatriciaTrie resulting from the removal of key from this PatriciaTrie. If key is not in this PatriciaTrie, an identical PatriciaTrie is returned.

Specified by:

remove in interface BSTInterface

Throws:

NullPointerException - If key is null

getDrawing

public JComponent getDrawing()

Returns a drawing of this PatriciaTrie.

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 PatriciaTrie.

Specified by:

clone in interface BSTInterface

getRoot

public Object getRoot()

Returns the root of this PatriciaTrie. 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 PatriciaTrie. This method is intended for use by the TreeDrawing class.

Specified by:

getChildren in interface TreeInterface

isEmpty

public boolean isEmpty()

Returns true if this PatriciaTrie is empty. This method is intended for use by the TreeDrawing class.

Specified by:

isEmpty in interface TreeInterface