/* arraylist.vala
 *
 * Copyright (C) 2004-2005  Novell, Inc
 * Copyright (C) 2005  David Waite
 * Copyright (C) 2007-2008  Jürg Billeter
 * Copyright (C) 2009  Didier Villevalois
 * Copyright (C) 2010-2014  Maciej Piechotka
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.

 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.

 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
 *
 * Author:
 * 	Jürg Billeter <j@bitron.ch>
 * 	Didier 'Ptitjes Villevalois <ptitjes@free.fr>
 */

using Gee.Utils.Assume;

/**
 * Resizable array implementation of the {@link List} interface.
 *
 * The storage array grows automatically when needed.
 *
 * This implementation is pretty good for rarely modified data. Because they are
 * stored in an array this structure does not fit for highly mutable data. For an
 * alternative implementation see {@link LinkedList}.
 *
 * @see LinkedList
 */
public class Gee.ArrayList<G> : AbstractBidirList<G> {
	/**
	 * {@inheritDoc}
	 */
	public override int size {
		get { return _size; }
	}

	/**
	 * {@inheritDoc}
	 */
	public override bool read_only {
		get { return false; }
	}

	/**
	 * The elements' equality testing function.
	 */
	[CCode (notify = false)]
	public EqualDataFunc<G> equal_func {
		private set {}
		get {
			return _equal_func.func;
		}
	}

	internal G[] _items;
	internal int _size;
	private Functions.EqualDataFuncClosure<G> _equal_func;

	// concurrent modification protection
	private int _stamp = 0;

	/**
	 * Constructs a new, empty array list.
	 *
	 * If not provided, the function parameter is requested to the
	 * {@link Functions} function factory methods.
	 *
	 * @param equal_func an optional element equality testing function
	 */
	public ArrayList (owned EqualDataFunc<G>? equal_func = null) {
		if (equal_func == null) {
			equal_func = Functions.get_equal_func_for (typeof (G));
		}
		_equal_func = new Functions.EqualDataFuncClosure<G>((owned)equal_func);
		_items = new G[4];
		_size = 0;
	}

	/**
	 * Constructs a new array list based on provided array.
	 *
	 * If not provided, the function parameter is requested to the
	 * {@link Functions} function factory methods.
	 *
	 * @param items initial items to be put into array
	 * @param equal_func an optional element equality testing function
	 */
	public ArrayList.wrap (owned G[] items, owned EqualDataFunc<G>? equal_func = null) {
		if (equal_func == null) {
			equal_func = Functions.get_equal_func_for (typeof (G));
		}
		_equal_func = new Functions.EqualDataFuncClosure<G>((owned)equal_func);
		_size = items.length;
		_items = do_wrap<G> ((owned)items);
	}

	internal ArrayList.with_closure (owned Functions.EqualDataFuncClosure<G> equal_func) {
		_equal_func = equal_func;
		_items = new G[4];
		_size = 0;
	}

	/**
	 * {@inheritDoc}
	 */
	public override bool foreach(ForallFunc<G> f) {
		for (int i = 0; i < _size; i++) {
			if (!f (_items[i])) {
				return false;
			}
		}
		return true;
	}

	/**
	 * {@inheritDoc}
	 */
	public override Gee.Iterator<G> iterator () {
		return new Iterator<G> (this);
	}

	/**
	 * {@inheritDoc}
	 */
	public override ListIterator<G> list_iterator () {
		return new Iterator<G> (this);
	}

	/**
	 * {@inheritDoc}
	 */
	public override BidirListIterator<G> bidir_list_iterator () {
		return new Iterator<G> (this);
	}

	/**
	 * {@inheritDoc}
	 */
	public override bool contains (G item) {
		return (index_of (item) != -1);
	}

	/**
	 * {@inheritDoc}
	 */
	public override int index_of (G item) {
		for (int index = 0; index < _size; index++) {
			if (equal_func (_items[index], item)) {
				return index;
			}
		}
		return -1;
	}

	/**
	 * {@inheritDoc}
	 */
	public override G get (int index) {
		assert (index >= 0);
		assert (index < _size);

		return _items[index];
	}

	/**
	 * {@inheritDoc}
	 */
	public override void set (int index, G item) {
		assert (index >= 0);
		assert (index < _size);

		_items[index] = item;
	}

