001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections4.collection;
018
019import java.util.Collection;
020import java.util.HashMap;
021
022import org.apache.commons.collections4.MultiMap;
023import org.apache.commons.collections4.Transformer;
024import org.apache.commons.collections4.map.MultiValueMap;
025
026/**
027 * An IndexedCollection is a Map-like view onto a Collection. It accepts a
028 * keyTransformer to define how the keys are converted from the values.
029 * <p>
030 * Modifications made to this decorator modify the index as well as the
031 * decorated {@link Collection}. However, modifications to the underlying
032 * {@link Collection} will not update the index and it will get out of sync.
033 * <p>
034 * If modification of the decorated {@link Collection} is unavoidable, then a
035 * call to {@link #reindex()} will update the index to the current contents of
036 * the {@link Collection}.
037 *
038 * @param <K> the type of object in the index.
039 * @param <C> the type of object in the collection.
040 *
041 * @since 4.0
042 * @version $Id: IndexedCollection.html 972421 2015-11-14 20:00:04Z tn $
043 */
044public class IndexedCollection<K, C> extends AbstractCollectionDecorator<C> {
045
046    /** Serialization version */
047    private static final long serialVersionUID = -5512610452568370038L;
048
049    /** The {@link Transformer} for generating index keys. */
050    private final Transformer<C, K> keyTransformer;
051
052    /** The map of indexes to collected objects. */
053    private final MultiMap<K, C> index;
054
055    /** The uniqueness constraint for the index. */
056    private final boolean uniqueIndex;
057
058    /**
059     * Create an {@link IndexedCollection} for a unique index.
060     * <p>
061     * If an element is added, which maps to an existing key, an {@link IllegalArgumentException}
062     * will be thrown.
063     *
064     * @param <K> the index object type.
065     * @param <C> the collection type.
066     * @param coll the decorated {@link Collection}.
067     * @param keyTransformer the {@link Transformer} for generating index keys.
068     * @return the created {@link IndexedCollection}.
069     */
070    public static <K, C> IndexedCollection<K, C> uniqueIndexedCollection(final Collection<C> coll,
071                                                                         final Transformer<C, K> keyTransformer) {
072        return new IndexedCollection<K, C>(coll, keyTransformer,
073                                           MultiValueMap.<K, C>multiValueMap(new HashMap<K, Collection<C>>()),
074                                           true);
075    }
076
077    /**
078     * Create an {@link IndexedCollection} for a non-unique index.
079     *
080     * @param <K> the index object type.
081     * @param <C> the collection type.
082     * @param coll the decorated {@link Collection}.
083     * @param keyTransformer the {@link Transformer} for generating index keys.
084     * @return the created {@link IndexedCollection}.
085     */
086    public static <K, C> IndexedCollection<K, C> nonUniqueIndexedCollection(final Collection<C> coll,
087                                                                            final Transformer<C, K> keyTransformer) {
088        return new IndexedCollection<K, C>(coll, keyTransformer,
089                                           MultiValueMap.<K, C>multiValueMap(new HashMap<K, Collection<C>>()),
090                                           false);
091    }
092
093    /**
094     * Create a {@link IndexedCollection}.
095     *
096     * @param coll  decorated {@link Collection}
097     * @param keyTransformer  {@link Transformer} for generating index keys
098     * @param map  map to use as index
099     * @param uniqueIndex  if the index shall enforce uniqueness of index keys
100     */
101    public IndexedCollection(final Collection<C> coll, final Transformer<C, K> keyTransformer,
102                             final MultiMap<K, C> map, final boolean uniqueIndex) {
103        super(coll);
104        this.keyTransformer = keyTransformer;
105        this.index = map;
106        this.uniqueIndex = uniqueIndex;
107        reindex();
108    }
109
110    /**
111     * {@inheritDoc}
112     *
113     * @throws IllegalArgumentException if the object maps to an existing key and the index
114     *   enforces a uniqueness constraint
115     */
116    @Override
117    public boolean add(final C object) {
118        final boolean added = super.add(object);
119        if (added) {
120            addToIndex(object);
121        }
122        return added;
123    }
124
125    @Override
126    public boolean addAll(final Collection<? extends C> coll) {
127        boolean changed = false;
128        for (final C c: coll) {
129            changed |= add(c);
130        }
131        return changed;
132    }
133
134    @Override
135    public void clear() {
136        super.clear();
137        index.clear();
138    }
139
140    /**
141     * {@inheritDoc}
142     * <p>
143     * Note: uses the index for fast lookup
144     */
145    @SuppressWarnings("unchecked")
146    @Override
147    public boolean contains(final Object object) {
148        return index.containsKey(keyTransformer.transform((C) object));
149    }
150
151    /**
152     * {@inheritDoc}
153     * <p>
154     * Note: uses the index for fast lookup
155     */
156    @Override
157    public boolean containsAll(final Collection<?> coll) {
158        for (final Object o : coll) {
159            if (!contains(o)) {
160                return false;
161            }
162        }
163        return true;
164    }
165
166    /**
167     * Get the element associated with the given key.
168     * <p>
169     * In case of a non-unique index, this method will return the first
170     * value associated with the given key. To retrieve all elements associated
171     * with a key, use {@link #values(Object)}.
172     *
173     * @param key  key to look up
174     * @return element found
175     * @see #values(Object)
176     */
177    public C get(final K key) {
178        @SuppressWarnings("unchecked") // index is a MultiMap which returns a Collection
179        final Collection<C> coll = (Collection<C>) index.get(key);
180        return coll == null ? null : coll.iterator().next();
181    }
182
183    /**
184     * Get all elements associated with the given key.
185     *
186     * @param key  key to look up
187     * @return a collection of elements found, or null if {@code contains(key) == false}
188     */
189    @SuppressWarnings("unchecked") // index is a MultiMap which returns a Collection
190    public Collection<C> values(final K key) {
191        return (Collection<C>) index.get(key);
192    }
193
194    /**
195     * Clears the index and re-indexes the entire decorated {@link Collection}.
196     */
197    public void reindex() {
198        index.clear();
199        for (final C c : decorated()) {
200            addToIndex(c);
201        }
202    }
203
204    @SuppressWarnings("unchecked")
205    @Override
206    public boolean remove(final Object object) {
207        final boolean removed = super.remove(object);
208        if (removed) {
209            removeFromIndex((C) object);
210        }
211        return removed;
212    }
213
214    @Override
215    public boolean removeAll(final Collection<?> coll) {
216        boolean changed = false;
217        for (final Object o : coll) {
218            changed |= remove(o);
219        }
220        return changed;
221    }
222
223    @Override
224    public boolean retainAll(final Collection<?> coll) {
225        final boolean changed = super.retainAll(coll);
226        if (changed) {
227            reindex();
228        }
229        return changed;
230    }
231
232    //-----------------------------------------------------------------------
233
234    /**
235     * Provides checking for adding the index.
236     *
237     * @param object the object to index
238     * @throws IllegalArgumentException if the object maps to an existing key and the index
239     *   enforces a uniqueness constraint
240     */
241    private void addToIndex(final C object) {
242        final K key = keyTransformer.transform(object);
243        if (uniqueIndex && index.containsKey(key)) {
244            throw new IllegalArgumentException("Duplicate key in uniquely indexed collection.");
245        }
246        index.put(key, object);
247    }
248
249    /**
250     * Removes an object from the index.
251     *
252     * @param object the object to remove
253     */
254    private void removeFromIndex(final C object) {
255        index.remove(keyTransformer.transform(object));
256    }
257
258}