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.List;
022
023/**
024 * An extended collection interface.
025 * 
026 * This interface overcomes various shortcomings of the {@link Collection}
027 * interface from the Java Collections Framework, and also introduces
028 * other features not present in other libraries (such as the Apache
029 * Commons Collections Library).
030 * 
031 * Efficiently operating on collections data structures is often hampered
032 * by the insufficient interface provided by the standard Java collections.
033 * 
034 * For example, linked lists allow constant time removal if the element
035 * to be removed is known. However, using {@link List#remove(int)} requires
036 * linear time in the provided parameter (and thus, in the worst case, linear
037 * time in the size of the list). Removal in constant time is possible when
038 * iterating manually using the {@link Iterator#remove()} method, but this
039 * is not only inconvenient, but also does not work if one wants to remove
040 * the elements later, because {@link Iterator}s can't be cloned, and
041 * additionally are invalidated by other modifications of the underlying
042 * collection during their existence.
043 * 
044 * This collection interface introduces a <i>reference</i> concept: References
045 * (represented by the marker interface {@link ElementReference}) to the
046 * elements allow efficient (in terms of what the data structure itself
047 * supports) operations on the elements, if the reference to the respective
048 * element is known. References can be acquired right at the point when an
049 * element is added to the collection (using {@link #referencedAdd(Object)}),
050 * by explicitly searching for an element (using {@link #find(Object)}) or
051 * during iteration (using the {@link #referenceIterator()} resp.
052 * {@link #references()} method). 
053 * 
054 * The validity of references is retained through all operations on the
055 * collection, except for those that cause removal of the respective elements. 
056 * 
057 * @author Malte Isberner <malte.isberner@gmail.com>
058 *
059 * @param <E> element class
060 */
061public interface SmartCollection<E> extends Collection<E> {
062        
063        /**
064         * Retrieves an element by its reference.
065         * 
066         * If the reference belongs to another collection, the behavior
067         * is undefined.
068         * 
069         * @param ref the element's reference.
070         * @return the element.
071         */
072        public E get(ElementReference ref);
073        
074        /**
075         * Adds an element to the collection, returning a reference to the
076         * newly added element. If the collection does not support containing
077         * the same element multiple times, a reference to the previously
078         * existing element is returned.
079         * 
080         * @param elem the element to be added.
081         * @return a reference to this element in the collection.
082         */
083        public ElementReference referencedAdd(E elem);
084        
085        /**
086         * Removes an element (by its reference) from the collection.
087         * 
088         * If the reference does not belong to this collection, the behavior
089         * is undefined.
090         * 
091         * @param elem the reference to the element to be removed.
092         */
093        public void remove(ElementReference elem);
094        
095        /**
096         * Retrieves an arbitrary element from the collection. If the collection
097         * is empty, <code>null</code> is returned. Note, however, that a
098         * <code>null</code> return value doesn't necessary mean that the
099         * collection is empty, since it may contain <code>null</code> elements.
100         * 
101         * @return an arbitrary element from the collection, or <code>null</code>.
102         */
103        public E choose();
104        
105        /**
106         * Retrieves the reference to an arbitrary element from the collection.
107         * If the collection is empty, <code>null</code> is returned. In contrast
108         * to the above {@link #choose()}, this method returns <code>null</code>
109         * if <i>and only if</i> the collection is empty.
110         * 
111         * @return the reference to an arbitrary element in the collection, or
112         * <code>null</code>.
113         */
114        public ElementReference chooseRef();
115        
116        /**
117         * This function is deprecated and should not be used, in favor of
118         * the removal by reference {@link #remove(ElementReference)}.
119         * @see Collection#remove(Object)
120         */
121        @Deprecated
122        @Override
123        public boolean remove(Object element);
124        
125        /**
126         * Retrieves an iterator for iterating over the references of elements
127         * in this collection.
128         * @return the reference iterator.
129         */
130        public Iterator<ElementReference> referenceIterator();
131        
132        /**
133         * This is a method provided for convenience, which allows iterating
134         * over the element references using a <i>foreach</i>-style
135         * <code>for</code>-loop.
136         * 
137         * @return an {@link Iterable} with the above {@link #referenceIterator()}
138         * as its iterator.
139         */
140        public Iterable<ElementReference> references();
141        
142        /**
143         * Adds all elements from a given iterable. Note that this may be
144         * inefficient, compared to adding a {@link Collection}, because the
145         * number of elements to be added is not known a priori.
146         * 
147         * @param iterable the iterable of elements to add.
148         */
149        public void addAll(Iterable<? extends E> iterable);
150        
151        /**
152         * Adds all elements from the specified array.
153         * @param <T> array element class, may be a subclass of <code>E</code>.
154         * @param array the array of elements to be added.
155         */
156        public <T extends E> void addAll(T[] array);
157        
158        /**
159         * Replaces the element referenced by the given reference with
160         * the specified element.
161         * 
162         * @param ref the reference of the element to be replaced.
163         * @param newElement the replacement.
164         */
165        public void replace(ElementReference ref, E newElement);
166        
167        /**
168         * Retrieves the reference for a given element. If the element is not
169         * contained in the collection, <code>null</code> is returned.
170         * 
171         * @param element the element to search for.
172         * @return the reference to this element, or <code>null</code>.
173         */
174        public ElementReference find(Object element);
175        
176        /**
177         * Quickly clears this collection. This method is supposed to perform
178         * the minimum amount of effort such that this collection is emptied,
179         * disregarding all other side-effects such as referencing or garbage
180         * collection issues.
181         * 
182         * Depending on the implementation, this may be just the same as
183         * {@link Collection#clear()}. However, this could also have side-effects
184         * like hampering the garbage collection or such.
185         * 
186         * After calling this method, even a call of the normal
187         * {@link Collection#clear()} is not guaranteed to fix all these issues.
188         * This can only be achieved by the method {@link #deepClear()} below.
189         */
190        public void quickClear();
191        
192        /**
193         * Thoroughly clears the collection, fixing all issues that may have been
194         * caused by a call of the above {@link #quickClear()}. 
195         */
196        public void deepClear();
197}