MADARA  3.1.8
LQueue.h
Go to the documentation of this file.
1 /* -*- C++ -*- */
2 #ifndef _MADARA_LQUEUE_H
3 #define _MADARA_LQUEUE_H
4 
5 // This header defines "size_t"
6 #include <stdlib.h>
7 
8 #include <stdexcept>
9 
10 namespace madara
11 {
12  namespace utility
13  {
14  // Solve circular include problem via forward decls.
15  template <typename T>
16  class LQueueNode;
17 
18  template <typename T>
20 
21  template <typename T>
23 
37  template <class T>
38  class LQueue
39  {
40  friend class LQueueIterator<T>;
41  friend class LQueueConstIterator<T>;
42  public:
43  // Define a "trait"
44  typedef T value_type;
45 
51  class Underflow {};
52 
58  class Overflow {};
59 
61  LQueue (size_t size_hint = 0);
62 
64  LQueue (const LQueue<T> &rhs);
65 
67  LQueue<T> &operator = (const LQueue<T> &rhs);
68 
70  ~LQueue (void);
71 
72 
76  void enqueue (const T &new_item);
77 
80  T dequeue (void);
81 
84  T front (void) const;
85 
87  bool is_empty (void) const;
88 
90  bool is_full (void) const;
91 
93  size_t size (void) const;
94 
98  bool operator== (const LQueue<T> &rhs) const;
99 
103  bool operator!= (const LQueue<T> &s) const;
104 
107 
109  iterator begin (void);
110 
112  const_iterator begin (void) const;
113 
115  iterator end (void);
116 
118  const_iterator end (void) const;
119 
120  protected:
122  void dequeue_i (void);
123 
124  // Copy a linked list of nodes. This can throw a @a ::std::bad_alloc
125  // exception.
126  void copy_list (const LQueue<T> &rhs);
127 
128  // Delete a linked list of nodes.
129  void delete_list (void);
130 
131  private:
136 
138  size_t count_;
139 
140  };
141 
150  template <typename T>
151  class LQueueIterator
152  {
153  public:
155  LQueueIterator (LQueue<T> &queue,
156  size_t pos = 0);
157 
159  LQueueIterator (LQueue<T> &queue,
160  LQueueNode<T> *pos = 0);
161 
164  T& operator* (void);
165 
167  const T& operator* (void) const;
168 
171 
174 
176  bool operator== (const LQueueIterator<T> &rhs) const;
177 
179  bool operator!= (const LQueueIterator<T> &lhs) const;
180 
181  // = Necessary traits
182  typedef ::std::forward_iterator_tag iterator_category;
183  typedef T value_type;
184  typedef T *pointer;
185  typedef T &reference;
186  typedef int difference_type;
187 
188  private:
191 
192  // the position in the linked list
193  mutable LQueueNode<T> *pos_;
194  };
195 
204  template <typename T>
205  class LQueueConstIterator
206  {
207  public:
209  LQueueConstIterator (const LQueue<T> &queue,
210  size_t pos = 0);
211 
213  LQueueConstIterator (const LQueue<T> &queue,
214  LQueueNode<T> *pos);
215 
218  const T& operator* (void) const;
219 
221  const LQueueConstIterator<T> &operator++ (void) const;
222 
225 
227  bool operator== (const LQueueConstIterator<T> &rhs) const;
228 
230  bool operator!= (const LQueueConstIterator<T> &lhs) const;
231 
232  // = Necessary traits
233  typedef ::std::forward_iterator_tag iterator_category;
234  typedef T value_type;
235  typedef T *pointer;
236  typedef T &reference;
237  typedef int difference_type;
238 
239  private:
242 
243  // the position in the linked list
244  mutable LQueueNode<T> *pos_;
245  };
246  }
247 }
248 
249 #include "LQueue.cpp"
250 #endif /* _MADARA_LQUEUE_H */
void delete_list(void)
Definition: LQueue.cpp:253
Implements a forward iterator for LQueue type classes.
Definition: LQueue.h:19
~LQueue(void)
Perform actions needed when queue goes out of scope.
Definition: LQueue.cpp:285
void enqueue(const T &new_item)
Place a new_item at the tail of the queue.
Definition: LQueue.cpp:320
iterator end(void)
Get an iterator that points to the end of the queue.
Definition: LQueue.cpp:430
T front(void) const
Returns the front queue item without removing it.
Definition: LQueue.cpp:390
bool is_full(void) const
Returns 1 if the queue is full, otherwise returns 0.
Definition: LQueue.cpp:412
LQueue< T > & operator=(const LQueue< T > &rhs)
Assignment operator.
Definition: LQueue.cpp:266
LQueueConstIterator< T > const_iterator
Definition: LQueue.h:106
bool operator!=(const LQueue< T > &s) const
Compare this queue with rhs for inequality such that *this>!=s is always the complement of the boolea...
Definition: LQueue.cpp:310
Implements a forward iterator for LQueue type classes.
Definition: LQueue.h:22
iterator begin(void)
Get an iterator that points to the beginning of the queue.
Definition: LQueue.cpp:421
LQueueIterator< T > iterator
Definition: LQueue.h:105
LQueue< T > & queue_
the queue we are dealing with
Definition: LQueue.h:190
auto operator*(const Tracked< T > &lhs, const Tracked< U > &rhs) -> decltype(lhs.get()*rhs.get())
Definition: Tracked.h:276
void dequeue_i(void)
Remove the front item on the queue. Does not throw exceptions.
Definition: LQueue.cpp:370
::std::forward_iterator_tag iterator_category
Definition: LQueue.h:182
const LQueue< T > & queue_
the queue we are dealing with
Definition: LQueue.h:241
LQueueNode< T > * tail_
We only need to keep a single pointer for the circular linked list.
Definition: LQueue.h:135
void copy_list(const LQueue< T > &rhs)
Definition: LQueue.cpp:230
bool operator==(const LQueue< T > &rhs) const
Compare this queue with rhs for equality.
Definition: LQueue.cpp:298
::std::forward_iterator_tag iterator_category
Definition: LQueue.h:233
T dequeue(void)
Remove and return the front item on the queue.
Definition: LQueue.cpp:349
bool is_empty(void) const
Returns 1 if the queue is empty, otherwise returns 0.
Definition: LQueue.cpp:404
Defines a node in the LQueue that&#39;s implemented as a circular linked list.
Definition: LQueue.cpp:21
Provides utility functions and classes for common tasks and needs.
Definition: IteratorImpl.h:14
size_t size(void) const
Returns the current number of elements in the queue.
Definition: LQueue.cpp:185
Exception thrown by methods in this class when an underflow condition occurs.
Definition: LQueue.h:51
Exception thrown by methods in this class when an overflow condition occurs.
Definition: LQueue.h:58
Copyright (c) 2015 Carnegie Mellon University.
Defines a generic "first-in/first-out" (FIFO) Abstract Data Type (ADT) using a circular linked list...
Definition: LQueue.h:38
LQueueNode< T > * pos_
Definition: LQueue.h:193
LQueue(size_t size_hint=0)
Constructor.
Definition: LQueue.cpp:193
auto operator++(Tracked< T > &lhs) -> decltype(++lhs.get_mut())
Definition: Tracked.h:301
size_t count_
Number of items that are currently in the queue.
Definition: LQueue.h:138