Skip to content

Instantly share code, notes, and snippets.

@inspirit
Created June 19, 2011 16:56
Show Gist options
  • Save inspirit/1034474 to your computer and use it in GitHub Desktop.
Save inspirit/1034474 to your computer and use it in GitHub Desktop.
Fast & Simple Dual Linked List
package ru.inspirit.asfeat.struct
{
/**
* Simple but fast Dual Linked List approach
* Core implementation idea grabbed from Linux Kernel C source
*
* @author Eugene Zatepyakin
*/
public final class LList
{
public var head:LListNode;
public var count:int;
protected var _headPool:LListNode;
protected var _tailPool:LListNode;
protected var _poolSize:int;
// i assume u pre initiate the pool by specifying
// maximum capacity possible
// that will allow us not to init new instance during
// append and not to check pool size
public function LList(capacity:int)
{
// we need only head
// due to connection style we can easily access
// head or tail
head = new LListNode();
head.next = head;
head.prev = head;
count = 0;
_poolSize = 0;
if(capacity > 0) _headPool = _tailPool = new LListNode();
for (var i:int = 0; i < capacity; ++i)
{
var node:LListNode = new LListNode();
_tailPool = _tailPool.next = node;
_poolSize++;
}
}
public function append(obj:*, value:Number):LListNode
{
// assume we have enough free nodes
var node:LListNode = _headPool;
_headPool = _headPool.next;
_poolSize--;
node.foo = obj;
node.value = value;
var prev:LListNode = head.prev;
var next:LListNode = head;
// add to end
next.prev = node;
node.next = next;
node.prev = prev;
prev.next = node;
count++;
return node;
}
public function prepend(obj:*, value:Number):LListNode
{
// assume we have enough free nodes
var node:LListNode = _headPool;
_headPool = _headPool.next;
_poolSize--;
node.foo = obj;
node.value = value;
var prev:LListNode = head;
var next:LListNode = head.next;
// add to start
next.prev = node;
node.next = next;
node.prev = prev;
prev.next = node;
count++;
return node;
}
public function remove(node:MatchNode):void
{
// unlink
var prev:LListNode = node.prev;
var next:LListNode = node.next;
next.prev = prev;
prev.next = next;
node.next = null;
node.prev = null;
// reserve
_tailPool = _tailPool.next = node;
// dont forget to clear link to your Class/Object
node.foo = null;
_poolSize++;
count--;
}
// just moving nodes from List to Pool
public function clear():void
{
// safe iterate to allow remove
var h:LListNode = head;
var pos:LListNode = h.next;
var next:LListNode = pos.next;
for ( ; pos != h; pos = next, next = pos.next )
{
// unlink
var prev:LListNode = pos.prev;
next.prev = prev;
prev.next = next;
pos.next = null;
pos.prev = null;
// reserve
_tailPool = _tailPool.next = pos;
pos.foo = null;
_poolSize++;
}
count = 0;
}
protected const SORT_PARTITION:Vector.<LListNode> = new Vector.<LListNode>(21, true);
public function sort():void
{
var part:Vector.<LListNode> = SORT_PARTITION;
var lev:int;
var max_lev:int = 0;
var list:LListNode;
var cur:LListNode;
var _head:LListNode;
var _tail:LListNode;
var a:LListNode;
var b:LListNode;
// get temp node from pool
_head = _headPool;
_headPool = _headPool.next;
// unchain structure and extract list
head.prev.next = null;
list = head.next;
while( null != list )
{
cur = list;
list = list.next;
cur.next = null;
for(lev = 0; part[lev]; ++lev)
{
// merge
a = part[lev];
b = cur;
_head.next = _head.prev = null;
_tail = _head;
// thanx to Patrick Le Clec'h (@pleclech)
// for optimizing this loop
if(a)
{
var scoreA:Number = a.value;
if(b) {
var scoreB:Number = b.value;
for(; ;)
{
if(scoreA <= scoreB) {
a.prev = _tail;
_tail.next = _tail = a;
a = a.next;
if(a) scoreA = a.value;
else {
_tail.next = b;
break;
}
} else {
b.prev = _tail;
_tail.next = _tail = b;
b = b.next;
if(b) scoreB = b.value;
else {
_tail.next = a;
break;
}
}
}
} else _tail.next = a;
} else _tail.next = b;
cur = _head.next;
//
part[lev] = null;
}
// IntMath.max(max_lev, lev) @ apparat lib
max_lev = max_lev ^ ((max_lev ^ lev) & -int(max_lev < lev));
part[lev] = cur;
}
//
for (lev = 0; lev < max_lev; ++lev)
{
a = part[lev];
//if (part[lev])
if (a)
{
// merge
//a = part[lev];
b = list;
_head.next = _head.prev = null;
_tail = _head;
//if(a)
{
scoreA = a.value;
if(b) {
scoreB = b.value;
for(; ;)
{
if(scoreA <= scoreB) {
a.prev = _tail;
_tail.next = _tail = a;
a = a.next;
if(a) scoreA = a.value;
else {
_tail.next = b;
break;
}
} else {
b.prev = _tail;
_tail.next = _tail = b;
b = b.next;
if(b) scoreB = b.value;
else {
_tail.next = a;
break;
}
}
}
} else _tail.next = a;
}// else _tail.next = b;
list = _head.next;
//
part[lev] = null; //set to null for future use
}
}
//
// merge and restore back links
_tail = head;
// merge
a = part[max_lev];
b = list;
//if(a) // this cant be null
{
scoreA = a.value;
if(b) {
scoreB = b.value;
for(; ;)
{
if(scoreA <= scoreB) {
a.prev = _tail;
_tail.next = _tail = a;
a = a.next;
if(a) scoreA = a.value;
else {
_tail.next = b;
break;
}
} else {
b.prev = _tail;
_tail.next = _tail = b;
b = b.next;
if(b) scoreB = b.value;
else {
_tail.next = a;
break;
}
}
}
} else _tail.next = a;
} //else _tail.next = b;
//
do {
_tail.next.prev = _tail;
_tail = _tail.next;
} while (_tail.next);
_tail.next = head;
head.prev = _tail;
part[max_lev] = null;
// put back temp node
_head.next = _head.prev = null;
_tailPool = _tailPool.next = _head;
}
public function toString():String
{
var pos:LListNode;
var i:int = 0;
var str:String = 'LList\n\t[';
for ( pos = head.next; pos != head; pos = pos.next )
{
str += '\n\t' + i + ':\t'+ pos.value;
++i;
}
str += '\n\t];';
return str;
}
}
}
package ru.inspirit.asfeat.struct
{
/**
* Linked List Node structure
* @author Eugene Zatepyakin
*/
public final class LListNode
{
public var next:LListNode;
public var prev:LListNode;
// actually u can add any data to each node
public var foo:*;
// to compare during sort
public var value:Number;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment