adt.trie.Trie

   1 /* Osm4j is a library that provides utilities to handle Openstreetmap data in java.
   2  *
   3  * Copyright (C) 2011  Sebastian Kuerten
   4  * 
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 3 of the License, or (at your option) any later version.
   9  * 
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  * 
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  */
  19 
  20 package adt.trie;
  21 
  22 import java.util.Iterator;
  23 
  24 /**
  25  * A Trie implementation that extends the functionality of a map for features like
  26  * prefix-queries.
  27  * 
  28  * TODO: set of methods not complete (i.e. prefix-queries)
  29  * 
  30  * @author Sebastian Kuerten (sebastian.kuerten@fu-berlin.de)
  31  * 
  32  * @param <T>
  33  *            the type of elements to store in this Trie.
  34  */
  35 public class Trie<T> implements Iterable<TrieIterEntry<T>> {
  36 
  37     Node<T> root;
  38 
  39     /**
  40      * Create an empty Trie.
  41      */
  42     public Trie() {
  43         root = new Node<T>("", false, null);
  44     }
  45 
  46     /**
  47      * Insert the tuple <code>(key, val)</code> into the trie.
  48      * 
  49      * @param key
  50      *            the String that is used to store the tuple.
  51      * @param val
  52      *            the value that is associated with <code>key</code>.
  53      */
  54     public void insert(String key, T val) {
  55         root.insert(key, val);
  56     }
  57 
  58     /**
  59      * Find out whether this trie contains the given key.
  60      * 
  61      * @param key
  62      *            the key to look for.
  63      * @return whether the given key is contained in this trie.
  64      */
  65     public boolean contains(String key) {
  66         return root.contains(key);
  67     }
  68 
  69     /**
  70      * Find the value associated with key.
  71      * 
  72      * @param key
  73      *            the value to look for.
  74      * @return the found value or null if not found.
  75      */
  76     public T get(String key) {
  77         return root.get(key);
  78     }
  79 
  80     /**
  81      * Test the trie. TODO: move this to an external test.
  82      * 
  83      * @param args
  84      *            none accepted
  85      */
  86     public static void main(String[] args) {
  87         Trie<Integer> trie = new Trie<Integer>();
  88 
  89         trie.insert("foobar", 1);
  90         trie.insert("foocar", 2);
  91         trie.insert("footar", 2);
  92         trie.insert("foo", 3);
  93         System.out.println(trie.contains("foo"));
  94         System.out.println(trie.get("foo"));
  95         System.exit(0);
  96 
  97         // trie.insert("hallo", 1);
  98         // trie.insert("halli", 2);
  99         // trie.insert("halla", 2);
 100         // trie.insert("hallal", 2);
 101         // trie.insert("boo", 3);
 102         // trie.insert("bar", 3);
 103         // trie.insert("b", 4);
 104         trie.insert("abcd", 1);
 105         trie.insert("abc", 1);
 106         trie.insert("a", 1);
 107         trie.insert("abcd", 5);
 108         trie.insert("abc", 4);
 109         trie.insert("a", 3);
 110         // trie.insert("ab", 1);
 111 
 112         trie.print();
 113 
 114         System.out.println();
 115         System.out.println("FOREACH");
 116         for (TrieIterEntry<Integer> e : trie) {
 117             System.out.println(e.word);
 118         }
 119 
 120         System.out.println("SIZE: " + trie.getSize());
 121 
 122         System.out.println(trie.contains("abcd"));
 123         System.out.println(trie.contains("abc"));
 124         System.out.println(trie.contains("a"));
 125         System.out.println(trie.contains("b"));
 126         System.out.println(trie.contains("abe"));
 127         System.out.println(trie.contains("abcd"));
 128 
 129         System.out.println("CONTAIN...");
 130         System.out.println(trie.get("abcd"));
 131         System.out.println(trie.get("abc"));
 132         System.out.println(trie.get("a"));
 133         System.out.println(trie.get("b"));
 134         System.out.println(trie.get("abe"));
 135         System.out.println(trie.get("abcd"));
 136     }
 137 
 138     private void print() {
 139         System.out.println("OUTPUT");
 140         root.print();
 141     }
 142 
 143     /**
 144      * Get the number of elements residing in this trie.
 145      * 
 146      * @return the number of elements.
 147      */
 148     public int getSize() {
 149         return root.getSize();
 150     }
 151 
 152     @Override
 153     public Iterator<TrieIterEntry<T>> iterator() {
 154         return new TrieIterator<T>(root);
 155     }
 156 }