Modifying Tries code in Java

Question

I am using Tries data structure to determine to which country a phonenumber belongs to based on number prefix.

I am using Tries implementation that Vladimir Kroz has created, which works really well: here

This is how I populate Tries map:

private static Trie<Country> trie = new Trie<>();
trie.put("7", new Country(countryID, country));
trie.put("794", new Country(countryID, country));

As you can see Tries holds phone number prefix as key and Country object as value.

This is how I perform searching:

Country country = trie.get("79519637944");
String CountryName = country.getName();

As you can see I use a phone number as keyword. Now Tries is trying to find matching prefix for this number. Tries will crawl as deep as it can starting from the first digit. If it can't find any matching number in the tree, then it will return the value of that particular prefix.

It works very well, but needs a little bit tweaking.

Let's say that I have prefix 7 and prefix 746.

Now when I try to find phone nr 74568706987069, then Tries will return null because it will crawl into tree like this 7-> 4-> will try to find 5, but it won't so it will return value that is associated with prefix 74 instead of 7.

How to make it remember the last prefix that value is not null.

Tries code is as follows (the search takes place in _get method):

import java.util.HashMap;
import java.util.Map;



/**
 * Prefix table based on trie structure. Allows to perform incremental lookup
 * and match based on search key prefixes (classic example - determine phone
 * area code for given phone number)
 * 
 * @param <V>
 *            a type of value object to be stored along with prefix (e.g when
 *            key is a country name, the value could be a name of the country)
 * 
 * @author Vladimir Kroz
 */
public class Trie<V> {


Entry<V> entry;
char key;
Map<Character, Trie<V>> childrens;

public Trie() {
    this.childrens = new HashMap<Character, Trie<V>>(10);
    entry = new Entry<V>();
}

/** non-public, used by _put() */
Trie(char key) {
    this.childrens = new HashMap<Character, Trie<V>>(10);
    this.key = key;
    entry = new Entry<V>();
}

public void put(String key, V value) {
    _put(new StringBuffer(key), new StringBuffer(""), value);
}

void _put(StringBuffer remainder, StringBuffer prefix, V value) {
    if (remainder.length() > 0) {
        char keyElement = remainder.charAt(0);
        Trie<V> t = null;
        try {
            t = childrens.get(keyElement);
        } catch (IndexOutOfBoundsException e) {
        }
        if (t == null) {
            t = new Trie<V>(keyElement);
            childrens.put(keyElement, t);
        }
        prefix.append(remainder.charAt(0));
        t._put(remainder.deleteCharAt(0), prefix, value);
    } else {
        this.entry.value = value;
        this.entry.prefix = prefix.toString();
    }

}

/**
 * Retrieves element from prefix table matching as a prefix to provided key.
 * E.g. is key is "abcde" and prefix table has node "ab" then this call will
 * return "ab"
 * 
 * @param key
 *            a string which starts with prefix to be searched in the table
 *            (e.g. phone number)
 * @return an Object assosiated with matching prefix (i.e if key is a phone
 *         number it may return a corresponding country name)
 */
public V get(String key) {
    return _get(new StringBuffer(key), 0);
}

/**
 * Returns true if key has matching prefix in the table
 */
public boolean hasPrefix(String key) {
    return ((this.get(key) != null) ? true : false);
}

V _get(StringBuffer key, int level) {
    if (key.length() > 0) {
        Trie<V> t = childrens.get(key.charAt(0));
        if (t != null) {
            return t._get(key.deleteCharAt(0), ++level);
        } else {
            return (level > 0) ? entry.value : null;
        }

    } else {
        return entry.value;
    }
}

@Override
public String toString() {
    return "Trie [entry=" + entry + ", key=" + key + ", childrens="
            + childrens + "]";
}

static public class Entry<V> {
    String prefix;
    V value;

    public Entry() {
    }

    public Entry(String p, V v) {
        prefix = p;
        value = v;
    }

    public String prefix() {
        return prefix;
    }

    public V value() {
        return value;
    }

    @Override
    public String toString() {
        return "Entry [prefix=" + prefix + ", value=" + value + "]";
    }

}
}

Any help is appreciated!

Answer 1

I was able to find a solution. The modified code is:

package tiesImpl;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * Prefix table based on Trie structure. Allows to perform incremental lookup
 * and match based on search key prefixes (classic example - determine phone
 * area code for given phone number)
 *
 * @param <V> a type of value object to be stored along with prefix (e.g when
 * key is a country name, the value could be a name of the country)
 *
 * @author Vladimir Kroz
 * https://vkroz.wordpress.com/2012/03/23/prefix-table-trie-implementation-in-java/
 */
public class Trie<V> {

Entry<V> entry;
char key;
Map<Character, Trie<V>> children;

public Trie() {
    this.children = new HashMap<>(10);
    entry = new Entry<>();
}

/**
 * non-public, used by _put()
 */
Trie(char key) {
    this.children = new HashMap<>(10);
    this.key = key;
    entry = new Entry<>();
}

public void put(String key, V value) {
    _put(new StringBuffer(key), new StringBuffer(""), value);
}

void _put(StringBuffer remainder, StringBuffer prefix, V value) {
    if (remainder.length() > 0) {
        char keyElement = remainder.charAt(0);
        Trie<V> t = null;
        try {
            t = children.get(keyElement);
        } catch (IndexOutOfBoundsException e) {
        }
        if (t == null) {
            t = new Trie<>(keyElement);
            children.put(keyElement, t);
        }
        prefix.append(remainder.charAt(0));
        t._put(remainder.deleteCharAt(0), prefix, value);
    } else {
        this.entry.value = value;
        this.entry.prefix = prefix.toString();
    }

}

/**
 * Retrieves element from prefix table matching as a prefix to provided
 * key. E.g. if key is "37251656565" and prefix table has node "372" then
 * this call will return the value of "372"
 *
 * @param key a string which starts with prefix to be searched in the table
 * (e.g. phone number)
 * @return an Object associated with matching prefix (i.e if key is a phone
 * number it may return a corresponding country name)
 */
public V get(String key) {
    return _get(new StringBuffer(key), 0);
}

/**
 * Returns true if key has matching prefix in the table
 *
 * @param key
 * @return
 */
public boolean hasPrefix(String key) {
    return this.get(key) != null;
}

V _get(StringBuffer key, int level) {
    if (key.length() > 0) {
        Trie<V> t = children.get(key.charAt(0));
        if (t != null) {
            //FYI: modified code to return deepest with value instead of returning null if prefix doesn't have corresponding value.
            V result = t._get(key.deleteCharAt(0), ++level);
            return result == null ? entry.value : result;

        } else {
            return (level > 0) ? entry.value : null;
        }

    } else {
        return entry.value;
    }
}

@Override
//For debugging
public String toString() {

    Iterator<Character> it = children.keySet().iterator();
    StringBuffer childs = new StringBuffer();

    while (it.hasNext()) {
        Character _key = it.next();
        childs.append(String.format("\n%s\n",
                //Adding a tab to the beginning of every line to create a visual tree
                String.format("%s: %s", _key, children.get(_key)).replaceAll("(?m)(^)", "\t")));
    }

    return String.format("Trie [entry=%s, children=%s]", entry, childs);
}

static public class Entry<V> {

    String prefix;
    V value;

    public Entry() {
    }

    public Entry(String p, V v) {
        prefix = p;
        value = v;
    }

    public String prefix() {
        return prefix;
    }

    public V value() {
        return value;
    }

    @Override
    public String toString() {
        return "Entry [prefix=" + prefix + ", value=" + value + "]";
    }

}
}

Hope it will be helpful to others also! Cheers!