00001 // $Id: genlist.h 751 2006-03-31 15:43:49Z alex $ 00002 /* @@tag:xara-cn@@ DO NOT MODIFY THIS LINE 00003 ================================XARAHEADERSTART=========================== 00004 00005 Xara LX, a vector drawing and manipulation program. 00006 Copyright (C) 1993-2006 Xara Group Ltd. 00007 Copyright on certain contributions may be held in joint with their 00008 respective authors. See AUTHORS file for details. 00009 00010 LICENSE TO USE AND MODIFY SOFTWARE 00011 ---------------------------------- 00012 00013 This file is part of Xara LX. 00014 00015 Xara LX is free software; you can redistribute it and/or modify it 00016 under the terms of the GNU General Public License version 2 as published 00017 by the Free Software Foundation. 00018 00019 Xara LX and its component source files are distributed in the hope 00020 that it will be useful, but WITHOUT ANY WARRANTY; without even the 00021 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00022 See the GNU General Public License for more details. 00023 00024 You should have received a copy of the GNU General Public License along 00025 with Xara LX (see the file GPL in the root directory of the 00026 distribution); if not, write to the Free Software Foundation, Inc., 51 00027 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00028 00029 00030 ADDITIONAL RIGHTS 00031 ----------------- 00032 00033 Conditional upon your continuing compliance with the GNU General Public 00034 License described above, Xara Group Ltd grants to you certain additional 00035 rights. 00036 00037 The additional rights are to use, modify, and distribute the software 00038 together with the wxWidgets library, the wxXtra library, and the "CDraw" 00039 library and any other such library that any version of Xara LX relased 00040 by Xara Group Ltd requires in order to compile and execute, including 00041 the static linking of that library to XaraLX. In the case of the 00042 "CDraw" library, you may satisfy obligation under the GNU General Public 00043 License to provide source code by providing a binary copy of the library 00044 concerned and a copy of the license accompanying it. 00045 00046 Nothing in this section restricts any of the rights you have under 00047 the GNU General Public License. 00048 00049 00050 SCOPE OF LICENSE 00051 ---------------- 00052 00053 This license applies to this program (XaraLX) and its constituent source 00054 files only, and does not necessarily apply to other Xara products which may 00055 in part share the same code base, and are subject to their own licensing 00056 terms. 00057 00058 This license does not apply to files in the wxXtra directory, which 00059 are built into a separate library, and are subject to the wxWindows 00060 license contained within that directory in the file "WXXTRA-LICENSE". 00061 00062 This license does not apply to the binary libraries (if any) within 00063 the "libs" directory, which are subject to a separate license contained 00064 within that directory in the file "LIBS-LICENSE". 00065 00066 00067 ARRANGEMENTS FOR CONTRIBUTION OF MODIFICATIONS 00068 ---------------------------------------------- 00069 00070 Subject to the terms of the GNU Public License (see above), you are 00071 free to do whatever you like with your modifications. However, you may 00072 (at your option) wish contribute them to Xara's source tree. You can 00073 find details of how to do this at: 00074 http://www.xaraxtreme.org/developers/ 00075 00076 Prior to contributing your modifications, you will need to complete our 00077 contributor agreement. This can be found at: 00078 http://www.xaraxtreme.org/developers/contribute/ 00079 00080 Please note that Xara will not accept modifications which modify any of 00081 the text between the start and end of this header (marked 00082 XARAHEADERSTART and XARAHEADEREND). 00083 00084 00085 MARKS 00086 ----- 00087 00088 Xara, Xara LX, Xara X, Xara X/Xtreme, Xara Xtreme, the Xtreme and Xara 00089 designs are registered or unregistered trademarks, design-marks, and/or 00090 service marks of Xara Group Ltd. All rights in these marks are reserved. 00091 00092 00093 Xara Group Ltd, Gaddesden Place, Hemel Hempstead, HP2 6EX, UK. 00094 http://www.xara.com/ 00095 00096 =================================XARAHEADEREND============================ 00097 */ 00098 // 00099 00100 #ifndef INC_LIST_TEMPLATE 00101 #define INC_LIST_TEMPLATE 00102 00103 // We want better memory tracking 00104 // Declare smart memory handling in Debug builds 00105 #define new CAM_DEBUG_NEW 00106 00107 00108 /************************************************************************************** 00109 00110 > template <class T> 00111 > class ListT 00112 00113 Author: Colin_Barfoot (Xara Group Ltd) <camelotdev@xara.com> (from STL) 00114 Created: 20/12/96 00115 Purpose: Generic List 00116 00117 **************************************************************************************/ 00118 00119 //#include "function.h" 00120 //#include <algobase.h> 00121 #include "iterator.h" 00122 #include "defalloc.h" 00123 00124 00125 template <typename T> 00126 class ListT 00127 { 00128 protected: 00129 typedef Allocator<void>::Pointer VoidPointer; 00130 00131 struct ListNode; 00132 friend struct ListNode; 00133 00134 struct ListNode 00135 { 00136 VoidPointer next; 00137 VoidPointer prev; 00138 T data; 00139 }; 00140 00141 public: 00142 typedef T ValueType; 00143 00144 typedef Allocator<T> ValueAllocatorType; 00145 typedef typename Allocator<T>::Pointer Pointer; 00146 typedef typename Allocator<T>::Reference Reference; 00147 typedef typename Allocator<T>::ConstReference ConstReference; 00148 00149 typedef Allocator<ListNode> ListNodeAllocatorType; 00150 typedef typename Allocator<ListNode>::Pointer LinkType; 00151 typedef typename Allocator<ListNode>::SizeType SizeType; 00152 typedef typename Allocator<ListNode>::DifferenceType DifferenceType; 00153 00154 protected: 00155 static ListNodeAllocatorType g_ListNodeAllocator; 00156 static ValueAllocatorType g_ValueAllocator; 00157 00158 protected: 00159 // SizeType BufferSize() 00160 // { 00161 // return ListNodeAllocator.InitPageSize(); 00162 // } 00163 00164 // struct list_node_buffer; 00165 // friend list_node_buffer; 00166 // struct ListNodeBuffer 00167 // { 00168 // void_pointer next_buffer; 00169 // link_type buffer; 00170 // }; 00171 public: 00172 // typedef Allocator<list_node_buffer> buffer_allocator_type; 00173 // typedef Allocator<list_node_buffer>::pointer buffer_pointer; 00174 protected: 00175 // static Allocator<list_node_buffer> buffer_allocator; 00176 00177 // /*static*/ buffer_pointer buffer_list; 00178 // /*static*/ link_type free_list; 00179 // /*static*/ link_type next_avail; 00180 // /*static*/ link_type last; 00181 /* 00182 void add_new_buffer() { 00183 buffer_pointer tmp = buffer_allocator.allocate((size_type)1); 00184 tmp->buffer = list_node_allocator.allocate(buffer_size()); 00185 tmp->next_buffer = buffer_list; 00186 buffer_list = tmp; 00187 next_avail = buffer_list->buffer; 00188 last = next_avail + buffer_size(); 00189 } 00190 */ 00191 SizeType m_NumberOfLists; 00192 // void deallocate_buffers(); 00193 00194 LinkType GetNode() 00195 { 00196 return new ListNode; 00197 /* Extended Mix 00198 LinkType NodeToReturn; 00199 if (m_FreeList != NULL) 00200 { 00201 LinkType tmp = m_FreeList; 00202 m_FreeList = (LinkType)m_FreeList->next; 00203 NodeToReturn = tmp; 00204 } 00205 else 00206 { 00207 if (m_NextAvail == m_Last) 00208 { 00209 AddNewBuffer(); 00210 } 00211 NodeToReturn = m_NextAvail++; 00212 } 00213 return NodeToReturn; 00214 } 00215 */ 00216 // return free_list ? (free_list = (link_type)(free_list->next), tmp) 00217 // : (next_avail == last ? (add_new_buffer(), next_avail++) : next_avail++); 00218 // ugly code for inlining - avoids multiple returns 00219 } 00220 void PutNode(LinkType p) 00221 { 00222 delete p; 00223 // p->next = free_list; 00224 // free_list = p; 00225 } 00226 00227 protected: 00228 LinkType m_Node; 00229 SizeType m_Length; 00230 BOOL m_bIsValid; 00231 00232 public: 00233 class ConstIterator; 00234 class Iterator : public BidirectionalIterator<T, DifferenceType> 00235 { 00236 friend class ListT<T>; 00237 friend class ConstIterator; 00238 // friend bool operator==(const iterator& x, const iterator& y); 00239 protected: 00240 LinkType m_Node; 00241 Iterator(LinkType x) : m_Node(x) {} 00242 00243 public: 00244 Iterator() {} 00245 00246 BOOL operator==(const Iterator& x) const { return m_Node == x.m_Node; } 00247 Reference operator*() const { return (*m_Node).data; } 00248 Iterator& operator++() 00249 { 00250 m_Node = (LinkType)((*m_Node).next); 00251 return *this; 00252 } 00253 00254 Iterator operator++(INT32) 00255 { 00256 Iterator tmp = *this; 00257 ++*this; 00258 return tmp; 00259 } 00260 Iterator& operator--() 00261 { 00262 m_Node = (LinkType)((*m_Node).prev); 00263 return *this; 00264 } 00265 Iterator operator--(INT32) 00266 { 00267 Iterator tmp = *this; 00268 --*this; 00269 return tmp; 00270 } 00271 }; 00272 00273 class ConstIterator : public BidirectionalIterator<T, DifferenceType> 00274 { 00275 friend class ListT<T>; 00276 protected: 00277 LinkType m_Node; 00278 ConstIterator(LinkType x) : m_Node(x) {} 00279 public: 00280 ConstIterator() {} 00281 ConstIterator(const Iterator& x) : m_Node(x.m_Node) {} 00282 BOOL operator==(const ConstIterator& x) const { return m_Node == x.m_Node; } 00283 00284 ConstReference operator*() const { return (*m_Node).data; } 00285 00286 00287 ConstIterator& operator++() 00288 { 00289 m_Node = (LinkType)((*m_Node).next); 00290 return *this; 00291 } 00292 00293 ConstIterator operator++(INT32) 00294 { 00295 ConstIterator tmp = *this; 00296 ++*this; 00297 return tmp; 00298 } 00299 00300 ConstIterator& operator--() 00301 { 00302 m_Node = (LinkType)((*m_Node).prev); 00303 return *this; 00304 } 00305 00306 ConstIterator operator--(INT32) 00307 { 00308 ConstIterator tmp = *this; 00309 --*this; 00310 return tmp; 00311 } 00312 }; 00313 /* 00314 typedef reverse_bidirectional_iterator<const_iterator, value_type, 00315 const_reference, difference_type> 00316 const_reverse_iterator; 00317 typedef reverse_bidirectional_iterator<iterator, value_type, reference, 00318 difference_type> 00319 reverse_iterator; 00320 */ 00321 ListT() : m_NumberOfLists(0), m_Length(0) //,free_list(0), buffer_list(0), next_avail(0), last(0), 00322 { 00323 ++m_NumberOfLists; 00324 m_Node = GetNode(); 00325 if (m_Node != NULL) 00326 { 00327 (*m_Node).next = m_Node; 00328 (*m_Node).prev = m_Node; 00329 m_bIsValid = TRUE; 00330 } 00331 else 00332 { 00333 m_bIsValid = FALSE; 00334 } 00335 } 00336 00337 BOOL IsValid() const { return m_bIsValid; } 00338 00339 Iterator Begin() { return (LinkType)((*m_Node).next); } 00340 ConstIterator Begin() const { return (LinkType)((*m_Node).next); } 00341 Iterator End() { return m_Node; } 00342 ConstIterator End() const { return m_Node; } 00343 /* 00344 reverse_iterator rbegin() { return reverse_iterator(end()); } 00345 const_reverse_iterator rbegin() const { 00346 return const_reverse_iterator(end()); 00347 } 00348 reverse_iterator rend() { return reverse_iterator(begin()); } 00349 const_reverse_iterator rend() const { 00350 return const_reverse_iterator(begin()); 00351 } 00352 */ 00353 BOOL Empty() const { return m_Length == 0; } 00354 SizeType Size() const { return m_Length; } 00355 /* 00356 size_type max_size() const { return list_node_allocator.max_size(); } 00357 */ 00358 Reference Front() { return *(Begin()); } // ++? 00359 ConstReference Front() const { return *(Begin()); } // ++? 00360 Reference Back() { return *(--End()); } 00361 ConstReference Back() const { return *(--End()); } 00362 /* 00363 void swap(list<T>& x) { 00364 std::swap(node, x.node); 00365 std::swap(length, x.length); 00366 } 00367 */ 00368 Iterator Insert(Iterator Position, const T& X) 00369 { 00370 LinkType tmp = GetNode(); 00371 if (tmp != NULL) 00372 { 00373 Construct(g_ValueAllocator.Address((*tmp).data), X); 00374 (*tmp).next = Position.m_Node; 00375 (*tmp).prev = (*Position.m_Node).prev; 00376 (*(LinkType((*Position.m_Node).prev))).next = tmp; 00377 (*Position.m_Node).prev = tmp; 00378 ++m_Length; 00379 } 00380 return tmp; 00381 } 00382 /* 00383 void insert(iterator position, const T* first, const T* last); 00384 void insert(iterator position, const_iterator first, 00385 const_iterator last); 00386 void insert(iterator position, size_type n, const T& x); 00387 void push_front(const T& x) { insert(begin(), x); } 00388 */ 00389 BOOL PushBack(const T& X) 00390 { 00391 return (Insert(End(), X).m_Node != NULL); 00392 } 00393 00394 00395 void Erase(Iterator Position) 00396 { 00397 if (m_Length != 0) 00398 { 00399 (*(LinkType((*Position.m_Node).prev))).next = (*Position.m_Node).next; 00400 (*(LinkType((*Position.m_Node).next))).prev = (*Position.m_Node).prev; 00401 Destroy(g_ValueAllocator.Address((*Position.m_Node).data)); 00402 PutNode(Position.m_Node); 00403 --m_Length; 00404 } 00405 else 00406 { 00407 ERROR3("Erase from Empty ListT"); 00408 } 00409 } 00410 void Erase(Iterator First, Iterator Last); 00411 // void pop_front() { erase(begin()); } 00412 void PopBack() 00413 { 00414 Iterator tmp = End(); 00415 Erase(--tmp); 00416 } 00417 /* 00418 List(size_type n, const T& value = T()) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) { 00419 ++number_of_lists; 00420 node = get_node(); 00421 (*node).next = node; 00422 (*node).prev = node; 00423 insert(begin(), n, value); 00424 } 00425 list(const T* first, const T* last) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) { 00426 ++number_of_lists; 00427 node = get_node(); 00428 (*node).next = node; 00429 (*node).prev = node; 00430 insert(begin(), first, last); 00431 } 00432 list(const list<T>& x) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) { 00433 ++number_of_lists; 00434 node = get_node(); 00435 (*node).next = node; 00436 (*node).prev = node; 00437 insert(begin(), x.begin(), x.end()); 00438 } 00439 */ 00440 ~ListT() 00441 { 00442 Erase(Begin(), End()); 00443 PutNode(m_Node); 00444 // if (--m_NumberOfLists == 0) 00445 // { 00446 // deallocate_buffers(); 00447 // } 00448 } 00449 00450 // list<T>& operator=(const list<T>& x); 00451 /* 00452 protected: 00453 void transfer(iterator position, iterator first, iterator last) { 00454 (*(link_type((*last.node).prev))).next = position.node; 00455 (*(link_type((*first.node).prev))).next = last.node; 00456 (*(link_type((*position.node).prev))).next = first.node; 00457 link_type tmp = link_type((*position.node).prev); 00458 (*position.node).prev = (*last.node).prev; 00459 (*last.node).prev = (*first.node).prev; 00460 (*first.node).prev = tmp; 00461 } 00462 public: 00463 void splice(iterator position, list<T>& x) { 00464 if (!x.empty()) { 00465 transfer(position, x.begin(), x.end()); 00466 length += x.length; 00467 x.length = 0; 00468 } 00469 } 00470 void splice(iterator position, list<T>& x, iterator i) { 00471 iterator j = i; 00472 if (position == i || position == ++j) return; 00473 transfer(position, i, j); 00474 ++length; 00475 --x.length; 00476 } 00477 void splice(iterator position, list<T>& x, iterator first, iterator last) { 00478 if (first != last) { 00479 if (&x != this) { 00480 difference_type n = 0; 00481 distance(first, last, n); 00482 x.length -= n; 00483 length += n; 00484 } 00485 transfer(position, first, last); 00486 } 00487 } 00488 void remove(const T& value); 00489 void unique(); 00490 void merge(list<T>& x); 00491 void reverse(); 00492 void sort(); 00493 */ 00494 }; 00495 00496 /* 00497 template <class T> 00498 list<T>::buffer_pointer list<T>::buffer_list = 0; 00499 00500 template <class T> 00501 list<T>::link_type list<T>::free_list = 0; 00502 00503 template <class T> 00504 list<T>::link_type list<T>::next_avail = 0; 00505 00506 template <class T> 00507 list<T>::link_type list<T>::last = 0; 00508 00509 template <class T> 00510 list<T>::size_type list<T>::number_of_lists = 0; 00511 */ 00512 00513 template< typename T > 00514 typename ListT<T>::ListNodeAllocatorType ListT<T>::g_ListNodeAllocator; 00515 00516 template< typename T > 00517 typename ListT<T>::ValueAllocatorType ListT<T>::g_ValueAllocator; 00518 00519 //template <class T> 00520 //list<T>::buffer_allocator_type list<T>::buffer_allocator; 00521 00522 /* 00523 * currently the following does not work - made into a member function 00524 00525 template <class T> 00526 inline bool operator==(const list<T>::iterator& x, const list<T>::iterator& y) { 00527 return x.node == y.node; 00528 } 00529 */ 00530 /* 00531 template <class T> 00532 inline bool operator==(const list<T>& x, const list<T>& y) { 00533 return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); 00534 } 00535 00536 template <class T> 00537 inline bool operator<(const list<T>& x, const list<T>& y) { 00538 return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); 00539 } 00540 template <class T> 00541 void list<T>::deallocate_buffers() { 00542 while (buffer_list) { 00543 buffer_pointer tmp = buffer_list; 00544 buffer_list = (buffer_pointer)(buffer_list->next_buffer); 00545 list_node_allocator.deallocate(tmp->buffer); 00546 buffer_allocator.deallocate(tmp); 00547 } 00548 free_list = 0; 00549 next_avail = 0; 00550 last = 0; 00551 } 00552 00553 template <class T> 00554 void list<T>::insert(iterator position, const T* first, const T* last) { 00555 while (first != last) insert(position, *first++); 00556 } 00557 00558 template <class T> 00559 void list<T>::insert(iterator position, const_iterator first, 00560 const_iterator last) { 00561 while (first != last) insert(position, *first++); 00562 } 00563 00564 template <class T> 00565 void list<T>::insert(iterator position, size_type n, const T& x) { 00566 while (n--) insert(position, x); 00567 } 00568 */ 00569 template <class T> 00570 void ListT<T>::Erase(Iterator First, Iterator Last) 00571 { 00572 while (!(First == Last)) 00573 { 00574 Erase(First++); 00575 } 00576 } 00577 00578 /* 00579 template <class T> 00580 list<T>& list<T>::operator=(const list<T>& x) { 00581 if (this != &x) { 00582 iterator first1 = begin(); 00583 iterator last1 = end(); 00584 const_iterator first2 = x.begin(); 00585 const_iterator last2 = x.end(); 00586 while (first1 != last1 && first2 != last2) *first1++ = *first2++; 00587 if (first2 == last2) 00588 erase(first1, last1); 00589 else 00590 insert(last1, first2, last2); 00591 } 00592 return *this; 00593 } 00594 00595 template <class T> 00596 void list<T>::remove(const T& value) { 00597 iterator first = begin(); 00598 iterator last = end(); 00599 while (first != last) { 00600 iterator next = first; 00601 ++next; 00602 if (*first == value) erase(first); 00603 first = next; 00604 } 00605 } 00606 00607 template <class T> 00608 void list<T>::unique() { 00609 iterator first = begin(); 00610 iterator last = end(); 00611 if (first == last) return; 00612 iterator next = first; 00613 while (++next != last) { 00614 if (*first == *next) 00615 erase(next); 00616 else 00617 first = next; 00618 next = first; 00619 } 00620 } 00621 00622 template <class T> 00623 void list<T>::merge(list<T>& x) { 00624 iterator first1 = begin(); 00625 iterator last1 = end(); 00626 iterator first2 = x.begin(); 00627 iterator last2 = x.end(); 00628 while (first1 != last1 && first2 != last2) 00629 if (*first2 < *first1) { 00630 iterator next = first2; 00631 transfer(first1, first2, ++next); 00632 first2 = next; 00633 } else 00634 ++first1; 00635 if (first2 != last2) transfer(last1, first2, last2); 00636 length += x.length; 00637 x.length= 0; 00638 } 00639 00640 template <class T> 00641 void list<T>::reverse() { 00642 if (size() < 2) return; 00643 for (iterator first = ++begin(); first != end();) { 00644 iterator old = first++; 00645 transfer(begin(), old, first); 00646 } 00647 } 00648 00649 template <class T> 00650 void list<T>::sort() { 00651 if (size() < 2) return; 00652 list<T> carry; 00653 list<T> counter[64]; 00654 INT32 fill = 0; 00655 while (!empty()) { 00656 carry.splice(carry.begin(), *this, begin()); 00657 INT32 i = 0; 00658 while(i < fill && !counter[i].empty()) { 00659 counter[i].merge(carry); 00660 carry.swap(counter[i++]); 00661 } 00662 carry.swap(counter[i]); 00663 if (i == fill) ++fill; 00664 } 00665 while(fill--) merge(counter[fill]); 00666 } 00667 00668 #undef Allocator 00669 #undef list 00670 */ 00671 00672 // undefine "new".otherwise it messes up the CC_IMPLEMENT_DYNCREATE 00673 // and CC_IMPLEMENT_DYNAMIC macros!! 00674 #undef new 00675 #endif