CollectionDiffUtil


1   
2   /*
3    * Copyright (c) 1998 - 2005 Versant Corporation
4    * All rights reserved. This program and the accompanying materials
5    * are made available under the terms of the Eclipse Public License v1.0
6    * which accompanies this distribution, and is available at
7    * http://www.eclipse.org/legal/epl-v10.html
8    *
9    * Contributors:
10   * Versant Corporation - initial API and implementation
11   */
12  package com.versant.core.jdo.sco;
13  
14  import com.versant.core.common.Debug;
15  import com.versant.core.jdo.VersantPersistenceManagerImp;
16  import com.versant.core.common.*;
17  import com.versant.core.util.Quicksort;
18  
19  import javax.jdo.spi.PersistenceCapable;
20  import java.util.Collection  ;
21  import java.util.Comparator  ;
22  import java.util.Iterator  ;
23  
24  import com.versant.core.common.BindingSupportImpl;
25  import com.versant.core.common.OID;
26  import com.versant.core.common.OrderedCollectionDiff;
27  import com.versant.core.common.UnorderedCollectionDiff;
28  import com.versant.core.metadata.FieldMetaData;
29  
30  /**
31   * This is an utility class used by SCO collection and lists to calculate diffs.
32   */
33  public class CollectionDiffUtil {
34  
35      /**
36       * Compares objects based on their hashcodes. This is used to sort arrays
37       * of objects that are not comparable.
38       */
39      private static class HashcodeComparator implements Comparator   {
40  
41          public int compare(Object   o1, Object   o2) {
42              int a = o1.hashCode();
43              int b = o2.hashCode();
44              if (a < b) return -1;
45              if (a > b) return +1;
46              if (o1.equals(o2)) return 0;
47              return -1;
48          }
49      }
50  
51      private static final HashcodeComparator HC_COMP = new HashcodeComparator();
52  
53      /**
54       * This builds an CollectionDiff for an ordered Collection. If the
55       * collection consists of PC instances then the before array must contain
56       * OIDs and the data array PC instances.
57       */
58      public static OrderedCollectionDiff getOrderedCollectionDiff(
59              VersantFieldMetaData fmd,
60              PersistenceContext pm, Object  [] data, int size,
61              Object  [] before) {
62  
63          OrderedCollectionDiff diff = new OrderedCollectionDiff(fmd);
64  
65          int beforeLen = fmd.isIncludeAllDataInDiff()
66                  ? 0
67                  : before == null ? 0 : before.length;
68  
69          // ignore nulls at the end of before
70  //        for (; beforeLen > 0 && before[beforeLen - 1] == null; --beforeLen) ;
71  
72          if (beforeLen == 0) {
73  
74              // everything is inserted
75              diff.insertedValues = new Object  [size];
76              if (fmd.isElementTypePC()) {
77                  Object  [] a = diff.insertedValues;
78                  for (int i = 0; i < size; i++) {
79                      a[i] = pm.getInternalOID((PersistenceCapable)data[i]);
80                  }
81              } else {
82                  System.arraycopy(data, 0, diff.insertedValues, 0, size);
83              }
84              diff.insertedIndexes = new int[size];
85              for (int i = 0; i < size; i++) diff.insertedIndexes[i] = i;
86  
87          } else if (size == 0) {
88  
89              // everything is deleted
90              diff.status = CollectionDiff.STATUS_NEW;
91  
92          } else {
93              int[] insertedIndexes = new int[size];
94              Object  [] insertedValues = new Object  [size];
95              int[] deletedIndexes = new int[beforeLen];
96  
97              int deletedSize;
98              int n = beforeLen < size ? beforeLen : size;
99              int pos = 0;
100 
101             if (fmd.isElementTypePC()) {
102                 // PC instances must be converted into OIDs before comparing.
103                 for (int i = 0; i < n; i++) {
104                     Object   a = pm.getInternalOID((PersistenceCapable)data[i]);
105                     Object   b = pm.getInternalOID((PersistenceCapable)before[i]);
106                     if (!equal(a, b)) {
107                         deletedIndexes[pos] = i;
108                         insertedIndexes[pos] = i;
109                         insertedValues[pos++] = a;
110                     }
111                 }
112                 deletedSize = pos;
113                 for (int i = beforeLen; i < size; i++) {
114                     insertedIndexes[pos] = i;
115                     insertedValues[pos++] =
116                             pm.getInternalOID((PersistenceCapable)data[i]);
117                 }
118             } else {
119                 for (int i = 0; i < n; i++) {
120                     if (!equal(data[i], before[i])) {
121                         deletedIndexes[pos] = i;
122                         insertedIndexes[pos] = i;
123                         insertedValues[pos++] = data[i];
124                     }
125                 }
126                 deletedSize = pos;
127                 for (int i = beforeLen; i < size; i++) {
128                     insertedIndexes[pos] = i;
129                     insertedValues[pos++] = data[i];
130                 }
131             }
132 
133             // delete any extra entries in before
134             for (int i = size; i < beforeLen; i++) {
135                 deletedIndexes[deletedSize++] = i;
136             }
137 
138             // Shrink arrays down to size. This can come out as soon as there
139             // are sizes in OrderedCollectionDiff.
140             diff.insertedIndexes = new int[pos];
141             if (pos > 0) {
142                 System.arraycopy(insertedIndexes, 0, diff.insertedIndexes, 0,
143                         pos);
144             }
145             diff.insertedValues = new Object  [pos];
146             if (pos > 0) {
147                 System.arraycopy(insertedValues, 0, diff.insertedValues, 0,
148                         pos);
149             }
150             diff.deletedIndexes = new int[deletedSize];
151             if (deletedSize > 0) {
152                 System.arraycopy(deletedIndexes, 0, diff.deletedIndexes, 0,
153                         deletedSize);
154             }
155         }
156 
157         if (Debug.DEBUG) {
158 //            System.out.println("*** CollectionDiffUtil.getOrderedCollectionDiff");
159 //            System.out.println(" fmd.getQName() = " + fmd.getQName());
160 //            System.out.println(" before = " +
161 //                    (fmd.isElementPC() ? toOIDString(pm, before) : toString(before)));
162 //            System.out.println(" data = " +
163 //                    (fmd.isElementPC() ? toOIDString(pm, data, size) : toString(data, size)));
164 //            System.out.println(" diff.deletedIndexes = " + toString(diff.deletedIndexes));
165 //            System.out.println(" diff.insertedIndexes = " + toString(diff.insertedIndexes));
166 //            System.out.println(" diff.insertedValues = " +
167 //                    (fmd.isElementPC() ? toOIDString(pm, diff.insertedValues) : toString(diff.insertedValues)));
168 //            System.out.println("---");
169 
170             // make sure there are no nulls in any of the arrays if pc
171             if (diff.insertedValues != null && fmd.isElementTypePC()
172                     && !((FieldMetaData)fmd).ordered) {
173                 for (int i = 0; i < diff.insertedValues.length; i++) {
174                     if (diff.insertedValues[i] == null) {
175                         throw BindingSupportImpl.getInstance().internal("diff.insertedValues[" + i + "] is null for " +
176                                 fmd.getQName());
177                     }
178                 }
179             }
180         }
181 
182         return diff;
183     }
184 
185     /**
186      * This builds an UnorderedCollectionDiff for an unordered Collection. If
187      * the collection consists of PC instances then the before array must
188      * contain OIDs and the data array PC instances.
189      */
190     public static UnorderedCollectionDiff getUnorderedCollectionDiff(
191             VersantFieldMetaData fmd, PersistenceContext pm,
192             Object  [] data, int size, Object  [] before) {
193         UnorderedCollectionDiff diff = new UnorderedCollectionDiff(fmd);
194 
195         int beforeLen = fmd.isIncludeAllDataInDiff()
196                 ? 0
197                 : before == null ? 0 : before.length;
198 
199         // ignore nulls at the end of before
200         for (; beforeLen > 0 && before[beforeLen - 1] == null; --beforeLen) ;
201 
202         if (beforeLen == 0) {
203             // everything is inserted
204             diff.insertedValues = new Object  [size];
205             if (fmd.isElementTypePC()) {
206                 Object  [] a = diff.insertedValues;
207                 for (int i = 0; i < size; i++) {
208                     a[i] = pm.getInternalOID((PersistenceCapable)data[i]);
209                 }
210             } else {
211                 System.arraycopy(data, 0, diff.insertedValues, 0, size);
212             }
213 
214         } else if (size == 0) {
215             // everything is deleted
216             diff.status = CollectionDiff.STATUS_NEW;
217             if (fmd.getInverseFieldMetaData() != null && fmd.getInverseFieldMetaData().isFake()) {
218                 diff.deletedValues = new Object  [beforeLen];
219                 if (fmd.isElementTypePC()) {
220                     for (int i = 0; i < beforeLen; i++) {
221                         diff.deletedValues[i] = pm.getInternalOID(
222                                 (PersistenceCapable)before[i]);
223                     }
224                 } else {
225                     System.arraycopy(before, 0, diff.deletedValues, 0,
226                             beforeLen);
227                 }
228             }
229         } else {
230             Object  [] inserted = new Object  [size];
231             int insertedCount = 0;
232             Object  [] deleted = new Object  [beforeLen];
233             int deletedCount = 0;
234 
235             // convert to OIDs if required
236             Object  [] sortedData;
237             Object  [] sortedBefore;
238             boolean pc = fmd.isElementTypePC();
239             if (pc) {
240                 sortedData = new Object  [size];
241                 for (int i = 0; i < size; i++) {
242                     sortedData[i] = pm.getInternalOID(
243                             (PersistenceCapable)data[i]);
244                 }
245                 sortedBefore = new Object  [beforeLen];
246                 for (int i = 0; i < beforeLen; i++) {
247                     sortedBefore[i] = pm.getInternalOID(
248                             (PersistenceCapable)before[i]);
249                 }
250             } else {
251                 sortedData = data;
252                 sortedBefore = before;
253             }
254 
255             // sort the arrays
256             if (pc || Comparable  .class.isAssignableFrom(fmd.getElementType())) {
257                 Quicksort.quicksort(sortedData, size);
258                 Quicksort.quicksort(sortedBefore, beforeLen);
259             } else {
260                 // The elements are not comparable so use a Comparator that
261                 // orders them based on HashCode. We do not allow duplicates
262                 // in unsorted collections so this method is ok.
263                 Quicksort.quicksort(sortedData, size, HC_COMP);
264                 Quicksort.quicksort(sortedBefore, beforeLen, HC_COMP);
265             }
266 
267             // find differences between the sorted arrays
268             int newPos = 0;
269             int oldPos = 0;
270             Object   nw = sortedData[0];
271             Object   old = sortedBefore[0];
272             for (; ;) {
273                 int c = ((Comparable  )nw).compareTo(old);
274                 if (c == 0) {
275                     ++newPos;
276                     ++oldPos; // must inc both so cannot do inc in test
277                     if (newPos == size || oldPos == beforeLen) break;
278                     nw = sortedData[newPos];
279                     old = sortedBefore[oldPos];
280                 } else if (c < 0) { // inserted element
281                     inserted[insertedCount++] = nw;
282                     if (++newPos == size) break;
283                     nw = sortedData[newPos];
284                 } else {
285                     deleted[deletedCount++] = old;
286                     if (++oldPos == beforeLen) break;
287                     old = sortedBefore[oldPos];
288                 }
289             }
290 
291             // copy in elements from side that was still going
292             int n = size - newPos;
293             if (n > 0) {
294                 System.arraycopy(sortedData, newPos, inserted, insertedCount,
295                         n);
296                 insertedCount += n;
297             }
298             if ((n = beforeLen - oldPos) > 0) {
299                 System.arraycopy(sortedBefore, oldPos, deleted, deletedCount,
300                         n);
301                 deletedCount += n;
302             }
303 
304             // Shrink arrays down to size. This can come out as soon as there
305             // are sizes in UnorderedCollectionDiff.
306             diff.insertedValues = new Object  [insertedCount];
307             System.arraycopy(inserted, 0, diff.insertedValues, 0,
308                     insertedCount);
309             diff.deletedValues = new Object  [deletedCount];
310             System.arraycopy(deleted, 0, diff.deletedValues, 0, deletedCount);
311         }
312 
313         if (Debug.DEBUG) {
314 //            System.out.println("*** CollectionDiffUtil.getUnorderedCollectionDiff");
315 //            System.out.println(" fmd.getQName() = " + fmd.getQName());
316 //            System.out.println(" before = " +
317 //                    (fmd.isElementPC() ? toOIDString(pm, before) : toString(before)));
318 //            System.out.println(" data = " +
319 //                    (fmd.isElementPC() ? toOIDString(pm, data, size) : toString(data, size)));
320 //            System.out.println(" diff.deletedValues = " +
321 //                    (fmd.isElementPC() ? toOIDString(pm, diff.deletedValues) : toString(diff.deletedValues)));
322 //            System.out.println(" diff.insertedValues = " +
323 //                    (fmd.isElementPC() ? toOIDString(pm, diff.insertedValues) : toString(diff.insertedValues)));
324 //            System.out.println("---");
325 
326             // make sure there are no nulls in any of the arrays
327             if (diff.insertedValues != null) {
328                 for (int i = 0; i < diff.insertedValues.length; i++) {
329                     if (diff.insertedValues[i] == null) {
330                         throw BindingSupportImpl.getInstance().internal("diff.insertedValues[" + i + "] is null for " +
331                                 fmd.getQName());
332                     }
333                 }
334             }
335             if (diff.deletedValues != null) {
336                 for (int i = 0; i < diff.deletedValues.length; i++) {
337                     if (diff.deletedValues[i] == null) {
338                         throw BindingSupportImpl.getInstance().internal("diff.deletedValues[" + i + "] is null for " +
339                                 fmd.getQName());
340                     }
341                 }
342             }
343         }
344 
345         return diff;
346     }
347 
348     private static void dump(Object  [] a) {
349         if (Debug.DEBUG) {
350             if (a == null) {
351                 System.out.println("null");
352             } else {
353                 for (int i = 0; i < a.length; i++) {
354                     System.out.println("[" + i + "] = " + a[i]);
355                 }
356                 System.out.println("-");
357             }
358         }
359     }
360 
361     /**
362      * Compare a and b for equality. Considers null == null to be true.
363      */
364     private static boolean equal(Object   a, Object   b) {
365         if (a == null) {
366             return b == null;
367         } else if (b == null) {
368             return false;
369         } else {
370             return a.equals(b);
371         }
372     }
373 
374     /**
375      * Create a diff for a new non-SCO collection field.
376      */
377     public static CollectionDiff getNonSCOCollectionDiff(Collection   c,
378             PersistenceContext sm, VersantFieldMetaData fmd) {
379         if (Debug.DEBUG) {
380             if (c instanceof VersantSimpleSCO) {
381                 throw BindingSupportImpl.getInstance().internal("getNonSCOCollectionDiff called for SCO collection: " +
382                         fmd.getQName() + " " + c);
383             }
384         }
385         int size = c.size();
386         boolean pc = fmd.isElementTypePC();
387         if (fmd.isOrdered()) {
388             OrderedCollectionDiff diff = new OrderedCollectionDiff(fmd);
389             int[] ia = new int[size];
390             diff.insertedIndexes = ia;
391             if (pc) {
392                 OID[] a = new OID[size];
393                 diff.insertedValues = a;
394                 int pos = 0;
395                 for (Iterator   i = c.iterator(); i.hasNext();) {
396                     ia[pos] = pos;
397                     a[pos++] = sm.getInternalOID((PersistenceCapable)i.next());
398                 }
399             } else {
400                 diff.insertedValues = c.toArray();
401                 for (int i = 0; i < size; i++) ia[i] = i;
402             }
403             diff.status = CollectionDiff.STATUS_NEW;
404             return diff;
405         } else {
406             UnorderedCollectionDiff diff = new UnorderedCollectionDiff(fmd);
407             if (pc) {
408                 OID[] a = new OID[size];
409                 diff.insertedValues = a;
410                 int pos = 0;
411                 for (Iterator   i = c.iterator(); i.hasNext();) {
412                     a[pos++] = sm.getInternalOID((PersistenceCapable)i.next());
413                 }
414             } else {
415                 diff.insertedValues = c.toArray();
416             }
417             diff.status = CollectionDiff.STATUS_NEW;
418             return diff;
419         }
420     }
421 
422     private static String   toString(Object  [] a) {
423         return toString(a, a == null ? 0 : a.length);
424     }
425 
426     private static String   toString(Object  [] a, int len) {
427         StringBuffer   s = new StringBuffer  ();
428         if (a == null) {
429             s.append("null");
430         } else {
431             s.append("[");
432             for (int i = 0; i < len; i++) {
433                 if (i > 0) s.append(", ");
434                 s.append(a[i]);
435             }
436             s.append("]");
437         }
438         return s.toString();
439     }
440 
441     private static String   toOIDString(VersantPersistenceManagerImp pm,
442             Object  [] a) {
443         return toOIDString(pm, a, a == null ? 0 : a.length);
444     }
445 
446     private static String   toOIDString(VersantPersistenceManagerImp pm,
447             Object  [] a, int len) {
448         StringBuffer   s = new StringBuffer  ();
449         if (a == null) {
450             s.append("null");
451         } else {
452             s.append("[");
453             for (int i = 0; i < len; i++) {
454                 if (i > 0) s.append(", ");
455                 Object   o = a[i];
456                 if (o instanceof OID) {
457                     s.append(o);
458                 } else {
459                     s.append("PC:" + pm.getInternalOID((PersistenceCapable)o));
460                 }
461             }
462             s.append("]");
463         }
464         return s.toString();
465     }
466 
467     private static String   toString(int[] a) {
468         return toString(a, a == null ? 0 : a.length);
469     }
470 
471     private static String   toString(int[] a, int len) {
472         StringBuffer   s = new StringBuffer  ();
473         if (a == null) {
474             s.append("null");
475         } else {
476             s.append("[");
477             for (int i = 0; i < len; i++) {
478                 if (i > 0) s.append(", ");
479                 s.append(a[i]);
480             }
481             s.append("]");
482         }
483         return s.toString();
484     }
485 
486 }
487
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags