Changes in libcfa/src/bits/queue.hfa [7d4ce2a:9536761]

File:

• libcfa/src/bits/queue.hfa (modified) (11 diffs)

libcfa/src/bits/queue.hfa

@@ -3 +3 @@
 #include "bits/collection.hfa"
 
-forall( dtype T ) {
+// A Queue(T) is a Collection(T) defining the ordering that nodes are returned by drop() in the same order from those
+// added by add(). T must be a public descendant of uColable.
+
+// The implementation is a typical singly-linked list, except the next field of the last element points to itself
+// instead of being null.
+
+forall( dtype T | { T *& Next ( T * ); } ) {
         struct Queue {
                 inline Collection;                                                              // Plan 9 inheritance
@@ -34 +40 @@
                 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
 
-                void addHead( Queue(T) & q, T & n ) with( q ) {
+                T & 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 );
@@ -45 +51 @@
                                 Next( &n ) = &n;                                                // last node points to itself
                         }
+                        return n;
                 }
 
-                void addTail( Queue(T) & q, T & n ) with( q ) {
+                T & 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 );
@@ -55 +62 @@
                         last = &n;
                         Next( &n ) = &n;                                                        // last node points to itself
+                        return n;
                 }
 
-                void add( Queue(T) & q, T & n ) with( q ) {
-                        addTail( q, n );
+                T & add( Queue(T) & q, T & n ) with( q ) {
+                        return addTail( q, n );
                 }
 
@@ -64 +72 @@
                         T & t = head( q );
                         if ( root ) {
-                                root = Next( root );
+                                root = Next( (T *)root );
                                 if ( &head( q ) == &t ) {
                                         root = last = 0p;                                       // only one element
@@ -77 +85 @@
                 }
 
-                void remove( Queue(T) & q, T & n ) with( q ) {  // O(n)
+                T & 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 );
@@ -103 +111 @@
                                 curr = Next( curr );
                         }
+                        return n;
                 } // post: ! listed( n )
 
-                T & dropTail( Queue(T) & q ) with( q ) { // O(n)
+                T & dropTail( Queue(T) & q ) with( q ) {                // O(n)
                         T & n = tail( q );
                         return &n ? remove( q, n ), n : *0p;
@@ -142 +151 @@
 } // distribution
 
-forall( dtype T ) {
+forall( dtype T | { T *& Next ( T * ); } ) {
         struct QueueIter {
                 inline ColIter;                                                                 // Plan 9 inheritance
@@ -152 +161 @@
                 } // post: curr == 0p
 
-                // create an iterator active in Queue q
+                // create an iterator active in queue q
                 void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
                         curr = &head( q );
@@ -161 +170 @@
                 } // post: curr = {e in q}
 
-                // make existing iterator active in Queue 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 ) {
+                bool ?|?( QueueIter(T) & qi, T && tp ) with( qi ) {
                         if ( curr ) {
                                 &tp = Curr( qi );
@@ -174 +183 @@
                         return &tp != 0p;
                 }
-                // post: elts == null & !operator>>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)
+                // post: elts == null & !operator|(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator|(tp)
         } // distribution
 } // distribution