dynamic_vector.h

// Copyright 2025 The Pigweed Authors
//
// 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
//
//     https://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.
#pragma once
 
#include <initializer_list>
#include <iterator>
 
#include "pw_allocator/allocator.h"
#include "pw_containers/dynamic_deque.h"
#include "pw_containers/ptr_iterator.h"
 
namespace pw {
 
 
 
template <typename T, typename SizeType = uint16_t>
class DynamicVector {
 public:
  using value_type = T;
  using size_type = SizeType;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = value_type*;
  using const_pointer = const value_type*;
  using iterator = containers::PtrIterator<DynamicVector>;
  using const_iterator = containers::ConstPtrIterator<DynamicVector>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  using allocator_type = Allocator;
 
  explicit constexpr DynamicVector(Allocator& allocator) : deque_(allocator) {}
 
  DynamicVector(const DynamicVector&) = delete;
  DynamicVector& operator=(const DynamicVector&) = delete;
 
  constexpr DynamicVector(DynamicVector&&) = default;
  constexpr DynamicVector& operator=(DynamicVector&&) = default;
 
  // Iterators
 
  iterator begin() { return iterator(data()); }
  const_iterator begin() const { return cbegin(); }
  const_iterator cbegin() const { return const_iterator(data()); }
 
  iterator end() { return iterator(data() + size()); }
  const_iterator end() const { return cend(); }
  const_iterator cend() const { return const_iterator(data() + size()); }
 
  reverse_iterator rbegin() { return reverse_iterator(end()); }
  const_reverse_iterator rbegin() const { return crbegin(); }
  const_reverse_iterator crbegin() const {
    return const_reverse_iterator(end());
  }
 
  reverse_iterator rend() { return reverse_iterator(begin()); }
  const_reverse_iterator rend() const { return crend(); }
  const_reverse_iterator crend() const {
    return const_reverse_iterator(begin());
  }
 
  // Capacity
 
  constexpr allocator_type& get_allocator() const {
    return deque_.get_allocator();
  }
 
  bool empty() const { return deque_.empty(); }
 
  size_type size() const { return deque_.size(); }
 
  size_type capacity() const { return deque_.capacity(); }
 
  size_type max_size() const { return deque_.max_size(); }
 
  void reserve(size_type new_capacity) { deque_.reserve(new_capacity); }
 
  void reserve_exact(size_type new_capacity) {
    deque_.reserve_exact(new_capacity);
  }
 
  [[nodiscard]] bool try_reserve(size_type new_capacity) {
    return deque_.try_reserve(new_capacity);
  }
 
  [[nodiscard]] bool try_reserve_exact(size_type new_capacity) {
    return deque_.try_reserve_exact(new_capacity);
  }
 
  void shrink_to_fit() { deque_.shrink_to_fit(); }
 
  // Element access
 
  reference operator[](size_type pos) { return data()[pos]; }
 
  const_reference operator[](size_type pos) const { return data()[pos]; }
 
  reference at(size_type pos) { return deque_.at(pos); }
 
  const_reference at(size_type pos) const { return deque_.at(pos); }
 
  reference front() { return deque_.front(); }
 
  const_reference front() const { return deque_.front(); }
 
  reference back() { return deque_.back(); }
 
  const_reference back() const { return deque_.back(); }
 
  pointer data() { return deque_.data(); }
 
  const_pointer data() const { return deque_.data(); }
 
  // Modifiers
 
  void assign(size_type count, const value_type& value) {
    deque_.assign(count, value);
  }
 
  [[nodiscard]] bool try_assign(size_type count, const value_type& value) {
    return deque_.try_assign(count, value);
  }
 
  void assign(std::initializer_list<T> init) { deque_.assign(init); }
 
  [[nodiscard]] bool try_assign(std::initializer_list<T> init) {
    return deque_.try_assign(init);
  }
 
  void push_back(const value_type& value) { deque_.push_back(value); }
 
  void push_back(value_type&& value) { deque_.push_back(std::move(value)); }
 
  [[nodiscard]] bool try_push_back(const value_type& value) {
    return deque_.try_push_back(value);
  }
 
  [[nodiscard]] bool try_push_back(value_type&& value) {
    return deque_.try_push_back(std::move(value));
  }
 
  void pop_back() { deque_.pop_back(); }
 
  template <typename... Args>
  void emplace_back(Args&&... args) {
    deque_.emplace_back(std::forward<Args>(args)...);
  }
 
