jars/icu4j-52_1/main/classes/core/src/com/ibm/icu/impl/SortedSetRelation.java

   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 }