source: libcfa/src/bits/queue.hfa @ 636d3715

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

more code sharing in containers

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