01

train reservation in visual basic

Imports System.Collections.Generic

Public Class PriorityQueue2
    'Binary Heap as per:
    'http://www.brpreiss.com/books/opus4/html/page354.html
    'This turned out to be key for an efficient search.


    Private mList As List(Of PuzzleState)
    Private mCount As Integer = -1
    Private mCompare As PuzzleComparer

    Public Sub New()
        mList = New List(Of PuzzleState)
        mCompare = New PuzzleComparer
    End Sub

    Public Sub Push(ByVal x As PuzzleState)
        mList.Add(x)
        mCount += 1
        Dim i As Integer = mCount
        'if greater than child, move child up.... iteratively until no longer greater than child
        Do While i > 0 And mCompare.Compare(mList((i - 1) \ 2), x) > 0
            mList(i) = mList((i - 1) \ 2)
            i = (i - 1) \ 2
        Loop
        'Drop in where last child was moved from
        mList(i) = x
    End Sub


    Public Function Pop() As PuzzleState
        'Pop the lowest cost off the list (always at the root)
        Dim Result As PuzzleState = mList(0)
        Dim Last As PuzzleState = mList(mCount)

        mList.RemoveAt(mCount)
        mCount -= 1
        'List may be empty now.
        If mCount < 0 Then Return Result

        Dim i As Integer = 0
        Do While (2 * i + 1) < mCount + 1
            Dim Child As Integer = 2 * i + 1  'left child
            If (Child + 1 < mCount + 1) AndAlso (mCompare.Compare(mList(Child + 1), mList(Child)) < 0) Then
                Child += 1  'We want the right child instead
            End If
            If mCompare.Compare(Last, mList(Child)) < 0 Then
                Exit Do
            End If
            mList(i) = mList(Child)
            i = Child
        Loop
        mList(i) = Last

        Return Result


    End Function

    



    Private Function OnCompare(ByVal x As Integer, ByVal y As Integer) As Integer
        Dim psx As PuzzleState = DirectCast(mList(x), PuzzleState)
        Dim psy As PuzzleState = DirectCast(mList(y), PuzzleState)
        Return mCompare.Compare(psx, psy)


    End Function



End Class