00001 /**************************************************************************** 00002 ** 00003 ** Copyright (c) 2008-2011 C.B. Barber. All rights reserved. 00004 ** $Id: //main/2011/qhull/src/libqhullcpp/QhullLinkedList.h#2 $$Change: 1342 $ 00005 ** $DateTime: 2011/03/07 21:55:47 $$Author: bbarber $ 00006 ** 00007 ****************************************************************************/ 00008 00009 #ifndef QHULLLINKEDLIST_H 00010 #define QHULLLINKEDLIST_H 00011 00012 namespace std { struct bidirectional_iterator_tag; struct random_access_iterator_tag; } 00013 00014 #include "QhullError.h" 00015 00016 #ifdef QHULL_USES_QT 00017 #include <QtCore/QList> 00018 #endif 00019 00020 #ifndef QHULL_NO_STL 00021 #include <algorithm> 00022 #endif 00023 00024 namespace orgQhull { 00025 00026 #//Type 00027 00028 00029 00030 00031 00032 00033 00034 00035 00036 00037 00038 template <typename T> 00039 class QhullLinkedList 00040 { 00041 private: 00042 #//Fields 00043 T begin_node; 00044 T end_node; 00045 00046 public: 00047 #//Subtypes and types 00048 class const_iterator; 00049 class iterator; 00050 typedef const_iterator ConstIterator; 00051 typedef iterator Iterator; 00052 typedef ptrdiff_t difference_type; 00053 typedef int size_type; 00054 typedef T value_type; 00055 typedef const value_type *const_pointer; 00056 typedef const value_type &const_reference; 00057 typedef value_type *pointer; 00058 typedef value_type &reference; 00059 00060 #//Constructors 00061 QhullLinkedList<T>(T b, T e) : begin_node(b), end_node(e) {} 00062 //Copy constructor copies pointer but not contents. Needed for return by value and parameter passing. 00063 QhullLinkedList<T>(const QhullLinkedList<T> &o) : begin_node(o.begin_node), end_node(o.end_node) {} 00064 ~QhullLinkedList<T>() {} 00065 00066 private: 00068 QhullLinkedList<T>() {} 00070 QhullLinkedList<T> &operator=(const QhullLinkedList<T> &l) {} 00071 public: 00072 00073 #//Conversions 00074 #ifndef QHULL_NO_STL 00075 std::vector<T> toStdVector() const; 00076 #endif 00077 #ifdef QHULL_USES_QT 00078 QList<T> toQList() const; 00079 #endif 00080 00081 #//Read-only 00082 int count() const; 00083 //count(t) under #//Search 00084 bool empty() const { return isEmpty(); } 00085 bool isEmpty() const { return (begin_node==end_node); } 00086 bool operator==(const QhullLinkedList<T> &o) const; 00087 bool operator!=(const QhullLinkedList<T> &o) const { return !operator==(o); } 00088 size_t size() const { return count(); } 00089 00090 #//Element access 00091 00092 T back() const { return last(); } 00093 T first() const { QHULL_ASSERT(!isEmpty()); return *begin(); } 00094 T front() const { return first(); } 00095 T last() const { QHULL_ASSERT(!isEmpty()); return *--end(); } 00096 00097 #//Modify -- Allocation of opaque types not implemented. 00098 00099 #//Search 00100 bool contains(const T &t) const; 00101 int count(const T &t) const; 00102 00103 #//Iterator 00104 iterator begin() { return begin_node; } 00105 const_iterator begin() const { return begin_node; } 00106 const_iterator constBegin() const { return begin_node; } 00107 const_iterator constEnd() const { return end_node; } 00108 iterator end() { return end_node; } 00109 const_iterator end() const { return end_node; } 00110 00111 class iterator { 00112 00113 private: 00114 T i; 00115 friend class const_iterator; 00116 00117 public: 00118 typedef std::bidirectional_iterator_tag iterator_category; 00119 typedef T value_type; 00120 typedef value_type *pointer; 00121 typedef value_type &reference; 00122 typedef ptrdiff_t difference_type; 00123 00124 iterator() : i() {} 00125 iterator(T t) : i(t) {} 00126 iterator(const iterator &o) : i(o.i) {} 00127 iterator &operator=(const iterator &o) { i= o.i; return *this; } 00128 00129 T operator*() const { return i; } 00130 T operator->() const { return i; } 00131 bool operator==(const iterator &o) const { return i == o.i; } 00132 bool operator!=(const iterator &o) const { return !operator==(o); } 00133 bool operator==(const const_iterator &o) const { return i==reinterpret_cast<const iterator &>(o).i; } 00134 bool operator!=(const const_iterator &o) const { return !operator==(o); } 00135 iterator &operator++() { i= i.next(); return *this; } 00136 iterator operator++(int) { iterator o= i; i= i.next(); return o; } 00137 iterator &operator--() { i= i.previous(); return *this; } 00138 iterator operator--(int) { iterator o= i; i= i.previous(); return o; } 00139 iterator operator+(int j) const; 00140 iterator operator-(int j) const { return operator+(-j); } 00141 iterator &operator+=(int j) { return *this= *this + j; } 00142 iterator &operator-=(int j) { return *this= *this - j; } 00143 };//QhullLinkedList::iterator 00144 00145 class const_iterator { 00146 00147 private: 00148 T i; 00149 00150 public: 00151 typedef std::bidirectional_iterator_tag iterator_category; 00152 typedef T value_type; 00153 typedef const value_type *pointer; 00154 typedef const value_type &reference; 00155 typedef ptrdiff_t difference_type; 00156 00157 const_iterator() : i() {} 00158 const_iterator(T t) : i(t) {} 00159 const_iterator(const const_iterator &o) : i(o.i) {} 00160 const_iterator(iterator o) : i(o.i) {} 00161 const_iterator &operator=(const const_iterator &o) { i= o.i; return *this; } 00162 00163 T operator*() const { return i; } 00164 T operator->() const { return i; } 00165 bool operator==(const const_iterator &o) const { return i == o.i; } 00166 bool operator!=(const const_iterator &o) const { return !operator==(o); } 00167 // No comparisons or iterator diff 00168 const_iterator &operator++() { i= i.next(); return *this; } 00169 const_iterator operator++(int) { const_iterator o= i; i= i.next(); return o; } 00170 const_iterator &operator--() { i= i.previous(); return *this; } 00171 const_iterator operator--(int) { const_iterator o= i; i= i.previous(); return o; } 00172 const_iterator operator+(int j) const; 00173 const_iterator operator-(int j) const { return operator+(-j); } 00174 const_iterator &operator+=(int j) { return *this= *this + j; } 00175 const_iterator &operator-=(int j) { return *this= *this - j; } 00176 };//QhullLinkedList::const_iterator 00177 00178 };//QhullLinkedList 00179 00180 template <typename T> 00181 class QhullLinkedListIterator // FIXUP QH11016 define QhullMutableLinkedListIterator 00182 { 00183 typedef typename QhullLinkedList<T>::const_iterator const_iterator; 00184 const QhullLinkedList<T> *c; 00185 const_iterator i; 00186 00187 public: 00188 QhullLinkedListIterator(const QhullLinkedList<T> &container) : c(&container), i(c->constBegin()) {} 00189 QhullLinkedListIterator &operator=(const QhullLinkedList<T> &container) { c= &container; i= c->constBegin(); return *this; } 00190 bool findNext(const T &t); 00191 bool findPrevious(const T &t); 00192 bool hasNext() const { return i != c->constEnd(); } 00193 bool hasPrevious() const { return i != c->constBegin(); } 00194 T next() { return *i++; } 00195 T peekNext() const { return *i; } 00196 T peekPrevious() const { const_iterator p= i; return *--p; } 00197 T previous() { return *--i; } 00198 void toFront() { i= c->constBegin(); } 00199 void toBack() { i= c->constEnd(); } 00200 };//QhullLinkedListIterator 00201 00202 #//== Definitions ========================================= 00203 00204 #//Conversion 00205 00206 #ifndef QHULL_NO_STL 00207 template <typename T> 00208 std::vector<T> QhullLinkedList<T>:: 00209 toStdVector() const 00210 { 00211 std::vector<T> tmp; 00212 std::copy(constBegin(), constEnd(), std::back_inserter(tmp)); 00213 return tmp; 00214 }//toStdVector 00215 #endif 00216 00217 #ifdef QHULL_USES_QT 00218 template <typename T> 00219 QList<T> QhullLinkedList<T>:: 00220 toQList() const 00221 { 00222 QhullLinkedListIterator<T> i(*this); 00223 QList<T> ls; 00224 while(i.hasNext()){ 00225 ls.append(i.next()); 00226 } 00227 return ls; 00228 }//toQList 00229 #endif 00230 00231 #//Read-only 00232 00233 template <typename T> 00234 int QhullLinkedList<T>:: 00235 count() const 00236 { 00237 const_iterator i= begin_node; 00238 int c= 0; 00239 while(i != end_node){ 00240 c++; 00241 i++; 00242 } 00243 return c; 00244 }//count 00245 00246 #//Search 00247 00248 template <typename T> 00249 bool QhullLinkedList<T>:: 00250 contains(const T &t) const 00251 { 00252 const_iterator i= begin_node; 00253 while(i != end_node){ 00254 if(i==t){ 00255 return true; 00256 } 00257 i++; 00258 } 00259 return false; 00260 }//contains 00261 00262 template <typename T> 00263 int QhullLinkedList<T>:: 00264 count(const T &t) const 00265 { 00266 const_iterator i= begin_node; 00267 int c= 0; 00268 while(i != end_node){ 00269 if(i==t){ 00270 c++; 00271 } 00272 i++; 00273 } 00274 return c; 00275 }//count 00276 00277 template <typename T> 00278 bool QhullLinkedList<T>:: 00279 operator==(const QhullLinkedList<T> &l) const 00280 { 00281 if(begin_node==l.begin_node){ 00282 return (end_node==l.end_node); 00283 } 00284 T i= begin_node; 00285 T il= l.begin_node; 00286 while(i != end_node){ 00287 if(i != il){ 00288 return false; 00289 } 00290 i= static_cast<T>(i.next()); 00291 il= static_cast<T>(il.next()); 00292 } 00293 if(il != l.end_node){ 00294 return false; 00295 } 00296 return true; 00297 }//operator== 00298 00299 #//Iterator 00300 00301 template <typename T> 00302 typename QhullLinkedList<T>::iterator QhullLinkedList<T>::iterator:: 00303 operator+(int j) const 00304 { 00305 T n= i; 00306 if(j>0){ 00307 while(j--){ 00308 n= n.next(); 00309 } 00310 }else{ 00311 while(j++){ 00312 n= n.previous(); 00313 } 00314 } 00315 return iterator(n); 00316 }//operator+ 00317 00318 template <typename T> 00319 typename QhullLinkedList<T>::const_iterator QhullLinkedList<T>::const_iterator:: 00320 operator+(int j) const 00321 { 00322 T n= i; 00323 if(j>0){ 00324 while(j--){ 00325 n= n.next(); 00326 } 00327 }else{ 00328 while(j++){ 00329 n= n.previous(); 00330 } 00331 } 00332 return const_iterator(n); 00333 }//operator+ 00334 00335 #//QhullLinkedListIterator 00336 00337 template <typename T> 00338 bool QhullLinkedListIterator<T>:: 00339 findNext(const T &t) 00340 { 00341 while(i != c->constEnd()){ 00342 if (*i++ == t){ 00343 return true; 00344 } 00345 } 00346 return false; 00347 }//findNext 00348 00349 template <typename T> 00350 bool QhullLinkedListIterator<T>:: 00351 findPrevious(const T &t) 00352 { 00353 while(i!=c->constBegin()){ 00354 if(*(--i)==t){ 00355 return true; 00356 } 00357 } 00358 return false; 00359 }//findNext 00360 00361 }//namespace orgQhull 00362 00363 #//Global functions 00364 00365 template <typename T> 00366 std::ostream & 00367 operator<<(std::ostream &os, const orgQhull::QhullLinkedList<T> &qs) 00368 { 00369 typename orgQhull::QhullLinkedList<T>::const_iterator i; 00370 for(i= qs.begin(); i != qs.end(); ++i){ 00371 os << *i; 00372 } 00373 return os; 00374 }//operator<< 00375 00376 #endif // QHULLLINKEDLIST_H 00377