jars/icu4j-4_4_2-src/main/classes/core/src/com/ibm/icu/impl/SortedSetRelation.java

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