001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.algorithm; 033 034import java.util.ArrayList; 035import java.util.Collection; 036import java.util.NoSuchElementException; 037import java.util.RandomAccess; 038 039/** 040 * Array list with immutable element indices. 041 * 042 * <p>A fixed array list is like an array list, but it ensures the property that 043 * each element will always stay at the same index, even if elements are 044 * removed in between. The counterpart of this property is that the array 045 * handles by itself the insertion of new elements (since when an element is 046 * removed in the middle, this position can be reused), and therefore indices 047 * cannot be chosen (i.e. only the {@link #add(Object)} and 048 * {@link #addAll(Collection)} methods are usable to insert new elements in the 049 * array).</p> 050 * 051 * <p>This is the reason why this does not implement the List interface, because 052 * the add(int,E) method cannot be implemented.</p> 053 * 054 * <p>Furthermore, this array cannot contain null values, because it marks 055 * unused positions within the array using the null value.</p> 056 * 057 * @author Antoine Dutot 058 * @since 20040912 059 */ 060public class FixedArrayList<E> 061 implements Collection<E>, RandomAccess 062{ 063// Attribute 064 065 /** 066 * List of elements. 067 */ 068 protected ArrayList<E> elements = new ArrayList<E>(); 069 070 /** 071 * List of free indices. 072 */ 073 protected ArrayList<Integer> freeIndices = new ArrayList<Integer>(); 074 075 /** 076 * Last inserted element index. 077 */ 078 protected int lastIndex = -1; 079 080// Construction 081 082 public FixedArrayList() { 083 elements = new ArrayList<E>(); 084 freeIndices = new ArrayList<Integer>(16); 085 } 086 087 public FixedArrayList(int capacity) { 088 elements = new ArrayList<E>(capacity); 089 freeIndices = new ArrayList<Integer>(16); 090 } 091 092// Access 093 094 /** 095 * Number of elements in the array. 096 * @return The number of elements in the array. 097 */ 098 public int size() { 099 return elements.size() - freeIndices.size(); 100 } 101 102 /** 103 * Real size of the array, counting elements that have been erased. 104 * @see #unsafeGet(int) 105 */ 106 public int realSize() { 107 return elements.size(); 108 } 109 110 public boolean isEmpty() { 111 return size() == 0; 112 } 113 114 /** 115 * True if the given index i references a value. 116 * @param i The index to test. 117 * @return True if a value exists at the given index. 118 */ 119 public boolean hasIndex(int i) { 120 if(i>0 && i<elements.size()) { 121 return elements.get(i) != null; 122 } 123 124 return false; 125 } 126 127 /** 128 * I-th element. 129 * @param i The element index. 130 * @return The element at index <code>i</code>. 131 */ 132 public E get(int i) { 133 E e = elements.get(i); 134 135 if(e == null) 136 throw new NoSuchElementException( "no element at index " + i ); 137 138 return e; 139 } 140 141 /** 142 * I-th element. Like the {@link #get(int)} method but it does not check 143 * the element does not exists at the given index. 144 * @param i The element index. 145 * @return The element at index <code>i</code>. 146 */ 147 public E unsafeGet(int i) { 148 return elements.get( i ); 149 } 150 151 public boolean contains(Object o) { 152 int n = elements.size(); 153 154 for(int i=0; i<n; ++i) { 155 E e = elements.get(i); 156 157 if(e != null) { 158 if(e == o) 159 return true; 160 161 if(elements.equals(o)) 162 return true; 163 } 164 } 165 166 return false; 167 } 168 169 public boolean containsAll(Collection<?> c) { 170 for(Object o: c) { 171 if(! contains(o)) 172 return false; 173 } 174 175 return true; 176 } 177 178 @Override 179 @SuppressWarnings("unchecked") 180 public boolean equals(Object o) { 181 if(o instanceof FixedArrayList) { 182 FixedArrayList<? extends E> other = (FixedArrayList<? extends E>) o; 183 184 int n = size(); 185 186 if(other.size() == n) { 187 for(int i=0; i<n; ++i) { 188 E e0 = elements.get(i); 189 E e1 = other.elements.get(i); 190 191 if(e0 != e1) { 192 if(e0 == null && e1 != null) 193 return false; 194 195 if(e0 != null && e1 == null) 196 return false; 197 198 if(! e0.equals(e1)) 199 return false; 200 } 201 } 202 203 return true; 204 } 205 } 206 207 return false; 208 } 209 210 public java.util.Iterator<E> iterator() { 211 return new FixedArrayIterator(); 212 } 213 214 /** 215 * Last index used by the {@link #add(Object)} method. 216 * @return The last insertion index. 217 */ 218 public int getLastIndex() { 219 return lastIndex; 220 } 221 222 /** 223 * The index that will be used in case of a next insertion in this array. 224 * @return 225 */ 226 public int getNextAddIndex() { 227 int n = freeIndices.size(); 228 229 if(n > 0) 230 return freeIndices.get(n - 1); 231 else return elements.size(); 232 } 233 234 public Object[] toArray() { 235 int n = size(); 236 int m = elements.size(); 237 int j = 0; 238 Object a[] = new Object[n]; 239 240 for(int i=0; i<m; ++i) { 241 E e = elements.get(i); 242 243 if(e != null) 244 a[j++] = e; 245 } 246 247 assert(j == n); 248 return a; 249 } 250 251 public <T> T[] toArray(T[] a) { 252 // TODO 253 throw new RuntimeException( "not implemented yet" ); 254 } 255 256// Commands 257 258 /** 259 * Add one <code>element</code> in the array. The index used for inserting 260 * the element is then available using {@link #getLastIndex()}. This method 261 * complexity is O(1). 262 * @see #getLastIndex() 263 * @param element The element to add. 264 * @return Always true. 265 * @throws NullPointerException If a null value is inserted. 266 */ 267 public boolean add(E element) throws java.lang.NullPointerException { 268 if(element == null) 269 throw new java.lang.NullPointerException( "this array cannot contain null value" ); 270 271 int n = freeIndices.size(); 272 273 if(n > 0) { 274 int i = freeIndices.remove(n - 1); 275 elements.set(i, element); 276 lastIndex = i; 277 } else { 278 elements.add(element); 279 lastIndex = elements.size() - 1; 280 } 281 282 return true; 283 } 284 285 public boolean addAll(Collection<? extends E> c) throws UnsupportedOperationException { 286 java.util.Iterator<? extends E> k = c.iterator(); 287 288 while(k.hasNext()) { 289 add(k.next()); 290 } 291 292 return true; 293 } 294 295 /** 296 * This operation set the i-th cell with the given value. 297 * 298 * This works only 299 * if the cell is empty, or if i is larger or equal to the size of the 300 * array (if larger, empty cells are added to fill the gap, and free 301 * indices will be used by the add() method). 302 * 303 * If the cell is not empty, the return value is false. 304 * 305 * This method is a convenience method, and its complexity is not O(1) 306 * like the add() and remove() methods. At worse the complexity is O(n). 307 * It is optimized so that when adding the element whose id is the one 308 * given by {@link FixedArrayList#getNextAddIndex()} its complexity is O(1). 309 * 310 * @param i The index of the cell to change. 311 * @param element The value to set. 312 * @return false If the insertion was not successful (there was already 313 * something in the set). 314 */ 315 public boolean addAt(int i, E element) { 316 if(i >= elements.size()) { 317 // Add at the end or at a non existent position at the end. 318 319 int n = elements.size(); 320 int d = i - n; 321 322 for(int j=0; j<d; j++) { 323 elements.add(null); 324 freeIndices.add(n+j); 325 326 } 327 elements.add(element); 328 assert(elements.size()-1 == i); 329 lastIndex = i; 330 } else { 331 // Add at an existing position 332 if(elements.get(i) == null) { 333 // Add the element and release the index in the index list. 334 elements.set(i, element); 335 freeIndices.remove(freeIndices.lastIndexOf(i)); // O(n) 336 } else { 337 return false; 338 } 339 } 340 341 return true; 342 } 343 344 /** 345 * Remove the element at index <code>i</code>. This method complexity 346 * is O(1). 347 * @param i Index of the element to remove. 348 * @return The removed element. 349 */ 350 public E remove(int i) { 351 int n = elements.size(); 352 353 if(i < 0 || i >= n) 354 throw new ArrayIndexOutOfBoundsException("index "+i+" does not exist"); 355 356 if(n > 0) { 357 if( elements.get( i ) == null ) 358 throw new NullPointerException("no element stored at index " + i); 359 360 if(i == (n - 1)) { 361 return elements.remove( i ); 362 } else { 363 E e = elements.get(i); 364 elements.set(i, null); 365 freeIndices.add(i); 366 return e; 367 } 368 } 369 370 throw new ArrayIndexOutOfBoundsException("index "+i+" does not exist"); 371 } 372 373 protected void removeIt(int i) { 374 remove(i); 375 } 376 377 /** 378 * Remove the element <code>e</code>. At worse the complexity is 379 * O(n). 380 * @param e The element to remove. 381 * @return True if removed. 382 */ 383 public boolean remove(Object e) { 384 int n = elements.size(); 385 386 for(int i=0; i<n; ++i) { 387 if(elements.get(i) == e) { 388 elements.remove(i); 389 return true; 390 } 391 } 392 393 return false; 394 } 395 396 public boolean removeAll(Collection<?> c) { 397 throw new UnsupportedOperationException( "not implemented yet" ); 398 } 399 400 public boolean retainAll(Collection<?> c) { 401 throw new UnsupportedOperationException( "not implemented yet" ); 402 } 403 404 public void clear() { 405 elements.clear(); 406 freeIndices.clear(); 407 } 408 409// Nested classes 410 411protected class FixedArrayIterator implements java.util.Iterator<E> { 412 int i; 413 414 public FixedArrayIterator() { 415 i = -1; 416 } 417 418 public boolean hasNext() { 419 int n = elements.size(); 420 421 for(int j=i+1; j<n; ++j) { 422 if(elements.get(j) != null) 423 return true; 424 } 425 426 return false; 427 } 428 429 public E next() { 430 int n = elements.size(); 431 432 for(int j=i+1; j<n; ++j) { 433 E e = elements.get(j); 434 435 if(e != null) { 436 i = j; 437 return e; 438 } 439 } 440 441 throw new NoSuchElementException("no more elements in iterator"); 442 } 443 444 public void remove() throws UnsupportedOperationException { 445 if(i >= 0 && i < elements.size() && elements.get(i) != null) { 446 removeIt(i); // A parent class method cannot be called if it has 447 // the same name as one in the inner class 448 // (normal), but even if they have distinct 449 // arguments types. Hence this strange removeIt() 450 // method... 451 } else { 452 throw new IllegalStateException("no such element"); 453 } 454 } 455} 456}