array_list.hpp

Go to the documentation of this file.

/*
 
Copyright 2025 Matthew Tolman
 
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
 
   http://www.apache.org/licenses/LICENSE-2.0
 
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
 
*/

 
#ifndef MTCORE_ARRAY_LIST_HPP
#define MTCORE_ARRAY_LIST_HPP
 
#include "../alloc.hpp"
#include "../traits.hpp"
#include "slice.hpp"

namespace mtcore {
  template<typename T>
  struct ArrayList {
  private:
    Slice<T> elements = {};
    size_t count      = 0;
 
  public:
    using Elem = T;

    [[nodiscard]] decltype(auto) ptr_iter() noexcept { return iter::ptr(*this); }
    [[nodiscard]] decltype(auto) ptr_iter() const noexcept { return iter::const_ptr(*this); }
    [[nodiscard]] decltype(auto) iter() const noexcept { return iter::val(*this); }

    [[nodiscard]] Result<void, AllocationError> init(Allocator &alloc, size_t initCapacity = 10) noexcept {
      ensure(elements.head == nullptr && elements.size() == 0, "ALREADY INITIALIZED!");
      initCapacity  = initCapacity ? initCapacity : 10;
      auto allocRes = alloc.create_many<T>(initCapacity);
      if (allocRes.is_error()) {
        return allocRes.error();
      }
 
      elements = *allocRes;
      return success();
    }

    [[nodiscard]] Result<void, AllocationError> init(Allocator &alloc, std::initializer_list<T> init,
                                                     size_t capacity = 0) noexcept {
      ensure(elements.head == nullptr && elements.size() == 0, "ALREADY INITIALIZED!");
      if (capacity < init.size()) {
        capacity = init.size();
      }
      capacity      = capacity ? capacity : 10;
      auto allocRes = alloc.create_many<T>(init.size());
      if (allocRes.is_error()) {
        return allocRes.error();
      }
 
      elements     = *allocRes;
      size_t index = 0;
      for (const auto &elem: init) {
        elements[index++] = elem;
      }
      count = index;
 
      return success();
    }

    void deinit(Allocator &alloc) noexcept {
      if (elements.head != nullptr) {
        alloc.destroy_many(elements);
        elements.head = nullptr;
      }
      elements.len = 0;
    }

    [[nodiscard]] Result<void, AllocationError> push(Allocator &alloc,
                                                     const Slice<std::add_const_t<T>> &elems) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      if (count + elems.size() >= elements.len) {
        size_t newSize = elements.len + std::max(((elements.len + 1) / 2), elems.size());
        if (auto res = reserve(alloc, newSize); res.is_error()) {
          return res;
        }
      }
 
      ensure(push(elems).is_success(), "SOMEHOW GIVING MORE SPACE DIDN'T WORK");
      return success();
    }

    [[nodiscard]] Result<void, AllocationError> push(Allocator &alloc,
                                                     const Slice<std::remove_const_t<T>> &elems) noexcept {
      return push(alloc, elems.to_const());
    }

    [[nodiscard]] Result<void, AllocationError> push(Allocator &alloc, const T &elem) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      if (count >= elements.len) {
        size_t newSize = elements.len + ((elements.len + 1) / 2);
        if (auto res = reserve(alloc, newSize); res.is_error()) {
          return res;
        }
      }
 
