1 /*! \file kbool/include/kbool/_dl_itr.h 2 \author Klaas Holwerda 3 4 Copyright: 2001-2004 (C) Klaas Holwerda 5 6 Licence: see kboollicense.txt 7 8 RCS-ID: $Id: _dl_itr.h,v 1.1 2005/05/24 19:13:35 titato Exp $ 9 */ 10 11 //! author="Klaas Holwerda" 12 /* 13 * Definitions of classes, for list implementation 14 * template list and iterator for any list node type 15 */ 16 17 #ifndef _DL_Iter_H 18 #define _DL_Iter_H 19 20 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA) 21 #pragma interface 22 #endif 23 24 #include <stdlib.h> 25 #include "kbool/include/booleng.h" 26 27 #ifndef _STATUS_ENUM 28 #define _STATUS_ENUM 29 //!<enum Error codes for List and iterator class 30 enum Lerror { 31 NO_MES, /*!<No Message will be generated */ 32 NO_LIST, /*!<List is not attached to the iterator*/ 33 NO_LIST_OTHER, /*!<no attached list on other iter*/ 34 AC_ITER_LIST_OTHER, /*!<iter not allowed on other list */ 35 SAME_LIST, /*!<same list not allowed*/ 36 NOT_SAME_LIST, /*!<must be same list*/ 37 ITER_GT_1, /*!<more then one iteriter at root*/ 38 ITER_GT_0, /*!<iter not allowed*/ 39 ITER_HITROOT, /*!<iter at root*/ 40 NO_ITEM, /*!<no item at current*/ 41 NO_NEXT, /*!<no next after current*/ 42 NO_PREV, /*!<no prev before current */ 43 EMPTY, /*!<list is empty*/ 44 NOT_ALLOW, /*!<not allowed*/ 45 ITER_NEG /*!<to much iters deleted*/ 46 }; 47 #endif 48 49 #define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t)) 50 #define RT _list->_root 51 #define HD _list->_root->_next 52 #define TL _list->_root->_prev 53 #define NB _list->_nbitems 54 55 template <class Dtype> class DL_List; 56 template <class Dtype> class DL_Iter; 57 template <class Dtype> class DL_SortIter; 58 59 //! Template class DL_Node 60 template <class Dtype> class DL_Node 61 { 62 friend class DL_List<Dtype>; 63 friend class DL_Iter<Dtype>; 64 friend class DL_SortIter<Dtype>; 65 66 //!Public members 67 public: 68 //!Template constructor no contents 69 //!Construct a node for a list object 70 DL_Node(); 71 72 //!constructor with init of Dtype 73 DL_Node( Dtype n ); 74 75 //!Destructor 76 ~DL_Node(); 77 78 //!Public members 79 public: 80 //!data in node 81 Dtype _item; 82 83 //!pointer to next node 84 DL_Node* _next; 85 86 //!pointer to previous node 87 DL_Node* _prev; 88 }; 89 90 //!Template class DL_List 91 template <class Dtype> class DL_List 92 { 93 friend class DL_Iter<Dtype>; 94 friend class DL_SortIter<Dtype>; 95 96 public: 97 //!Constructor 98 //!Construct a list object 99 //!!tcarg class | Dtype | list object 100 DL_List(); 101 102 //!destructor 103 ~DL_List(); 104 105 //!Report off List Errors 106 void Error(const char* function,Lerror a_error); 107 108 //!Number of items in the list 109 int count(); 110 111 //!Empty List? 112 bool empty(); 113 114 //!insert the object given at the end of the list, after tail 115 DL_Node<Dtype>* insend( Dtype n ); 116 117 //!insert the object given at the begin of the list, before head 118 DL_Node<Dtype>* insbegin( Dtype n ); 119 120 //!remove the object at the begin of the list (head) 121 void removehead(); 122 123 //! remove the object at the end of the list (tail) 124 void removetail(); 125 126 //!remove all objects from the list 127 void remove_all( bool deleteObject = false ); 128 129 //!Get the item at the head of the list 130 Dtype headitem(); 131 132 //!Get the item at the tail of the list 133 Dtype tailitem(); 134 135 //! to move all objects in a list to this list. 136 void takeover(DL_List<Dtype>* otherlist); 137 138 public: 139 //!the root node pointer of the list, the first and last node 140 //! in the list are connected to the root node. The root node is used 141 //! to detect the end / beginning of the list while traversing it. 142 DL_Node<Dtype>* _root; 143 144 //!the number of items in the list, if empty list it is 0 145 int _nbitems; 146 147 //!number of iterators on the list, Attaching or instantiating an iterator to list, 148 //! will increment this member, detaching and 149 //! destruction of iterator for a list will decrement this number 150 short int _iterlevel; 151 }; 152 153 //! Template class DL_Iter for iterator on DL_List 154 template <class Dtype> 155 class DL_Iter 156 { 157 public: 158 //!Construct an iterator object for a given list of type Dtype 159 DL_Iter(DL_List<Dtype>* newlist); 160 161 //!Constructor of iterator for the same list as another iterator 162 DL_Iter(DL_Iter* otheriter); 163 164 //!Constructor without an attached list 165 DL_Iter(); 166 167 //!destructor 168 ~DL_Iter(); 169 170 //!Report off Iterator Errors 171 void Error(const char* function,Lerror a_error); 172 173 //!This attaches an iterator to a list of a given type. 174 void Attach(DL_List<Dtype>* newlist); 175 176 //!This detaches an iterator from a list 177 void Detach(); 178 179 //!execute given function for each item in the list/iterator 180 void foreach_f(void (*fp) (Dtype n) ); 181 182 //! list mutations 183 184 //!insert after tail item 185 DL_Node<Dtype>* insend(Dtype n); 186 187 //!insert before head item 188 DL_Node<Dtype>* insbegin(Dtype n); 189 190 //!insert before current iterator position 191 DL_Node<Dtype>* insbefore(Dtype n); 192 193 //!insert after current iterator position 194 DL_Node<Dtype>* insafter(Dtype n); 195 196 //!to move all objects in a list to the list of the iterator. 197 void takeover(DL_List<Dtype>* otherlist); 198 199 //!to move all objects in a list (using iterator of that list) to the list of the iterator 200 void takeover(DL_Iter* otheriter); 201 202 //! to move maxcount objects in a list (using iterator of that list) to the list of the iterator 203 void takeover(DL_Iter* otheriter, int maxcount); 204 205 //!remove object at current iterator position from the list. 206 void remove(); 207 208 //!Remove head item 209 void removehead(); 210 211 //!Remove tail item 212 void removetail(); 213 214 //!Remove all items 215 void remove_all(); 216 217 218 /* void foreach_mf(void (Dtype::*mfp)() ); //call Dtype::mfp for each item */ 219 220 //!is list empty (contains items or not)? 221 bool empty(); 222 223 //!is iterator at root node (begin or end)? 224 bool hitroot(); 225 226 //!is iterator at head/first node? 227 bool athead(); 228 229 //!is iterator at tail/last node? 230 bool attail(); 231 232 //!is given item member of the list 233 bool has(Dtype otheritem); 234 235 //!Number of items in the list 236 int count(); 237 238 /* cursor movements */ 239 240 //!go to last item, if list is empty goto hite 241 void totail(); 242 243 //!go to first item, if list is empty goto hite 244 void tohead(); 245 246 //!set the iterator position to the root (empty dummy) object in the list. 247 void toroot(); 248 249 //! set the iterator position to next object in the list ( can be the root also). 250 void operator++ (void); 251 252 //!set iterator to next item (pre fix) 253 void operator++ (int); 254 255 //!set the iterator position to previous object in the list ( can be the root also)(postfix). 256 void operator-- (void); 257 258 //!set the iterator position to previous object in the list ( can be the root also)(pre fix). 259 void operator-- (int); 260 261 //!set the iterator position n objects in the next direction ( can be the root also). 262 void operator>> (int); 263 264 //!set the iterator position n objects in the previous direction ( can be the root also). 265 void operator<< (int); 266 267 //!set the iterator position to next object in the list, if this would be the root object, 268 //!then set the iterator at the head object 269 void next_wrap(); 270 271 //!set the iterator position to previous object in the list, if this would be the root object, 272 //!then set the iterator at the tail object 273 void prev_wrap(); 274 275 //!move root in order to make the current node the tail 276 void reset_tail(); 277 278 //!move root in order to make the current node the head 279 void reset_head(); 280 281 //!put the iterator at the position of the given object in the list. 282 bool toitem(Dtype); 283 284 //!put the iterator at the same position as the given iterator in the list. 285 void toiter(DL_Iter* otheriter); 286 287 //!put the iterator at the position of the given node in the list. 288 bool tonode(DL_Node<Dtype>*); 289 290 //!iterate through all items of the list 291 bool iterate(void); 292 293 //!To get the item at the current iterator position 294 Dtype item(); 295 296 //! get node at iterator 297 DL_Node<Dtype>* node(); 298 299 //!sort list with mergesort 300 void mergesort(int (*fcmp) (Dtype, Dtype)); 301 302 //!sort list with cocktailsort 303 /*! 304 \return number of swaps done. 305 */ 306 int cocktailsort(int (*)(Dtype,Dtype), bool (*)(Dtype,Dtype)=NULL); 307 308 protected: 309 310 //!sort list with mergesort 311 void mergesort_rec(int (*fcmp)(Dtype,Dtype), DL_Node<Dtype> *RT1,int n); 312 313 //!sort list with mergesort 314 void mergetwo(int (*fcmp)(Dtype,Dtype), DL_Node<Dtype> *RT1,DL_Node<Dtype> *RT2); 315 316 //!set the iterator position to next object in the list ( can be the root also). 317 void next(); 318 319 //!set the iterator position to previous object in the list ( can be the root also). 320 void prev(); 321 322 //!the list for this iterator 323 DL_List<Dtype> *_list; 324 325 //!the current position of the iterator 326 DL_Node<Dtype> *_current; 327 }; 328 329 330 //! template class DL_StackIter class for stack iterator on DL_List 331 template <class Dtype> 332 class DL_StackIter :protected DL_Iter<Dtype> 333 { 334 public: 335 //!Constructor of stack iterator for given list 336 DL_StackIter(DL_List<Dtype> *); 337 //!Constructor of stack iterator no list attached 338 DL_StackIter(); 339 340 //!Destructor of stack iterator 341 ~DL_StackIter(); 342 343 //!Remove all items from the stack 344 void remove_all(); 345 //!push given item on the stack 346 void push(Dtype n); 347 //!get last inserted item from stack 348 Dtype pop(); 349 //!is stack empty? 350 bool empty(); 351 //!number of items on the stack 352 int count(); 353 }; 354 355 //!template class DL_SortIter 356 template <class DType> class DL_SortIter :public DL_Iter<DType> 357 { 358 public: 359 //!Constructor of sort iterator for given list and sort function 360 DL_SortIter(DL_List<DType>* nw_list, int (*new_func)(DType ,DType )); 361 362 //!Constructor of sort iterator with sort function and no list attached 363 DL_SortIter(int (*newfunc)(DType,DType)); 364 365 //!Destructor of sort iterator 366 ~DL_SortIter(); 367 368 //!insert item in sorted order 369 void insert (DType new_item); 370 371 /*override following functions to give an error */ 372 //!Not allowed insend(bool n)373 void insend (bool n){sortitererror();}; 374 //!Not allowed insbegin(bool n)375 void insbegin (bool n){sortitererror();}; 376 //!Not allowed insbefore(bool n)377 void insbefore (bool n){sortitererror();}; 378 //!Not allowed insafter(bool n)379 void insafter (bool n){sortitererror();}; 380 //!Not allowed takeover(DL_List<DType> *)381 void takeover (DL_List<DType>*){sortitererror();}; 382 //!Not allowed takeover(DL_Iter<DType> *)383 void takeover (DL_Iter<DType>*){sortitererror();}; 384 //!Not allowed takeover(DL_Iter<DType> * otheriter,int maxcount)385 void takeover (DL_Iter<DType>* otheriter, int maxcount){sortitererror();}; 386 //!Not allowed next_wrap()387 void next_wrap() {sortitererror();}; 388 //!Not allowed prev_wrap()389 void prev_wrap() {sortitererror();}; 390 //!Not allowed reset_tail()391 void reset_tail() {sortitererror();}; 392 //!Not allowed reset_head()393 void reset_head() {sortitererror();}; 394 395 private: 396 //!Report off Iterator Errors 397 void sortitererror(); 398 399 //!comparefunction used to insert items in sorted order 400 int (*comparef)(DType, DType); 401 }; 402 403 #include "kbool/include/_dl_itr.cpp" 404 405 #endif 406