1 #ifndef GENERIC_LIST
2 #define GENERIC_LIST
3 
4 /*
5 Funciones para LISTAS:
6 
7 	void Delete()
8 	void Instance(List<T> &l)
9 	void Rewind(void)
10 	void Forward(void)
11 	void Next(void)
12 	void Prev(void)
13 	T *GetObj(void)
14 	LLink<T> *GetPos(void)
15 	bool EmptyP()
16 	bool EndP()
17 	bool LastP()
18 	bool BeginP()
19 	void Insert(T *o)
20 	void Add(T *o)
21 	void AddAfter(LLink<T> *pos,T *o)
22 	bool Iterate(T *&o)
23 	T *ExtractIni(void)
24 	T *Extract(void)
25 	bool MemberP(T *o)
26 	T *MemberGet(T *o)
27 	bool MemberRefP(T *o)
28 	int Length()
29 	void Copy(List l)
30 	bool DeleteElement(T *o)
31 	T *GetRandom(void)
32 	int SearchObjRef(T *o)
33 	int SearchObj(T *o)
34 	void SetNoOriginal(void)
35 	void SetOriginal(void)
36 
37 
38 	bool operator==(List<T> &l)
39 	T *operator[](int index)
40 */
41 
42 template <class T> class LLink {
43 public:
44 	LLink<T>(T *o,LLink<T> *n=0) {
45 		obj=o;next=n;
46 	};
47 	~LLink<T>() {delete obj;
48 				 if (next!=0) delete next;};
Getnext()49 	inline LLink<T> *Getnext() {return next;};
Setnext(LLink<T> * n)50 	inline void Setnext(LLink<T> *n) {next=n;};
GetObj()51 	inline T *GetObj() {return obj;};
Setobj(T * o)52 	inline void Setobj(T *o) {obj=o;};
53 
Anade(T * o)54 	void Anade(T *o) {
55 		if (next==NULL) {
56 			LLink<T> *node=new LLink<T>(o);
57 			next=node;
58 		} else {
59 			next->Anade(o);
60 		}
61 		};
62 
63 private:
64 	T *obj;
65 	LLink<T> *next;
66 };
67 
68 template <class T> class List {
69 public:
70 	List<T>() {list=0;act=0;top=0;original=true;};
71 	~List<T>() {
72 		if (original) {
73 			delete list;
74 		} /* if */
75 	};
76 	List<T>(List<T> &l) {list=l.list;act=list;top=l.top;original=false;};
77 
Delete()78 	void Delete() {
79 		if (original) {
80 			delete list;
81 		} /* if */
82 		list=NULL;
83 		act=NULL;
84 		top=NULL;
85 	};
86 
Instance(List<T> & l)87 	void Instance(List<T> &l) {list=l.list;act=list;top=l.top;original=false;};
Rewind(void)88 	void Rewind(void) {act=list;};
Forward(void)89 	void Forward(void) {act=top;};
Next(void)90 	void Next(void) {
91 		if (act!=NULL) act=act->Getnext();
92 	};
93 
Prev(void)94 	void Prev(void) {
95 		LLink<T> *tmp;
96 
97 		if (act!=list) {
98 			tmp=list;
99 			while(tmp->Getnext()!=act) tmp=tmp->Getnext();
100 			act=tmp;
101 		} /* if */
102 	};
103 
GetObj(void)104 	T *GetObj(void) {return act->GetObj();};
GetPos(void)105 	LLink<T> *GetPos(void) {return act;};
EmptyP()106 	bool EmptyP() {return list==NULL;};
EndP()107 	bool EndP() {return act==NULL;};
LastP()108 	bool LastP() {return act==top;};
BeginP()109 	bool BeginP() {return act==list;};
110 
Insert(T * o)111 	void Insert(T *o) {
112 		if (list==NULL) {
113 			list=new LLink<T>(o);
114 			top=list;
115 		} else {
116 			list=new LLink<T>(o,list);
117 		} /* if */
118 	};
119 
Add(T * o)120 	void Add(T *o) {
121 		if (list==NULL) {
122 			list=new LLink<T>(o);
123 			top=list;
124 		} else {
125 			top->Anade(o);
126 			top=top->Getnext();
127 		} /* if */
128 	};
129 
AddAfter(LLink<T> * pos,T * o)130 	void AddAfter(LLink<T> *pos,T *o)
131 	{
132 		if (pos==NULL) {
133 			if (list==NULL) {
134 				list=new LLink<T>(o);
135 				top=list;
136 			} else {
137 				list=new LLink<T>(o,list);
138 			} /* if */
139 		} else {
140 			LLink<T> *nl=new LLink<T>(o);
141 
142 			nl->Setnext(pos->Getnext());
143 			pos->Setnext(nl);
144 			if (nl->Getnext()==NULL) top=nl;
145 		} /* if */
146 	} /* AddAfter */
147 
148 	T *operator[](int index) {
149 		LLink<T> *tmp=list;
150 		while(tmp!=NULL && index>0) {
151 			tmp=tmp->Getnext();
152 			index--;
153 		} /* while */
154 		if (tmp==NULL) throw;
155 		return tmp->GetObj();
156 	};
157 
Iterate(T * & o)158 	bool Iterate(T *&o) {
159 		if (EndP()) return false;
160 		o=act->GetObj();
161 		act=act->Getnext();
162 		return true;
163 	} /* Iterate */
164 
ExtractIni(void)165 	T *ExtractIni(void) {
166 		LLink<T> *tmp;
167 		T *o;
168 
169 		if (list==NULL) return NULL;
170 		o=list->GetObj();
171 		tmp=list;
172 		list=list->Getnext();
173 		tmp->Setnext(NULL);
174 		if (act==tmp) act=list;
175 		if (top==act) top=NULL;
176 		tmp->Setobj(NULL);
177 		delete tmp;
178 		return o;
179 	} /* ExtractIni */
180 
Extract(void)181 	T *Extract(void) {
182 		LLink<T> *tmp,*tmp2=NULL;
183 		T *o;
184 
185 		if (list==NULL) return NULL;
186 		tmp=list;
187 		while(tmp->Getnext()!=NULL) {
188 			tmp2=tmp;
189 			tmp=tmp->Getnext();
190 		} /* while */
191 		o=tmp->GetObj();
192 		if (tmp2==NULL) {
193 			list=NULL;
194 			top=NULL;
195 			act=NULL;
196 		} else {
197 			tmp2->Setnext(NULL);
198 			top=tmp2;
199 		} /* if */
200 
201 		if (act==tmp) act=top;
202 		tmp->Setobj(NULL);
203 		delete tmp;
204 		return o;
205 	} /* Extract */
206 
MemberP(T * o)207 	bool MemberP(T *o) {
208 		LLink<T> *tmp;
209 		tmp=list;
210 		while(tmp!=NULL) {
211 			if (*(tmp->GetObj())==*o) return true;
212 			tmp=tmp->Getnext();
213 		} /* while */
214 		return false;
215 	} /* MemberP */
216 
MemberGet(T * o)217 	T *MemberGet(T *o) {
218 		LLink<T> *tmp;
219 		tmp=list;
220 		while(tmp!=NULL) {
221 			if (*(tmp->GetObj())==*o) return tmp->GetObj();
222 			tmp=tmp->Getnext();
223 		} /* while */
224 		return NULL;
225 	} /* MemberGet */
226 
MemberRefP(T * o)227 	bool MemberRefP(T *o) {
228 		LLink<T> *tmp;
229 		tmp=list;
230 		while(tmp!=NULL) {
231 			if (tmp->GetObj()==o) return true;
232 			tmp=tmp->Getnext();
233 		} /* while */
234 		return false;
235 	} /* MemberRefP */
236 
Length()237 	int Length() {
238 		LLink<T> *tmp;
239 		int count=0;
240 
241 		tmp=list;
242 		while(tmp!=NULL) {
243 			tmp=tmp->Getnext();
244 			count++;
245 		} /* while */
246 		return count;
247 	};
248 
Copy(List l)249 	void Copy(List l) {
250 		T *o;
251 		Delete();
252 		original=true;
253 		l.Rewind();
254 		while(l.Iterate(o)) {
255 			o=new T(*o);
256 			Add(o);
257 		} /* while */
258 	} /* Copy */
259 
DeleteElement(T * o)260 	bool DeleteElement(T *o)
261 	{
262 		LLink<T> *tmp1,*tmp2;
263 
264 		tmp1=list;
265 		tmp2=NULL;
266 		while(tmp1!=NULL && tmp1->GetObj()!=o) {
267 			tmp2=tmp1;
268 			tmp1=tmp1->Getnext();
269 		} /* while */
270 
271 		if (tmp1!=NULL) {
272 			if (tmp2==NULL) {
273 				/* Eliminar el primer elemento de la lista: */
274 				list=list->Getnext();
275 				tmp1->Setnext(NULL);
276 				if (act==tmp1) act=list;
277 				tmp1->Setobj(NULL);
278 				delete tmp1;
279 			} else {
280 				/* Eliminar un elemento intermedio: */
281 				tmp2->Setnext(tmp1->Getnext());
282 				if (act==tmp1) act=tmp1->Getnext();
283 				if (top==tmp1) top=tmp2;
284 				tmp1->Setnext(NULL);
285 				tmp1->Setobj(NULL);
286 				delete tmp1;
287 			} /* if */
288 			return true;
289 		} else {
290 			return false;
291 		} /* if */
292 
293 	} /* DeleteOne */
294 
GetRandom(void)295 	T *GetRandom(void) {
296 		int i,l=Length();
297 		i=((rand()*l)/RAND_MAX);
298 		if (i==l) i=l-1;
299 
300 		return operator[](i);
301 	} /* GetRandom */
302 
303 	bool operator==(List<T> &l) {
304 		LLink<T> *tmp1,*tmp2;
305 
306 		tmp1=list;
307 		tmp2=l.list;
308 		while(tmp1!=NULL && tmp2!=NULL) {
309 			if (!((*(tmp1->GetObj()))==(*(tmp2->GetObj())))) return false;
310 			tmp1=tmp1->Getnext();
311 			tmp2=tmp2->Getnext();
312 		} /* while */
313 		return tmp1==tmp2;
314 	} /* == */
315 
316 
SearchObjRef(T * o)317 	int SearchObjRef(T *o)
318 	{
319 		LLink<T> *tmp;
320 		int pos=0;
321 
322 		tmp=list;
323 		while(tmp!=NULL) {
324 			if ((tmp->GetObj())==o) return pos;
325 			tmp=tmp->Getnext();
326 			pos++;
327 		} /* while */
328 		return -1;
329 	} /* SearchObj */
330 
SearchObj(T * o)331 	int SearchObj(T *o)
332 	{
333 		LLink<T> *tmp;
334 		int pos=0;
335 
336 		tmp=list;
337 		while(tmp!=NULL) {
338 			if (*(tmp->GetObj())==*o) return pos;
339 			tmp=tmp->Getnext();
340 			pos++;
341 		} /* while */
342 		return -1;
343 	} /* SearchObj */
344 
345 
SetNoOriginal(void)346 	void SetNoOriginal(void) {original=false;}
SetOriginal(void)347 	void SetOriginal(void) {original=true;}
348 
349 private:
350 	bool original;
351 	LLink<T> *list,*top;
352 	LLink<T> *act;
353 };
354 
355 
356 
357 #endif
358