package lazystrings.datastructures;

import java.util.Collection;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import lazystrings.datastructures.charmap.CharMap;
import lazystrings.datastructures.charmap.RadixCharMap;
import lazystrings.datastructures.charmap.SingleCharMap;
import lazystrings.util.StringUtils;

/**
 * Implementation of a Trie. Currently uses Strings for keys, but will be improved
 * to use arbitrary CharStreams.
 * 
 * @author david
 */
public final class Trie<T> implements Map<CharSequence, T>
{

  public void clear() {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public boolean containsKey(Object key) {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public boolean containsValue(Object value) {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public Set<Entry<CharSequence, T>> entrySet() {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public boolean isEmpty() {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public Set<CharSequence> keySet() {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public void putAll(Map<? extends CharSequence, ? extends T> m) {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public T remove(Object key) {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public int size() {
    throw new UnsupportedOperationException("Not supported yet.");
  }

  public Collection<T> values() {
    throw new UnsupportedOperationException("Not supported yet.");
  }
  @SuppressWarnings("unchecked")
  private CharMap<Trie<T>> leaves = RadixCharMap.BLANK;    
  private String prefix = "";

  private T value;  
  
  public Trie() { }
  
  private Trie(String prefix, CharMap<Trie<T>> leaves){
    this.prefix = prefix;
    this.leaves = leaves;
  }
    
  private Trie(String prefix){
    this.prefix = prefix;
  }
   
  public T get(Object key){
    if (key instanceof CharSequence) return this.get((CharSequence)key);
    else return null;
  }
  
  public T get(CharSequence key){
    int j = 0;
    Trie<T> current = this;
    boolean keepRunning = true;
    for (int i = 0; (i < key.length()) && keepRunning && (current != null); i++){
      if (j >= current.prefix.length()){
        current = current.leaves.get(key.charAt(i));
        j = 0;
      }
      else{
        keepRunning = (key.charAt(i) != current.prefix.charAt(j));
        j++;
      }            
    }
    if ((current == null) || !keepRunning || (j != current.prefix.length())) return null;
    else return current.value;
  }
    
  public T put(CharSequence key, T value){
    int j = 0;
    Trie<T> current = this;
    Trie<T> last = null;
    boolean noMismatch = true;
    for (int i = 0; (i < key.length()) && noMismatch && (current != null); i++){
      if (j >= current.prefix.length()){
        last = current;
        current = current.leaves.get(key.charAt(i));
        j = 0;
      }
      else{
        noMismatch = (key.charAt(i) != current.prefix.charAt(j));
        j++;
      }            
    }
    
    if (noMismatch){      
      T oldValue = current.value;
      current.value = value;
      return oldValue;
    } else{
      // The key ends 
    }
    //TODO
    return null;
  }
    
    
//
//
//      // We know that key does not start with prefix. Therefore newPrefix is strictly
//      // shorter than prefix and this substring is valid.
//      Trie<T> newTrie = new Trie<T>(this.prefix.substring(newPrefix.length() + 1), this.leaves);
//      this.leaves = new SingleCharMap<Trie<T>>(this.prefix.charAt(newPrefix.length()), newTrie);
//      this.prefix = newPrefix;}
//
//    // We are now guaranteed that key.startsWith(prefix)
//
//    if (key.length() == prefix.length()){
//      // In fact, key == prefix.
//      this.value = value;}
//    else{
//      // key.length() > prefix.length()
//      Trie<T> nextTrie = this.leaves.get(key.charAt(prefix.length()));
//      if (nextTrie == null){
//        nextTrie = new Trie<T>(key.substring(prefix.length() + 1));
//        this.leaves = this.leaves.put(key.charAt(prefix.length()), nextTrie);
//        nextTrie.value = value;
//      }
//      else{
//        nextTrie.put(key.substring(prefix.length() + 1), value);
//      }
//    }
//    return this;}
}