' Copy Right: Dr Alexander J Turner, all rights reserved.
' You can use this code in any way you want as long as
' you mention I wrote it. Thanks
'
' A Simple linked list class for manipulating and accumulating
' data in VBScript
'
' e.g.
' list=new cLinkedList
' for i=1 to 100
'  list.Push i
' next i
'
' while list.size>0
'  WScript.echo list.UnShift()
' wend
'
' Last Modification:
' 17.05.2009 by Nic

Class cListLink

  Public before
  Public datum
  Public after

End Class

Class cLinkedList

  Private start_
  Private end_
  Private current_
  Private size_
  Private index_

  Private Sub Class_Initialize()
    start_ = Null
    end_ = Null
    current_ = Null
    size_ = 0
    index_ = 1
  End Sub

  Private Sub Class_Terminate()
    On Error Resume Next
    Me.Free
  End Sub

  Private Sub setDatum(ll, datum)
    If IsObject(datum) Then
      Set ll.datum = datum
    Else
      ll.datum = datum
    End If
  End Sub

  Private Sub getDatum(ll, datum)
    If IsObject(ll.datum) Then
      Set datum = ll.datum
    Else
      datum = ll.datum
    End If
  End Sub

  ' winds index to start quickly
  Public Sub Rewind()
    index_ = 1
    Set current_ = start_
  End Sub

  ' Winds index to end quickly
  Public Sub WindToEnd()
    index_ = Me.Size()
    Set current_ = end_
  End Sub

  ' Returns current index
  Public Function index()
    index = index_
  End Function

  ' Returns the current datum (which may be null) or
  ' null if the list is empty.
  ' Warning - this is ambiguous, you should check the
  ' size is bigger than 0 before getting datum if there
  ' is any chance that the list will be empty.
  Public Function datum()
    If IsNull(current_) Then
      datum = Null
    Else
      datum = current_.datum
    End If
  End Function

  ' Moves index on one if it can
  Public Sub MoveNext()
    If index_ < size_ Then
      Set current_ = current_.after
    End If
    index_ = index_ + 1
  End Sub

  ' Moves index back one if it can
  Public Sub MovePrevious()
    If index_ > 1 Then
      Set current_ = current_.before
    End If
    index_ = index_ - 1
  End Sub

  ' true if index is at the end of the list
  ' false otherwise
  Public Function EOF()
    If size_ > index_ Then
      EOF = False
    Else
      EOF = True
    End If
  End Function

  ' Retrieves a datum by index without changing
  ' the lists index.  This is slow as it must itterate
  ' through the list, please try and use enumeration
  ' via
  '   Rewind
  '   MoveNext
  ' or
  '   WindToEnd
  '   MovePrevious
  '
  ' if you are traversing all or a large part of the
  ' list
  Public Function Item(ByVal indx)
    If (index > size_) Or (indx < 1) Then
      Item = Null
    Else
      Set c = start_
      Dim i
      For i = 2 To indx
        Set c = c.after
      Next
      'Item=c.datum
      getDatum c, Item
    End If
  End Function

  Public Function SetItem(indx, datum)
    If (index > size_) Or (indx < 1) Then
      Item = Null
    Else
      Set c = start_
      Dim i
      For i = 2 To indx
        Set c = c.after
      Next
      'c.datum=datum
      setDatum c, datum
    End If
  End Function

  ' Add an item to the end of the list
  Public Sub Push(datum)
    If IsNull(end_) Then
      Set l = New cListLink
      Set start_ = l
      Set end_ = l
      Set current_ = l
      'l.datum=datum
      setDatum l, datum
      index_ = 1
      size_ = 1
    Else
      Set l = New cListLink
      Set end_.after = l
      Set l.before = end_
      Set end_ = l
      'end_.datum=datum
      setDatum end_, datum
      size_ = size_ + 1
    End If
  End Sub

  ' Add an item at the start of the list
  Public Sub Shift(datum)
    If IsNull(end_) Then
      Set l = New cListLink
      Set start_ = l
      Set end_ = l
      Set current_ = l
      'l.datum=datum
      setDatum l, datum
      index_ = 1
      size_ = 1
    Else
      Set l = New cListLink
      'l.datum = datum
      setDatum l, datum
      Set start_.before = l
      Set l.after = start_
      Set start_ = l
      size_ = size_ + 1
      index_ = index_ + 1
    End If
  End Sub

  ' Remove an item from the top of the list and return its value
  Public Function Pop()
    If size_ = 0 Then
      Pop = Null
    Else
      'Pop=end_.datum
      getDatum end_, Pop
      If size_ = 1 Then
        start_ = Null
        end_ = Null
        current_ = Null
        size_ = 0
      Else
        Set end_ = end_.before
        end_.after = Null
        If index_ = size_ Then
          Set current_ = end_
          index_ = index_ - 1
        End If
        size_ = size_ - 1
      End If
    End If
  End Function

  ' Remove an item from the end of the list and return its value
  Public Function UnShift()
    If size_ = 0 Then
      UnShift = Null
    Else
      'UnShift=start_.datum
      getDatum start_, UnShift
      If size_ = 1 Then
        start_ = Null
        end_ = Null
        current_ = Null
        size_ = 0
      Else
        Set start_ = start_.after
        start_.before = Null
        size_ = size_ - 1
        If index = 1 Then Set current_ = start_
      End If
    End If
  End Function

  ' How big is the list
  Public Function Size()
    Size = size_
  End Function

  ' Move the index
  Public Sub SetIndex(index)
    If index <= size_ Then
      Me.Rewind
      Dim i
      For i = 2 To index
        Me.MoveNext
      Next
    End If
  End Sub

  ' Add a list to the end of this list
  Public Sub AppendList(list)
    If list.Size = 0 Then Exit Sub
    Dim tmpIndex
    tmpIndex = list.index()
    list.Rewind
    While list.index() <= list.Size()
      Me.Push list.datum()
      list.MoveNext
    Wend
    list.SetIndex tmpIndex
  End Sub

  ' Add a list to the start of this list
  Public Sub PrependList(list)
    If list.Size = 0 Then Exit Sub
    tmpIndex = list.index()
    list.WindToEnd
    While list.index() > 0
      Me.Shift list.datum()
      list.MovePrevious
    Wend
    list.SetIndex tmpIndex
  End Sub

  ' Add all array elements to the end of the list
  Public Sub AppendArray(arr)
    If IsArray(arr) Then
      Dim v
      For Each v In arr
        Me.Push v
      Next
    End If
  End Sub

  ' Add all array elements to the start of the list
  Public Sub PrependArray(arr)
    If IsArray(arr) Then
      Dim i
      For i = UBound(arr) To LBound(arr) Step -1
        Me.Shift arr(i)
      Next
    End If
  End Sub

  ' return an array made of the elements of the list
  Public Function ToArray()
    Dim ret()
    If size_ = 0 Then
      ToArray = Null
      Exit Function
    End If
    If size_ = 1 Then
      ReDim ret(0)
      'ret(0)=start_.datum
      getDatum start_, ret(0)
      ToArray = ret
      Exit Function
    End If
    ReDim ret(size_ - 1)
    Dim tmpIndex
    tmpIndex = Me.index
    Me.Rewind
    Dim i
    i = 0
    Do
      'ret(i)=me.Datum
      getDatum current_, ret(i)
      Me.MoveNext
      i = i + 1
    Loop Until Me.EOF
    ret(i) = Me.datum
    Me.SetIndex tmpIndex
    ToArray = ret
  End Function

  ' Clear list
  Public Sub Free()
    If Me.Size = 0 Then Exit Sub
    While Me.Size > 0
      Me.UnShift
    Wend
  End Sub

End Class