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; 021import java.util.Iterator; 022import java.util.Objects; 023import java.util.function.Predicate; 024 025import org.apache.commons.collections4.MultiMap; 026import org.apache.commons.collections4.Transformer; 027import org.apache.commons.collections4.map.MultiValueMap; 028 029/** 030 * An IndexedCollection is a Map-like view onto a Collection. It accepts a 031 * keyTransformer to define how the keys are converted from the values. 032 * <p> 033 * Modifications made to this decorator modify the index as well as the 034 * decorated {@link Collection}. However, modifications to the underlying 035 * {@link Collection} will not update the index and it will get out of sync. 036 * </p> 037 * <p> 038 * If modification of the decorated {@link Collection} is unavoidable, then a 039 * call to {@link #reindex()} will update the index to the current contents of 040 * the {@link Collection}. 041 * </p> 042 * 043 * @param <K> the type of object in the index. 044 * @param <C> the type of object in the collection. 045 * 046 * @since 4.0 047 */ 048public class IndexedCollection<K, C> extends AbstractCollectionDecorator<C> { 049 050 // TODO: replace with MultiValuedMap 051 052 /** Serialization version */ 053 private static final long serialVersionUID = -5512610452568370038L; 054 055 /** 056 * Create an {@link IndexedCollection} for a non-unique index. 057 * 058 * @param <K> the index object type. 059 * @param <C> the collection type. 060 * @param coll the decorated {@link Collection}. 061 * @param keyTransformer the {@link Transformer} for generating index keys. 062 * @return the created {@link IndexedCollection}. 063 */ 064 public static <K, C> IndexedCollection<K, C> nonUniqueIndexedCollection(final Collection<C> coll, 065 final Transformer<C, K> keyTransformer) { 066 return new IndexedCollection<>(coll, keyTransformer, 067 MultiValueMap.<K, C>multiValueMap(new HashMap<>()), 068 false); 069 } 070 071 /** 072 * Create an {@link IndexedCollection} for a unique index. 073 * <p> 074 * If an element is added, which maps to an existing key, an {@link IllegalArgumentException} 075 * will be thrown. 076 * 077 * @param <K> the index object type. 078 * @param <C> the collection type. 079 * @param coll the decorated {@link Collection}. 080 * @param keyTransformer the {@link Transformer} for generating index keys. 081 * @return the created {@link IndexedCollection}. 082 */ 083 public static <K, C> IndexedCollection<K, C> uniqueIndexedCollection(final Collection<C> coll, 084 final Transformer<C, K> keyTransformer) { 085 return new IndexedCollection<>(coll, keyTransformer, 086 MultiValueMap.<K, C>multiValueMap(new HashMap<>()), 087 true); 088 } 089 090 /** The {@link Transformer} for generating index keys. */ 091 private final Transformer<C, K> keyTransformer; 092 093 /** The map of indexes to collected objects. */ 094 private final MultiMap<K, C> index; 095 096 /** The uniqueness constraint for the index. */ 097 private final boolean uniqueIndex; 098 099 /** 100 * Create a {@link IndexedCollection}. 101 * 102 * @param coll decorated {@link Collection} 103 * @param keyTransformer {@link Transformer} for generating index keys 104 * @param map map to use as index 105 * @param uniqueIndex if the index shall enforce uniqueness of index keys 106 */ 107 public IndexedCollection(final Collection<C> coll, final Transformer<C, K> keyTransformer, 108 final MultiMap<K, C> map, final boolean uniqueIndex) { 109 super(coll); 110 this.keyTransformer = keyTransformer; 111 this.index = map; 112 this.uniqueIndex = uniqueIndex; 113 reindex(); 114 } 115 116 /** 117 * {@inheritDoc} 118 * 119 * @throws IllegalArgumentException if the object maps to an existing key and the index 120 * enforces a uniqueness constraint 121 */ 122 @Override 123 public boolean add(final C object) { 124 final boolean added = super.add(object); 125 if (added) { 126 addToIndex(object); 127 } 128 return added; 129 } 130 131 @Override 132 public boolean addAll(final Collection<? extends C> coll) { 133 boolean changed = false; 134 for (final C c: coll) { 135 changed |= add(c); 136 } 137 return changed; 138 } 139 140 /** 141 * Provides checking for adding the index. 142 * 143 * @param object the object to index 144 * @throws IllegalArgumentException if the object maps to an existing key and the index 145 * enforces a uniqueness constraint 146 */ 147 private void addToIndex(final C object) { 148 final K key = keyTransformer.transform(object); 149 if (uniqueIndex && index.containsKey(key)) { 150 throw new IllegalArgumentException("Duplicate key in uniquely indexed collection."); 151 } 152 index.put(key, object); 153 } 154 155 @Override 156 public void clear() { 157 super.clear(); 158 index.clear(); 159 } 160 161 /** 162 * {@inheritDoc} 163 * <p> 164 * Note: uses the index for fast lookup 165 */ 166 @SuppressWarnings("unchecked") 167 @Override 168 public boolean contains(final Object object) { 169 return index.containsKey(keyTransformer.transform((C) object)); 170 } 171 172 /** 173 * {@inheritDoc} 174 * <p> 175 * Note: uses the index for fast lookup 176 */ 177 @Override 178 public boolean containsAll(final Collection<?> coll) { 179 for (final Object o : coll) { 180 if (!contains(o)) { 181 return false; 182 } 183 } 184 return true; 185 } 186 187 /** 188 * Gets the element associated with the given key. 189 * <p> 190 * In case of a non-unique index, this method will return the first 191 * value associated with the given key. To retrieve all elements associated 192 * with a key, use {@link #values(Object)}. 193 * 194 * @param key key to look up 195 * @return element found 196 * @see #values(Object) 197 */ 198 public C get(final K key) { 199 @SuppressWarnings("unchecked") // index is a MultiMap which returns a Collection 200 final Collection<C> coll = (Collection<C>) index.get(key); 201 return coll == null ? null : coll.iterator().next(); 202 } 203 204 /** 205 * Clears the index and re-indexes the entire decorated {@link Collection}. 206 */ 207 public void reindex() { 208 index.clear(); 209 for (final C c : decorated()) { 210 addToIndex(c); 211 } 212 } 213 214 @SuppressWarnings("unchecked") 215 @Override 216 public boolean remove(final Object object) { 217 final boolean removed = super.remove(object); 218 if (removed) { 219 removeFromIndex((C) object); 220 } 221 return removed; 222 } 223 224 @Override 225 public boolean removeAll(final Collection<?> coll) { 226 boolean changed = false; 227 for (final Object o : coll) { 228 changed |= remove(o); 229 } 230 return changed; 231 } 232 233 /** 234 * Removes an object from the index. 235 * 236 * @param object the object to remove 237 */ 238 private void removeFromIndex(final C object) { 239 index.remove(keyTransformer.transform(object)); 240 } 241 242 /** 243 * @since 4.4 244 */ 245 @Override 246 public boolean removeIf(final Predicate<? super C> filter) { 247 if (Objects.isNull(filter)) { 248 return false; 249 } 250 boolean changed = false; 251 final Iterator<C> it = iterator(); 252 while (it.hasNext()) { 253 if (filter.test(it.next())) { 254 it.remove(); 255 changed = true; 256 } 257 } 258 if (changed) { 259 reindex(); 260 } 261 return changed; 262 } 263 264 @Override 265 public boolean retainAll(final Collection<?> coll) { 266 final boolean changed = super.retainAll(coll); 267 if (changed) { 268 reindex(); 269 } 270 return changed; 271 } 272 273 /** 274 * Gets all elements associated with the given key. 275 * 276 * @param key key to look up 277 * @return a collection of elements found, or null if {@code contains(key) == false} 278 */ 279 @SuppressWarnings("unchecked") // index is a MultiMap which returns a Collection 280 public Collection<C> values(final K key) { 281 return (Collection<C>) index.get(key); 282 } 283 284}