source: mainline/uspace/dist/src/sysel/lib/list.sy@ 1c79996

--
-- Copyright (c) 2010 Jiri Svoboda
-- All rights reserved.
--
-- Redistribution and use in source and binary forms, with or without
-- modification, are permitted provided that the following conditions
-- are met:
--
-- o Redistributions of source code must retain the above copyright
--   notice, this list of conditions and the following disclaimer.
-- o Redistributions in binary form must reproduce the above copyright
--   notice, this list of conditions and the following disclaimer in the
--   documentation and/or other materials provided with the distribution.
-- o The name of the author may not be used to endorse or promote products
--   derived from this software without specific prior written permission.
--
-- THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
-- IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
-- OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
-- IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
-- INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
-- NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-- DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-- THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-- (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
-- THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
--

-- Doubly-linked list.
class List/t : IEnumerable/t is
        var head : ListNode/t;

        -- New empty list.
        new() is
                head = new ListNode/t();
                head.prev = head;
                head.next = head;
        end

        -- Append new entry at the end of the list.
        fun Append(data : t) is
                var n : ListNode/t;
                var ntl : ListNode/t;

                ntl = head.prev;

                n = new ListNode/t();
                n.data = data;

                n.prev = ntl;
                n.next = head;
                n.head = head;

                ntl.next = n;
                head.prev = n;
        end

        -- Return first node in the list or @c nil if there is none.
        prop First : ListNode/t is
                get is
                        return get_first();
                end
        end

        -- Return first node in the list or @c nil if there is none.
        fun GetEnumerator() : IEnumerator/t is
                return new ListEnumerator/t(get_first());
        end

        -- Return first node in the list or @c nil if there is none.
        fun get_first() : ListNode/t is
                if head.next == head then
                        return nil;
                else
                        return head.next;
                end
        end
end

class ListNode/t is
        var data : t;

        var prev : ListNode/t;
        var next : ListNode/t;
        var head : ListNode/t;

        -- Data stored in this node.
        prop Data : t is
                get is
                        return data;
                end
        end

        -- Previous node in list.
        prop Prev : ListNode/t is
                get is
                        return get_prev();
                end
        end

        -- Next node in list.
        prop Next : ListNode/t is
                get is
                        return get_next();
                end
        end

        -- Remove node from list.
        fun Remove() is
                var p : ListNode/t;
                var n : ListNode/t;

                p = prev; n = next;
                p.next = n;
                n.prev = p;

                prev = nil;
                next = nil;
        end

        -- Get next node.
        fun get_next() : ListNode/t is
                if next != head then
                        return next;
                else
                        return nil;
                end
        end

        -- Get previous node.
        fun get_prev() : ListNode/t is
                if prev != head then
                        return next;
                else
                        return nil;
                end
        end
end

class ListEnumerator/t : IEnumerator/t is
        var first : ListNode/t;
        var current : ListNode/t;
        var started : bool;

        new(first_node : ListNode/t) is
                first = first_node;
                current = nil;
                started = false;
        end

        fun MoveNext() : bool is
                if started then
                        current = current.Next;
                else
                        current = first;
                        started = true;
                end

                return current != nil;
        end

        prop Data : t is
                get is
                        return current.Data;
                end
        end
end