Strict

import mojo

Global myGame:MyGame

Function Main:int()
    myGame = new MyGame
    return 0
End Function

Class MyGame extends App
    Field list:LinkedList<Alien>

    Method OnCreate:Int()

        list = New LinkedList<Alien>

        Local a:Alien = new Alien()
        a.name = "Fred"
        list.AddLast(a)

        a = new Alien()
        a.name = "George"
        list.AddLast(a)

        For Local a:Alien = Eachin list
            Print a.name
        Next
        Print list.Count()

        list.Sort()

        SetUpdateRate 60
        return 0
    End Method

    Method OnLoading:Int()
        return 0
    End Method

    Method OnUpdate:Int()
        return 0
    End Method

    Method OnRender:Int()
        Cls

        return 0
    End Method
end class

Class Sprite
    Field x#, y#
End

Class Alien Extends Sprite
    Field name$
End

Class LinkedList<T>
    Field head:LinkedNode<T> = New LinkedNode<T>

    Method AddLast:LinkedNode<T>( data:T )
        Return New LinkedNode<T>( head, head.pred, data )
    End

    Method ObjectEnumerator:LinkedEnumerator<T>()
        Return New LinkedEnumerator<T>( Self )
    End Method

    Method Count:Int()
        Local n:Int
        local node := head.succ
        While node <> head
            node = node.succ
            n+=1
        Wend
        Return n
    End

    Method FirstLink:LinkedNode<T>()
        Return head.succ
    End


    Method Sort:Void( ascending?=True )
        Print "sort"
        Local h:LinkedNode<T> = FirstLink( )
        If h = Null Then Return
        If h.NextLink( ) = Null Then Return ' No need to sort one element
        h = ISort( h, head )
        head.succ = h
        While h.NextLink( )
            h = h.NextLink( )
        Wend
'         If Not ascending Then Swap Reversed( )
    End Method

    ' Internal sort function
    Method ISort:LinkedNode<T>( h:LinkedNode<T>, oh:LinkedNode<T> )
        Print "sorting"
        Local p:LinkedNode<T>, q:LinkedNode<T>, e:LinkedNode<T>, tail:LinkedNode<T>, oldhead:LinkedNode<T>
        Local insize%, merges%, psize%, qsize%, i%
        If h = Null Then Return null
        insize = 1
        While True
            p = h
            oldhead = h
            h = Null
            tail = Null
            merges = 0
            While p
                merges += 1
                q = p
                psize = 0
                For i = 0 To insize-1
                   psize += 1
                   q = q.NextLink( )
                   If Not q Then Exit
                Next

                qsize = insize

                While psize > 0 Or ( qsize > 0 And q )
                    If psize = 0 Then
                       e = q
                       q = q.NextLink( )
                       qsize -= 1
                    ElseIf qsize = 0 Or Not q
                       e = p
                       p = p.NextLink( )
                       psize -= 1
                    Else
                       Local cmp%
                       If p.data And q.data Then
                            'cmp = p.data.Compare( q.data )
                         cmp = Compare(  p.data, q.data )
                        ElseIf p.data
                            cmp = -1
                        ElseIf q.data
                            cmp = 1
                        Else
                            cmp = 0
                        EndIf

                        If cmp <= 0 Then
                            e = p
                            p = p.NextLink( )
                            psize -= 1
                        Else
                            e = q
                            q = q.NextLink( )
                            qsize -= 1
                        EndIf
                    EndIf

                    If tail Then
                        tail.succ = e
                    Else
                        h = e
                    EndIf

                    tail = e

                Wend

                p = q
            Wend
            tail.succ = oh
            h.pred = oh
            If merges <= 1 Then Return h
            insize *= 2
        Wend
    Return null
    End Method

End

Function Compare:Int(o1:Object, o2:Object)
    Local c1:Card = Card(o1)
    Local c2:Card = Card(o2)
    If c2 = c1 Return False

    If c1.shuffleOrder = c2.shuffleOrder
        Return True
    endif

    Return Sgn(c1.shuffleOrder - c2.shuffleOrder)

End

Class LinkedEnumerator<T>
    Field list:LinkedList<T>
    Field curr:LinkedNode<T>

    Method New( lst:LinkedList<T> )
        list = lst
        curr = lst.head.succ
    End Method

    Method HasNext:Bool()
        Return curr <> list.head
    End

    Method NextObject:T()
        Local data:T = curr.data
        curr = curr.succ
        Return data
    End


End

Class LinkedNode<T>
    Field succ:LinkedNode
    Field pred:LinkedNode
    Field data:T

    Method New()
        succ=Self
        pred=Self
    End

    Method New( succ:LinkedNode, pred:LinkedNode, data:T )
        self.succ=succ
        self.pred=pred
        self.succ.pred=Self
        self.pred.succ=Self
        self.data=data
    End


    Method NextLink:LinkedNode<T>()
        If succ.data<>succ Return succ
        Return succ
    End

End