Fast & Simple Dual Linked List

LList.as

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

}