Queue< T > Class Template Reference

This class implements a simple, singly-linked list of objects implementing the base class Queue::Node. More...

#include <object/queue.h>

Classes
class	Iterator
	A Queue Iterator. More...
class	Node
	Base class Node for all queueable classes. More...

Public Member Functions
	Queue ()
	Default constructor; initialized the queue as empty.
void	enqueue (T *item)
	Enqueues the provided item at the end of the queue. More...
T *	dequeue ()
	Removes the first element in the queue and returns it. More...
Iterator	begin ()
Iterator	end ()
T *	remove (T *item, bool(*cmp)(T *, T *)=[](T *a, T *b) {return a==b;})
	Removes and returns a single element from the queue. More...
void	insertFirst (T *item)
	Adds item to the beginning of the queue. More...
void	insertAfter (T *old_item, T *new_item)
	Inserts the element new_item directly after old_item. More...
T *	first ()
	Returns the first element in the queue without removing it. More...
T *	next (T *o)
	Returns the next element in the queue for a given element.

Detailed Description

template<typename T>
class Queue< T >

This class implements a simple, singly-linked list of objects implementing the base class Queue::Node.

Queue::Node itself merely adds an attribute _next_node to the parent object, allowing to enqueue the element into a single Queue.

Warning

One instance of a class inheriting from Queue::Node can be at most in one Queue

The following example illustrates the usage of Queue::Node :

class Foo : public Queue<Foo>::Node {
  // ...
}

This Queue implementation supports using C++11 range expressions:

Queue<Foo> list;
Foo a, b, c;

list.enqueue(&a);
list.enqueue(&b);
list.enqueue(&c);

for(Foo * elem : list) {
  // use elem
}

Note

Implementation details: Unlike in other implementations, the tail pointer does not point to the last element in the queue, but to the last element's next pointer. As long as the queue is empty, tail points to the queue's head pointer; therefore inserting can be implemented without further special cases handling empty queues. The check for emptiness can, however, not be omitted on removal.

Member Function Documentation

enqueue()

template<typename T >

void Queue< T >::enqueue ( T *  item )

inline

Enqueues the provided item at the end of the queue.

Parameters

item	Queue element to be appended.

dequeue()

template<typename T >

T * Queue< T >::dequeue ( )

inline

Removes the first element in the queue and returns it.

Returns

The removed head, or 0 if the queue was empty.

begin()

template<typename T >

Iterator Queue< T >::begin ( )

inline

Returns an iterator referring to the head of the queue.

end()

template<typename T >

Iterator Queue< T >::end ( )

inline

Returns an end iterator.

remove()

template<typename T >

T * Queue< T >::remove ( T *  item, bool(*)(T *, T *)  cmp = [] (T* a, T* b) {return a == b;}  )

inline

Removes and returns a single element from the queue.

This method removes and returns a single element (provided via parameter item) from the queue, irrespective of its position. By default, this function compares pointers; it is possible to override the default comparator lambda function by specifying a function type as second parameter.

Parameters

item	Element to be removed.
cmp	Comparator function.

Returns

Returns the removed element, or 0 if no element matches.

insertFirst()

template<typename T >

void Queue< T >::insertFirst ( T *  item )

inline

Adds item to the beginning of the queue.

Parameters

item	The element to be inserted.

insertAfter()

template<typename T >

void Queue< T >::insertAfter ( T *  old_item, T *  new_item  )

inline

Inserts the element new_item directly after old_item.

Parameters

old_item	Element to insert after.
new_item	Element to be inserted.

first()

template<typename T >

T * Queue< T >::first ( )

inline

Returns the first element in the queue without removing it.

Returns

The first element in the queue

---

The documentation for this class was generated from the following file:

• object/queue.h