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() {
            // 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
			owner.onCollectionChange(DbLinkedList.this);
		}

		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();
		}

	}


}