CycList

library CycList

//*****************************************************************
//*  CYCLIST
//*
//*  written by: Anitarf
//*
//*  CycList is a lightweight and efficient circular double linked
//*  list module and struct with a minimalist and intuitive API.
//*
//*  Since the list is circular, it has no first or last node; all
//*  nodes are equal and each CycList instance is a reference to
//*  both a single node and the list as a whole. This simplifies
//*  the code compared to other linked list implementations, which
//*  have separate list and link structs. A CycList can still be
//*  used to simulate a linear linked list by adding an additional
//*  sentinel node to mark the start/end of the list.
//*
//*  Struct index 0 can not be used as a list node. If all you need
//*  is a static list and you want to use the 0 index as a sentinel
//*  node, then you should use a different list library.
//*
//*  Module API:
//*
//*    .next
//*    .prev
//*  These operators return the next or previous node in the list.
//*  If the node is not in a list then these operators will return
//*  the node itself, with one exception: if the node has not been
//*  used before, they will return 0 instead. To avoid checking for
//*  this exception all the time, it is recommended that whenever
//*  a new node index is allocated, the .exclude method is called
//*  on it, which will initialize the .next and .prev values. The
//*  CycList struct does this in its create method.
//*
//*    .next=
//*    .prev=
//*  These operators insert another node after or in front of this
//*  node. If the inserted node is already a part of another list,
//*  then that whole list gets inserted. If both nodes are already
//*  a part of the same list, then the nodes between them will get
//*  excluded from the list. If the next or prev value of a node is
//*  set to itself, then the node will get excluded from its list.
//*
//*    .exclude()
//*  This is a more elegant way of removing a node from a list. It
//*  does the same thing as node.next=node, but it returns the node
//*  it is called on so further operations can be done on that node
//*  immediately on the same line, such as destroying it or adding
//*  it to another list. It is also slightly more efficient.
//*
//*  Struct API:
//*
//*  In most cases, implementing the CycList module directly into
//*  your struct is the most elegant and robust solution. However,
//*  sometimes you just need a simple external list and declaring
//*  another struct for it seems like overkill, for those cases
//*  the CycList struct is provided so multiple libraries can use
//*  the same implementation of the CycList module.
//*
//*    CycList.create( integer value )
//*  The create method allocates a new list node that stores the
//*  given value. You can use all the CycList module operators on
//*  this node as described above.
//*
//*    .value
//*  The value operator returns the value stored on this node.
//*
//*    .destroy()
//*  The destroy method destroy the entire list. If you just want
//*  to destroy a single node, exclude it from the list first.
//*
//*****************************************************************

    module CycList
        private thistype n
        private thistype p
        
        method exclude takes nothing returns thistype
            set .n.p=.p // When using this method to initialize a node,
            set .p.n=.n // the first two lines effectively do nothing.
            set .n=this
            set .p=this
            return this
        endmethod

        method operator next takes nothing returns thistype
            return .n
        endmethod

        method operator prev takes nothing returns thistype
            return .p
        endmethod
        
        //! textmacro CycListInsertDebug takes token
            if $token$.n==0 then
                call $token$.exclude()
                if $token$.n==0 then // invalid node
                    debug call BJDebugMsg("CycList error: attempted to insert an invalid instance ("+I2S($token$)+") of "+SubString($token$.exclude.name,3,StringLength($token$.exclude.name)-8)+".")
                    return
                endif
            endif
        //! endtextmacro

        method operator next= takes thistype that returns nothing
            //! runtextmacro CycListInsertDebug("this")
            //! runtextmacro CycListInsertDebug("that")
            set this.n.p=that.p
            set that.p.n=this.n
            set this.n=that
            set that.p=this
        endmethod

        method operator prev= takes thistype that returns nothing
            //! runtextmacro CycListInsertDebug("this")
            //! runtextmacro CycListInsertDebug("that")
            set this.p.n=that.n
            set that.n.p=this.p
            set this.p=that
            set that.n=this
        endmethod
    endmodule

// ================================================================

    struct CycList
        // This line implements the module, which gives the struct next and prev method
        // operators and the exclude method. The rest of the functionality described in
        // the library documentation is provided by the struct, not the module.
        implement CycList

        // This stores the data value attached to this node.
        readonly integer value

        // The create method allocates a new node with the given data value.
        static method create takes integer value returns CycList
            local CycList this = CycList.allocate()
            set .value = value
            if .next == 0 then
                call .exclude()
            endif
            return this
        endmethod

        // Calling the destroy method on a single node will destroy the entire list. Use
        // the exclude method first if you only want to destroy a single node.
        method destroy takes nothing returns nothing
            loop
                exitwhen .next==this or .next==0
                call .next.exclude().deallocate()
            endloop
            call .deallocate()
        endmethod
    endstruct

endlibrary