StuBS
Loading...
Searching...
No Matches
Queue< T > Class Template Reference

Templated Queue for arbitrary objects. More...

#include <queue.h>

Classes

class  Iterator
 Minimal forward iterator You can use this iterator to iterate the queue like a normal STL container. It only supports forward iteration, since the queue is single linked. More...
 

Public Member Functions

 Queue (unsigned link_index, NextFunc get_link=default_get_link)
 Constructor.
 
bool enqueue (T &item)
 Enqueues the provided item at the end of the queue. If the element is already contained in the queue, false will be returned.
 
bool insertFirst (T &item)
 insert a new element at the start of the queue
 
bool insertAfter (T &after, T &item)
 Insert a new element item into the list after an element after. Returns false if item is already in the/a list or after is not in this list.
 
T * next (T &item)
 return the next element of a given one or nullptr if the end is reached
 
bool is_empty ()
 Return whether or not the queue is empty.
 
T * dequeue ()
 Removes the first element in the queue and returns it.
 
T * remove (T *that)
 Removes a given element from the queue and returns that element, or nullptr if it was not present.
 
Queue< T >::Iterator begin ()
 get an iterator to the first element
 
Queue< T >::Iterator end ()
 get an iterator that marks the end of list
 
T * first ()
 get the first element of the queue
 
T * last ()
 get the last element of the queue
 

Private Types

typedef T **(* NextFunc) (T &, unsigned)
 Type definition for the get_link function.
 

Static Private Member Functions

static T ** default_get_link (T &obj, unsigned link_index)
 Default get_link implementation returns a pointer to the link_index'th element of the next-pointer array. The function assumes a member named "queue_link" that stores the next-pointer.
 

Private Attributes

unsigned link_index
 Queue-local index into the next-pointer array.
 
const NextFunc get_link
 
T * head
 
T * tail
 

Detailed Description

template<class T>
class Queue< T >

Templated Queue for arbitrary objects.

Queue is implemented by a head-object (Queue<T>) and next-pointers embedded in the queued objects. This Queue supports arrays of next-pointers by passing an index into the constructor identifying the index into the next-pointer array. By passing a different get_link function into the constructor, the member name of the next-pointer array can be changed and objects can be contained in different independent queues.

Constructor & Destructor Documentation

◆ Queue()

template<class T >
Queue< T >::Queue ( unsigned link_index,
NextFunc get_link = default_get_link )
inlineexplicit

Constructor.

Parameters
[in]link_indexdenotes the index into the next-pointer array to be used by this queue-object
[in]get_linkA function pointer to the get_link, i.e. a function which returns a pointer to the next-pointer of an element in the Queue.

Member Function Documentation

◆ default_get_link()

template<class T >
static T ** Queue< T >::default_get_link ( T & obj,
unsigned link_index )
inlinestaticprivate

Default get_link implementation returns a pointer to the link_index'th element of the next-pointer array. The function assumes a member named "queue_link" that stores the next-pointer.

If your object contains a queue_link member you can just ignore this function and the get_link keyword argument of the constructor.

Parameters
[in]objthe object whose link should be accessed.
[in]link_indexthe index within the array.
Returns
A pointer to the next-object pointer.

◆ dequeue()

template<class T >
T * Queue< T >::dequeue ( )
inline

Removes the first element in the queue and returns it.

Note
Does not update the tail-pointer
Returns
Pointer to the removed item or nullptr if the queue was empty.

◆ enqueue()

template<class T >
bool Queue< T >::enqueue ( T & item)
inline

Enqueues the provided item at the end of the queue. If the element is already contained in the queue, false will be returned.

Parameters
[in]itemelement to be appended (enqueued).
Returns
false if the element already was enqueued (and nothing was done) or not (and it is now enqueued, then true)

◆ insertAfter()

template<class T >
bool Queue< T >::insertAfter ( T & after,
T & item )
inline

Insert a new element item into the list after an element after. Returns false if item is already in the/a list or after is not in this list.

Parameters
[in]afterthe element after which the new one should be inserted
[in]itemthe new element to add
Returns
true if successful, false if item was in the list or after was not

◆ insertFirst()

template<class T >
bool Queue< T >::insertFirst ( T & item)
inline

insert a new element at the start of the queue

Parameters
[in]itemthe new item to add
Returns
true if successful, false if item was already in the queue

◆ is_empty()

template<class T >
bool Queue< T >::is_empty ( )
inline

Return whether or not the queue is empty.

Returns
True if the queue is empty or false otherwise.

◆ next()

template<class T >
T * Queue< T >::next ( T & item)
inline

return the next element of a given one or nullptr if the end is reached

Parameters
[in]itemthe current item
Returns
the next element or nullptr if the end is reached or the item is not in this list

◆ remove()

template<class T >
T * Queue< T >::remove ( T * that)
inline

Removes a given element from the queue and returns that element, or nullptr if it was not present.

Returns
pointer to the removed element, or nullptr if not present

Member Data Documentation

◆ get_link

template<class T >
const NextFunc Queue< T >::get_link
private

Function pointer to the get_link function, called whenever the next pointer array is referenced

◆ head

template<class T >
T* Queue< T >::head
private

head points to the first element (the one returned on first dequeue). Can be nullptr if the queue is empty.

◆ tail

template<class T >
T* Queue< T >::tail
private

tail points to the last element (the one last added). Is only valid if head != nullptr


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