/* linkedlist.vala
*
* Copyright (C) 2004-2005 Novell, Inc
* Copyright (C) 2005 David Waite
* Copyright (C) 2007-2008 Jürg Billeter
* Copyright (C) 2009 Mark Lee, 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:
* Mark Lee <marklee@src.gnome.org>
* Didier 'Ptitjes Villevalois <ptitjes@free.fr>
*/
using Gee.Utils.Assume;
/**
* Doubly-linked list implementation of the {@link List} interface.
*
* This implementation is pretty well designed for highly mutable data. When
* indexed access is privileged prefer using {@link ArrayList}.
*
* @see ArrayList
*/
public class Gee.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
private int _size = 0;
private int _stamp = 0;
private Node<G>? _head = null;
private weak Node<G>? _tail = null;
private Functions.EqualDataFuncClosure<G> _equal_func;
/**
* The elements' equality testing function.
*/
[CCode (notify = false)]
public EqualDataFunc<G> equal_func {
private set {}
get {
return _equal_func.func;
}
}
/**
* Constructs a new, empty linked 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 LinkedList (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);
}
private LinkedList.with_closures (owned Functions.EqualDataFuncClosure<G> equal_func) {
_equal_func = equal_func;
}
~LinkedList () {
this.clear ();
}
/**
* {@inheritDoc}
*/
public override bool foreach(ForallFunc<G> f) {
for (weak Node<G>? node = _head; node != null; node = node.next) {
if (!f (node.data)) {
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 int size {
get { return this._size; }
}
/**
* {@inheritDoc}
*/
public override bool read_only {
get { return false; }
}
/**
* {@inheritDoc}
*/
public override bool contains (G item) {
return this.index_of (item) != -1;
}
/**
* {@inheritDoc}
*/
public override bool add (G item) {
Node<G> n = new Node<G> (item);
if (this._head == null && this._tail == null) {
this._tail = n;
this._head = (owned) n;
} else {
n.prev = this._tail;
this._tail.next = (owned) n;
this._tail = this._tail.next;
}
// Adding items to the list during iterations is allowed.
//++this._stamp;
this._size++;
return true;
}
/**
* {@inheritDoc}
*/
public override bool remove (G item) { // Should remove only the first occurence (a test should be added)
for (weak Node<G> n = this._head; n != null; n = n.next) {
if (this.equal_func (item, n.data)) {
this._remove_node (n);
return true;
}
}
return false;
}
/**
* {@inheritDoc}
*/
public override void clear () {
while (_head != null) {
_remove_node (_head);
}
++this._stamp;
this._head = null;
this._tail = null;
this._size = 0;
}
/**
* {@inheritDoc}
*/
public override G get (int index) {
assert (index >= 0);
assert (index < this._size);
unowned Node<G>? n = this._get_node_at (index);
#if !DISABLE_INTERNAL_ASSERTS
assert (n != null);
#endif
return n.data;
}
/**
* {@inheritDoc}
*/
public override void set (int index, G item) {
assert (index >= 0);
assert (index < this._size);
unowned Node<G>? n = this._get_node_at (index);
return_if_fail (n != null);
n.data = item;
}
/**
* {@inheritDoc}
*/
public override int index_of (G item) {
int idx = 0;
for (weak Node<G>? node = _head; node != null; node = node.next, idx++) {
if (this.equal_func (item, node.data)) {
return idx;
}
}
return -1;
}
/**
* {@inheritDoc}
*/
public override void insert (int index, G item) {
assert (index >= 0);
assert (index <= this._size);
if (index == this._size) {
this.add (item);
} else {
Node<G> n = new Node<G> (item);
if (index == 0) {
n.next = (owned) this._head;
n.next.prev = n;
this._head = (owned)n;
} else {
weak Node prev = this._head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
n.prev = prev;
n.next = (owned) prev.next;
n.next.prev = n;
prev.next = (owned) n;
}
// Adding items to the list during iterations is allowed.
//++this._stamp;
this._size++;
}
}
/**
* {@inheritDoc}
*/
public override G remove_at (int index) {
assert (index >= 0);
assert (index < this._size);
unowned Node<G>? n = this._get_node_at (index);
#if !DISABLE_INTERNAL_ASSERTS
assert (n != null);
#endif
G element = n.data;
this._remove_node (n);
return element;
}
/**
* {@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 <= this._size, null);
List<G> slice = new LinkedList<G>.with_closures (_equal_func);
weak Node<G> n = this._get_node_at (start);
for (int i = start; i < stop; i++) {
slice.add (n.data);
n = n.next;
}
return slice;
}
/**
* {@inheritDoc}
*/
public G first () {
assert (_size > 0);
return _head.data;
}
/**
* {@inheritDoc}
*/
public G last () {
assert (_size > 0);
return _tail.data;
}
/**
* {@inheritDoc}
*/
public int capacity {
get { return UNBOUNDED_CAPACITY; }
}
/**
* {@inheritDoc}
*/
public int remaining_capacity {
get { return UNBOUNDED_CAPACITY; }
}
/**
* {@inheritDoc}
*/
public bool is_full {
get { return false; }
}
/**
* {@inheritDoc}
*/
public bool offer (G element) {
return offer_tail (element);
}
/**
* {@inheritDoc}
*/
public G? peek () {
return peek_head ();
}
/**
* {@inheritDoc}
*/
public G? poll () {
return poll_head ();
}
/**
* {@inheritDoc}
*/
public int drain (Collection<G> recipient, int amount = -1) {
return drain_head (recipient, amount);
}
/**
* {@inheritDoc}
*/
public bool offer_head (G element) {
insert (0, element);
return true;
}
/**
* {@inheritDoc}
*/
public G? peek_head () {
if (this._size == 0) {
return null;
}
return get (0);
}
/**
* {@inheritDoc}
*/
public G? poll_head () {
if (this._size == 0) {
return null;
}
return remove_at (0);
}
/**
* {@inheritDoc}
*/
public int drain_head (Collection<G> recipient, int amount = -1) {
if (amount == -1) {
amount = this._size;
}
for (int i = 0; i < amount; i++) {
if (this._size == 0) {
return i;
}
recipient.add (remove_at (0));
}
return amount;
}
/**
* {@inheritDoc}
*/
public bool offer_tail (G element) {
return add (element);
}
/**
* {@inheritDoc}
*/
public G? peek_tail () {
if (this._size == 0) {
return null;
}
return get (_size - 1);
}
/**
* {@inheritDoc}
*/
public G? poll_tail () {
if (this._size == 0) {
return null;
}
return remove_at (_size - 1);
}
/**
* {@inheritDoc}
*/
public int drain_tail (Collection<G> recipient, int amount = -1) {
if (amount == -1) {
amount = this._size;
}
for (int i = 0; i < amount; i++) {
if (this._size == 0) {
return i;
}
recipient.add (remove_at (this._size - 1));
}
return amount;
}
[Compact]
private class Node<G> { // Maybe a compact class should be used?
public G data;
public weak Node<G>? prev = null;
public Node<G>? next = null;
public Node (owned G data) {
this.data = data;
}
}
private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G>, BidirListIterator<G> {
public Iterator (LinkedList<G> list) {
this._list = list;
this._position = null;
this._index = -1;
this._stamp = list._stamp;
}
public Iterator.from_iterator (Iterator<G> iter) {
_removed = iter._removed;
_position = iter._position;
_stamp = iter._stamp;
_list = iter._list;
_index = iter._index;
}
public bool next () {
assert (this._stamp == this._list._stamp);
if (GLib.unlikely (_position == null)) {
#if !DISABLE_INTERNAL_ASSERTS
assert (!_removed);
#else
assume (!_removed);
#endif
if (_list._head != null) {
_position = _list._head;
_index = 0;
return true;
} else {
return false;
}
} else {
if (_position.next != null) {
_position = _position.next;
_index++;
_removed = false;
return true;
} else {
return false;
}
}
}
public bool has_next () {
assert (_stamp == _list._stamp);
if (GLib.unlikely (_position == null)) {
return _list._head != null;
} else {
return _position.next != null;
}
}
public bool first () {
assert (_stamp == _list._stamp);
if (_list.size == 0) {
return false;
}
_position = _list._head;
_index = 0;
_removed = false;
#if !DISABLE_INTERNAL_ASSERTS
assert (_position != null);
#endif
return true;
}
public new G get () {
assert (_stamp == _list._stamp);
assert (_position != null && !_removed);
return _position.data;
}
public void remove () {
assert (_stamp == _list._stamp);
assert (_position != null && !_removed);
unowned Node<G>? new_position = _position.prev;
_list._remove_node (_position);
_position = new_position;
if (_position != null) {
_removed = true;
}
_index--;
_stamp = _list._stamp;
}
public bool previous () {
assert (_stamp == _list._stamp);
if (GLib.likely (_position != null)) {
if (GLib.unlikely (_removed)) {
_removed = false;
return true;
} else if (GLib.likely(_position.prev != null)) {
_position = _position.prev;
_index--;
return true;
} else {
return false;
}
} else {
return false;
}
}
public bool has_previous () {
assert (_stamp == _list._stamp);
if (GLib.likely (_position != null)) {
if (GLib.unlikely (_removed)) {
return true;
} else {
return _position.prev != null;
}
} else {
return false;
}
}
public bool last () {
assert (_stamp == _list._stamp);
if (_list.size == 0) {
return false;
}
_position = _list._tail;
_index = _list._size - 1;
#if !DISABLE_INTERNAL_ASSERTS
assert (_position != null);
#endif
return true;
}
public new void set (G item) {
assert (_stamp == _list._stamp);
assert (_position != null && !_removed);
_position.data = item;
}
public void insert (G item) {
assert (_stamp == _list._stamp);
Node<G> n = new Node<G> (item);
unowned Node<G> n_ref = n;
if (_position == null) {
Node<G>? position = (owned)_list._head;
if (position != null) {
position.prev = n;
n.next = (owned)position;
} else {
#if !DISABLE_INTERNAL_ASSERTS
assert (_list._tail == null);
#endif
_list._tail = n;
}
if (_position == null) {
_position = n_ref;
}
_list._head = (owned)n;
} else {
if (_removed) {
if (_position.next != null) {
n.next = (owned)_position.next;
n.next.prev = n;
} else {
_list._tail = n;
}
n.prev = _position;
_position.next = (owned)n;
_position = n_ref;
} else {
n.prev = _position.prev;
_position.prev = n;
if (n.prev != null) {
n.next = (owned)n.prev.next;
n.prev.next = (owned)n;
} else {
n.next = (owned)_list._head;
_list._head = (owned)n;
}
}
}
_list._size++;
_index++;
_stamp = _list._stamp;
}
public void add (G item) {
assert (_stamp == _list._stamp);
Node<G> n = new Node<G> (item);
unowned Node<G> n_ref = n;
if (_position == null) {
Node<G> position = (owned)_list._head;
position.prev = n;
n.next = (owned)position;
_list._head = (owned) n;
} else {
if (_position.next != null) {
_position.next.prev = n;
n.next = (owned)_position.next;
} else {
_list._tail = n;
}
_position.next = (owned)n;
_position.next.prev = _position;
}
_position = n_ref;
_removed = false;
_list._size++;
_index++;
_stamp = _list._stamp;
}
public int index () {
assert (_stamp == _list._stamp);
assert (_position != null && !_removed);
return _index;
}
public bool read_only {
get {
return false;
}
}
public bool valid {
get {
return !_removed && _position != null;
}
}
public bool foreach (ForallFunc<G> f) {
assert (_stamp == _list._stamp);
if (_position == null) {
_position = _list._head;
}
if (_removed) {
_position = _position.next;
_removed = false;
}
while (_position != null) {
if (!f (_position.data)) {
return false;
}
_position = _position.next;
}
_position = _list._tail;
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 bool _removed = false;
protected unowned Node<G>? _position;
protected int _stamp;
protected LinkedList<G> _list;
protected int _index;
}
private unowned Node<G>? _get_node_at (int index) {
unowned Node<G>? n = null;;
if (index == 0) {
n = this._head;
} else if (index == this._size - 1) {
n = this._tail;
} else if (index <= this._size / 2) {
n = this._head;
for (int i = 0; index != i; i++) {
n = n.next;
}
} else {
n = this._tail;
for (int i = this._size - 1; index != i; i--) {
n = n.prev;
}
}
return n;
}
private void _remove_node (Node<G> _n) {
Node<G> n;
weak Node<G> next;
if (_n == this._head) {
n = (owned) this._head;
next = this._head = (owned) n.next;
} else {
n = (owned) _n.prev.next;
next = n.prev.next = (owned) n.next;
}
if (n == this._tail) {
this._tail = n.prev;
} else {
next.prev = n.prev;
}
n.prev = null;
n.next = null;
n.data = null;
++this._stamp;
this._size--;
}
}