linkedqueue.h

Go to the documentation of this file.

 
#ifndef SEMF_UTILS_CORE_QUEUES_LINKEDQUEUE_H_
#define SEMF_UTILS_CORE_QUEUES_LINKEDQUEUE_H_
 
#include <iterator>
#include <cstdint>
#include <cstddef>
#include <algorithm>
 
namespace semf
{
template <class T>
class LinkedQueue
{
public:
    class Node
    {
    public:
        virtual ~Node() = default;
 
        T* next() const
        {
            return m_next;
        }
        void setNext(T* next)
        {
            m_next = next;
        }
        bool isInQueue(LinkedQueue& queue)
        {
            Node* me = this;
            return queue.end() != std::find_if(queue.begin(), queue.end(), [&me](T& node) { return &node == me; });
        }
 
    private:
        T* m_next = nullptr;
    };
 
    class Iterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using refernce = T&;
 
        Iterator() = default;
        explicit Iterator(T* element)
        : m_node(element)
        {
        }
        virtual ~Iterator() = default;
 
        T& operator*() const
        {
            return *m_node;
        }
        T* operator->() const
        {
            return m_node;
        }
        Iterator& operator++()
        {
            m_node = m_node->LinkedQueue::Node::next();
            return *this;
        }
        Iterator operator++(int)
        {
            Iterator temp = *this;
            m_node = m_node->LinkedQueue::Node::next();
            return temp;
        }
        bool operator==(const Iterator& other) const
        {
            return m_node == other.m_node;
        }
        bool operator!=(const Iterator& other) const
        {
            return m_node != other.m_node;
        }
 
    private:
        T* m_node = nullptr;
    };
 
    class ConstIterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using refernce = T&;
 
        ConstIterator() = default;
        explicit ConstIterator(const T* element)
        : m_node(element)
        {
        }
        explicit ConstIterator(const Iterator& iterator)
        : m_node(iterator.m_node)
        {
        }
        virtual ~ConstIterator() = default;
 
        const T& operator*() const
        {
            return *m_node;
        }
        const T* operator->() const
        {
            return m_node;
        }
        ConstIterator& operator++()
        {
            m_node = m_node->LinkedQueue::Node::next();
            return *this;
        }
        ConstIterator operator++(int)
        {
            ConstIterator temp = *this;
            m_node = m_node->LinkedQueue::Node::next();
            return temp;
        }
        bool operator==(const ConstIterator& other) const
        {
            return m_node == other.m_node;
        }
        bool operator!=(const ConstIterator& other) const
        {
            return m_node != other.m_node;
        }
 
    private:
        const T* m_node = nullptr;
    };
 
    T& front();
    const T& front() const;
    T& back();
    const T& back() const;
    Iterator begin();
    ConstIterator begin() const;
    ConstIterator cbegin() const;
    Iterator end();
    ConstIterator end() const;
    ConstIterator cend() const;
    bool empty() const;
    size_t size() const;
    void push(T& element);
    void pop();
    LinkedQueue<T>& operator=(const LinkedQueue<T>& queue);
 
private:
    T* m_front = nullptr;
    T* m_back = nullptr;
    size_t m_size = 0;
};
 
template <class T>
T& LinkedQueue<T>::front()
{
    return *m_front;
}
 
template <class T>
const T& LinkedQueue<T>::front() const
{
    return *m_front;
}
 
template <class T>
T& LinkedQueue<T>::back()
{
    return *m_back;
}
 
template <class T>
const T& LinkedQueue<T>::back() const
{
    return *m_back;
}
 
template <class T>
typename LinkedQueue<T>::Iterator LinkedQueue<T>::begin()
{
    return Iterator(m_front);
}
 
template <class T>
typename LinkedQueue<T>::ConstIterator LinkedQueue<T>::begin() const
{
    return ConstIterator(m_front);
}
 
template <class T>
typename LinkedQueue<T>::ConstIterator LinkedQueue<T>::cbegin() const
{
    return ConstIterator(m_front);
}
 
template <class T>
typename LinkedQueue<T>::Iterator LinkedQueue<T>::end()
{
    return Iterator(nullptr);
}
 
template <class T>
typename LinkedQueue<T>::ConstIterator LinkedQueue<T>::end() const
{
    return ConstIterator(nullptr);
}
 
template <class T>
typename LinkedQueue<T>::ConstIterator LinkedQueue<T>::cend() const
{
    return ConstIterator(nullptr);
}
 
template <class T>
bool LinkedQueue<T>::empty() const
{
    return m_size == 0;
}
 
template <class T>
size_t LinkedQueue<T>::size() const
{
    return m_size;
}
 
template <class T>
void LinkedQueue<T>::push(T& element)
{
    element.LinkedQueue::Node::setNext(nullptr);
    if (m_size > 1)
    {
        m_back->LinkedQueue::Node::setNext(&element);
        m_back = &element;
    }
    else if (m_size == 1)
    {
        m_front->LinkedQueue::Node::setNext(&element);
        m_back = &element;
    }
    else  // m_size == 0
    {
        m_front = &element;
        m_back = &element;
    }
    m_size++;
}
 
template <class T>
void LinkedQueue<T>::pop()
{
    if (m_size == 1)
    {
        m_front = nullptr;
        m_back = nullptr;
        m_size--;
    }
    else
    {
        m_front = m_front->LinkedQueue::Node::next();
        m_size--;
    }
}
 
template <class T>
LinkedQueue<T>& LinkedQueue<T>::operator=(const LinkedQueue<T>& queue)
{
    this->m_front = queue.m_front;
    this->m_back = queue.m_back;
    this->m_size = queue.m_size;
    return *this;
}
} /* namespace semf */
#endif /* SEMF_UTILS_CORE_QUEUES_LINKEDQUEUE_H_ */