001: //##header
002: /*
003: *******************************************************************************
004: * Copyright (C) 1996-2006, International Business Machines Corporation and *
005: * others. All Rights Reserved. *
006: *******************************************************************************
007: */
008: //#ifndef FOUNDATION
009: package com.ibm.icu.dev.test.util;
010:
011: import java.util.Collection;
012: import java.util.Comparator;
013: import java.util.HashMap;
014: import java.util.Iterator;
015: import java.util.Map;
016: import java.util.Set;
017: import java.util.SortedSet;
018: import java.util.TreeSet;
019: import java.util.regex.Matcher;
020:
021: import com.ibm.icu.impl.UCharacterProperty;
022: import com.ibm.icu.lang.UCharacter;
023: import com.ibm.icu.text.UTF16;
024: import com.ibm.icu.text.UnicodeSet;
025: import com.ibm.icu.text.UnicodeSetIterator;
026:
027: /**
028: * Utilities that ought to be on collections, but aren't
029: */
030: public final class CollectionUtilities {
031: /**
032: * Utility like Arrays.asList()
033: */
034: public static Map asMap(Object[][] source, Map target,
035: boolean reverse) {
036: int from = 0, to = 1;
037: if (reverse) {
038: from = 1;
039: to = 0;
040: }
041: for (int i = 0; i < source.length; ++i) {
042: target.put(source[i][from], source[i][to]);
043: }
044: return target;
045: }
046:
047: public static Collection addAll(Iterator source, Collection target) {
048: while (source.hasNext()) {
049: target.add(source.next());
050: }
051: return target; // for chaining
052: }
053:
054: public static int size(Iterator source) {
055: int result = 0;
056: while (source.hasNext()) {
057: source.next();
058: ++result;
059: }
060: return result;
061: }
062:
063: public static Map asMap(Object[][] source) {
064: return asMap(source, new HashMap(), false);
065: }
066:
067: /**
068: * Utility that ought to be on Map
069: */
070: public static Map removeAll(Map m, Collection itemsToRemove) {
071: for (Iterator it = itemsToRemove.iterator(); it.hasNext();) {
072: Object item = it.next();
073: m.remove(item);
074: }
075: return m;
076: }
077:
078: public Object getFirst(Collection c) {
079: Iterator it = c.iterator();
080: if (!it.hasNext())
081: return null;
082: return it.next();
083: }
084:
085: public static Object getBest(Collection c, Comparator comp,
086: int direction) {
087: Iterator it = c.iterator();
088: if (!it.hasNext())
089: return null;
090: Object bestSoFar = it.next();
091: while (it.hasNext()) {
092: Object item = it.next();
093: if (comp.compare(item, bestSoFar) == direction) {
094: bestSoFar = item;
095: }
096: }
097: return bestSoFar;
098: }
099:
100: public interface Filter {
101: boolean matches(Object o);
102: }
103:
104: public static Collection removeAll(Collection c, Filter f) {
105: for (Iterator it = c.iterator(); it.hasNext();) {
106: Object item = it.next();
107: if (f.matches(item))
108: it.remove();
109: }
110: return c;
111: }
112:
113: public static Collection retainAll(Collection c, Filter f) {
114: for (Iterator it = c.iterator(); it.hasNext();) {
115: Object item = it.next();
116: if (!f.matches(item))
117: it.remove();
118: }
119: return c;
120: }
121:
122: public static boolean containsSome(Collection a, Collection b) {
123: // fast paths
124: if (a.size() == 0 || b.size() == 0)
125: return false;
126: if (a == b)
127: return true; // must test after size test.
128:
129: if (a instanceof SortedSet && b instanceof SortedSet) {
130: SortedSet aa = (SortedSet) a;
131: SortedSet bb = (SortedSet) b;
132: aa.containsAll(null);
133: Comparator bbc = bb.comparator();
134: Comparator aac = aa.comparator();
135: if (bbc == null) {
136: if (aac == null) {
137: Iterator ai = aa.iterator();
138: Iterator bi = bb.iterator();
139: Comparable ao = (Comparable) ai.next(); // these are ok, since the sizes are != 0
140: Comparable bo = (Comparable) bi.next();
141: while (true) {
142: int rel = ao.compareTo(bo);
143: if (rel < 0) {
144: if (!ai.hasNext())
145: return false;
146: ao = (Comparable) ai.next();
147: } else if (rel > 0) {
148: if (!bi.hasNext())
149: return false;
150: bo = (Comparable) bi.next();
151: } else {
152: return true;
153: }
154: }
155: }
156: } else if (bbc.equals(a)) {
157: Iterator ai = aa.iterator();
158: Iterator bi = bb.iterator();
159: Object ao = ai.next(); // these are ok, since the sizes are != 0
160: Object bo = bi.next();
161: while (true) {
162: int rel = aac.compare(ao, bo);
163: if (rel < 0) {
164: if (!ai.hasNext())
165: return false;
166: ao = ai.next();
167: } else if (rel > 0) {
168: if (!bi.hasNext())
169: return false;
170: bo = bi.next();
171: } else {
172: return true;
173: }
174: }
175: }
176: }
177: for (Iterator it = a.iterator(); it.hasNext();) {
178: if (b.contains(it.next()))
179: return true;
180: }
181: return false;
182: }
183:
184: public static boolean containsAll(Collection a, Collection b) {
185: // fast paths
186: if (a == b)
187: return true;
188: if (b.size() == 0)
189: return true;
190: if (a.size() == 0)
191: return false;
192:
193: if (a instanceof SortedSet && b instanceof SortedSet) {
194: SortedSet aa = (SortedSet) a;
195: SortedSet bb = (SortedSet) b;
196: Comparator bbc = bb.comparator();
197: Comparator aac = aa.comparator();
198: if (bbc == null) {
199: if (aac == null) {
200: Iterator ai = aa.iterator();
201: Iterator bi = bb.iterator();
202: Comparable ao = (Comparable) ai.next(); // these are ok, since the sizes are != 0
203: Comparable bo = (Comparable) bi.next();
204: while (true) {
205: int rel = ao.compareTo(bo);
206: if (rel == 0) {
207: if (!bi.hasNext())
208: return true;
209: if (!ai.hasNext())
210: return false;
211: bo = (Comparable) bi.next();
212: ao = (Comparable) ai.next();
213: } else if (rel < 0) {
214: if (!ai.hasNext())
215: return false;
216: ao = (Comparable) ai.next();
217: } else {
218: return false;
219: }
220: }
221: }
222: } else if (bbc.equals(a)) {
223: Iterator ai = aa.iterator();
224: Iterator bi = bb.iterator();
225: Object ao = ai.next(); // these are ok, since the sizes are != 0
226: Object bo = bi.next();
227: while (true) {
228: int rel = aac.compare(ao, bo);
229: if (rel == 0) {
230: if (!bi.hasNext())
231: return true;
232: if (!ai.hasNext())
233: return false;
234: bo = bi.next();
235: ao = ai.next();
236: } else if (rel < 0) {
237: if (!ai.hasNext())
238: return false;
239: ao = ai.next();
240: } else {
241: return false;
242: }
243: }
244: }
245: }
246: return a.containsAll(b);
247: }
248:
249: public static boolean containsNone(Collection a, Collection b) {
250: return !containsSome(a, b);
251: }
252:
253: /**
254: * Used for results of getContainmentRelation
255: */
256: public static final int ALL_EMPTY = 0, NOT_A_SUPERSET_B = 1,
257: NOT_A_DISJOINT_B = 2, NOT_A_SUBSET_B = 4,
258: NOT_A_EQUALS_B = NOT_A_SUBSET_B | NOT_A_SUPERSET_B,
259: A_PROPER_SUBSET_OF_B = NOT_A_DISJOINT_B | NOT_A_SUPERSET_B,
260: A_PROPER_SUPERSET_B = NOT_A_SUBSET_B | NOT_A_DISJOINT_B,
261: A_PROPER_OVERLAPS_B = NOT_A_SUBSET_B | NOT_A_DISJOINT_B
262: | NOT_A_SUPERSET_B;
263:
264: /**
265: * Assesses all the possible containment relations between collections A and B with one call.<br>
266: * Returns an int with bits set, according to a "Venn Diagram" view of A vs B.<br>
267: * NOT_A_SUPERSET_B: a - b != {}<br>
268: * NOT_A_DISJOINT_B: a * b != {} // * is intersects<br>
269: * NOT_A_SUBSET_B: b - a != {}<br>
270: * Thus the bits can be used to get the following relations:<br>
271: * for A_SUPERSET_B, use (x & CollectionUtilities.NOT_A_SUPERSET_B) == 0<br>
272: * for A_SUBSET_B, use (x & CollectionUtilities.NOT_A_SUBSET_B) == 0<br>
273: * for A_EQUALS_B, use (x & CollectionUtilities.NOT_A_EQUALS_B) == 0<br>
274: * for A_DISJOINT_B, use (x & CollectionUtilities.NOT_A_DISJOINT_B) == 0<br>
275: * for A_OVERLAPS_B, use (x & CollectionUtilities.NOT_A_DISJOINT_B) != 0<br>
276: */
277: public static int getContainmentRelation(Collection a, Collection b) {
278: if (a.size() == 0) {
279: return (b.size() == 0) ? ALL_EMPTY : NOT_A_SUPERSET_B;
280: } else if (b.size() == 0) {
281: return NOT_A_SUBSET_B;
282: }
283: int result = 0;
284: // WARNING: one might think that the following can be short-circuited, by looking at
285: // the sizes of a and b. However, this would fail in general, where a different comparator is being
286: // used in the two collections. Unfortunately, there is no failsafe way to test for that.
287: for (Iterator it = a.iterator(); result != 6 && it.hasNext();) {
288: result |= (b.contains(it.next())) ? NOT_A_DISJOINT_B
289: : NOT_A_SUBSET_B;
290: }
291: for (Iterator it = b.iterator(); (result & 3) != 3
292: && it.hasNext();) {
293: result |= (a.contains(it.next())) ? NOT_A_DISJOINT_B
294: : NOT_A_SUPERSET_B;
295: }
296: return result;
297: }
298:
299: public static String remove(String source, UnicodeSet removals) {
300: StringBuffer result = new StringBuffer();
301: int cp;
302: for (int i = 0; i < source.length(); i += UTF16
303: .getCharCount(cp)) {
304: cp = UTF16.charAt(source, i);
305: if (!removals.contains(cp))
306: UTF16.append(result, cp);
307: }
308: return result.toString();
309: }
310:
311: public static String prettyPrint(UnicodeSet uset, Comparator comp,
312: Comparator spaceComparator, boolean compressRanges) {
313: Appender result = new Appender(compressRanges, spaceComparator);
314: // make sure that comparison separates all strings, even canonically equivalent ones
315: Comparator comp2 = new MultiComparator(new Comparator[] { comp,
316: new UTF16.StringComparator(true, false, 0) });
317: Set ordering = new TreeSet(comp2);
318: for (UnicodeSetIterator it = new UnicodeSetIterator(uset); it
319: .next();) {
320: ordering.add(it.getString());
321: }
322: result.append("[");
323: for (Iterator it = ordering.iterator(); it.hasNext();) {
324: result.appendUnicodeSetItem((String) it.next());
325: }
326: result.flushLast();
327: result.append("]");
328: String sresult = result.toString();
329: UnicodeSet doubleCheck = new UnicodeSet(sresult);
330: if (!uset.equals(doubleCheck)) {
331: throw new IllegalStateException(
332: "Failure to round-trip in pretty-print");
333: }
334: return sresult;
335: }
336:
337: private static class Appender {
338: private boolean first = true;
339: private StringBuffer target = new StringBuffer();
340: private int firstCodePoint = -2;
341: private int lastCodePoint = -2;
342: private boolean compressRanges;
343: private Comparator spaceComp;
344: private String lastString = "";
345:
346: public Appender(boolean compressRanges, Comparator spaceComp) {
347: this .compressRanges = compressRanges;
348: this .spaceComp = spaceComp;
349: }
350:
351: Appender appendUnicodeSetItem(String s) {
352: int cp;
353: if (UTF16.hasMoreCodePointsThan(s, 1)) {
354: flushLast();
355: addSpace(s);
356: target.append("{");
357: for (int i = 0; i < s.length(); i += UTF16
358: .getCharCount(cp)) {
359: appendQuoted(cp = UTF16.charAt(s, i));
360: }
361: target.append("}");
362: lastString = s;
363: } else {
364: if (!compressRanges)
365: flushLast();
366: cp = UTF16.charAt(s, 0);
367: if (cp == lastCodePoint + 1) {
368: lastCodePoint = cp; // continue range
369: } else { // start range
370: flushLast();
371: firstCodePoint = lastCodePoint = cp;
372: }
373: }
374: return this ;
375: }
376:
377: /**
378: *
379: */
380: private void addSpace(String s) {
381: if (first) {
382: first = false;
383: } else if (spaceComp.compare(s, lastString) != 0) {
384: target.append(' ');
385: } else {
386: int type = UCharacter.getType(UTF16.charAt(s, 0));
387: if (type == UCharacter.NON_SPACING_MARK
388: || type == UCharacter.ENCLOSING_MARK) {
389: target.append(' ');
390: }
391: }
392: }
393:
394: private void flushLast() {
395: if (lastCodePoint >= 0) {
396: addSpace(UTF16.valueOf(firstCodePoint));
397: if (firstCodePoint != lastCodePoint) {
398: appendQuoted(firstCodePoint);
399: target
400: .append(firstCodePoint + 1 == lastCodePoint ? ' '
401: : '-');
402: }
403: appendQuoted(lastCodePoint);
404: lastString = UTF16.valueOf(lastCodePoint);
405: firstCodePoint = lastCodePoint = -2;
406: }
407: }
408:
409: Appender appendQuoted(int codePoint) {
410: switch (codePoint) {
411: case '[': // SET_OPEN:
412: case ']': // SET_CLOSE:
413: case '-': // HYPHEN:
414: case '^': // COMPLEMENT:
415: case '&': // INTERSECTION:
416: case '\\': //BACKSLASH:
417: case '{':
418: case '}':
419: case '$':
420: case ':':
421: target.append('\\');
422: break;
423: default:
424: // Escape whitespace
425: if (UCharacterProperty.isRuleWhiteSpace(codePoint)) {
426: target.append('\\');
427: }
428: break;
429: }
430: UTF16.append(target, codePoint);
431: return this ;
432: }
433:
434: Appender append(String s) {
435: target.append(s);
436: return this ;
437: }
438:
439: public String toString() {
440: return target.toString();
441: }
442: }
443:
444: static class MultiComparator implements Comparator {
445: private Comparator[] comparators;
446:
447: public MultiComparator(Comparator[] comparators) {
448: this .comparators = comparators;
449: }
450:
451: /* Lexigraphic compare. Returns the first difference
452: * @return zero if equal. Otherwise +/- (i+1)
453: * where i is the index of the first comparator finding a difference
454: * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
455: */
456: public int compare(Object arg0, Object arg1) {
457: for (int i = 0; i < comparators.length; ++i) {
458: int result = comparators[i].compare(arg0, arg1);
459: if (result == 0)
460: continue;
461: if (result > 0)
462: return i + 1;
463: return -(i + 1);
464: }
465: return 0;
466: }
467: }
468:
469: /**
470: * Modifies Unicode set to flatten the strings. Eg [abc{da}] => [abcd]
471: * Returns the set for chaining.
472: * @param exemplar1
473: * @return
474: */
475: public static UnicodeSet flatten(UnicodeSet exemplar1) {
476: UnicodeSet result = new UnicodeSet();
477: boolean gotString = false;
478: for (UnicodeSetIterator it = new UnicodeSetIterator(exemplar1); it
479: .nextRange();) {
480: if (it.codepoint == it.IS_STRING) {
481: result.addAll(it.string);
482: gotString = true;
483: } else {
484: result.add(it.codepoint, it.codepointEnd);
485: }
486: }
487: if (gotString)
488: exemplar1.set(result);
489: return exemplar1;
490: }
491:
492: /**
493: * For producing filtered iterators
494: */
495: public static abstract class FilteredIterator implements Iterator {
496: private Iterator baseIterator;
497: private static final Object EMPTY = new Object();
498: private static final Object DONE = new Object();
499: private Object nextObject = EMPTY;
500:
501: public FilteredIterator set(Iterator baseIterator) {
502: this .baseIterator = baseIterator;
503: return this ;
504: }
505:
506: public void remove() {
507: throw new UnsupportedOperationException(
508: "Doesn't support removal");
509: }
510:
511: public Object next() {
512: Object result = nextObject;
513: nextObject = EMPTY;
514: return result;
515: }
516:
517: public boolean hasNext() {
518: if (nextObject == DONE)
519: return false;
520: if (nextObject != EMPTY)
521: return true;
522: while (baseIterator.hasNext()) {
523: nextObject = baseIterator.next();
524: if (isIncluded(nextObject)) {
525: return true;
526: }
527: }
528: nextObject = DONE;
529: return false;
530: }
531:
532: abstract public boolean isIncluded(Object item);
533: }
534:
535: public static class PrefixIterator extends FilteredIterator {
536: private String prefix;
537:
538: public PrefixIterator set(Iterator baseIterator, String prefix) {
539: super .set(baseIterator);
540: this .prefix = prefix;
541: return this ;
542: }
543:
544: public boolean isIncluded(Object item) {
545: return ((String) item).startsWith(prefix);
546: }
547: }
548:
549: public static class RegexIterator extends FilteredIterator {
550: private Matcher matcher;
551:
552: public RegexIterator set(Iterator baseIterator, Matcher matcher) {
553: super .set(baseIterator);
554: this .matcher = matcher;
555: return this ;
556: }
557:
558: public boolean isIncluded(Object item) {
559: return matcher.reset((String) item).matches();
560: }
561: }
562:
563: }
564: //#endif
|