source: libcfa/src/bits/queue.hfa @ a25bcf8

ADTast-experimental
Last change on this file since a25bcf8 was c407434e, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Fixed missing static

  • Property mode set to 100644
File size: 5.5 KB
Line 
1#pragma once
2
3#include "bits/collection.hfa"
4
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
11forall( T & | { T *& Next ( T * ); } ) {
12        struct Queue {
13                inline Collection;                                                              // Plan 9 inheritance
14                T * last;                                                                               // last element, or 0 if queue is empty.
15        };
16
17        static inline {
18                // wrappers to make Collection have T
19                T & head( Queue(T) & q ) with( q ) {
20                        return *(T *)head( (Collection &)q );
21                } // post: empty() & head() == 0 | !empty() & head() in *q
22
23                void ?{}( Queue(T) &, const Queue(T) & ) = void; // no copy
24                Queue(T) & ?=?( const Queue(T) & ) = void;              // no assignment
25
26                void ?{}( Queue(T) & q ) with( q ) {
27                        ((Collection &)q){};
28                        last = 0p;
29                } // post: empty()
30
31                T & tail( Queue(T) & q ) with( q ) {
32                        return *last;
33                }
34
35                T * succ( Queue(T) & q, T * n ) with( q ) {             // pre: *n in *q
36                        #ifdef __CFA_DEBUG__
37                        if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n );
38                        #endif // __CFA_DEBUG__
39                        return (Next( n ) == n) ? 0p : Next( n );
40                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
41
42                T & addHead( Queue(T) & q, T & n ) with( q ) {
43                        #ifdef __CFA_DEBUG__
44                        if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n );
45                        #endif // __CFA_DEBUG__
46                        if ( last ) {
47                                Next( &n ) = &head( q );
48                                q.root = &n;
49                        } else {
50                                root = last = &n;
51                                Next( &n ) = &n;                                                // last node points to itself
52                        }
53                        return n;
54                }
55
56                T & addTail( Queue(T) & q, T & n ) with( q ) {
57                        #ifdef __CFA_DEBUG__
58                        if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
59                        #endif // __CFA_DEBUG__
60                        if ( last ) Next( last ) = &n;
61                        else root = &n;
62                        last = &n;
63                        Next( &n ) = &n;                                                        // last node points to itself
64                        return n;
65                }
66
67                T & add( Queue(T) & q, T & n ) with( q ) {
68                        return addTail( q, n );
69                }
70
71                T & dropHead( Queue(T) & q ) with( q ) {
72                        T & t = head( q );
73                        if ( root ) {
74                                root = Next( (T *)root );
75                                if ( &head( q ) == &t ) {
76                                        root = last = 0p;                                       // only one element
77                                }
78                                Next( &t ) = 0p;
79                        }
80                        return t;
81                }
82
83                T & drop( Queue(T) & q ) with( q ) {
84                        return dropHead( q );
85                }
86
87                T & remove( Queue(T) & q, T & n ) with( q ) {   // O(n)
88                        #ifdef __CFA_DEBUG__
89                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
90                        #endif // __CFA_DEBUG__
91                        T * prev = 0p;
92                        T * curr = (T *)root;
93                        for ( ;; ) {
94                                if ( &n == curr ) {                                             // found => remove
95                                        if ( (T *)root == &n ) {
96                                                dropHead( q );
97                                        } else if ( last == &n ) {
98                                                last = prev;
99                                                Next( last ) = last;
100                                        } else {
101                                                Next( prev ) = Next( curr );
102                                        }
103                                        Next( &n ) = 0p;
104                                        break;
105                                }
106                                // not found => error
107                                #ifdef __CFA_DEBUG__
108                                if ( curr == last ) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n );
109                                #endif // __CFA_DEBUG__
110                                prev = curr;
111                                curr = Next( curr );
112                        }
113                        return n;
114                } // post: ! listed( n )
115
116                T & dropTail( Queue(T) & q ) with( q ) {                // O(n)
117                        T & n = tail( q );
118                        return &n ? remove( q, n ), n : *0p;
119                }
120
121                // Transfer the "from" list to the end of queue sequence; the "from" list is empty after the transfer.
122                void transfer( Queue(T) & q, Queue(T) & from ) with( q ) {
123                        if ( empty( from ) ) return;                            // "from" list empty ?
124                        if ( empty( q ) ) {                                                     // "to" list empty ?
125                                root = from.root;
126                        } else {                                                                        // "to" list not empty
127                                Next( last ) = &head( from );
128                        }
129                        last = from.last;
130                        from.root = from.last = 0p;                                     // mark "from" list empty
131                }
132
133                // Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
134                // Node "n" must be in the "from" list.
135                void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) {
136                        #ifdef __CFA_DEBUG__
137                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n );
138                        #endif // __CFA_DEBUG__
139                        Queue(T) to;
140                        to.root = from.root;                                            // start of "to" list
141                        to.last = &n;                                                           // end of "to" list
142                        from.root = Next( &n );                                         // start of "from" list
143                        if ( &n == &head( from ) ) {                            // last node in list ?
144                                from.root = from.last = 0p;                             // mark "from" list empty
145                        } else {
146                                Next( &n ) = &n;                                                // fix end of "to" list
147                        }
148                        transfer( q, to );
149                }
150        } // distribution
151} // distribution
152
153forall( T & | { T *& Next ( T * ); } ) {
154        struct QueueIter {
155                inline ColIter;                                                                 // Plan 9 inheritance
156        };
157
158        static inline {
159                void ?{}( QueueIter(T) & qi ) with( qi ) {
160                        ((ColIter &)qi){};
161                } // post: curr == 0p
162
163                // create an iterator active in queue q
164                void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
165                        curr = &head( q );
166                } // post: curr = {e in q}
167
168                void ?{}( QueueIter(T) & qi, T & start ) with( qi ) {
169                        curr = &start;
170                } // post: curr = {e in q}
171
172                // make existing iterator active in queue q
173                void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
174                        curr = &head( q );
175                } // post: curr = {e in q}
176
177                bool ?|?( QueueIter(T) & qi, T && tp ) with( qi ) {
178                        if ( curr ) {
179                                &tp = Curr( qi );
180                                T * n = Next( Curr( qi ) );
181                                curr = (n == Curr( qi ) ) ? 0p : n;
182                        } else &tp = 0p;
183                        return &tp != 0p;
184                }
185                // post: elts == null & !operator|(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator|(tp)
186        } // distribution
187} // distribution
Note: See TracBrowser for help on using the repository browser.