Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/bits/queue.hfa

    r9536761 r7d4ce2a  
    33#include "bits/collection.hfa"
    44
    5 // A Queue(T) is a Collection(T) defining the ordering that nodes are returned by drop() in the same order from those
    6 // added by add(). T must be a public descendant of uColable.
    7 
    8 // The implementation is a typical singly-linked list, except the next field of the last element points to itself
    9 // instead of being null.
    10 
    11 forall( dtype T | { T *& Next ( T * ); } ) {
     5forall( dtype T ) {
    126        struct Queue {
    137                inline Collection;                                                              // Plan 9 inheritance
    … …  
    4034                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
    4135
    42                 T & addHead( Queue(T) & q, T & n ) with( q ) {
     36                void addHead( Queue(T) & q, T & n ) with( q ) {
    4337                        #ifdef __CFA_DEBUG__
    4438                        if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n );
    … …  
    5145                                Next( &n ) = &n;                                                // last node points to itself
    5246                        }
    53                         return n;
    5447                }
    5548
    56                 T & addTail( Queue(T) & q, T & n ) with( q ) {
     49                void addTail( Queue(T) & q, T & n ) with( q ) {
    5750                        #ifdef __CFA_DEBUG__
    5851                        if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
    … …  
    6255                        last = &n;
    6356                        Next( &n ) = &n;                                                        // last node points to itself
    64                         return n;
    6557                }
    6658
    67                 T & add( Queue(T) & q, T & n ) with( q ) {
    68                         return addTail( q, n );
     59                void add( Queue(T) & q, T & n ) with( q ) {
     60                        addTail( q, n );
    6961                }
    7062
    … …  
    7264                        T & t = head( q );
    7365                        if ( root ) {
    74                                 root = Next( (T *)root );
     66                                root = Next( root );
    7567                                if ( &head( q ) == &t ) {
    7668                                        root = last = 0p;                                       // only one element
    … …  
    8577                }
    8678
    87                 T & remove( Queue(T) & q, T & n ) with( q ) {   // O(n)
     79                void remove( Queue(T) & q, T & n ) with( q ) {  // O(n)
    8880                        #ifdef __CFA_DEBUG__
    8981                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
    … …  
    111103                                curr = Next( curr );
    112104                        }
    113                         return n;
    114105                } // post: ! listed( n )
    115106
    116                 T & dropTail( Queue(T) & q ) with( q ) {                // O(n)
     107                T & dropTail( Queue(T) & q ) with( q ) { // O(n)
    117108                        T & n = tail( q );
    118109                        return &n ? remove( q, n ), n : *0p;
    … …  
    151142} // distribution
    152143
    153 forall( dtype T | { T *& Next ( T * ); } ) {
     144forall( dtype T ) {
    154145        struct QueueIter {
    155146                inline ColIter;                                                                 // Plan 9 inheritance
    … …  
    161152                } // post: curr == 0p
    162153
    163                 // create an iterator active in queue q
     154                // create an iterator active in Queue q
    164155                void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
    165156                        curr = &head( q );
    … …  
    170161                } // post: curr = {e in q}
    171162
    172                 // make existing iterator active in queue q
     163                // make existing iterator active in Queue q
    173164                void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
    174165                        curr = &head( q );
    175166                } // post: curr = {e in q}
    176167
    177                 bool ?|?( QueueIter(T) & qi, T && tp ) with( qi ) {
     168                bool ?>>?( QueueIter(T) & qi, T && tp ) with( qi ) {
    178169                        if ( curr ) {
    179170                                &tp = Curr( qi );
    … …  
    183174                        return &tp != 0p;
    184175                }
    185                 // post: elts == null & !operator|(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator|(tp)
     176                // post: elts == null & !operator>>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)
    186177        } // distribution
    187178} // distribution
Note: See TracChangeset for help on using the changeset viewer.