ArrayDiff


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  
20  package org.netbeans.swing.tabcontrol.event;
21  
22  import org.netbeans.swing.tabcontrol.TabData;
23  
24  import java.util.*;
25  
26  /*
27   * ArrayDiff.java
28   *
29   * Created on November 5, 2003, 12:44 PM
30   */
31  
32  /**
33   * Class representing a diff of two arrays.  Note that it is
34   * <strong>not</strong> designed to work with arrays which contain the same
35   * element more than one time - in that case, the results are undefined.
36   * <p/>
37   * <p>Note the current implementation is unoptimized and fairly brute force.
38   *
39   * @author Tim Boudreau
40   */
41  public final class ArrayDiff {
42      /**
43       * The old array
44       */
45      private TabData[] old;
46      /**
47       * The new array
48       */
49      private TabData[] nue;
50      
51      //XXX all of this could be implemented more efficiently with a single
52      //loop to calculate all statistics and so forth.  The approach is algorithmically
53      //inelegant and brute force. To do that would significantly
54      //increase the complexity of the code, but it could be done later as an
55      //optimization
56      
57      /**
58       * Creates a new instance of ArrayDiff
59       */
60      private ArrayDiff(TabData[] old, TabData[] nue) {
61          this.old = old;
62          this.nue = nue;
63          if (nue == null || old == null) {
64              throw new NullPointerException  (old == null && nue == null ?
65                                             "Both arrays are null" :
66                                             old == null ?
67                                             "Old array is null" :
68                                             "New array is null");
69          }
70      }
71  
72      /**
73       * Get the array representing the old state
74       */
75      public TabData[] getOldData() {
76          return old;
77      }
78  
79      /**
80       * Get the array representing the new state
81       */
82      public TabData[] getNewData() {
83          return nue;
84      }
85  
86      /**
87       * Returns an ArrayDiff object if the two arrays are not the same, or null
88       * if they are
89       */
90      public static ArrayDiff createDiff(TabData[] old, TabData[] nue) {
91          if (!Arrays.equals(old, nue)) {
92              return new ArrayDiff(old, nue);
93          } else {
94              return null;
95          }
96      }
97  
98      private Set<Integer  > deleted = null;
99  
100     /**
101      * Returns the indices of objects in the old array which are not present in
102      * the new array.  The resulting array's size will be that of the old array
103      */
104     public Set<Integer  > getDeletedIndices() {
105         if (deleted == null) {
106             HashSet<TabData> set = new HashSet<TabData>(Arrays.asList(nue));
107             HashSet<Integer  > results = new HashSet<Integer  >(old.length);
108             for (int i = 0; i < old.length; i++) {
109                 if (!set.contains(old[i])) {
110                     results.add(new Integer  (i));
111                 }
112             }
113             deleted = results;
114         }
115         return deleted;
116     }
117 
118     private Set<Integer  > added = null;
119 
120     /**
121      * Returns the indices of objects in the new array which are not present in
122      * the old array
123      */
124     public Set<Integer  > getAddedIndices() {
125         if (added == null) {
126             HashSet<TabData> set = new HashSet<TabData>(Arrays.asList(old));
127             Set<Integer  > results = new HashSet<Integer  >(nue.length);
128             for (int i = 0; i < nue.length; i++) {
129                 if (!set.contains(nue[i])) {
130                     results.add(new Integer  (i));
131                 }
132             }
133             added = results;
134         }
135         return added;
136     }
137 
138     /**
139      * Returns the indices of objects which differ in any way between the new
140      * and old array.  The size of the result is Math.max(old.length,
141      * nue.length).
142      */
143     public Set<Integer  > getChangedIndices() {
144         //XXX can add similar caching as with deleted/added fields if it looks
145         //to prove useful.  getDeletedIndices() and getAddedIndices() are called
146         //more than once, and the computation can be expensive.
147         int max = Math.max(nue.length, old.length);
148         HashSet<Integer  > results = new HashSet<Integer  >(max);
149 
150         for (int i = 0; i < max; i++) {
151             if (i < old.length && i < nue.length) {
152                 if (!old[i].equals(nue[i])) {
153                     results.add(new Integer  (i));
154                 }
155             } else {
156                 results.add(new Integer  (i));
157             }
158         }
159         return results;
160     }
161 
162     /**
163      * Returns the indices of objects which were in the old array and are also
164      * in the new array, but at a different index.  The indices returned are
165      * indices into the old array.
166      */
167     public Set<Integer  > getMovedIndices() {
168         HashSet<TabData> set = new HashSet<TabData>(Arrays.asList(nue));
169         HashSet<Integer  > results = new HashSet<Integer  >(old.length);
170 
171         for (int i = 0; i < old.length; i++) {
172             boolean isPresent = set.contains(old[i]);
173             if (isPresent) {
174                 boolean isMoved = (i < nue.length
175                         && !nue[i].equals(old[i])) || i >= nue.length;
176                 if (isMoved) {
177                     results.add(new Integer  (i));
178                 }
179             }
180         }
181         return results;
182     }
183 
184     public String   toString() {
185         StringBuffer   sb = new StringBuffer  ();
186         sb.append("<ArrayDiff: deleted indices: [");
187         sb.append(outCol(getDeletedIndices()));
188         sb.append("] added indices: [");
189         sb.append(outCol(getAddedIndices()));
190         sb.append("] changed indices: [");
191         sb.append(outCol(getChangedIndices()));
192         sb.append("] moved indices: [");
193         sb.append(outCol(getChangedIndices()));
194         sb.append("]>");
195         return sb.toString();
196     }
197 
198     private static String   outCol(Collection c) {
199         Iterator i = c.iterator();
200         StringBuffer   result = new StringBuffer  ();
201         while (i.hasNext()) {
202             Object   o = i.next();
203             result.append(o.toString());
204             if (i.hasNext()) {
205                 result.append(",");
206             }
207         }
208         return result.toString();
209     }
210 
211     public boolean equals(Object   o) {
212         if (o instanceof ArrayDiff) {
213             if (o == this) {
214                 return true;
215             }
216             TabData[] otherOld = ((ArrayDiff) o).getOldData();
217             TabData[] otherNue = ((ArrayDiff) o).getNewData();
218             return Arrays.equals(old, otherOld)
219                     && Arrays.equals(nue, otherNue);
220         }
221         return false;
222     }
223 
224     public int hashCode() {
225         return arrayHashCode(old) ^ arrayHashCode(nue);
226     }
227 
228     private static int arrayHashCode(Object  [] o) {
229         int result = 0;
230         for (int i = 0; i < o.length; i++) {
231             result += o[i].hashCode() ^ i;
232         }
233         return result;
234     }
235 }
236
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags