package org.kit.furia.fragment;
   
   import java.io.StringReader;
   import java.util.HashMap;
   import java.util.Iterator;
   import java.util.LinkedList;
   import java.util.List;
   import java.util.ListIterator;
   import java.util.Map;
  
  import org.ajmm.obsearch.exception.OBException;
  import org.ajmm.obsearch.ob.OBShort;
  import org.kit.furia.misc.IntegerHolder;
  
  import com.sleepycat.bind.tuple.TupleInput;
  import com.sleepycat.bind.tuple.TupleOutput;
  
  /*
   Furia-chan: An Open Source software license violation detector.    
   Copyright (C) 2008 Kyushu Institute of Technology
  
   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, either version 3 of the License, or
   (at your option) any later version.
  
   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, see <http://www.gnu.org/licenses/>.
   */
  
  /**
   * Implementation of the mtd algorithm. This algorithm exploits hash codes from
   * string representation of the tree and its complete subtrees. Additionally, it
   * exploits the fact that once two complete subtrees j and m that belong
   * respectively to trees T1 and T2, the intersection of j and m and all their
   * complete subtrees can be calculated in linear time. This requires to have a
   * value of multiplicity in each node of T1 and T2.
   * So the expected running time is around O(|T1|) (where |T1| the size of the smallest tree)
   * @author Arnoldo Jose Muller Molina
   */
  
  public final class OBFragment implements OBShort {
  
      private Map < MTDFragmentAST, Tuple > mapS;
  
      private Map < String, IntegerHolder > mapN;
  
      private int maxId;
  
      private MTDFragmentAST tree;
      
      public OBFragment(){
          
      }
  
      public OBFragment(String x) throws OBException {
          updateTree(x);
      }
  
      /**
       * Internal method that updates the Tree from the String
       * @throws OBException
       */
      protected final void updateTree(String x) throws OBException {
          tree = parseTree(x);
  
          mapS = new HashMap < MTDFragmentAST, Tuple >();
          mapN = new HashMap < String, IntegerHolder >();
          decorate(tree, new IntegerHolder(0));
      }
  
      public static final  MTDFragmentAST parseTree(String x)
              throws FragmentParseException {
          try {
              FragmentLexer lexer = new FragmentLexer(new StringReader(x));
              FragmentParser parser = new FragmentParser(lexer);
              parser.setASTNodeClass("org.kit.furia.fragment.MTDFragmentAST");
              parser.fragment();
              MTDFragmentAST t = (MTDFragmentAST) parser.getAST();
              t.update();
              return t;
          } catch (Exception e) {
              throw new FragmentParseException(x, e);
          }
      }
  
      /**
       * Returns the size (in nodes) of the tree.
       * @return The size of the tree.
       * @throws OBException
       *                 If something goes wrong.
       */
      public final int size() throws OBException {
          return tree.getSize();
     }
 
     /**
      * @return A String representation of the tree.
      */
     public final String toString() {
         String res = ":(";
         try {
             res = tree.toFuriaChanTree() + "|" + tree.getSize() + "|";
         } catch (Exception e) {
             assert false;
         }
         return res;
     }
 
     /**
      * Re-creates this object from the given byte stream
      * @param in
      *                A byte stream with the data that must be loaded.
      * @see org.ajmm.obsearch.Storable#load(com.sleepycat.bind.tuple.TupleInput)
      */
     public final void load(TupleInput in) throws OBException {
         short size = in.readShort();
         updateTree(in.readBytes(size));
     }
 
     /**
      * Stores this object into the given byte stream.
      * @param out
      *                The byte stream to be used
      * @see org.ajmm.obsearch.Storable#store(com.sleepycat.bind.tuple.TupleOutput)
      */
     public final void store(TupleOutput out) {
         String str = tree.toFuriaChanTree();
         out.writeShort(str.length());
         out.writeBytes(str);
     }
 
     private void decorate(MTDFragmentAST t, IntegerHolder id) {
         if (t == null) {
             return;
         }
         t.update();
         Tuple tMapped = mapS.get(t);
         if (tMapped != null) {
             assert tMapped.tree.hashCode() == t.hashCode();
             tMapped.repetitions.inc();
 
         } else {
             tMapped = new Tuple();
             tMapped.repetitions = new IntegerHolder(1);
             tMapped.id = id.getValue();
             tMapped.tree = t;
             mapS.put(t, tMapped);
             id.inc();
             maxId = id.getValue();
         }
         t.id = tMapped.id;
         t.repetitions = tMapped.repetitions;
         assert mapS.get(t).tree.equals(t) : mapS.get(t).tree.prettyPrint()
                 + " != " + t.prettyPrint();
         assert t.equals(tMapped.tree);
         IntegerHolder node = mapN.get(t.getText());
         if (node != null) {
             node.inc();
         } else {
             mapN.put(t.getText(), new IntegerHolder(1));
         }
         decorate(t.getLeft(), id);
         decorate(t.getSibbling(), id);
     }
 
     public final short distance(OBShort other) {
         OBFragment b = (OBFragment) other;
         // use the smallest tree for the match!
         if (this.tree.getSize() < b.tree.getSize()) {
             return this.mtd( b);
         } else {
             return b.mtd( this);
         }
         /*if (this.tree.getSize() < b.tree.getSize()) {
             return (short)this.ds( b);
         } else {
             return (short)b.ds( this);
         }*/
     }
 
     public final short mtd(OBFragment other) {
 
         int res =  (ds(other) + dn(other) ) / 2;
         //assert res == distance(this.tree, other.tree);
         return (short)res;
     }
 
     private int dnAux(OBFragment other) {
         int res = 0;
         Iterator < Map.Entry < String, IntegerHolder >> keysIt = mapN
                 .entrySet().iterator();
         while (keysIt.hasNext()) {
             Map.Entry < String, IntegerHolder > entry = keysIt.next();
             IntegerHolder n2 = other.mapN.get(entry.getKey());
             if (n2 != null) {
                 IntegerHolder n1 = entry.getValue();
                 res += Math.min(n1.getValue(), n2.getValue());
             }
         }
         return res;
     }
 
     public int ds(OBFragment other) {
         boolean[] visited = new boolean[maxId];
         int res = ds(tree, other, visited);
         return (tree.getSize() + other.tree.getSize()) - (2 * res);
     }
 
     public int dn(OBFragment other) {
         int res = dnAux(other);
         return (tree.getSize() + other.tree.getSize()) - (2 * res);
     }
 
     /*
      * public int ftedAux(MTDFragmentASTHolder other) { boolean[] visited = new
      * boolean[maxId]; int res = ds(tree, other, visited); return
      * (tree.getSize() + other.tree.getSize()) - (2 * res); }
      */
 
     private int ds(MTDFragmentAST current, OBFragment other, boolean[] visited) {
         if (current == null) {
             return 0;
         }
         int res = 0;
         if (!visited[current.id]) {
 
             Tuple m2 = other.mapS.get(current);
 
             if (m2 != null) {
                 assert current.equals(m2.tree) : " Tree A:"
                         + current.prettyPrint() + " Tree B: "
                         + m2.tree.prettyPrint() + " hash A "
                         + current.hashCode() + " hash B " + m2.tree.hashCode();
                 res = update(current, m2.tree, visited);
             } else {
                 res = ds(current.getLeft(), other, visited);
             }
         }
         return res + ds(current.getSibbling(), other, visited);
     }
 
     private int update(MTDFragmentAST current, MTDFragmentAST current2,
             boolean[] visited) {
         assert current != null;
         if (visited[current.id]) {
             return 0;
         }
         visited[current.id] = true;
         int res = Math.min(current.repetitions.getValue(), current2.repetitions
                 .getValue());
         return res + updateAux(current.getLeft(), current2.getLeft(), visited);
     }
 
     private int updateAux(MTDFragmentAST current, MTDFragmentAST current2,
             boolean[] visited) {
         if (current == null) {
             return 0;
         }
         assert current != null && current2 != null;
         int res = 0, res1 = 0, res2 = 0;
 
         if (!visited[current.id]) {
 
             visited[current.id] = true;
             res = Math.min(current.repetitions.getValue(), current2.repetitions
                     .getValue());
             res1 = updateAux(current.getLeft(), current2.getLeft(), visited);
 
         }
         res2 = updateAux(current.getSibbling(), current2.getSibbling(), visited);
         return res + res1 + res2;
 
     }
 
     private class Tuple {
         public MTDFragmentAST tree;
 
         public int id;
 
         public IntegerHolder repetitions;
 
         public String toString() {
             return tree.toString() + " " + id + " " + repetitions.getValue();
         }
     }
 
     public MTDFragmentAST getTree() {
         return tree;
     }
 
     public void setTree(MTDFragmentAST tree) {
         this.tree = tree;
     }
 
     /**
      * Returns true of this.tree.equals(obj.tree). For this distance function
      * this.distance(obj) == 0 implies that this.equals(obj) == true
      * @param obj
      *                Object to compare.
      * @return true if this == obj
      */
     public final boolean equals(final Object obj) {
         return tree.equals(obj);
     }
 
     /**
      * A hashCode based on the string representation of the tree.
      * @return a hash code of the string representation of this tree.
      */
     public final int hashCode() {
         return this.tree.hashCode();
     }
     
     /**
      * Calculates the distance between trees a and b. Used to validate the
      * distance implementation. Only to be executed in assert mode.
      * @param a
      *                The first tree (should be smaller than b)
      * @param b
      *                The second tree
      * @return The distance of the trees.
      */
     private final short distance(FragmentAST a, FragmentAST b) {
 
         List < FragmentAST > aExpanded = a.depthFirst();
         List < FragmentAST > bExpanded = b.depthFirst();
         List < FragmentAST > bExpanded2 = new LinkedList < FragmentAST >();
         bExpanded2.addAll(bExpanded);
         int Na = aExpanded.size() * 2;
         int Nb = bExpanded.size() * 2;
 
         ListIterator < FragmentAST > ait = aExpanded.listIterator();
         int res = 0;
         while (ait.hasNext()) {
             FragmentAST aTree = ait.next();
             ListIterator < FragmentAST > bit = bExpanded.listIterator();
             while (bit.hasNext()) {
                 FragmentAST bTree = bit.next();
                 if (aTree.equalsTree(bTree)) {
                     res++;
                     bit.remove();
                     break;
                 }
             }
             // do the same for the nodes without children
             bit = bExpanded2.listIterator();
             while (bit.hasNext()) {
                 FragmentAST bTree = bit.next();
                 if (aTree.getText().equals(bTree.getText())) {
                     res++;
                     bit.remove();
                     break;
                 }
             }
         }
         // return Na - res + Nb - res;
         // return (Na + Nb) - ( 2 * res);
         short r = (short) (((Na + Nb) - (2 * res)) / 2);
         assert r >= 0;
         return r;
     }
 
 }