001: /*
002: **********************************************************************
003: * Copyright (c) 2002-2004, International Business Machines
004: * Corporation and others. All Rights Reserved.
005: **********************************************************************
006: * Author: M. Davis
007: * Created: December 2002 (moved from UnicodeSet)
008: * Since: ICU 2.4
009: **********************************************************************
010: */
011: package com.ibm.icu.impl;
012:
013: import java.util.SortedSet;
014: import java.util.Iterator;
015: import java.util.TreeSet;
016:
017: /**
018: * Computationally efficient determination of the relationship between
019: * two SortedSets.
020: */
021: public class SortedSetRelation {
022:
023: /**
024: * The relationship between two sets A and B can be determined by looking at:
025: * A - B
026: * A & B (intersection)
027: * B - A
028: * These are represented by a set of bits.
029: * Bit 2 is true if A - B is not empty
030: * Bit 1 is true if A & B is not empty
031: * BIT 0 is true if B - A is not empty
032: */
033: public static final int A_NOT_B = 4, A_AND_B = 2, B_NOT_A = 1;
034:
035: /**
036: * There are 8 combinations of the relationship bits. These correspond to
037: * the filters (combinations of allowed bits) in hasRelation. They also
038: * correspond to the modification functions, listed in comments.
039: */
040: public static final int ANY = A_NOT_B | A_AND_B | B_NOT_A, // union, addAll
041: CONTAINS = A_NOT_B | A_AND_B, // A (unnecessary)
042: DISJOINT = A_NOT_B | B_NOT_A, // A xor B, missing Java function
043: ISCONTAINED = A_AND_B | B_NOT_A, // B (unnecessary)
044: NO_B = A_NOT_B, // A setDiff B, removeAll
045: EQUALS = A_AND_B, // A intersect B, retainAll
046: NO_A = B_NOT_A, // B setDiff A, removeAll
047: NONE = 0, // null (unnecessary)
048:
049: ADDALL = ANY, // union, addAll
050: A = CONTAINS, // A (unnecessary)
051: COMPLEMENTALL = DISJOINT, // A xor B, missing Java function
052: B = ISCONTAINED, // B (unnecessary)
053: REMOVEALL = NO_B, // A setDiff B, removeAll
054: RETAINALL = EQUALS, // A intersect B, retainAll
055: B_REMOVEALL = NO_A; // B setDiff A, removeAll
056:
057: /**
058: * Utility that could be on SortedSet. Faster implementation than
059: * what is in Java for doing contains, equals, etc.
060: * @param a first set
061: * @param allow filter, using ANY, CONTAINS, etc.
062: * @param b second set
063: * @return whether the filter relationship is true or not.
064: */
065: public static boolean hasRelation(SortedSet a, int allow,
066: SortedSet b) {
067: if (allow < NONE || allow > ANY) {
068: throw new IllegalArgumentException("Relation " + allow
069: + " out of range");
070: }
071:
072: // extract filter conditions
073: // these are the ALLOWED conditions Set
074:
075: boolean anb = (allow & A_NOT_B) != 0;
076: boolean ab = (allow & A_AND_B) != 0;
077: boolean bna = (allow & B_NOT_A) != 0;
078:
079: // quick check on sizes
080: switch (allow) {
081: case CONTAINS:
082: if (a.size() < b.size())
083: return false;
084: break;
085: case ISCONTAINED:
086: if (a.size() > b.size())
087: return false;
088: break;
089: case EQUALS:
090: if (a.size() != b.size())
091: return false;
092: break;
093: }
094:
095: // check for null sets
096: if (a.size() == 0) {
097: if (b.size() == 0)
098: return true;
099: return bna;
100: } else if (b.size() == 0) {
101: return anb;
102: }
103:
104: // pick up first strings, and start comparing
105: Iterator ait = a.iterator();
106: Iterator bit = b.iterator();
107:
108: Comparable aa = (Comparable) ait.next();
109: Comparable bb = (Comparable) bit.next();
110:
111: while (true) {
112: int comp = aa.compareTo(bb);
113: if (comp == 0) {
114: if (!ab)
115: return false;
116: if (!ait.hasNext()) {
117: if (!bit.hasNext())
118: return true;
119: return bna;
120: } else if (!bit.hasNext()) {
121: return anb;
122: }
123: aa = (Comparable) ait.next();
124: bb = (Comparable) bit.next();
125: } else if (comp < 0) {
126: if (!anb)
127: return false;
128: if (!ait.hasNext()) {
129: return bna;
130: }
131: aa = (Comparable) ait.next();
132: } else {
133: if (!bna)
134: return false;
135: if (!bit.hasNext()) {
136: return anb;
137: }
138: bb = (Comparable) bit.next();
139: }
140: }
141: }
142:
143: /**
144: * Utility that could be on SortedSet. Allows faster implementation than
145: * what is in Java for doing addAll, removeAll, retainAll, (complementAll).
146: * @param a first set
147: * @param relation the relation filter, using ANY, CONTAINS, etc.
148: * @param b second set
149: * @return the new set
150: */
151: public static SortedSet doOperation(SortedSet a, int relation,
152: SortedSet b) {
153: // TODO: optimize this as above
154: TreeSet temp;
155: switch (relation) {
156: case ADDALL:
157: a.addAll(b);
158: return a;
159: case A:
160: return a; // no action
161: case B:
162: a.clear();
163: a.addAll(b);
164: return a;
165: case REMOVEALL:
166: a.removeAll(b);
167: return a;
168: case RETAINALL:
169: a.retainAll(b);
170: return a;
171: // the following is the only case not really supported by Java
172: // although all could be optimized
173: case COMPLEMENTALL:
174: temp = new TreeSet(b);
175: temp.removeAll(a);
176: a.removeAll(b);
177: a.addAll(temp);
178: return a;
179: case B_REMOVEALL:
180: temp = new TreeSet(b);
181: temp.removeAll(a);
182: a.clear();
183: a.addAll(temp);
184: return a;
185: case NONE:
186: a.clear();
187: return a;
188: default:
189: throw new IllegalArgumentException("Relation " + relation
190: + " out of range");
191: }
192: }
193: }
|