linkedlist.h

Go to the documentation of this file.

 
#ifndef SEMF_UTILS_CORE_LISTS_LINKEDLIST_H_
#define SEMF_UTILS_CORE_LISTS_LINKEDLIST_H_
 
#include <iterator>
#include <cstdint>
#include <cstddef>
 
namespace semf
{
template <class T>
class LinkedList
{
public:
    class Node
    {
    public:
        virtual ~Node() = default;
 
        T* next() const
        {
            return m_next;
        }
        void setNext(T* next)
        {
            m_next = next;
        }
        T* previous() const
        {
            return m_previous;
        }
        void setPrevious(T* previous)
        {
            m_previous = previous;
        }
        bool isInAList()
        {
            if (m_previous != nullptr || m_next != nullptr)
                return true;
            else
                return false;
        }
 
    private:
        T* m_next = nullptr;
        T* m_previous = nullptr;
    };
 
    class Iterator
    {
    public:
        using iterator_category = std::bidirectional_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->LinkedList::Node::next();
            return *this;
        }
        Iterator operator++(int)
        {
            Iterator temp = *this;
            m_node = m_node->LinkedList::Node::next();
            return temp;
        }
        Iterator& operator--()
        {
            m_node = m_node->LinkedList::Node::previous();
            return *this;
        }
        Iterator operator--(int)
        {
            Iterator temp = *this;
            temp.m_node = temp.m_node->LinkedList::Node::previous();
            return temp;
        }
        bool operator==(const Iterator& that) const
        {
            return m_node == that.m_node;
        }
        bool operator!=(const Iterator& that) const
        {
            return m_node != that.m_node;
        }
 
    private:
        T* m_node = nullptr;
    };
 
    class ConstIterator
    {
    public:
        using iterator_category = std::bidirectional_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->LinkedList::Node::next();
            return *this;
        }
        ConstIterator operator++(int)
        {
            ConstIterator temp = *this;
            m_node = m_node->LinkedList::Node::next();
            return temp;
        }
        ConstIterator& operator--()
        {
            m_node = m_node->LinkedList::Node::previous();
            return *this;
        }
        ConstIterator operator--(int)
        {
            ConstIterator temp = *this;
            m_node = m_node->LinkedList::Node::previous();
            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;
    };
    LinkedList();
    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 clear();
    Iterator insert(Iterator position, T& element);
    Iterator erase(Iterator position);
    Iterator erase(Iterator first, Iterator last);
    void pushBack(T& element);
    void pushFront(T& element);
    void popBack();
    void popFront();
    LinkedList<T>& operator=(const LinkedList<T>& list);
 
private:
    void pushEmpty(T& element);
    T* m_front = nullptr;
    Node m_end;
    size_t m_size = 0;
};
 
template <class T>
LinkedList<T>::LinkedList()
{
    clear();
}
 
template <class T>
T& LinkedList<T>::front()
{
    return *m_front;
}
 
template <class T>
const T& LinkedList<T>::front() const
{
    return *m_front;
}
 
template <class T>
T& LinkedList<T>::back()
{
    return *m_end.previous();
}
 
template <class T>
const T& LinkedList<T>::back() const
{
    return *m_end.previous();
}
 
template <class T>
typename LinkedList<T>::Iterator LinkedList<T>::begin()
{
    return m_front ? Iterator(m_front) : end();
}
 
template <class T>
typename LinkedList<T>::ConstIterator LinkedList<T>::begin() const
{
    return m_front ? ConstIterator(m_front) : end();
}
 
template <class T>
typename LinkedList<T>::ConstIterator LinkedList<T>::cbegin() const
{
    return m_front ? ConstIterator(m_front) : cend();
}
 
template <class T>
typename LinkedList<T>::Iterator LinkedList<T>::end()
{
    return Iterator(reinterpret_cast<T*>(&m_end));
}
 
template <class T>
typename LinkedList<T>::ConstIterator LinkedList<T>::end() const
{
    return ConstIterator(reinterpret_cast<const T*>(&m_end));
}
 
