| /* |
| ********************************************************************** |
| * Copyright (c) 2002-2004, International Business Machines |
| * Corporation and others. All Rights Reserved. |
| ********************************************************************** |
| * Author: M. Davis |
| * Created: December 2002 (moved from UnicodeSet) |
| * Since: ICU 2.4 |
| ********************************************************************** |
| */ |
| package com.ibm.icu.impl; |
| |
| import java.util.SortedSet; |
| import java.util.Iterator; |
| import java.util.TreeSet; |
| |
| /** |
| * Computationally efficient determination of the relationship between |
| * two SortedSets. |
| */ |
| public class SortedSetRelation { |
| |
| /** |
| * The relationship between two sets A and B can be determined by looking at: |
| * A - B |
| * A & B (intersection) |
| * B - A |
| * These are represented by a set of bits. |
| * Bit 2 is true if A - B is not empty |
| * Bit 1 is true if A & B is not empty |
| * BIT 0 is true if B - A is not empty |
| */ |
| public static final int |
| A_NOT_B = 4, |
| A_AND_B = 2, |
| B_NOT_A = 1; |
| |
| /** |
| * There are 8 combinations of the relationship bits. These correspond to |
| * the filters (combinations of allowed bits) in hasRelation. They also |
| * correspond to the modification functions, listed in comments. |
| */ |
| public static final int |
| ANY = A_NOT_B | A_AND_B | B_NOT_A, // union, addAll |
| CONTAINS = A_NOT_B | A_AND_B, // A (unnecessary) |
| DISJOINT = A_NOT_B | B_NOT_A, // A xor B, missing Java function |
| ISCONTAINED = A_AND_B | B_NOT_A, // B (unnecessary) |
| NO_B = A_NOT_B, // A setDiff B, removeAll |
| EQUALS = A_AND_B, // A intersect B, retainAll |
| NO_A = B_NOT_A, // B setDiff A, removeAll |
| NONE = 0, // null (unnecessary) |
| |
| ADDALL = ANY, // union, addAll |
| A = CONTAINS, // A (unnecessary) |
| COMPLEMENTALL = DISJOINT, // A xor B, missing Java function |
| B = ISCONTAINED, // B (unnecessary) |
| REMOVEALL = NO_B, // A setDiff B, removeAll |
| RETAINALL = EQUALS, // A intersect B, retainAll |
| B_REMOVEALL = NO_A; // B setDiff A, removeAll |
| |
| |
| /** |
| * Utility that could be on SortedSet. Faster implementation than |
| * what is in Java for doing contains, equals, etc. |
| * @param a first set |
| * @param allow filter, using ANY, CONTAINS, etc. |
| * @param b second set |
| * @return whether the filter relationship is true or not. |
| */ |
| public static boolean hasRelation(SortedSet a, int allow, SortedSet b) { |
| if (allow < NONE || allow > ANY) { |
| throw new IllegalArgumentException("Relation " + allow + " out of range"); |
| } |
| |
| // extract filter conditions |
| // these are the ALLOWED conditions Set |
| |
| boolean anb = (allow & A_NOT_B) != 0; |
| boolean ab = (allow & A_AND_B) != 0; |
| boolean bna = (allow & B_NOT_A) != 0; |
| |
| // quick check on sizes |
| switch(allow) { |
| case CONTAINS: if (a.size() < b.size()) return false; break; |
| case ISCONTAINED: if (a.size() > b.size()) return false; break; |
| case EQUALS: if (a.size() != b.size()) return false; break; |
| } |
| |
| // check for null sets |
| if (a.size() == 0) { |
| if (b.size() == 0) return true; |
| return bna; |
| } else if (b.size() == 0) { |
| return anb; |
| } |
| |
| // pick up first strings, and start comparing |
| Iterator ait = a.iterator(); |
| Iterator bit = b.iterator(); |
| |
| Comparable aa = (Comparable) ait.next(); |
| Comparable bb = (Comparable) bit.next(); |
| |
| while (true) { |
| int comp = aa.compareTo(bb); |
| if (comp == 0) { |
| if (!ab) return false; |
| if (!ait.hasNext()) { |
| if (!bit.hasNext()) return true; |
| return bna; |
| } else if (!bit.hasNext()) { |
| return anb; |
| } |
| aa = (Comparable) ait.next(); |
| bb = (Comparable) bit.next(); |
| } else if (comp < 0) { |
| if (!anb) return false; |
| if (!ait.hasNext()) { |
| return bna; |
| } |
| aa = (Comparable) ait.next(); |
| } else { |
| if (!bna) return false; |
| if (!bit.hasNext()) { |
| return anb; |
| } |
| bb = (Comparable) bit.next(); |
| } |
| } |
| } |
| |
| /** |
| * Utility that could be on SortedSet. Allows faster implementation than |
| * what is in Java for doing addAll, removeAll, retainAll, (complementAll). |
| * @param a first set |
| * @param relation the relation filter, using ANY, CONTAINS, etc. |
| * @param b second set |
| * @return the new set |
| */ |
| public static SortedSet doOperation(SortedSet a, int relation, SortedSet b) { |
| // TODO: optimize this as above |
| TreeSet temp; |
| switch (relation) { |
| case ADDALL: |
| a.addAll(b); |
| return a; |
| case A: |
| return a; // no action |
| case B: |
| a.clear(); |
| a.addAll(b); |
| return a; |
| case REMOVEALL: |
| a.removeAll(b); |
| return a; |
| case RETAINALL: |
| a.retainAll(b); |
| return a; |
| // the following is the only case not really supported by Java |
| // although all could be optimized |
| case COMPLEMENTALL: |
| temp = new TreeSet(b); |
| temp.removeAll(a); |
| a.removeAll(b); |
| a.addAll(temp); |
| return a; |
| case B_REMOVEALL: |
| temp = new TreeSet(b); |
| temp.removeAll(a); |
| a.clear(); |
| a.addAll(temp); |
| return a; |
| case NONE: |
| a.clear(); |
| return a; |
| default: |
| throw new IllegalArgumentException("Relation " + relation + " out of range"); |
| } |
| } |
| } |