Queue< T, ContainerType > 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.
T *	dequeue ()
	Removes the first element in the queue and returns it.
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.
void	insertFirst (T *item)
	Adds item to the beginning of the queue.
void	insertAfter (T *old_item, T *new_item)
	Inserts the element new_item directly after old_item.
T *	first ()
	Returns the first element in the queue without removing it.
T *	next (T *o)
	Returns the next element in the queue for a given element.

Private Member Functions
	Queue (const Queue< T, ContainerType > &)=delete
Queue &	operator= (const Queue< T, ContainerType > &)=delete

Private Attributes
T *	head
T **	tail

Detailed Description

template<typename T, template< typename V > class ContainerType>
class Queue< T, ContainerType >

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.

Constructor & Destructor Documentation

Queue() [1/2]

template<typename T , template< typename V > class ContainerType>

Queue< T, ContainerType >::Queue ( const Queue< T, ContainerType > &  )

privatedelete

Queue() [2/2]

template<typename T , template< typename V > class ContainerType>

Queue< T, ContainerType >::Queue ( )

inline

Default constructor; initialized the queue as empty.

Member Function Documentation

operator=()

template<typename T , template< typename V > class ContainerType>

Queue & Queue< T, ContainerType >::operator= ( const Queue< T, ContainerType > &  )

privatedelete

enqueue()

template<typename T , template< typename V > class ContainerType>

void Queue< T, ContainerType >::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 , template< typename V > class ContainerType>

T * Queue< T, ContainerType >::dequeue ( )

inline

Removes the first element in the queue and returns it.

Returns

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

begin()

template<typename T , template< typename V > class ContainerType>

Iterator Queue< T, ContainerType >::begin ( )

inline

Returns an iterator referring to the head of the queue.

end()

template<typename T , template< typename V > class ContainerType>

Iterator Queue< T, ContainerType >::end ( )

inline

Returns an end iterator.

remove()

template<typename T , template< typename V > class ContainerType>

T * Queue< T, ContainerType >::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 , template< typename V > class ContainerType>

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

inline

Adds item to the beginning of the queue.

Parameters

item	The element to be inserted.

insertAfter()

template<typename T , template< typename V > class ContainerType>

void Queue< T, ContainerType >::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 , template< typename V > class ContainerType>

T * Queue< T, ContainerType >::first ( )

inline

Returns the first element in the queue without removing it.

Returns

The first element in the queue

next()

template<typename T , template< typename V > class ContainerType>

T * Queue< T, ContainerType >::next ( T *  o )

inline

Returns the next element in the queue for a given element.

Member Data Documentation

head

template<typename T , template< typename V > class ContainerType>

T* Queue< T, ContainerType >::head

private

tail

template<typename T , template< typename V > class ContainerType>

T** Queue< T, ContainerType >::tail

private

---

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

• object/queue.h