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}