/**
 * This represents an Integer Patricia Tree instance.
 * Each Tree has at least the zeroth node or the root
 * which may have zero or more (< 10) child nodes
 * Each node is represented by an object of type Element
 * The presence of Element at the index indicates that 
 * the value equal to the index is present in the tree
 */
public class DATree {

  private Element zerothNode = new Element();
  private int depth;

  /**
   * This would insert a number in the tree. 
   * This works by tokenizing the number into separate
   * characters and then inserting them one by one in 
   * the tree. If the number already exists at that depth
   * then the next character is taken and the tree is
   * further traversed. This is done until the entire 
   * number is entered in the tree.The maximum depth of 
   * the tree is the size of the number as returned by
   * the length() method on the String form of that number
   */
  public void insert (String number) {
  try {
    char[] numberArray = number.toCharArray();
    Element currentElement = zerothNode;  
    Element tempElement = null;
    for(int i=0; i<numberArray.length;i++) {
      if ((tempElement=currentElement.getElementAt(numberArray[i]-'0')) == null) {
        tempElement = new Element();
        currentElement.insertElementAt(tempElement,(numberArray[i]-'0'));
      }
        currentElement = tempElement;
    }  
   } 
   catch (Exception e) {
      System.out.println("Unable to insert number "+number+
                         " Error : "+e.getMessage());     
   } 
  }


  /**
   * A utility method to print the  value of parent node and print
   * recursively all the child nodes from there 
   */ 
  public void  printLevel(int parentVal,Element currentElement,int depth) {
    Element tempElement = null;
    for(int i=0;i<10;i++) {
     if( (tempElement=currentElement.getElementAt(i))!=null){
       for(int k=0;k<depth;k++)
	 System.out.print("  "); 
         System.out.println(parentVal+","+i);
       printLevel(i,tempElement,depth+1);
     }
    }
  }


  /**
   * A utility method to print the entire tree on the standard output
   */
  public void printAll() {
    printLevel (0,zerothNode,0);
  }


 /**
  * This method returns the number after stripping the prefix as
  * found in the tree. This number is wrapped in the DataRecord
  * structure which will hold the subscriberId also. This is done
  * to reduce the number of queries to get the subscriber profile.
  * If the number is a substring or a proper
  * substring of any pattern in the tree then a null is returned
  * If any pattern is a substring of the number then the substring
  * after stripping the pattern in returned. If neither the number
  * nor the pattern are substrings of each other then the null is returned
  * Consider an example
  * Suppose we create the tree with a pattern 2345
  * Following is the return value for each call of this method.
  * <code>
  * DATree ipt;
  * ipt.insert("2345");
  * ipt.stripPatternFromNumber("234567"); // returns  67
  * ipt.stripPatternFromNumber("23456");  // returns  6
  * ipt.stripPatternFromNumber("2345");   // returns  null
  * ipt.stripPatternFromNumber("234");    // returns  null
  * ipt.stripPatternFromNumber("877");    // returns  null
  * </code>
  */
  public String stripPatternFromNumber(String number) {
   try { 
    char[] numberArray = number.toCharArray();
    Element currentElement = zerothNode;
    Element tempElement = null;
    for(int i=0; i<numberArray.length;i++) {
     if ((numberArray[i] >= '0') & (numberArray[i] <= '9')) { 
      if ((tempElement=currentElement.getElementAt(numberArray[i]-'0')) == null){
        if((currentElement.isLeaf())&(currentElement != zerothNode)){
          return number.substring(i);
        }
        else {
          return null;
        }
      }
      else {
        currentElement = tempElement;
      }
     } 
     else { 
       return null;
     }
    }
    return null;
   }
   catch (Exception e) {
     e.printStackTrace();
     System.out.println("Error in searching number "+number+" "+
                         e.getMessage());
     return null; 
   }
  }

   
}