/*
    *  XNap - A P2P framework and client.
    *
    *  See the file AUTHORS for copyright information.
    *
    *  This program is free software; you can redistribute it and/or modify
    *  it under the terms of the GNU General Public License as published by
    *  the Free Software Foundation.
    *
   *  This program is distributed in the hope that it will be useful,
   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *  GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License
   *  along with this program; if not, write to the Free Software
   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   */
  package org.xnap.gui.component;
  
  import java.util.Arrays;
  import java.util.Stack;
  
  import javax.swing.DefaultComboBoxModel;
  
  import org.apache.log4j.Logger;
  
  
  /***
   * The DefaultComboBoxModel uses a ternary search tree for completion.
   */
  public class DefaultCompletionModel extends DefaultComboBoxModel
      implements CompletionModel
  {
      private static Logger logger =
          Logger.getLogger(DefaultCompletionModel.class);
  
      //--- Constant(s) ---
      //--- Data field(s) ---
      private CharNode root = null;
  
      //--- Constructor(s) ---
      /***
       * Constructs a new model with no items.
       */
      public DefaultCompletionModel() 
  	{
  	}
  
      /***
       * Constructs a new model using the given items for completion.
       *
       * @param items the objects used for completion
       */
      public DefaultCompletionModel(Object[] items)
      {
          this(items, false);
      }
  
      /***
       * Constructs a new model using the given items for completion.
       *
       * @param items the array of objects used for completion
       * @param sorted whether the array of items is sorted or not
       */
      public DefaultCompletionModel(Object[] items, boolean sorted)
      {
          if (!sorted) {
              Arrays.sort(items);
          }
          insert(items, 0, items.length);
      }
  
      public boolean complete(String prefix)
      {
          removeAllElements();
  
          if (prefix.length() == 0) {
              //  collectElements(root);
          }
          else {
              CharNode node = search(prefix);
  
              if (node != null) {
                  if (node.obj != null) {
                      addElement(node.obj);
                  }
                  collectElements(node.eqkid);
              }
          }
          return getSize() > 0;
      }
  
      public String completeUniquePrefix(String prefix)
      {
          CharNode node = search(prefix);
  
          if (node != null && node.obj == null && node.eqkid != null) {
              StringBuffer sb = new StringBuffer(prefix);
 			node = node.eqkid;
 
             while ((node != null) && (node.lokid == null) 
 				   && (node.hikid == null)) {
                 sb.append(node.splitchar);
 				if (node.obj != null) {
 					break;
 				}
                 node = node.eqkid;
             }
             return sb.toString();
         }
         return prefix;
     }
 
     //--- Method(s) ---
 
     /***
      * Adds an object to the completion tree.
      *
      * @param object the object which is completed using its {@link
      * Object#toString()} method 
 	 */
     public void insert(Object object)
     {
         char[] key = object.toString().toCharArray();
         root = insert(root, key, 0, object);
     }
 
 	// TODO
     public void remove(Object object)
     {
 		CharNode node = root;
         int index = 0;
 		Stack stack = new Stack();
 		String prefix = object.toString();
 
         while ((node != null) && (index < prefix.length())) {
 			stack.push(node);
             char c = prefix.charAt(index);
 
             if (c < node.splitchar) {
                 node = node.lokid;
             }
             else if (c == node.splitchar) {
                 if (index == (prefix.length() - 1)) {
                     break;
                 }
                 else {
                     node = node.eqkid;
                     index++;
                 }
             }
             else {
                 node = node.hikid;
             }
         }
 		
 		if (node != null && node.obj == object) {
 			node.obj = null;
 			stack.pop();
 			while (node.obj == null && node.eqkid == null && node.lokid == null
 				   && node.hikid == null) {
 				CharNode parent = (CharNode)stack.pop();
 				
 			}
 		}
 	}
 
     /***
      * Traverses the tree preorder wise and adds all elements to the model.
      */
     private void collectElements(CharNode node)
     {
         if (node != null) {
             collectElements(node.lokid);
 
             if (node.obj != null) {
                 addElement(node.obj);
             }
             collectElements(node.eqkid);
             collectElements(node.hikid);
         }
     }
 
     private void insert(Object[] items, int left, int right)
     {
         if (left < right) {
             int m = left + (int)Math.floor((right - left) / 2);
             insert(items[m]);
             insert(items, left, m);
             insert(items, m + 1, right);
         }
     }
 
     private CharNode insert(CharNode node, char[] key, int index, Object object)
     {
         if (node == null) {
             node = new CharNode(key[index]);
 
             if (index == (key.length - 1)) {
                 node.obj = object;
             }
         }
 
         if (key[index] < node.splitchar) {
             node.lokid = insert(node.lokid, key, index, object);
         }
         else if (key[index] == node.splitchar) {
             if (++index < key.length) {
                 node.eqkid = insert(node.eqkid, key, index, object);
             }
             else {
                 // the newly inserted object replaces the old one
                 node.obj = object;
             }
         }
         else {
             node.hikid = insert(node.hikid, key, index, object);
         }
 
         return node;
     }
 
     /***
      * Returns node.
      */
     private CharNode search(String prefix)
     {
         CharNode node = root;
         int index = 0;
 
         while ((node != null) && (index < prefix.length())) {
             logger.debug("Visiting " + node.obj);
 
             char c = prefix.charAt(index);
             logger.debug("checking char " + c);
 
             if (c < node.splitchar) {
                 node = node.lokid;
             }
             else if (c == node.splitchar) {
                 if (index == (prefix.length() - 1)) {
                     return node;
                 }
                 else {
                     node = node.eqkid;
                     index++;
                 }
             }
             else {
                 node = node.hikid;
             }
         }
 
         return node;
     }
 
     //--- Inner class(es) ---
     /***
      * Implementation of ternary search trees.
      */
     private class CharNode
     {
         public char splitchar;
         public CharNode lokid;
         public CharNode eqkid;
         public CharNode hikid;
         public Object obj;
 
         public CharNode(char value)
         {
             splitchar = value;
         }
     }
 }