linked list structure + users

2 files changed, 457 insertions, 0 deletions

diff --git a/src/structures/pl_list.hpp b/src/structures/pl_list.hpp
new file mode 100644
index 0000000..327e259
--- /dev/null
+++ b/src/structures/pl_list.hpp
@@ -0,0 +1,128 @@
+//          Copyright Jean Pierre Cimalando 2018.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef PL_LIST_HPP
+#define PL_LIST_HPP
+
+#include <iterator>
+#include <cstddef>
+
+/*
+  pl_cell: the linked list cell
+ */
+template <class T>
+struct pl_cell;
+
+template <class T>
+struct pl_basic_cell
+{
+    pl_cell<T> *prev, *next;
+};
+
+template <class T>
+struct pl_cell : pl_basic_cell<T>
+{
+    T value;
+};
+
+/*
+  pl_iterator: the linked list iterator
+ */
+template <class Cell>
+class pl_iterator
+{
+public:
+    typedef std::bidirectional_iterator_tag iterator_category;
+    typedef Cell value_type;
+    typedef Cell &reference;
+    typedef Cell *pointer;
+    typedef std::ptrdiff_t difference_type;
+
+    pl_iterator(Cell *cell = NULL);
+    bool is_end() const;
+    Cell &operator*() const;
+    Cell *operator->() const;
+    bool operator==(const pl_iterator &i) const;
+    bool operator!=(const pl_iterator &i) const;
+    pl_iterator &operator++();
+    pl_iterator operator++(int);
+    pl_iterator &operator--();
+    pl_iterator operator--(int);
+
+private:
+    Cell *cell_;
+};
+
+/*
+  pl_list: the preallocated linked list
+ */
+template <class T>
+class pl_list
+{
+public:
+    typedef pl_cell<T> value_type;
+    typedef value_type *pointer;
+    typedef value_type &reference;
+    typedef const value_type *const_pointer;
+    typedef const value_type &const_reference;
+    typedef pl_iterator< pl_cell<T> > iterator;
+    typedef pl_iterator< const pl_cell<T> > const_iterator;
+
+    pl_list(std::size_t capacity = 0);
+    ~pl_list();
+
+    pl_list(const pl_list &other);
+    pl_list &operator=(const pl_list &other);
+
+    std::size_t size() const;
+    std::size_t capacity() const;
+    bool empty() const;
+
+    iterator begin();
+    iterator end();
+    const_iterator begin() const;
+    const_iterator end() const;
+
+    void clear();
+
+    pl_cell<T> &front();
+    const pl_cell<T> &front() const;
+    pl_cell<T> &back();
+    const pl_cell<T> &back() const;
+
+    iterator insert(iterator pos, const T &x);
+    iterator erase(iterator pos);
+    void push_front(const T &x);
+    void push_back(const T &x);
+    void pop_front();
+    void pop_back();
+
+    iterator find(const T &x);
+    const_iterator find(const T &x) const;
+    template <class Pred> iterator find_if(const Pred &p);
+    template <class Pred> const_iterator find_if(const Pred &p) const;
+
+private:
+    // number of cells in the list
+    std::size_t size_;
+    // number of cells allocated
+    std::size_t capacity_;
+    // array of cells allocated
+    pl_cell<T> *cells_;
+    // pointer to the head cell
+    pl_cell<T> *first_;
+    // pointer to the next free cell
+    pl_cell<T> *free_;
+    // value-less cell which terminates the linked list
+    pl_basic_cell<T> endcell_;
+
+    void initialize(std::size_t capacity);
+    pl_cell<T> *allocate(pl_cell<T> *pos);
+    void deallocate(pl_cell<T> *cell);
+};
+
+#include "pl_list.tcc"
+
+#endif // PL_LIST_HPP
diff --git a/src/structures/pl_list.tcc b/src/structures/pl_list.tcc
new file mode 100644
index 0000000..37ccc75
--- /dev/null
+++ b/src/structures/pl_list.tcc
@@ -0,0 +1,329 @@
+//          Copyright Jean Pierre Cimalando 2018.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+#include "pl_list.hpp"
+
+template <class Cell>
+pl_iterator<Cell>::pl_iterator(Cell *cell)
+    : cell_(cell)
+{
+}
+
+template <class Cell>
+bool pl_iterator<Cell>::is_end() const
+{
+    return cell_->next == NULL;
+}
+
+template <class Cell>
+Cell &pl_iterator<Cell>::operator*() const
+{
+    return *cell_;
+}
+
+template <class Cell>
+Cell *pl_iterator<Cell>::operator->() const
+{
+    return cell_;
+}
+
+template <class T>
+bool pl_iterator<T>::operator==(const pl_iterator &i) const
+{
+    return cell_ == i.cell_;
+}
+
+template <class T>
+bool pl_iterator<T>::operator!=(const pl_iterator &i) const
+{
+    return cell_ != i.cell_;
+}
+
+template <class T>
+pl_iterator<T> &pl_iterator<T>::operator++()
+{
+    cell_ = cell_->next;
+    return *this;
+}
+
+template <class T>
+pl_iterator<T> pl_iterator<T>::operator++(int)
+{
+    pl_iterator i(cell_);
+    cell_ = cell_->next;
+    return i;
+}
+
+template <class T>
+pl_iterator<T> &pl_iterator<T>::operator--()
+{
+    cell_ = cell_->prev;
+    return *this;
+}
+
+template <class T>
+pl_iterator<T> pl_iterator<T>::operator--(int)
+{
+    pl_iterator i(cell_);
+    cell_ = cell_->prev;
+    return i;
+}
+
+template <class T>
+pl_list<T>::pl_list(std::size_t capacity)
+{
+    initialize(capacity);
+}
+
+template <class T>
+pl_list<T>::~pl_list()
+{
+    delete[] cells_;
+}
+
+template <class T>
+pl_list<T>::pl_list(const pl_list &other)
+{
+    initialize(other.capacity());
+    for(const_iterator i = other.end(), b = other.begin(); i-- != b;)
+        push_front(i->value);
+}
+
+template <class T>
+pl_list<T> &pl_list<T>::operator=(const pl_list &other)
+{
+    if(this != &other)
+    {
+        std::size_t size = other.size();
+        if(size <= capacity())
+            clear();
+        else
+        {
+            pl_cell<T> *oldcells = cells_;
+            initialize(other.capacity());
+            delete[] oldcells;
+        }
+        for(const_iterator i = other.end(), b = other.begin(); i-- != b;)
+            push_front(i->value);
+    }
+    return *this;
+}
+
+template <class T>
+std::size_t pl_list<T>::size() const
+{
+    return size_;
+}
+
+template <class T>
+std::size_t pl_list<T>::capacity() const
+{
+    return capacity_;
+}
+
+template <class T>
+bool pl_list<T>::empty() const
+{
+    return size_ == 0;
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::begin()
+{
+    return iterator(first_);
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::end()
+{
+    return iterator(reinterpret_cast<pl_cell<T> *>(&endcell_));
+}
+
+template <class T>
+typename pl_list<T>::const_iterator pl_list<T>::begin() const
+{
+    return const_iterator(first_);
+}
+
+template <class T>
+typename pl_list<T>::const_iterator pl_list<T>::end() const
+{
+    return const_iterator(reinterpret_cast<const pl_cell<T> *>(&endcell_));
+}
+
+template <class T>
+void pl_list<T>::clear()
+{
+    std::size_t capacity = capacity_;
+    pl_cell<T> *cells = cells_;
+    pl_cell<T> *endcell = &*end();
+    size_ = 0;
+    first_ = endcell;
+    free_ = cells;
+    endcell->prev = NULL;
+    for(std::size_t i = 0; i < capacity; ++i)
+    {
+        cells[i].prev = (i > 0) ? &cells[i - 1] : NULL;
+        cells[i].next = (i + 1 < capacity) ? &cells[i + 1] : NULL;
+        cells[i].value = T();
+    }
+}
+
+template <class T>
+pl_cell<T> &pl_list<T>::front()
+{
+    return *first_;
+}
+
+template <class T>
+const pl_cell<T> &pl_list<T>::front() const
+{
+    return *first_;
+}
+
+template <class T>
+pl_cell<T> &pl_list<T>::back()
+{
+    iterator i = end();
+    return *--i;
+}
+
+template <class T>
+const pl_cell<T> &pl_list<T>::back() const
+{
+    const_iterator i = end();
+    return *--i;
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::insert(iterator pos, const T &x)
+{
+    pl_cell<T> *cell = allocate(&*pos);
+    if (!cell)
+        throw std::bad_alloc();
+    cell->value = x;
+    return iterator(cell);
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::erase(iterator pos)
+{
+    deallocate(&*(pos++));
+    return pos;
+}
+
+template <class T>
+void pl_list<T>::push_front(const T &x)
+{
+    insert(begin(), x);
+}
+
+template <class T>
+void pl_list<T>::push_back(const T &x)
+{
+    insert(end(), x);
+}
+
+template <class T>
+void pl_list<T>::pop_front()
+{
+    deallocate(first_);
+}
+
+template <class T>
+void pl_list<T>::pop_back()
+{
+    iterator i(&*end());
+    deallocate(&*--i);
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::find(const T &x)
+{
+    const_iterator i = const_cast<const pl_list<T> *>(this)->find(x);
+    return iterator(&const_cast<reference>(*i));
+}
+
+template <class T>
+typename pl_list<T>::const_iterator pl_list<T>::find(const T &x) const
+{
+    const_iterator e = end();
+    for (const_iterator i = begin(); i != e; ++i)
+    {
+        if(i->value == x)
+            return i;
+    }
+    return e;
+}
+
+template <class T>
+template <class Pred>
+typename pl_list<T>::iterator pl_list<T>::find_if(const Pred &p)
+{
+    const_iterator i = const_cast<const pl_list<T> *>(this)->find_if(p);
+    return iterator(&const_cast<reference>(*i));
+}
+
+template <class T>
+template <class Pred>
+typename pl_list<T>::const_iterator pl_list<T>::find_if(const Pred &p) const
+{
+    const_iterator e = end();
+    for (const_iterator i = begin(); i != e; ++i)
+    {
+        if(p(i->value))
+            return i;
+    }
+    return e;
+}
+
+template <class T>
+void pl_list<T>::initialize(std::size_t capacity)
+{
+    cells_ = new pl_cell<T>[capacity];
+    capacity_ = capacity;
+    endcell_.next = NULL;
+    clear();
+}
+
+template <class T>
+pl_cell<T> *pl_list<T>::allocate(pl_cell<T> *pos)
+{
+    // remove free cells front
+    pl_cell<T> *cell = free_;
+    if(!cell)
+        return NULL;
+    free_ = cell->next;
+    if(free_)
+        free_->prev = NULL;
+
+    // insert at position
+    if (pos == first_)
+        first_ = cell;
+    cell->prev = pos->prev;
+    if (cell->prev)
+        cell->prev->next = cell;
+    cell->next = pos;
+    pos->prev = cell;
+
+    ++size_;
+    return cell;
+}
+
+template <class T>
+void pl_list<T>::deallocate(pl_cell<T> *cell)
+{
+    if(cell->prev)
+        cell->prev->next = cell->next;
+    if(cell->next)
+        cell->next->prev = cell->prev;
+    if(cell == first_)
+        first_ = cell->next;
+    cell->prev = NULL;
+    cell->next = free_;
+    cell->value = T();
+    free_ = cell;
+    --size_;
+}