Coverage Report - com.sdmetrics.math.HashMultiSet - www.sdmetrics.com
 
Classes in this File Line Coverage Branch Coverage Complexity
HashMultiSet
100%
92/92
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  182
                 } else {
 163  112
                         backingMap.put(e, Integer.valueOf(count.intValue() + 1));
 164  
                 }
 165  294
                 elementCount++;
 166  294
                 return true;
 167  
         }
 168  
 
 169  
         /**
 170  
          * Removes one occurrence of the specified element from this set. If the
 171  
          * element is present more than once, its cardinality is decreased by one.
 172  
          * If it is present only once, it is removed entirely from the set.
 173  
          * 
 174  
          * @param o Element of which one occurrence is to be removed from this set.
 175  
          * @return <code>true</code> if the element was present in the set
 176  
          */
 177  
         @Override
 178  
         @SuppressWarnings("unchecked")
 179  
         public boolean remove(Object o) {
 180  19
                 Integer count = backingMap.get(o);
 181  19
                 if (count == null) {
 182  9
                         return false;
 183  
                 }
 184  10
                 if (ONE.equals(count)) {
 185  5
                         backingMap.remove(o);
 186  5
                 } else {
 187  5
                         backingMap.put((E) o, Integer.valueOf(count.intValue() - 1));
 188  
                 }
 189  
 
 190  10
                 elementCount--;
 191  10
                 return true;
 192  
         }
 193  
 
 194  
         /**
 195  
          * Removes elements in this set that are also contained in the specified
 196  
          * collection. For each occurrence of an element in the specified
 197  
          * collection, the cardinality of that element is decreased by one in this
 198  
          * set.
 199  
          * <p>
 200  
          * Let the cardinality of element <code>e</code> be <code>n&gt;0</code> in
 201  
          * this set, and assume the element is returned <code>m&ge;0</code> times by
 202  
          * the iterator of the specified collection. After the operation,
 203  
          * <ul>
 204  
          * <li>
 205  
          * if <code>m&lt;n</code>, the cardinality of element <code>e</code> in this
 206  
          * set is <code>n-m</code></li>
 207  
          * <li>
 208  
          * if <code>m&ge;n</code>, all occurrences of <code>e</code> have been
 209  
          * removed from this set</li>
 210  
          * </ul>
 211  
          */
 212  
         @Override
 213  
         public boolean removeAll(Collection<?> c) {
 214  4
                 boolean modified = false;
 215  23
                 for (Object o : c) {
 216  15
                         modified |= remove(o);
 217  
                 }
 218  
 
 219  4
                 return modified;
 220  
         }
 221  
 
 222  
         /**
 223  
          * Retains only the elements in this collection that are also contained in
 224  
          * the specified collection.
 225  
          * <p>
 226  
          * Let the cardinality of element <code>e</code> be <code>n&gt;0</code> in
 227  
          * this set, and assume the element is returned <code>m&ge;0</code> times by
 228  
          * the iterator of the specified collection. After the operation,
 229  
          * <ul>
 230  
          * <li>
 231  
          * if <code>m&lt;n</code>, the cardinality of element <code>e</code> in this
 232  
          * set is <code>m</code></li>
 233  
          * <li>
 234  
          * if <code>m&ge;n</code>, the cardinality of element <code>e</code> in this
 235  
          * set remains unchanged at <code>n</code></li>
 236  
          * </ul>
 237  
          */
 238  
         @SuppressWarnings({ "rawtypes" })
 239  
         @Override
 240  
         public boolean retainAll(Collection<?> c) {
 241  
 
 242  2
                 HashMultiSet elementsToKeep = makeMultiSet(c);
 243  2
                 boolean modified = false;
 244  2
                 Iterator<Entry<E, Integer>> it = backingMap.entrySet().iterator();
 245  9
                 while (it.hasNext()) {
 246  5
                         Entry<E, Integer> entry = it.next();
 247  10
                         Integer maxCount = (Integer) elementsToKeep.backingMap.get(entry
 248  5
                                         .getKey());
 249  5
                         int currentCount = entry.getValue().intValue();
 250  5
                         if (maxCount == null) {
 251  1
                                 elementCount -= currentCount;
 252  1
                                 it.remove();
 253  1
                                 modified = true;
 254  1
                         } else {
 255  4
                                 int elementsToRemove = currentCount - maxCount.intValue();
 256  4
                                 if (elementsToRemove > 0) {
 257  2
                                         entry.setValue(Integer.valueOf(currentCount
 258  1
                                                         - elementsToRemove));
 259  1
                                         elementCount -= elementsToRemove;
 260  1
                                         modified = true;
 261  
                                 }
 262  
                         }
 263  
                 }
 264  2
                 return modified;
 265  
         }
 266  
 
 267  
         /**
 268  
          * Creates a multiset from a collection if it isn't already one.
 269  
          * 
 270  
          * @param c The collection to turn into a multiset
 271  
          * @return <code>c</code> for instances of HashMultiSet, else a new
 272  
          *         HashMultiSet with the contents of <code>c</code>
 273  
          */
 274  
         @SuppressWarnings({ "rawtypes", "unchecked" })
 275  
         private HashMultiSet makeMultiSet(Collection<?> c) {
 276  5
                 if (c instanceof HashMultiSet) {
 277  2
                         return (HashMultiSet) c;
 278  
                 }
 279  3
                 return new HashMultiSet(c);
 280  
         }
 281  
 
 282  
         /**
 283  
          * Removes all occurrences of all elements from this set. The set will be
 284  
          * empty after this call returns.
 285  
          */
 286  
         @Override
 287  
         public void clear() {
 288  1
                 backingMap.clear();
 289  1
                 elementCount = 0;
 290  1
         }
 291  
 
 292  
         /**
 293  
          * Removes all occurrences of an element from this set.
 294  
          * 
 295  
          * @param o The element to remove
 296  
          * @return The cardinality of the element before the call, <code>0</code> if
 297  
          *         the set did not contain the element
 298  
          */
 299  
         public int removeAny(Object o) {
 300  4
                 Integer count = backingMap.remove(o);
 301  4
                 if (count != null) {
 302  3
                         elementCount -= count.intValue();
 303  3
                         return count.intValue();
 304  
                 }
 305  1
                 return 0;
 306  
         }
 307  
 
 308  
         /**
 309  
          * Compares the specified object with this set for equality. Returns
 310  
          * <tt>true</tt> if the given object is a collection of the same size (both
 311  
          * flat and respecting cardinality), and each element in this set has the
 312  
          * same number of occurrences in the specified collection.
 313  
          * <p>
 314  
          * Note: if the specified object is not itself a HashMultiSet, we may have
 315  
          * <code>this.equals(o)</code> but
 316  
          * <code>this.hashCode()!=o.hashCode()</code>.
 317  
          * 
 318  
          * @param o object to be compared for equality with this set
 319  
          * @return <tt>true</tt> if the specified object is equal to this set
 320  
          */
 321  
         @Override
 322  
         public boolean equals(Object o) {
 323  10
                 if (o == null) {
 324  1
                         return false;
 325  
                 }
 326  9
                 if (o == this) {
 327  1
                         return true;
 328  
                 }
 329  8
                 if (!(o instanceof Collection)) {
 330  1
                         return false;
 331  
                 }
 332  
 
 333  7
                 Collection<?> col = (Collection<?>) o;
 334  7
                 if (col.size() != size()) {
 335  1
                         return false;
 336  
                 }
 337  6
                 if (isEmpty()) {
 338  3
                         return true; // both sets are empty, happens a lot
 339  
                 }
 340  
 
 341  
                 @SuppressWarnings("rawtypes")
 342  3
                 HashMultiSet ms = makeMultiSet(col);
 343  3
                 if (ms.flatSetSize() != flatSetSize()) {
 344  1
                         return false;
 345  
                 }
 346  8
                 for (Entry<E, Integer> entry : backingMap.entrySet()) {
 347  5
                         if (!entry.getValue().equals(ms.backingMap.get(entry.getKey()))) {
 348  1
                                 return false;
 349  
                         }
 350  
                 }
 351  
 
 352  1
                 return true;
 353  
         }
 354  
 
 355  
         /**
 356  
          * Returns the hash code value for this set.
 357  
          * <p>
 358  
          * 
 359  
          * This implementation takes the sum of
 360  
          * <code>hashCode(e)^cardinality(e)</code> over all elements in the set.
 361  
          */
 362  
         @Override
 363  
         public int hashCode() {
 364  5
                 int hash = 0;
 365  22
                 for (Entry<E, Integer> entry : backingMap.entrySet()) {
 366  24
                         int keyHash = entry.getKey() == null ? 0 : entry.getKey()
 367  8
                                         .hashCode();
 368  12
                         hash += keyHash ^ entry.getValue().intValue();
 369  
                 }
 370  
 
 371  5
                 return hash;
 372  
         }
 373  
 
 374  
         /**
 375  
          * Iterator for the multiset. Does not support remove().
 376  
          */
 377  
         class HashMultiSetIterator implements Iterator<E> {
 378  
 
 379  
                 /** Iterator of the entries of the backing hash map. */
 380  
                 private Iterator<Entry<E, Integer>> backingIterator;
 381  
                 /** Answer for the next call to hasNext(). */
 382  
                 private boolean hasNextElement;
 383  
                 /** Answer for the next call to next(). */
 384  
                 private E nextElement;
 385  
                 /**
 386  
                  * Counts how many more calls to next() will return the current element.
 387  
                  */
 388  
                 private int elementCounter;
 389  
                 /** Indicates if this iterator should ignore element cardinality. */
 390  
                 private boolean isFlatIteration;
 391  
 
 392  
                 /**
 393  
                  * Constructs a new iterator.
 394  
                  * 
 395  
                  * @param flatIteration <code>true</code> if the iterator should ignore
 396  
                  *        cardinality of elements and return each element only once.
 397  
                  */
 398  52
                 HashMultiSetIterator(boolean flatIteration) {
 399  52
                         backingIterator = backingMap.entrySet().iterator();
 400  52
                         elementCounter = 0;
 401  52
                         hasNextElement = true;
 402  52
                         isFlatIteration = flatIteration;
 403  52
                         getReady();
 404  52
                 }
 405  
 
 406  
                 @Override
 407  
                 public boolean hasNext() {
 408  127
                         return hasNextElement;
 409  
                 }
 410  
 
 411  
                 @Override
 412  
                 public E next() {
 413  79
                         if (hasNextElement) {
 414  77
                                 E result = nextElement;
 415  77
                                 getReady();
 416  77
                                 return result;
 417  
                         }
 418  2
                         throw new NoSuchElementException();
 419  
                 }
 420  
 
 421  
                 /**
 422  
                  * Raises an exception.
 423  
                  * 
 424  
                  * @throws UnsupportedOperationException Removal of elements is not
 425  
                  *         supported.
 426  
                  */
 427  
                 @Override
 428  
                 public void remove() {
 429  2
                         throw new UnsupportedOperationException();
 430  
                 }
 431  
 
 432  
                 /** Prepare nextObject and hasNextObject for subsequent calls. */
 433  
                 private void getReady() {
 434  129
                         if (elementCounter > 0) {
 435  18
                                 elementCounter--;
 436  18
                                 return;
 437  
                         }
 438  
 
 439  111
                         if (backingIterator.hasNext()) {
 440  61
                                 Entry<E, Integer> entry = backingIterator.next();
 441  61
                                 nextElement = entry.getKey();
 442  122
                                 elementCounter = isFlatIteration ? 0 : entry.getValue()
 443  40
                                                 .intValue() - 1;
 444  61
                                 return;
 445  
                         }
 446  
 
 447  50
                         hasNextElement = false;
 448  50
                 }
 449  
         }
 450  
 }