// Copyright (c) Ralph Varjabedian http://varjabedian.net
//
// vnetLinkedlist.js v 1.1.0
// A file containing an implementation of a double linked list data structure,queue,stack
// July 2008
// 
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


/*************** LinkedListClass ***************/
LinkedListClass = function()
{
    /// <summary>The LinkedListClass is an implementation of a double linked list</summary>
    
	this.IsLinkedListClass = true;
	
    this.linkedList = null;
    this.linkedListEnd = null;
    this.count = 0;
}

LinkedListClass.prototype = 
{
    Add : function(object)
    {
        /// <summary>Adds a new object to the linked list at the end</summary>
        
        if (this.linkedList == null) // empty list
        {
            this.linkedList = new LinkedListNodeClass(this);
            this.linkedList.object = object;
            this.linkedListEnd = this.linkedList;
        }
        else
        {
            this.linkedListEnd.next = new LinkedListNodeClass(this);
            this.linkedListEnd.next.prev = this.linkedListEnd;
            this.linkedListEnd = this.linkedListEnd.next;
            this.linkedListEnd.object = object;
        }
        this.count++;
    },

    RemoveByObject : function(object)
    {
        /// <summary>Removes a node given the object it holds, if the node is not found, it returns false</summary>
        
        if (!this.HasNodes())
            return false;
            
        var traverse = this.GetListStart();
        
        while (traverse)
        {
            if (traverse.object == object)
            {
                traverse.Remove();
                return true;
            }
           traverse = traverse.Next();
        }
        
        return false;
    },

    GetListStart : function()
    {
        /// <summary>Gets the first Node</summary>
        
        return this.linkedList;
    },

    GetListEnd : function()
    {
        /// <summary>Gets the last Node</summary>
        
        return this.linkedListEnd;
    },

    GetSize : function()
    {
        /// <summary>Gets the size of the list</summary>
        
        return this.count;
    },

    HasNodes : function()
    {
        /// <summary>Returns true if the list has nodes</summary>
        
        return this.count > 0;
    },

    /***** Private ******/
    _InsertAfter : function(node, object)
    {
        if (!node.IsLinkedListNodeClass)
            throw "not a node";
        if (node.linkedListObject != this)
            throw "node does not belong to this list";

        var oldNextNode = node.next;
        
        node.next = new LinkedListNodeClass(this);
        node.next.prev = node;
        node = node.next;
        node.object = object;
        node.next = oldNextNode;
        if (oldNextNode != null)
            oldNextNode.prev = node;
        
        if (this.linkedListEnd == node.prev)
            this.linkedListEnd = node;
            
        this.count++;
    },

    _InsertBefore : function(node, object)
    {
        if (!node.IsLinkedListNodeClass)
            throw "not a node";
        if (node.linkedListObject != this)
            throw "node does not belong to this list";

        var oldPrevNode = node.prev;
        
        node.prev = new LinkedListNodeClass(this);
        node.prev.next = node;
        node = node.prev;
        node.object = object;
        node.prev = oldPrevNode;
        if (oldPrevNode != null)
            oldPrevNode.next = node;
        
        if (this.linkedList == node.next)
            this.linkedList = node;
            
        this.count++;
    },

    _Remove : function(node)
    {
        if (!node.IsLinkedListNodeClass)
            throw "not a node";
        if (node.linkedListObject != this)
            throw "node does not belong to this list";
            
        if (node.prev == null) // first node
        {
            this.linkedList = node.next;
            if (this.linkedListEnd == node)
                this.linkedListEnd = this.linkedList;
            if (this.linkedList)            
                this.linkedList.prev = null;            
        }
        else if (node.next == null) // last node
        {
            node.prev.next = null;
            this.linkedListEnd = node.prev;
        }
        else // in the middle
        {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }        
        
        this.count--;
        node.next = null;
        node.prev = null;
        node = null;
    },
    /***** Private ******/
    
    _end : null
}
/*************** LinkedListClass ***************/



/*************** LinkedListNodeClass ***************/

LinkedListNodeClass = function(linkedListObject)
{
    /// <summary>The LinkedListNodeClass is the node of a double linked list</summary>
    if (!linkedListObject.IsLinkedListClass)
        throw "not a linked list class";

	this.IsLinkedListNodeClass = true;
    
    this.object = null;
    this.next = null;
    this.prev = null;
	
	this.linkedListObject = linkedListObject;
}

LinkedListNodeClass.prototype = 
{
    GetObject : function()
    {
        /// <summary>Returns the object that the Node is attached to</summary>
        
        return this.object;
    },
    
    Next : function()
    {
        /// <summary>Returns the next node or null if there is no more</summary>
        
        return this.next;
    },

    Previous : function()
    {
        /// <summary>Returns the previous node or null if there is no more</summary>
        
        return this.prev;
    },

    Remove : function()
    {
        /// <summary>Removes the Node from its containing list</summary>
        
        this.linkedListObject._Remove(this);
    },

    InsertAfter : function(object)
    {
        /// <summary>Inserts an Object after this Node</summary>
    
        this.linkedListObject._InsertAfter(this, object);
    },

    InsertBefore : function(object)
    {
        /// <summary>Inserts an Object before this Node</summary>
    
        this.linkedListObject._InsertBefore(this, object);
    },
    
    _end : null
}
/*************** LinkedListNodeClass ***************/


/*************** StackClass ***************/
StackClass = function()
{
    this.linkedList = new LinkedListClass();
}

StackClass.prototype = 
{
    Push : function(obj)
    {
        this.linkedList.Add(obj);
    },

    HasElements : function()
    {
        return this.linkedList.HasNodes();
    },
    
    GetCount : function()
    {
        return this.linkedList.GetSize();
    },
    
    Peek : function()
    {
        var node = this.linkedList.GetListEnd();
        if (node == null)
            return null;
        return node.object;
    },
    
    Pop : function()
    {
        var node = this.linkedList.GetListEnd();
        if (node == null)
            return null;
        var object = node.object;
        node.Remove();
        return object;
    }
}
/*************** StackClass ***************/


/*************** QueueClass ***************/
QueueClass = function()
{
    this.linkedList = new LinkedListClass();
}

QueueClass.prototype = 
{
    Push : function(obj)
    {
        this.linkedList.Add(obj);
    },

    HasElements : function()
    {
        return this.linkedList.HasNodes();
    },
    
    GetCount : function()
    {
        return this.linkedList.GetSize();
    },
    
    Peek : function()
    {
        var node = this.linkedList.GetListStart();
        if (node == null)
            return null;
        return node.object;
    },
    
    Pop : function()
    {
        var node = this.linkedList.GetListStart();
        if (node == null)
            return null;
        var object = node.object;
        node.Remove();
        return object;
    }
}
/*************** QueueClass ***************/