Line data Source code
1 : /* src/toolbox/ordered_list.hpp - ordered list
2 :
3 : Copyright (C) 1996-2013
4 : CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
5 :
6 : This file is part of CACAO.
7 :
8 : This program is free software; you can redistribute it and/or
9 : modify it under the terms of the GNU General Public License as
10 : published by the Free Software Foundation; either version 2, or (at
11 : your option) any later version.
12 :
13 : This program is distributed in the hope that it will be useful, but
14 : WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 : General Public License for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with this program; if not, write to the Free Software
20 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 : 02110-1301, USA.
22 :
23 : */
24 :
25 :
26 : #ifndef ORDEREDLIST_HPP_
27 : #define ORDEREDLIST_HPP_ 1
28 :
29 : #include <list>
30 : #include <algorithm>
31 :
32 : namespace cacao {
33 :
34 : // forward declaration
35 : template<class T, class Allocator, class intern_list>
36 : class _ordered_iterator;
37 : template<class T, class Allocator, class intern_list>
38 : class _ordered_const_iterator;
39 :
40 : /**
41 : * An ordered_list is an indexed sequence container. It shares most
42 : * characteristics with a std::list with the difference that its iterators are
43 : * more powerful. In addition the features of bidirectional iterators the total
44 : * ordering relation is supported (hence the name ordered_list).
45 : *
46 : * Like std::list it supports constant time insertion and removal of elements
47 : * anywhere. Additionally those operations do not invalidate iterators.
48 : *
49 : * ordered_list meets the requirement of Container, AllocatorAwareContainer,
50 : * SequenceContainer, ReversibleContainer.
51 : *
52 : * @todo not all methods are implemented yet!
53 : */
54 : template <class T,class Allocator = std::allocator<T> >
55 0 : class ordered_list {
56 : private:
57 : struct Entry;
58 : typedef std::list<Entry,typename Allocator::template rebind<Entry>::other> intern_list;
59 : typedef typename intern_list::iterator intern_iterator;
60 :
61 : /// tagged list entry
62 0 : struct Entry {
63 0 : Entry(T value, std::size_t index) : value(value), index(index) {}
64 : T value;
65 : std::size_t index;
66 : bool operator==(const Entry& other) const {
67 : return index == other.index && value == other.value;
68 : }
69 : };
70 : /// Inserter
71 : struct Inserter {
72 : intern_list &list;
73 : intern_iterator pos;
74 : std::size_t index;
75 0 : Inserter(intern_list &list, intern_iterator pos)
76 0 : : list(list), pos(pos), index(pos->index) {}
77 0 : void operator()(T& value) {
78 0 : list.insert(pos, Entry(value,index++));
79 0 : }
80 : };
81 : /// Increment function struct
82 : struct IncrementEntry {
83 0 : void operator()(Entry& E) {
84 0 : ++E.index;
85 0 : }
86 : };
87 : /// Increasing function struct
88 : struct IncreasingEntry {
89 : std::size_t index;
90 0 : IncreasingEntry(std::size_t index) : index(index) {}
91 0 : void operator()(Entry& E) {
92 0 : E.index = index++;
93 0 : }
94 : };
95 : /// Decrement function struct
96 : struct DecrementEntry {
97 : void operator()(Entry& E) {
98 : --E.index;
99 : }
100 : };
101 : /// internal storage
102 : intern_list list;
103 :
104 : public:
105 : typedef T value_type;
106 : typedef Allocator allocator_type;
107 : typedef typename allocator_type::reference reference;
108 : typedef typename allocator_type::const_reference const_reference;
109 : typedef typename allocator_type::pointer pointer;
110 : typedef typename allocator_type::const_pointer const_pointer;
111 : typedef _ordered_iterator<T, Allocator, intern_list > iterator;
112 : typedef _ordered_const_iterator<T, Allocator, intern_list > const_iterator;
113 : typedef std::reverse_iterator<iterator> reverse_iterator;
114 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
115 :
116 : /// construct an empty MachineBasicBlock
117 0 : ordered_list() {}
118 : /// copy constructor
119 : ordered_list(const ordered_list<T,Allocator> &other) : list(other.list) {}
120 : /// copy assignment operator
121 : ordered_list& operator=(const ordered_list<T,Allocator> &other);
122 : /// checks if the container has no elements.
123 : bool empty() const;
124 :
125 : /// returns the number of elements
126 : std::size_t size() const;
127 : /// returns the maximum possible number of elements
128 : std::size_t max_size() const;
129 : /// Appends the given element value to the end of the container.
130 : void push_back(const T& value);
131 : /// inserts value to the beginning
132 : void push_front(const T& value);
133 : /// inserts value before the element pointed to by pos
134 : iterator insert(iterator pos, const T& value);
135 : /// inserts elements from range [first, last) before the element pointed to by pos
136 : template<class InputIt>
137 : void insert(iterator pos, InputIt first, InputIt last);
138 : /// erases element
139 : iterator erase(iterator pos );
140 : /// erases elements
141 : iterator erase(iterator first, iterator last);
142 : /// returns an iterator to the beginning
143 : iterator begin();
144 : /// returns an iterator to the end
145 : iterator end();
146 : /// returns a const_iterator to the beginning
147 : const_iterator begin() const;
148 : /// returns a const_iterator to the end
149 : const_iterator end() const;
150 : /// returns a reverse iterator to the beginning
151 : reverse_iterator rbegin();
152 : /// returns a reverse iterator to the end
153 : reverse_iterator rend();
154 : /// returns a const reverse iterator to the beginning
155 : const_reverse_iterator rbegin() const;
156 : /// returns a const reverse iterator to the end
157 : const_reverse_iterator rend() const;
158 : /// access the first element
159 : const_reference front() const;
160 : /// access the last element
161 : const_reference back() const;
162 : /// access the first element
163 : reference front();
164 : /// access the last element
165 : reference back();
166 : /// removes all elements from the container
167 : void clear();
168 : /// exchanges the contents of the container with those of other
169 : void swap(ordered_list<T,Allocator> &other);
170 :
171 : // friends
172 : template<class _T,class _Allocator>
173 : friend bool operator==(const ordered_list<_T,_Allocator>& lhs,
174 : const ordered_list<_T,_Allocator>& rhs);
175 : template<class _T,class _Allocator>
176 : friend bool operator==(const typename ordered_list<_T,_Allocator>::Entry& lhs,
177 : const typename ordered_list<_T,_Allocator>::Entry& rhs);
178 :
179 : };
180 :
181 : /// equality
182 : template< class T, class Allocator>
183 : inline bool operator==(const ordered_list<T,Allocator>& lhs,
184 : const ordered_list<T,Allocator>& rhs) {
185 : return lhs.list == rhs.list;
186 : }
187 :
188 : /// inequality
189 : template< class T, class Allocator>
190 : inline bool operator!=(const ordered_list<T,Allocator>& lhs,
191 : const ordered_list<T,Allocator>& rhs) {
192 : return !(lhs == rhs);
193 : }
194 :
195 :
196 : /**
197 : * ordered iterator
198 : */
199 : template<class T, class Allocator, class intern_list>
200 : class _ordered_iterator : public std::iterator<std::bidirectional_iterator_tag,T> {
201 : public:
202 : typedef typename std::iterator<std::bidirectional_iterator_tag,T>
203 : ::reference reference;
204 : typedef typename std::iterator<std::bidirectional_iterator_tag,T>
205 : ::pointer pointer;
206 0 : _ordered_iterator() {}
207 0 : _ordered_iterator(typename intern_list::iterator it) : it(it) {}
208 0 : _ordered_iterator(const _ordered_iterator& other) : it(other.it) {}
209 0 : _ordered_iterator& operator++() {
210 0 : ++it;
211 0 : return *this;
212 : }
213 : _ordered_iterator operator++(int) {
214 : _ordered_iterator tmp(*this);
215 : operator++();
216 : return tmp;
217 : }
218 0 : _ordered_iterator& operator--() {
219 0 : --it;
220 0 : return *this;
221 : }
222 : _ordered_iterator operator--(int) {
223 : _ordered_iterator tmp(*this);
224 : operator--();
225 : return tmp;
226 : }
227 0 : bool operator==(const _ordered_iterator& rhs) const { return it == rhs.it; }
228 0 : bool operator!=(const _ordered_iterator& rhs) const { return it != rhs.it; }
229 0 : bool operator<( const _ordered_iterator& rhs) const { return it->index < rhs.it->index; }
230 : bool operator>( const _ordered_iterator& rhs) const { return rhs < *this; }
231 0 : reference operator*() { return it->value; }
232 0 : const reference operator*() const { return it->value; }
233 : pointer operator->() { return it->value; }
234 : const pointer operator->() const { return it->value; }
235 : private:
236 : typename intern_list::iterator it;
237 : friend class ordered_list<T,Allocator>;
238 : friend class _ordered_const_iterator<T,Allocator,intern_list>;
239 : };
240 :
241 : /**
242 : * ordered const_iterator
243 : */
244 : template<class T, class Allocator, class intern_list>
245 : class _ordered_const_iterator : public std::iterator<std::bidirectional_iterator_tag,const T> {
246 : public:
247 : typedef typename std::iterator<std::bidirectional_iterator_tag,const T>
248 : ::reference reference;
249 : typedef typename std::iterator<std::bidirectional_iterator_tag,const T>
250 : ::pointer pointer;
251 : _ordered_const_iterator() {}
252 0 : _ordered_const_iterator(typename intern_list::const_iterator it) : it(it) {}
253 0 : _ordered_const_iterator(const _ordered_const_iterator& other) : it(other.it) {}
254 : // convert from non const version
255 0 : _ordered_const_iterator(const _ordered_iterator<T,Allocator,
256 0 : intern_list>& other) : it(other.it) {}
257 0 : _ordered_const_iterator& operator++() {
258 0 : ++it;
259 0 : return *this;
260 : }
261 : _ordered_const_iterator operator++(int) {
262 : _ordered_const_iterator tmp(*this);
263 : operator++();
264 : return tmp;
265 : }
266 0 : _ordered_const_iterator& operator--() {
267 0 : --it;
268 0 : return *this;
269 : }
270 : _ordered_const_iterator operator--(int) {
271 : _ordered_const_iterator tmp(*this);
272 : operator--();
273 : return tmp;
274 : }
275 0 : bool operator==(const _ordered_const_iterator& rhs) const { return it == rhs.it; }
276 0 : bool operator!=(const _ordered_const_iterator& rhs) const { return it != rhs.it; }
277 : bool operator<( const _ordered_const_iterator& rhs) const { return it->index < rhs.it->index; }
278 : bool operator>( const _ordered_const_iterator& rhs) const { return rhs < *this; }
279 0 : reference operator*() { return it->value; }
280 : const reference operator*() const { return it->value; }
281 : pointer operator->() { return it->value; }
282 : const pointer operator->() const { return it->value; }
283 : private:
284 : typename intern_list::const_iterator it;
285 : friend class ordered_list<T,Allocator>;
286 : };
287 :
288 : // implementation
289 : template <class T, class Allocator>
290 : inline ordered_list<T,Allocator>&
291 : ordered_list<T,Allocator>::operator=(const ordered_list<T,Allocator> &other) {
292 : list = other.list;
293 : return *this;
294 : }
295 :
296 : template <class T, class Allocator>
297 0 : inline bool ordered_list<T, Allocator>::empty() const {
298 0 : return list.empty();
299 : }
300 :
301 : template <class T, class Allocator>
302 0 : inline std::size_t ordered_list<T, Allocator>::size() const {
303 0 : return list.size();
304 : }
305 :
306 : template <class T, class Allocator>
307 : inline std::size_t ordered_list<T, Allocator>::max_size() const {
308 : return list.max_size();
309 : }
310 :
311 : template <class T, class Allocator>
312 0 : inline void ordered_list<T, Allocator>::push_back(const T& value) {
313 0 : list.push_back(Entry(value,size()));
314 0 : }
315 :
316 : template <class T, class Allocator>
317 0 : inline void ordered_list<T, Allocator>::push_front(const T& value) {
318 0 : std::for_each(list.begin(),list.end(),IncrementEntry());
319 0 : list.push_front(Entry(value,0));
320 0 : }
321 :
322 : template <class T, class Allocator>
323 : inline typename ordered_list<T, Allocator>::iterator
324 0 : ordered_list<T, Allocator>::insert(typename ordered_list<T, Allocator>::iterator pos,
325 : const T& value) {
326 0 : typename intern_list::iterator it = list.insert(pos.it,Entry(value,pos.it->index));
327 0 : std::for_each(pos.it,list.end(),IncrementEntry());
328 0 : return iterator(it);
329 : }
330 :
331 : template <class T, class Allocator>
332 : template <class InputIt>
333 0 : inline void ordered_list<T, Allocator>::insert(
334 : typename ordered_list<T, Allocator>::iterator pos,
335 : InputIt first, InputIt last) {
336 0 : typename intern_list::iterator it = pos.it;
337 0 : std::for_each(first,last,Inserter(list,pos.it));
338 0 : std::for_each(it,list.end(),IncreasingEntry((--it)->index+1));
339 0 : }
340 :
341 : template <class T, class Allocator>
342 : inline typename ordered_list<T, Allocator>::iterator
343 : ordered_list<T, Allocator>::erase(
344 : typename ordered_list<T, Allocator>::iterator pos) {
345 : typename intern_list::iterator it = list.erase(pos.it);
346 : std::for_each(it,list.end(),DecrementEntry());
347 : return it;
348 : }
349 :
350 : template <class T, class Allocator>
351 : inline typename ordered_list<T, Allocator>::iterator
352 0 : ordered_list<T, Allocator>::erase(
353 : typename ordered_list<T, Allocator>::iterator first,
354 : typename ordered_list<T, Allocator>::iterator last) {
355 0 : std::size_t index = first.it->index;
356 0 : typename intern_list::iterator it = list.erase(first.it,last.it);
357 0 : std::for_each(it,list.end(),IncreasingEntry(index));
358 0 : return it;
359 : }
360 :
361 : template <class T, class Allocator>
362 0 : inline typename ordered_list<T, Allocator>::iterator ordered_list<T, Allocator>::begin() {
363 0 : return list.begin();
364 : }
365 :
366 : template <class T, class Allocator>
367 : inline typename ordered_list<T, Allocator>::const_iterator
368 0 : ordered_list<T, Allocator>::begin() const {
369 0 : return list.begin();
370 : }
371 :
372 : template <class T, class Allocator>
373 0 : inline typename ordered_list<T, Allocator>::iterator ordered_list<T, Allocator>::end() {
374 0 : return list.end();
375 : }
376 :
377 : template <class T, class Allocator>
378 : inline typename ordered_list<T, Allocator>::const_iterator
379 0 : ordered_list<T, Allocator>::end() const {
380 0 : return list.end();
381 : }
382 :
383 : template <class T, class Allocator>
384 : inline typename ordered_list<T, Allocator>::reverse_iterator
385 0 : ordered_list<T, Allocator>::rbegin() {
386 0 : return list.rbegin();
387 : }
388 :
389 : template <class T, class Allocator>
390 : inline typename ordered_list<T, Allocator>::reverse_iterator
391 0 : ordered_list<T, Allocator>::rend() {
392 0 : return list.rend();
393 : }
394 :
395 : template <class T, class Allocator>
396 : inline typename ordered_list<T, Allocator>::const_reverse_iterator
397 : ordered_list<T, Allocator>::rbegin() const {
398 : return list.rbegin();
399 : }
400 :
401 : template <class T, class Allocator>
402 : inline typename ordered_list<T, Allocator>::const_reverse_iterator
403 : ordered_list<T, Allocator>::rend() const {
404 : return list.rend();
405 : }
406 :
407 : template <class T, class Allocator>
408 : inline typename ordered_list<T, Allocator>::reference
409 0 : ordered_list<T, Allocator>::front() {
410 0 : return list.front().value;
411 : }
412 : template <class T, class Allocator>
413 : inline typename ordered_list<T, Allocator>::reference
414 0 : ordered_list<T, Allocator>::back() {
415 0 : return list.back().value;
416 : }
417 : template <class T, class Allocator>
418 : inline typename ordered_list<T, Allocator>::const_reference
419 : ordered_list<T, Allocator>::front() const {
420 : return list.front().value;
421 : }
422 : template <class T, class Allocator>
423 : inline typename ordered_list<T, Allocator>::const_reference
424 : ordered_list<T, Allocator>::back() const {
425 : return list.back().value;
426 : }
427 : template <class T, class Allocator>
428 : inline void ordered_list<T, Allocator>::clear() {
429 : return list.clear();
430 : }
431 :
432 : template <class T, class Allocator>
433 : inline void ordered_list<T, Allocator>::swap(ordered_list<T,Allocator> &other) {
434 : list.swap(other.list);
435 : }
436 :
437 : } // end namespace cacao
438 :
439 : #endif // ORDEREDLIST_HPP
440 :
441 :
442 : /*
443 : * These are local overrides for various environment variables in Emacs.
444 : * Please do not remove this and leave it at the end of the file, where
445 : * Emacs will automagically detect them.
446 : * ---------------------------------------------------------------------
447 : * Local variables:
448 : * mode: c++
449 : * indent-tabs-mode: t
450 : * c-basic-offset: 4
451 : * tab-width: 4
452 : * End:
453 : * vim:noexpandtab:sw=4:ts=4:
454 : */
|
