jars/icu4j-4_4_2-src/main/tests/core/src/com/ibm/icu/dev/test/util/SortedBag.java

   1 /*\r
   2 **********************************************************************\r
   3 * Copyright (c) 2002-2006, International Business Machines\r
   4 * Corporation and others.  All Rights Reserved.\r
   5 **********************************************************************\r
   6 * Author: Mark Davis\r
   7 **********************************************************************\r
   8 */package com.ibm.icu.dev.test.util;\r
   9 \r
  10 import java.util.Collection;\r
  11 import java.util.Comparator;\r
  12 import java.util.HashSet;\r
  13 import java.util.Iterator;\r
  14 import java.util.Map;\r
  15 import java.util.Set;\r
  16 import java.util.TreeMap;\r
  17 \r
  18 /**\r
  19  * A collection that is like a sorted set, except that it allows\r
  20  * multiple elements that compare as equal\r
  21  * @author medavis\r
  22  */\r
  23 // TODO replace use of Set with a collection that takes an Equator\r
  24 public class SortedBag implements Collection {\r
  25     /**\r
  26      * A map of sets, where each corresponds to one sorted element.\r
  27      * The sets are never empty\r
  28      */\r
  29     private Map m;\r
  30     private int size;\r
  31 \r
  32     public SortedBag(Comparator c) {\r
  33         m = new TreeMap(c);\r
  34     }\r
  35     public boolean add(Object s) {\r
  36         Set o = (Set)m.get(s);\r
  37         if (o == null) {\r
  38             o = new HashSet(1);\r
  39             m.put(s,o);\r
  40         }\r
  41         boolean result = o.add(s);\r
  42         if (result) size++;\r
  43         return result;\r
  44     }\r
  45     public Iterator iterator() {\r
  46         return new MyIterator();\r
  47     }\r
  48     static Iterator EMPTY_ITERATOR = new HashSet().iterator();\r
  49     private class MyIterator implements Iterator {\r
  50         private Iterator mapIterator = m.keySet().iterator();\r
  51         private Iterator setIterator = null;\r
  52 \r
  53         private MyIterator() {\r
  54             mapIterator = m.keySet().iterator();\r
  55             setIterator = getSetIterator();\r
  56         }\r
  57         private Iterator getSetIterator() {\r
  58             if (!mapIterator.hasNext()) return EMPTY_ITERATOR;\r
  59             return ((Set)m.get(mapIterator.next())).iterator();\r
  60         }\r
  61         public boolean hasNext() {\r
  62             return setIterator.hasNext() || mapIterator.hasNext();\r
  63         }\r
  64         public Object next() {\r
  65             if (!setIterator.hasNext()) {\r
  66                 setIterator = getSetIterator();\r
  67             }\r
  68             return setIterator.next();\r
  69         }\r
  70         public void remove() {\r
  71             throw new UnsupportedOperationException();\r
  72         }\r
  73     }\r
  74     /**\r
  75      *\r
  76      */\r
  77     public void clear() {\r
  78         m.clear();\r
  79     }\r
  80     public int size() {\r
  81         return size;\r
  82     }\r
  83     public boolean isEmpty() {\r
  84         return size == 0;\r
  85     }\r
  86     public boolean contains(Object o) {\r
  87         Set set = (Set)m.get(o);\r
  88         if (set == null) return false;\r
  89         return set.contains(o);\r
  90     }\r
  91     public Object[] toArray() {\r
  92         return toArray(new Object[size]);\r
  93     }\r
  94     public Object[] toArray(Object[] a) {\r
  95         int count = 0;\r
  96         for (Iterator it = iterator(); it.hasNext();) {\r
  97             a[count++] = it.next();\r
  98         }\r
  99         return a;\r
 100     }\r
 101     /* (non-Javadoc)\r
 102      * @see java.util.Collection#remove(java.lang.Object)\r
 103      */\r
 104     public boolean remove(Object o) {\r
 105         Set set = (Set)m.get(o);\r
 106         if (set == null) return false;\r
 107         if (!set.remove(o)) return false;\r
 108         if (set.size() == 0) m.remove(o);\r
 109         size--;\r
 110         return true;\r
 111     }\r
 112     public boolean containsAll(Collection c) {\r
 113         for (Iterator it = c.iterator(); it.hasNext(); ) {\r
 114             if (!contains(it.next())) return false;\r
 115         }\r
 116         return true;\r
 117     }\r
 118     public boolean addAll(Collection c) {\r
 119         boolean result = false;\r
 120         for (Iterator it = c.iterator(); it.hasNext(); ) {\r
 121             if (add(it.next())) result = true;\r
 122         }\r
 123         return result;\r
 124     }\r
 125     public boolean removeAll(Collection c) {\r
 126         boolean result = false;\r
 127         for (Iterator it = c.iterator(); it.hasNext(); ) {\r
 128             if (remove(it.next())) result = true;\r
 129         }\r
 130         return result;\r
 131     }\r
 132     public boolean retainAll(Collection c) {\r
 133         // WARNING: this may not work if the comparator does not distinguish\r
 134         // all items that are equals().\r
 135         Set stuffToRemove = new HashSet(); // have to do this since iterator may not allow removal!\r
 136         for (Iterator it = iterator(); it.hasNext(); ) {\r
 137             Object item = it.next();\r
 138             if (!c.contains(item)) stuffToRemove.add(item);\r
 139         }\r
 140         return removeAll(stuffToRemove);\r
 141     }\r
 142 }\r