Coverage Report - net.sf.triemap.TrieMap
 
Classes in this File Line Coverage Branch Coverage Complexity
TrieMap
94%
226/239
84%
103/122
2,865
TrieMap$1
N/A
N/A
2,865
TrieMap$Entry
91%
11/12
50%
1/2
2,865
TrieMap$TrieMapBackedProperties
93%
100/107
72%
35/48
2,865
TrieMap$TrieMapBackedProperties$1
100%
3/3
N/A
2,865
TrieMap$TrieMapBackedProperties$2
33%
1/3
N/A
2,865
TrieMap$TrieNode
86%
86/99
68%
41/60
2,865
 
 1  
 /*
 2  
  * Copyright (c) 2010, Marco Brade [https://sourceforge.net/users/mbrade] All rights reserved.
 3  
  *
 4  
  * Redistribution and use in source and binary forms, with or without
 5  
  * modification, are permitted provided that the following conditions are met:
 6  
  *
 7  
  *     * Redistributions of source code must retain the above copyright notice,
 8  
  *       this list of conditions and the following disclaimer.
 9  
  *     * Redistributions in binary form must reproduce the above copyright notice,
 10  
  *       this list of conditions and the following disclaimer in the documentation
 11  
  *       and/or other materials provided with the distribution.
 12  
  *
 13  
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 14  
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 15  
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 16  
  * ARE DISCLAIMED.
 17  
  * IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
 18  
  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 19  
  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 20  
  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 21  
  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 22  
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 23  
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 24  
  */
 25  
 
 26  
 package net.sf.triemap;
 27  
 
 28  
 import java.io.IOException;
 29  
 import java.io.ObjectInputStream;
 30  
 import java.io.ObjectOutputStream;
 31  
 import java.io.Serializable;
 32  
 import java.util.ArrayList;
 33  
 import java.util.Collection;
 34  
 import java.util.Collections;
 35  
 import java.util.Enumeration;
 36  
 import java.util.HashMap;
 37  
 import java.util.HashSet;
 38  
 import java.util.Iterator;
 39  
 import java.util.LinkedList;
 40  
 import java.util.List;
 41  
 import java.util.Map;
 42  
 import java.util.Properties;
 43  
 import java.util.Set;
 44  
 import java.util.TreeMap;
 45  
 import java.util.TreeSet;
 46  
 import java.util.concurrent.locks.ReentrantReadWriteLock;
 47  
 
 48  
 import org.apache.commons.lang.StringUtils;
 49  
 
 50  
 /**
 51  
  * The TrieMap stores a list of strings in a tree based way.<br/>
 52  
  * On each String it is possible to assign an object.<br/>
 53  
  * Each Key-String can represent only one object.
 54  
  * 
 55  
  * @param <Value>
 56  
  *            the value type
 57  
  * @author Marco Brade
 58  
  */
 59  10648
 public class TrieMap<Value> implements Serializable, Map<String, Value>, Cloneable {
 60  
 
 61  
     /** The Constant serialVersionUID. */
 62  
     private static final long serialVersionUID = 1L;
 63  
 
 64  
     /** The root node. */
 65  
     private transient TrieNode<Value> rootNode;
 66  
 
 67  49
     private transient ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
 68  
 
 69  
     /**
 70  
      * Instantiates a new trie map.
 71  
      */
 72  49
     public TrieMap() {
 73  49
         rootNode = new TrieNode<Value>(' ', null, false);
 74  49
     }
 75  
 
 76  
     /**
 77  
      * Instantiates a new trie map.
 78  
      * 
 79  
      * @param map
 80  
      *            the map
 81  
      */
 82  
     public TrieMap(final Map<String, Value> map) {
 83  0
         this();
 84  0
         putAll(map);
 85  0
     }
 86  
 
 87  
     /**
 88  
      * Adds the phrase to the TrieMap<br/>
 89  
      * If the phrase has been added before and multivalue is disabled it will return false.<br/>
 90  
      * 
 91  
      * @param phrase
 92  
      *            the phrase
 93  
      * @return true, if successful
 94  
      */
 95  
     public boolean add(final String phrase) {
 96  6
         return addRecursive(rootNode, phrase, null, false);
 97  
     }
 98  
 
 99  
     /**
 100  
      * Adds the phrase to the TrieMap and assigns the given object to it.<br/>
 101  
      * If the phrase has been added before it will return false. The previous stored object will stay as is even if it has not been set.<br/>
 102  
      * 
 103  
      * @param phrase
 104  
      *            the phrase
 105  
      * @param object
 106  
      *            the object
 107  
      * @return true, if successful
 108  
      */
 109  
     public boolean add(final String phrase, final Value object) {
 110  519
         return addRecursive(rootNode, phrase, object, false);
 111  
     }
 112  
 
 113  
     /**
 114  
      * As properties.
 115  
      * 
 116  
      * @return the properties
 117  
      */
 118  
     public Properties asProperties() {
 119  9
         return new TrieMapBackedProperties();
 120  
     }
 121  
 
 122  
     /**
 123  
      * As properties.
 124  
      * 
 125  
      * @param defaults
 126  
      *            the defaults
 127  
      * @return the properties
 128  
      */
 129  
     public Properties asProperties(final Properties defaults) {
 130  9
         return new TrieMapBackedProperties(defaults);
 131  
     }
 132  
 
 133  
     /* (non-Javadoc)
 134  
      * @see java.util.Map#clear()
 135  
      */
 136  
     @Override
 137  
     public void clear() {
 138  10
         rootNode = new TrieNode<Value>(' ', null, false);
 139  10
     }
 140  
 
 141  
     /* (non-Javadoc)
 142  
      * @see java.lang.Object#clone()
 143  
      */
 144  
     @SuppressWarnings("unchecked")
 145  
     @Override
 146  
     public TrieMap<Value> clone() {
 147  1
         TrieMap<Value> clone = null;
 148  
         try {
 149  1
             clone = (TrieMap<Value>) super.clone();
 150  1
             clone.rootNode = rootNode.clone();
 151  0
         } catch (final CloneNotSupportedException e) {
 152  1
         }
 153  1
         return clone;
 154  
     }
 155  
 
 156  
     /* (non-Javadoc)
 157  
      * @see java.util.Map#containsKey(java.lang.Object)
 158  
      */
 159  
     @Override
 160  
     public boolean containsKey(final Object key) {
 161  17
         if (key instanceof String) {
 162  15
             return containsPrefix((String) key);
 163  
         }
 164  2
         return false;
 165  
     }
 166  
 
 167  
     /**
 168  
      * Checks if a node would match the prefix.
 169  
      * 
 170  
      * @param prefix
 171  
      *            the prefix
 172  
      * 
 173  
      * @return true, if successful
 174  
      */
 175  
     public boolean containsPrefix(final String prefix) {
 176  18
         final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, prefix);
 177  18
         return (matchedNode != null);
 178  
     }
 179  
 
 180  
     /* (non-Javadoc)
 181  
      * @see java.util.Map#containsValue(java.lang.Object)
 182  
      */
 183  
     @Override
 184  
     public boolean containsValue(final Object value) {
 185  31
         return getPathForValue(value) != null;
 186  
     }
 187  
 
 188  
     /* (non-Javadoc)
 189  
      * @see java.util.Map#entrySet()
 190  
      */
 191  
     @Override
 192  
     public Set<java.util.Map.Entry<String, Value>> entrySet() {
 193  2
         final Set<Map.Entry<String, Value>> result = new TreeSet<Map.Entry<String, Value>>();
 194  2
         for (final String key : keySet()) {
 195  22
             result.add(new Entry(key));
 196  
         }
 197  2
         return result;
 198  
     }
 199  
 
 200  
     /* (non-Javadoc)
 201  
      * @see java.lang.Object#equals(java.lang.Object)
 202  
      */
 203  
     @SuppressWarnings("unchecked")
 204  
     @Override
 205  
     public boolean equals(final Object obj) {
 206  2
         if (this == obj) {
 207  0
             return true;
 208  
         }
 209  2
         if (obj == null) {
 210  0
             return false;
 211  
         }
 212  2
         if (getClass() != obj.getClass()) {
 213  0
             return false;
 214  
         }
 215  2
         final TrieMap other = (TrieMap) obj;
 216  2
         if (rootNode == null) {
 217  0
             if (other.rootNode != null) {
 218  0
                 return false;
 219  
             }
 220  2
         } else if (!rootNode.equals(other.rootNode)) {
 221  0
             return false;
 222  
         }
 223  2
         return true;
 224  
     }
 225  
 
 226  
     /**
 227  
      * Forces to add the phrase and assigns the given object to it even if an existing object has been set before.<br/>
 228  
      * 
 229  
      * @param phrase
 230  
      *            the phrase
 231  
      * @param object
 232  
      *            the object
 233  
      * @return true, if successful
 234  
      */
 235  
     public boolean forceAdd(final String phrase, final Value object) {
 236  35
         return addRecursive(rootNode, phrase, object, true);
 237  
     }
 238  
 
 239  
     /* (non-Javadoc)
 240  
      * @see java.util.Map#get(java.lang.Object)
 241  
      */
 242  
     @Override
 243  
     public Value get(final Object key) {
 244  91
         if (key instanceof String) {
 245  90
             final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, (String) key);
 246  90
             if (matchedNode != null) {
 247  68
                 final Value result = matchedNode.getObject();
 248  68
                 return result;
 249  
             }
 250  
         }
 251  23
         return null;
 252  
     }
 253  
 
 254  
     /**
 255  
      * Finds the path that is best matching the given prefix.<br/>
 256  
      * Returns null if the given prefix is empty or the given prefix is not contained in this TrieMap.<br/>
 257  
      * The returned path might be a part of the prefix, the complete prefix or null if the no part of the prefix is contained in this TrieMap<br/>
 258  
      * The result might not be a complete key.
 259  
      * 
 260  
      * @param prefix
 261  
      *            the prefix
 262  
      * @return the best matching prefix
 263  
      */
 264  
     public String getBestMatchingPath(final String prefix) {
 265  6
         if (isEmpty(prefix)) {
 266  1
             return null;
 267  
         }
 268  5
         final TrieNode<Value> trieNode = rootNode.getChildNode(prefix.charAt(0));
 269  5
         if (trieNode != null) {
 270  4
             final StringBuilder builder = new StringBuilder().append(prefix.charAt(0));
 271  4
             final String subPrefix = prefix.substring(1);
 272  4
             if (StringUtils.isEmpty(subPrefix)) {
 273  1
                 return builder.toString();
 274  
             } else {
 275  3
                 return findLastMatchingRecursivly(trieNode, prefix.substring(1), builder);
 276  
             }
 277  
         } else {
 278  1
             return null;
 279  
         }
 280  
     }
 281  
 
 282  
     /**
 283  
      * Returns the Strings stored below the given prefix.
 284  
      * 
 285  
      * @param prefix
 286  
      *            the prefix
 287  
      * @return the list
 288  
      */
 289  
     public List<String> getCompletitions(final String prefix) {
 290  20
         final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, prefix);
 291  20
         final List<String> completions = new ArrayList<String>();
 292  20
         findCompletionsRecursive(matchedNode, prefix, completions);
 293  20
         return completions;
 294  
     }
 295  
 
 296  
     /**
 297  
      * Gets the path for the given value.
 298  
      * 
 299  
      * @param objectToFind
 300  
      *            the object to find
 301  
      * @return the path for object
 302  
      */
 303  
     public String getPathForValue(final Object objectToFind) {
 304  31
         final String path = findPathForObject(rootNode, "", objectToFind);
 305  31
         return path;
 306  
     }
 307  
 
 308  
     /**
 309  
      * Gets a Map of Objects with it's keys that are below the given prefix.
 310  
      * 
 311  
      * @param prefix
 312  
      *            the prefix
 313  
      * @return the object entries
 314  
      */
 315  
     public TrieMap<Value> getSubMap(final String prefix) {
 316  1
         final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, prefix);
 317  1
         final TrieMap<Value> completitions = new TrieMap<Value>();
 318  1
         findObjectMapRecursive(matchedNode, prefix, completitions);
 319  1
         return completitions;
 320  
     }
 321  
 
 322  
     /**
 323  
      * Returns the stored object below the given prefix. Or an empty list if no objects have been stored.
 324  
      * 
 325  
      * @param prefix
 326  
      *            the prefix
 327  
      * @return the list
 328  
      */
 329  
     public List<Value> getSubValues(final String prefix) {
 330  24
         final TrieNode<Value> matchedNode = (prefix == null) ? rootNode : matchPrefixRecursive(rootNode, prefix);
 331  24
         final List<Value> completions = new LinkedList<Value>();
 332  24
         findObjectsRecursive(matchedNode, prefix, completions);
 333  24
         return completions;
 334  
     }
 335  
 
 336  
     /**
 337  
      * Gets the last found object of the best matching path for the given prefix<br/>
 338  
      * Will return null if the given prefix is empty.
 339  
      * 
 340  
      * @param prefix
 341  
      *            the prefix
 342  
      * @return the last matching objects
 343  
      */
 344  
     public Value getValueForBestMatchingKey(final String prefix) {
 345  11
         if (isEmpty(prefix)) {
 346  1
             return null;
 347  
         }
 348  10
         final Value result = getLastMatchingObject(rootNode, prefix, null);
 349  10
         return result;
 350  
     }
 351  
 
 352  
     /**
 353  
      * Gets the objects that lie on the given path. The path has to be complete.<br/>
 354  
      * It means it has to be a value which has been added by the {@link #add(String, Object)} method.
 355  
      * 
 356  
      * @param <T>
 357  
      *            the generic type
 358  
      * @param prefix
 359  
      *            the prefix
 360  
      * @return the objects on path
 361  
      */
 362  
     public <T extends Value> List<Value> getValuesOnPath(final String prefix) {
 363  3
         if (isEmpty(prefix)) {
 364  1
             return Collections.emptyList();
 365  
         }
 366  2
         final List<TrieNode<Value>> matchedNodes = matchNodesOnPathRecursive(rootNode, prefix);
 367  2
         final List<Value> result = new ArrayList<Value>(matchedNodes.size());
 368  2
         for (final TrieNode<Value> node : matchedNodes) {
 369  6
             if (node.containsObject()) {
 370  6
                 final Value object = node.getObject();
 371  6
                 if (object != null) {
 372  6
                     result.add(object);
 373  
                 }
 374  6
             }
 375  
         }
 376  2
         return result;
 377  
     }
 378  
 
 379  
     /* (non-Javadoc)
 380  
      * @see java.lang.Object#hashCode()
 381  
      */
 382  
     @Override
 383  
     public int hashCode() {
 384  2
         final int prime = 31;
 385  2
         int result = 1;
 386  2
         result = prime * result + ((rootNode == null) ? 0 : rootNode.hashCode());
 387  2
         return result;
 388  
     }
 389  
 
 390  
     /* (non-Javadoc)
 391  
      * @see java.util.Map#isEmpty()
 392  
      */
 393  
     @Override
 394  
     public boolean isEmpty() {
 395  3
         return rootNode.getChildren().isEmpty();
 396  
     }
 397  
 
 398  
     /* (non-Javadoc)
 399  
      * @see java.util.Map#keySet()
 400  
      */
 401  
     @Override
 402  
     public Set<String> keySet() {
 403  15
         final List<String> keys = getCompletitions("");
 404  15
         keys.remove("" + rootNode.getNodeValue());
 405  15
         return new TreeSet<String>(keys);
 406  
     }
 407  
 
 408  
     /* (non-Javadoc)
 409  
      * @see java.util.Map#put(java.lang.Object, java.lang.Object)
 410  
      */
 411  
     @Override
 412  
     public Value put(final String key, final Value value) {
 413  20
         final Value preResult = get(key);
 414  20
         forceAdd(key, value);
 415  20
         return preResult;
 416  
     }
 417  
 
 418  
     /* (non-Javadoc)
 419  
      * @see java.util.Map#putAll(java.util.Map)
 420  
      */
 421  
     @Override
 422  
     public void putAll(final Map<? extends String, ? extends Value> m) {
 423  1
         if (m != null) {
 424  1
             for (final Map.Entry<? extends String, ? extends Value> entry : m.entrySet()) {
 425  2
                 forceAdd(entry.getKey(), entry.getValue());
 426  
             }
 427  
         }
 428  1
     }
 429  
 
 430  
     /* (non-Javadoc)
 431  
      * @see java.util.Map#remove(java.lang.Object)
 432  
      */
 433  
     @Override
 434  
     public Value remove(final Object key) {
 435  4
         if (key instanceof String) {
 436  3
             final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, (String) key);
 437  3
             if (matchedNode != null) {
 438  2
                 final Value object = matchedNode.removeObject();
 439  2
                 matchedNode.setBoundary(false);
 440  2
                 return object;
 441  
             }
 442  
         }
 443  2
         return null;
 444  
     }
 445  
 
 446  
     /* (non-Javadoc)
 447  
      * @see java.util.Map#size()
 448  
      */
 449  
     @Override
 450  
     public int size() {
 451  11
         return keySet().size();
 452  
     }
 453  
 
 454  
     /* (non-Javadoc)
 455  
      * @see java.lang.Object#toString()
 456  
      */
 457  
     @Override
 458  
     public String toString() {
 459  2
         return rootNode.toString();
 460  
     }
 461  
 
 462  
     /* (non-Javadoc)
 463  
      * @see java.util.Map#values()
 464  
      */
 465  
     @Override
 466  
     public Collection<Value> values() {
 467  4
         return getSubValues("");
 468  
     }
 469  
 
 470  
     private boolean addRecursive(final TrieNode<Value> node, final String phrase, final Value object, final boolean force) {
 471  2904
         if (isEmpty(phrase)) {
 472  1
             return true;
 473  
         }
 474  2903
         final char firstChar = phrase.charAt(0);
 475  
 
 476  2903
         final String subString = phrase.substring(1);
 477  2903
         if (isEmpty(subString)) {
 478  559
             if (node.add(firstChar, object, force, true)) {
 479  552
                 return true;
 480  
             }
 481  7
             return false;
 482  
         } else {
 483  2344
             node.add(firstChar, null, force, false);
 484  
         }
 485  
 
 486  2344
         final TrieNode<Value> childNode = node.getChildNode(firstChar);
 487  2344
         if (childNode != null) {
 488  2344
             return addRecursive(childNode, subString, object, force);
 489  
         }
 490  0
         return false;
 491  
     }
 492  
 
 493  
     private void findCompletionsRecursive(final TrieNode<Value> node, final String prefix, final List<String> completions) {
 494  275
         if (node == null) {
 495  1
             return;
 496  
         }
 497  274
         if (node.isBoundary()) {
 498  125
             completions.add(prefix);
 499  
         }
 500  274
         final Collection<TrieNode<Value>> childNodes = node.getChildren();
 501  274
         for (final TrieNode<Value> childNode : childNodes) {
 502  255
             final char childChar = childNode.getNodeValue();
 503  255
             findCompletionsRecursive(childNode, prefix + childChar, completions);
 504  255
         }
 505  274
     }
 506  
 
 507  
     private String findLastMatchingRecursivly(final TrieNode<Value> node, final String phrase, final StringBuilder completion) {
 508  13
         final char firstChar = phrase.charAt(0);
 509  13
         final String subString = phrase.substring(1);
 510  13
         if (isEmpty(subString)) {
 511  2
             completion.append(firstChar);
 512  2
             return completion.toString();
 513  
         }
 514  
 
 515  11
         final TrieNode<Value> childNode = node.getChildNode(firstChar);
 516  11
         if (childNode != null) {
 517  10
             completion.append(firstChar);
 518  10
             return findLastMatchingRecursivly(childNode, subString, completion);
 519  
         } else {
 520  1
             return completion.toString();
 521  
         }
 522  
     }
 523  
 
 524  
     private void findObjectMapRecursive(final TrieNode<Value> node, final String prefix, final TrieMap<Value> completions) {
 525  5
         if (node == null) {
 526  
             // our prefix did not match anything we return
 527  0
             return;
 528  
         }
 529  5
         if (node.containsObject()) {
 530  3
             final Value object = node.getObject();
 531  3
             if (object != null) {
 532  3
                 completions.put(prefix, object);
 533  
             }
 534  
         }
 535  5
         final Collection<TrieNode<Value>> childNodes = node.getChildren();
 536  5
         for (final TrieNode<Value> childNode : childNodes) {
 537  4
             final char childChar = childNode.getNodeValue();
 538  4
             findObjectMapRecursive(childNode, prefix + childChar, completions);
 539  4
         }
 540  5
     }
 541  
 
 542  
     private void findObjectsRecursive(final TrieNode<Value> node, final String prefix, final List<Value> completions) {
 543  207
         if (node == null) {
 544  
             // our prefix did not match anything we return
 545  2
             return;
 546  
         }
 547  205
         if (node.containsObject()) {
 548  100
             final Value object = node.getObject();
 549  100
             if (object != null) {
 550  100
                 completions.add(object);
 551  
             }
 552  
         }
 553  205
         final Collection<TrieNode<Value>> childNodes = node.getChildren();
 554  205
         for (final TrieNode<Value> childNode : childNodes) {
 555  183
             final char childChar = childNode.getNodeValue();
 556  183
             findObjectsRecursive(childNode, prefix + childChar, completions);
 557  183
         }
 558  205
     }
 559  
 
 560  
     private String findPathForObject(final TrieNode<Value> node, final String prefix, final Object toFind) {
 561  565
         if (node == null) {
 562  
             // our prefix did not match anything we return
 563  0
             return null;
 564  
         }
 565  565
         if (node.containsObject()) {
 566  229
             final Value object = node.getObject();
 567  229
             if (object != null && object.equals(toFind)) {
 568  26
                 return prefix;
 569  
             }
 570  
         }
 571  539
         final Collection<TrieNode<Value>> childNodes = node.getChildren();
 572  539
         for (final TrieNode<Value> childNode : childNodes) {
 573  534
             final char childChar = childNode.getNodeValue();
 574  534
             final String path = findPathForObject(childNode, prefix + childChar, toFind);
 575  534
             if (path != null) {
 576  145
                 return path;
 577  
             }
 578  389
         }
 579  394
         return null;
 580  
     }
 581  
 
 582  
     @SuppressWarnings("unchecked")
 583  
     private Value getLastMatchingObject(final TrieNode node, final String prefix, final Value lastObject) {
 584  115
         if (isEmpty(prefix)) {
 585  5
             return lastObject;
 586  
         }
 587  110
         final char firstChar = prefix.charAt(0);
 588  110
         final TrieNode childNode = node.getChildNode(firstChar);
 589  110
         if (childNode == null) {
 590  
             // no match at this char, exit
 591  5
             return lastObject;
 592  
         } else {
 593  
             // go deeper
 594  105
             return getLastMatchingObject(childNode, prefix.substring(1), ((Value) ((childNode.containsObject()) ? childNode.getObject() : lastObject)));
 595  
         }
 596  
     }
 597  
 
 598  
     private boolean isEmpty(final String phrase) {
 599  6701
         return StringUtils.isEmpty(phrase);
 600  
     }
 601  
 
 602  
     private List<TrieNode<Value>> matchNodesOnPathRecursive(final TrieNode<Value> node, final String prefix) {
 603  2
         return matchNodesOnPathRecursive(node, prefix, new LinkedList<TrieNode<Value>>());
 604  
     }
 605  
 
 606  
     private List<TrieNode<Value>> matchNodesOnPathRecursive(final TrieNode<Value> node, final String prefix, final List<TrieNode<Value>> result) {
 607  13
         if (isEmpty(prefix)) {
 608  1
             result.add(node);
 609  1
             return result;
 610  
         }
 611  12
         final char firstChar = prefix.charAt(0);
 612  12
         final TrieNode<Value> childNode = node.getChildNode(firstChar);
 613  12
         if (childNode == null) {
 614  
             // no match at this char, exit
 615  1
             if (node.isBoundary()) {
 616  1
                 result.add(node);
 617  
             }
 618  1
             return result;
 619  
         } else {
 620  
             // go deeper
 621  11
             if (node.isBoundary()) {
 622  4
                 result.add(node);
 623  
             }
 624  11
             return matchNodesOnPathRecursive(childNode, prefix.substring(1), result);
 625  
         }
 626  
     }
 627  
 
 628  
     private TrieNode<Value> matchPrefixRecursive(final TrieNode<Value> node, final String prefix) {
 629  733
         if (isEmpty(prefix)) {
 630  126
             return node;
 631  
         }
 632  607
         final char firstChar = prefix.charAt(0);
 633  607
         final TrieNode<Value> childNode = node.getChildNode(firstChar);
 634  607
         if (childNode == null) {
 635  
             // no match at this char, exit
 636  30
             return null;
 637  
         } else {
 638  
             // go deeper
 639  577
             return matchPrefixRecursive(childNode, prefix.substring(1));
 640  
         }
 641  
     }
 642  
 
 643  
     @SuppressWarnings("unchecked")
 644  
     private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
 645  1
         lock = new ReentrantReadWriteLock();
 646  
         //rootNode = (TrieNode<Value>) in.readObject();
 647  1
         rootNode = new TrieNode<Value>(' ', null, false);
 648  1
         final int size = in.readInt();
 649  
         String key;
 650  
         Value value;
 651  12
         for (int i = 0; i < size; i++) {
 652  11
             key = (String) in.readObject();
 653  11
             value = (Value) in.readObject();
 654  11
             add(key, value);
 655  
         }
 656  1
     }
 657  
 
 658  
     /* (non-Javadoc)
 659  
      * @see java.io.Externalizable#writeExternal(java.io.ObjectOutput)
 660  
      */
 661  
     private void writeObject(final ObjectOutputStream out) throws IOException {
 662  
         try {
 663  1
             lock.readLock().lock();
 664  1
             final Set<Map.Entry<String, Value>> entrySet = entrySet();
 665  1
             out.writeInt(entrySet.size());
 666  1
             for (final Map.Entry<String, Value> entry : entrySet) {
 667  11
                 out.writeObject(entry.getKey());
 668  11
                 out.writeObject(entry.getValue());
 669  
             }
 670  
         } finally {
 671  1
             lock.readLock().unlock();
 672  1
         }
 673  1
     }
 674  
 
 675  
     /**
 676  
      * Gets the key set.
 677  
      * 
 678  
      * @return the key set
 679  
      */
 680  
     @SuppressWarnings("unchecked")
 681  
     protected Set<Object> getkeySet() {
 682  2
         final List keys = getCompletitions("");
 683  2
         keys.remove("" + rootNode.getNodeValue());
 684  2
         return new TreeSet<Object>(keys);
 685  
     }
 686  
 
 687  
     /**
 688  
      * Gets the object values.
 689  
      * 
 690  
      * @param prefix
 691  
      *            the prefix
 692  
      * @return the object values
 693  
      */
 694  
     @SuppressWarnings("unchecked")
 695  
     protected List<Object> getObjectValues(final String prefix) {
 696  2
         final List<Object> completions = new ArrayList(getSubValues(prefix));
 697  2
         return completions;
 698  
     }
 699  
 
 700  
     /**
 701  
      * Internal entry set.
 702  
      * 
 703  
      * @return the sets the
 704  
      */
 705  
     @SuppressWarnings("unchecked")
 706  
     protected Set internalEntrySet() {
 707  2
         final Set result = new HashSet();
 708  2
         for (final String key : keySet()) {
 709  12
             result.add(new Entry(key));
 710  
         }
 711  2
         return result;
 712  
     }
 713  
 
 714  
     /**
 715  
      * java.util.Properties extension backed by this given TrieMap.
 716  
      * 
 717  
      * @author Marco Brade
 718  
      * 
 719  
      */
 720  19
     public final class TrieMapBackedProperties extends Properties implements Cloneable {
 721  
 
 722  
         /** The Constant serialVersionUID. */
 723  
         private static final long serialVersionUID = 1L;
 724  
 
 725  
         /** The none string key map. */
 726  18
         private final Map<Object, Object> noneStringKeyMap = new HashMap<Object, Object>();
 727  
 
 728  
         /** The lock. */
 729  18
         private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
 730  
 
 731  9
         private TrieMapBackedProperties() {
 732  9
         }
 733  
 
 734  9
         private TrieMapBackedProperties(final Properties defaults) {
 735  9
             super(defaults);
 736  9
         }
 737  
 
 738  
         /* (non-Javadoc)
 739  
          * @see java.util.Hashtable#clear()
 740  
          */
 741  
         @Override
 742  
         public void clear() {
 743  
             try {
 744  2
                 lock.writeLock().lock();
 745  2
                 TrieMap.this.clear();
 746  2
                 noneStringKeyMap.clear();
 747  
             } finally {
 748  2
                 lock.writeLock().unlock();
 749  2
             }
 750  2
         }
 751  
 
 752  
         /* (non-Javadoc)
 753  
          * @see java.util.Hashtable#clone()
 754  
          */
 755  
         @Override
 756  
         public TrieMapBackedProperties clone() {
 757  
             try {
 758  1
                 lock.readLock().lock();
 759  1
                 final TrieMap<Value> clonedMap = TrieMap.this.clone();
 760  1
                 final TrieMapBackedProperties clone = (TrieMapBackedProperties) clonedMap.asProperties(defaults);
 761  1
                 clone.noneStringKeyMap.putAll(noneStringKeyMap);
 762  1
                 return clone;
 763  
             } finally {
 764  1
                 lock.readLock().unlock();
 765  
             }
 766  
 
 767  
         }
 768  
 
 769  
         /* (non-Javadoc)
 770  
          * @see java.util.Hashtable#contains(java.lang.Object)
 771  
          */
 772  
         @Override
 773  
         public boolean contains(final Object value) {
 774  17
             return containsValue(value);
 775  
         }
 776  
 
 777  
         /* (non-Javadoc)
 778  
          * @see java.util.Hashtable#containsKey(java.lang.Object)
 779  
          */
 780  
         @Override
 781  
         public boolean containsKey(final Object key) {
 782  
             try {
 783  3
                 lock.readLock().lock();
 784  3
                 return TrieMap.this.containsKey(key) || noneStringKeyMap.containsKey(key);
 785  
             } finally {
 786  3
                 lock.readLock().unlock();
 787  
             }
 788  
         }
 789  
 
 790  
         /* (non-Javadoc)
 791  
          * @see java.util.Hashtable#containsValue(java.lang.Object)
 792  
          */
 793  
         @Override
 794  
         public boolean containsValue(final Object value) {
 795  20
             if (value == null) {
 796  1
                 throw new NullPointerException();
 797  
             }
 798  
             try {
 799  19
                 lock.readLock().lock();
 800  19
                 return TrieMap.this.containsValue(value) || noneStringKeyMap.containsValue(value);
 801  
             } finally {
 802  19
                 lock.readLock().unlock();
 803  
             }
 804  
         }
 805  
 
 806  
         /* (non-Javadoc)
 807  
          * @see java.util.Hashtable#elements()
 808  
          */
 809  
         @Override
 810  
         public Enumeration<Object> elements() {
 811  1
             final Iterator<Object> iterator = values().iterator();
 812  1
             return new Enumeration<Object>() {
 813  
 
 814  
                 @Override
 815  
                 public boolean hasMoreElements() {
 816  14
                     return iterator.hasNext();
 817  
                 }
 818  
 
 819  
                 @Override
 820  
                 public Object nextElement() {
 821  13
                     return iterator.next();
 822  
                 }
 823  
             };
 824  
         }
 825  
 
 826  
         /* (non-Javadoc)
 827  
          * @see java.util.Hashtable#entrySet()
 828  
          */
 829  
         @SuppressWarnings("unchecked")
 830  
         @Override
 831  
         public Set<Map.Entry<Object, Object>> entrySet() {
 832  
             try {
 833  2
                 lock.readLock().lock();
 834  2
                 final Set entrySet = TrieMap.this.internalEntrySet();
 835  2
                 entrySet.addAll(noneStringKeyMap.entrySet());
 836  2
                 return entrySet;
 837  
             } finally {
 838  2
                 lock.readLock().unlock();
 839  
             }
 840  
         }
 841  
 
 842  
         /* (non-Javadoc)
 843  
          * @see java.util.Hashtable#equals(java.lang.Object)
 844  
          */
 845  
         @Override
 846  
         public boolean equals(final Object obj) {
 847  
             try {
 848  1
                 lock.readLock().lock();
 849  1
                 if (this == obj) {
 850  0
                     return true;
 851  
                 }
 852  1
                 if (!super.equals(obj)) {
 853  0
                     return false;
 854  
                 }
 855  1
                 if (getClass() != obj.getClass()) {
 856  0
                     return false;
 857  
                 }
 858  1
                 final TrieMapBackedProperties other = (TrieMapBackedProperties) obj;
 859  1
                 if (!getOuterType().equals(other.getOuterType())) {
 860  0
                     return false;
 861  
                 }
 862  1
                 if (noneStringKeyMap == null) {
 863  0
                     if (other.noneStringKeyMap != null) {
 864  0
                         return false;
 865  
                     }
 866  1
                 } else if (!noneStringKeyMap.equals(other.noneStringKeyMap)) {
 867  0
                     return false;
 868  
                 }
 869  1
                 return true;
 870  
             } finally {
 871  1
                 lock.readLock().unlock();
 872  
             }
 873  
         }
 874  
 
 875  
         /* (non-Javadoc)
 876  
          * @see java.util.Hashtable#get(java.lang.Object)
 877  
          */
 878  
         @Override
 879  
         public Object get(final Object key) {
 880  
             try {
 881  18
                 lock.readLock().lock();
 882  18
                 Object result = TrieMap.this.get(key);
 883  18
                 if (result == null) {
 884  3
                     result = noneStringKeyMap.get(key);
 885  
                 }
 886  18
                 return result;
 887  
             } finally {
 888  18
                 lock.readLock().unlock();
 889  
             }
 890  
         }
 891  
 
 892  
         /* (non-Javadoc)
 893  
          * @see java.util.Properties#getProperty(java.lang.String)
 894  
          */
 895  
         @Override
 896  
         public String getProperty(final String key) {
 897  5
             final Object oval = get(key);
 898  5
             final String sval = (oval instanceof String) ? (String) oval : null;
 899  5
             return ((sval == null) && (defaults != null)) ? defaults.getProperty(key) : sval;
 900  
         }
 901  
 
 902  
         /* (non-Javadoc)
 903  
          * @see java.util.Hashtable#hashCode()
 904  
          */
 905  
         @Override
 906  
         public int hashCode() {
 907  2
             final int prime = 31;
 908  2
             int result = 0;
 909  2
             result = prime * result + getOuterType().hashCode();
 910  2
             result = prime * result + ((noneStringKeyMap == null) ? 0 : noneStringKeyMap.hashCode());
 911  2
             return result;
 912  
         }
 913  
 
 914  
         /* (non-Javadoc)
 915  
          * @see java.util.Hashtable#isEmpty()
 916  
          */
 917  
         @Override
 918  
         public boolean isEmpty() {
 919  
             try {
 920  1
                 lock.readLock().lock();
 921  1
                 return TrieMap.this.isEmpty() && noneStringKeyMap.isEmpty();
 922  
             } finally {
 923  1
                 lock.readLock().unlock();
 924  
             }
 925  
         }
 926  
 
 927  
         /* (non-Javadoc)
 928  
          * @see java.util.Hashtable#keys()
 929  
          */
 930  
         @Override
 931  
         public Enumeration<Object> keys() {
 932  1
             final Iterator<Object> it = keySet().iterator();
 933  1
             return new Enumeration<Object>() {
 934  
 
 935  
                 @Override
 936  
                 public boolean hasMoreElements() {
 937  0
                     return it.hasNext();
 938  
                 }
 939  
 
 940  
                 @Override
 941  
                 public Object nextElement() {
 942  0
                     return it.next();
 943  
                 }
 944  
             };
 945  
         }
 946  
 
 947  
         /* (non-Javadoc)
 948  
          * @see java.util.Hashtable#keySet()
 949  
          */
 950  
         @Override
 951  
         public Set<Object> keySet() {
 952  
             try {
 953  2
                 lock.readLock().lock();
 954  2
                 final Set<Object> keys = new HashSet<Object>(TrieMap.this.getkeySet());
 955  2
                 keys.addAll(noneStringKeyMap.keySet());
 956  2
                 if (defaults != null) {
 957  2
                     keys.addAll(defaults.keySet());
 958  
                 }
 959  2
                 return keys;
 960  
             } finally {
 961  2
                 lock.readLock().unlock();
 962  
             }
 963  
         }
 964  
 
 965  
         /* (non-Javadoc)
 966  
          * @see java.util.Hashtable#put(java.lang.Object, java.lang.Object)
 967  
          */
 968  
         @SuppressWarnings("unchecked")
 969  
         @Override
 970  
         public Object put(final Object key, final Object value) {
 971  
             try {
 972  25
                 lock.writeLock().lock();
 973  25
                 if (key instanceof String) {
 974  14
                     return TrieMap.this.put((String) key, (Value) value);
 975  
                 } else {
 976  11
                     return noneStringKeyMap.put(key, value);
 977  
                 }
 978  
             } finally {
 979  25
                 lock.writeLock().unlock();
 980  
             }
 981  
         }
 982  
 
 983  
         /* (non-Javadoc)
 984  
          * @see java.util.Hashtable#putAll(java.util.Map)
 985  
          */
 986  
         @SuppressWarnings("unchecked")
 987  
         @Override
 988  
         public void putAll(final Map<? extends Object, ? extends Object> t) {
 989  
             try {
 990  1
                 lock.writeLock().lock();
 991  1
                 for (final Map.Entry entry : t.entrySet()) {
 992  2
                     put(entry.getKey(), entry.getValue());
 993  
                 }
 994  
             } finally {
 995  1
                 lock.writeLock().unlock();
 996  1
             }
 997  1
         }
 998  
 
 999  
         /* (non-Javadoc)
 1000  
          * @see java.util.Hashtable#remove(java.lang.Object)
 1001  
          */
 1002  
         @Override
 1003  
         public Object remove(final Object key) {
 1004  
             try {
 1005  2
                 lock.writeLock().lock();
 1006  2
                 Object result = TrieMap.this.remove(key);
 1007  2
                 if (result == null) {
 1008  1
                     result = noneStringKeyMap.remove(key);
 1009  
                 }
 1010  2
                 return result;
 1011  
             } finally {
 1012  2
                 lock.writeLock().unlock();
 1013  
             }
 1014  
         }
 1015  
 
 1016  
         /* (non-Javadoc)
 1017  
          * @see java.util.Properties#setProperty(java.lang.String, java.lang.String)
 1018  
          */
 1019  
         @Override
 1020  
         public Object setProperty(final String key, final String value) {
 1021  12
             return put(key, value);
 1022  
         }
 1023  
 
 1024  
         /* (non-Javadoc)
 1025  
          * @see java.util.Hashtable#size()
 1026  
          */
 1027  
         @Override
 1028  
         public int size() {
 1029  6
             return TrieMap.this.size() + noneStringKeyMap.size();
 1030  
         }
 1031  
 
 1032  
         /* (non-Javadoc)
 1033  
          * @see java.util.Hashtable#toString()
 1034  
          */
 1035  
         @Override
 1036  
         public String toString() {
 1037  1
             return new StringBuilder(TrieMap.this.toString()).append(",").append(noneStringKeyMap.toString()).toString();
 1038  
         }
 1039  
 
 1040  
         /* (non-Javadoc)
 1041  
          * @see java.util.Hashtable#values()
 1042  
          */
 1043  
         @Override
 1044  
         public Collection<Object> values() {
 1045  
             try {
 1046  2
                 lock.readLock().lock();
 1047  2
                 final List<Object> result = TrieMap.this.getObjectValues("");
 1048  2
                 result.addAll(noneStringKeyMap.values());
 1049  2
                 if (defaults != null) {
 1050  1
                     result.addAll(defaults.values());
 1051  
                 }
 1052  2
                 return result;
 1053  
             } finally {
 1054  2
                 lock.readLock().unlock();
 1055  
             }
 1056  
         }
 1057  
 
 1058  
         /**
 1059  
          * Gets the outer type.
 1060  
          * 
 1061  
          * @return the outer type
 1062  
          */
 1063  
         @SuppressWarnings("unchecked")
 1064  
         private TrieMap getOuterType() {
 1065  4
             return TrieMap.this;
 1066  
         }
 1067  
     }
 1068  
 
 1069  
     /**
 1070  
      * The Class Entry.
 1071  
      */
 1072  132
     private final class Entry implements Map.Entry<String, Value>, Comparable<Entry> {
 1073  
 
 1074  
         /** The key. */
 1075  
         private final String key;
 1076  
 
 1077  
         /**
 1078  
          * Instantiates a new entry.
 1079  
          * 
 1080  
          * @param keyParam
 1081  
          *            the key param
 1082  
          */
 1083  34
         private Entry(final String keyParam) {
 1084  34
             this.key = keyParam;
 1085  34
         }
 1086  
 
 1087  
         /* (non-Javadoc)
 1088  
          * @see java.lang.Comparable#compareTo(java.lang.Object)
 1089  
          */
 1090  
         @Override
 1091  
         public int compareTo(final Entry o) {
 1092  64
             return key.compareTo(o.getKey());
 1093  
         }
 1094  
 
 1095  
         /* (non-Javadoc)
 1096  
          * @see java.util.Map.Entry#getKey()
 1097  
          */
 1098  
         @Override
 1099  
         public String getKey() {
 1100  98
             return key;
 1101  
         }
 1102  
 
 1103  
         /* (non-Javadoc)
 1104  
          * @see java.util.Map.Entry#getValue()
 1105  
          */
 1106  
         @Override
 1107  
         public Value getValue() {
 1108  34
             return get(key);
 1109  
         }
 1110  
 
 1111  
         /* (non-Javadoc)
 1112  
          * @see java.util.Map.Entry#setValue(java.lang.Object)
 1113  
          */
 1114  
         @Override
 1115  
         public Value setValue(final Value value) {
 1116  11
             final Value result = get(key);
 1117  11
             if (value == null) {
 1118  0
                 remove(key);
 1119  
             } else {
 1120  11
                 forceAdd(key, value);
 1121  
             }
 1122  11
             return result;
 1123  
         }
 1124  
     }
 1125  
 
 1126  60
     private final class TrieNode<ValueNode> implements Cloneable {
 1127  
 
 1128  
         /** The Constant serialVersionUID. */
 1129  
         private static final long serialVersionUID = 1L;
 1130  
 
 1131  
         /** The object. */
 1132  
         private ValueNode object;
 1133  
 
 1134  
         /** The character. */
 1135  
         private final Character character;
 1136  
 
 1137  
         /** The children. */
 1138  
         private Map<Character, TrieNode<ValueNode>> children;
 1139  
 
 1140  
         /** The boundary. */
 1141  1239
         private boolean boundary = false;
 1142  
 
 1143  1239
         private TrieNode(final char c, final ValueNode value, final boolean boundaryParam) {
 1144  1239
             this.character = Character.valueOf(c);
 1145  1239
             this.boundary = boundaryParam;
 1146  1239
             children = new TreeMap<Character, TrieNode<ValueNode>>();
 1147  1239
             if (value != null) {
 1148  493
                 setValue(value);
 1149  
             }
 1150  1239
         }
 1151  
 
 1152  
         public boolean add(final char c, final ValueNode object, final boolean force, final boolean isBoundary) {
 1153  
             try {
 1154  2903
                 lock.writeLock().lock();
 1155  2903
                 final TrieNode<ValueNode> node = children.get(Character.valueOf(c));
 1156  2903
                 if (node == null) {
 1157  
                     // children does not contain c, add a TrieNode
 1158  1179
                     children.put(Character.valueOf(c), new TrieNode<ValueNode>(c, object, isBoundary));
 1159  1179
                     return true;
 1160  1724
                 } else if (object != null && (force || !node.isBoundary())) {
 1161  58
                     node.setValue(object);
 1162  58
                     node.setBoundary(isBoundary);
 1163  58
                     return true;
 1164  
                 }
 1165  
             } finally {
 1166  1237
                 lock.writeLock().unlock();
 1167  1666
             }
 1168  1666
             return false;
 1169  
         }
 1170  
 
 1171  
         @SuppressWarnings("unchecked")
 1172  
         @Override
 1173  
         public TrieNode<ValueNode> clone() {
 1174  
             try {
 1175  23
                 lock.readLock().lock();
 1176  23
                 TrieNode<ValueNode> node = null;
 1177  
                 try {
 1178  23
                     node = (TrieNode<ValueNode>) super.clone();
 1179  23
                     final Map<Character, TrieNode<ValueNode>> childs = new TreeMap<Character, TrieNode<ValueNode>>();
 1180  23
                     for (final TrieNode<ValueNode> nodeTrieNode : children.values()) {
 1181  22
                         childs.put(nodeTrieNode.character, nodeTrieNode.clone());
 1182  
                     }
 1183  23
                     node.children = childs;
 1184  0
                 } catch (final CloneNotSupportedException cnse) {
 1185  23
                 }
 1186  23
                 return node;
 1187  
             } finally {
 1188  23
                 lock.readLock().unlock();
 1189  
             }
 1190  
         }
 1191  
 
 1192  
         /**
 1193  
          * Contains objects.
 1194  
          * 
 1195  
          * @return true, if successful
 1196  
          */
 1197  
         public boolean containsObject() {
 1198  
             try {
 1199  886
                 lock.readLock().lock();
 1200  886
                 return isBoundary() && object != null;
 1201  
             } finally {
 1202  886
                 lock.readLock().unlock();
 1203  
             }
 1204  
         }
 1205  
 
 1206  
         /* (non-Javadoc)
 1207  
          * @see java.lang.Object#equals(java.lang.Object)
 1208  
          */
 1209  
         @SuppressWarnings("unchecked")
 1210  
         @Override
 1211  
         public boolean equals(final Object obj) {
 1212  46
             if (this == obj) {
 1213  0
                 return true;
 1214  
             }
 1215  46
             if (obj == null) {
 1216  0
                 return false;
 1217  
             }
 1218  46
             if (getClass() != obj.getClass()) {
 1219  0
                 return false;
 1220  
             }
 1221  46
             final TrieNode<ValueNode> other = (TrieNode<ValueNode>) obj;
 1222  46
             if (boundary != other.boundary) {
 1223  0
                 return false;
 1224  
             }
 1225  46
             if (character == null) {
 1226  0
                 if (other.character != null) {
 1227  0
                     return false;
 1228  
                 }
 1229  46
             } else if (!character.equals(other.character)) {
 1230  0
                 return false;
 1231  
             }
 1232  46
             if (children == null) {
 1233  0
                 if (other.children != null) {
 1234  0
                     return false;
 1235  
                 }
 1236  46
             } else if (!children.equals(other.children)) {
 1237  0
                 return false;
 1238  
             }
 1239  46
             if (object == null) {
 1240  24
                 if (other.object != null) {
 1241  0
                     return false;
 1242  
                 }
 1243  22
             } else if (!object.equals(other.object)) {
 1244  0
                 return false;
 1245  
             }
 1246  46
             return true;
 1247  
         }
 1248  
 
 1249  
         /**
 1250  
          * Gets the child node.
 1251  
          * 
 1252  
          * @param c
 1253  
          *            the c
 1254  
          * 
 1255  
          * @return the child node
 1256  
          */
 1257  
         public TrieNode<ValueNode> getChildNode(final char c) {
 1258  3089
             return children.get(Character.valueOf(c));
 1259  
         }
 1260  
 
 1261  
         /**
 1262  
          * Gets the children.
 1263  
          * 
 1264  
          * @return the children
 1265  
          */
 1266  
         public Collection<TrieNode<ValueNode>> getChildren() {
 1267  
             try {
 1268  1026
                 lock.readLock().lock();
 1269  1026
                 return (children == null) ? Collections.<TrieNode<ValueNode>> emptyList() : children.values();
 1270  
             } finally {
 1271  1026
                 lock.readLock().unlock();
 1272  
             }
 1273  
         }
 1274  
 
 1275  
         /**
 1276  
          * Gets the node value.
 1277  
          * 
 1278  
          * @return the node value
 1279  
          */
 1280  
         public char getNodeValue() {
 1281  993
             return character.charValue();
 1282  
         }
 1283  
 
 1284  
         /**
 1285  
          * Gets the object.
 1286  
          * 
 1287  
          * @return the object
 1288  
          */
 1289  
         public ValueNode getObject() {
 1290  
             try {
 1291  424
                 lock.readLock().lock();
 1292  424
                 return object;
 1293  
             } finally {
 1294  424
                 lock.readLock().unlock();
 1295  
             }
 1296  
         }
 1297  
 
 1298  
         /* (non-Javadoc)
 1299  
          * @see java.lang.Object#hashCode()
 1300  
          */
 1301  
         @Override
 1302  
         public int hashCode() {
 1303  46
             final int prime = 31;
 1304  46
             int result = 1;
 1305  46
             result = prime * result + (boundary ? 1231 : 1237);
 1306  46
             result = prime * result + ((character == null) ? 0 : character.hashCode());
 1307  46
             result = prime * result + ((children == null) ? 0 : children.hashCode());
 1308  46
             result = prime * result + ((object == null) ? 0 : object.hashCode());
 1309  46
             return result;
 1310  
         }
 1311  
 
 1312  
         /**
 1313  
          * Checks if is boundary.
 1314  
          * 
 1315  
          * @return true, if is boundary
 1316  
          */
 1317  
         public boolean isBoundary() {
 1318  1263
             return boundary;
 1319  
         }
 1320  
 
 1321  
         /**
 1322  
          * Removes the objects.
 1323  
          * 
 1324  
          * @return the list
 1325  
          */
 1326  
         public ValueNode removeObject() {
 1327  
             try {
 1328  2
                 lock.writeLock().lock();
 1329  
                 // children does not contain c, add a TrieNode
 1330  2
                 final ValueNode result = getObject();
 1331  2
                 object = null;
 1332  2
                 return result;
 1333  
             } finally {
 1334  2
                 lock.writeLock().unlock();
 1335  
             }
 1336  
         }
 1337  
 
 1338  
         /**
 1339  
          * Sets the boundary.
 1340  
          * 
 1341  
          * @param boundary
 1342  
          *            the new boundary
 1343  
          */
 1344  
         public void setBoundary(final boolean boundary) {
 1345  
             try {
 1346  60
                 lock.writeLock().lock();
 1347  60
                 this.boundary = boundary;
 1348  
             } finally {
 1349  60
                 lock.writeLock().unlock();
 1350  60
             }
 1351  60
         }
 1352  
 
 1353  
         /* (non-Javadoc)
 1354  
          * @see java.lang.Object#toString()
 1355  
          */
 1356  
         @Override
 1357  
         public String toString() {
 1358  2
             final StringBuilder sb = new StringBuilder("{");
 1359  2
             for (final TrieNode<ValueNode> node : children.values()) {
 1360  4
                 node.toString(sb, "");
 1361  
             }
 1362  2
             return sb.append("}").toString();
 1363  
         }
 1364  
 
 1365  
         /*
 1366  
                 @SuppressWarnings("unchecked")
 1367  
                 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
 1368  
                     in.defaultReadObject();
 1369  
                     character = Character.valueOf(in.readChar());
 1370  
                     final byte b = in.readByte();
 1371  
                     boundary = ((b & 1) == 1);
 1372  
                     if ((b & 2) != 0) {
 1373  
                         object = (ValueNode) in.readObject();
 1374  
                     }
 1375  
                     final char count = in.readChar();
 1376  
                     children = new TreeMap<Character, TrieNode<ValueNode>>();
 1377  
                     for (char i = 0; i < count; i++) {
 1378  
                         final TrieNode<ValueNode> node = (TrieNode<ValueNode>) in.readObject();
 1379  
                         children.put(node.character, node);
 1380  
                     }
 1381  
                 }
 1382  
         */
 1383  
         private Object setValue(final ValueNode obj) {
 1384  551
             final Object result = this.object;
 1385  551
             this.object = obj;
 1386  551
             return result;
 1387  
         }
 1388  
 
 1389  
         /*
 1390  
                 private void writeObject(final ObjectOutputStream out) throws IOException {
 1391  
                     try {
 1392  
                         lock.readLock().lock();
 1393  
                         out.defaultWriteObject();
 1394  
                         out.writeChar(character.charValue());
 1395  
                         byte b = (boundary) ? (byte) 1 : 0;
 1396  
                         b |= (object != null) ? 1 << 1 : 0;
 1397  
                         out.writeByte(b);
 1398  
                         if (object != null) {
 1399  
                             out.writeObject(object);
 1400  
                         }
 1401  
                         out.writeChar(children != null ? (char) children.size() : 0);
 1402  
                         if (children != null) {
 1403  
                             for (final TrieNode<ValueNode> node : children.values()) {
 1404  
                                 out.writeObject(node);
 1405  
                             }
 1406  
                         }
 1407  
                     } finally {
 1408  
                         lock.readLock().unlock();
 1409  
                     }
 1410  
                 }*/
 1411  
 
 1412  
         /**
 1413  
          * Append.
 1414  
          * 
 1415  
          * @param sb
 1416  
          *            the sb
 1417  
          * @param prefix
 1418  
          *            the prefix
 1419  
          * @return the string builder
 1420  
          */
 1421  
         protected StringBuilder toString(final StringBuilder sb, final String prefix) {
 1422  44
             if (isBoundary() && object != null) {
 1423  22
                 sb.append(prefix + character);
 1424  22
                 sb.append(" : ").append(object.toString()).append(";\n");
 1425  
             }
 1426  44
             for (final TrieNode<ValueNode> node : children.values()) {
 1427  40
                 node.toString(sb, prefix + character.charValue());
 1428  
             }
 1429  44
             return sb;
 1430  
         }
 1431  
 
 1432  
     }
 1433  
 
 1434  
 }