001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.commons.smartcollections; 018 019import java.util.Collection; 020import java.util.Iterator; 021import java.util.Objects; 022 023import net.automatalib.commons.util.array.ResizingObjectArray; 024 025 026/** 027 * This class implements a collection for storing objects in no 028 * particular order. 029 * 030 * It supports (amortized) constant time insertion and removal. Removal does 031 * not invalidate the references of other objects, and can be performed during 032 * iteration (using the respective {@link Iterator#remove()} method). 033 * 034 * @author Malte Isberner <malte.isberner@gmail.com> 035 * 036 * @param <E> element class. 037 */ 038public class UnorderedCollection<E> extends AbstractSmartCollection<E> 039 implements CapacityManagement { 040 041 /* 042 * The reference for this collection, effectively containing 043 * an index in addition to the element itself. 044 */ 045 private static class Reference<E> implements ElementReference { 046 public E element; 047 public int index; 048 049 /** 050 * Constructor. 051 * @param element the stored element. 052 * @param index its index. 053 */ 054 public Reference(E element, int index) { 055 this.element = element; 056 this.index = index; 057 } 058 } 059 060 /* 061 * The iterator for iterating over the element references. 062 */ 063 private class ReferenceIterator implements Iterator<ElementReference> { 064 private int index; 065 066 /* 067 * (non-Javadoc) 068 * @see java.util.Iterator#hasNext() 069 */ 070 @Override 071 public boolean hasNext() { 072 return (index < size); 073 } 074 075 /* 076 * (non-Javadoc) 077 * @see java.util.Iterator#next() 078 */ 079 @Override 080 public ElementReference next() { 081 return (ElementReference)storage.array[index++]; 082 } 083 084 /* 085 * (non-Javadoc) 086 * @see java.util.Iterator#remove() 087 */ 088 @Override 089 public void remove() { 090 UnorderedCollection.this.remove(--index); 091 } 092 } 093 094 /* 095 * The iterator for iterating over the elements themselves. 096 */ 097 private class ElementIterator implements Iterator<E> { 098 private int index; 099 100 /* 101 * (non-Javadoc) 102 * @see java.util.Iterator#hasNext() 103 */ 104 @Override 105 public boolean hasNext() { 106 return (index < size); 107 } 108 109 /* 110 * (non-Javadoc) 111 * @see java.util.Iterator#next() 112 */ 113 @Override 114 @SuppressWarnings("unchecked") 115 public E next() { 116 return ((Reference<E>)storage.array[index++]).element; 117 } 118 119 /* 120 * (non-Javadoc) 121 * @see java.util.Iterator#remove() 122 */ 123 @Override 124 public void remove() { 125 UnorderedCollection.this.remove(--index); 126 } 127 } 128 129 private static final int DEFAULT_INITIAL_CAPACITY = 10; 130 131 132 // The collection's storage 133 private final ResizingObjectArray storage; 134 private int size; 135 136 /** 137 * Default constructor. Reserves capacity for 10 elements. 138 */ 139 public UnorderedCollection() { 140 this(DEFAULT_INITIAL_CAPACITY); 141 } 142 143 /** 144 * Constructor. Reserves the specified initial capacity. 145 * @param initialCapacity the number of elements to reserve capacity 146 * for. 147 */ 148 public UnorderedCollection(int initialCapacity) { 149 if(initialCapacity <= 0) 150 initialCapacity = DEFAULT_INITIAL_CAPACITY; 151 this.storage 152 = new ResizingObjectArray(initialCapacity); 153 154 } 155 156 /** 157 * Constructor. Initializes the collection with the contents of the 158 * specified collection. 159 * @param coll the collection. 160 */ 161 public UnorderedCollection(Collection<? extends E> coll) { 162 this(coll.size()); 163 addAll(coll); 164 } 165 166 167 /* 168 * Convenience method, renders a plain cast obsolete and throws a 169 * more specific exception if the cast fails. 170 */ 171 @SuppressWarnings("unchecked") 172 private static <E> Reference<E> asIndexedRef(ElementReference ref) { 173 if(ref.getClass() != Reference.class) 174 throw new InvalidReferenceException("Reference is of wrong class '" 175 + ref.getClass().getName() 176 + "', should be " + Reference.class.getName() + "."); 177 return (Reference<E>)ref; 178 } 179 180 181 /* 182 * Convenience method for extracting the index stored in an 183 * ElementReference, and throws a more specific exception if the 184 * cast fails or the index is not valid. 185 */ 186 private int extractValidIndex(ElementReference ref) { 187 Reference<E> iRef = asIndexedRef(ref); 188 int idx = iRef.index; 189 if(idx < 0 || idx >= size) 190 throw new InvalidReferenceException("Index " + idx 191 + " is not valid for collection with size " + size + "."); 192 return idx; 193 } 194 195 196 /* 197 * (non-Javadoc) 198 * @see de.ls5.collections.SmartCollection#get(de.ls5.collections.ElementReference) 199 */ 200 @Override 201 public E get(ElementReference ref) { 202 Reference<E> r = asIndexedRef(ref); 203 return r.element; 204 } 205 206 207 /* 208 * (non-Javadoc) 209 * @see de.ls5.collections.SmartCollection#referencedAdd(java.lang.Object) 210 */ 211 @Override 212 public ElementReference referencedAdd(E elem) { 213 ensureCapacity(size+1); 214 int insertPos = size++; 215 Reference<E> ref = new Reference<E>(elem, insertPos); 216 storage.array[insertPos] = ref; 217 return ref; 218 } 219 220 /* 221 * (non-Javadoc) 222 * @see de.ls5.collections.AbstractSmartCollection#addAll(T[]) 223 */ 224 @Override 225 public <T extends E> void addAll(T[] array) { 226 int sizeInc = array.length; 227 ensureCapacity(size+sizeInc); 228 for(int index = size, i = 0; i < array.length; index++, i++) 229 storage.array[index] = new Reference<E>(array[i], index); 230 size += sizeInc; 231 } 232 233 /* 234 * (non-Javadoc) 235 * @see java.util.AbstractCollection#addAll(java.util.Collection) 236 */ 237 @Override 238 public boolean addAll(Collection<? extends E> coll) { 239 int sizeInc = coll.size(); 240 ensureCapacity(size+sizeInc); 241 for(E elem : coll) 242 storage.array[size] = new Reference<E>(elem, size); 243 size += sizeInc; 244 245 return true; 246 } 247 248 /* 249 * (non-Javadoc) 250 * @see java.util.AbstractCollection#isEmpty() 251 */ 252 @Override 253 public boolean isEmpty() { 254 return (size == 0); 255 } 256 257 /* 258 * (non-Javadoc) 259 * @see de.ls5.collections.SmartCollection#referenceIterator() 260 */ 261 @Override 262 public Iterator<ElementReference> referenceIterator() { 263 return new ReferenceIterator(); 264 } 265 266 /* 267 * (non-Javadoc) 268 * @see de.ls5.collections.AbstractSmartCollection#references() 269 */ 270 @Override 271 public Iterable<ElementReference> references() { 272 return new Iterable<ElementReference>() { 273 @Override 274 public Iterator<ElementReference> iterator() { 275 return referenceIterator(); 276 } 277 }; 278 } 279 280 /* 281 * Removes an element by its index. 282 */ 283 @SuppressWarnings("unchecked") 284 private void remove(int index) { 285 int lastIndex = --size; 286 Reference<E> removed = (Reference<E>)storage.array[index]; 287 Reference<E> lastElem = (Reference<E>)storage.array[lastIndex]; 288 storage.array[index] = lastElem; 289 lastElem.index = index; 290 removed.index = -1; 291 storage.array[lastIndex] = null; 292 } 293 294 /* 295 * (non-Javadoc) 296 * @see de.ls5.collections.SmartCollection#remove(de.ls5.collections.ElementReference) 297 */ 298 @Override 299 public void remove(ElementReference ref) { 300 remove(extractValidIndex(ref)); 301 } 302 303 304 /* 305 * (non-Javadoc) 306 * @see java.util.AbstractCollection#remove(java.lang.Object) 307 */ 308 @Override 309 public boolean remove(Object elem) { 310 for(int i = 0; i < size; i++) { 311 if(Objects.equals(storage.array[i], elem)) { 312 remove(i); 313 return true; 314 } 315 } 316 return false; 317 } 318 319 /* 320 * (non-Javadoc) 321 * @see java.util.AbstractCollection#size() 322 */ 323 @Override 324 public int size() { 325 return size; 326 } 327 328 /* 329 * (non-Javadoc) 330 * @see java.util.AbstractCollection#iterator() 331 */ 332 @Override 333 public Iterator<E> iterator() { 334 return new ElementIterator(); 335 } 336 337 338 339 /* 340 * (non-Javadoc) 341 * @see java.util.AbstractCollection#clear() 342 */ 343 @Override 344 @SuppressWarnings("unchecked") 345 public void clear() { 346 for(int i = 0; i < size; i++) { 347 ((Reference<E>)storage.array[i]).index = -1; 348 storage.array[i] = null; 349 } 350 size = 0; 351 } 352 353 /* 354 * (non-Javadoc) 355 * @see de.ls5.collections.SmartCollection#choose() 356 */ 357 @Override 358 @SuppressWarnings("unchecked") 359 public E choose() { 360 if(size == 0) 361 return null; 362 return ((Reference<E>)storage.array[0]).element; 363 } 364 365 366 /* 367 * (non-Javadoc) 368 * @see de.ls5.collections.SmartCollection#chooseRef() 369 */ 370 @Override 371 public ElementReference chooseRef() { 372 if(size == 0) 373 return null; 374 return (ElementReference)storage.array[0]; 375 } 376 377 /* 378 * (non-Javadoc) 379 * @see de.ls5.collections.SmartCollection#replace(de.ls5.collections.ElementReference, java.lang.Object) 380 */ 381 @Override 382 @SuppressWarnings("unchecked") 383 public void replace(ElementReference ref, E newElement) { 384 int idx = extractValidIndex(ref); 385 ((Reference<E>)storage.array[idx]).element = newElement; 386 } 387 388 /* 389 * (non-Javadoc) 390 * @see de.ls5.smartcollections.CapacityManagement#ensureCapacity(int) 391 */ 392 @Override 393 public boolean ensureCapacity(int minCapacity) { 394 return storage.ensureCapacity(minCapacity); 395 } 396 397 /* 398 * (non-Javadoc) 399 * @see de.ls5.smartcollections.CapacityManagement#ensureAdditionalCapacity(int) 400 */ 401 @Override 402 public boolean ensureAdditionalCapacity(int additionalSpace) { 403 return ensureCapacity(size+additionalSpace); 404 } 405 406 /* 407 * (non-Javadoc) 408 * @see de.ls5.smartcollections.CapacityManagement#hintNextCapacity(int) 409 */ 410 @Override 411 public void hintNextCapacity(int nextCapacityHint) { 412 storage.hintNextCapacity(nextCapacityHint); 413 } 414 415 /* 416 * (non-Javadoc) 417 * @see de.ls5.smartcollections.SmartCollection#deepClear() 418 */ 419 @Override 420 public void deepClear() { 421 storage.setAll(null); 422 } 423 424 /* 425 * (non-Javadoc) 426 * @see de.ls5.smartcollections.SmartCollection#quickClear() 427 */ 428 @Override 429 public void quickClear() { 430 size = 0; 431 } 432 433 /** 434 * Swaps the contents of this {@link UnorderedCollection} with another one 435 * storing the same elements. 436 * This operation runs in constant time, by only swapping storage references. 437 * @param other the {@link UnorderedCollection} to swap contents with. 438 */ 439 public void swap(UnorderedCollection<E> other) { 440 int sizeTmp = size; 441 size = other.size; 442 other.size = sizeTmp; 443 storage.swap(other.storage); 444 } 445}