  template <typename... Args>
  [[nodiscard]] bool try_emplace_back(Args&&... args) {
    return deque_.try_emplace_back(std::forward<Args>(args)...);
  }
 
  template <typename... Args>
  iterator emplace(const_iterator pos, Args&&... args) {
    auto deque_it = deque_.try_emplace_shift_right(ToDequeIterator(pos),
                                                   std::forward<Args>(args)...);
    PW_ASSERT(deque_it.has_value());
    return iterator(data() + deque_it->pos_);
  }
 
  template <typename... Args>
  [[nodiscard]] std::optional<iterator> try_emplace(const_iterator pos,
                                                    Args&&... args) {
    auto deque_it = deque_.try_emplace_shift_right(ToDequeIterator(pos),
                                                   std::forward<Args>(args)...);
    if (!deque_it.has_value()) {
      return std::nullopt;
    }
    return iterator(data() + deque_it->pos_);
  }
 
  iterator insert(const_iterator pos, const T& value) {
    return emplace(pos, value);
  }
 
  iterator insert(const_iterator pos, T&& value) {
    return emplace(pos, std::move(value));
  }
 
  iterator insert(const_iterator pos, size_type count, const T& value) {
    auto deque_it =
        deque_.try_insert_shift_right(ToDequeIterator(pos), count, value);
    PW_ASSERT(deque_it.has_value());
    return iterator(data() + deque_it->pos_);
  }
 
  template <typename InputIt>
  iterator insert(const_iterator pos, InputIt first, InputIt last) {
    auto deque_it =
        deque_.try_insert_shift_right(ToDequeIterator(pos), first, last);
    PW_ASSERT(deque_it.has_value());
    return iterator(data() + deque_it->pos_);
  }
 
  iterator insert(const_iterator pos, std::initializer_list<T> ilist) {
    return insert(pos, ilist.begin(), ilist.end());
  }
 
  [[nodiscard]] std::optional<iterator> try_insert(const_iterator pos,
                                                   const T& value) {
    return try_emplace(pos, value);
  }
 
  [[nodiscard]] std::optional<iterator> try_insert(const_iterator pos,
                                                   T&& value) {
    return try_emplace(pos, std::move(value));
  }
 
  [[nodiscard]] std::optional<iterator> try_insert(const_iterator pos,
                                                   size_type count,
                                                   const T& value) {
    auto deque_it =
        deque_.try_insert_shift_right(ToDequeIterator(pos), count, value);
    if (!deque_it.has_value()) {
      return std::nullopt;
    }
    return iterator(data() + deque_it->pos_);
  }
 
  template <typename InputIt>
  [[nodiscard]] std::optional<iterator> try_insert(const_iterator pos,
                                                   InputIt first,
                                                   InputIt last) {
    auto deque_it =
        deque_.try_insert_shift_right(ToDequeIterator(pos), first, last);
    if (!deque_it.has_value()) {
      return std::nullopt;
    }
    return iterator(data() + deque_it->pos_);
  }
 
  [[nodiscard]] std::optional<iterator> try_insert(
      const_iterator pos, std::initializer_list<T> ilist) {
    return try_insert(pos, ilist.begin(), ilist.end());
  }
 
  // TODO: b/424613355 - Implement insert, emplace
 
  iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
 
  iterator erase(const_iterator first, const_iterator last) {
    auto first_ptr = const_cast<pointer>(&*first);
    if (first != last) {
      std::move(const_cast<pointer>(&*last), data() + size(), first_ptr);
      size_t items_to_pop = static_cast<SizeType>(last - first);
      for (size_t i = 0; i < items_to_pop; ++i) {
        deque_.pop_back();
      }
    }
    return iterator(first_ptr);
  }
 
  void resize(size_type count) { deque_.resize(count); }
 
  void resize(size_type count, const value_type& value) {
    deque_.resize(count, value);
  }
 
  [[nodiscard]] bool try_resize(size_type count) {
    return deque_.try_resize(count);
  }
 
  [[nodiscard]] bool try_resize(size_type count, const value_type& value) {
    return deque_.try_resize(count, value);
  }
 
  void clear() { deque_.clear(); }
 
  void reset() { deque_.reset(); }
 
  void swap(DynamicVector& other) { deque_.swap(other.deque_); }
 
 private:
  typename DynamicDeque<T, size_type>::const_iterator ToDequeIterator(
      const_iterator it) const {
    return {deque_, static_cast<size_type>(it - cbegin())};
  }
 
  // The underlying DynamicDeque instance that provides the storage.
  DynamicDeque<T, size_type> deque_;
};
 
}  // namespace pw