	/**
	 * {@inheritDoc}
	 */
	public override bool add (G item) {
		if (_size == _items.length) {
			grow_if_needed (1);
		}
		_items[_size++] = item;
		_stamp++;
		return true;
	}

	/**
	 * {@inheritDoc}
	 */
	public override void insert (int index, G item) {
		assert (index >= 0);
		assert (index <= _size);

		if (_size == _items.length) {
			grow_if_needed (1);
		}
		shift (index, 1);
		_items[index] = item;
		_stamp++;
	}

	/**
	 * {@inheritDoc}
	 */
	public override bool remove (G item) {
		for (int index = 0; index < _size; index++) {
			if (equal_func (_items[index], item)) {
				remove_at (index);
				return true;
			}
		}
		return false;
	}

	/**
	 * {@inheritDoc}
	 */
	public override G remove_at (int index) {
		assert (index >= 0);
		assert (index < _size);

		G item = _items[index];
		_items[index] = null;

		shift (index + 1, -1);

		_stamp++;
		return item;
	}

	/**
	 * {@inheritDoc}
	 */
	public override void clear () {
		for (int index = 0; index < _size; index++) {
			_items[index] = null;
		}
		_size = 0;
		_stamp++;
	}

	/**
	 * {@inheritDoc}
	 */
	public override List<G>? slice (int start, int stop) {
		return_val_if_fail (start <= stop, null);
		return_val_if_fail (start >= 0, null);
		return_val_if_fail (stop <= _size, null);

		var slice = new ArrayList<G>.with_closure (_equal_func);
		for (int i = start; i < stop; i++) {
			slice.add (this[i]);
		}

		return slice;
	}

	/**
	 * {@inheritDoc}
	 */
	public bool add_all (Collection<G> collection) {
		if (collection.is_empty) {
			return false;
		}

		grow_if_needed (collection.size);
		collection.foreach ((item) => {_items[_size++] = item; return true;});
		_stamp++;
		return true;
	}

	private void shift (int start, int delta) {
#if !DISABLE_INTERNAL_ASSERTS
		assert (start >= 0);
		assert (start <= _size);
		assert (start >= -delta);
#else
		assume (start >= 0);
		assume (start <= _size);
		assume (start >= -delta);
#endif

		_items.move (start, start + delta, _size - start);

		_size += delta;
	}

	private void grow_if_needed (int new_count) {
#if !DISABLE_INTERNAL_ASSERTS
		assert (new_count >= 0);
#else
		assume (new_count >= 0);
#endif

		int minimum_size = _size + new_count;
		if (minimum_size > _items.length) {
			// double the capacity unless we add even more items at this time
			set_capacity (new_count > _items.length ? minimum_size : 2 * _items.length);
		}
	}

	private void set_capacity (int value) {
#if !DISABLE_INTERNAL_ASSERTS
		assert (value >= _size);
#endif

		_items.resize (value);
	}

	private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G>, BidirListIterator<G> {
		public Iterator (ArrayList<G> list) {
			_list = list;
			_stamp = _list._stamp;
		}

		public Iterator.from_iterator (Iterator<G> iter) {
			_list = iter._list;
			_index = iter._index;
			_removed = iter._removed;
			_stamp = iter._stamp;
		}

		public bool next () {
			assert (_stamp == _list._stamp);
			if (_index + 1 < _list._size) {
				_index++;
				_removed = false;
				return true;
			}
			return false;
		}

		public bool has_next () {
			assert (_stamp == _list._stamp);
			return (_index + 1 < _list._size);
		}

		public bool first () {
			assert (_stamp == _list._stamp);
			if (_list.size == 0) {
				return false;
			}
			_index = 0;
			_removed = false;
			return true;
		}

		public new G get () {
			assert (_stamp == _list._stamp);
			assert (! _removed);
			assert (_index >= 0);
#if !DISABLE_INTERNAL_ASSERTS
			assert (_index < _list._size);
#else
			assume (_index < _list._size);
#endif
			return _list._items[_index];
		}

		public void remove () {
			assert (_stamp == _list._stamp);
			assert (! _removed && _index >= 0);
#if !DISABLE_INTERNAL_ASSERTS
			assert (_index < _list._size);
#else
			assume (_index < _list._size);
#endif
			_list.remove_at (_index);
			_index--;
			_removed = true;
			_stamp = _list._stamp;
		}

		public bool previous () {
			assert (_stamp == _list._stamp);
			if (_removed && _index >= 0) {
				_removed = false;
				return true;
			}
			if (_index > 0) {
				_index--;
				return true;
			}
			return false;
		}

		public bool has_previous () {
			assert (_stamp == _list._stamp);
			return (_index > 0 || (_removed && _index >= 0));
		}

		public bool last () {
			assert (_stamp == _list._stamp);
			if (_list.size == 0) {
				return false;
			}
			_index = _list._size - 1;
			return true;
		}

		public new void set (G item) {
			assert (_stamp == _list._stamp);
			assert (! _removed);
			assert (_index >= 0);
#if !DISABLE_INTERNAL_ASSERTS
			assert (_index < _list._size);
#else
			assume (_index < _list._size);
#endif
			_list._items[_index] = item;
			_stamp = ++_list._stamp;
		}

		public void insert (G item) {
			assert (_stamp == _list._stamp);
			assert (_index < _list._size);
			if (_index == -1) {
				_list.insert (0, item);
				_removed = true;
			}
			if (_removed) {
				_list.insert (_index + 1, item);
			} else {
				_list.insert (_index, item);
			}
			_index++;
			_stamp = _list._stamp;
		}

		public void add (G item) {
			assert (_stamp == _list._stamp);
			assert (_index < _list._size);
			_list.insert (_index + 1, item);
			_index++;
			_removed = false;
			_stamp = _list._stamp;
		}

		public int index () {
			assert (_stamp == _list._stamp);
			assert (_index >= 0);
			assert (_index < _list._size);
			return _index;
		}

		public bool read_only {
			get {
				return false;
			}
		}

		public bool valid {
			get {
				return _index >= 0 && _index < _list._size && ! _removed;
			}
		}

		public bool foreach (ForallFunc<G> f) {
			assert (_stamp == _list._stamp);
			if (_index < 0 || _removed) {
				_index++;
			}
			while (_index < _list._size) {
				if (!f (_list._items[_index])) {
					return false;
				}
				_index++;
			}
			_index = _list._size - 1;
			return true;
		}

		public Gee.Iterator<G>[] tee (uint forks) {
			if (forks == 0) {
				return new Gee.Iterator<G>[0];
			} else {
				Gee.Iterator<G>[] result = new Gee.Iterator<G>[forks];
				result[0] = this;
				for (uint i = 1; i < forks; i++) {
					result[i] = new Iterator<G>.from_iterator (this);
				}
				return result;
			}
		}

		protected ArrayList<G> _list;
		protected int _index = -1;
		protected bool _removed = false;
		protected int _stamp = 0;
	}

	private static G[] do_wrap<G> (owned G[] data) {
		var t = typeof (G);
		if (t == typeof (bool)) {
			return wrap_bool<G> ((bool[])data);
		} else if (t == typeof (char)) {
			return wrap_char<G> ((char[])data);
		} else if (t == typeof (uchar)) {
			return wrap_uchar<G> ((uchar[])data);
		} else if (t == typeof (int)) {
			return wrap_int<G> ((int[])data);
		} else if (t == typeof (uint)) {
			return wrap_uint<G> ((uint[])data);
		} else if (t == typeof (int64)) {
			return wrap_int64<G> ((int64[])data);
		} else if (t == typeof (uint64)) {
			return wrap_uint64<G> ((uint64[])data);
		} else if (t == typeof (long)) {
			return wrap_long<G> ((long[])data);
		} else if (t == typeof (ulong)) {
			return wrap_ulong<G> ((ulong[])data);
		} else if (t == typeof (float)) {
			return wrap_float<G> ((float?[])data);
		} else if (t == typeof (double)) {
			return wrap_double<G> ((double?[])data);
		} else if (t.is_enum () || t.is_flags ()) {
			return wrap_int<G> ((int[])data);
		} else {
			return (owned)data;
		}
	}

	private static G[] wrap_bool<G> (bool[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_char<G> (char[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_uchar<G> (uchar[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_int<G> (int[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_uint<G> (uint[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_int64<G> (int64[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_uint64<G> (uint64[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_long<G> (long[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_ulong<G> (ulong[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_float<G> (float?[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}

	private static G[] wrap_double<G> (double?[] data) {
		G[] arr = new G[data.length];
		for (uint i = 0; i < data.length; i++) {
			arr[i] = data[i];
		}
		return arr;
	}
}