Package com.abstractkamen.datastructures.impl.trees.search

Class PrefixTrieImpl

java.lang.Object
com.abstractkamen.datastructures.impl.trees.search.PrefixTrieImpl
All Implemented Interfaces:
PrefixTrie
Direct Known Subclasses:
ReversePrefixTrie
public class PrefixTrieImpl extends Object implements PrefixTrie
Basic implementation of a prefix 'trie'. Each character of an inserted string is stored in a node in lexicographical order and each node has children and a parent. All nodes have one common ancestor which is the root. A node is marked if the path from the root to it forms a word (a string inserted by insert(String)).

  • Constructor Details

    • PrefixTrieImpl

      public PrefixTrieImpl()
      Constructor

  • Method Details

    • getRoot

      protected PrefixTrieImpl.PrefixTrieNode getRoot()
      Get the root of this tree.
      Returns:
      root of this tree which can never be null

    • startsWith

      public Collection<String> startsWith(String prefix, int limit)
      Description copied from interface: PrefixTrie
      Try to find strings which start with prefix. Matching strings are always in lexicographical order.
      Specified by:
      startsWith in interface PrefixTrie
      Parameters:
      prefix - to look for
      limit - maximum number of found strings
      Returns:
      collection of words with the same prefix

    • isPrefix

      public boolean isPrefix(String substring)
      Description copied from interface: PrefixTrie
      Checks if prefix is present in this trie.
      Specified by:
      isPrefix in interface PrefixTrie
      Parameters:
      substring - to check
      Returns:
      true if prefix exists

    • insert

      public boolean insert(String string)
      Description copied from interface: PrefixTrie
      Inserts a word into the trie. Duplicate words will be ignored.
      Specified by:
      insert in interface PrefixTrie
      Parameters:
      string - word to be inserted
      Returns:
      true if the word was inserted false if it already existed

    • delete

      public boolean delete(String string)
      Description copied from interface: PrefixTrie
      Deletes a word from the trie. The number of complete words will be decremented by one and the size of the trie will shrink by the number of unique characters and their placements in the deleted word if they aren't used by a different word.
      Specified by:
      delete in interface PrefixTrie
      Parameters:
      string - to be deleted
      Returns:
      true if word is successfully deleted false if word was not in the trie

    • size

      public int size()
      Description copied from interface: PrefixTrie
      The number of nodes in this trie.
      Specified by:
      size in interface PrefixTrie
      Returns:
      number of nodes

    • completeWords

      public int completeWords()
      Description copied from interface: PrefixTrie
      The number of complete words in this trie.
      Specified by:
      completeWords in interface PrefixTrie
      Returns:
      number of complete words

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • contains

      public boolean contains(String string)
      Description copied from interface: PrefixTrie
      Checks if a word exists in this trie.
      Specified by:
      contains in interface PrefixTrie
      Parameters:
      string - to check
      Returns:
      true if word is in this trie

    • prettyString

      public String prettyString()
      Description copied from interface: PrefixTrie
      A detailed string representation of the structure of this trie.
      Specified by:
      prettyString in interface PrefixTrie
      Returns:
      detailed string

    • visitWordNode

      protected void visitWordNode(PrefixTrieImpl.PrefixTrieNode node, StringBuilder visitor, StringBuilder currentChars)
      Visit a node which we know is a word.
      Parameters:
      node - word node
      visitor - sb visitor
      currentChars - word so far

    • insert

      protected PrefixTrieImpl.PrefixTrieNode insert(String word, PrefixTrieImpl.PrefixTrieNode root, int i, BiFunction<Integer,PrefixTrieImpl.PrefixTrieNode,PrefixTrieImpl.PrefixTrieNode> factory)
      Inserts a word character by character where first a character is lookup in the root and if it's missing a new node is created and appended to the root after which the algorithm is repeated recursively until we reach the end of the word. The final result of the recursion will be the leaf node.
      Parameters:
      word - input sting
      root - root node
      i - current character index
      factory - node factory - useful in extensions
      Returns:
      the 'inserted' node

    • search

      protected boolean search(PrefixTrieImpl.PrefixTrieNode n, String needle, int i, Collection<String> result, int resultLimit, Predicate<PrefixTrieImpl.PrefixTrieNode> resultTest, StringBuilder currentChars)
      Searching method for this trie. Will walk through all characters in needle and find a possible path of nodes for them. If the path exists return true.
      Parameters:
      n - current node
      needle - string
      i - offset
      result - string storage
      resultLimit - storage limit
      resultTest - add to result collection if true
      currentChars - word so far
      Returns:
      true if a needle path exists

    • delete

      protected boolean delete(PrefixTrieImpl.PrefixTrieNode n, String word, int i)
      Internal protected delete for this tree implementation.
      Parameters:
      n - current node
      word - word to delete
      i - current index
      Returns:
      true if word was deleted

    • shouldDecrementWordOnDelete

      protected boolean shouldDecrementWordOnDelete(PrefixTrieImpl.PrefixTrieNode n)
      completeWords decrementing condition. Can be overridden in extensions.
      Parameters:
      n - word node
      Returns:
      true if completeWords should be decremented