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.util.set; 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// Attributes 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// Constructors 081 082 public 083 FixedArrayList() 084 { 085 elements = new ArrayList<E>(); 086 freeIndices = new ArrayList<Integer>( 16 ); 087 } 088 089 public 090 FixedArrayList( int capacity ) 091 { 092 elements = new ArrayList<E>( capacity ); 093 freeIndices = new ArrayList<Integer>( 16 ); 094 } 095 096// Accessors 097 098 /** 099 * Number of elements in the array. 100 * @return The number of elements in the array. 101 */ 102 public int 103 size() 104 { 105 return elements.size() - freeIndices.size(); 106 } 107 108 /** 109 * Real size of the array, counting elements that have been erased. 110 * @see #unsafeGet(int) 111 */ 112 public int 113 realSize() 114 { 115 return elements.size(); 116 } 117 118 public boolean 119 isEmpty() 120 { 121 return( size() == 0 ); 122 } 123 124 /** 125 * I-th element. 126 * @param i The element index. 127 * @return The element at index <code>i</code>. 128 */ 129 public E 130 get( int i ) 131 { 132 E e = elements.get( i ); 133 134 if( e == null ) 135 throw new NoSuchElementException( "no element at index " + i ); 136 137 return e; 138 } 139 140 /** 141 * I-th element. Like the {@link #get(int)} method but it does not check 142 * the element does not exists at the given index. 143 * @param i The element index. 144 * @return The element at index <code>i</code>. 145 */ 146 public E 147 unsafeGet( int i ) 148 { 149 return elements.get( i ); 150 } 151 152 public boolean 153 contains( Object o ) 154 { 155 int n = elements.size(); 156 157 for( int i=0; i<n; ++i ) 158 { 159 E e = elements.get( i ); 160 161 if( e != null ) 162 { 163 if( e == o ) 164 return true; 165 166 if( elements.equals( o ) ) 167 return true; 168 } 169 } 170 171 return false; 172 } 173 174 public boolean 175 containsAll( Collection<?> c ) 176 { 177 for( Object o: c ) 178 { 179 if( ! contains( o ) ) 180 return false; 181 } 182 183 return true; 184 } 185 186 @Override 187 @SuppressWarnings("unchecked") 188 public boolean 189 equals( Object o ) 190 { 191 if( o instanceof FixedArrayList ) 192 { 193 FixedArrayList<? extends E> other = (FixedArrayList<? extends E>) o; 194 195 int n = size(); 196 197 if( other.size() == n ) 198 { 199 for( int i=0; i<n; ++i ) 200 { 201 E e0 = elements.get( i ); 202 E e1 = other.elements.get( i ); 203 204 if( e0 != e1 ) 205 { 206 if( e0 == null && e1 != null ) 207 return false; 208 209 if( e0 != null && e1 == null ) 210 return false; 211 212 if( ! e0.equals( e1 ) ) 213 return false; 214 } 215 } 216 217 return true; 218 } 219 } 220 221 return false; 222 } 223 224 public java.util.Iterator<E> 225 iterator() 226 { 227 return new FixedArrayIterator(); 228 } 229 230 /** 231 * Last index used by the {@link #add(Object)} method. 232 * @return The last insertion index. 233 */ 234 public int 235 getLastIndex() 236 { 237 return lastIndex; 238 } 239 240 /** 241 * The index that will be used in case of a next insertion in this array. 242 * @return 243 */ 244 public int 245 getNextAddIndex() 246 { 247 int n = freeIndices.size(); 248 249 if( n > 0 ) 250 return freeIndices.get( n - 1 ); 251 else return elements.size(); 252 } 253 254 public Object[] 255 toArray() 256 { 257 int n = size(); 258 int m = elements.size(); 259 int j = 0; 260 Object a[] = new Object[n]; 261 262 for( int i=0; i<m; ++i ) 263 { 264 E e = elements.get( i ); 265 266 if( e != null ) 267 a[j++] = e; 268 } 269 270 assert( j == n ); 271 return a; 272 } 273 274 public <T> T[] 275 toArray( T[] a ) 276 { 277 // TODO 278 throw new RuntimeException( "not implemented yet" ); 279 } 280 281// Commands 282 283 /** 284 * Add one <code>element</code> in the array. The index used for inserting 285 * the element is then available using {@link #getLastIndex()}. 286 * @see #getLastIndex() 287 * @param element The element to add. 288 * @return Always true. 289 * @throws NullPointerException If a null value is inserted. 290 */ 291 public boolean 292 add( E element ) 293 throws java.lang.NullPointerException 294 { 295 if( element == null ) 296 throw new java.lang.NullPointerException( "this array cannot contain null value" ); 297 298 int n = freeIndices.size(); 299 300 if( n > 0 ) 301 { 302 int i = freeIndices.remove( n - 1 ); 303 elements.set( i, element ); 304 lastIndex = i; 305 } 306 else 307 { 308 elements.add( element ); 309 lastIndex = elements.size() - 1; 310 } 311 312 return true; 313 } 314 315 public boolean 316 addAll( Collection<? extends E> c ) 317 throws UnsupportedOperationException 318 { 319 java.util.Iterator<? extends E> k = c.iterator(); 320 321 while( k.hasNext() ) 322 { 323 add( k.next() ); 324 } 325 326 return true; 327 } 328 329 /** 330 * Remove the element at index <code>i</code>. 331 * @param i Index of the element to remove. 332 * @return The removed element. 333 */ 334 public E 335 remove( int i ) 336 { 337 int n = elements.size(); 338 339 if( i < 0 || i >= n ) 340 throw new ArrayIndexOutOfBoundsException( "index "+i+" does not exist" ); 341 342 if( n > 0 ) 343 { 344 if( elements.get( i ) == null ) 345 throw new NullPointerException( "no element stored at index " + i ); 346 347 if( i == ( n - 1 ) ) 348 { 349 return elements.remove( i ); 350 } 351 else 352 { 353 E e = elements.get( i ); 354 elements.set( i, null ); 355 freeIndices.add( i ); 356 return e; 357 } 358 } 359 360 throw new ArrayIndexOutOfBoundsException( "index "+i+" does not exist" ); 361 } 362 363 protected void 364 removeIt( int i ) 365 { 366 remove( i ); 367 } 368 369 /** 370 * Remove the element <code>e</code>. 371 * @param e The element to remove. 372 * @return True if removed. 373 */ 374 public boolean 375 remove( Object e ) 376 { 377 int n = elements.size(); 378 379 for( int i=0; i<n; ++i ) 380 { 381 if( elements.get( i ) == e ) 382 { 383 elements.remove( i ); 384 return true; 385 } 386 } 387 388 return false; 389 } 390 391 public boolean 392 removeAll( Collection<?> c ) 393 { 394 throw new UnsupportedOperationException( "not implemented yet" ); 395 } 396 397 public boolean 398 retainAll( Collection<?> c ) 399 { 400 throw new UnsupportedOperationException( "not implemented yet" ); 401 } 402 403 public void 404 clear() 405 { 406 elements.clear(); 407 freeIndices.clear(); 408 } 409 410// Nested classes 411 412protected class FixedArrayIterator 413 implements java.util.Iterator<E> 414{ 415 int i; 416 417 public 418 FixedArrayIterator() 419 { 420 i = -1; 421 } 422 423 public boolean 424 hasNext() 425 { 426 int n = elements.size(); 427 428 for( int j=i+1; j<n; ++j ) 429 { 430 if( elements.get( j ) != null ) 431 return true; 432 } 433 434 return false; 435 } 436 437 public E 438 next() 439 { 440 int n = elements.size(); 441 442 for( int j=i+1; j<n; ++j ) 443 { 444 E e = elements.get( j ); 445 446 if( e != null ) 447 { 448 i = j; 449 return e; 450 } 451 } 452 453 throw new NoSuchElementException( "no more elements in iterator" ); 454 } 455 456 public void 457 remove() 458 throws UnsupportedOperationException 459 { 460// throw new UnsupportedOperationException( "not implemented yet" ); 461 462 if( i >= 0 && i < elements.size() && elements.get( i ) != null ) 463 { 464 removeIt( i ); // A parent class method cannot be called if it has 465 // the same name as one in the inner class 466 // (normal), but even if they have distinct 467 // arguments types. Hence this strange removeIt() 468 // method... 469 } 470 else 471 { 472 throw new IllegalStateException( "no such element" ); 473 } 474 475 } 476} 477 478}