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