package net.sourceforge.pain.db; import java.util.*; /** * Persistent linked list implementation of the <tt>List</tt> interface. * todo: add removeLast */ public final class DbLinkedList extends DbCollection implements List { private int size; private Entry first; // first entry has prev, but last one have not next! private int modCount; /** * Startup method. * @param owner * @param refIds */ DbLinkedList(final DbObject owner, final int[] refIds, final int fid) { super(owner, fid); modCount = 0; restoreFromImage(refIds); } /** * runtime(not startup) method. default value for collection type field is empty collection * @param owner */ DbLinkedList(final DbObject owner, final int fid) { super(owner, fid); modCount = 0; size = 0; } private void restoreFromImage(final int[] refIds) { final PainDB db = owner._getDB(); size = refIds.length; Entry runner = null; for (int i = refIds.length; --i >= 0;) { runner = new Entry(db.getObjectByIndexId(refIds[i]), null, runner); } first = runner; } private int _index(final Entry e) { Entry runner = first; for (int i = 0; runner != null; i++, runner = runner.nextInList) { if (runner == e) { return i; } } throw new RuntimeException("entry not found!"); } public int size() { owner.ensureReal(); return size; } public boolean isEmpty() { owner.ensureReal(); return size == 0; } public boolean contains(final Object obj) { owner.ensureReal(); if (obj != null && (!(obj instanceof DbObject) || !hasSameDb((DbObject) obj))) { return false; } for (Entry runner = first; runner != null; runner = runner.nextInList) { if (obj == runner.obj) { return true; } } return false; } public Iterator iterator() { return listIterator(); } public Object[] toArray() { owner.ensureReal(); final Object[] result = new Object[size]; Entry runner = first; for (int i = 0; runner != null; i++, runner = runner.nextInList) { result[i] = runner.obj; } return result; } public Object[] toArray(Object a[]) { owner.ensureReal(); if (a.length < size) { a = (Object[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size); } int i = 0; for (Entry runner = first; runner != null; runner = runner.nextInList) { a[i++] = runner.obj; } if (a.length > size) { a[size] = null; } return a; } public boolean add(final Object o) { owner.ensureReal(); owner.onCollectionChange(this); _add(checkObject(o)); modCount++; return true; } private void _add(final DbObject obj) { first = new Entry(obj, first == null ? null : first.prevInList, first); // will bind itself in queue in factory, to last position size++; } public boolean remove(final Object o) { owner.ensureReal(); for (Entry runner = first; runner != null; runner = runner.nextInList) { if (o == runner.obj) { owner.onCollectionChange(this); _remove(runner); modCount++; return true; } } return false; } private void _removeByIterator(final Entry e) { modCount++; _remove(e); } private Entry _remove(final Entry e) { e.removeFromList(); size--; return e.nextInList; } public boolean containsAll(final Collection c) { owner.ensureReal(); for (Iterator it = c.iterator(); it.hasNext();) { if (!contains(it.next())) { return false; } } return true; } public boolean addAll(final Collection c) { owner.ensureReal(); owner.onCollectionChange(this); if (c == null || c.isEmpty()) { return false; } Object array[] = c.toArray(); final int len = array.length; for (int i = 0; i < len; i++) { _add(checkObject(array[i])); } modCount++; return true; } public boolean removeAll(final Collection c) { owner.ensureReal(); boolean changed = false; for (Entry runner = first; runner != null; runner = runner.nextInList) { if (c.contains(runner.obj)) { if (!changed) { owner.onCollectionChange(this); changed = true; } runner = _remove(runner); } } if (changed) { modCount++; } return changed; } public boolean retainAll(final Collection c) { owner.ensureReal(); boolean changed = false; for (Entry runner = first; runner != null; runner = runner.nextInList) { if (!c.contains(runner.obj)) { if (!changed) { owner.onCollectionChange(this); } runner = _remove(runner); changed = true; } } if (changed) { modCount++; } return changed; } void _clear() { if (size == 0) { return; } while (first != null) { _remove(first); } size = 0; modCount++; } public void clear() { owner.ensureReal(); if (first == null) { return; } owner.onCollectionChange(this); _clear(); } Entry getFirstEntry() { return first; } int _size() { return size; } public boolean addAll(final int index, final Collection c) { owner.ensureReal(); checkRange(index); if (c == null || c.isEmpty()) { return false; } owner.onCollectionChange(this); Entry point = findEntry(index); for (Iterator it = c.iterator(); it.hasNext();) { point = new Entry(checkObject(it.next()), point.prevInList, point); } size += c.size(); modCount++; return true; } public Object get(final int index) { owner.ensureReal(); checkRange(index); return findEntry(index).obj; } private Entry findEntry(final int index) { Entry result = first; for (int i = 0; i < index; i++) { result = result.nextInList; } return result; } public Object set(final int index, final Object o) { owner.ensureReal(); checkRange(index); final DbObject obj = checkObject(o); final Entry e = findEntry(index); if (e.obj == obj) { return obj; } owner.onCollectionChange(this); final Entry prev = e.prevInList; final Entry next = e.nextInList; final Object result = e.obj; e.removeFromList(); new Entry(obj, prev, next); modCount++; return result; } private boolean hasSameDb(final DbObject o) { return o._getDB() == owner._getDB(); } private DbObject checkObject(final Object o) { if (o != null) { final DbObject obj = (DbObject) o; obj.ensureReal(); owner.ensureDb(obj); return obj; } return null; } public void add(final int index, final Object o) { owner.ensureReal(); checkRange(index); final DbObject obj = checkObject(o); owner.onCollectionChange(this); final Entry e = findEntry(index); new Entry(obj, e, e.nextInList); size++; modCount++; } public Object removeFirst() { return remove(0); } public Object remove(final int index) { owner.ensureReal(); checkRange(index); owner.onCollectionChange(this); final Entry e = findEntry(index); final Object result = e.obj; e.removeFromList(); size--; modCount++; return result; } public int indexOf(final Object o) { owner.ensureReal(); int i = 0; for (Entry runner = first; runner != null; runner = runner.nextInList, i++) { if (runner.obj == o) { return i; } } return -1; } public int lastIndexOf(final Object o) { owner.ensureReal(); final int i = 0; if (first == null) { return -1; } Entry runner = first.prevInList; do { if (runner.obj == o) { return i; } runner = runner.prevInList; } while (runner != first); return -1; } private void checkRange(final int index) { if (index >= size || index < 0) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } public ListIterator listIterator() { owner.ensureReal(); return new DbLinkedListIterator(); } public ListIterator listIterator(final int index) { owner.ensureReal(); if (index < 0 || index > size) { throw new ArrayIndexOutOfBoundsException("" + index); } if (index < size) { return new DbLinkedListIterator(findEntry(index), true); } else { return new DbLinkedListIterator(findEntry(size), false); } } public List subList(final int fromIndex, final int toIndex) { throw new UnsupportedOperationException(); } /** * called when object gets transaction context (during any field changed during transaction) * @return */ Object createBackupImage() { if (size == 0) { return DbConstants.ZERO_INT_ARRAY; } final int[] backup = new int[size]; int i = 0; for (Entry runner = first; runner != null; runner = runner.nextInList, i++) { final DbObject obj = runner.obj; backup[i] = (obj == null ? -1 : obj.indexId); } return backup; } /** * called on rollbacks * @param backup */ void restoreFromBackup(final Object backup) { final int[] ids = (int[]) backup; _clear(); restoreFromImage(ids); } //------------------inners ---------------------------// final class Entry extends DbInverseRef { Entry nextInList; Entry prevInList; Entry(final DbObject obj, final Entry prevInCollection, final Entry nextInCollection) { super(obj); this.nextInList = nextInCollection; this.prevInList = prevInCollection; if (nextInCollection != null) { nextInCollection.prevInList = this; } if (prevInCollection != null && first.prevInList != prevInCollection) { //first.prev.next is only record that "NULL" prevInCollection.nextInList = this; } } void _onTargetDelete() { owner.onCollectionChange(DbLinkedList.this); // in list we keep only index ids (no version ids), so we should flush it image //if object from it's content deleted to avoid indexIds collision (indexIds of deleted are reusable) in separate transactions } void removeFromList() { // method could be called only from collection; // modCount and size will be reduced in caller method if (this == first) { first = nextInList; } else { //not first prevInList.nextInList = nextInList; } if (nextInList != null) { nextInList.prevInList = prevInList; } if (obj != null) { onReferenceDestroy(); } } }; final class DbLinkedListIterator implements ListIterator { private int expectedModCount; private Entry e = null; private int dir = 0; public DbLinkedListIterator() { expectedModCount = modCount; e = first; } public DbLinkedListIterator(final Entry entry, boolean isEntryNext) { if (!isEntryNext) { e = entry.nextInList; } expectedModCount = modCount; } public boolean hasNext() { checkState(); return e != null; } public Object next() { if (!hasNext()) { throw new NoSuchElementException(); } Object res = e.obj; e = e.nextInList; dir = 1; return res; } public void remove() { checkState(); owner.onCollectionChange(DbLinkedList.this); if (dir == 0) { throw new IllegalStateException(); } final Entry remEntry; if (dir == 1) { if (e == null) { remEntry = findEntry(size - 1); } else { remEntry = e; e = e.prevInList; } } else { remEntry = e; e = e.nextInList; } _removeByIterator(remEntry); expectedModCount++; } private void checkState() { checkForComodification(); owner.ensureReal(); } private void checkForComodification() { if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } public boolean hasPrevious() { checkState(); if (e == null) { return size > 0; } return e.prevInList != null; } public Object previous() { if (!hasPrevious()) { throw new NoSuchElementException(); } dir = -1; if (e == null) { //end of list e = findEntry(size - 1); } else { e = e.prevInList; } return e.obj; } public int nextIndex() { if (!hasNext()) { return size; } return _index(e); } public int previousIndex() { if (!hasPrevious()) { return -1; } return _index(e.prevInList); } public void set(final Object o) { //todo throw new UnsupportedOperationException(); } public void add(final Object o) { //todo throw new UnsupportedOperationException(); } } }