SortedSetRelation


1   /*
2   **********************************************************************
3   * Copyright (c) 2002-2004, 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.SortedSet  ;
14  import java.util.Iterator  ;
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 boolean hasRelation(SortedSet   a, int allow, SortedSet   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   ait = a.iterator();
99          Iterator   bit = b.iterator();
100         
101         Comparable   aa = (Comparable  ) ait.next();
102         Comparable   bb = (Comparable  ) 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 = (Comparable  ) ait.next();
115                 bb = (Comparable  ) bit.next();
116             } else if (comp < 0) {
117                 if (!anb) return false;
118                 if (!ait.hasNext()) {
119                     return bna;
120                 }
121                 aa = (Comparable  ) ait.next(); 
122             } else  {
123                 if (!bna) return false;
124                 if (!bit.hasNext()) {
125                     return anb;
126                 }
127                 bb = (Comparable  ) 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 SortedSet   doOperation(SortedSet   a, int relation, SortedSet   b) {
141         // TODO: optimize this as above
142         TreeSet   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  (b);
163                 temp.removeAll(a);
164                 a.removeAll(b);
165                 a.addAll(temp);
166                 return a;
167             case B_REMOVEALL:
168                 temp = new TreeSet  (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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags