source: libcfa/src/bits/queue.hfa @ 63ec5fa

#pragma once

#include "collection.hfa"

forall( dtype T ) {
        struct Queue {
                inline Collection;                                                              // Plan 9 inheritance
                T * last;                                                                               // last element, or 0 if queue is empty.
        };

        inline {
                // wrappers to make Collection have T
                T * head( Queue(T) & q ) with( q ) {
                        return (T *)head( (Collection &)q );
                } // post: empty() & head() == 0 | !empty() & head() in *q

                bool empty( Queue(T) & q ) with( q ) {                  // 0 <=> *q contains no elements
                        return empty( (Collection &)q );
                }

                bool listed( T * n ) {
                        return Next( (Colable *)n ) != 0;
                }

                T *& Next( T * n ) {
                        return (T *)Next( (Colable *)n );
                }

                T * Root( Queue(T) & q ) with( q ) {
                        return (T *)root;
                }

                void ?{}( Queue(T) &, const Queue(T) & ) = void; // no copy
                Queue(T) & ?=?( const Queue(T) & ) = void;              // no assignment

                void ?{}( Queue(T) & q ) with( q ) {
                        ((Collection &)q){};
                        last = 0p;
                } // post: empty()

                T * tail( Queue(T) & q ) with( q ) {
                        return last;
                }

                T * succ( Queue(T) & q, T * n ) with( q ) {             // pre: *n in *q
#ifdef __CFA_DEBUG__
                        if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n );
#endif // __CFA_DEBUG__
                        return (Next( n ) == n) ? 0p : Next( n );
                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q

                void addHead( Queue(T) & q, T * n ) with( q ) {
#ifdef __CFA_DEBUG__
                        if ( listed( n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, n );
#endif // __CFA_DEBUG__
                        if ( last ) {
                                Next( n ) = Root( q );
                                q.root = n;
                        } else {
                                root = last = n;
                                Next( n ) = n;                                                  // last node points to itself
                        }
                }

                void addTail( Queue(T) & q, T * n ) with( q ) {
#ifdef __CFA_DEBUG__
                        if ( listed( n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, n );
#endif // __CFA_DEBUG__
                        if ( last ) Next( last ) = n;
                        else root = n;
                        last = n;
                        Next( n ) = n;                                                          // last node points to itself
                }

                void add( Queue(T) & q, T * n ) with( q ) {
                        addTail( q, n );
                }

                T * dropHead( Queue(T) & q ) with( q ) {
                        T * t = head( q );
                        if ( root ) {
                                root = Next( root );
                                if ( Root( q ) == t ) {
                                        root = last = 0p;                                       // only one element
                                }
                                Next( t ) = 0p;
                        }
                        return t;
                }

                T * drop( Queue(T) & q ) with( q ) {
                        return dropHead( q );
                }

                void remove( Queue(T) & q, T * n ) with( q ) {  // O(n)
#ifdef __CFA_DEBUG__
                        if ( ! listed( (Colable &)(*n) ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, n );
#endif // __CFA_DEBUG__
                        T * prev = 0;
                        T * curr = (T *)root;
                        for ( ;; ) {
                                if (n == curr) {                                                // found => remove
                                        if ((T *)root == n) {
                                                dropHead( q );
                                        } else if (last == n) {
                                                last = prev;
                                                Next( last ) = last;
                                        } else {
                                                Next( prev ) = Next( curr );
                                        }
                                        Next( n ) = 0p;
                                        break;
                                }
#ifdef __CFA_DEBUG__
                                // not found => error
                                if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, n );
#endif // __CFA_DEBUG__
                                prev = curr;
                                curr = Next( curr );
                        }
                } // post: ! listed( n )

                T * dropTail( Queue(T) & q ) with( q ) { // O(n)
                        T * n = tail( q );
                        return n ? remove( q, n ), n : 0p;
                }

                // Transfer the "from" list to the end of queue sequence; the "from" list is empty after the transfer.
                void transfer( Queue(T) & q, Queue(T) & from ) with( q ) {
                        if ( empty( from ) ) return;                            // "from" list empty ?
                        if ( empty( q ) ) {                                                     // "to" list empty ?
                                root = from.root;
                        } else {                                                                        // "to" list not empty
                                Next( last ) = Root( from );
                        }
                        last = from.last;
                        from.root = from.last = 0p;                                     // mark "from" list empty
                }

                // Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
                // Node "n" must be in the "from" list.
                void split( Queue(T) & q, Queue(T) & from, T * n ) with( q ) {
#ifdef __CFA_DEBUG__
                        if ( ! listed( (Colable &)(*n) ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, n );
#endif // __CFA_DEBUG__
                        Queue(T) to;
                        to.root = from.root;                                            // start of "to" list
                        to.last = n;                                                            // end of "to" list
                        from.root = Next( n );                                          // start of "from" list
                        if ( n == Root( from ) ) {                                      // last node in list ?
                                from.root = from.last = 0p;                             // mark "from" list empty
                        } else {
                                Next( n ) = n;                                                  // fix end of "to" list
                        }
                        transfer( q, to );
                }
        } // distribution
} // distribution

forall( dtype T ) {
        struct QueueIter {
                inline ColIter;                                                                 // Plan 9 inheritance
        };      

        inline {
                // wrappers to make ColIter have T
                T * Curr( QueueIter(T) & qi ) with( qi ) {
                        return (T *)curr;
                }

                void ?{}( QueueIter(T) & qi ) with( qi ) {
                        ((ColIter &)qi){};
                } // post: curr == 0p

                // create an iterator active in Queue q
                void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
                        curr = head( q );
                } // post: curr = {e in q}

                void ?{}( QueueIter(T) & qi, T * start ) with( qi ) {
                        curr = start;
                } // post: curr = {e in q}

                // make existing iterator active in Queue q
                void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
                        curr = head( q );
                } // post: curr = {e in q}

                bool ?>>?( QueueIter(T) & qi, T && tp ) with( qi ) {
                        if ( curr ) {
                                &tp = Curr( qi );
                                T * n = Next( Curr( qi ) );
                                curr = (n == Curr( qi ) ) ? 0p : n;
                        } else &tp = 0p;
                        return &tp != 0p;
                }
                // post: elts == null & !operator>>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)
        } // distribution
} // distribution

// Local Variables: //
// compile-command: "make install" //
// End: //