View Javadoc

1   package org.kit.furia.fragment;
2   
3   import java.util.LinkedList;
4   import java.util.List;
5   import java.util.ListIterator;
6   
7   import org.kit.furia.misc.IntegerHolder;
8   
9   import antlr.collections.AST;
10  
11  /*
12   Furia-chan: An Open Source software license violation detector.    
13   Copyright (C) 2008 Kyushu Institute of Technology
14  
15   This program is free software: you can redistribute it and/or modify
16   it under the terms of the GNU General Public License as published by
17   the Free Software Foundation, either version 3 of the License, or
18   (at your option) any later version.
19  
20   This program is distributed in the hope that it will be useful,
21   but WITHOUT ANY WARRANTY; without even the implied warranty of
22   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23   GNU General Public License for more details.
24  
25   You should have received a copy of the GNU General Public License
26   along with this program.  If not, see <http://www.gnu.org/licenses/>.
27   */
28  
29  /**
30   * MTDFragmentAST A tree that holds an internal id for each unique complete
31   * subtree and a hash code computed on the string representation of this
32   * complete subtree. Additionally, the number of repetitions is included. This
33   * helps to make this algorithm O(n) for equal complete subtrees of two
34   * different trees. Once we found that two complete subtrees m,j belonging to
35   * different trees T1 T2, we can compute their intersection in linear time.
36   * @author Arnoldo Jose Muller Molina
37   */
38  public class MTDFragmentAST
39          extends FragmentAST {
40  
41      int hashCode = -1;
42  
43      public int id = -1;
44  
45      public IntegerHolder repetitions;
46  
47      public void update() {
48          super.updateDecendantInformation();
49          hashCode = super.toStringTree().hashCode();
50      }
51  
52      public boolean equals(AST x) {
53          return equals((Object) x);
54      }
55  
56      public int hashCode() {
57          return hashCode;
58      }
59  
60      public boolean equals(Object o) {
61          MTDFragmentAST other = (MTDFragmentAST) o;
62          boolean res = fequalsTree(other);
63          assert res == this.toStringTree().equals(other.toStringTree());
64          return res;
65      }
66  
67      private boolean fequalsTree(MTDFragmentAST other) {
68  
69          if (other == null 
70                  || this.hashCode != other.hashCode
71                  || this.decendants != other.decendants
72                  || !this.text.equals(other.text)) {
73              return false;
74          }
75  
76          if (this.getLeft() != null) {
77              return this.getLeft().fequalsTreeAux(other.getLeft());
78          } else if (this.getLeft() == null && other.getLeft() == null) {
79              return true;
80          } else {
81              return false;
82          }
83      }
84  
85      private boolean fequalsTreeAux(MTDFragmentAST other) {
86          if (other == null) {
87              return false;
88          }
89          if (!this.text.equals(other.text)) {
90              return false;
91          }
92  
93          boolean res = true;
94          MTDFragmentAST left = this.getLeft();
95          if (left != null) {
96              res = left.fequalsTreeAux(other.getLeft());
97          }
98          if (res) {
99              MTDFragmentAST sib = this.getSibbling();
100             if (sib != null) {
101                 res = sib.fequalsTreeAux(other.getSibbling());
102             }
103         }
104         return res;
105     }
106 
107     public MTDFragmentAST getLeft() {
108         return (MTDFragmentAST) this.getFirstChild();
109     }
110 
111     public MTDFragmentAST getSibbling() {
112         return (MTDFragmentAST) this.getNextSibling();
113     }
114 
115     
116 
117 }