jars/icu4j-52_1/main/tests/framework/src/com/ibm/icu/dev/util/SortedBag.java

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