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

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

modify routines to return added/removed node to allow cascading calls

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