1 /* 2 ********************************************************************** 3 * Copyright (c) 2002-2010, International Business Machines 4 * Corporation and others. All Rights Reserved. 5 ********************************************************************** 6 * Author: M. Davis 7 * Created: December 2002 (moved from UnicodeSet) 8 * Since: ICU 2.4 9 ********************************************************************** 10 */ 11 package com.ibm.icu.impl; 12 13 import java.util.Iterator; 14 import java.util.SortedSet; 15 import java.util.TreeSet; 16 17 /** 18 * Computationally efficient determination of the relationship between 19 * two SortedSets. 20 */ 21 public class SortedSetRelation { 22 23 /** 24 * The relationship between two sets A and B can be determined by looking at: 25 * A - B 26 * A & B (intersection) 27 * B - A 28 * These are represented by a set of bits. 29 * Bit 2 is true if A - B is not empty 30 * Bit 1 is true if A & B is not empty 31 * BIT 0 is true if B - A is not empty 32 */ 33 public static final int 34 A_NOT_B = 4, 35 A_AND_B = 2, 36 B_NOT_A = 1; 37 38 /** 39 * There are 8 combinations of the relationship bits. These correspond to 40 * the filters (combinations of allowed bits) in hasRelation. They also 41 * correspond to the modification functions, listed in comments. 42 */ 43 public static final int 44 ANY = A_NOT_B | A_AND_B | B_NOT_A, // union, addAll 45 CONTAINS = A_NOT_B | A_AND_B, // A (unnecessary) 46 DISJOINT = A_NOT_B | B_NOT_A, // A xor B, missing Java function 47 ISCONTAINED = A_AND_B | B_NOT_A, // B (unnecessary) 48 NO_B = A_NOT_B, // A setDiff B, removeAll 49 EQUALS = A_AND_B, // A intersect B, retainAll 50 NO_A = B_NOT_A, // B setDiff A, removeAll 51 NONE = 0, // null (unnecessary) 52 53 ADDALL = ANY, // union, addAll 54 A = CONTAINS, // A (unnecessary) 55 COMPLEMENTALL = DISJOINT, // A xor B, missing Java function 56 B = ISCONTAINED, // B (unnecessary) 57 REMOVEALL = NO_B, // A setDiff B, removeAll 58 RETAINALL = EQUALS, // A intersect B, retainAll 59 B_REMOVEALL = NO_A; // B setDiff A, removeAll 60 61 62 /** 63 * Utility that could be on SortedSet. Faster implementation than 64 * what is in Java for doing contains, equals, etc. 65 * @param a first set 66 * @param allow filter, using ANY, CONTAINS, etc. 67 * @param b second set 68 * @return whether the filter relationship is true or not. 69 */ 70 public static <T extends Object & Comparable<? super T>> boolean hasRelation(SortedSet<T> a, int allow, SortedSet<T> b) { 71 if (allow < NONE || allow > ANY) { 72 throw new IllegalArgumentException("Relation " + allow + " out of range"); 73 } 74 75 // extract filter conditions 76 // these are the ALLOWED conditions Set 77 78 boolean anb = (allow & A_NOT_B) != 0; 79 boolean ab = (allow & A_AND_B) != 0; 80 boolean bna = (allow & B_NOT_A) != 0; 81 82 // quick check on sizes 83 switch(allow) { 84 case CONTAINS: if (a.size() < b.size()) return false; break; 85 case ISCONTAINED: if (a.size() > b.size()) return false; break; 86 case EQUALS: if (a.size() != b.size()) return false; break; 87 } 88 89 // check for null sets 90 if (a.size() == 0) { 91 if (b.size() == 0) return true; 92 return bna; 93 } else if (b.size() == 0) { 94 return anb; 95 } 96 97 // pick up first strings, and start comparing 98 Iterator<? extends T> ait = a.iterator(); 99 Iterator<? extends T> bit = b.iterator(); 100 101 T aa = ait.next(); 102 T bb = bit.next(); 103 104 while (true) { 105 int comp = aa.compareTo(bb); 106 if (comp == 0) { 107 if (!ab) return false; 108 if (!ait.hasNext()) { 109 if (!bit.hasNext()) return true; 110 return bna; 111 } else if (!bit.hasNext()) { 112 return anb; 113 } 114 aa = ait.next(); 115 bb = bit.next(); 116 } else if (comp < 0) { 117 if (!anb) return false; 118 if (!ait.hasNext()) { 119 return bna; 120 } 121 aa = ait.next(); 122 } else { 123 if (!bna) return false; 124 if (!bit.hasNext()) { 125 return anb; 126 } 127 bb = bit.next(); 128 } 129 } 130 } 131 132 /** 133 * Utility that could be on SortedSet. Allows faster implementation than 134 * what is in Java for doing addAll, removeAll, retainAll, (complementAll). 135 * @param a first set 136 * @param relation the relation filter, using ANY, CONTAINS, etc. 137 * @param b second set 138 * @return the new set 139 */ 140 public static <T extends Object & Comparable<? super T>> SortedSet<? extends T> doOperation(SortedSet<T> a, int relation, SortedSet<T> b) { 141 // TODO: optimize this as above 142 TreeSet<? extends T> temp; 143 switch (relation) { 144 case ADDALL: 145 a.addAll(b); 146 return a; 147 case A: 148 return a; // no action 149 case B: 150 a.clear(); 151 a.addAll(b); 152 return a; 153 case REMOVEALL: 154 a.removeAll(b); 155 return a; 156 case RETAINALL: 157 a.retainAll(b); 158 return a; 159 // the following is the only case not really supported by Java 160 // although all could be optimized 161 case COMPLEMENTALL: 162 temp = new TreeSet<T>(b); 163 temp.removeAll(a); 164 a.removeAll(b); 165 a.addAll(temp); 166 return a; 167 case B_REMOVEALL: 168 temp = new TreeSet<T>(b); 169 temp.removeAll(a); 170 a.clear(); 171 a.addAll(temp); 172 return a; 173 case NONE: 174 a.clear(); 175 return a; 176 default: 177 throw new IllegalArgumentException("Relation " + relation + " out of range"); 178 } 179 } 180 } 181
