topical media & game development
lib-as-de-polygonal-ds-DLinkedList.ax
lib-as-de-polygonal-ds-DLinkedList.ax
(swf
)
[ flash
]
flex
Copyright (c) Michael Baczynski 2007
http://lab.polygonal.de/ds/
This software is distributed under licence. Use of this software
implies agreement with all terms and conditions of the accompanying
software licence.
package de.polygonal.ds
{
import de.polygonal.ds.Iterator;
import de.polygonal.ds.Collection;
import de.polygonal.ds.DListNode;
import de.polygonal.ds.DListIterator;
A doubly linked list.
<p>A doubly linked list stores a reference to the next
and previous node which makes it possible to traverse
the list in both directions.</p>
public class @ax-lib-as-de-polygonal-ds-DLinkedList implements Collection
{
private var _count:int;
The head node being referenced.
public var head:DListNode;
The tail node being referenced.
public var tail:DListNode;
Initializes an empty list.
public function @ax-lib-as-de-polygonal-ds-DLinkedList()
{
head = tail = null;
_count = 0;
}
Appends an item to the list.
parameter: obj The data.
returns: A doubly linked list node wrapping the data.
public function append(obj:*):DListNode
{
var node:DListNode = new DListNode(obj);
if (head)
{
tail.insertAfter(node);
tail = tail.next;
}
else
head = tail = node;
_count++;
return node;
}
Prepends an item to the list.
parameter: obj The data.
returns: A doubly linked list node wrapping the data.
public function prepend(obj:*):DListNode
{
var node:DListNode = new DListNode(obj);
if (head)
{
head.insertBefore(node);
head = head.prev;
}
else
head = tail = node;
_count++;
return node;
}
Inserts an item after a given iterator or appends it
if the iterator is invalid.
parameter: itr A doubly linked list iterator.
parameter: obj The data.
returns: A doubly linked list node wrapping the data.
public function insertAfter(itr:DListIterator, obj:*):DListNode
{
if (itr.list != this) return null;
if (itr.node)
{
var node:DListNode = new DListNode(obj);
itr.node.insertAfter(node);
if (itr.node == tail)
tail = itr.node.next;
_count++;
return node;
}
else
return append(obj);
}
Inserts an item before a given iterator or appends it
if the iterator is invalid.
parameter: itr A doubly linked list iterator.
parameter: obj The data.
returns: A doubly linked list node wrapping the data.
public function insertBefore(itr:DListIterator, obj:*):DListNode
{
if (itr.list != this) return null;
if (itr.node)
{
var node:DListNode = new DListNode(obj);
itr.node.insertBefore(node);
if (itr.node == head)
head = head.prev;
_count++;
return node;
}
else
return prepend(obj);
}
Removes the node the iterator is pointing
at and moves the iterator to the next node.
returns: True if the removal succeeded, otherwise false.
public function remove(itr:DListIterator):Boolean
{
if (itr.list != this || !itr.node) return false;
var node:DListNode = itr.node;
if (node == head)
head = head.next;
else
if (node == tail)
tail = tail.prev;
itr.forth();
node.unlink();
if (head == null) tail = null;
_count--;
return true;
}
Removes the head of the list.
public function removeHead():void
{
if (head)
{
head = head.next;
if (head)
head.prev = null;
else
tail = null
_count--;
}
}
Removes the tail of the list.
public function removeTail():void
{
if (tail)
{
tail = tail.prev;
if (tail)
tail.next = null;
else
head = null;
_count--;
}
}
Checks if a given item exists.
returns: True if the item is found, otherwise false.
public function contains(obj:*):Boolean
{
var node:DListNode = head;
while (node)
{
if (node.data == obj) return true;
node = node.next;
}
return false;
}
Clears the list by unlinking all nodes
from it. This is important to unlock
the nodes for the garbage collector.
public function clear():void
{
var node:DListNode = head;
head = null;
var next:DListNode;
while (node)
{
next = node.next;
node.next = node.prev = null;
node = next;
}
_count = 0;
}
Creates an iterator object pointing
at the first node in the list.
returns: An iterator object.
public function getIterator():Iterator
{
return new DListIterator(this, head);
}
Creates a doubly linked iterator object pointing
at the first node in the list.
returns: A DListIterator object.
public function getListIterator():DListIterator
{
return new DListIterator(this, head);
}
The total number of nodes in the list.
public function get size():int
{
return _count;
}
Checks if the list is empty.
public function isEmpty():Boolean
{
return _count == 0;
}
Converts the linked list into an array.
returns: An array.
public function toArray():Array
{
var a:Array = [];
var node:DListNode = head;
while (node)
{
a.push(node.data);
node = node.next;
}
return a;
}
Returns a string representing the current object.
public function toString():String
{
return "[@ax-lib-as-de-polygonal-ds-DLinkedList > has " + size + " nodes]";
}
Prints out all elements in the list (for debug/demo purposes).
public function dump():String
{
if (head == null) return "@ax-lib-as-de-polygonal-ds-DLinkedList, empty";
var s:String = "@ax-lib-as-de-polygonal-ds-DLinkedList, has " + _count + " node" + (_count == 1 ? "" : "s") + "\n|< Head\n";
var itr:DListIterator = getListIterator();
for (; itr.valid(); itr.forth())
s += "\t" + itr.data + "\n";
s += "Tail >|";
return s;
}
}
}
(C) Æliens
20/2/2008
You may not copy or print any of this material without explicit permission of the author or the publisher.
In case of other copyright issues, contact the author.
