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}