genlist.h

Go to the documentation of this file.
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

Generated on Sat Nov 10 03:45:26 2007 for Camelot by  doxygen 1.4.4