template <class T>
typename LinkedList<T>::ConstIterator LinkedList<T>::cend() const
{
    return ConstIterator(reinterpret_cast<const T*>(&m_end));
}
 
template <class T>
bool LinkedList<T>::empty() const
{
    return m_size == 0;
}
 
template <class T>
size_t LinkedList<T>::size() const
{
    return m_size;
}
 
template <class T>
void LinkedList<T>::clear()
{
    m_front = nullptr;
    m_end.setPrevious(m_front);
    m_size = 0;
}
 
template <class T>
typename LinkedList<T>::Iterator LinkedList<T>::insert(Iterator position, T& element)
{
    Iterator ret = position;
    if (&(*position) == m_front)
    {
        pushFront(element);
        ret = Iterator(m_front);
    }
    else if (m_size == 0)
    {
        m_front = &element;
        m_end.setPrevious(&element);
        m_size++;
        ret = Iterator(m_front);
    }
    else
    {
        T* nex = &(*position);
        nex->LinkedList::Node::setPrevious(&element);
        T* pre = &(*position--);
        pre->LinkedList::Node::setNext(&element);
    }
    return ret;
}
 
template <class T>
typename LinkedList<T>::Iterator LinkedList<T>::erase(Iterator position)
{
    if (&(*position) == m_front)
    {
        popFront();
        return begin();
    }
    else if (&(*position) == m_end.previous())
    {
        popBack();
        return end();
    }
    else if (m_size > 0)
    {
        T* pre = (&(*position))->LinkedList::Node::previous();
        T* nex = (&(*position))->LinkedList::Node::next();
        pre->LinkedList::Node::setNext(nex);
        nex->LinkedList::Node::setPrevious(pre);
        m_size--;
        return ++position;
    }
    return Iterator();
}
 
template <class T>
typename LinkedList<T>::Iterator LinkedList<T>::erase(Iterator first, Iterator last)
{
    while (first != last)
    {
        first = erase(first);
    }
    return erase(first);
}
 
template <class T>
void LinkedList<T>::pushBack(T& element)
{
    element.LinkedList::Node::setNext(nullptr);
 
    if (m_size >= 1)
    {
        back().LinkedList::Node::setNext(&element);
        element.LinkedList::Node::setPrevious(m_end.previous());
        element.LinkedList::Node::setNext(reinterpret_cast<T*>(&m_end));
        m_end.setPrevious(&element);
    }
    else  // m_size == 0
    {
        pushEmpty(element);
    }
    m_size++;
}
 
template <class T>
void LinkedList<T>::pushFront(T& element)
{
    element.LinkedList::Node::setPrevious(nullptr);
    if (m_size >= 1)
    {
        element.LinkedList::Node::setNext(m_front);
        m_front->LinkedList::Node::setPrevious(element);
        m_front = &element;
    }
    else  // m_size == 0
    {
        pushEmpty(element);
    }
    m_size++;
}
 
template <class T>
void LinkedList<T>::popBack()
{
    if (m_size == 1)
    {
        clear();
    }
    else if (m_size > 1)
    {
        Iterator newPrev = (end()--)--;
        m_end.setPrevious(&(*newPrev));
        newPrev->LinkedList::Node::setNext(reinterpret_cast<T*>(&m_end));
        m_size--;
    }
}
 
template <class T>
void LinkedList<T>::popFront()
{
    if (m_size == 1)
    {
        clear();
    }
    else
    {
        m_front = m_front->LinkedList::Node::next();
        m_size--;
    }
}
 
template <class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& list)
{
    this->m_front = list.m_front;
    this->m_end = list.m_end;
    this->m_size = list.m_size;
    return *this;
}
template <class T>
void semf::LinkedList<T>::pushEmpty(T& element)
{
    element.LinkedList::Node::setPrevious(nullptr);
    element.LinkedList::Node::setNext(reinterpret_cast<T*>(&m_end));
    m_end.setPrevious(&element);
    m_front = &element;
}
} /* namespace semf */
#endif /* SEMF_UTILS_CORE_LISTS_LINKEDLIST_H_ */