jars/icu4j-4_4_2-src/main/classes/core/src/com/ibm/icu/impl/TextTrieMap.java

   1 /*\r
   2  * ********************************************************************************\r
   3  * Copyright (C) 2007-2009, International Business Machines Corporation and others.\r
   4  * All Rights Reserved.\r
   5  * ********************************************************************************\r
   6  */\r
   7 package com.ibm.icu.impl;\r
   8 \r
   9 import java.util.ArrayList;\r
  10 import java.util.Iterator;\r
  11 import java.util.LinkedList;\r
  12 import java.util.List;\r
  13 \r
  14 import com.ibm.icu.lang.UCharacter;\r
  15 import com.ibm.icu.text.UTF16;\r
  16 \r
  17 /**\r
  18  * TextTrieMap is a trie implementation for supporting\r
  19  * fast prefix match for the key.\r
  20  */\r
  21 public class TextTrieMap<V> {\r
  22     /**\r
  23      * Constructs a TextTrieMap object.\r
  24      * \r
  25      * @param ignoreCase true to use case insensitive match\r
  26      */\r
  27     public TextTrieMap(boolean ignoreCase) {\r
  28         this.ignoreCase = ignoreCase;\r
  29     }\r
  30 \r
  31     /**\r
  32      * Adds the text key and its associated object in this object.\r
  33      * \r
  34      * @param text The text.\r
  35      * @param o The object associated with the text.\r
  36      */\r
  37     public synchronized void put(String text, V o) {\r
  38         CharacterNode node = root;\r
  39         for (int i = 0; i < text.length(); i++) {\r
  40             int ch = UTF16.charAt(text, i);\r
  41             node = node.addChildNode(ch);\r
  42             if (UTF16.getCharCount(ch) == 2) {\r
  43                 i++;\r
  44             }\r
  45         }\r
  46         node.addObject(o);\r
  47     }\r
  48 \r
  49     /**\r
  50      * Gets an iterator of the objects associated with the\r
  51      * longest prefix matching string key.\r
  52      * \r
  53      * @param text The text to be matched with prefixes.\r
  54      * @return An iterator of the objects associated with\r
  55      * the longest prefix matching matching key, or null\r
  56      * if no matching entry is found.\r
  57      */\r
  58     public Iterator<V> get(String text) {\r
  59         return get(text, 0);\r
  60     }\r
  61 \r
  62     /**\r
  63      * Gets an iterator of the objects associated with the\r
  64      * longest prefix matching string key starting at the \r
  65      * specified position.\r
  66      * \r
  67      * @param text The text to be matched with prefixes.\r
  68      * @param start The start index of of the text\r
  69      * @return An iterator of the objects associated with the\r
  70      * longest prefix matching matching key, or null if no \r
  71      * matching entry is found.\r
  72      */\r
  73     public Iterator<V> get(String text, int start) {\r
  74         LongestMatchHandler<V> handler = new LongestMatchHandler<V>();\r
  75         find(text, start, handler);\r
  76         return handler.getMatches();\r
  77     }\r
  78 \r
  79     public void find(String text, ResultHandler<V> handler) {\r
  80         find(text, 0, handler);\r
  81     }\r
  82     \r
  83     public void find(String text, int start, ResultHandler<V> handler) {\r
  84         find(root, text, start, start, handler);\r
  85     }\r
  86 \r
  87     /*\r
  88      * Find an iterator of the objects associated with the\r
  89      * longest prefix matching string key under the specified node.\r
  90      * \r
  91      * @param node The character node in this trie.\r
  92      * @param text The text to be matched with prefixes.\r
  93      * @param start The start index within the text.\r
  94      * @param index The current index within the text.\r
  95      * @param handler The result handler, ResultHandler#handlePrefixMatch\r
  96      * is called when any prefix match is found.\r
  97      */\r
  98     private synchronized void find(CharacterNode node, String text,\r
  99             int start, int index, ResultHandler<V> handler) {\r
 100         Iterator<V> itr = node.iterator();\r
 101         if (itr != null) {\r
 102             if (!handler.handlePrefixMatch(index - start, itr)) {\r
 103                 return;\r
 104             }\r
 105         }\r
 106         if (index < text.length()) {\r
 107             List<CharacterNode> childNodes = node.getChildNodes();\r
 108             if (childNodes == null) {\r
 109                 return;\r
 110             }\r
 111             int ch = UTF16.charAt(text, index);\r
 112             int chLen = UTF16.getCharCount(ch);\r
 113             for (int i = 0; i < childNodes.size(); i++) {\r
 114                 CharacterNode child = childNodes.get(i);\r
 115                 if (compare(ch, child.getCharacter())) {\r
 116                     find(child, text, start, index + chLen, handler);\r
 117                     break;\r
 118                 }\r
 119             }\r
 120         }\r
 121     }\r
 122     \r
 123     /**\r
 124      * A private method used for comparing two characters.\r
 125      * \r
 126      * @param ch1 The first character.\r
 127      * @param ch2 The second character.\r
 128      * @return true if the first character matches the second.\r
 129      */\r
 130     private boolean compare(int ch1, int ch2) {\r
 131         if (ch1 == ch2) {\r
 132             return true;\r
 133         }\r
 134         else if (ignoreCase) {\r
 135             if (UCharacter.toLowerCase(ch1) == UCharacter.toLowerCase(ch2)) {\r
 136                 return true;\r
 137             }\r
 138             else if (UCharacter.toUpperCase(ch1) == UCharacter.toUpperCase(ch2)) {\r
 139                 return true;\r
 140             }\r
 141         }\r
 142         return false;\r
 143     }\r
 144 \r
 145     // The root node of this trie\r
 146     private CharacterNode root = new CharacterNode(0);\r
 147 \r
 148     // Character matching option\r
 149     boolean ignoreCase;\r
 150 \r
 151     /**\r
 152      * Inner class representing a character node in the trie.\r
 153      */\r
 154     private class CharacterNode {\r
 155         int character;\r
 156         List<CharacterNode> children;\r
 157         List<V> objlist;\r
 158 \r
 159         /**\r
 160          * Constructs a node for the character.\r
 161          * \r
 162          * @param ch The character associated with this node.\r
 163          */\r
 164         public CharacterNode(int ch) {\r
 165             character = ch;\r
 166         }\r
 167 \r
 168         /**\r
 169          * Gets the character associated with this node.\r
 170          * \r
 171          * @return The character\r
 172          */\r
 173         public int getCharacter() {\r
 174             return character;\r
 175         }\r
 176 \r
 177         /**\r
 178          * Adds the object to the node.\r
 179          *  \r
 180          * @param obj The object set in the leaf node.\r
 181          */\r
 182         public void addObject(V obj) {\r
 183             if (objlist == null) {\r
 184                 objlist = new LinkedList<V>();\r
 185             }\r
 186             objlist.add(obj);\r
 187         }\r
 188 \r
 189         /**\r
 190          * Gets an iterator of the objects associated with\r
 191          * the leaf node.\r
 192          * \r
 193          * @return The iterator or null if no objects are\r
 194          * associated with this node.\r
 195          */\r
 196         public Iterator<V> iterator() {\r
 197             if (objlist == null) {\r
 198                 return null;\r
 199             }\r
 200             return objlist.iterator();\r
 201         }\r
 202 \r
 203         /**\r
 204          * Adds a child node for the character under this character\r
 205          * node in the trie.  When the matching child node already\r
 206          * exists, the reference of the existing child node is\r
 207          * returned.\r
 208          * \r
 209          * @param ch The character associated with a child node.\r
 210          * @return The child node.\r
 211          */\r
 212         public CharacterNode addChildNode(int ch) {\r
 213             if (children == null) {\r
 214                 children = new ArrayList<CharacterNode>();\r
 215                 CharacterNode newNode = new CharacterNode(ch);\r
 216                 children.add(newNode);\r
 217                 return newNode;\r
 218             }\r
 219             CharacterNode node = null;\r
 220             for (int i = 0; i < children.size(); i++) {\r
 221                 CharacterNode cur = children.get(i);\r
 222                 if (compare(ch, cur.getCharacter())) {\r
 223                     node = cur;\r
 224                     break;\r
 225                 }               \r
 226             }\r
 227             if (node == null) {\r
 228                 node = new CharacterNode(ch);\r
 229                 children.add(node);\r
 230             }\r
 231             return node;\r
 232         }\r
 233 \r
 234         /**\r
 235          * Gets the list of child nodes under this node.\r
 236          * \r
 237          * @return The list of child nodes.\r
 238          */\r
 239         public List<CharacterNode> getChildNodes() {\r
 240             return children;\r
 241         }\r
 242     }\r
 243 \r
 244     /**\r
 245      * Callback handler for processing prefix matches used by\r
 246      * find method.\r
 247      */\r
 248     public interface ResultHandler<V> {\r
 249         /**\r
 250          * Handles a prefix key match\r
 251          * \r
 252          * @param matchLength Matched key's length\r
 253          * @param values An iterator of the objects associated with the matched key\r
 254          * @return Return true to continue the search in the trie, false to quit.\r
 255          */\r
 256         public boolean handlePrefixMatch(int matchLength, Iterator<V> values);\r
 257     }\r
 258 \r
 259     private static class LongestMatchHandler<V> implements ResultHandler<V> {\r
 260         private Iterator<V> matches = null;\r
 261         private int length = 0;\r
 262 \r
 263         public boolean handlePrefixMatch(int matchLength, Iterator<V> values) {\r
 264             if (matchLength > length) {\r
 265                 length = matchLength;\r
 266                 matches = values;\r
 267             }\r
 268             return true;\r
 269         }\r
 270 \r
 271         public Iterator<V> getMatches() {\r
 272             return matches;\r
 273         }\r
 274     }\r
 275 }\r