Advertisement
DulcetAirman

Multiset

Feb 20th, 2015
310
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ///////////////////////////////////////////////////////
  2.  
  3. MOVED TO : https://github.com/claudemartin/multiset
  4.  
  5. ///////////////////////////////////////////////////////
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15. package ch.claude_martin;
  16.  
  17. import static java.util.Arrays.asList;
  18. import static java.util.Objects.requireNonNull;
  19.  
  20. import java.io.Serializable;
  21. import java.lang.reflect.Constructor;
  22. import java.lang.reflect.InvocationTargetException;
  23. import java.util.*;
  24. import java.util.AbstractMap.SimpleImmutableEntry;
  25. import java.util.Map.Entry;
  26. import java.util.function.*;
  27. import java.util.stream.Collectors;
  28. import java.util.stream.IntStream;
  29. import java.util.stream.Stream;
  30.  
  31. import javax.annotation.concurrent.NotThreadSafe;
  32.  
  33. /**
  34. * Multiset in Java. It doesn't maintain sorting or insertion order. But it's not a regular set,
  35. * because you can add an element more than once. If an element is already present that equals the
  36. * element to be inserted then it's multiplicity (count) is incremented by one. <code>null</code> is
  37. * allowed as an element.
  38. *
  39. * <p>
  40. * An element with multiplicity zero is completely removed from the data structure and will not
  41. * occur as a tuple of {@code (element, 0)}. This needs to be considered when using methods such as
  42. * {@link #setMultiplicities(ToIntBiFunction)}, {@link #forEach(ObjIntConsumer)}, {@link #entries()}
  43. * , and {@link #merge(Multiset, IntBinaryOperator)}.
  44. *
  45. * <p>
  46. * <a href="https://humanoidreadable.wordpress.com/2015/02/20/multiset-in-java/">blog entry</a>
  47. * <p>
  48. * Copyright: You can use this for whatever you like! No restrictions.
  49. *
  50. * @author Claude Martin
  51. *
  52. * @param <T>
  53. * The type of the elements
  54. */
  55. @NotThreadSafe
  56. public final class Multiset<T> extends AbstractCollection<T> implements Serializable {
  57. private static final long serialVersionUID = -7083567870279959503L;
  58.  
  59. /** The backing map. */
  60. final Map<T, Integer> map;
  61. /** View as map. Lazy. This is the same as {@link #map} if and only if this is unmodifiable. */
  62. private transient Map<T, Integer> view = null;
  63.  
  64. /**
  65. * Total size of this multiset.
  66. *
  67. * @implNote Modification must always be performend on the {@link #map} first. This will fail if
  68. * this multiset {@link #isUnmodifiable() is unmodifiable}.
  69. */
  70. int size = 0;
  71.  
  72. public Multiset() {
  73. this.map = new HashMap<>();
  74. }
  75.  
  76. /** Creates an unmodifiable Multiset. */
  77. private Multiset(final Multiset<T> multiset, final boolean unmodifiable) {
  78. assert unmodifiable;
  79. this.map = this.view = Collections.unmodifiableMap(multiset.map);
  80. this.size = multiset.size;
  81. this.checkSize();
  82. return;
  83. }
  84.  
  85. /** Creates an empty Multiset. */
  86. private Multiset(final boolean empty) {
  87. this.map = this.view = Collections.emptyMap();
  88. this.size = 0;
  89. }
  90.  
  91. /** Creates a new Multiset and adds all elements from the given collection. */
  92. public Multiset(final Collection<? extends T> coll) {
  93. requireNonNull(coll, "coll");
  94. this.map = new HashMap<>(coll.size());
  95. for (final T t : coll)
  96. this.map.merge(t, 1, Integer::sum);
  97. this.size = coll.size();
  98. this.checkSize();
  99. }
  100.  
  101. /** Creates a new Multiset and adds all elements from the given Multiset. */
  102. public Multiset(final Multiset<? extends T> multiset) {
  103. requireNonNull(multiset, "multiset");
  104. multiset.checkSize();
  105. this.map = new HashMap<>(multiset.map);
  106. this.size = multiset.size;
  107. this.checkSize();
  108. }
  109.  
  110. /**
  111. * Creates a new {@link Multiset} containing all given elements.
  112. *
  113. * @param elements
  114. * The elements
  115. * @return <code>new Multiset<>(asList(elements));</code>
  116. */
  117. @SafeVarargs
  118. public static <T> Multiset<T> of(final T... elements) {
  119. requireNonNull(elements, "elements");
  120. return new Multiset<>(asList(elements));
  121. }
  122.  
  123. /**
  124. * Creates a new {@link Multiset} containing all given elements, with the multiplicity defined by
  125. * the given function.
  126. *
  127. * @param set
  128. * The elements
  129. * @param m
  130. * The multiplicity
  131. * @return new {@link Multiset} greated from the given data.
  132. */
  133. public static <T> Multiset<T> of(final Set<? extends T> set, final ToIntFunction<? super T> m) {
  134. requireNonNull(set, "set");
  135. requireNonNull(m, "m");
  136. final Multiset<T> result = new Multiset<>();
  137. for (final T t : set)
  138. result.setMultiplicity(t, m.applyAsInt(t));
  139. return result;
  140. }
  141.  
  142. /**
  143. * Adds the object and returns true.
  144. *
  145. * @see #insert(Object)
  146. */
  147. @Override
  148. public boolean add(final T t) {
  149. this.insert(t);
  150. return true;
  151. }
  152.  
  153. /**
  154. * Sets the multiplicity of a certain key. The key is removed if m is 0 or added if it was 0.
  155. * Therefore this may lead to a modification of the underlying data structure. The
  156. * {@link #iterator() Iterator} supports @link {@link Iterator#remove() removal} of elements
  157. * during iteration.
  158. *
  159. * @param element
  160. * the element
  161. * @param m
  162. * new multiplicity
  163. * @returns the old multiplicity.
  164. */
  165. public int setMultiplicity(final T element, final int m) {
  166. if (m < 0)
  167. throw new IllegalArgumentException("m < 0");
  168. final int i = this.map.getOrDefault(element, 0);
  169. if (m == i)
  170. return i;
  171. if (m == 0)
  172. this.map.remove(element);
  173. else
  174. this.map.put(element, m);
  175. this.size = this.size - i + m;
  176. this.checkSize();
  177. return i;
  178. }
  179.  
  180. /**
  181. * Sets the multiplicity of a certain key, only if currently set to the specified value.
  182. *
  183. * @param element
  184. * the element
  185. * @param oldMultiplicity
  186. * old multiplicity
  187. * @param newMultiplicity
  188. * new multiplicity
  189. *
  190. * @return {@code true} if the value was replaced
  191. *
  192. * @see Map#replace(Object, Object, Object)
  193. */
  194. public boolean setMultiplicity(final T element, final int oldMultiplicity,
  195. final int newMultiplicity) {
  196. requireNonNull(element, "obj");
  197. if (oldMultiplicity < 0 || newMultiplicity < 0)
  198. throw new IllegalArgumentException("negative multiplicity");
  199. if (this.getMultiplicity(element) == oldMultiplicity) {
  200. this.setMultiplicity(element, newMultiplicity);
  201. return true;
  202. }
  203. return false;
  204. }
  205.  
  206. /**
  207. * Adds the object and returns the new multiplicity.
  208. *
  209. * @see #add(Object)
  210. */
  211. public int insert(final T t) {
  212. final Integer result = this.map.merge(t, 1, Integer::sum);
  213. this.size++;
  214. this.checkSize();
  215. return result;
  216. }
  217.  
  218. /**
  219. * Removes a single instance of the specified element from this multiset. This decrements the
  220. * multiplicity by one. Does nothing if it wasn't in the set. To remove all equal objects you must
  221. * call <code>{@link #setMultiplicity(Object, int) setMultiplicity(t, 0)}</code>.
  222. */
  223. @Override
  224. @SuppressWarnings("unchecked")
  225. public boolean remove(final Object t) {
  226. final int value = this.map.getOrDefault(t, 0);
  227. switch (value) {
  228. case 0:
  229. return false;
  230. case 1:
  231. this.map.remove(t);
  232. break;
  233. default:
  234. assert value > 1 : "invalid value";
  235. this.map.put((T) t, value - 1);
  236. break;
  237. }
  238. this.size--;
  239. this.checkSize();
  240. return true;
  241. }
  242.  
  243. /**
  244. * Reset the multiplicity for each element in this {@link Multiset}.
  245. *
  246. * <p>
  247. * Note that elements with a multiplicity of zero will not be processed, as they are not contained
  248. * in the multiset.
  249. *
  250. * @param m
  251. * function for new multiplicities
  252. * @return true, if any multiplicity of any element was altered.
  253. */
  254. public boolean setMultiplicities(final ToIntBiFunction<? super T, Integer> m) {
  255. requireNonNull(m, "m");
  256. if (this.isEmpty())
  257. return false;
  258. boolean modified = false;
  259. final Iterator<Entry<T, Integer>> itr = this.map.entrySet().iterator();
  260. while (itr.hasNext()) {
  261. final Entry<T, Integer> next = itr.next();
  262. final T t = next.getKey();
  263. final int oldm = next.getValue();
  264. final int newM = m.applyAsInt(t, oldm);
  265. if (oldm != newM) {
  266. if (newM == 0)
  267. itr.remove();
  268. else
  269. next.setValue(newM);
  270. this.size += -oldm + newM;
  271. modified = true;
  272. }
  273. }
  274. this.checkSize();
  275. return modified;
  276. }
  277.  
  278. @SuppressWarnings({ "unchecked" })
  279. @Override
  280. public boolean removeAll(final Collection<?> c) {
  281. requireNonNull(c, "c");
  282. if (c instanceof Multiset)
  283. return this.removeAll((Multiset<? extends T>) c);
  284. return super.removeAll(c);
  285. }
  286.  
  287. /**
  288. * @see #removeAll(Collection)
  289. */
  290. public boolean removeAll(final Multiset<?> set) {
  291. requireNonNull(set, "set");
  292. boolean result = false;
  293. if (set.isEmpty())
  294. return false;
  295. final Iterator<Entry<T, Integer>> itr = this.map.entrySet().iterator();
  296. while (itr.hasNext()) {
  297. final Entry<T, Integer> next = itr.next();
  298. if (set.map.containsKey(next.getKey())) {
  299. itr.remove();
  300. this.size -= next.getValue();
  301. result = true;
  302. }
  303. }
  304. this.checkSize();
  305. return result;
  306. }
  307.  
  308. @Override
  309. public boolean retainAll(final Collection<?> c) {
  310. requireNonNull(c, "c");
  311. if (c instanceof Multiset)
  312. return this.retainAll((Multiset<?>) c);
  313. return this.asSet().retainAll(c);
  314. }
  315.  
  316. /**
  317. * @see #retainAll(Collection)
  318. */
  319. public boolean retainAll(final Multiset<?> set) {
  320. requireNonNull(set, "set");
  321. if (set == this)
  322. return false;
  323. return this.asSet().retainAll(set.asSet());
  324. }
  325.  
  326. /**
  327. * Get the multiplicity or the given object. If the object is not in this multiset then the
  328. * multiplicity is 0.
  329. *
  330. * @return the multiplicity.
  331. */
  332. public int getMultiplicity(final Object t) {
  333. return this.map.getOrDefault(t, 0);
  334. }
  335.  
  336. Iterator<T> iterator(final Iterator<Entry<T, Integer>> entries) {
  337. return new Iterator<T>() {
  338. int c = 0;
  339. T t = null;
  340.  
  341. @Override
  342. public T next() {
  343. if (!this.hasNext())
  344. throw new NoSuchElementException();
  345. if (this.c == 0) {
  346. final Entry<T, Integer> e = entries.next();
  347. this.t = e.getKey();
  348. this.c = e.getValue();
  349. }
  350. this.c--;
  351. return this.t;
  352. }
  353.  
  354. @Override
  355. public boolean hasNext() {
  356. return this.c > 0 || entries.hasNext();
  357. }
  358.  
  359. @Override
  360. public void remove() {
  361. final int multiplicity = Multiset.this.getMultiplicity(this.t);
  362. if (multiplicity == 1) {
  363. entries.remove();
  364. Multiset.this.size--;
  365. } else
  366. Multiset.this.setMultiplicity(this.t, multiplicity - 1);
  367. }
  368. };
  369. }
  370.  
  371. /**
  372. * Iterator of all elements. Each element is iterated as many times as it is in this multiset. The
  373. * {@link Iterator} supports the {@link Iterator#remove() remove} method.
  374. */
  375. @Override
  376. public Iterator<T> iterator() {
  377. this.checkSize();
  378. return this.iterator(this.map.entrySet().iterator());
  379. }
  380.  
  381. @Override
  382. public Spliterator<T> spliterator() {
  383. return Spliterators.spliterator(this, 0);
  384. }
  385.  
  386. /** The class invariant. */
  387. void checkSize() {
  388. assert this.map.values().stream().mapToInt(i -> i).sum() == this.size : this.getClass()
  389. .getSimpleName() + ": wrong size";
  390. }
  391.  
  392. /**
  393. * {@inheritDoc}
  394. * <p>
  395. * This returns the total number of elements, including repeated memberships (cardinality). To get
  396. * the amount of discinct elements use {@link #asMap()}.{@link Map#size() size()}.
  397. * */
  398. @Override
  399. public int size() {
  400. this.checkSize();
  401. return this.size;
  402. }
  403.  
  404. /**
  405. * Returns a copy of the underlying set of elements. Changes to this set do not alter the
  406. * Multiset.
  407. *
  408. * <p>
  409. * If using the formal definition <code>(A, m)</code> of a multiset, the returned set is
  410. * <code>A</code> and <code>multiset::getMultiplicity</code> is <code>m</code>.
  411. *
  412. * @see #asSet()
  413. * @see #entries()
  414. */
  415. public Set<T> toSet() {
  416. return new HashSet<>(this.map.keySet());
  417. }
  418.  
  419. /**
  420. * Conventiance mehtod to create a string representation of this multiset.
  421. * <p>
  422. * Example: {@code ms.toString((t, i) -> t + " x " + i, ", ", "[ ", " ]")}
  423. *
  424. * @param f
  425. * Mapping function for each entry (element and multiplicity)
  426. * @param delimiter
  427. * the delimiter to be used between each entry
  428. * @param prefix
  429. * the sequence of characters to be used at the beginning of the joined result
  430. * @param suffix
  431. * the sequence of characters to be used at the end of the joined result
  432. * @return string representation of this multiset
  433. */
  434. public String toString(final BiFunction<T, Integer, String> f, final CharSequence delimiter,
  435. final CharSequence prefix, final CharSequence suffix) {
  436. requireNonNull(f, "f");
  437. requireNonNull(delimiter, "delimiter");
  438. requireNonNull(prefix, "prefix");
  439. requireNonNull(suffix, "suffix");
  440.  
  441. return this.map.entrySet().stream().map(e -> f.apply(e.getKey(), e.getValue()))
  442. .collect(Collectors.joining(delimiter, prefix, suffix));
  443. }
  444.  
  445. /**
  446. * As a new, sorted List.
  447. *
  448. * <p>
  449. * To sort by multiplicity, descending:<br>
  450. * <code>multiset.toList((a, b) -> b.getValue() - a.getValue())</code>
  451. */
  452. public List<T> toList(final Comparator<Map.Entry<T, Integer>> comparator) {
  453. if (null == comparator)
  454. return this.stream().collect(Collectors.toList());
  455. return this.entries().sorted(comparator)
  456. .flatMap(e -> IntStream.range(0, e.getValue()).<T> mapToObj(x -> e.getKey()))
  457. .collect(Collectors.toList());
  458. }
  459.  
  460. /**
  461. * Streams each element and it's multiplicity. The returned entries are immutable. Mutable entries
  462. * can be accessed using: {@code this.asMap().entrySet()}
  463. */
  464. @SuppressWarnings("unchecked")
  465. public Stream<Map.Entry<T, Integer>> entries() {
  466. final Stream<Entry<T, Integer>> stream = this.map.entrySet().stream();
  467. if (this.isUnmodifiable())
  468. return stream;
  469. return stream.map(SimpleImmutableEntry::new);
  470. }
  471.  
  472. @Override
  473. public boolean addAll(final Collection<? extends T> c) {
  474. requireNonNull(c, "c");
  475. if (c instanceof Multiset)
  476. return this.addAll((Multiset<? extends T>) c);
  477. return super.addAll(c);
  478. }
  479.  
  480. /** @see #addAll(Collection) */
  481. public boolean addAll(final Multiset<? extends T> ms) {
  482. for (final Entry<? extends T, Integer> e : ms.map.entrySet()) {
  483. final Integer val = e.getValue();
  484. this.map.merge(e.getKey(), val, Integer::sum);
  485. this.size += val;
  486. }
  487. this.checkSize();
  488. return ms.size() != 0;
  489. }
  490.  
  491. /**
  492. * Two {@link Multiset}s are equal if both contain the same elements with the same multiplicities.
  493. */
  494. @Override
  495. public boolean equals(final Object obj) {
  496. if (obj instanceof Multiset) {
  497. final Multiset<?> other = (Multiset<?>) obj;
  498. return this.size == other.size && this.map.equals(other.map);
  499. }
  500. return false;
  501. }
  502.  
  503. @Override
  504. public int hashCode() {
  505. return this.size ^ this.map.hashCode();
  506. }
  507.  
  508. @Override
  509. public void clear() {
  510. if (this.size == 0)
  511. return;
  512. this.map.clear();
  513. this.size = 0;
  514. this.checkSize();
  515. }
  516.  
  517. /**
  518. * Creates a clone. The cloned multiset is modifiable.
  519. */
  520. @Override
  521. protected Object clone() {
  522. return new Multiset<>(this);
  523. }
  524.  
  525. @Override
  526. public boolean containsAll(final Collection<?> c) {
  527. requireNonNull(c, "c");
  528. if (c instanceof Multiset)
  529. this.map.keySet().containsAll(((Multiset<?>) c).map.keySet());
  530. return this.map.keySet().containsAll(c);
  531. }
  532.  
  533. @Override
  534. public boolean isEmpty() {
  535. return this.size == 0;
  536. }
  537.  
  538. /** Process each object only once, with the multiplicity given as a second parameter. */
  539. public void forEach(final ObjIntConsumer<T> action) {
  540. this.map.forEach(action::accept);
  541. }
  542.  
  543. @Override
  544. public boolean contains(final Object obj) {
  545. return this.map.containsKey(obj);
  546. }
  547.  
  548. /**
  549. * The intersection of two multisets. This is equal to
  550. * <code>this.{@link #merge(Multiset, IntBinaryOperator) merge}(set, {@link Math#min(int, int) Math::min})</code>
  551. * . However, the type of the elements in the provided multiset does not matter.
  552. */
  553. @SuppressWarnings("unchecked")
  554. public Multiset<T> intersect(final Multiset<?> set) {
  555. requireNonNull(set, "set");
  556. return this.merge((Multiset<T>) set, Math::min);
  557. }
  558.  
  559. /**
  560. * The union of two multisets. This is equal to
  561. * <code>this.{@link #merge(Multiset, IntBinaryOperator) merge}(set, {@link Integer#sum(int, int) Integer::sum})</code>
  562. *
  563. * <p>
  564. * Note: A different definition of <i>union</i> would use {@link Math#max(int, int)} with
  565. * {@link #merge(Multiset, IntBinaryOperator)}.
  566. *
  567. * @see #addAll(Collection)
  568. */
  569. public Multiset<T> union(final Multiset<? extends T> set) {
  570. requireNonNull(set, "set");
  571. return this.merge(set, Integer::sum);
  572. }
  573.  
  574. public <S> Multiset<S> union(final Multiset<? extends S> set, final Class<S> supertype) {
  575. requireNonNull(set, "set");
  576. requireNonNull(supertype, "supertype");
  577. return this.merge(set, Integer::sum, supertype);
  578. }
  579.  
  580. /**
  581. * The relative complement of this and a given multiset.
  582. *
  583. * @see #removeAll(Collection)
  584. */
  585. public Multiset<T> minus(final Multiset<? extends T> set) {
  586. requireNonNull(set, "set");
  587. final Multiset<T> result = new Multiset<>(this);
  588. if (set.isEmpty())
  589. return result;
  590. result.removeAll(set);
  591. return result;
  592. }
  593.  
  594. /**
  595. * Create new multiset from this and another multiset. The given operation will calculate the new
  596. * multiplicity for all elements.
  597. *
  598. * <p>
  599. * This pseudo-code illustrates how the operation is used to create a new multiset. In this case
  600. * the result is equal to the result of {@link #union(Multiset)}. <code><pre>
  601. * mset1 = [ a, a, a, b ];
  602. * mset2 = [ b, c ];
  603. * union = m1.merge(m2, Integer::sum);
  604. * // m3 = [ a, a, a, b, b, c ]
  605. * </pre></code>
  606. */
  607. public Multiset<T> merge(final Multiset<? extends T> set, final IntBinaryOperator operation) {
  608. requireNonNull(set, "set");
  609. requireNonNull(operation, "operation");
  610. final Multiset<T> result = new Multiset<>(this);
  611. if (set.isEmpty() && this.isEmpty())
  612. return result;
  613. Stream.concat(this.map.keySet().stream(), set.map.keySet().stream()).distinct().forEach(t -> {
  614. result.setMultiplicity(t, //
  615. operation.applyAsInt(this.getMultiplicity(t), set.getMultiplicity(t)));
  616. });
  617. result.checkSize();
  618. return result;
  619. }
  620.  
  621. /**
  622. * Create new multiset from this and another multiset. The given operation will calculate the new
  623. * multiplicity for all elements.
  624. *
  625. * @implNote Only with assertions enabled there will be a check that all elements are assignable
  626. * to the given supertype.
  627. * @param set
  628. * The other multiset
  629. * @param operation
  630. * the operation for the multiplicities
  631. * @param supertype
  632. * a supertype of both multisets
  633. */
  634. @SuppressWarnings("unchecked")
  635. public <S> Multiset<S> merge(final Multiset<? extends S> set, final IntBinaryOperator operation,
  636. final Class<S> supertype) {
  637. requireNonNull(set, "set");
  638. requireNonNull(operation, "operation");
  639. requireNonNull(supertype, "supertype");
  640. assert this.asSet().stream().allMatch(e -> supertype.isAssignableFrom(e.getClass()));
  641. assert set.asSet().stream().allMatch(e -> supertype.isAssignableFrom(e.getClass()));
  642. return ((Multiset<S>) this).merge(set, operation);
  643. }
  644.  
  645. private void readObject(final java.io.ObjectInputStream stream) throws Exception {
  646. requireNonNull(stream, "stream").defaultReadObject();
  647. this.checkSize();
  648. }
  649.  
  650. /**
  651. * Returnes an unmodifiable view of the specified {@link Multiset}.
  652. *
  653. * @param multiset
  654. * the multiset for which an unmodifiable view is to be returned.
  655. * @return an unmodifiable view of the specified map.
  656. */
  657. public static <T> Multiset<T> unmodifiableMultiset(final Multiset<T> multiset) {
  658. requireNonNull(multiset, "multiset");
  659. if (multiset.isUnmodifiable())
  660. return multiset;
  661. if (multiset.isEmpty())
  662. return emptyMultiset();
  663. return new Multiset<>(multiset, true);
  664. }
  665.  
  666. /**
  667. * Checks whether this is backed by an unmodifiable map. An unmodifiable {@link Multiset} always
  668. * has the same reference set for {@link #map} and {@link #view}.
  669. *
  670. * @see #unmodifiableMultiset(Multiset)
  671. */
  672. public boolean isUnmodifiable() {
  673. return this.map == this.view;
  674. }
  675.  
  676. /**
  677. * A map-view of this {@link Multiset}. Changes are reflected on the {@link Multiset}. However,
  678. * when using streams or iterators it is not allowed to set the multiplicity to 0. Instead the
  679. * entry needs to be {@link Iterator#remove() removed}.
  680. * <p>
  681. * Methods such as {@link Map#put}, {@link Map#clear}, and {@link Map#contains} delegated to the
  682. * backing map of the {@link Multiset}.
  683. *
  684. * @see #asSet()
  685. * @see #entries()
  686. * */
  687. public Map<T, Integer> asMap() {
  688. if (this.view != null)
  689. return this.view;
  690. return this.view = new AbstractMap<T, Integer>() {
  691. private Set<java.util.Map.Entry<T, Integer>> entrySet;
  692.  
  693. @Override
  694. public Integer put(final T key, final Integer value) {
  695. return Multiset.this.setMultiplicity(key, value);
  696. }
  697.  
  698. @Override
  699. public Set<java.util.Map.Entry<T, Integer>> entrySet() {
  700. if (this.entrySet != null)
  701. return this.entrySet;
  702. return this.entrySet = new AbstractSet<Map.Entry<T, Integer>>() {
  703.  
  704. @Override
  705. public Iterator<java.util.Map.Entry<T, Integer>> iterator() {
  706. final Iterator<java.util.Map.Entry<T, Integer>> itr = Multiset.this.map.entrySet()
  707. .iterator();
  708. return new Iterator<Map.Entry<T, Integer>>() {
  709. private Entry<T, Integer> last = null;
  710.  
  711. @Override
  712. public boolean hasNext() {
  713. return itr.hasNext();
  714. }
  715.  
  716. @Override
  717. public java.util.Map.Entry<T, Integer> next() {
  718. return this.last = new Entry<T, Integer>() {
  719. final Entry<T, Integer> next = itr.next();
  720. final T t = this.next.getKey();
  721. int v = this.next.getValue();
  722.  
  723. @Override
  724. public T getKey() {
  725. return this.t;
  726. }
  727.  
  728. @Override
  729. public Integer getValue() {
  730. return this.v;
  731. }
  732.  
  733. @Override
  734. public Integer setValue(final Integer value) {
  735. requireNonNull(value, "value");
  736. final int val = value.intValue();
  737. if (val < 0)
  738. throw new IllegalArgumentException("value=" + val);
  739. if (val == 0)
  740. throw new IllegalArgumentException(
  741. "Can't set multiplicity to 0. Use remove() instead!");
  742. final int old = this.v;
  743. Multiset.this.setMultiplicity(this.t, val);
  744. this.v = val;
  745. return old;
  746. }
  747.  
  748. @Override
  749. public final int hashCode() {
  750. return Objects.hashCode(this.t) ^ this.v;
  751. }
  752.  
  753. @Override
  754. public final boolean equals(final Object o) {
  755. if (o == this)
  756. return true;
  757. if (o instanceof Map.Entry) {
  758. final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
  759. if (Objects.equals(this.t, e.getKey())
  760. && Objects.equals(this.v, e.getValue()))
  761. return true;
  762. }
  763. return false;
  764. }
  765.  
  766. @Override
  767. public String toString() {
  768. return this.t + "=" + this.v;
  769. }
  770. };
  771. }
  772.  
  773. @Override
  774. public void remove() {
  775. if (this.last == null)
  776. throw new NoSuchElementException();
  777. itr.remove();
  778. Multiset.this.size -= this.last.getValue();
  779. Multiset.this.checkSize();
  780. }
  781. };
  782.  
  783. }
  784.  
  785. @Override
  786. public int size() {
  787. return Multiset.this.map.size();
  788. }
  789.  
  790. @Override
  791. public boolean isEmpty() {
  792. return Multiset.this.map.isEmpty();
  793. }
  794.  
  795. @Override
  796. public boolean contains(final Object o) {
  797. return Multiset.this.map.keySet().contains(o);
  798. }
  799.  
  800. @Override
  801. public boolean add(final java.util.Map.Entry<T, Integer> e) {
  802. // NOT SUPPORTED!!!
  803. return Multiset.this.map.entrySet().add(e);
  804. }
  805.  
  806. @Override
  807. public boolean remove(final Object o) {
  808. return Multiset.this.map.entrySet().remove(o);
  809. }
  810.  
  811. @Override
  812. public boolean containsAll(final Collection<?> c) {
  813. return Multiset.this.map.entrySet().containsAll(c);
  814. }
  815.  
  816. @Override
  817. public void clear() {
  818. Multiset.this.map.clear();
  819. }
  820.  
  821. };
  822. }
  823. };
  824.  
  825. }
  826.  
  827. /**
  828. * Returns a set of all elements, without multiplicity. The set is backed by the multiset, so
  829. * changes to the multiset are reflected in the set, and vice-versa. Removing one element from the
  830. * set removes all equal elements from the multiset. It does not support the <code>add</code> or
  831. * <code>addAll</code>.
  832. *
  833. * <p>
  834. * If using the formal definition <code>(A, m)</code> of a multiset, the returned set is
  835. * <code>A</code> and <code>multiset::getMultiplicity</code> is <code>m</code>.
  836. *
  837. * @see #toSet()
  838. * @see #asMap()
  839. * @see #entries()
  840. * @return set-view of all elements
  841. */
  842. public Set<T> asSet() {
  843. return this.asMap().keySet();
  844. }
  845.  
  846. /**
  847. * Creates a synchronized (thread-safe) collection and a synchronized map, both backed by the
  848. * specified multiset. The collection behaves just like the specified multiset, while the map
  849. * corresponds to {@link #asMap()}. Both data structures are modifiable and use the created
  850. * collection as the mutex for synchronization.
  851. *
  852. * @see Collections#synchronizedCollection(Collection)
  853. *
  854. * @param set
  855. * the multiset
  856. * @param consumer
  857. * accepts the collection and the map.
  858. * @throws RuntimeException
  859. * if the security manager does not allow to create a SynchronizedMap by reflection.
  860. */
  861. @SuppressWarnings("unchecked")
  862. public static <T> void synchronizedMultiset(final Multiset<T> set,
  863. final BiConsumer<Collection<T>, Map<T, Integer>> consumer) throws RuntimeException {
  864. requireNonNull(set, "set");
  865. requireNonNull(consumer, "consumer");
  866. try {
  867. final Collection<T> collection = Collections.synchronizedCollection(set);
  868. final Class<? extends Map<T, Integer>> cls = (Class<? extends Map<T, Integer>>) Class
  869. .forName("java.util.Collections$SynchronizedMap");
  870. final Constructor<? extends Map<T, Integer>> ctor = //
  871. cls.getDeclaredConstructor(Map.class, Object.class);
  872. ctor.setAccessible(true);
  873. final Map<T, Integer> map = ctor.newInstance(set.asMap(), collection);
  874. consumer.accept(collection, map);
  875. } catch (InstantiationException | IllegalAccessException | IllegalArgumentException
  876. | InvocationTargetException | NoSuchMethodException | SecurityException
  877. | ClassNotFoundException ex) {
  878. throw new RuntimeException("Can't create synchronized Multiset.", ex);
  879. }
  880. }
  881.  
  882. static Multiset<?> emptyMultiset;
  883.  
  884. /** Returns an empty multiset (unmodifiable). */
  885. @SuppressWarnings("unchecked")
  886. public static <T> Multiset<T> emptyMultiset() {
  887. if (null == emptyMultiset)
  888. return (Multiset<T>) (emptyMultiset = new Multiset<T>(true));
  889. return (Multiset<T>) emptyMultiset;
  890. }
  891. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement