/* slist.vala
 *
 * Copyright (C) 2004-2005  Novell, Inc
 * Copyright (C) 2005  David Waite
 * Copyright (C) 2007-2008  Jürg Billeter
 * Copyright (C) 2009  Julien Fontanet
 *
 * 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:
 * 	Julien Fontanet <julien.fontanet@isonoe.net>
 */

/**
 * Singly linked list implementation.
 */
public class Gee.SList<G> : GLib.Object, Gee.Iterable<G>, Gee.Collection<G>,
	Gee.List<G> {

	//public delegate int CompareFunc<G> (G a, G b);

	public int size {
		get { return this._size; }
	}

	public GLib.EqualFunc equal_func {
		set { this._equal_func = value; }
	}

	private Node<G> *_head = null;
	private int _size = 0;
	private GLib.EqualFunc _equal_func;

	// concurrent modification protection
	private int _stamp = 0;

	public SList (GLib.EqualFunc equal_func = GLib.direct_equal) {
		this.equal_func = equal_func;
	}

	~SList () {
		this.clear ();
	}

	public Type get_element_type () {
		return typeof (G);
	}

	public Gee.Iterator<G> iterator () {
		return new Iterator<G> (this);
	}

	public bool contains (G item) {
		return (this.index_of (item) != -1);
	}

	public int index_of (G item) {
		var node = this._head;
		int i = 0;
		while ((node != null) && (!_equal_func (node->data, item))) {
			node = node->next;
			++i;
		}
		if (i < this._size) {
			return i;
		}
		return -1;
	}

	public int index_of_sorted (G item, GLib.CompareFunc compare_func) {
		var node = this._head;
		int cmp = -1;
		int i = 0;
		while ((node != null) && ((cmp = compare_func (node->data, item)) < 0)) {
			node = node->next;
			++i;
		}
		if (cmp == 0) {
			return i;
		}
		return -1;
	}

	public new G? get (int index) {
		assert (index >= 0);
		assert (index < this._size);

		var node = this._head;
		while (index > 0) {
			node = node->next;
			assert (node != null); // Because index < this._size
			--index;
		}
		return node->data;
	}

	public new void set (int index, G item) {
		assert (index >= 0);
		assert (index < this._size);

		var node = this._head;
		while (index > 0) {
			node = node->next;
			assert (node != null); // Because index < this._size
			--index;
		}

		node->data = item;
	}

	/**
	 * Adds an item at the begining of the list.
	 *
	 * @see Gee.Collection#add(G)
	 */
	public bool add (G item) {
		this.insert_data (null, item);

		return true;
	}

	public void insert (int index, G item) {
		assert (index >= 0);
		assert (index <= this._size);

		if (index == 0) {
			this.insert_data (null, item);
			return;
		}

		var prev = this._head;
		while (index > 1) {
			prev = prev->next;
			assert (prev != null); // Because index <= this._size
			--index;
		}

		this.insert_data (prev, item);
	}

	public void insert_sorted (G item, GLib.CompareFunc compare_func) {
		Node *prev = null;
		var node = this._head;
		while ((node != null) && (compare_func (node->data, item) < 0)) {
			prev = node;
			node = node->next;
		}

		this.insert_data (prev, item);
	}

	public bool remove (G item) {
		Node<G> *prev = null;
		var node = this._head;
		while ((node != null) && (!_equal_func (node->data, item))) {
			prev = node;
			node = node->next;
		}

		if (node == null) { // Item not found.
			return false;
		}

		this.remove_node (prev, node);
		return true;
	}

	public bool remove_sorted (G item, GLib.CompareFunc compare_func) {
		if (this._head == null) {
			return false;
		}

		Node *prev = null;
		var node = this._head;
		int cmp = -1;
		while ((node != null) && ((cmp = compare_func (node->data, item)) < 0)) {
			prev = node;
			node = node->next;
			cmp = compare_func (node->data, item);
		}

		if (cmp != 0) { // Item not found.
			return false;
		}

		this.remove_node (prev, node);
		return true;
	}

	public void remove_at (int index) {
		assert (index >= 0);
		assert (index < this._size);

		Node<G> *prev = null;
		var node = this._head;
		while (index > 0) {
			prev = node;
			node = node->next;
			assert (node != null); // Because index < this._size
			--index;
		}

		this.remove_node (prev, node);
	}

	/**
	 * Reverses the list.
	 */
	public void reverse () { // Code from glib/gslist.c#g_slist_reverse
		Node *prev = null;
		var node = this._head;

		while (node != null) {
			Node *next = node->next;
			node->next = prev;
			prev = node;
			node = next;
		}

		this._head = prev;
	}

	public void clear () {
		if (this._size == 0) {
			assert (this._head == null);
			return;
		}

		var node = this._head;
		do {
			var prev = node;
			node = node->next;
			var data = (owned) prev->data; // Avoids memory leak
			delete prev;
		} while (node != null);

		this._size = 0;
		++this._stamp;
	}

	public 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 <= this._size, null);

		var slice = new SList<G> (this._equal_func);
		var node = this._head;
		stop -= start;
		while (start > 0) {
			assert (node != null); // start <= stop <= this._size
			node = node->next;
			--start;
		}
		while (stop > 0) {
			assert (node != null); // stop <= this._size
			slice.add (node->data);
			node = node->next;
			--stop;
		}

		slice.reverse ();

		return slice;
	}

	public G? pop () {
		if (this._head == null) {
			return null;
		}
		var data = (owned) this._head->data;
		var node = this._head;
		this._head = this._head->next;
		delete node;
		--this._size;
		++this._stamp;
		return data;
	}

	private inline void insert_data (Node *prev, G item) {
		Node *node = new Node<G>[1];
		node->data = item;
		this.insert_node (prev, node);
	}

	private void insert_node (Node *prev, Node *node) {
		assert (node != null);

		if (prev == null) {
			node->next = this._head;
			this._head = node;
		} else {
			node->next = prev->next;
			prev->next = node;
		}

		++this._size;
		++this._stamp;
	}

	private void remove_node (Node *prev, Node *node) {
		assert (node != null);

		if (prev == null) { // First item of the list.
			assert (this._head == node);
			this._head = node->next;
		} else {
			prev->next = node->next;
		}
		var data = (owned) node->data; // Avoids memory leak.
		delete node;
		--this._size;
		++this._stamp;
	}

	private struct Node<G> {
		public G data;
		public Node<G> *next;
	}

	private class Iterator<G> : Object, Gee.Iterator<G> {
		private SList<G> _list;
		private Node<G> *_current = null;
		private bool _done = false;

		// concurrent modification protection
		public int _stamp;

		public Iterator (SList list) {
			this._list = list;
			this._stamp = list._stamp;
		}

		public bool next () {
			assert (this._stamp == this._list._stamp);
			if (this._done) {
				return false;
			}

			if (this._current == null) {
				this._current = this._list._head;
			}
			else {
				this._current = this._current->next;
			}
			this._done = (this._current == null);
			return !(this._done);
		}

		public new G? get () {
			assert (this._stamp == this._list._stamp);
			assert (this._current != null);

			return this._current->data;
		}
	}
}

