001: /*
002: * Copyright (c) 1998 - 2005 Versant Corporation
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * Versant Corporation - initial API and implementation
010: */
011: package com.versant.core.jdo.sco;
012:
013: import com.versant.core.common.Debug;
014: import com.versant.core.jdo.VersantPersistenceManagerImp;
015: import com.versant.core.common.*;
016: import com.versant.core.util.Quicksort;
017:
018: import javax.jdo.spi.PersistenceCapable;
019: import java.util.Collection;
020: import java.util.Comparator;
021: import java.util.Iterator;
022:
023: import com.versant.core.common.BindingSupportImpl;
024: import com.versant.core.common.OID;
025: import com.versant.core.common.OrderedCollectionDiff;
026: import com.versant.core.common.UnorderedCollectionDiff;
027: import com.versant.core.metadata.FieldMetaData;
028:
029: /**
030: * This is an utility class used by SCO collection and lists to calculate diffs.
031: */
032: public class CollectionDiffUtil {
033:
034: /**
035: * Compares objects based on their hashcodes. This is used to sort arrays
036: * of objects that are not comparable.
037: */
038: private static class HashcodeComparator implements Comparator {
039:
040: public int compare(Object o1, Object o2) {
041: int a = o1.hashCode();
042: int b = o2.hashCode();
043: if (a < b)
044: return -1;
045: if (a > b)
046: return +1;
047: if (o1.equals(o2))
048: return 0;
049: return -1;
050: }
051: }
052:
053: private static final HashcodeComparator HC_COMP = new HashcodeComparator();
054:
055: /**
056: * This builds an CollectionDiff for an ordered Collection. If the
057: * collection consists of PC instances then the before array must contain
058: * OIDs and the data array PC instances.
059: */
060: public static OrderedCollectionDiff getOrderedCollectionDiff(
061: VersantFieldMetaData fmd, PersistenceContext pm,
062: Object[] data, int size, Object[] before) {
063:
064: OrderedCollectionDiff diff = new OrderedCollectionDiff(fmd);
065:
066: int beforeLen = fmd.isIncludeAllDataInDiff() ? 0
067: : before == null ? 0 : before.length;
068:
069: // ignore nulls at the end of before
070: // for (; beforeLen > 0 && before[beforeLen - 1] == null; --beforeLen) ;
071:
072: if (beforeLen == 0) {
073:
074: // everything is inserted
075: diff.insertedValues = new Object[size];
076: if (fmd.isElementTypePC()) {
077: Object[] a = diff.insertedValues;
078: for (int i = 0; i < size; i++) {
079: a[i] = pm
080: .getInternalOID((PersistenceCapable) data[i]);
081: }
082: } else {
083: System.arraycopy(data, 0, diff.insertedValues, 0, size);
084: }
085: diff.insertedIndexes = new int[size];
086: for (int i = 0; i < size; i++)
087: diff.insertedIndexes[i] = i;
088:
089: } else if (size == 0) {
090:
091: // everything is deleted
092: diff.status = CollectionDiff.STATUS_NEW;
093:
094: } else {
095: int[] insertedIndexes = new int[size];
096: Object[] insertedValues = new Object[size];
097: int[] deletedIndexes = new int[beforeLen];
098:
099: int deletedSize;
100: int n = beforeLen < size ? beforeLen : size;
101: int pos = 0;
102:
103: if (fmd.isElementTypePC()) {
104: // PC instances must be converted into OIDs before comparing.
105: for (int i = 0; i < n; i++) {
106: Object a = pm
107: .getInternalOID((PersistenceCapable) data[i]);
108: Object b = pm
109: .getInternalOID((PersistenceCapable) before[i]);
110: if (!equal(a, b)) {
111: deletedIndexes[pos] = i;
112: insertedIndexes[pos] = i;
113: insertedValues[pos++] = a;
114: }
115: }
116: deletedSize = pos;
117: for (int i = beforeLen; i < size; i++) {
118: insertedIndexes[pos] = i;
119: insertedValues[pos++] = pm
120: .getInternalOID((PersistenceCapable) data[i]);
121: }
122: } else {
123: for (int i = 0; i < n; i++) {
124: if (!equal(data[i], before[i])) {
125: deletedIndexes[pos] = i;
126: insertedIndexes[pos] = i;
127: insertedValues[pos++] = data[i];
128: }
129: }
130: deletedSize = pos;
131: for (int i = beforeLen; i < size; i++) {
132: insertedIndexes[pos] = i;
133: insertedValues[pos++] = data[i];
134: }
135: }
136:
137: // delete any extra entries in before
138: for (int i = size; i < beforeLen; i++) {
139: deletedIndexes[deletedSize++] = i;
140: }
141:
142: // Shrink arrays down to size. This can come out as soon as there
143: // are sizes in OrderedCollectionDiff.
144: diff.insertedIndexes = new int[pos];
145: if (pos > 0) {
146: System.arraycopy(insertedIndexes, 0,
147: diff.insertedIndexes, 0, pos);
148: }
149: diff.insertedValues = new Object[pos];
150: if (pos > 0) {
151: System.arraycopy(insertedValues, 0,
152: diff.insertedValues, 0, pos);
153: }
154: diff.deletedIndexes = new int[deletedSize];
155: if (deletedSize > 0) {
156: System.arraycopy(deletedIndexes, 0,
157: diff.deletedIndexes, 0, deletedSize);
158: }
159: }
160:
161: if (Debug.DEBUG) {
162: // System.out.println("*** CollectionDiffUtil.getOrderedCollectionDiff");
163: // System.out.println(" fmd.getQName() = " + fmd.getQName());
164: // System.out.println(" before = " +
165: // (fmd.isElementPC() ? toOIDString(pm, before) : toString(before)));
166: // System.out.println(" data = " +
167: // (fmd.isElementPC() ? toOIDString(pm, data, size) : toString(data, size)));
168: // System.out.println(" diff.deletedIndexes = " + toString(diff.deletedIndexes));
169: // System.out.println(" diff.insertedIndexes = " + toString(diff.insertedIndexes));
170: // System.out.println(" diff.insertedValues = " +
171: // (fmd.isElementPC() ? toOIDString(pm, diff.insertedValues) : toString(diff.insertedValues)));
172: // System.out.println("---");
173:
174: // make sure there are no nulls in any of the arrays if pc
175: if (diff.insertedValues != null && fmd.isElementTypePC()
176: && !((FieldMetaData) fmd).ordered) {
177: for (int i = 0; i < diff.insertedValues.length; i++) {
178: if (diff.insertedValues[i] == null) {
179: throw BindingSupportImpl.getInstance()
180: .internal(
181: "diff.insertedValues[" + i
182: + "] is null for "
183: + fmd.getQName());
184: }
185: }
186: }
187: }
188:
189: return diff;
190: }
191:
192: /**
193: * This builds an UnorderedCollectionDiff for an unordered Collection. If
194: * the collection consists of PC instances then the before array must
195: * contain OIDs and the data array PC instances.
196: */
197: public static UnorderedCollectionDiff getUnorderedCollectionDiff(
198: VersantFieldMetaData fmd, PersistenceContext pm,
199: Object[] data, int size, Object[] before) {
200: UnorderedCollectionDiff diff = new UnorderedCollectionDiff(fmd);
201:
202: int beforeLen = fmd.isIncludeAllDataInDiff() ? 0
203: : before == null ? 0 : before.length;
204:
205: // ignore nulls at the end of before
206: for (; beforeLen > 0 && before[beforeLen - 1] == null; --beforeLen)
207: ;
208:
209: if (beforeLen == 0) {
210: // everything is inserted
211: diff.insertedValues = new Object[size];
212: if (fmd.isElementTypePC()) {
213: Object[] a = diff.insertedValues;
214: for (int i = 0; i < size; i++) {
215: a[i] = pm
216: .getInternalOID((PersistenceCapable) data[i]);
217: }
218: } else {
219: System.arraycopy(data, 0, diff.insertedValues, 0, size);
220: }
221:
222: } else if (size == 0) {
223: // everything is deleted
224: diff.status = CollectionDiff.STATUS_NEW;
225: if (fmd.getInverseFieldMetaData() != null
226: && fmd.getInverseFieldMetaData().isFake()) {
227: diff.deletedValues = new Object[beforeLen];
228: if (fmd.isElementTypePC()) {
229: for (int i = 0; i < beforeLen; i++) {
230: diff.deletedValues[i] = pm
231: .getInternalOID((PersistenceCapable) before[i]);
232: }
233: } else {
234: System.arraycopy(before, 0, diff.deletedValues, 0,
235: beforeLen);
236: }
237: }
238: } else {
239: Object[] inserted = new Object[size];
240: int insertedCount = 0;
241: Object[] deleted = new Object[beforeLen];
242: int deletedCount = 0;
243:
244: // convert to OIDs if required
245: Object[] sortedData;
246: Object[] sortedBefore;
247: boolean pc = fmd.isElementTypePC();
248: if (pc) {
249: sortedData = new Object[size];
250: for (int i = 0; i < size; i++) {
251: sortedData[i] = pm
252: .getInternalOID((PersistenceCapable) data[i]);
253: }
254: sortedBefore = new Object[beforeLen];
255: for (int i = 0; i < beforeLen; i++) {
256: sortedBefore[i] = pm
257: .getInternalOID((PersistenceCapable) before[i]);
258: }
259: } else {
260: sortedData = data;
261: sortedBefore = before;
262: }
263:
264: // sort the arrays
265: if (pc
266: || Comparable.class.isAssignableFrom(fmd
267: .getElementType())) {
268: Quicksort.quicksort(sortedData, size);
269: Quicksort.quicksort(sortedBefore, beforeLen);
270: } else {
271: // The elements are not comparable so use a Comparator that
272: // orders them based on HashCode. We do not allow duplicates
273: // in unsorted collections so this method is ok.
274: Quicksort.quicksort(sortedData, size, HC_COMP);
275: Quicksort.quicksort(sortedBefore, beforeLen, HC_COMP);
276: }
277:
278: // find differences between the sorted arrays
279: int newPos = 0;
280: int oldPos = 0;
281: Object nw = sortedData[0];
282: Object old = sortedBefore[0];
283: for (;;) {
284: int c = ((Comparable) nw).compareTo(old);
285: if (c == 0) {
286: ++newPos;
287: ++oldPos; // must inc both so cannot do inc in test
288: if (newPos == size || oldPos == beforeLen)
289: break;
290: nw = sortedData[newPos];
291: old = sortedBefore[oldPos];
292: } else if (c < 0) { // inserted element
293: inserted[insertedCount++] = nw;
294: if (++newPos == size)
295: break;
296: nw = sortedData[newPos];
297: } else {
298: deleted[deletedCount++] = old;
299: if (++oldPos == beforeLen)
300: break;
301: old = sortedBefore[oldPos];
302: }
303: }
304:
305: // copy in elements from side that was still going
306: int n = size - newPos;
307: if (n > 0) {
308: System.arraycopy(sortedData, newPos, inserted,
309: insertedCount, n);
310: insertedCount += n;
311: }
312: if ((n = beforeLen - oldPos) > 0) {
313: System.arraycopy(sortedBefore, oldPos, deleted,
314: deletedCount, n);
315: deletedCount += n;
316: }
317:
318: // Shrink arrays down to size. This can come out as soon as there
319: // are sizes in UnorderedCollectionDiff.
320: diff.insertedValues = new Object[insertedCount];
321: System.arraycopy(inserted, 0, diff.insertedValues, 0,
322: insertedCount);
323: diff.deletedValues = new Object[deletedCount];
324: System.arraycopy(deleted, 0, diff.deletedValues, 0,
325: deletedCount);
326: }
327:
328: if (Debug.DEBUG) {
329: // System.out.println("*** CollectionDiffUtil.getUnorderedCollectionDiff");
330: // System.out.println(" fmd.getQName() = " + fmd.getQName());
331: // System.out.println(" before = " +
332: // (fmd.isElementPC() ? toOIDString(pm, before) : toString(before)));
333: // System.out.println(" data = " +
334: // (fmd.isElementPC() ? toOIDString(pm, data, size) : toString(data, size)));
335: // System.out.println(" diff.deletedValues = " +
336: // (fmd.isElementPC() ? toOIDString(pm, diff.deletedValues) : toString(diff.deletedValues)));
337: // System.out.println(" diff.insertedValues = " +
338: // (fmd.isElementPC() ? toOIDString(pm, diff.insertedValues) : toString(diff.insertedValues)));
339: // System.out.println("---");
340:
341: // make sure there are no nulls in any of the arrays
342: if (diff.insertedValues != null) {
343: for (int i = 0; i < diff.insertedValues.length; i++) {
344: if (diff.insertedValues[i] == null) {
345: throw BindingSupportImpl.getInstance()
346: .internal(
347: "diff.insertedValues[" + i
348: + "] is null for "
349: + fmd.getQName());
350: }
351: }
352: }
353: if (diff.deletedValues != null) {
354: for (int i = 0; i < diff.deletedValues.length; i++) {
355: if (diff.deletedValues[i] == null) {
356: throw BindingSupportImpl.getInstance()
357: .internal(
358: "diff.deletedValues[" + i
359: + "] is null for "
360: + fmd.getQName());
361: }
362: }
363: }
364: }
365:
366: return diff;
367: }
368:
369: private static void dump(Object[] a) {
370: if (Debug.DEBUG) {
371: if (a == null) {
372: System.out.println("null");
373: } else {
374: for (int i = 0; i < a.length; i++) {
375: System.out.println("[" + i + "] = " + a[i]);
376: }
377: System.out.println("-");
378: }
379: }
380: }
381:
382: /**
383: * Compare a and b for equality. Considers null == null to be true.
384: */
385: private static boolean equal(Object a, Object b) {
386: if (a == null) {
387: return b == null;
388: } else if (b == null) {
389: return false;
390: } else {
391: return a.equals(b);
392: }
393: }
394:
395: /**
396: * Create a diff for a new non-SCO collection field.
397: */
398: public static CollectionDiff getNonSCOCollectionDiff(Collection c,
399: PersistenceContext sm, VersantFieldMetaData fmd) {
400: if (Debug.DEBUG) {
401: if (c instanceof VersantSimpleSCO) {
402: throw BindingSupportImpl.getInstance().internal(
403: "getNonSCOCollectionDiff called for SCO collection: "
404: + fmd.getQName() + " " + c);
405: }
406: }
407: int size = c.size();
408: boolean pc = fmd.isElementTypePC();
409: if (fmd.isOrdered()) {
410: OrderedCollectionDiff diff = new OrderedCollectionDiff(fmd);
411: int[] ia = new int[size];
412: diff.insertedIndexes = ia;
413: if (pc) {
414: OID[] a = new OID[size];
415: diff.insertedValues = a;
416: int pos = 0;
417: for (Iterator i = c.iterator(); i.hasNext();) {
418: ia[pos] = pos;
419: a[pos++] = sm.getInternalOID((PersistenceCapable) i
420: .next());
421: }
422: } else {
423: diff.insertedValues = c.toArray();
424: for (int i = 0; i < size; i++)
425: ia[i] = i;
426: }
427: diff.status = CollectionDiff.STATUS_NEW;
428: return diff;
429: } else {
430: UnorderedCollectionDiff diff = new UnorderedCollectionDiff(
431: fmd);
432: if (pc) {
433: OID[] a = new OID[size];
434: diff.insertedValues = a;
435: int pos = 0;
436: for (Iterator i = c.iterator(); i.hasNext();) {
437: a[pos++] = sm.getInternalOID((PersistenceCapable) i
438: .next());
439: }
440: } else {
441: diff.insertedValues = c.toArray();
442: }
443: diff.status = CollectionDiff.STATUS_NEW;
444: return diff;
445: }
446: }
447:
448: private static String toString(Object[] a) {
449: return toString(a, a == null ? 0 : a.length);
450: }
451:
452: private static String toString(Object[] a, int len) {
453: StringBuffer s = new StringBuffer();
454: if (a == null) {
455: s.append("null");
456: } else {
457: s.append("[");
458: for (int i = 0; i < len; i++) {
459: if (i > 0)
460: s.append(", ");
461: s.append(a[i]);
462: }
463: s.append("]");
464: }
465: return s.toString();
466: }
467:
468: private static String toOIDString(VersantPersistenceManagerImp pm,
469: Object[] a) {
470: return toOIDString(pm, a, a == null ? 0 : a.length);
471: }
472:
473: private static String toOIDString(VersantPersistenceManagerImp pm,
474: Object[] a, int len) {
475: StringBuffer s = new StringBuffer();
476: if (a == null) {
477: s.append("null");
478: } else {
479: s.append("[");
480: for (int i = 0; i < len; i++) {
481: if (i > 0)
482: s.append(", ");
483: Object o = a[i];
484: if (o instanceof OID) {
485: s.append(o);
486: } else {
487: s
488: .append("PC:"
489: + pm
490: .getInternalOID((PersistenceCapable) o));
491: }
492: }
493: s.append("]");
494: }
495: return s.toString();
496: }
497:
498: private static String toString(int[] a) {
499: return toString(a, a == null ? 0 : a.length);
500: }
501:
502: private static String toString(int[] a, int len) {
503: StringBuffer s = new StringBuffer();
504: if (a == null) {
505: s.append("null");
506: } else {
507: s.append("[");
508: for (int i = 0; i < len; i++) {
509: if (i > 0)
510: s.append(", ");
511: s.append(a[i]);
512: }
513: s.append("]");
514: }
515: return s.toString();
516: }
517:
518: }
|