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"
        a.x = 30
        list.AddLast(a)

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

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

        list.Sort()

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


        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)',compareFunc( o1:Object,o2:Object )=CompareObjects )
        Print "Sorting..."
        Local ccsgn%=-1
        If ascending ccsgn=1

        Local insize%=1
        Repeat
            Local merges%
            Local tail:LinkedNode<T> = head
            Local p:LinkedNode<T> = head.succ

            While p<>head
                merges+=1
                Local q:LinkedNode<T>=p.succ,qsize%=insize,psize%=1

                While psize<insize And q<>head
                    psize+=1
                    q=q.succ
                Wend

                Repeat
                    Local t:LinkedNode<T>
                    If psize And qsize And q<>head
                        Local cc% = Compare(p.data, q.data) '( CompareFunc( p._value,q._value ) * ccsgn
                        If cc<=0
                            t=p
                            p=p.succ
                            psize-=1
                        Else
                            t=q
                            q=q.succ
                            qsize-=1
                        EndIf
                    Else If psize
                        t=p
                        p=p.succ
                        psize-=1
                    Else If qsize And q<>head
                        t=q
                        q=q.succ
                        qsize-=1
                    Else
                        Exit
                    EndIf
                    t.pred=tail
                    tail.succ=t
                    tail=t
                Forever
                p=q
            Wend
            tail.succ=head
            head.pred=tail

            If merges<=1 Return

            insize*=2
        Forever
    End Method

End

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

    If c1.x = c2.x
        Return True
    endif

    Return Sgn(c1.x - c2.x)

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