Coverage Report - com.sdmetrics.math.HashMultiSet - www.sdmetrics.com
 
Classes in this File Line Coverage Branch Coverage Complexity
HashMultiSet
100%
90/90
100%
40/40
2,773
HashMultiSet$HashMultiSetIterator
100%
25/25
100%
8/8
2,773
 
 1  
 /*
 2  
  * SDMetrics Open Core for UML design measurement
 3  
  * Copyright (c) Juergen Wuest
 4  
  * To contact the author, see <http://www.sdmetrics.com/Contact.html>.
 5  
  * 
 6  
  * This file is part of the SDMetrics Open Core.
 7  
  * 
 8  
  * SDMetrics Open Core is free software: you can redistribute it and/or modify
 9  
  * it under the terms of the GNU Affero General Public License as
 10  
  * published by the Free Software Foundation, either version 3 of the
 11  
  * License, or (at your option) any later version.
 12  
     
 13  
  * SDMetrics Open Core is distributed in the hope that it will be useful,
 14  
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 15  
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 16  
  * GNU Affero General Public License for more details.
 17  
  *
 18  
  * You should have received a copy of the GNU Affero General Public License
 19  
  * along with SDMetrics Open Core.  If not, see <http://www.gnu.org/licenses/>.
 20  
  *
 21  
  */
 22  
 package com.sdmetrics.math;
 23  
 
 24  
 import java.util.AbstractCollection;
 25  
 import java.util.Collection;
 26  
 import java.util.HashMap;
 27  
 import java.util.Iterator;
 28  
 import java.util.Map.Entry;
 29  
 import java.util.NoSuchElementException;
 30  
 
 31  
 /**
 32  
  * A hash set that can contain the same element multiple times. Such sets are
 33  
  * known as multisets or bags.
 34  
  * <p>
 35  
  * The number of times an element is contained in the multi set is called the
 36  
  * cardinality of the element.
 37  
  * <p>
 38  
  * 
 39  
  * 
 40  
  * This implementation uses a {@link HashMap} to store the elements as keys, and
 41  
  * their cardinality as values. Like HashMap, it is not thread safe and supports
 42  
  * <code>null</code> values. Unlike HashMap, the iterator does not support
 43  
  * removal of elements.
 44  
  * 
 45  
  * @param <E> the type of elements maintained by this set
 46  
  * 
 47  
  * 
 48  
  */
 49  
 public class HashMultiSet<E> extends AbstractCollection<E> {
 50  22
         private static final Integer ONE = Integer.valueOf(1);
 51  
 
 52  
         /** The elements of the set and their cardinality. */
 53  52
         private final HashMap<E, Integer> backingMap;
 54  
         /** The number of elements in the set, respecting their cardinality. */
 55  122
         private int elementCount = 0;
 56  
 
 57  
         /**
 58  
          * Creates an empty multiset with specified initial capacity. For the
 59  
          * initial capacity, you only need to consider the number of distinct
 60  
          * elements the set eventually holds, regardless of their cardinality.
 61  
          * 
 62  
          * @param capacity the initial capacity
 63  
          */
 64  99
         public HashMultiSet(int capacity) {
 65  99
                 backingMap = new HashMap<E, Integer>(capacity);
 66  99
         }
 67  
 
 68  
         /**
 69  
          * Creates a new set containing all elements in the specified collection. If
 70  
          * the collection can contain elements multiple times (such as lists or
 71  
          * other multi sets), the new set will respect the cardinality of the
 72  
          * elements.
 73  
          * 
 74  
          * @param contents the collection whose elements are to be placed into this
 75  
          *        set
 76  
          */
 77  23
         public HashMultiSet(Collection<? extends E> contents) {
 78  23
                 backingMap = new HashMap<E, Integer>(contents.size());
 79  23
                 addAll(contents);
 80  23
         }
 81  
 
 82  
         /**
 83  
          * Returns an iterator over the elements in the set. Elements are returned
 84  
          * in no particular order, however, an element of cardinality <code>N</code>
 85  
          * will be returned <code>N</code> times.
 86  
          * <p>
 87  
          * This iterator does not support {@link Iterator#remove()}.
 88  
          * 
 89  
          * @return an iterator over the elements contained in this set
 90  
          */
 91  
         @Override
 92  
         public Iterator<E> iterator() {
 93  43
                 return new HashMultiSetIterator(false);
 94  
         }
 95  
 
 96  
         /**
 97  
          * Returns an iterator over the elements in the set, ignoring the
 98  
          * cardinality. Each element in the set is returned exactly once, regardless
 99  
          * of its cardinality.
 100  
          * <p>
 101  
          * This iterator does not support {@link Iterator#remove()}.
 102  
          * 
 103  
          * @return an iterator over the distinct elements contained in this set
 104  
          * 
 105  
          */
 106  
         public Iterator<E> getFlatIterator() {
 107  9
                 return new HashMultiSetIterator(true);
 108  
         }
 109  
 
 110  
         /**
 111  
          * Returns the number of elements in the set, respecting cardinality of the
 112  
          * elements.
 113  
          */
 114  
         @Override
 115  
         public int size() {
 116  53
                 return elementCount;
 117  
         }
 118  
 
 119  
         /**
 120  
          * Gets the number of distinct elements in this set, ignoring the
 121  
          * cardinality of the elements.
 122  
          * 
 123  
          * @return The number of distinct elements in this set,
 124  
          */
 125  
         public int flatSetSize() {
 126  18
                 return backingMap.size();
 127  
         }
 128  
 
 129  
         /**
 130  
          * Returns <code>true</code> if this set contains the specified element at
 131  
          * least once.
 132  
          */
 133  
         @Override
 134  
         public boolean contains(Object o) {
 135  15
                 return backingMap.containsKey(o);
 136  
         }
 137  
 
 138  
         /**
 139  
          * Retrieves the cardinality of an element in this set.
 140  
          * 
 141  
          * @param o the element to look up
 142  
          * @return The cardinality of the element in this set, <code>0</code> if the
 143  
          *         set does not contain the element
 144  
          */
 145  
         public int getElementCount(Object o) {
 146  40
                 Integer count = backingMap.get(o);
 147  40
                 return count == null ? 0 : count.intValue();
 148  
         }
 149  
 
 150  
         /**
 151  
          * Adds the specified element to this set. If the element is already
 152  
          * present, its cardinality increases by one.
 153  
          * 
 154  
          * @param e element to be added to this set
 155  
          * @return <code>true</code> (as specified by {@link Collection#add})
 156  
          */
 157  
         @Override
 158  
         public boolean add(E e) {
 159  294
                 Integer count = backingMap.get(e);
 160  294
                 if (count == null)
 161  182
                         backingMap.put(e, ONE);
 162  
                 else
 163  112
                         backingMap.put(e, Integer.valueOf(count.intValue() + 1));
 164  294
                 elementCount++;
 165  294
                 return true;
 166  
         }
 167  
 
 168  
         /**
 169  
          * Removes one occurrence of the specified element from this set. If the
 170  
          * element is present more than once, its cardinality is decreased by one.
 171  
          * If it is present only once, it is removed entirely from the set.
 172  
          * 
 173  
          * @param o Element of which one occurrence is to be removed from this set.
 174  
          * @return <code>true</code> if the element was present in the set
 175  
          */
 176  
         @Override
 177  
         @SuppressWarnings("unchecked")
 178  
         public boolean remove(Object o) {
 179  19
                 Integer count = backingMap.get(o);
 180  19
                 if (count == null)
 181  9
                         return false;
 182  10
                 if (ONE.equals(count))
 183  5
                         backingMap.remove(o);
 184  
                 else
 185  5
                         backingMap.put((E) o, Integer.valueOf(count.intValue() - 1));
 186  
 
 187  10
                 elementCount--;
 188  10
                 return true;
 189  
         }
 190  
 
 191  
         /**
 192  
          * Removes elements in this set that are also contained in the specified
 193  
          * collection. For each occurrence of an element in the specified
 194  
          * collection, the cardinality of that element is decreased by one in this
 195  
          * set.
 196  
          * <p>
 197  
          * Let the cardinality of element <code>e</code> be <code>n&gt;0</code> in
 198  
          * this set, and assume the element is returned <code>m&ge;0</code> times by
 199  
          * the iterator of the specified collection. After the operation,
 200  
          * <ul>
 201  
          * <li>
 202  
          * if <code>m&lt;n</code>, the cardinality of element <code>e</code> in this
 203  
          * set is <code>n-m</code></li>
 204  
          * <li>
 205  
          * if <code>m&ge;n</code>, all occurrences of <code>e</code> have been
 206  
          * removed from this set</li>
 207  
          * </ul>
 208  
          */
 209  
         @Override
 210  
         public boolean removeAll(Collection<?> c) {
 211  4
                 boolean modified = false;
 212  23
                 for (Object o : c)
 213  15
                         modified |= remove(o);
 214  
 
 215  4
                 return modified;
 216  
         }
 217  
 
 218  
         /**
 219  
          * Retains only the elements in this collection that are also contained in
 220  
          * the specified collection.
 221  
          * <p>
 222  
          * Let the cardinality of element <code>e</code> be <code>n&gt;0</code> in
 223  
          * this set, and assume the element is returned <code>m&ge;0</code> times by
 224  
          * the iterator of the specified collection. After the operation,
 225  
          * <ul>
 226  
          * <li>
 227  
          * if <code>m&lt;n</code>, the cardinality of element <code>e</code> in this
 228  
          * set is <code>m</code></li>
 229  
          * <li>
 230  
          * if <code>m&ge;n</code>, the cardinality of element <code>e</code> in this
 231  
          * set remains unchanged at <code>n</code></li>
 232  
          * </ul>
 233  
          */
 234  
         @SuppressWarnings({ "rawtypes" })
 235  
         @Override
 236  
         public boolean retainAll(Collection<?> c) {
 237  
 
 238  2
                 HashMultiSet elementsToKeep = makeMultiSet(c);
 239  2
                 boolean modified = false;
 240  2
                 Iterator<Entry<E, Integer>> it = backingMap.entrySet().iterator();
 241  9
                 while (it.hasNext()) {
 242  5
                         Entry<E, Integer> entry = it.next();
 243  10
                         Integer maxCount = (Integer) elementsToKeep.backingMap.get(entry
 244  5
                                         .getKey());
 245  5
                         int currentCount = entry.getValue().intValue();
 246  5
                         if (maxCount == null) {
 247  1
                                 elementCount -= currentCount;
 248  1
                                 it.remove();
 249  1
                                 modified = true;
 250  1
                         } else {
 251  4
                                 int elementsToRemove = currentCount - maxCount.intValue();
 252  4
                                 if (elementsToRemove > 0) {
 253  2
                                         entry.setValue(Integer.valueOf(currentCount
 254  1
                                                         - elementsToRemove));
 255  1
                                         elementCount -= elementsToRemove;
 256  1
                                         modified = true;
 257  
                                 }
 258  
                         }
 259  
                 }
 260  2
                 return modified;
 261  
         }
 262  
 
 263  
         /**
 264  
          * Creates a multiset from a collection if it isn't already one.
 265  
          * 
 266  
          * @param c The collection to turn into a multiset
 267  
          * @return <code>c</code> for instances of HashMultiSet, else a new
 268  
          *         HashMultiSet with the contents of <code>c</code>
 269  
          */
 270  
         @SuppressWarnings({ "rawtypes", "unchecked" })
 271  
         private HashMultiSet makeMultiSet(Collection<?> c) {
 272  5
                 if (c instanceof HashMultiSet)
 273  2
                         return (HashMultiSet) c;
 274  3
                 return new HashMultiSet(c);
 275  
         }
 276  
 
 277  
         /**
 278  
          * Removes all occurrences of all elements from this set. The set will be
 279  
          * empty after this call returns.
 280  
          */
 281  
         @Override
 282  
         public void clear() {
 283  1
                 backingMap.clear();
 284  1
                 elementCount = 0;
 285  1
         }
 286  
 
 287  
         /**
 288  
          * Removes all occurrences of an element from this set.
 289  
          * 
 290  
          * @param o The element to remove
 291  
          * @return The cardinality of the element before the call, <code>0</code> if
 292  
          *         the set did not contain the element
 293  
          */
 294  
         public int removeAny(Object o) {
 295  4
                 Integer count = backingMap.remove(o);
 296  4
                 if (count != null) {
 297  3
                         elementCount -= count.intValue();
 298  3
                         return count.intValue();
 299  
                 }
 300  1
                 return 0;
 301  
         }
 302  
 
 303  
         /**
 304  
          * Compares the specified object with this set for equality. Returns
 305  
          * <tt>true</tt> if the given object is a collection of the same size (both
 306  
          * flat and respecting cardinality), and each element in this set has the
 307  
          * same number of occurrences in the specified collection.
 308  
          * <p>
 309  
          * Note: if the specified object is not itself a HashMultiSet, we may have
 310  
          * <code>this.equals(o)</code> but
 311  
          * <code>this.hashCode()!=o.hashCode()</code>.
 312  
          * 
 313  
          * @param o object to be compared for equality with this set
 314  
          * @return <tt>true</tt> if the specified object is equal to this set
 315  
          */
 316  
         @Override
 317  
         public boolean equals(Object o) {
 318  10
                 if (o == null)
 319  1
                         return false;
 320  9
                 if (o == this)
 321  1
                         return true;
 322  8
                 if (!(o instanceof Collection))
 323  1
                         return false;
 324  
 
 325  7
                 Collection<?> col = (Collection<?>) o;
 326  7
                 if (col.size() != size())
 327  1
                         return false;
 328  6
                 if (isEmpty())
 329  3
                         return true; // both sets are empty, happens a lot
 330  
 
 331  
                 @SuppressWarnings("rawtypes")
 332  3
                 HashMultiSet ms = makeMultiSet(col);
 333  3
                 if (ms.flatSetSize() != flatSetSize())
 334  1
                         return false;
 335  8
                 for (Entry<E, Integer> entry : backingMap.entrySet()) {
 336  5
                         if (!entry.getValue().equals(ms.backingMap.get(entry.getKey())))
 337  1
                                 return false;
 338  
                 }
 339  
 
 340  1
                 return true;
 341  
         }
 342  
 
 343  
         /**
 344  
          * Returns the hash code value for this set.
 345  
          * <p>
 346  
          * 
 347  
          * This implementation takes the sum of
 348  
          * <code>hashCode(e)^cardinality(e)</code> over all elements in the set.
 349  
          */
 350  
         @Override
 351  
         public int hashCode() {
 352  5
                 int hash = 0;
 353  22
                 for (Entry<E, Integer> entry : backingMap.entrySet()) {
 354  24
                         int keyHash = entry.getKey() == null ? 0 : entry.getKey()
 355  8
                                         .hashCode();
 356  12
                         hash += keyHash ^ entry.getValue().intValue();
 357  
                 }
 358  
 
 359  5
                 return hash;
 360  
         }
 361  
 
 362  
         /**
 363  
          * Iterator for the multiset. Does not support remove().
 364  
          */
 365  
         class HashMultiSetIterator implements Iterator<E> {
 366  
 
 367  
                 /** Iterator of the entries of the backing hash map. */
 368  
                 private Iterator<Entry<E, Integer>> backingIterator;
 369  
                 /** Answer for the next call to hasNext(). */
 370  
                 private boolean hasNextElement;
 371  
                 /** Answer for the next call to next(). */
 372  
                 private E nextElement;
 373  
                 /**
 374  
                  * Counts how many more calls to next() will return the current element.
 375  
                  */
 376  
                 private int elementCounter;
 377  
                 /** Indicates if this iterator should ignore element cardinality. */
 378  
                 private boolean isFlatIteration;
 379  
 
 380  
                 /**
 381  
                  * Constructs a new iterator.
 382  
                  * 
 383  
                  * @param flatIteration <code>true</code> if the iterator should ignore
 384  
                  *        cardinality of elements and return each element only once.
 385  
                  */
 386  52
                 HashMultiSetIterator(boolean flatIteration) {
 387  52
                         backingIterator = backingMap.entrySet().iterator();
 388  52
                         elementCounter = 0;
 389  52
                         hasNextElement = true;
 390  52
                         isFlatIteration = flatIteration;
 391  52
                         getReady();
 392  52
                 }
 393  
 
 394  
                 @Override
 395  
                 public boolean hasNext() {
 396  127
                         return hasNextElement;
 397  
                 }
 398  
 
 399  
                 @Override
 400  
                 public E next() {
 401  79
                         if (hasNextElement) {
 402  77
                                 E result = nextElement;
 403  77
                                 getReady();
 404  77
                                 return result;
 405  
                         }
 406  2
                         throw new NoSuchElementException();
 407  
                 }
 408  
 
 409  
                 /**
 410  
                  * Raises an exception
 411  
                  * 
 412  
                  * @throws UnsupportedOperationException Removal of elements is not
 413  
                  *         supported.
 414  
                  */
 415  
                 @Override
 416  
                 public void remove() {
 417  2
                         throw new UnsupportedOperationException();
 418  
                 }
 419  
 
 420  
                 /** Prepare nextObject and hasNextObject for subsequent calls. */
 421  
                 private void getReady() {
 422  129
                         if (elementCounter > 0) {
 423  18
                                 elementCounter--;
 424  18
                                 return;
 425  
                         }
 426  
 
 427  111
                         if (backingIterator.hasNext()) {
 428  61
                                 Entry<E, Integer> entry = backingIterator.next();
 429  61
                                 nextElement = entry.getKey();
 430  122
                                 elementCounter = isFlatIteration ? 0 : entry.getValue()
 431  40
                                                 .intValue() - 1;
 432  61
                                 return;
 433  
                         }
 434  
 
 435  50
                         hasNextElement = false;
 436  50
                 }
 437  
         }
 438  
 }