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 */
043public class IndexedCollection<K, C> extends AbstractCollectionDecorator<C> {
044
045    // TODO: replace with MultiValuedMap
046
047    /** Serialization version */
048    private static final long serialVersionUID = -5512610452568370038L;
049
050    /** The {@link Transformer} for generating index keys. */
051    private final Transformer<C, K> keyTransformer;
052
053    /** The map of indexes to collected objects. */
054    private final MultiMap<K, C> index;
055
056    /** The uniqueness constraint for the index. */
057    private final boolean uniqueIndex;
058
059    /**
060     * Create an {@link IndexedCollection} for a unique index.
061     * <p>
062     * If an element is added, which maps to an existing key, an {@link IllegalArgumentException}
063     * will be thrown.
064     *
065     * @param <K> the index object type.
066     * @param <C> the collection type.
067     * @param coll the decorated {@link Collection}.
068     * @param keyTransformer the {@link Transformer} for generating index keys.
069     * @return the created {@link IndexedCollection}.
070     */
071    public static <K, C> IndexedCollection<K, C> uniqueIndexedCollection(final Collection<C> coll,
072                                                                         final Transformer<C, K> keyTransformer) {
073        return new IndexedCollection<>(coll, keyTransformer,
074                                           MultiValueMap.<K, C>multiValueMap(new HashMap<K, Collection<C>>()),
075                                           true);
076    }
077
078    /**
079     * Create an {@link IndexedCollection} for a non-unique index.
080     *
081     * @param <K> the index object type.
082     * @param <C> the collection type.
083     * @param coll the decorated {@link Collection}.
084     * @param keyTransformer the {@link Transformer} for generating index keys.
085     * @return the created {@link IndexedCollection}.
086     */
087    public static <K, C> IndexedCollection<K, C> nonUniqueIndexedCollection(final Collection<C> coll,
088                                                                            final Transformer<C, K> keyTransformer) {
089        return new IndexedCollection<>(coll, keyTransformer,
090                                           MultiValueMap.<K, C>multiValueMap(new HashMap<K, Collection<C>>()),
091                                           false);
092    }
093
094    /**
095     * Create a {@link IndexedCollection}.
096     *
097     * @param coll  decorated {@link Collection}
098     * @param keyTransformer  {@link Transformer} for generating index keys
099     * @param map  map to use as index
100     * @param uniqueIndex  if the index shall enforce uniqueness of index keys
101     */
102    public IndexedCollection(final Collection<C> coll, final Transformer<C, K> keyTransformer,
103                             final MultiMap<K, C> map, final boolean uniqueIndex) {
104        super(coll);
105        this.keyTransformer = keyTransformer;
106        this.index = map;
107        this.uniqueIndex = uniqueIndex;
108        reindex();
109    }
110
111    /**
112     * {@inheritDoc}
113     *
114     * @throws IllegalArgumentException if the object maps to an existing key and the index
115     *   enforces a uniqueness constraint
116     */
117    @Override
118    public boolean add(final C object) {
119        final boolean added = super.add(object);
120        if (added) {
121            addToIndex(object);
122        }
123        return added;
124    }
125
126    @Override
127    public boolean addAll(final Collection<? extends C> coll) {
128        boolean changed = false;
129        for (final C c: coll) {
130            changed |= add(c);
131        }
132        return changed;
133    }
134
135    @Override
136    public void clear() {
137        super.clear();
138        index.clear();
139    }
140
141    /**
142     * {@inheritDoc}
143     * <p>
144     * Note: uses the index for fast lookup
145     */
146    @SuppressWarnings("unchecked")
147    @Override
148    public boolean contains(final Object object) {
149        return index.containsKey(keyTransformer.transform((C) object));
150    }
151
152    /**
153     * {@inheritDoc}
154     * <p>
155     * Note: uses the index for fast lookup
156     */
157    @Override
158    public boolean containsAll(final Collection<?> coll) {
159        for (final Object o : coll) {
160            if (!contains(o)) {
161                return false;
162            }
163        }
164        return true;
165    }
166
167    /**
168     * Get the element associated with the given key.
169     * <p>
170     * In case of a non-unique index, this method will return the first
171     * value associated with the given key. To retrieve all elements associated
172     * with a key, use {@link #values(Object)}.
173     *
174     * @param key  key to look up
175     * @return element found
176     * @see #values(Object)
177     */
178    public C get(final K key) {
179        @SuppressWarnings("unchecked") // index is a MultiMap which returns a Collection
180        final Collection<C> coll = (Collection<C>) index.get(key);
181        return coll == null ? null : coll.iterator().next();
182    }
183
184    /**
185     * Get all elements associated with the given key.
186     *
187     * @param key  key to look up
188     * @return a collection of elements found, or null if {@code contains(key) == false}
189     */
190    @SuppressWarnings("unchecked") // index is a MultiMap which returns a Collection
191    public Collection<C> values(final K key) {
192        return (Collection<C>) index.get(key);
193    }
194
195    /**
196     * Clears the index and re-indexes the entire decorated {@link Collection}.
197     */
198    public void reindex() {
199        index.clear();
200        for (final C c : decorated()) {
201            addToIndex(c);
202        }
203    }
204
205    @SuppressWarnings("unchecked")
206    @Override
207    public boolean remove(final Object object) {
208        final boolean removed = super.remove(object);
209        if (removed) {
210            removeFromIndex((C) object);
211        }
212        return removed;
213    }
214
215    @Override
216    public boolean removeAll(final Collection<?> coll) {
217        boolean changed = false;
218        for (final Object o : coll) {
219            changed |= remove(o);
220        }
221        return changed;
222    }
223
224    @Override
225    public boolean retainAll(final Collection<?> coll) {
226        final boolean changed = super.retainAll(coll);
227        if (changed) {
228            reindex();
229        }
230        return changed;
231    }
232
233    //-----------------------------------------------------------------------
234
235    /**
236     * Provides checking for adding the index.
237     *
238     * @param object the object to index
239     * @throws IllegalArgumentException if the object maps to an existing key and the index
240     *   enforces a uniqueness constraint
241     */
242    private void addToIndex(final C object) {
243        final K key = keyTransformer.transform(object);
244        if (uniqueIndex && index.containsKey(key)) {
245            throw new IllegalArgumentException("Duplicate key in uniquely indexed collection.");
246        }
247        index.put(key, object);
248    }
249
250    /**
251     * Removes an object from the index.
252     *
253     * @param object the object to remove
254     */
255    private void removeFromIndex(final C object) {
256        index.remove(keyTransformer.transform(object));
257    }
258
259}