KezvhLib/src-lib/net/kezvh/collections/text/TrieMap.java

   1 package net.kezvh.collections.text;
   2
   3 import java.util.AbstractMap;
   4 import java.util.AbstractSet;
   5 import java.util.ArrayList;
   6 import java.util.Arrays;
   7 import java.util.Collection;
   8 import java.util.Comparator;
   9 import java.util.Iterator;
  10 import java.util.LinkedList;
  11 import java.util.Map;
  12 import java.util.NoSuchElementException;
  13 import java.util.Set;
  14 import java.util.SortedMap;
  15 import java.util.SortedSet;
  16
  17 import net.kezvh.collections.TreeIterator;
  18 import net.kezvh.collections.views.IteratorView;
  19 import net.kezvh.development.UnimplementedException;
  20 import net.kezvh.functional.lambda.L1;
  21
  22 /**
  23  * @author afflux
  24  * @param <T> COMMENT
  25  */
  26 public class TrieMap<T> extends AbstractMap<String, T> implements SortedMap<String, T> {
  27         private final TreeIterator.ChildrenAccessor<TrieNode<T>> childrenAccessor = new TreeIterator.ChildrenAccessor<TrieNode<T>>() {
  28                 /**
  29                  * @see net.kezvh.collections.TreeIterator.ChildrenAccessor#getChildren(java.lang.Object)
  30                  * @param node COMMENT
  31                  * @return x
  32                  */
  33                 @Override
  34                 public Set<TrieNode<T>> getChildren(final TrieNode<T> node) {
  35                         return new AbstractSet<TrieNode<T>>() {
  36
  37                                 @Override
  38                                 public Iterator<TrieNode<T>> iterator() {
  39                                         return node.suffices.iterator();
  40                                 }
  41
  42                                 @Override
  43                                 public int size() {
  44                                         return node.suffices.size();
  45                                 }
  46
  47                         };
  48                 }
  49         };
  50
  51         private static final class TrieNode<V> {
  52                 private char[] keys = new char[] {};
  53                 private final ArrayList<TrieNode<V>> suffices = new ArrayList<TrieNode<V>>() {
  54                         /**
  55                          * @see java.util.AbstractList#iterator()
  56                          * @return x
  57                          */
  58                         @Override
  59                         public Iterator<TrieNode<V>> iterator() {
  60                                 final Iterator<TrieNode<V>> iterator = super.iterator();
  61                                 return new Iterator<TrieNode<V>>() {
  62                                         /**
  63                                          * @see java.util.Iterator#hasNext()
  64                                          * @return x
  65                                          */
  66                                         @Override
  67                                         public boolean hasNext() {
  68                                                 return iterator.hasNext();
  69                                         }
  70
  71                                         /**
  72                                          * @see java.util.Iterator#next()
  73                                          * @return x
  74                                          */
  75                                         @Override
  76                                         public TrieNode<V> next() {
  77                                                 return iterator.next();
  78                                         }
  79
  80                                         /**
  81                                          * @see java.util.Iterator#remove()
  82                                          */
  83                                         @Override
  84                                         public void remove() {
  85                                                 iterator.remove();
  86                                                 throw new UnimplementedException("need to invoke remove on the TriENode"); // FIXME
  87                                         }
  88                                 };
  89                         }
  90                 };
  91                 private V value;
  92
  93                 /**
  94                  * @param index COMMENT
  95                  * @return x
  96                  */
  97                 public char getSuffixKey(final int index) {
  98                         return this.keys[index];
  99                 }
 100
 101                 /**
 102                  * @param index COMMENT
 103                  * @return x
 104                  */
 105                 public TrieNode<V> getSuffixNode(final int index) {
 106                         return this.suffices.get(index);
 107                 }
 108
 109                 /**
 110                  * @param key COMMENT
 111                  * @return x
 112                  */
 113                 public TrieNode<V> find(final char key) {
 114                         return this.getSuffixNode(this.keyIndex(key));
 115                 }
 116
 117                 /**
 118                  * @param key COMMENT
 119                  * @return x
 120                  */
 121                 public int keyIndex(final char key) {
 122                         return Arrays.binarySearch(this.keys, key);
 123                 }
 124
 125                 /**
 126                  * @param key COMMENT
 127                  * @param newValue COMMENT
 128                  * @param insertionPoint COMMENT
 129                  */
 130                 public void insert(final char key, final TrieNode<V> newValue, final int insertionPoint) {
 131                         final char[] newKeys = new char[this.keys.length + 1];
 132                         System.arraycopy(this.keys, 0, newKeys, 0, insertionPoint);
 133                         newKeys[insertionPoint] = key;
 134                         System.arraycopy(this.keys, insertionPoint, newKeys, insertionPoint + 1, this.keys.length - insertionPoint);
 135                         this.keys = newKeys;
 136                         this.suffices.add(insertionPoint, newValue);
 137                         this.suffices.trimToSize();
 138                 }
 139
 140                 /**
 141                  * @return x
 142                  */
 143                 public int getNumKeys() {
 144                         return this.keys.length;
 145                 }
 146
 147                 /**
 148                  * @return your mom
 149                  */
 150                 public int getNumEntries() {
 151                         int numEntries = 0;
 152                         if (this.value != null)
 153                                 numEntries++;
 154
 155                         for (final TrieNode<V> t : this.suffices)
 156                                 numEntries += t.getNumEntries();
 157                         return numEntries;
 158                 }
 159
 160                 /**
 161                  * @param key COMMENT
 162                  * @param newValue COMMENT
 163                  * @return x
 164                  */
 165                 public TrieNode<V> put(final char key, final TrieNode<V> newValue) {
 166                         final int index = this.keyIndex(key);
 167                         if (index >= 0)
 168                                 return this.suffices.set(index, newValue);
 169
 170                         final int insertionPoint = -(index + 1);
 171                         this.insert(key, newValue, insertionPoint);
 172                         return null;
 173                 }
 174
 175                 /**
 176                  * @return x
 177                  */
 178                 public boolean hasValue() {
 179                         return this.value != null;
 180                 }
 181
 182                 /**
 183                  * @return x
 184                  */
 185                 public V getValue() {
 186                         return this.value;
 187                 }
 188
 189                 /**
 190                  * @param value COMMENT
 191                  * @return x
 192                  */
 193                 public V setValue(final V value) {
 194                         try {
 195                                 return this.value;
 196                         } finally {
 197                                 this.value = value;
 198                         }
 199                 }
 200         }
 201
 202         private final TrieNode<T> rootTrieNode = new TrieNode<T>();
 203
 204         /**
 205          * @see java.util.AbstractMap#put(java.lang.Object, java.lang.Object)
 206          * @param key COMMENT
 207          * @param value COMMENT
 208          * @return x
 209          */
 210         @Override
 211         public T put(final String key, final T value) {
 212                 // final long[] longs = TrieMap.getLongs(key);
 213                 final char[] chars = key.toCharArray();
 214                 TrieNode<T> t = this.rootTrieNode;
 215
 216                 for (final char element : chars) {
 217                         final int index = t.keyIndex(element);
 218                         if (index >= 0)
 219                                 t = t.getSuffixNode(index);
 220
 221                         else {
 222                                 final int insertionPoint = -(index + 1);
 223                                 final TrieNode<T> tn = new TrieNode<T>();
 224                                 t.insert(element, tn, insertionPoint);
 225                                 t = tn;
 226                         }
 227                 }
 228
 229                 return t.setValue(value);
 230         }
 231
 232         /**
 233          * @see java.util.AbstractMap#containsKey(java.lang.Object)
 234          * @param key COMMENT
 235          * @return x
 236          */
 237         @Override
 238         public boolean containsKey(final Object key) {
 239                 if (key == null || String.class != key.getClass())
 240                         return false;
 241
 242                 final String string = (String) key;
 243                 // final long[] longs = TrieMap.getLongs(string);
 244                 final char[] chars = string.toCharArray();
 245                 TrieNode<T> t = this.rootTrieNode;
 246                 for (final char element : chars) {
 247                         final int index = t.keyIndex(element);
 248                         if (index >= 0)
 249                                 t = t.getSuffixNode(index);
 250                         else
 251                                 return false;
 252                 }
 253
 254                 return t.hasValue();
 255         }
 256
 257         /**
 258          * @see java.util.AbstractMap#get(java.lang.Object)
 259          * @param key COMMENT
 260          * @return x
 261          */
 262         @Override
 263         public T get(final Object key) {
 264                 if (key == null || String.class != key.getClass())
 265                         return null;
 266
 267                 final String string = (String) key;
 268                 // final long[] longs = TrieMap.getLongs(string);
 269                 final char[] chars = string.toCharArray();
 270                 TrieNode<T> t = this.rootTrieNode;
 271                 for (final char element : chars) {
 272                         final int index = t.keyIndex(element);
 273                         if (index >= 0)
 274                                 t = t.getSuffixNode(index);
 275                         else
 276                                 return null;
 277                 }
 278
 279                 return t.getValue();
 280         }
 281
 282         /**
 283          * TODO: this MUST implement SortedSet
 284          *
 285          * @author afflux
 286          */
 287         private final class EntrySet extends AbstractSet<Map.Entry<String, T>> implements SortedSet<Map.Entry<String, T>> {
 288
 289                 private final L1<Map.Entry<String, T>, TrieNode<T>> map = new L1<Entry<String, T>, TrieNode<T>>() {
 290                         /**
 291                          * @see L1
 292                          * @param param COMMENT
 293                          * @return x
 294                          */
 295                         @Override
 296                         public Entry<String, T> op(final TrieNode<T> param) {
 297                                 return new Map.Entry<String, T>() {
 298                                         /**
 299                                          * @see java.util.Map.Entry#getKey()
 300                                          * @return x
 301                                          */
 302                                         @Override
 303                                         public String getKey() {
 304
 305                                                 throw new UnimplementedException();
 306                                                 // param
 307                                                 // AAAAAAAAAAAAARRRRRRRRRRRRRGGGGGGGGGGGGGGGGGHHHHHHHHHHHHHHH
 308                                                 // // FIXME
 309                                         }
 310
 311                                         /**
 312                                          * @see java.util.Map.Entry#getValue()
 313                                          * @return x
 314                                          */
 315                                         @Override
 316                                         public T getValue() {
 317                                                 return param.getValue();
 318                                         }
 319
 320                                         /**
 321                                          * @see java.util.Map.Entry#setValue(java.lang.Object)
 322                                          * @param value COMMENT
 323                                          * @return x
 324                                          */
 325                                         @Override
 326                                         public T setValue(final T value) {
 327                                                 return param.setValue(value);
 328                                         }
 329                                 };
 330                         }
 331                 };
 332
 333                 /**
 334                  * @see java.util.AbstractCollection#iterator()
 335                  * @return x
 336                  */
 337                 @Override
 338                 public Iterator<java.util.Map.Entry<String, T>> iterator() {
 339                         return new IteratorView<TrieNode<T>, Entry<String, T>>(this.map, new TreeIterator<TrieNode<T>>(TrieMap.this.rootTrieNode, TrieMap.this.childrenAccessor));
 340                 }
 341
 342                 /**
 343                  * @see java.util.AbstractCollection#size()
 344                  * @return x
 345                  */
 346                 @Override
 347                 public int size() {
 348                         return TrieMap.this.size();
 349                 }
 350
 351                 @Override
 352                 public Comparator<? super java.util.Map.Entry<String, T>> comparator() {
 353                         throw new UnimplementedException(); // FIXME
 354                 }
 355
 356                 @Override
 357                 public java.util.Map.Entry<String, T> first() {
 358                         throw new UnimplementedException(); // FIXME
 359                 }
 360
 361                 @Override
 362                 public SortedSet<java.util.Map.Entry<String, T>> headSet(final java.util.Map.Entry<String, T> toElement) {
 363                         throw new UnimplementedException(); // FIXME
 364                 }
 365
 366                 @Override
 367                 public java.util.Map.Entry<String, T> last() {
 368                         throw new UnimplementedException(); // FIXME
 369                 }
 370
 371                 @Override
 372                 public SortedSet<java.util.Map.Entry<String, T>> subSet(final java.util.Map.Entry<String, T> fromElement, final java.util.Map.Entry<String, T> toElement) {
 373                         throw new UnimplementedException(); // FIXME
 374                 }
 375
 376                 @Override
 377                 public SortedSet<java.util.Map.Entry<String, T>> tailSet(final java.util.Map.Entry<String, T> fromElement) {
 378                         throw new UnimplementedException(); // FIXME
 379                 }
 380
 381         }
 382
 383         private EntrySet entrySet = null;
 384
 385         /**
 386          * @see java.util.AbstractMap#entrySet()
 387          * @return x
 388          */
 389         @Override
 390         public Set<java.util.Map.Entry<String, T>> entrySet() {
 391                 if (this.entrySet == null)
 392                         this.entrySet = new EntrySet();
 393                 return this.entrySet;
 394         }
 395
 396         /**
 397          * @see java.util.SortedMap#comparator()
 398          * @return x
 399          */
 400         public Comparator<? super String> comparator() {
 401                 return new Comparator<String>() {
 402                         /**
 403                          * @see java.util.Comparator#compare(java.lang.Object,
 404                          *      java.lang.Object)
 405                          * @param o1 COMMENT
 406                          * @param o2 COMMENT
 407                          * @return o1.compareTo(o2)
 408                          */
 409                         @Override
 410                         public int compare(final String o1, final String o2) {
 411                                 return o1.compareTo(o2);
 412                         }
 413                 };
 414         }
 415
 416         /**
 417          * @see java.util.SortedMap#firstKey()
 418          * @return x
 419          */
 420         public String firstKey() {
 421                 if (this.isEmpty())
 422                         throw new NoSuchElementException();
 423
 424                 return null;
 425         }
 426
 427         /**
 428          * @see java.util.SortedMap#headMap(java.lang.Object)
 429          * @param toKey COMMENT
 430          * @return x
 431          */
 432         public SortedMap<String, T> headMap(final String toKey) {
 433                 return null;
 434         }
 435
 436         /**
 437          * @see java.util.SortedMap#lastKey()
 438          * @return x
 439          */
 440         public String lastKey() {
 441                 if (this.isEmpty())
 442                         throw new NoSuchElementException();
 443
 444                 return null;
 445         }
 446
 447         /**
 448          * @see java.util.SortedMap#subMap(java.lang.Object, java.lang.Object)
 449          * @param fromKey COMMENT
 450          * @param toKey COMMENT
 451          * @return x
 452          */
 453         public SortedMap<String, T> subMap(final String fromKey, final String toKey) {
 454                 return null;
 455         }
 456
 457         /**
 458          * @see java.util.SortedMap#tailMap(java.lang.Object)
 459          * @param fromKey COMMENT
 460          * @return x
 461          */
 462         public SortedMap<String, T> tailMap(final String fromKey) {
 463                 return null;
 464         }
 465
 466         private boolean hasSuffix(final TrieNode<T> trieNode, final char[] chars, final int firstCharIndex) {
 467                 TrieNode<T> currentNode = trieNode;
 468                 for (int i = firstCharIndex; i < chars.length; i++) {
 469                         final int keyIndex = currentNode.keyIndex(chars[i]);
 470                         if (keyIndex >= 0)
 471                                 currentNode = currentNode.getSuffixNode(keyIndex);
 472                         else
 473                                 return false;
 474                 }
 475
 476                 return currentNode.hasValue();
 477         }
 478
 479         private ArrayList<TrieNode<T>> getTrieNodes(final char[] chars) {
 480                 TrieNode<T> currentTrieNode = this.rootTrieNode;
 481                 final ArrayList<TrieNode<T>> trieNodes = new ArrayList<TrieNode<T>>(chars.length + 1);
 482
 483                 trieNodes.add(this.rootTrieNode);
 484
 485                 for (final char element : chars) {
 486                         final TrieNode<T> nextTrieNode = currentTrieNode.find(element);
 487                         trieNodes.add(nextTrieNode);
 488                         currentTrieNode = nextTrieNode;
 489                 }
 490                 trieNodes.trimToSize();
 491                 return trieNodes;
 492         }
 493
 494         private Collection<String> getSingleChars() {
 495                 final Collection<String> similar = new LinkedList<String>();
 496                 for (int i = 0; i < this.rootTrieNode.getNumKeys(); i++)
 497                         if (this.rootTrieNode.getSuffixNode(i).hasValue())
 498                                 similar.add(String.valueOf(this.rootTrieNode.getSuffixKey(i)));
 499                 return similar;
 500         }
 501
 502         /**
 503          * @param key COMMENT
 504          * @return x
 505          */
 506         public Collection<String> getKeysSimilarTo(final String key) {
 507                 // FIXME refactor this nasty motherfucker.
 508                 final int len = key.length();
 509                 if (len == 0)
 510                         return this.getSingleChars();
 511                 final Collection<String> similar = new LinkedList<String>();
 512
 513                 final StringBuffer add = new StringBuffer(key + 'X'); // add
 514                 final StringBuffer rem = new StringBuffer(key.subSequence(0, len - 1)); // remove
 515                 final StringBuffer del = new StringBuffer(key); // change
 516
 517                 final char[] chars = key.toCharArray();
 518                 final ArrayList<TrieNode<T>> trieNodes = this.getTrieNodes(chars); // len
 519                 // +
 520                 // 1
 521                 // elements,
 522                 // 0
 523                 // is
 524                 // root
 525
 526                 { // first iteration, last character, only care about adds
 527                         final TrieNode<T> lastNode = trieNodes.get(len);
 528                         for (int i = 0; i < lastNode.getNumKeys(); i++)
 529                                 if (lastNode.getSuffixNode(i).hasValue()) {
 530                                         add.setCharAt(len, lastNode.getSuffixKey(i));
 531                                         similar.add(add.toString());
 532                                 }
 533
 534                         add.setCharAt(len, chars[len - 1]); // set last character of add
 535                 }
 536
 537                 for (int k = len - 1; k >= 0; k--) {
 538                         final TrieNode<T> cur = trieNodes.get(k);
 539                         if (this.hasSuffix(cur, chars, k + 1)) // removes
 540                                 similar.add(rem.toString());
 541
 542                         for (int i = 0; i < cur.getNumKeys(); i++) {
 543                                 final char c = cur.getSuffixKey(i);
 544
 545                                 if (chars[k] == c)
 546                                         continue;
 547
 548                                 final TrieNode<T> node = cur.getSuffixNode(i);
 549
 550                                 if (this.hasSuffix(node, chars, k + 1)) { // changes
 551                                         del.setCharAt(k, c);
 552                                         similar.add(del.toString());
 553                                 }
 554
 555                                 if (this.hasSuffix(node, chars, k)) { // adds
 556                                         add.setCharAt(k, c);
 557                                         similar.add(add.toString());
 558                                 }
 559                         }
 560
 561                         del.setCharAt(k, chars[k]);
 562                         if (k > 0) {
 563                                 add.setCharAt(k, chars[k - 1]);
 564                                 rem.setCharAt(k - 1, chars[k]);
 565                         }
 566                 }
 567
 568                 return similar;
 569         }
 570 }