ROSE  0.9.9.109
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://github.com/matzke1/sawyer.
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 
17 namespace Sawyer {
18 namespace Container {
19 
23 template<class T, class Cmp = std::less<T> >
24 class DistinctList {
25 public:
26  typedef T Item;
27  typedef Cmp Comparator;
28  typedef std::list<Item> Items; // iterators must be insert- and erase-stable
29 
30 private:
32  Items items_;
33  Map position_;
34 
35 public:
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
size_t position(const Item &item) const
Determine the position of an item.
Definition: DistinctList.h:87
bool exists(const Key &key) const
Determine if a key exists.
Definition: Sawyer/Map.h:377
bool exists(const Item &item) const
Determine if an item exists.
Definition: DistinctList.h:80
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:103
const Item & front() const
Reference to item at front of list.
Definition: DistinctList.h:103
bool isEmpty() const
Determines whether list is empty.
Definition: DistinctList.h:66
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:616
Name space for the entire library.
Definition: Access.h:11
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:137
DistinctList & operator=(const DistinctList< T2, Cmp2 > &other)
Assign one list to another.
Definition: DistinctList.h:48
bool isEmpty() const
Determines whether this container is empty.
Definition: Sawyer/Map.h:315
void erase(const Item &item)
Erase an item from the list.
Definition: DistinctList.h:170
const Items & items() const
Return all items as a list.
Definition: DistinctList.h:181
DistinctList(const DistinctList< T2, Cmp2 > &other)
Copy-construct a list.
Definition: DistinctList.h:41
void pushFront(const Item &item)
Insert item at front of list if distinct.
Definition: DistinctList.h:122
void pushBack(const Item &item)
Insert item at back of list if distinct.
Definition: DistinctList.h:133
Item popBack()
Return and erase item at back of list.
Definition: DistinctList.h:158
Item popFront()
Return and erase item at front of list.
Definition: DistinctList.h:145
Map & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:655
size_t size() const
Number of items in list.
Definition: DistinctList.h:73
DistinctList()
Construct an empty list.
Definition: DistinctList.h:37
Map & erase(const Key &key)
Remove a node with specified key.
Definition: Sawyer/Map.h:628
const Item & back() const
Reference to item at back of list.
Definition: DistinctList.h:113
NodeIterator find(const Key &key)
Find a node by key.
Definition: Sawyer/Map.h:364
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:530
A doubly-linked list of distinct items.
Definition: DistinctList.h:24
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: Sawyer/Map.h:271
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:322
void clear()
Clear the list.
Definition: DistinctList.h:58