' Copyright (c) 2009, Insomnia 24/7 All rights reserved.
 
'  Redistribution and use in source and binary forms, with or without
'  modification, are permitted provided that the following conditions are met:
 
'  Redistributions of source code must retain the above copyright notice, this
'  list of conditions and the following disclaimer. Redistributions in binary
'  form must reproduce the above copyright notice, this list of conditions and
'  the following disclaimer in the documentation and/or other materials
'  provided with the distribution. Neither the name of Insomnia 24/7 nor
'  the names of its contributors may be used to endorse or promote products
'  derived from this software without specific prior written permission.
 
'  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
'  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
'  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
'  ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR
'  ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
'  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
'  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
'  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
'  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
'  OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
'  DAMAGE.
 
Module LinkedList
 
    ' This class provides a linked list
    Public Class LinkedList
        Private Length As Integer = 0
        Private first As Node
        Private last As Node
        Private firstSet As Boolean = False
 
        ' Constructor for the LinkedList class
        Public Sub New()
        End Sub
 
        ' Add an object to the end of the list
        Public Sub Push(ByVal d As Object)
            If firstSet Then
                Dim n As Node = New Node(d, last)
                last.setChild(n)
                last = n
            Else
                first = New Node(d)
                last = first
                firstSet = True
            End If
            Length += 1
        End Sub
 
        ' View last nodes data and remove last node
        Public Function Pop() As Object
            If Length > 0 Then
                Dim tmpData As Object = last.GetData()
                Dim newLast As Node = last.getParent()
                last = Nothing
                last = newLast
                Length -= 1
                Return tmpData
            Else
                Throw New IndexOutOfRangeException
            End If
        End Function
 
        ' View last nodes data
        Public Function Peek() As Object
            If Length > 0 Then
                Return last.GetData
            Else
                Throw New IndexOutOfRangeException
            End If
        End Function
 
        ' Return the value for a specific item in the list
        Public Function Peek(ByVal key As Integer) As Object
            key -= 1
            If Length - 1 <= key Then
                Throw New IndexOutOfRangeException
            ElseIf Length = key Then
                Return last.GetData
            ElseIf key = 0 Then
                Return first.GetData
            Else
                Dim currentNode As Node
                currentNode = first
                Dim i As Integer
 
                For i = 0 To key
                    Dim tmpNode As Node = currentNode.getChild()
                    currentNode = tmpNode
                Next i
                Return currentNode.GetData
            End If
        End Function
 
        ' Returns the number of elements in the list
        Public Function Size() As Integer
            Return Length
        End Function
 
    End Class
 
    ' This class stores the data and information about it's parent and child node
    ' You should never have to call this class yourself, they're created and managed by the LinkedList class.
    Public Class Node
        Private first As Boolean = False
        Private hasChild As Boolean = False
        Private child As Node
        Private parent As Node
        Private data As Object
 
        ' Node constructor for first node in the list
        Public Sub New(ByVal d As Object)
            first = True
            data = d
        End Sub
 
        ' Node constructor for following nodes
        Public Sub New(ByVal d As Object, ByRef p As Node)
            data = d
            parent = p
        End Sub
 
        ' Function used to assign a child node reference when one is created
        Public Sub setChild(ByRef c As Node)
            hasChild = True
            child = c
        End Sub
 
        ' Returns a reference to it's child node if it has one
        Public Function getChild() As Node
            If hasChild Then
                Return child
            Else
                Throw New IndexOutOfRangeException
            End If
        End Function
 
        ' Returns reference to it's parent node if it has one
        Public Function getParent() As Node
            If Not first Then
                Return parent
            Else
                Throw New IndexOutOfRangeException
            End If
        End Function
 
        ' Returns node data
        Public Function GetData() As Object
            Return data
        End Function
    End Class
End Module