Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
linkedlist.h
Go to the documentation of this file.
1 #ifndef LINKEDLIST_H
2 #define LINKEDLIST_H
3 
4 #include <boost/static_assert.hpp>
5 #include <boost/type_traits.hpp>
6 #include <list>
7 
8 namespace frechet { namespace data {
9 
24 protected:
27  friend class BLinkedList;
28 public:
31 
32 #ifdef LINKED_LIST_VDESTRUCTOR
33 
41  virtual ~BLinkedListElement();
42 #endif
43  BLinkedListElement*& prev() { return link[0]; }
46  BLinkedListElement*& next() { return link[1]; }
47 };
48 
53 template<class T>
55  //BOOST_STATIC_ASSERT((boost::is_base_of<BLinkedListElement, T>::value));
56  //moved to LinkedList<T>
57 public:
60 
62  T* prev() const { return (T*)link[0]; }
64  T* next() const { return (T*)link[1]; }
65 
68  T* next(bool forward) { return (T*)link[(int)forward]; }
69 };
70 
71 class BLinkedList;
72 
76 class BLinkedList {
77 protected:
83  int _size;
85  bool _circular;
86 public:
91  BLinkedList(bool circular=false);
101  BLinkedList(BLinkedList&& that);
104  ~BLinkedList();
105 
107  bool empty() const;
109  int size() const;
110 
112  bool circular() const;
114  void setCircular(bool);
115 
127 
142 
159 
169  void clear();
170 
176  int concat(BLinkedList& that);
182  int swap(BLinkedList& that);
183 
184 protected:
190  BLinkedListElement* operator[] (int i) const;
191 private:
193  void dispose();
195  void releaseAll();
196  // shallow copies are not allowed
198  BLinkedList(const BLinkedList&) { throw "illegal"; }
200  BLinkedList& operator= (const BLinkedList&) { throw "illegal"; }
201 };
202 
251 template<class T>
252 class LinkedList : public BLinkedList {
253  BOOST_STATIC_ASSERT((boost::is_base_of<BLinkedListElement, T>::value));
254 public:
260 
267  template<typename Cloner>
268  LinkedList(const LinkedList& that, Cloner cloner) : BLinkedList(that.allocator)
269  {
270  for(T* p = that.first(); p; p = p->next())
271  insert_last(cloner(p));
272  }
273 
286  return *this;
287  }
288 
292  T* first() const { return (T*)_first; }
296  T* last() const { return (T*)_last; }
297 
298  T* remove(T* el) { return (T*)BLinkedList::remove(el); }
299 
305  T* operator[] (int i) const { return (T*) BLinkedList::operator[] (i); }
306 
312  void swap(LinkedList<T>& that) {
313  BLinkedList::swap(that);
314  }
315 };
316 
317 
318 /*
319 //namespace std {
320  template<typename T>
321  void swap(LinkedList<T>& a, LinkedList<T>& b) {
322  a.swap(b);
323  }
324 //}
325 
326 namespace std {
327  template<typename T>
328  void swap(LinkedList<T>& a, LinkedList<T>& b) {
329  a.swap(b);
330  }
331 }
332 */
333 
334 } } // namespace
335 
336 #endif // LINKEDLIST_H
abstract base class for LinkedList
Definition: linkedlist.h:76
BLinkedListElement *& prev()
Definition: linkedlist.h:44
BLinkedList(bool circular=false)
default constructor; creates an empty list
Definition: linkedlist.cpp:16
An intrusive double-linked list, similar to boost::intrusive.
Definition: linkedlist.h:252
void insert_after(BLinkedListElement *el, BLinkedListElement *after)
insert a new element after a certain element of the list; the list takes ownership of the element....
Definition: linkedlist.cpp:82
BLinkedListElement *& next()
Definition: linkedlist.h:46
void insert_last(BLinkedListElement *el)
insert a new element at the end of the list; the list takes ownership of the element....
Definition: linkedlist.cpp:52
LinkedList & operator=(LinkedList &&that)
move assigment operator
Definition: linkedlist.h:284
BLinkedListElement()
empty constructor
Definition: linkedlist.cpp:10
LinkedList(LinkedList &&that)
move constructor; takes ownership of another list
Definition: linkedlist.h:259
global definitions for all algorithms.
LinkedList(const LinkedList &that, Cloner cloner)
deep copy constructor
Definition: linkedlist.h:268
BLinkedListElement * operator[](int i) const
positional lookup (note: O(n), use with care)
Definition: linkedlist.cpp:183
int concat(BLinkedList &that)
append all elements of another list, taking ownership of the new elements
Definition: linkedlist.cpp:145
void insert_first(BLinkedListElement *el)
insert a new element at the beginning of the list; the list takes ownership of the element....
Definition: linkedlist.cpp:39
BLinkedListElement * remove(BLinkedListElement *el)
remove an element from the list and release its memory
Definition: linkedlist.cpp:115
bool _circular
if true, this is a circular list, i.e. the last element is connected to the first element
Definition: linkedlist.h:85
void setCircular(bool)
update the circularity property of this list
Definition: linkedlist.cpp:99
void swap(LinkedList< T > &that)
exchange all elements with another list, taking ownership of the new elements
Definition: linkedlist.h:312
void insert_before(BLinkedListElement *el, BLinkedListElement *before)
insert a new element before a certain element of the list; the list takes ownership of the element....
Definition: linkedlist.cpp:65
void dispose()
release all elements and update anchors
Definition: linkedlist.cpp:174
int swap(BLinkedList &that)
exchange all elements with another list, taking ownership of the new elements
Definition: linkedlist.cpp:165
T * operator[](int i) const
positional lookup (note: O(n), use with care)
Definition: linkedlist.h:305
base class for elements of a BLinkedList
Definition: linkedlist.h:23
BLinkedListElement * _last
the last element in the list (or nullptr)
Definition: linkedlist.h:81
void clear()
release all elements
Definition: linkedlist.cpp:138
BLinkedListElement * link[2]
double links (previous, next)
Definition: linkedlist.h:26
LinkedList()
empty constructor; creates an empty list
Definition: linkedlist.h:256
BLinkedList(const BLinkedList &)
copy constructor. do not use.
Definition: linkedlist.h:198
int _size
current number of elements
Definition: linkedlist.h:83
BLinkedListElement * _first
the first element in the list (or nullptr)
Definition: linkedlist.h:79
base template for elements of a LinkedList
Definition: linkedlist.h:54
LinkedListElement()
empty constructor
Definition: linkedlist.h:59
void releaseAll()
release all elements
Definition: linkedlist.cpp:207
~BLinkedList()
destructor; releases all element objects
Definition: linkedlist.cpp:29
BLinkedList & operator=(BLinkedList &&that)
move assigment operator
Definition: linkedlist.cpp:197
BOOST_STATIC_ASSERT((boost::is_base_of< BLinkedListElement, T >::value))