libs: move stack to kstd

1 files changed, 213 insertions, 0 deletions

diff --git a/libs/kstd/include/kstd/stack.hpp b/libs/kstd/include/kstd/stack.hpp
new file mode 100644
index 0000000..8c702cf
--- /dev/null
+++ b/libs/kstd/include/kstd/stack.hpp
@@ -0,0 +1,213 @@
+#ifndef KSTD_STACK_HPP
+#define KSTD_STACK_HPP
+
+#include "kstd/vector.hpp"
+
+#include <utility>
+
+namespace kstd
+{
+  /**
+   * @brief Custom stack implementation mirroring the std::stack to allow for the usage of STL functionality with our
+   * custom memory management.
+   *
+   * @tparam T Element the stack instance should contain.
+   * @tparam Container Actual underlying container that should be wrapped to provide stack functionality. Requires
+   * access to pop_back(), push_back(), back(), size(), empty() and emplace_back()
+   */
+  template<typename T, typename Container = kstd::vector<T>>
+  struct stack
+  {
+    using container_type = Container;  ///< Type of the underlying container used to implement stack-like interface.
+    using value_type = Container::value_type;  ///< Type of the elements contained in the underlying container.
+    using size_type = Container::size_type;    ///< Type of the size in the underlying container.
+    using reference = Container::reference;    ///< Type of reference to the elements.
+    using const_reference = Container::const_reference;  ///< Type of constant reference to the elements.
+
+    /**
+     * @brief Default Constructor.
+     */
+    stack() = default;
+
+    /**
+     * @brief Constructs data with the given amount of elements containg the given value or alterantively the default
+     * constructed value.
+     *
+     * @param n Amount of elements we want to create and set the given value for.
+     * @param initial Inital value of all elements in the underlying data array.
+     */
+    [[gnu::section(".stl_text")]]
+    explicit stack(size_type n, value_type initial = value_type{})
+        : _container(n, initial)
+    {
+      // Nothing to do.
+    }
+
+    /**
+     * @brief Constructs data by copying all element from the given exclusive range.
+     *
+     * @tparam InputIterator Template that should have atleast input iterator characteristics.
+     * @param first Input iterator to the first element in the range we want to copy from.
+     * @param last Input iterator to one past the last element in the range we want to copy from.
+     */
+    template<typename InputIterator>
+    [[gnu::section(".stl_text")]]
+    explicit stack(InputIterator first, InputIterator last)
+        : _container(first, last)
+    {
+      // Nothing to do.
+    }
+
+    /**
+     * @brief Construct data by copying all elements from the initializer list.
+     *
+     * @param initalizer_list List we want to copy all elements from.
+     */
+    [[gnu::section(".stl_text")]]
+    explicit stack(std::initializer_list<T> initalizer_list)
+        : _container(initalizer_list)
+    {
+      // Nothing to do.
+    }
+
+    /**
+     * @brief Copy constructor.
+     *
+     * @note Allocates underlying data container with the same capacity as stack we are copying from and copies all
+     * elements from it.
+     *
+     * @param other Other instance of stack we want to copy the data from.
+     */
+    [[gnu::section(".stl_text")]]
+    stack(stack<T> const & other)
+        : _container(other)
+    {
+      // Nothing to do.
+    }
+
+    /**
+     * @brief Copy assignment operator.
+     *
+     * @note Allocates underlying data container with the same capacity as vector we are copying from and copies all
+     * elements from it.
+     *
+     * @param other Other instance of vector we want to copy the data from.
+     * @return Newly created copy.
+     */
+    [[gnu::section(".stl_text")]]
+    stack<T> & operator=(stack<T> const & other)
+    {
+      _container = other;
+    }
+
+    /**
+     * @brief Destructor.
+     */
+    ~stack() = default;
+
+    /**
+     * @brief Amount of elements currently contained in this vector, will fill up until we have reached the capacity. If
+     * that is the case the capacity is increased automatically.
+     *
+     * @return Current amount of elements.
+     */
+    [[gnu::section(".stl_text")]]
+    auto size() const -> size_type
+    {
+      return _container.size();
+    }
+
+    /**
+     * @brief Returns a reference to the last element in the container. Calling back on an empty container causes
+     * undefined behavior.
+     *
+     * @return Reference to the last element.
+     */
+    [[gnu::section(".stl_text")]]
+    auto top() -> reference
+    {
+      return _container.back();
+    }
+
+    /**
+     * @brief Returns a reference to the last element in the container. Calling back on an empty container causes
+     * undefined behavior.
+     *
+     * @return Reference to the last element.
+     */
+    [[gnu::section(".stl_text")]]
+    auto top() const -> const_reference
+    {
+      return _container.back();
+    }
+
+    /**
+     * @brief Appends the given element value to the end of the container. The element is assigned through the
+     * assignment operator of the template type. The value is forwarded to the constructor as
+     * std::forward<U>(value), meaning it is either moved (rvalue) or copied (lvalue).
+     *
+     * @note If after the operation the new size() is greater than old capacity() a reallocation takes place,
+     * in which case all iterators (including the end() iterator) and all references to the elements are invalidated.
+     * Otherwise only the end() iterator is invalidated. Uses a forward reference for the actual value passed, which
+     * allows the template method to be used by both lvalue and rvalues and compile a different implementation.
+     *
+     * @param value The value of the element to append.
+     */
+    template<class U>
+    [[gnu::section(".stl_text")]]
+    auto push(U && value) -> void
+    {
+      _container.push_back(std::forward<U>(value));
+    }
+
+    /**
+     * @brief Appends a new element to the end of the container. The element is constructed through a constructor of the
+     * template type. The arguments args... are forwarded to the constructor as std::forward<Args>(args)....
+     *
+     * If after the operation the new size() is greater than old capacity() a reallocation takes place, in which case
+     * all iterators (including the end() iterator) and all references to the elements are invalidated. Otherwise only
+     * the end() iterator is invalidated. Uses a forward reference for the actual value passed, which
+     * allows the template method to be used by both lvalue and rvalues and compile a different implementation.
+     *
+     * @tparam Args
+     * @param args Arguments to forward to the constructor of the element
+     * @return value_type&
+     */
+    template<class... Args>
+    [[gnu::section(".stl_text")]]
+    auto emplace(Args &&... args) -> reference
+    {
+      _container.emplace_back(std::forward<Args>(args)...);
+    }
+
+    /**
+     * @brief Removes the last element of the container.
+     *
+     * @note Calling pop_back on an empty container results in halting the
+     * further execution. Iterators and references to the last element are invalidated. The end()
+     * iterator is also invalidated.
+     */
+    [[gnu::section(".stl_text")]]
+    auto pop() -> void
+    {
+      _container.pop_back();
+    }
+
+    /**
+     * @brief Wheter there are currently any items this container or not.
+     *
+     * @return True if there are no elements, false if there are.
+     */
+    [[gnu::section(".stl_text")]]
+    auto empty() const -> bool
+    {
+      return _container.empty();
+    }
+
+  private:
+    container_type _container = {};  ///< Underlying container used by the stack to actually save the data.
+  };
+
+}  // namespace kstd
+
+#endif