      ensure(push(elem).is_success(), "SOMEHOW GIVING MORE SPACE DIDN'T WORK");
      return success();
    }

    [[nodiscard]] size_t size() const noexcept {
      ensure(count <= elements.len, "COUNT EXCEEDS SLICE SIZE!");
      return count;
    }

    [[nodiscard]] size_t capacity() const noexcept {
      ensure(count <= elements.len, "COUNT EXCEEDS SLICE SIZE!");
      return elements.len;
    }

    [[nodiscard]] Result<void, AllocationError> reserve(Allocator &alloc, const size_t newSize) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(count <= elements.len, "COUNT EXCEEDS SLICE SIZE!");
      if (newSize <= capacity()) {
        return success();
      }
      ensure(newSize > size(), "FAILED TO GROW");
      auto newElemAllocRes = alloc.create_many<T>(newSize);
      if (newElemAllocRes.is_error()) {
        return newElemAllocRes.error();
      }
 
      auto newElems = *newElemAllocRes;
      for (size_t i = 0; i < elements.size(); ++i) {
        std::swap(newElems[i], elements[i]);
      }
      alloc.destroy_many(elements);
      elements = newElems;
      return success();
    }

    [[nodiscard]] Result<void, AllocationError> shrink_to_fit(Allocator &alloc) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(count <= elements.len, "COUNT EXCEEDS SLICE SIZE!");
      auto newSize = size();
      if (newSize == capacity()) {
        return success();
      }
 
      ensure(newSize < size(), "FAILED TO SHRINK");
      auto newElemAllocRes = alloc.create_many<T>(newSize);
      if (!newElemAllocRes) {
        return newElemAllocRes;
      }
 
      auto newElems = *newElemAllocRes;
      for (size_t i = 0; i < elements.size(); ++i) {
        std::swap(newElems[i], elements[i]);
      }
      alloc.destroy_many(elements);
      elements = newElems;
      return success();
    }

    [[nodiscard]] Result<void, CollectionAddNoAllocationError>
    push(const Slice<std::remove_const_t<T>> &elems) noexcept {
      return push(elems.to_const());
    }

    [[nodiscard]] Result<void, CollectionAddNoAllocationError> push(const Slice<std::add_const_t<T>> &elems) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      if (count + elems.size() > elements.len) {
        return error(CollectionAddNoAllocationError::NO_ROOM);
      }
 
      for (size_t i = 0; i < elems.size(); ++i) {
        elements[count++] = elems[i];
      }
 
      return success();
    }

    [[nodiscard]] Result<void, CollectionAddNoAllocationError> push(const T &elem) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      if (count >= elements.len) {
        return error(CollectionAddNoAllocationError::NO_ROOM);
      }
 
      elements[count++] = elem;
      return success();
    }

    [[nodiscard]] Result<void, AllocationError> unshift(const T &elem) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      // add the new element to the end
      if (auto err = push(elem)) {
        return err;
      }
 
      // then bubble the last element down
      for (size_t i = 0; i + 1 < count; ++i) {
        const auto upper = count - 1 - i;
        const auto lower = count - 2 - i;
        std::swap(elements[upper], elements[lower]);
      }
      return success();
    }

    [[nodiscard]] Result<void, AllocationError> unshift(Allocator &alloc, const T &elem) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      // add the new element to the end
      if (auto err = push(alloc, elem)) {
        return err;
      }
 
      // then bubble the last element down
      for (size_t i = 0; i + 1 < count; ++i) {
        const auto upper = count - 1 - i;
        const auto lower = count - 2 - i;
        std::swap(elements[upper], elements[lower]);
      }
      return success();
    }

    Optional<T> shift() noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      if (count == 0) {
        return nullopt;
      }
      return shift_remove(0);
    }

    Optional<T> pop() noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      if (count == 0) {
        return nullopt;
      }
      --count;
      return elements[count];
    }

    [[nodiscard]] T &at(size_t index) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return elements[index];
    }

    [[nodiscard]] const T &at(size_t index) const noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return elements[index];
    }

    T &operator[](size_t index) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return elements[index];
    }

    const T &operator[](size_t index) const noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return elements[index];
    }

    T swap_remove(size_t index) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(index < count, "ARRAY OUT OF BOUNDS DETECTED!");
      auto end = count - 1;
      if (index != end) {
        std::swap(elements[end], elements[index]);
      }
 
      auto popRes = pop();
      ensure(popRes.has_value(), "COULDN'T REMOVE ELMENT FROM NON-EMPTY LIST");
      return *popRes;
    }

    T shift_remove(size_t index) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(index < count, "ARRAY OUT OF BOUNDS DETECTED!");
 
      for (size_t i = index; i + 1 < count; ++i) {
        std::swap(elements[index], elements[index + 1]);
      }
      auto popRes = pop();
      ensure(popRes, "COULDN'T REMOVE ELMENT FROM NON-EMPTY LIST");
      return *popRes;
    }

    [[nodiscard]] Slice<T> slice() { return elements.sub(0, count); }

    [[nodiscard]] Slice<std::add_const_t<T>> slice() const { return elements.sub(0, count).to_const(); }
  };
 
  static_assert(is_mutable_addressable<ArrayList<int>>, "ARRAY LIST IS NOT MUTABLE ADDRESSABLE");
  static_assert(is_iterator<decltype(ArrayList<int>{}.iter())>, "ITER IS NOT VALID");
  static_assert(is_iterator<decltype(ArrayList<int>{}.ptr_iter())>, "ITER IS NOT VALID");
}  // namespace mtcore
 
#endif  // MTCORE_ARRAY_LIST_HPP