/* singlylinkedlist.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.SinglyLinkedList<G> : AbstractCollection<G>, Iterable<G>, Collection<G>, List<G> {
	public override int size {
		get {
			return this._size;
		}
	}

	public EqualFunc equal_func {
		get; set;
	}

	private Node<G> *_head = null;
	private Node<G> *_tail = null;

	private int _size = 0;

	// Concurrent modification protection.
	private int _stamp = 0;

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

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

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

	public override 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) && !this.equal_func (node->data, item)) {
			node = node->next;
			++i;
		}
		if (i != this._size) { // Found
			return i;
		}
		return -1;
	}

	/**
	 * Returns the index of the first item equals to @item in the list.
	 *
	 * This method is equivalent to List.index_of but is more efficient because
	 * it uses the fact that the list is sorted.
	 *
	 * @param item         The item we are looking for.
	 * @param compare_func This function compares two items of the list with the
	 *                     same relation of the list.
	 *
	 * @return The index of the item if found, -1 otherwise.
	 *
	 * @see Gee.List.index_of
	 */
	public int index_of_sorted (G item, 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) {
		return get_node_at (index)->data;
	}

	public new void set (int index, G item) {
		get_node_at (index)->data = item;
	}

	public override bool add (G item) {
		this.insert_data (this._tail, item);

		return true;
	}

	public void insert (int index, G item) {
		if (index == 0) {
			this.insert_data (null, item);
		} else {
			this.insert_data (this.get_node_at (index - 1), item);
		}
	}

	/**
	 * Inserts a item at its correct position in a sorted SinglyLinkedList.
	 *
	 * @param item         The item to remove.
	 * @param compare_func This function defines the order of the list.
	 */
	public void insert_sorted (G item, CompareFunc compare_func) {
		Node<G> *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);
	}

	/**
	 * Inserts an item at the begining of the list.
	 *
	 * This method is equivalent List.insert (0, item).
	 *
	 * @param item The item to insert.
	 *
	 * @see Gee.List.insert
	 */
	public void prepend (G item) {
		this.insert_data (null, item);
	}

	public override 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;
	}

	/**
	 * Removes a item in a sorted SinglyLinkedList.
	 *
	 * This method  is equivalent  to List.remove but  is more efficient if the
	 * list is sorted.
	 *
	 * @param item         The item to remove.
	 * @param compare_func This function compares two items of the list with the
	 *                     same relation of the list.
	 *
	 * @return True if the list is modified, else otherwise.
	 *
	 * @see Gee.Collection.remove
	 */
	public bool remove_sorted (G item, CompareFunc compare_func) {
		if (this._head == null) {
			return false;
		}

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

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

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

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

		if (index == 0) {
			this.remove_node (null, this._head);
		} else {
			var prev = this.get_node_at (index - 1);
			this.remove_node (prev, prev->next);
		}
	}

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

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

		this._head = prev;
	}

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

		var node = this._head;
		do {
			var prev = node;
			node = node->next;

			prev->data = null; // Avoids memory leak.

			delete prev;
		} while (node != null);

		this._head = null;
		this._tail = null;
		this._size = 0;
		++this._stamp;
	}

	public List<G>? slice (int start, int stop) {
		return_val_if_fail (start >= 0, null);
		return_val_if_fail (start <= stop, null);
		return_val_if_fail (stop <= this._size, null);

		var slice = new SinglyLinkedList<G> (this.equal_func);

		if (start == stop) { // No items.
			return slice;
		}

		var node = this.get_node_at (start);
		stop -= start;
		do {
			assert (node != null); // stop <= (_size - start)
			slice.add (node->data);
			node = node->next;
		} while (--stop > 0);

		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;

		if (this._head == null) {
			this._tail = null;
		}

		--this._size;
		++this._stamp;
		return data;
	}

	private Node *get_node_at (int index) {
		assert (index >= 0);
		assert (index < this._size);

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

			node = node->next;
			--index;
		}

		return node;
	}

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

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

		if (prev == null) {
			if (this._head == null) {
				this._tail = node;
			} else {
				this._tail = this._head;
			}

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

			node->next = prev->next;
			prev->next = node;
		}

		++this._size;

		// Adding items to the list during iterations is allowed.
		//++this._stamp;
	}

	private void remove_node (Node<G> *prev, Node<G> *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;
		}

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

		node->data = null; // 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 SinglyLinkedList<G> _list;
		private Node<G> *_current;
		private bool _first = true;

		// Concurrent modification protection.
		public int _stamp;

		public Iterator (SinglyLinkedList<G> list) {
			this._list = list;
			this._current = this._list._head;
			this._stamp = list._stamp;
		}

		public bool next () {
			assert (this._stamp == this._list._stamp);

			if (this._first) { // Only on the first pass _current can be null.
				if (this._current == null) {
					return false;
				}
				this._first = false;
				return true;
			}
			if (this._current->next == null) {
				return false;
			}
			this._current = this._current->next;
			return true;
		}

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

			return this._current->data;
		}
	}
}

