IndexedCollection.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.collections4.collection;

  18. import java.util.Collection;
  19. import java.util.HashMap;
  20. import java.util.Iterator;
  21. import java.util.Objects;
  22. import java.util.function.Predicate;

  23. import org.apache.commons.collections4.MultiMap;
  24. import org.apache.commons.collections4.Transformer;
  25. import org.apache.commons.collections4.map.MultiValueMap;

  26. /**
  27.  * An IndexedCollection is a Map-like view onto a Collection. It accepts a
  28.  * keyTransformer to define how the keys are converted from the values.
  29.  * <p>
  30.  * Modifications made to this decorator modify the index as well as the
  31.  * decorated {@link Collection}. However, modifications to the underlying
  32.  * {@link Collection} will not update the index and it will get out of sync.
  33.  * </p>
  34.  * <p>
  35.  * If modification of the decorated {@link Collection} is unavoidable, then a
  36.  * call to {@link #reindex()} will update the index to the current contents of
  37.  * the {@link Collection}.
  38.  * </p>
  39.  *
  40.  * @param <K> the type of object in the index.
  41.  * @param <C> the type of object in the collection.
  42.  * @since 4.0
  43.  */
  44. public class IndexedCollection<K, C> extends AbstractCollectionDecorator<C> {

  45.     // TODO: replace with MultiValuedMap

  46.     /** Serialization version */
  47.     private static final long serialVersionUID = -5512610452568370038L;

  48.     /**
  49.      * Create an {@link IndexedCollection} for a non-unique index.
  50.      *
  51.      * @param <K> the index object type.
  52.      * @param <C> the collection type.
  53.      * @param coll the decorated {@link Collection}.
  54.      * @param keyTransformer the {@link Transformer} for generating index keys.
  55.      * @return the created {@link IndexedCollection}.
  56.      */
  57.     public static <K, C> IndexedCollection<K, C> nonUniqueIndexedCollection(final Collection<C> coll,
  58.                                                                             final Transformer<C, K> keyTransformer) {
  59.         return new IndexedCollection<>(coll, keyTransformer,
  60.                                            MultiValueMap.<K, C>multiValueMap(new HashMap<>()),
  61.                                            false);
  62.     }

  63.     /**
  64.      * Create an {@link IndexedCollection} for a unique index.
  65.      * <p>
  66.      * If an element is added, which maps to an existing key, an {@link IllegalArgumentException}
  67.      * will be thrown.
  68.      *
  69.      * @param <K> the index object type.
  70.      * @param <C> the collection type.
  71.      * @param coll the decorated {@link Collection}.
  72.      * @param keyTransformer the {@link Transformer} for generating index keys.
  73.      * @return the created {@link IndexedCollection}.
  74.      */
  75.     public static <K, C> IndexedCollection<K, C> uniqueIndexedCollection(final Collection<C> coll,
  76.                                                                          final Transformer<C, K> keyTransformer) {
  77.         return new IndexedCollection<>(coll, keyTransformer,
  78.                                            MultiValueMap.<K, C>multiValueMap(new HashMap<>()),
  79.                                            true);
  80.     }

  81.     /** The {@link Transformer} for generating index keys. */
  82.     private final Transformer<C, K> keyTransformer;

  83.     /** The map of indexes to collected objects. */
  84.     private final MultiMap<K, C> index;

  85.     /** The uniqueness constraint for the index. */
  86.     private final boolean uniqueIndex;

  87.     /**
  88.      * Create a {@link IndexedCollection}.
  89.      *
  90.      * @param coll  decorated {@link Collection}
  91.      * @param keyTransformer  {@link Transformer} for generating index keys
  92.      * @param map  map to use as index
  93.      * @param uniqueIndex  if the index shall enforce uniqueness of index keys
  94.      */
  95.     public IndexedCollection(final Collection<C> coll, final Transformer<C, K> keyTransformer,
  96.                              final MultiMap<K, C> map, final boolean uniqueIndex) {
  97.         super(coll);
  98.         this.keyTransformer = keyTransformer;
  99.         this.index = map;
  100.         this.uniqueIndex = uniqueIndex;
  101.         reindex();
  102.     }

  103.     /**
  104.      * {@inheritDoc}
  105.      *
  106.      * @throws IllegalArgumentException if the object maps to an existing key and the index
  107.      *   enforces a uniqueness constraint
  108.      */
  109.     @Override
  110.     public boolean add(final C object) {
  111.         final boolean added = super.add(object);
  112.         if (added) {
  113.             addToIndex(object);
  114.         }
  115.         return added;
  116.     }

  117.     @Override
  118.     public boolean addAll(final Collection<? extends C> coll) {
  119.         boolean changed = false;
  120.         for (final C c: coll) {
  121.             changed |= add(c);
  122.         }
  123.         return changed;
  124.     }

  125.     /**
  126.      * Provides checking for adding the index.
  127.      *
  128.      * @param object the object to index
  129.      * @throws IllegalArgumentException if the object maps to an existing key and the index
  130.      *   enforces a uniqueness constraint
  131.      */
  132.     private void addToIndex(final C object) {
  133.         final K key = keyTransformer.apply(object);
  134.         if (uniqueIndex && index.containsKey(key)) {
  135.             throw new IllegalArgumentException("Duplicate key in uniquely indexed collection.");
  136.         }
  137.         index.put(key, object);
  138.     }

  139.     @Override
  140.     public void clear() {
  141.         super.clear();
  142.         index.clear();
  143.     }

  144.     /**
  145.      * {@inheritDoc}
  146.      * <p>
  147.      * Note: uses the index for fast lookup
  148.      */
  149.     @SuppressWarnings("unchecked")
  150.     @Override
  151.     public boolean contains(final Object object) {
  152.         return index.containsKey(keyTransformer.apply((C) object));
  153.     }

  154.     /**
  155.      * {@inheritDoc}
  156.      * <p>
  157.      * Note: uses the index for fast lookup
  158.      */
  159.     @Override
  160.     public boolean containsAll(final Collection<?> coll) {
  161.         for (final Object o : coll) {
  162.             if (!contains(o)) {
  163.                 return false;
  164.             }
  165.         }
  166.         return true;
  167.     }

  168.     /**
  169.      * Gets the element associated with the given key.
  170.      * <p>
  171.      * In case of a non-unique index, this method will return the first
  172.      * value associated with the given key. To retrieve all elements associated
  173.      * with a key, use {@link #values(Object)}.
  174.      *
  175.      * @param key  key to look up
  176.      * @return element found
  177.      * @see #values(Object)
  178.      */
  179.     public C get(final K key) {
  180.         @SuppressWarnings("unchecked") // index is a MultiMap which returns a Collection
  181.         final Collection<C> coll = (Collection<C>) index.get(key);
  182.         return coll == null ? null : coll.iterator().next();
  183.     }

  184.     /**
  185.      * Clears the index and re-indexes the entire decorated {@link Collection}.
  186.      */
  187.     public void reindex() {
  188.         index.clear();
  189.         for (final C c : decorated()) {
  190.             addToIndex(c);
  191.         }
  192.     }

  193.     @SuppressWarnings("unchecked")
  194.     @Override
  195.     public boolean remove(final Object object) {
  196.         final boolean removed = super.remove(object);
  197.         if (removed) {
  198.             removeFromIndex((C) object);
  199.         }
  200.         return removed;
  201.     }

  202.     @Override
  203.     public boolean removeAll(final Collection<?> coll) {
  204.         boolean changed = false;
  205.         for (final Object o : coll) {
  206.             changed |= remove(o);
  207.         }
  208.         return changed;
  209.     }

  210.     /**
  211.      * Removes an object from the index.
  212.      *
  213.      * @param object the object to remove
  214.      */
  215.     private void removeFromIndex(final C object) {
  216.         index.remove(keyTransformer.apply(object));
  217.     }

  218.     /**
  219.      * @since 4.4
  220.      */
  221.     @Override
  222.     public boolean removeIf(final Predicate<? super C> filter) {
  223.         if (Objects.isNull(filter)) {
  224.             return false;
  225.         }
  226.         boolean changed = false;
  227.         final Iterator<C> it = iterator();
  228.         while (it.hasNext()) {
  229.             if (filter.test(it.next())) {
  230.                 it.remove();
  231.                 changed = true;
  232.             }
  233.         }
  234.         if (changed) {
  235.             reindex();
  236.         }
  237.         return changed;
  238.     }

  239.     @Override
  240.     public boolean retainAll(final Collection<?> coll) {
  241.         final boolean changed = super.retainAll(coll);
  242.         if (changed) {
  243.             reindex();
  244.         }
  245.         return changed;
  246.     }

  247.     /**
  248.      * Gets all elements associated with the given key.
  249.      *
  250.      * @param key  key to look up
  251.      * @return a collection of elements found, or null if {@code contains(key) == false}
  252.      */
  253.     @SuppressWarnings("unchecked") // index is a MultiMap which returns a Collection
  254.     public Collection<C> values(final K key) {
  255.         return (Collection<C>) index.get(key);
  256.     }

  257. }