1 : /* _________________________________________________________________________
2 : *
3 : * UTILIB: A utility library for developing portable C++ codes.
4 : * Copyright (c) 2001, Sandia National Laboratories.
5 : * This software is distributed under the GNU Lesser General Public License.
6 : * For more information, see the README file in the top UTILIB directory.
7 : * _________________________________________________________________________
8 : */
9 :
10 : /**
11 : * \file LinkedList.h
12 : *
13 : * Defines the utilib::ListItem and utilib::LinkedList classes
14 : */
15 :
16 : #ifndef utilib_LinkedList_h
17 : #define utilib_LinkedList_h
18 :
19 : #include <utilib/std_headers.h>
20 : #include <utilib/exception_mngr.h>
21 : #include <utilib/CachedAllocator.h>
22 : #include <utilib/_generic.h>
23 : #include <utilib/PackBuf.h>
24 :
25 :
26 : namespace utilib {
27 :
28 : using std::bidirectional_iterator_tag;
29 :
30 : template <class T, class _Alloc>
31 : class LinkedItem;
32 :
33 : template <class _Tp, class _Alloc>
34 : class LinkedList;
35 :
36 : template<typename _Tp, typename _Ref, typename _Ptr, typename _Node,
37 : typename _NodeOpClass>
38 : class __LinkedList_iterator;
39 :
40 :
41 : /**
42 : * A simple container class that is used by LinkedList.
43 : *
44 : * This code includes the management of a list of unused ListItem's,
45 : * which are used first before new ListItem's are constructed. The
46 : * user can clear the unused items if that is desirable.
47 : */
48 : template <class T>
49 : class ListItem : public CachedAllocatorObject<ListItem<T> >
50 : {
51 :
52 : #if !defined(DOXYGEN)
53 : template <class wasT, class wasAlloc> friend class LinkedList;
54 : #endif
55 :
56 : public:
57 :
58 : /// Construct an item with the given data value.
59 : ListItem( const T& Data_)
60 : : Data(Data_) {next = prev = 0;}
61 :
62 : /// Construct an item with the given data value.
63 478364 : ListItem( )
64 478364 : {next = prev = 0;}
65 :
66 : /// Destructor
67 478364 : virtual ~ListItem() {}
68 :
69 : /// Return the item's data value.
70 100671 : T& data()
71 100671 : {return Data;}
72 :
73 : /// Return true if \a item equals the data value in the current item.
74 : bool operator==(const ListItem<T>& item)
75 : {return (Data == item.Data);}
76 :
77 : /// The item's data value.
78 : T Data;
79 :
80 : /// The next item in the linked list
81 : ListItem<T>* next;
82 :
83 : /// The previous item in the linked list
84 : ListItem<T>* prev;
85 :
86 : ///
87 497569 : void deallocate_derived()
88 497569 : { CachedAllocator<ListItem<T> > :: deallocate_derived(this); }
89 :
90 : };
91 :
92 :
93 :
94 : /**
95 : * Base class for __LinkedList_iterator that defines operations that
96 : * are specific to the _Node object used to represent the elements of
97 : * the linked list.
98 : */
99 : template<typename _Tp, typename _Ref, typename _Ptr, typename _Node,
100 : typename _NodeOpClass>
101 : class __LinkedList_iterator_base : public _NodeOpClass
102 : {
103 : public:
104 :
105 : /// Pointer to the data that is being iteratored through
106 : _Node* _M_node;
107 :
108 : /// Constructor
109 32017 : __LinkedList_iterator_base()
110 32017 : : _M_node(0)
111 32017 : { }
112 :
113 : /// Constructor
114 2456462 : __LinkedList_iterator_base(_Node* __x)
115 2456462 : : _M_node(__x)
116 2456462 : { }
117 :
118 : /// Increment the iterator
119 736615 : void _M_incr()
120 736615 : { _M_node = _M_node->next; }
121 :
122 : /// Decrement the iterator
123 : void _M_decr()
124 : { _M_node = _M_node->prev; }
125 :
126 : /// Return a reference to the data
127 800667 : _Ref operator*() const
128 800667 : { return value(_M_node); }
129 :
130 : /// Return a pointer to the data
131 46277 : _Ptr operator->() const
132 46277 : { _Ref tmp = this->operator*(); return &tmp; }
133 :
134 : };
135 :
136 :
137 :
138 : /**
139 : * Base class for __LinkedList_iterator that a LinkedList can use
140 : * as an iterator for the array
141 : */
142 : template<typename _Ref, typename _Node>
143 : class __LinkedList_Standard_OpClass
144 1498496 : {
145 : public:
146 :
147 : /// Return a reference to the data being passed in
148 240069 : _Ref value(_Node* node) const
149 : {
150 240069 : if (!node)
151 0 : EXCEPTION_MNGR(runtime_error,"Accessing an invalid iterator.");
152 240069 : return node->Data;
153 : }
154 :
155 : };
156 :
157 :
158 :
159 : /**
160 : * Base class for __LinkedList_iterator that a LinkedList can use
161 : * as an iterator for the array
162 : */
163 : template<typename _Ref, typename _Node>
164 : class __LinkedList_Pointer_OpClass
165 557815 : {
166 : public:
167 :
168 : /// Return a reference to the data being passed in
169 38133 : _Ref value(_Node* node) const
170 : {
171 38133 : if (!node)
172 0 : EXCEPTION_MNGR(runtime_error,"Accessing an invalid iterator.");
173 38133 : return *(node->Data);
174 : }
175 :
176 : };
177 :
178 :
179 : /**
180 : * class for __LinkedList_iterator that a LinkedList can use
181 : * as an iterator for the array
182 : */
183 : template<typename _Tp, typename _Ref, typename _Ptr, typename _Node,
184 : typename _NodeOpClass>
185 : class __LinkedList_iterator :
186 : public __LinkedList_iterator_base<_Tp,_Ref,_Ptr,_Node,_NodeOpClass>
187 : {
188 : public:
189 :
190 : #if !defined(DOXYGEN)
191 : ///
192 : typedef size_t size_type;
193 :
194 : ///
195 : typedef ptrdiff_t difference_type;
196 :
197 : ///
198 : typedef bidirectional_iterator_tag iterator_category;
199 :
200 : ///
201 : typedef _Tp value_type;
202 :
203 : ///
204 : typedef _Ptr pointer;
205 :
206 : ///
207 : typedef _Ref reference;
208 :
209 : ///
210 : typedef __LinkedList_iterator<_Tp,_Ref,_Ptr,_Node,_NodeOpClass> iterator;
211 : #endif
212 :
213 : /// Constructor
214 32017 : __LinkedList_iterator()
215 32017 : : __LinkedList_iterator_base<_Tp,_Ref,_Ptr,_Node,_NodeOpClass>() {}
216 :
217 : /// Constructor
218 2456462 : __LinkedList_iterator(_Node* __x)
219 2456462 : : __LinkedList_iterator_base<_Tp,_Ref,_Ptr,_Node,_NodeOpClass>(__x) {}
220 :
221 : /// Copy operator
222 33932 : iterator& operator=(const iterator& __x)
223 : {
224 33932 : this->_M_node = __x._M_node;
225 33932 : return *this;
226 : }
227 :
228 : /// Equality operator
229 68858 : bool operator==(const iterator& __x) const
230 68858 : { return this->_M_node == __x._M_node; }
231 :
232 : /// Inequality operator
233 1201374 : bool operator!=(const iterator& __x) const
234 1201374 : { return this->_M_node != __x._M_node; }
235 :
236 : /// Increment the iterator
237 : iterator& operator++()
238 : {
239 : this->_M_incr();
240 : return *this;
241 : }
242 :
243 : /// Increment the iterator
244 736615 : iterator operator++(int)
245 : {
246 736615 : iterator __tmp = *this;
247 736615 : this->_M_incr();
248 736615 : return __tmp;
249 : }
250 :
251 : /// Decrement the iterator
252 : iterator& operator--()
253 : {
254 : this->_M_decr();
255 : return *this;
256 : }
257 :
258 : /// Decrement the iterator
259 : iterator operator--(int)
260 : {
261 : iterator __tmp = *this;
262 : this->_M_decr();
263 : return __tmp;
264 : }
265 :
266 : };
267 :
268 :
269 : /**
270 : * class for __LinkedList_ptr_iterator that a LinkedList can use
271 : * as an iterator for the array
272 : */
273 : template<typename _Tp, typename _Ref, typename _Ptr, typename _Node,
274 : typename _NodeOpClass>
275 : class __LinkedList_ptr_iterator :
276 : public __LinkedList_iterator_base<_Tp,_Ref,_Ptr,_Node,_NodeOpClass>
277 : {
278 : public:
279 :
280 : #if !defined(DOXYGEN)
281 : ///
282 : typedef size_t size_type;
283 :
284 : ///
285 : typedef ptrdiff_t difference_type;
286 :
287 : ///
288 : typedef bidirectional_iterator_tag iterator_category;
289 :
290 : ///
291 : typedef _Tp value_type;
292 :
293 : ///
294 : typedef _Ptr pointer;
295 :
296 : ///
297 : typedef _Ref reference;
298 :
299 : ///
300 : typedef __LinkedList_ptr_iterator<_Tp,_Ref,_Ptr,_Node,_NodeOpClass> iterator;
301 : #endif
302 :
303 : /// Constructor
304 : __LinkedList_ptr_iterator()
305 : : __LinkedList_iterator_base<_Tp,_Ref,_Ptr,_Node,_NodeOpClass>() {}
306 :
307 : /// Constructor
308 : __LinkedList_ptr_iterator(_Node* __x)
309 : : __LinkedList_iterator_base<_Tp,_Ref,_Ptr,_Node,_NodeOpClass>(__x) {}
310 :
311 : /// Copy constructor
312 : __LinkedList_ptr_iterator(const iterator& __x)
313 : : __LinkedList_iterator_base<_Tp,_Ref,_Ptr,_Node,_NodeOpClass>(__x._M_node) {}
314 :
315 : /// Constructor
316 : __LinkedList_ptr_iterator(const typename __LinkedList_iterator<_Tp*,_Ref,_Ptr,_Node,_NodeOpClass>::iterator& __x)
317 : : __LinkedList_iterator_base<_Tp,_Ref,_Ptr,_Node,_NodeOpClass>(__x._M_node) {}
318 :
319 : /// Copy operator
320 : iterator& operator=(const iterator& __x)
321 : {
322 : this->_M_node = __x._M_node;
323 : return *this;
324 : }
325 :
326 : /// Copy operator
327 : iterator& operator=(const typename __LinkedList_iterator<_Tp*,_Tp*&,_Tp**,_Node,_NodeOpClass>::iterator& __x)
328 : { this->_M_node = __x._M_node; return *this; }
329 :
330 : /// Copy operator
331 : iterator& operator=(const typename __LinkedList_iterator<_Tp*,_Tp* const&,_Tp*const *,_Node,_NodeOpClass>::iterator& __x)
332 : { this->_M_node = __x._M_node; return *this; }
333 :
334 : /// Returns true if the current iterator points to a value that differs
335 : /// from the value returned by this iterator.
336 : bool operator!=(const iterator& __x) const
337 : { return this->_M_node != __x._M_node; }
338 :
339 : /// Increment the iterator
340 : iterator& operator++()
341 : {
342 : this->_M_incr();
343 : return *this;
344 : }
345 :
346 : /// Increment the iterator
347 : iterator operator++(int)
348 : {
349 : iterator __tmp = *this;
350 : this->_M_incr();
351 : return __tmp;
352 : }
353 :
354 : /// Decrement the iterator
355 : iterator& operator--()
356 : {
357 : this->_M_decr();
358 : return *this;
359 : }
360 :
361 : /// Decrement the iterator
362 : iterator operator--(int)
363 : {
364 : iterator __tmp = *this;
365 : this->_M_decr();
366 : return __tmp;
367 : }
368 :
369 : };
370 :
371 :
372 : /**
373 : * A class that defines a doubly-linked list.
374 : *
375 : * The design of this class was strongly influenced by
376 : * Stanley B. Lippman, "C++ Primer, 2nd Edition." Addison Wesley, 1991.
377 : * This linked list code can be switched between use as a queue, stack or
378 : * simple linked list by setting different `mode' values. By default, a
379 : * LinkedList object behaves like a queue.
380 : */
381 : template <class _Tp, class _Alloc = std::allocator<_Tp> >
382 : class LinkedList
383 : {
384 : public:
385 :
386 : #if !defined(DOXYGEN)
387 : ///
388 : typedef _Tp value_type;
389 :
390 : ///
391 : typedef value_type* pointer;
392 :
393 : ///
394 : typedef const value_type* const_pointer;
395 :
396 : ///
397 : typedef value_type& reference;
398 :
399 : ///
400 : typedef const value_type& const_reference;
401 :
402 : ///
403 : typedef ListItem<_Tp> _Node;
404 :
405 : ///
406 : typedef size_t size_type;
407 :
408 : ///
409 : typedef ptrdiff_t difference_type;
410 :
411 : ///
412 : typedef __LinkedList_iterator<_Tp,_Tp&,_Tp*,_Node,__LinkedList_Standard_OpClass<_Tp&,_Node> > iterator;
413 :
414 : ///
415 : typedef __LinkedList_iterator<_Tp,const _Tp&,const _Tp*,_Node,__LinkedList_Standard_OpClass<_Tp&,_Node> > const_iterator;
416 :
417 : /*
418 : ** TODO: What is the issue here? namespace support?
419 : */
420 : #if defined(UTILIB_SOLARIS_CC)
421 : ///
422 : typedef std::__reverse_bi_iterator<const_iterator,
423 : bidirectional_iterator_tag, value_type,
424 : const_reference, const_pointer, difference_type>
425 : const_reverse_iterator;
426 :
427 : ///
428 : typedef std::__reverse_bi_iterator<iterator,
429 : bidirectional_iterator_tag, value_type,
430 : reference, pointer, difference_type>
431 : reverse_iterator;
432 : #elif defined(COUGAR) || defined(TFLOPS_SERVICE)
433 :
434 : #if 0 /// disabled because the coompiler has problems...
435 : ///
436 : typedef reverse_bidirectional_iterator<const_iterator, value_type,
437 : const_reference, difference_type>
438 : const_reverse_iterator;
439 :
440 : ///
441 : typedef reverse_bidirectional_iterator<iterator, value_type, reference,
442 : difference_type>
443 : reverse_iterator;
444 : #endif
445 :
446 : #else
447 : ///
448 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
449 :
450 : ///
451 : typedef std::reverse_iterator<iterator> reverse_iterator;
452 : #endif
453 : #endif
454 :
455 : /// Empty constructor, which sets up an empty linked list.
456 237234 : LinkedList()
457 237234 : {
458 237234 : mode=queueLL;
459 237234 : counter++;
460 237234 : first = last = CachedAllocator<ListItem<_Tp> > :: allocate();
461 237234 : last->next = last->prev = 0;
462 237234 : Len=0;
463 237234 : validate_flag=false;
464 : }
465 :
466 : /**
467 : * Destructor.
468 : * After deleting the list, the destructor deletes the list of
469 : * additional unused ListItem objects.
470 : */
471 : virtual ~LinkedList();
472 :
473 : /**
474 : * Copy equal operator.
475 : */
476 100 : LinkedList<_Tp,_Alloc>& operator=(const LinkedList<_Tp,_Alloc>& list_)
477 : {
478 100 : validate_flag = list_.validate_flag;
479 100 : mode = list_.mode;
480 100 : clear();
481 100 : const_iterator curr = list_.begin();
482 100 : const_iterator end = list_.end();
483 335 : while (curr != end) {
484 135 : push_back(*curr);
485 135 : curr++;
486 : }
487 100 : return *this;
488 : }
489 :
490 : /**
491 : * Copy constructor.
492 : */
493 100 : LinkedList(const LinkedList<_Tp,_Alloc>& list_)
494 100 : {
495 100 : mode=queueLL;
496 100 : counter++;
497 100 : first = last = CachedAllocator<ListItem<_Tp> > :: allocate();
498 100 : last->next = last->prev = 0;
499 100 : Len=0;
500 100 : validate_flag=false;
501 100 : *this = list_;
502 : }
503 :
504 : /**
505 : * Find the ListItem with value \a data in the list.
506 : * If this data value is not found in the list, this method
507 : * returns \c NULL.
508 : */
509 : ListItem<_Tp>* find(const _Tp& data);
510 :
511 : /// Returns the iterator that defines the beginning of the list
512 425410 : iterator begin()
513 425410 : { return first; }
514 :
515 : /// Returns the iterator that defines the ending of the list
516 775817 : iterator end()
517 775817 : { return last; }
518 :
519 : /// Returns the const iterator that defines the beginning of the list
520 150 : const_iterator begin() const
521 150 : { return first; }
522 :
523 : /// Returns the const iterator that defines the ending of the list
524 150 : const_iterator end() const
525 150 : { return last; }
526 : //{ return const_cast<ListItem<_Tp>*>(last); }
527 :
528 : ///
529 : /// Returns a reverse iterator to the last element of the list
530 : reverse_iterator rbegin()
531 : { return reverse_iterator(end()); }
532 :
533 : /// Returns a reverse iterator to the last element of the list
534 : const_reverse_iterator rbegin() const
535 : { return const_reverse_iterator(end()); }
536 :
537 : /// Returns a reverse iterator to the first element of the list
538 : reverse_iterator rend()
539 : { return reverse_iterator(begin()); }
540 :
541 : /// Returns a reverse iterator to the first element of the list
542 : const_reverse_iterator rend() const
543 : { return const_reverse_iterator(begin()); }
544 :
545 : /// Returns an iterator to the first element of the list
546 : reference front()
547 : {
548 : if (Len == 0)
549 : EXCEPTION_MNGR(runtime_error, "LinkedList::front() - empty list");
550 : return *begin();
551 : }
552 :
553 : /// Returns an iterator to the first element of the list
554 : const_reference front() const
555 : {
556 : if (Len == 0)
557 : EXCEPTION_MNGR(runtime_error, "LinkedList::front() - empty list");
558 : return *begin();
559 : }
560 :
561 : /// Returns an iterator to the last element of the list
562 : reference back()
563 : {
564 : if (Len == 0)
565 : EXCEPTION_MNGR(runtime_error, "LinkedList::back() - empty list");
566 : return *(--end());
567 : }
568 :
569 : /// Returns an iterator to the last element of the list
570 : const_reference back() const
571 : {
572 : if (Len == 0)
573 : EXCEPTION_MNGR(runtime_error, "LinkedList::back() - empty list");
574 : return *(--end());
575 : }
576 :
577 : /// Insert __x before the specified position
578 239804 : iterator insert(iterator __position, const _Tp& __x)
579 : {
580 239804 : return insert_value(__x, __position._M_node);
581 : }
582 :
583 : /// Insert an empty value before the specified position
584 : iterator insert(iterator __position)
585 : { return insert_value(__position._M_node); }
586 :
587 : /// Insert a value to the begining of the list
588 10 : void push_front(const _Tp& __x)
589 10 : { insert(begin(), __x); }
590 :
591 : /// Insert an empty element to the begining of the list
592 : void push_front()
593 : { insert(begin()); }
594 :
595 : /// Insert a value to the end of the list
596 239794 : void push_back(const _Tp& __x)
597 239794 : { insert(end(), __x); }
598 :
599 : /// Insert an empty element to the end of the list
600 : void push_back()
601 : { insert(end()); }
602 :
603 : /// Remove an element at the specified position
604 19075 : iterator erase(iterator __position)
605 : {
606 19075 : ListItem<_Tp>* next = __position._M_node->next;
607 19075 : remove(__position._M_node);
608 19075 : return iterator(next);
609 : }
610 :
611 : /// Clear the list
612 104 : void clear()
613 : {
614 238 : while (!empty())
615 134 : pop_front();
616 : }
617 :
618 :
619 : /// Remove an item from the beginning
620 30 : void pop_front()
621 30 : { erase(begin()); }
622 :
623 : /// Remove an item from the end
624 : void pop_back()
625 : {
626 : iterator __tmp = end();
627 : erase(--__tmp);
628 : }
629 :
630 : /// Returns the head of the linked list.
631 2592 : ListItem<_Tp>* head() const
632 2592 : {return (first == last ? 0 : first);}
633 :
634 : /// Returns the tail of the linked list.
635 : ListItem<_Tp>* tail() const
636 : {return last->prev;}
637 :
638 : /// Returns the next item in the list after \a item.
639 7869 : ListItem<_Tp>* next(ListItem<_Tp>* item) const
640 7869 : {return (item->next == last ? 0 : item->next);}
641 :
642 : /// Returns the value of the next item that will be removed.
643 0 : _Tp& top()
644 : {
645 0 : if (Len <= 0) {
646 0 : EXCEPTION_MNGR(runtime_error, "LinkedList::top -- Empty list");
647 0 : exit(0);
648 : }
649 0 : if (mode == queueLL) return first->data();
650 0 : return last->prev->data();
651 : }
652 :
653 : /**
654 : * Adds a list item with data value \a data, and returns the ListItem
655 : * object that is generated.
656 : */
657 115 : ListItem<_Tp>* add(const _Tp& data)
658 115 : { return insert_value(data,0); }
659 :
660 : /**
661 : * Adds a list item with data value \a data, which is inserted
662 : * just before the given position. Returns the ListItem
663 : * object in the \a item argument.
664 : */
665 0 : ListItem<_Tp>* add(const _Tp& data, ListItem<_Tp>* position)
666 0 : { return insert_value(data,position); }
667 :
668 : /**
669 : * Insert an item in the list with data value \a data.
670 : * If \a item is not null, then the new item is inserted before
671 : * \a next. Otherwise, it is inserted at the end of the list.
672 : */
673 260235 : ListItem<_Tp>* insert_value( const _Tp& data, ListItem<_Tp>* item)
674 : {
675 260235 : ListItem<_Tp>* tmp = insert_value(item);
676 260235 : tmp->Data=data;
677 260235 : return tmp;
678 : }
679 :
680 : /**
681 : * Insert an empty item in the list.
682 : * If \a item is not null, then the new item is inserted before
683 : * \a next. Otherwise, it is inserted at the end of the list.
684 : */
685 : ListItem<_Tp>* insert_value(ListItem<_Tp>* item);
686 :
687 : /// Removes the next list item and returns the data value in \a data.
688 45 : void remove( _Tp& data)
689 : {
690 45 : if (mode==queueLL)
691 45 : extract(first,data);
692 : else
693 0 : extract(last->prev,data);
694 : }
695 :
696 : /// Removes \a item from the list.
697 20346 : void remove( ListItem<_Tp>* item)
698 20346 : {extract(item);}
699 :
700 : /// Removes \a item from the list and returns the data value in \a data.
701 0 : void remove(ListItem<_Tp>* item, _Tp& data)
702 0 : {extract(item,data);}
703 :
704 : /// Returns true if the list is empty
705 : bool empty() const;
706 :
707 : /// Returns true if the list is not empty
708 1613 : operator bool() const
709 1613 : {return (first == last ? false : true);}
710 :
711 : /// Returns the length of the list.
712 70503 : size_type size() const
713 70503 : {return Len;}
714 :
715 : /// Sets the add/remove mode to operate a stack.
716 0 : void stack_mode()
717 0 : {mode = stackLL;}
718 :
719 : /// Sets the add/remove mode to operate a queue (the default).
720 0 : void queue_mode()
721 0 : {mode = queueLL;}
722 :
723 : /// If true, then validate extraction operations
724 : bool validate_flag;
725 :
726 : /// Write this object to a stream
727 : void write(std::ostream& os) const;
728 :
729 : /// Read this object from a stream
730 : void read(std::istream& is);
731 :
732 : /// Write this object to a buffer
733 : void write(PackBuffer& os) const;
734 :
735 : /// Read this object from a buffer
736 : void read(UnPackBuffer& is);
737 :
738 : protected:
739 :
740 : /// Defines the different modes that the LinkedList can operate
741 : enum {
742 : /// Adds items to the beginning; Removes items from the beginning
743 : stackLL = 0,
744 : /// Adds items to the end; Removes items from the beginning
745 : queueLL = 1
746 : };
747 :
748 : /// The add/remove mode.
749 : int mode;
750 :
751 : /// Removes an item from the list.
752 : void extract(ListItem<_Tp>* item);
753 :
754 : /// Removes an item from the list and returns its value in \a data.
755 45 : void extract(ListItem<_Tp>* item, _Tp& data)
756 45 : {data = item->Data; extract(item);}
757 :
758 : /// The first item in the list.
759 : ListItem<_Tp> *first;
760 :
761 : /// The last item in the list.
762 : ListItem<_Tp>* last;
763 :
764 : /// The length of the list.
765 : size_type Len;
766 :
767 : /// The number of unused ListItem objects.
768 : static int counter;
769 :
770 : /// A routine used to debug/validate the LinkedList class
771 : void validate(ListItem<_Tp>* item=0);
772 : };
773 :
774 :
775 :
776 :
777 :
778 : //
779 : // LinkedList methods
780 : //
781 :
782 : template <class _Tp, class _Alloc>
783 : int LinkedList<_Tp,_Alloc>::counter=0;
784 :
785 :
786 : template <class _Tp, class _Alloc>
787 237334 : LinkedList<_Tp,_Alloc>::~LinkedList()
788 : {
789 714512 : while (!empty())
790 239844 : extract(first);
791 237334 : counter--;
792 237334 : CachedAllocator<ListItem<_Tp> > :: deallocate(last);
793 237334 : last = 0;
794 :
795 237334 : if (!counter)
796 237190 : CachedAllocator<ListItem<_Tp> > :: delete_unused();
797 237334 : }
798 :
799 :
800 : template <class _Tp, class _Alloc>
801 737547 : bool LinkedList<_Tp,_Alloc>::empty() const
802 : {
803 737547 : return (first == last ? true : false) ;
804 : }
805 :
806 :
807 : template <class _Tp, class _Alloc>
808 260235 : void LinkedList<_Tp,_Alloc>::extract(ListItem<_Tp>* item)
809 : {
810 260235 : if (item == last)
811 0 : EXCEPTION_MNGR(runtime_error, "LinkedList::extract - trying to erase 'last'");
812 260235 : if (empty())
813 0 : EXCEPTION_MNGR(runtime_error, "LinkedList<_Tp,_Alloc>::extract : empty list");
814 :
815 260235 : if (validate_flag)
816 0 : validate(item);
817 :
818 260235 : if (item->prev)
819 17584 : item->prev->next = item->next;
820 : else
821 242651 : first = item->next;
822 :
823 260235 : item->next->prev = item->prev;
824 260235 : Len--;
825 :
826 260235 : if (validate_flag)
827 0 : validate();
828 :
829 260235 : CachedAllocator<ListItem<_Tp> > :: deallocate(item);
830 260235 : item = 0;
831 : }
832 :
833 :
834 : template <class _Tp, class _Alloc>
835 260235 : ListItem<_Tp>* LinkedList<_Tp,_Alloc>::insert_value(ListItem<_Tp>* next)
836 : {
837 260235 : ListItem<_Tp>* item = CachedAllocator<ListItem<_Tp> > :: allocate();
838 260235 : item->next = item->prev = 0;
839 :
840 260235 : if (next) {
841 241108 : if (next->prev)
842 3890 : next->prev->next = item;
843 : else
844 237218 : first = item;
845 241108 : item->next = next;
846 241108 : item->prev = next->prev;
847 241108 : next->prev = item;
848 : }
849 : else { // appending to end of list
850 19127 : if (last->prev) {
851 18858 : last->prev->next = item;
852 18858 : item->prev = last->prev;
853 18858 : item->next = last;
854 18858 : last->prev = item;
855 : }
856 : else {
857 269 : first = last->prev = item;
858 269 : first->next = last;
859 : }
860 : }
861 :
862 260235 : Len++;
863 260235 : if (validate_flag)
864 0 : validate();
865 260235 : return item;
866 : }
867 :
868 :
869 : template <class _Tp, class _Alloc>
870 19045 : ListItem<_Tp>* LinkedList<_Tp,_Alloc>::find(const _Tp& data)
871 : {
872 19045 : ListItem<_Tp>* curr = first; //(first == last ? 0 : first);
873 :
874 80930 : while (curr != last) {
875 61885 : if (data == curr->data()) break;
876 42840 : curr = curr->next;
877 : }
878 :
879 19045 : return curr;
880 : }
881 :
882 : template <class _Tp, class _Alloc>
883 0 : void LinkedList<_Tp,_Alloc>::validate(ListItem<_Tp>*item)
884 : {
885 0 : if (first == last) {
886 0 : if (Len != 0)
887 0 : EXCEPTION_MNGR(runtime_error, "Nonzero length but first==last");
888 0 : if (last->next || last->prev)
889 0 : EXCEPTION_MNGR(runtime_error, "Bad link pointers in last");
890 0 : return;
891 : }
892 :
893 0 : if (last->next)
894 0 : EXCEPTION_MNGR(runtime_error, "Bad next pointers in last");
895 0 : if (first->prev)
896 0 : EXCEPTION_MNGR(runtime_error, "Bad prev pointers in first");
897 :
898 0 : ListItem<_Tp>* curr = first;
899 0 : unsigned int ctr=0;
900 0 : while (curr != last) {
901 0 : ctr++;
902 0 : if (ctr > Len)
903 0 : EXCEPTION_MNGR(runtime_error, "More than Len items in the list");
904 0 : if ((curr != first) && (curr->prev == 0))
905 0 : EXCEPTION_MNGR(runtime_error, "Null prev ptr for non-first");
906 0 : if ((curr != last) && (curr->next == 0))
907 0 : EXCEPTION_MNGR(runtime_error, "Null next ptr for non-last");
908 0 : if ((curr->prev) && (curr->prev->next != curr))
909 0 : EXCEPTION_MNGR(runtime_error, "curr->prev->next != curr");
910 0 : if ((curr->next) && (curr->next->prev != curr))
911 0 : EXCEPTION_MNGR(runtime_error, "curr->next->prev != curr");
912 0 : curr = curr->next;
913 : }
914 :
915 0 : if (!item) return;
916 :
917 0 : curr = first;
918 0 : bool flag=false;
919 0 : while (curr != last) {
920 0 : if (curr == item) {
921 0 : if (curr->next != item->next)
922 0 : EXCEPTION_MNGR(runtime_error, "curr->next != item->next");
923 0 : if (curr->prev != item->prev)
924 0 : EXCEPTION_MNGR(runtime_error, "curr->prev != item->prev");
925 0 : flag=true;
926 0 : break;
927 : }
928 0 : curr = curr->next;
929 : }
930 0 : if (!flag)
931 0 : EXCEPTION_MNGR(runtime_error, "The given item is not in the list!");
932 : }
933 :
934 :
935 : template <class _Tp, class _Alloc>
936 105 : void LinkedList<_Tp,_Alloc>::write(std::ostream& os) const
937 : {
938 105 : utilib::ListItem<_Tp>* curr = (first == last ? 0 : first);
939 :
940 105 : os << size() << " : ";
941 105 : if (size() == 0) return;
942 325 : while (curr != last) {
943 185 : os << curr->data() << " ";
944 185 : curr = curr->next;
945 : }
946 : }
947 :
948 :
949 : template <class _Tp, class _Alloc>
950 1 : void LinkedList<_Tp,_Alloc>::write(utilib::PackBuffer& os) const
951 : {
952 1 : utilib::ListItem<_Tp>* curr = (first == last ? 0 : first);
953 :
954 1 : os << size();
955 1 : if (size() == 0) return;
956 12 : while (curr != last) {
957 10 : os << curr->data();
958 10 : curr = curr->next;
959 : }
960 : }
961 :
962 :
963 : template <class _Tp, class _Alloc>
964 1 : void LinkedList<_Tp,_Alloc>::read(std::istream& is)
965 : {
966 : int tmp;
967 1 : is >> tmp;
968 : char c;
969 1 : is >> c;
970 11 : for (int i=0; i<tmp; i++) {
971 : _Tp item;
972 10 : is >> item;
973 11 : add(item);
974 : }
975 : }
976 :
977 :
978 : template <class _Tp, class _Alloc>
979 1 : void LinkedList<_Tp,_Alloc>::read(utilib::UnPackBuffer& is)
980 : {
981 : size_type tmp;
982 1 : is >> tmp;
983 11 : for (size_type i=0; i<tmp; i++) {
984 : _Tp item;
985 10 : is >> item;
986 11 : add(item);
987 : }
988 : }
989 :
990 :
991 : } // namespace utilib
992 :
993 : /// Out-stream operator for removing data from a list
994 : template <class _Tp, class _Alloc>
995 45 : inline utilib::LinkedList<_Tp,_Alloc>& operator>>(utilib::LinkedList<_Tp,_Alloc>& list, _Tp& data)
996 45 : {list.remove(data); return list;}
997 :
998 : /// Out-stream operator for adding data to a list
999 : template <class _Tp, class _Alloc>
1000 65 : inline utilib::LinkedList<_Tp,_Alloc>& operator<<(utilib::LinkedList<_Tp,_Alloc>& list, const _Tp& data)
1001 65 : {list.add(data); return list;}
1002 :
1003 : /// Out-stream operator for writing the contents of a LinkedList
1004 : template <class _Tp, class _Alloc>
1005 : inline std::ostream& operator<<(std::ostream& os,
1006 105 : const utilib::LinkedList<_Tp,_Alloc>& obj)
1007 105 : { obj.write(os); return(os); }
1008 :
1009 : /// Out-stream operator for writing the contents of a LinkedList
1010 : template <class _Tp, class _Alloc>
1011 : inline utilib::PackBuffer& operator<<(utilib::PackBuffer& os,
1012 1 : const utilib::LinkedList<_Tp,_Alloc>& obj)
1013 1 : { obj.write(os); return(os); }
1014 :
1015 : /// In-stream operator for reading the contents of a LinkedList
1016 : template <class _Tp, class _Alloc>
1017 : inline std::istream& operator>>(std::istream& is,
1018 1 : utilib::LinkedList<_Tp,_Alloc>& obj)
1019 1 : { obj.read(is); return(is); }
1020 :
1021 : /// In-stream operator for reading the contents of a LinkedList
1022 : template <class _Tp, class _Alloc>
1023 : inline utilib::UnPackBuffer& operator>>(utilib::UnPackBuffer& is,
1024 1 : utilib::LinkedList<_Tp,_Alloc>& obj)
1025 1 : { obj.read(is); return(is); }
1026 :
1027 : #endif
|
