source: libcfa/src/bits/queue.hfa @ 3d0560d

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 3d0560d was 3d0560d, checked in by Peter A. Buhr <pabuhr@…>, 12 months ago

clean up all new collections and fix sequence iterator bug

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