FixedArrayList.java
/*
* Copyright 2006 - 2013
* Stefan Balev <stefan.balev@graphstream-project.org>
* Julien Baudry <julien.baudry@graphstream-project.org>
* Antoine Dutot <antoine.dutot@graphstream-project.org>
* Yoann Pign�� <yoann.pigne@graphstream-project.org>
* Guilhelm Savin <guilhelm.savin@graphstream-project.org>
*
* This file is part of GraphStream <http://graphstream-project.org>.
*
* GraphStream is a library whose purpose is to handle static or dynamic
* graph, create them from scratch, file or any source and display them.
*
* This program is free software distributed under the terms of two licenses, the
* CeCILL-C license that fits European law, and the GNU Lesser General Public
* License. You can use, modify and/ or redistribute the software under the terms
* of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
* URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
* the Free Software Foundation, either version 3 of the License, or (at your
* option) any later version.
*
* This program is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
* PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
* The fact that you are presently reading this means that you have had
* knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
*/
package org.graphstream.util.set;
import java.util.ArrayList;
import java.util.Collection;
import java.util.NoSuchElementException;
import java.util.RandomAccess;
/**
* Array list with immutable element indices.
*
* <p>A fixed array list is like an array list, but it ensures the property that
* each element will always stay at the same index, even if elements are
* removed in between. The counterpart of this property is that the array
* handles by itself the insertion of new elements (since when an element is
* removed in the middle, this position can be reused), and therefore indices
* cannot be chosen (i.e. only the {@link #add(Object)} and
* {@link #addAll(Collection)} methods are usable to insert new elements in the
* array).</p>
*
* <p>This is the reason why this does not implement the List interface, because
* the add(int,E) method cannot be implemented.</p>
*
* <p>Furthermore, this array cannot contain null values, because it marks
* unused positions within the array using the null value.</p>
*
* @author Antoine Dutot
* @since 20040912
*/
public class FixedArrayList<E>
implements Collection<E>, RandomAccess
{
// Attributes
/**
* List of elements.
*/
protected ArrayList<E> elements = new ArrayList<E>();
/**
* List of free indices.
*/
protected ArrayList<Integer> freeIndices = new ArrayList<Integer>();
/**
* Last inserted element index.
*/
protected int lastIndex = -1;
// Constructors
public
FixedArrayList()
{
elements = new ArrayList<E>();
freeIndices = new ArrayList<Integer>( 16 );
}
public
FixedArrayList( int capacity )
{
elements = new ArrayList<E>( capacity );
freeIndices = new ArrayList<Integer>( 16 );
}
// Accessors
/**
* Number of elements in the array.
* @return The number of elements in the array.
*/
public int
size()
{
return elements.size() - freeIndices.size();
}
/**
* Real size of the array, counting elements that have been erased.
* @see #unsafeGet(int)
*/
public int
realSize()
{
return elements.size();
}
public boolean
isEmpty()
{
return( size() == 0 );
}
/**
* I-th element.
* @param i The element index.
* @return The element at index <code>i</code>.
*/
public E
get( int i )
{
E e = elements.get( i );
if( e == null )
throw new NoSuchElementException( "no element at index " + i );
return e;
}
/**
* I-th element. Like the {@link #get(int)} method but it does not check
* the element does not exists at the given index.
* @param i The element index.
* @return The element at index <code>i</code>.
*/
public E
unsafeGet( int i )
{
return elements.get( i );
}
public boolean
contains( Object o )
{
int n = elements.size();
for( int i=0; i<n; ++i )
{
E e = elements.get( i );
if( e != null )
{
if( e == o )
return true;
if( elements.equals( o ) )
return true;
}
}
return false;
}
public boolean
containsAll( Collection<?> c )
{
for( Object o: c )
{
if( ! contains( o ) )
return false;
}
return true;
}
@Override
@SuppressWarnings("unchecked")
public boolean
equals( Object o )
{
if( o instanceof FixedArrayList )
{
FixedArrayList<? extends E> other = (FixedArrayList<? extends E>) o;
int n = size();
if( other.size() == n )
{
for( int i=0; i<n; ++i )
{
E e0 = elements.get( i );
E e1 = other.elements.get( i );
if( e0 != e1 )
{
if( e0 == null && e1 != null )
return false;
if( e0 != null && e1 == null )
return false;
if( ! e0.equals( e1 ) )
return false;
}
}
return true;
}
}
return false;
}
public java.util.Iterator<E>
iterator()
{
return new FixedArrayIterator();
}
/**
* Last index used by the {@link #add(Object)} method.
* @return The last insertion index.
*/
public int
getLastIndex()
{
return lastIndex;
}
/**
* The index that will be used in case of a next insertion in this array.
* @return
*/
public int
getNextAddIndex()
{
int n = freeIndices.size();
if( n > 0 )
return freeIndices.get( n - 1 );
else return elements.size();
}
public Object[]
toArray()
{
int n = size();
int m = elements.size();
int j = 0;
Object a[] = new Object[n];
for( int i=0; i<m; ++i )
{
E e = elements.get( i );
if( e != null )
a[j++] = e;
}
assert( j == n );
return a;
}
public <T> T[]
toArray( T[] a )
{
// TODO
throw new RuntimeException( "not implemented yet" );
}
// Commands
/**
* Add one <code>element</code> in the array. The index used for inserting
* the element is then available using {@link #getLastIndex()}.
* @see #getLastIndex()
* @param element The element to add.
* @return Always true.
* @throws NullPointerException If a null value is inserted.
*/
public boolean
add( E element )
throws java.lang.NullPointerException
{
if( element == null )
throw new java.lang.NullPointerException( "this array cannot contain null value" );
int n = freeIndices.size();
if( n > 0 )
{
int i = freeIndices.remove( n - 1 );
elements.set( i, element );
lastIndex = i;
}
else
{
elements.add( element );
lastIndex = elements.size() - 1;
}
return true;
}
public boolean
addAll( Collection<? extends E> c )
throws UnsupportedOperationException
{
java.util.Iterator<? extends E> k = c.iterator();
while( k.hasNext() )
{
add( k.next() );
}
return true;
}
/**
* Remove the element at index <code>i</code>.
* @param i Index of the element to remove.
* @return The removed element.
*/
public E
remove( int i )
{
int n = elements.size();
if( i < 0 || i >= n )
throw new ArrayIndexOutOfBoundsException( "index "+i+" does not exist" );
if( n > 0 )
{
if( elements.get( i ) == null )
throw new NullPointerException( "no element stored at index " + i );
if( i == ( n - 1 ) )
{
return elements.remove( i );
}
else
{
E e = elements.get( i );
elements.set( i, null );
freeIndices.add( i );
return e;
}
}
throw new ArrayIndexOutOfBoundsException( "index "+i+" does not exist" );
}
protected void
removeIt( int i )
{
remove( i );
}
/**
* Remove the element <code>e</code>.
* @param e The element to remove.
* @return True if removed.
*/
public boolean
remove( Object e )
{
int n = elements.size();
for( int i=0; i<n; ++i )
{
if( elements.get( i ) == e )
{
elements.remove( i );
return true;
}
}
return false;
}
public boolean
removeAll( Collection<?> c )
{
throw new UnsupportedOperationException( "not implemented yet" );
}
public boolean
retainAll( Collection<?> c )
{
throw new UnsupportedOperationException( "not implemented yet" );
}
public void
clear()
{
elements.clear();
freeIndices.clear();
}
// Nested classes
protected class FixedArrayIterator
implements java.util.Iterator<E>
{
int i;
public
FixedArrayIterator()
{
i = -1;
}
public boolean
hasNext()
{
int n = elements.size();
for( int j=i+1; j<n; ++j )
{
if( elements.get( j ) != null )
return true;
}
return false;
}
public E
next()
{
int n = elements.size();
for( int j=i+1; j<n; ++j )
{
E e = elements.get( j );
if( e != null )
{
i = j;
return e;
}
}
throw new NoSuchElementException( "no more elements in iterator" );
}
public void
remove()
throws UnsupportedOperationException
{
// throw new UnsupportedOperationException( "not implemented yet" );
if( i >= 0 && i < elements.size() && elements.get( i ) != null )
{
removeIt( i ); // A parent class method cannot be called if it has
// the same name as one in the inner class
// (normal), but even if they have distinct
// arguments types. Hence this strange removeIt()
// method...
}
else
{
throw new IllegalStateException( "no such element" );
}
}
}
}