1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
// -*- Mode: C++ -*-
//
// Copyright (C) Glen Ditchfield 1994
//
// uStack.h --
//
// Author : Peter Buhr
// Created On : Sun Feb 13 19:35:33 1994
// Last Modified By : Peter A. Buhr
// Last Modified On : Mon Jul 19 23:09:39 2004
// Update Count : 47
//
// This library is free software; you can redistribute it and/or modify it
// under the terms of the GNU Lesser General Public License as published by the
// Free Software Foundation; either version 2.1 of the License, or (at your
// option) any later version.
//
// This library is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
// for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this library.
//
#ifndef __U_STACK_H__
#define __U_STACK_H__
#include "uCollection.h"
// A uStack<T> is a uCollection<T> that defines an ordering among the elements:
// they are returned by uDrop() in the reverse order that they are added by
// uAdd().
// The implementation is a typical singly-linked list, except that uStack
// maintains uColable's invariant by having the next field of the last element
// of the list point to itself instead of being null.
template<class T> class uStack: public uCollection<T> {
protected:
using uCollection<T>::root;
uStack(const uStack&); // no copy
uStack &operator=(const uStack&); // no assignment
public:
using uCollection<T>::uHead;
using uCollection<T>::uNext;
uStack() : uCollection<T>() {}; // post: isEmpty().
inline T *uTop() const {
return uHead();
}
void uAddHead(T *n) {
#ifdef __U_DEBUG__
if ( n->uListed() ) uAbort( "(uStack &)0x%p.uAdd( 0x%p ) node is already on another list.", this, n );
#endif // __U_DEBUG__
uNext(n) = root ? root : n;
root = n;
}
inline void uAdd(T *n) {
uAddHead( n );
}
inline void uPush(T *n) {
uAddHead( n );
}
T *uDrop() {
T *t = root;
if (root) {
root = (T *)uNext(root);
if (root == t) root = 0; // There was only one element.
uNext(t) = 0;
};
return t;
}
inline T *uPop() {
return uDrop();
}
};
// A uStackGen<T> is a subclass of uColGen<T> that generates the elements of a
// uStack<T>. It returns the elements in the order that they would be returned
// by uDrop().
template<class T> class uStackGen : public uColGen<T> {
protected:
using uColGen<T>::curr;
public:
uStackGen() : uColGen<T>() {}; // post: elts = null.
// Create a generator active in stack s.
uStackGen(const uStack<T> &s) {
curr = s.uHead();
}
// Make the generator active in stack s.
void uOver(const uStack<T> &s) { // post: elts = {e in s}.
curr = s.uHead();
}
bool operator>>(T *&tp) {
if (curr) {
tp = curr;
T *n = (T *)uNext(curr);
curr = (n == curr) ? 0 : n;
}
else tp = 0;
return tp != 0;
}
};
#endif // __U_STACK_H__
// Local Variables: //
// compile-command: "gmake install" //
// End: //
|
