ROSE 0.11.145.147
DistinctList.h
1// WARNING: Changes to this file must be contributed back to Sawyer or else they will
2// be clobbered by the next update from Sawyer. The Sawyer repository is at
3// https://gitlab.com/charger7534/sawyer.git.
4
5
6
7
8#ifndef Sawyer_DistinctList_H
9#define Sawyer_DistinctList_H
10
11#include <boost/foreach.hpp>
12#include <list>
13#include <Sawyer/Map.h>
14#include <Sawyer/Sawyer.h>
15#include <stdexcept>
16
17namespace Sawyer {
18namespace Container {
19
23template<class T, class Cmp = std::less<T> >
25public:
26 typedef T Item;
27 typedef Cmp Comparator;
28 typedef std::list<Item> Items; // iterators must be insert- and erase-stable
29
30private:
32 Items items_;
33 Map position_;
34
35public:
38
40 template<class T2, class Cmp2>
42 BOOST_FOREACH (const T2 &item, other.items())
43 pushBack(item);
44 }
45
47 template<class T2, class Cmp2>
49 clear();
50 BOOST_FOREACH (const T2 &item, other.items())
51 pushBack(item);
52 return *this;
53 }
54
58 void clear() {
59 items_.clear();
60 position_.clear();
61 }
62
66 bool isEmpty() const {
67 return position_.isEmpty();
68 }
69
73 size_t size() const {
74 return position_.size();
75 }
76
80 bool exists(const Item &item) const {
81 return position_.exists(item);
82 }
83
87 size_t position(const Item &item) const {
88 if (!position_.exists(item))
89 return size();
90 size_t retval = 0;
91 BOOST_FOREACH (const Item &x, items_) {
92 if (x == item)
93 return retval;
94 ++retval;
95 }
96 return retval;
97 }
98
103 const Item& front() const {
104 if (isEmpty())
105 throw std::runtime_error("front called on empty list");
106 return items_.front();
107 }
108
113 const Item& back() const {
114 if (isEmpty())
115 throw std::runtime_error("back called on empty list");
116 return items_.back();
117 }
118
122 void pushFront(const Item &item) {
123 typename Map::NodeIterator found = position_.find(item);
124 if (found == position_.nodes().end()) {
125 items_.push_front(item);
126 position_.insert(item, items_.begin());
127 }
128 }
129
133 void pushBack(const Item &item) {
134 typename Map::NodeIterator found = position_.find(item);
135 if (found == position_.nodes().end()) {
136 items_.push_back(item);
137 position_.insert(item, --items_.end());
138 }
139 }
140
145 Item popFront() {
146 if (isEmpty())
147 throw std::runtime_error("popFront called on empty list");
148 Item item = items_.front();
149 items_.pop_front();
150 position_.erase(item);
151 return item;
152 }
153
158 Item popBack() {
159 if (isEmpty())
160 throw std::runtime_error("popBack called on empty list");
161 Item item = items_.back();
162 items_.pop_back();
163 position_.erase(item);
164 return item;
165 }
166
170 void erase(const Item &item) {
171 typename Map::NodeIterator found = position_.find(item);
172 if (found != position_.nodes().end()) {
173 items_.erase(found->value());
174 position_.eraseAt(found);
175 }
176 }
177
181 const Items& items() const {
182 return items_;
183 }
184};
185
186} // namespace
187} // namespace
188
189#endif
A doubly-linked list of distinct items.
size_t position(const Item &item) const
Determine the position of an item.
DistinctList & operator=(const DistinctList< T2, Cmp2 > &other)
Assign one list to another.
void clear()
Clear the list.
DistinctList(const DistinctList< T2, Cmp2 > &other)
Copy-construct a list.
const Items & items() const
Return all items as a list.
void pushBack(const Item &item)
Insert item at back of list if distinct.
Item popFront()
Return and erase item at front of list.
size_t size() const
Number of items in list.
DistinctList()
Construct an empty list.
bool exists(const Item &item) const
Determine if an item exists.
bool isEmpty() const
Determines whether list is empty.
const Item & back() const
Reference to item at back of list.
Item popBack()
Return and erase item at back of list.
void pushFront(const Item &item)
Insert item at front of list if distinct.
void erase(const Item &item)
Erase an item from the list.
const Item & front() const
Reference to item at front of list.
Bidirectional iterator over key/value nodes.
Definition Sawyer/Map.h:187
Value & value()
Value part of key/value node.
Definition Sawyer/Map.h:123
Container associating values with keys.
Definition Sawyer/Map.h:72
NodeIterator find(const Key &key)
Find a node by key.
Definition Sawyer/Map.h:480
Map & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition Sawyer/Map.h:771
bool exists(const Key &key) const
Determine if a key exists.
Definition Sawyer/Map.h:493
size_t size() const
Number of nodes, keys, or values in this container.
Definition Sawyer/Map.h:438
bool isEmpty() const
Determines whether this container is empty.
Definition Sawyer/Map.h:431
Map & erase(const Key &key)
Remove a node with specified key.
Definition Sawyer/Map.h:744
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition Sawyer/Map.h:387
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition Sawyer/Map.h:646
Map & clear()
Remove all nodes.
Definition Sawyer/Map.h:732
Sawyer support library.