java/src/main/com/google/appengine/api/datastore/PrefixTrie.java

   1 // Copyright 2007 Google Inc. All Rights Reserved.
   2
   3 package com.google.appengine.api.datastore;
   4
   5 import com.google.common.collect.Maps;
   6
   7 import java.util.Map;
   8
   9 /**
  10  * Trie implementation supporting CharSequences as prefixes.
  11  *
  12  * <p>Prefixes are sequences of characters, and the set of allowed characters is
  13  * specified as a range of sequential characters. By default, any seven-bit
  14  * character may appear in a prefix, and so the trie is a 128-ary tree.
  15  *
  16  * @param <T> the type of values in the trie.
  17  *
  18  */
  19 class PrefixTrie<T> {
  20   private final char rangeOffset;
  21   private final int rangeSize;
  22
  23   private final Node<T> root;
  24
  25   /** Constructs a trie for holding strings of seven-bit characters. */
  26   PrefixTrie() {
  27     rangeOffset = '\0';
  28     rangeSize = 128;
  29     root = new Node<T>(rangeSize);
  30   }
  31
  32   /**
  33    * Constructs a trie for holding strings of characters. The set of characters
  34    * allowed in prefixes is given by the range [rangeOffset, lastCharInRange],
  35    * inclusive.
  36    */
  37   PrefixTrie(char firstCharInRange, char lastCharInRange) {
  38     this.rangeOffset = firstCharInRange;
  39     this.rangeSize = lastCharInRange - firstCharInRange + 1;
  40
  41     if (rangeSize <= 0) {
  42       throw new IllegalArgumentException("Char range must include some chars");
  43     }
  44
  45     root = new Node<T>(rangeSize);
  46   }
  47
  48   /**
  49    * Maps prefix to value, which must not be null.
  50    *
  51    * @return the previous value stored for this prefix, or {@code null} if none
  52    *
  53    * @throws IllegalArgumentException if prefix is an empty string, or
  54    * contains a character outside the range of legal prefix characters.
  55    */
  56   T put(CharSequence prefix, T value) {
  57     if (value == null) {
  58       throw new NullPointerException();
  59     }
  60     return putInternal(prefix, value);
  61   }
  62
  63   private T putInternal(CharSequence prefix, T value) {
  64     Node<T> current = root;
  65     for (int i = 0; i < prefix.length(); i++) {
  66       int nodeIndex = prefix.charAt(i) - rangeOffset;
  67       try {
  68         Node<T> next = current.next[nodeIndex];
  69         if (next == null) {
  70           next = current.next[nodeIndex] = new Node<T>(rangeSize);
  71         }
  72         current = next;
  73       } catch (ArrayIndexOutOfBoundsException e) {
  74         throw new IllegalArgumentException(
  75             "'" + prefix.charAt(i) + "' is not a legal prefix character.");
  76       }
  77     }
  78     T oldValue = current.value;
  79     current.value = value;
  80     return oldValue;
  81   }
  82
  83   /**
  84    * Finds a prefix that matches {@code s} and returns the mapped value. If
  85    * multiple prefixes in the map match {@code s}, the longest match wins.
  86    *
  87    * @return value for prefix matching {@code s}, or {@code null} if none match
  88    */
  89   T get(CharSequence s) {
  90     Node<T> deepestWithValue = root;
  91     Node<T> current = root;
  92     for (int i = 0; i < s.length(); i++) {
  93       int nodeIndex = s.charAt(i) - rangeOffset;
  94       if (nodeIndex < 0 || rangeSize <= nodeIndex) {
  95         return null;
  96       }
  97       current = current.next[nodeIndex];
  98       if (current == null) {
  99         break;
 100       }
 101       if (current.value != null) {
 102         deepestWithValue = current;
 103       }
 104     }
 105     return deepestWithValue.value;
 106   }
 107
 108   /**
 109    * Removes an exact prefix stored in the map, returning the old value,
 110    * or null if it did not exist. Inverse operation of put(prefix).
 111    *
 112    * @return the previous value stored for this prefix, or {@code null} if none
 113    *
 114    * @throws IllegalArgumentException if prefix is an empty string, or
 115    * contains a character outside the range of legal prefix characters.
 116    */
 117   T remove(CharSequence prefix) {
 118     return putInternal(prefix, null);
 119   }
 120
 121   /**
 122    * Returns a Map containing the same data as this structure.
 123    *
 124    * <p>This implementation constructs and populates an entirely new map rather
 125    * than providing a map view on the trie, so this is mostly useful for
 126    * debugging.
 127    *
 128    * @return a Map mapping each prefix to its corresponding value.
 129    */
 130   Map<String, T> toMap() {
 131     Map<String, T> map = Maps.newLinkedHashMap();
 132     addEntries(root, new StringBuilder(), map);
 133     return map;
 134   }
 135
 136   /**
 137    * Adds to the given map all entries at or below the given node.
 138    *
 139    * @param builder a StringBuilder containing the prefix for the given node.
 140    */
 141   private void addEntries(
 142       Node<T> node, StringBuilder builder, Map<String, T> map) {
 143     if (node.value != null) {
 144       map.put(builder.toString(), node.value);
 145     }
 146
 147     for (int i = 0; i < node.next.length; i++) {
 148       Node<T> next = node.next[i];
 149       if (next != null) {
 150         builder.append((char) (i + rangeOffset));
 151         addEntries(next, builder, map);
 152         builder.deleteCharAt(builder.length() - 1);
 153       }
 154     }
 155   }
 156
 157   private static class Node<T> {
 158     T value;
 159     final Node<T>[] next;
 160
 161     @SuppressWarnings({"rawtypes", "unchecked"})
 162     Node(int numChildren) {
 163       next = new Node[numChildren];
 164     }
 165   }
 166 }