frameworks/projects/framework/src/mx/utils/LinkedList.as

////////////////////////////////////////////////////////////////////////////////
//
//  Licensed to the Apache Software Foundation (ASF) under one or more
//  contributor license agreements.  See the NOTICE file distributed with
//  this work for additional information regarding copyright ownership.
//  The ASF licenses this file to You under the Apache License, Version 2.0
//  (the "License"); you may not use this file except in compliance with
//  the License.  You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
//
////////////////////////////////////////////////////////////////////////////////

package mx.utils
{
    
/**
 *  Provides a generic doubly linked list implementation.
 *  
 *  @langversion 3.0
 *  @playerversion Flash 10
 *  @playerversion AIR 1.5
 *  @productversion Flex 4.5
 */
public class LinkedList
{
    //--------------------------------------------------------------------------
    //
    //  Variables
    //
    //--------------------------------------------------------------------------
    
    private var _head:LinkedListNode;
    private var _tail:LinkedListNode;
    private var _length:Number = 0;
    
    //--------------------------------------------------------------------------
    //
    //  Constructor
    //
    //--------------------------------------------------------------------------
    
    /**
     *  Constructor. 
     *  
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function LinkedList():void
    {
        _head = new LinkedListNode();
        _tail = new LinkedListNode();
        _head.next = _tail;
        _tail.prev = _head;
    }

    //--------------------------------------------------------------------------
    //
    //  Properties
    //
    //--------------------------------------------------------------------------

    //----------------------------------
    //  head
    //----------------------------------
    
    /**
     *  Node representing head of the list.
     *
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function get head():LinkedListNode
    {
        return (_head.next == _tail) ? null : _head.next;
    }
    
    //----------------------------------
    //  length
    //----------------------------------
    
    /**
     *  Returns length of list.
     *
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function get length():Number
    {
        return _length;
    }
    
    //----------------------------------
    //  tail
    //----------------------------------
    
    /**
     *  Node representing tail of the list.
     *
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function get tail():LinkedListNode
    {
        return (_tail.prev == _head) ? null : _tail.prev;
    }
        
    //--------------------------------------------------------------------------
    //
    //  Class methods
    //
    //--------------------------------------------------------------------------
    
    /**
     *  Inserts new node after a previously existing node. 
     * 
     *  @param value Value to insert. If the value is not a LinkedListNode
     *  one will be created.
     * 
     *  @param prev The previous node to insert relative to.
     *  
     *  @return The new node.
     * 
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function insertAfter(value:*, prev:LinkedListNode):LinkedListNode
    {
        var node:LinkedListNode = makeNode(value);
        node.prev = prev;
        node.next = prev.next;
        node.prev.next = node;
        node.next.prev = node;
        
        _length++;
        return node;
    }
    
    /**
     *  Inserts new node before a previously existing node. 
     * 
     *  @param value Value to insert. If the value is not a LinkedListNode
     *  one will be created.
     * 
     *  @param prev The node to insert relative to.
     *  
     *  @return The new node.
     *  
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function insertBefore(value:*, next:LinkedListNode):LinkedListNode
    {
        var node:LinkedListNode = makeNode(value);
        
        node.prev = next.prev;
        node.next = next;
        node.prev.next = node;
        node.next.prev = node;
        
        _length++;
        return node;
    }
        
    /**
     *  Searches through all nodes for the given value.
     * 
     *  @param value The value to find.
     *
     *  @return The node location.
     *  
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function find(value:*):LinkedListNode
    {
        var cur:LinkedListNode = _head;
        while (cur.value != value && cur != _tail)
            cur = cur.next;
        return (cur == _tail) ? null : cur;
    }
    
    /**
     *  Searches through all nodes for the given value and
     *  removes it from the list if found.
     * 
     *  @param value The value to find and remove.
     *  @return The removed node, null otherwise.
     *  
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function remove(value:*):LinkedListNode
    {
        var node:LinkedListNode = getNode(value);
        if (node)
        {
            node.prev.next = node.next;
            node.next.prev = node.prev;  
            node.next = node.prev = null;
            _length--;
        }
        return node;
    }
    
    /**
     *  Push a new node to the tail of list.
     * 
     *  @param value The value to append.
     *  @return The newly appended node.
     *  
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function push(value:*):LinkedListNode
    {
        return insertAfter(value, _tail.prev);
    }
    
    /**
     *  Removes the node at the tail of the list.
     * 
     *  @return The removed node.
     *  
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function pop():LinkedListNode
    {
        return (_length == 0) ? null : remove(_tail.prev);  
    }
    
    /**
     *  Push a new node to the head of list.
     * 
     *  @param value The value to append.
     *  @return The newly appended node.
     *  
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function unshift(value:*):LinkedListNode
    {
        return insertAfter(value, _head);
    }
    
    /**
     *  Removes the node at the head of the list.
     * 
     *  @return The removed node.
     *  
     *  @langversion 3.0
     *  @playerversion Flash 10
     *  @playerversion AIR 1.5
     *  @productversion Flex 4.5
     */
    public function shift():LinkedListNode
    {
        return (_length == 0) ? null : remove(_head.next);
    }
    
    /**
     *  @private
     */
    protected function getNode(value:*):LinkedListNode
    {
        return (value is LinkedListNode) ? value : find(value);
    }
    
    /**
     *  @private
     */
    protected function makeNode(value:*):LinkedListNode
    {
        return (value is LinkedListNode) ? value : new LinkedListNode(value);
    }
}
}