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}