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

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since accc5dbb was accc5dbb, checked in by Colby Alexander Parsons <caparsons@…>, 3 years ago

updated other collections to match changes to sequence.hfa

  • 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 * ); bool listed ( 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( (T *)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 = 0p;
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                                // not found => error
99                                #ifdef __CFA_DEBUG__
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 | { T *& Next ( T * ); bool listed ( 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
Note: See TracBrowser for help on using the repository browser.