source: libcfa/src/bits/sequence.hfa @ 7c1144b

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

formatting, more switch from pointer to reference

  • Property mode set to 100644
File size: 9.5 KB
Line 
1#pragma once
2
3#include "collection.hfa"
4
5struct Seqable {
6        inline Colable;
7        Seqable * back;                                                                         // pointer to previous node in the list
8};
9
10inline {
11        // PUBLIC
12
13        void ?{}( Seqable & sq ) with( sq ) {
14                ((Colable &) sq){};
15                back = 0p;
16        } // post: ! listed()
17
18        Seqable & getBack( Seqable & sq ) with( sq ) {
19                return *back;
20        }
21
22        // PRIVATE
23
24        Seqable *& Back( Seqable * sq ) {
25                return sq->back;
26        }
27
28        // wrappers to make Collection have T
29        forall( dtype T ) {
30                T *& Back( T & n ) {
31                        return (T *)Back( (Seqable *)&n );
32                }
33
34                T & head( Sequence(T) & s ) with( s ) {
35                        return *(T *)head( (Collection &)s );
36                } // post: empty() & head() == 0 | !empty() & head() in *s
37        } // distribution
38} // distribution
39
40forall( dtype T ) {
41        struct Sequence {
42                inline Collection;                                                              // Plan 9 inheritance
43        };
44
45        inline {
46                void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy
47                Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment
48
49                void ?{}( Sequence(T) & s ) with( s ) {
50                        ((Collection &) s){};
51                }       // post: isEmpty().
52
53                // Return a pointer to the last sequence element, without removing it. 
54                T & tail( Sequence(T) & s ) with( s ) {
55                        return root ? (T &)*Back( head( s ) ) : *0p;
56                }       // post: empty() & tail() == 0 | !empty() & tail() in *s
57
58                // Return a pointer to the element after *n, or 0p if list empty.
59                T * succ( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
60                        #ifdef __CFA_DEBUG__
61                        if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n );
62                        #endif // __CFA_DEBUG__
63                        return Next( *n ) == &head( s ) ? 0p : Next( *n );
64                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s
65
66                // Return a pointer to the element before *n, or 0p if there isn't one.
67                T * pred( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
68                        #ifdef __CFA_DEBUG__
69                        if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n );
70                        #endif // __CFA_DEBUG__
71                        return n == &head( s ) ? 0p : Back( *n );
72                }       // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s
73
74
75                // Insert *n into the sequence before *bef, or at the end if bef == 0.
76                void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
77                        #ifdef __CFA_DEBUG__
78                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );
79                        #endif // __CFA_DEBUG__
80                        if ( &bef == &head( s ) ) {                                     // must change root
81                                if ( root ) {
82                                        Next( n ) = &head( s );
83                                        Back( n ) = Back( head( s ) );
84                                        // inserted node must be consistent before it is seen
85                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
86                                        Back( head( s ) ) = &n;
87                                        Next( *Back( n ) ) = &n;
88                                } else {
89                                        Next( n ) = &n;
90                                        Back( n ) = &n;
91                                } // if
92                                // inserted node must be consistent before it is seen
93                                asm( "" : : : "memory" );                               // prevent code movement across barrier
94                                root = &n;
95                        } else {
96                                if ( ! &bef ) &bef = &head( s );
97                                Next( n ) = &bef;
98                                Back( n ) = Back( bef );
99                                // inserted node must be consistent before it is seen
100                                asm( "" : : : "memory" );                               // prevent code movement across barrier
101                                Back( bef ) = &n;
102                                Next( *Back( n ) ) = &n;
103                        } // if
104                }       // post: n->listed() & *n in *s & succ(n) == bef
105
106
107                // Insert *n into the sequence after *aft, or at the beginning if aft == 0.
108                void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {   // pre: !n->listed() & *aft in *s
109                        #ifdef __CFA_DEBUG__
110                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
111                        #endif // __CFA_DEBUG__
112                        if ( ! &aft ) {                                                         // must change root
113                                if ( root ) {
114                                        Next( n ) = &head( s );
115                                        Back( n ) = Back( head( s ) );
116                                        // inserted node must be consistent before it is seen
117                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
118                                        Back( head( s ) ) = &n;
119                                        Next( *Back( n ) ) = &n;
120                                } else {
121                                        Next( n ) = &n;
122                                        Back( n ) = &n;
123                                } // if
124                                asm( "" : : : "memory" );                               // prevent code movement across barrier
125                                root = &n;
126                        } else {
127                                Next( n ) = Next( aft );
128                                Back( n ) = &aft;
129                                // inserted node must be consistent before it is seen
130                                asm( "" : : : "memory" );                               // prevent code movement across barrier
131                                Back( *Next( n ) ) = &n;
132                                Next( aft ) = &n;
133                        } // if
134                }         // post: n->listed() & *n in *s & succ(n) == bef
135               
136                // pre: n->listed() & *n in *s
137                void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
138                        #ifdef __CFA_DEBUG__
139                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
140                        #endif // __CFA_DEBUG__
141                        if ( &n == &head( s ) ) {
142                                if ( Next( head( s ) ) == &head( s ) ) root = 0p;
143                                else root = Next( head( s ) );
144                        } // if
145                        Back( *Next( n ) ) = Back( n );
146                        Next( *Back( n ) ) = Next( n );
147                        Next( n ) = Back( n ) = 0p;
148                }                                                       // post: !n->listed().
149
150                // Add an element to the head of the sequence.
151                void addHead( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
152                        insertAft( s, *0p, n );
153                }
154                // Add an element to the tail of the sequence.
155                void addTail( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
156                        insertBef( s, n, *0p );
157                }
158                // Add an element to the tail of the sequence.
159                void add( Sequence(T) & s, T & n ) {                    // pre: !n->listed(); post: n->listed() & head() == n
160                        addTail( s, n );
161                }
162                // Remove and return the head element in the sequence.
163                T & dropHead( Sequence(T) & s ) {
164                        T & n = head( s );
165                        return &n ? remove( s, n ), n : *0p;
166                }
167                // Remove and return the head element in the sequence.
168                T & drop( Sequence(T) & s ) {
169                        return dropHead( s );
170                }
171                // Remove and return the tail element in the sequence.
172                T & dropTail( Sequence(T) & s ) {
173                        T & n = tail( s );
174                        return &n ? remove( s, n ), n : *0p;
175                }
176
177                // Transfer the "from" list to the end of s sequence; the "from" list is empty after the transfer.
178                void transfer( Sequence(T) & s, Sequence(T) & from ) with( s ) {
179                        if ( empty( from ) ) return;                            // "from" list empty ?
180                        if ( empty( s ) ) {                                                     // "to" list empty ?
181                                root = from.root;
182                        } else {                                                                        // "to" list not empty
183                                T * toEnd = Back( head( s ) );
184                                T * fromEnd = Back( head( from ) );
185                                Back( *root ) = fromEnd;
186                                Next( *fromEnd ) = &head( s );
187                                Back( *from.root ) = toEnd;
188                                Next( *toEnd ) = &head( from );
189                        } // if
190                        from.root = 0p;                                                         // mark "from" list empty
191                }
192
193                // Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n".
194                // Node "n" must be in the "from" list.
195                void split( Sequence(T) & s, Sequence(T) & from, T & n ) with( s ) {
196                        #ifdef __CFA_DEBUG__
197                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, &n );
198                        #endif // __CFA_DEBUG__
199                        Sequence(T) to;
200                        to.root = from.root;                                            // start of "to" list
201                        from.root = Next( n );                                          // start of "from" list
202                        if ( to.root == from.root ) {                           // last node in list ?
203                                from.root = 0p;                                                 // mark "from" list empty
204                        } else {
205                                Back( head( from ) ) = Back( head( to ) ); // fix "from" list
206                                Next( *Back( head( to ) ) ) = &head( from );
207                                Next( n ) = &head( to );                                // fix "to" list
208                                Back( head( to ) ) = &n;
209                        } // if
210                        transfer( s, to );
211                }
212        } // distribution
213} // distribution
214
215forall( dtype T ) {
216        // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order.
217        struct SeqIter {
218                inline ColIter;
219                // The Sequence must be passed to pred and succ to check for the end of the Sequence and return 0p. Without
220                // passing the sequence, traversing would require its length. Thus the iterator needs a pointer to the sequence
221                // to pass to succ/pred. Both stack and queue just encounter 0p since the lists are not circular.
222                Sequence(T) * seq;                                                              // FIX ME: cannot be reference
223        };
224
225        inline {
226                void ?{}( SeqIter(T) & si ) with( si ) {
227                        ((ColIter &)si){};
228                        seq = 0p;
229                } // post: elts = null.
230
231                void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
232                        ((ColIter &) si){};
233                        seq = &s;
234                        curr = &head( s );
235                } // post: elts = null.
236
237                void ?{}( SeqIter(T) & si, Sequence(T) & s, T & start ) with( si ) {
238                        ((ColIter &) si){};
239                        seq = &s;
240                        curr = &start;
241                } // post: elts = null.
242
243                void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
244                        seq = &s;
245                        curr = &head( s );
246                } // post: elts = {e in s}.
247
248                bool ?>>?( SeqIter(T) & si, T && tp ) with( si ) {
249                        if ( curr ) {
250                                &tp = Curr( si );
251                                T * n = succ( *seq, Curr( si ) );
252                                curr = n == &head( *seq ) ? 0p : n;
253                        } else &tp = 0p;
254                        return &tp != 0p;
255                }
256        } // distribution
257
258
259        // A SeqIterRev(T) is used to iterate over a Sequence(T) in tail-to-head order.
260        struct SeqIterRev {
261                inline ColIter;
262                // See above for explanation.
263                Sequence(T) * seq;                                                              // FIX ME: cannot be reference
264        };
265
266        inline {
267                void ?{}( SeqIterRev(T) & si ) with( si ) {     
268                        ((ColIter &) si){};
269                        seq = 0p;
270                } // post: elts = null.
271
272                void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {   
273                        ((ColIter &) si){};
274                        seq = &s;
275                        curr = &tail( s );
276                } // post: elts = null.
277
278                void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) {
279                        ((ColIter &) si){};
280                        seq = &s;
281                        curr = &start;
282                } // post: elts = null.
283
284                void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
285                        seq = &s;
286                        curr = &tail( s );
287                } // post: elts = {e in s}.
288
289                bool ?>>?( SeqIterRev(T) & si, T && tp ) with( si ) {
290                        if ( curr ) {
291                                &tp = Curr( si );
292                                T * n = pred( *seq, Curr( si ) );
293                                curr = n == &tail( *seq ) ? 0p : n;
294                        } else &tp = 0p;
295                        return &tp != 0p;
296                }
297        } // distribution
298} // distribution
Note: See TracBrowser for help on using the repository browser.