Context Navigation

sequence.hfa @ a32cbac2

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since a32cbac2 was a32cbac2, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago
add comments to SeqIter?
Property mode set to `100644`
File size: 9.5 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format