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