Package edu.ksu.cis.viewer

Class PatriciaTrie

java.lang.Object
edu.ksu.cis.viewer.PatriciaTrie
All Implemented Interfaces:
BSTInterface, TreeInterface, Serializable
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 (rhowell@ksu.edu)
See Also:

  • Constructor Details

    • PatriciaTrie

      public PatriciaTrie()
      Constructs an empty PatriciaTrie.

  • Method Details

    • 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
      Parameters:
      key - the key to insert
      Returns:
      the resutling tree
      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
      Parameters:
      key - the key to remove
      Returns:
      the resulting tree
      Throws:
      NullPointerException - If key is null

    • getDrawing

      public JComponent getDrawing()
      Returns a drawing of this PatriciaTrie.
      Specified by:
      getDrawing in interface BSTInterface
      Returns:
      a drawing of the tree

    • getDrawing

      public JComponent getDrawing(Font fnt) throws NullPointerException
      Returns a drawing of this tree using the given Font.
      Specified by:
      getDrawing in interface BSTInterface
      Parameters:
      fnt - the font to use
      Returns:
      a drawing of the tree
      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
      Overrides:
      clone in class Object
      Returns:
      a clone of the this tree

    • 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
      Returns:
      the root of this tree
      See Also:

    • 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
      Returns:
      an array containing the children of this tree

    • 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
      Returns:
      whether this tree is empty