TextTrieMap


1   /*
2    * *****************************************************************************
3    * Copyright (C) 2006, International Business Machines Corporation and others.
4    * All Rights Reserved.
5    * *****************************************************************************
6    */
7   package com.ibm.icu.impl;
8   
9   import java.util.ArrayList  ;
10  import java.util.List  ;
11  
12  import com.ibm.icu.lang.UCharacter;
13  import com.ibm.icu.text.UTF16;
14  
15  /**
16   * TextTrieMap is a trie implementation for supporting
17   * fast prefix match for the key.
18   */
19  public class TextTrieMap {
20      /**
21       * Costructs a TextTrieMap object.
22       * 
23       * @param ignoreCase true to use case insensitive match
24       */
25      public TextTrieMap(boolean ignoreCase) {
26          this.ignoreCase = ignoreCase;
27      }
28  
29      /**
30       * Adds the text key and its associated object in this object.
31       * 
32       * @param text The text.
33       * @param o The object associated with the text.
34       * @return The previous value associated with specified text,
35       * or null if there was no mapping for the text.
36       */
37      public synchronized Object   put(String   text, Object   o) {
38          CharacterNode node = root;
39          for (int i = 0; i < text.length(); i++) {
40              int ch = UTF16.charAt(text, i);
41              node = node.addChildNode(ch);
42              if (UTF16.getCharCount(ch) == 2) {
43                  i++;
44              }
45          }
46          Object   prevObj = node.getObject();
47          node.setObject(o);
48          return prevObj;
49      }
50  
51      /**
52       * Gets the object associated with the longest prefix
53       * matching string key.
54       * 
55       * @param text The text to be matched with prefixes.
56       * @return The object associated with the longet prefix matching
57       * matching key, or null if no matching entry is found.
58       */
59      public Object   get(String   text) {
60          return get(root, text, 0);
61      }
62  
63      /**
64       * Gets the object associated with the longest prefix
65       * matching string key starting at the specified position.
66       * 
67       * @param text The text to be matched with prefixes.
68       * @param start The start index of of the text
69       * @return The object associated with the longet prefix matching
70       * matching key, or null if no matching entry is found.
71       */
72      public Object   get(String   text, int start) {
73          return get(root, text, start);
74      }
75  
76      /**
77       * Gets the object associated with the longet prefix
78       * matching string key under the specified node.
79       * 
80       * @param node The character node in this trie.
81       * @param text The text to be matched with prefixes.
82       * @param index The current index within the text.
83       * @return The object associated with the longest prefix
84       * match under the node.
85       */
86      private synchronized Object   get(CharacterNode node, String   text, int index) {
87          Object   obj = node.getObject();
88          if (index < text.length()) {
89              List   childNodes = node.getChildNodes();
90              if (childNodes == null) {
91                  return obj;
92              }
93              int ch = UTF16.charAt(text, index);
94              int chLen = UTF16.getCharCount(ch);
95              for (int i = 0; i < childNodes.size(); i++) {
96                  CharacterNode child = (CharacterNode)childNodes.get(i);
97                  if (compare(ch, child.getCharacter())) {
98                      Object   tmp = get(child, text, index + chLen);
99                      if (tmp != null) {
100                         obj = tmp;
101                     }
102                     break;
103                 }
104             }
105         }
106         return obj;
107     }
108 
109     /**
110      * A private method used for comparing two characters.
111      * 
112      * @param ch1 The first character.
113      * @param ch2 The second character.
114      * @return true if the first character matches the second.
115      */
116     private boolean compare(int ch1, int ch2) {
117         if (ch1 == ch2) {
118             return true;
119         }
120         else if (ignoreCase) {
121             if (UCharacter.toLowerCase(ch1) == UCharacter.toLowerCase(ch2)) {
122                 return true;
123             }
124             else if (UCharacter.toUpperCase(ch1) == UCharacter.toUpperCase(ch2)) {
125                 return true;
126             }
127         }
128         return false;
129     }
130 
131     // The root node of this trie
132     private CharacterNode root = new CharacterNode(0);
133 
134     // Character matching option
135     boolean ignoreCase;
136 
137     /**
138      * Inner class representing a character node in the trie.
139      */
140     private class CharacterNode {
141         int character;
142         List   children;
143         Object   obj;
144 
145         /**
146          * Constructs a node for the character.
147          * 
148          * @param ch The character associated with this node.
149          */
150         public CharacterNode(int ch) {
151             character = ch;
152         }
153 
154         /**
155          * Gets the character associated with this node.
156          * 
157          * @return The character
158          */
159         public int getCharacter() {
160             return character;
161         }
162 
163         /**
164          * Sets the object to the node.  Only a leaf node has
165          * the reference of an object associated with a key.
166          * 
167          * @param obj The object set in the leaf node.
168          */
169         public void setObject(Object   obj) {
170             this.obj = obj;
171         }
172 
173         /**
174          * Gets the object associated the leaf node.
175          * 
176          * @return The object.
177          */
178         public Object   getObject() {
179             return obj;
180         }
181 
182         /**
183          * Adds a child node for the characer under this character
184          * node in the trie.  When the matching child node already
185          * exists, the reference of the existing child node is
186          * returned.
187          * 
188          * @param ch The character associated with a child node.
189          * @return The child node.
190          */
191         public CharacterNode addChildNode(int ch) {
192             if (children == null) {
193                 children = new ArrayList  ();
194                 CharacterNode newNode = new CharacterNode(ch);
195                 children.add(newNode);
196                 return newNode;
197             }
198             CharacterNode node = null;
199             for (int i = 0; i < children.size(); i++) {
200                 CharacterNode cur = (CharacterNode)children.get(i);
201                 if (compare(ch, cur.getCharacter())) {
202                     node = cur;
203                     break;
204                 }               
205             }
206             if (node == null) {
207                 node = new CharacterNode(ch);
208                 children.add(node);
209             }
210             return node;
211         }
212 
213         /**
214          * Gets the list of child nodes under this node.
215          * 
216          * @return The list of child nodes.
217          */
218         public List   getChildNodes() {
219             return children;
220         }
221     }
222 }
223
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags