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.util.nid;
018
019import java.util.AbstractList;
020import java.util.Iterator;
021
022import net.automatalib.commons.util.array.ArrayWritable;
023import net.automatalib.commons.util.array.ResizingObjectArray;
024
025
026public class DynamicList<T extends MutableNumericID> extends
027                AbstractList<T> implements ArrayWritable<T> {
028        
029        private final ResizingObjectArray storage
030                = new ResizingObjectArray();
031        
032        private int size = 0;
033        
034
035        @Override
036        public Iterator<T> iterator() {
037                return new Iterator<T>() {
038                        
039                        int index = 0;
040                        
041                        @Override
042                        public boolean hasNext() {
043                                return (index < size);
044                        }
045
046                        @Override
047                        public T next() {
048                                return get(index++);
049                        }
050
051                        @Override
052                        public void remove() {
053                                DynamicList.this.remove(--index);
054                        }
055                        
056                };
057        }
058
059        @Override
060        public int size() {
061                return size;
062        }
063        
064        @Override
065        public boolean isEmpty() {
066                return (size == 0);
067        }
068        
069        @Override
070        public boolean add(T elem) {
071                storage.ensureCapacity(size+1);
072                storage.array[size] = elem;
073                elem.setId(size);
074                size++;
075                return true;
076        }
077        
078        @SuppressWarnings("unchecked")
079        public void swap(int a, int b) {
080                if(a == b)
081                        return;
082                if(a < 0 || a >= size)
083                        throw new IndexOutOfBoundsException("Invalid index " + a);
084                if(b < 0 || b >= size)
085                        throw new IndexOutOfBoundsException("Invalid index " + b);
086                Object tmp = storage.array[a];
087                storage.array[a] = storage.array[b];
088                storage.array[b] = tmp;
089                ((T)storage.array[a]).setId(a);
090                ((T)storage.array[b]).setId(b);
091        }
092        
093        @Override
094        @SuppressWarnings("unchecked")
095        public T get(int index) {
096                if(index < 0 || index >= size)
097                        throw new IndexOutOfBoundsException("Invalid index " + index);
098                return (T)storage.array[index];
099        }
100        
101        @SuppressWarnings("unchecked")
102        public T safeGet(int index) {
103                if(index < 0 || index >= size)
104                        return null;
105                return (T)storage.array[index];
106        }
107        
108        
109        @Override
110        public boolean remove(Object elem) {
111                return remove(elem, null);
112        }
113        
114        public boolean remove(Object elem, IDChangeNotifier<T> tracker) {
115                if(!(elem instanceof MutableNumericID))
116                        return false;
117                MutableNumericID idElem = (MutableNumericID)elem;
118                int idx = idElem.getId();
119                T myElem = safeGet(idx);
120                if(elem != myElem)
121                        return false;
122                
123                T last = safeGet(size-1);
124                size--;
125                
126                if(idx != size) {
127                        storage.array[idx] = last;
128                        last.setId(idx);
129                        if(tracker != null)
130                                tracker.notifyListeners(last, idx, size);
131                }
132                storage.array[size] = null;
133                myElem.setId(-1);
134                
135                return true;
136        }
137        
138        public T remove(int index, IDChangeNotifier<T> tracker) {
139                T elem = get(index);
140                
141                T last = safeGet(--size);
142                
143                if(index != size) {
144                        storage.array[index] = last;
145                        last.setId(index);
146                        if(tracker != null)
147                                tracker.notifyListeners(last, index, size);
148                }
149                storage.array[size] = null;
150                elem.setId(-1);
151                
152                return elem;
153        }
154        
155        @Override
156        public void clear() {
157                for(int i = 0; i < size; i++)
158                        storage.array[i] = null;
159                size = 0;
160        }
161
162        @Override
163        public void writeToArray(int offset, Object[] array, int tgtOfs, int num) {
164                System.arraycopy(storage.array, offset, array, tgtOfs, num);
165        }
166
167}