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}