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