Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
linkedlist.cpp
Go to the documentation of this file.
1 
2 #include <linkedlist.h>
3 
4 #include <QtGlobal>
5 #include <data/linkedlist.h>
6 
7 using namespace frechet;
8 using namespace data;
9 
10 BLinkedListElement::BLinkedListElement() : link{nullptr,nullptr} { }
11 
12 #ifdef LINKED_LIST_VDESTRUCTOR
13 BLinkedListElement::~BLinkedListElement() { }
14 #endif
15 
17  : _first(0), _last(0),
18  _size(0), _circular(circular) {}
19 
21  : _first(that._first),
22  _last(that._last),
23  _size(that._size),
24  _circular(that._circular)
25 {
26  that.clear();
27 }
28 
30 
31 bool BLinkedList::empty() const {
32  Q_ASSERT((_first==0) == (_last==0));
33  Q_ASSERT((_first==0) == (_size==0));
34  return _first==0;
35 }
36 
37 int BLinkedList::size() const { return _size; }
38 
40 {
41  Q_ASSERT(el);
42 
43  el->prev() = nullptr;
44  el->next() = _first;
45  if (_first) _first->prev() = el;
46  _first = el;
47  if (!_last) _last = _first;
49  ++_size;
50 }
51 
53 {
54  Q_ASSERT(el);
55 
56  el->prev() = _last;
57  el->next() = nullptr;
58  if (_last) _last->next() = el;
59  _last = el;
60  if (!_first) _first = _last;
62  ++_size;
63 }
64 
66 {
67  Q_ASSERT(el);
68  Q_ASSERT(before);
69 
70  el->next() = before;
71  el->prev() = before->prev();
72  if (before->prev())
73  before->prev()->next() = el;
74  before->prev() = el;
75  if (before==_first) {
76  _first = el;
78  }
79  ++_size;
80 }
81 
83 {
84  Q_ASSERT(el);
85  Q_ASSERT(after);
86 
87  el->prev() = after;
88  el->next() = after->next();
89  if (after->next())
90  after->next()->prev() = el;
91  after->next() = el;
92  if (after==_last) {
93  _last = el;
95  }
96  ++_size;
97 }
98 
99 void BLinkedList::setCircular(bool circ)
100 {
101  if (_first) {
102  Q_ASSERT(_last);
103  if (circ) {
104  _first->prev()=_last;
105  _last->next()=_first;
106  }
107  else {
108  _first->prev()=nullptr;
109  _last->next()=nullptr;
110  }
111  }
112  _circular = circ;
113 }
114 
116 {
117  Q_ASSERT(el);
118 
119  BLinkedListElement* result = el->next();
120  if (el->next()) el->next()->prev() = el->prev();
121  if (el->prev()) el->prev()->next() = el->next();
122 
123  if (el==_first) {
124  _first = el->next();
126  }
127  if (el==_last) {
128  _last = el->prev();
130  }
131 
132  delete el;
133  --_size;
134  Q_ASSERT(_size >= 0);
135  return result;
136 }
137 
139 {
140  _first = _last = nullptr;
141  _size = 0;
142  _circular = false;
143 }
144 
146 {
147  // Don't mix lists with different allocators !!
148  if (empty())
149  return swap(that);
150 
151  _last->next() = that._first;
152  if (that._first) that._first->prev() = _last;
153 
154  _last = that._last;
155  _size += that._size;
156 
157  that._first = that._last = nullptr;
158  that._size = 0;
159  Q_ASSERT(that.empty());
160 
162  return _size;
163 }
164 
166 {
167  std::swap(_first,that._first);
168  std::swap(_last,that._last);
169  std::swap(_size,that._size);
171  return _size;
172 }
173 
175 {
176  if (empty()) return;
177 
178  setCircular(false);
179  releaseAll();
180  clear();
181 }
182 
184 {
185  BLinkedListElement* res;
186  if (i>=0) {
187  res=_first;
188  while(res && (i-- > 0)) res = res->next();
189  }
190  else {
191  res=_last;
192  while(res && (++i < 0)) res = res->prev();
193  }
194  return res;
195 }
196 
198  this->dispose();
199  this->_first = that._first;
200  this->_last = that._last;
201  this->_size = that._size;
202  this->_circular = that._circular;
203  that.clear();
204  return *this;
205 }
206 
208 {
210  BLinkedListElement *next;
211  while(obj) {
212  next = obj->next();
213  delete obj;
214  obj = next;
215  }
216 }
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
void swap(gpuword **A, gpuword **B)
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
BLinkedListElement()
empty constructor
Definition: linkedlist.cpp:10
global definitions for all algorithms.
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 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
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
int _size
current number of elements
Definition: linkedlist.h:83
BLinkedListElement * _first
the first element in the list (or nullptr)
Definition: linkedlist.h:79
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