Commit | Line | Data |
---|---|---|
d4ee6ee2 JM |
1 | /************************************************************************* |
2 | * | |
3 | * $Author: Jim Morris $ | |
4 | * $Date: 1999/02/05 21:05:00 $ | |
5 | * | |
6 | * this code is Licensed LGPL | |
7 | * | |
8 | *************************************************************************/ | |
9 | #ifndef _FIFO_H_ | |
10 | #define _FIFO_H_ | |
11 | ||
12 | #include <stdlib.h> | |
13 | ||
14 | // Doubly Linked list class | |
15 | ||
16 | template<class T> class LList; | |
17 | ||
18 | template<class T> | |
19 | class Tlink | |
20 | { | |
21 | public: | |
22 | Tlink<T> *pnext; | |
23 | Tlink<T> *pprev; | |
24 | ||
25 | public: | |
26 | Tlink() | |
27 | { | |
28 | pnext = pprev = 0; | |
29 | } | |
30 | Tlink(Tlink *p, Tlink *n) | |
31 | { | |
32 | pprev = p; | |
33 | pnext = n; | |
34 | } | |
35 | Tlink(const T &d) : data(d) | |
36 | { | |
37 | pnext = pprev = 0; | |
38 | } | |
39 | T data; | |
40 | }; | |
41 | ||
42 | template<class T> | |
43 | class list_base | |
44 | { | |
45 | private: | |
46 | Tlink<T> *head; | |
47 | Tlink<T> *tail; | |
48 | int cnt; | |
49 | ||
50 | protected: | |
51 | list_base() | |
52 | { | |
53 | head = tail = NULL; | |
54 | cnt = 0; | |
55 | } | |
56 | ||
57 | list_base(Tlink<T> *n) // link into head of list | |
58 | { | |
59 | cnt = 1; | |
60 | n->pnext = NULL; | |
61 | n->pprev = NULL; | |
62 | head = n; | |
63 | tail = n; | |
64 | } | |
65 | ||
66 | Tlink<T> *gethead(void) const | |
67 | { | |
68 | return head; | |
69 | } | |
70 | Tlink<T> *gettail(void) const | |
71 | { | |
72 | return tail; | |
73 | } | |
74 | Tlink<T> *getnext(Tlink<T> *n) const | |
75 | { | |
76 | return n->pnext; | |
77 | } | |
78 | Tlink<T> *getprev(Tlink<T> *n) const | |
79 | { | |
80 | return n->pprev; | |
81 | } | |
82 | ||
83 | void addtohead(Tlink<T> *n) // add at head of list | |
84 | { | |
85 | n->pnext = head; | |
86 | n->pprev = NULL; | |
87 | if (head) head->pprev = n; | |
88 | head = n; | |
89 | if (tail == NULL) // first one | |
90 | tail = n; | |
91 | cnt++; | |
92 | } | |
93 | ||
94 | void addtohead(int c, Tlink<T> *a, Tlink<T> *b) // add list at head of list | |
95 | { | |
96 | b->pnext = head; | |
97 | a->pprev = NULL; | |
98 | if (head) head->pprev = b; | |
99 | head = a; | |
100 | if (tail == NULL) // first one | |
101 | tail = b; | |
102 | cnt += c; | |
103 | } | |
104 | ||
105 | void addtotail(Tlink<T> *n) // add to tail of list | |
106 | { | |
107 | n->pnext = NULL; | |
108 | n->pprev = tail; | |
109 | if (tail) tail->pnext = n; | |
110 | tail = n; | |
111 | if (head == NULL) // first one | |
112 | head = n; | |
113 | cnt++; | |
114 | } | |
115 | ||
116 | void remove(Tlink<T> *n) // remove it by relinking | |
117 | { | |
118 | cnt--; | |
119 | if (n->pprev) n->pprev->pnext = n->pnext; | |
120 | else head = n->pnext; // it must be the head | |
121 | if (n->pnext) n->pnext->pprev = n->pprev; | |
122 | else tail = n->pprev; | |
123 | } | |
124 | ||
125 | void reset() | |
126 | { | |
127 | head = tail = NULL; | |
128 | cnt = 0; | |
129 | } | |
130 | int count() const | |
131 | { | |
132 | return cnt; | |
133 | } | |
134 | }; | |
135 | ||
136 | // fifo | |
137 | template<class T> | |
138 | class Fifo : private list_base<T> | |
139 | { | |
140 | public: | |
141 | Fifo(){} | |
142 | ||
143 | void push(const T &a); | |
144 | T pop(); | |
145 | T peek(); | |
146 | int size() const; | |
147 | }; | |
148 | ||
149 | template <class T> | |
150 | int Fifo<T>::size() const | |
151 | { | |
152 | return list_base<T>::count(); | |
153 | } | |
154 | ||
155 | // add to end of list (FIFO) | |
156 | template <class T> | |
157 | void Fifo<T>::push(const T &a) | |
158 | { | |
159 | list_base<T>::addtotail(new Tlink<T>(a)); | |
160 | } | |
161 | ||
162 | // return the first item in the list | |
163 | template <class T> | |
164 | T Fifo<T>::peek() | |
165 | { | |
166 | Tlink<T> *p = list_base<T>::gethead(); | |
167 | return p->data; | |
168 | } | |
169 | ||
170 | // pop the first item off the fifo | |
171 | template <class T> | |
172 | T Fifo<T>::pop() | |
173 | { | |
174 | Tlink<T> *p = list_base<T>::gethead(); | |
175 | T data = p->data; | |
176 | list_base<T>::remove(p); | |
177 | delete p; | |
178 | return data; | |
179 | }; | |
180 | #endif |