// ver graficos en 
   // https://blog.devgenius.io/implementing-a-vector-container-data-structure-in-c-using-templates-79b247784fc8
   //

#ifndef VECTOR_HH
#define VECTOR_HH

#include "assert.hh"

namespace pro2 {

  /**
   * @class Vector
   *
   * @brief Una classe que representa un vector dinàmic amb gestió de memòria explícita.
   *
   * Un vector dinàmic permet accedir als elements per índex amb `operator[]`,
   * afegir elements al final amb `push_back`, treure'ls amb `pop_back`,
   * i canviar la mida amb `resize`. La capacitat es gestiona automàticament:
   * es duplica quan cal créixer i es redueix a la meitat quan la mida baixa
   * per sota de la meitat de la capacitat.
   *
   * Internament, utilitza un array dinàmic (`new[]`/`delete[]`) per
   * il·lustrar la gestió de memòria en C++.
   *
   * Exemple:
   * ```c++
   * Vector<int> v;
   * v.push_back(3);
   * v.push_back(7);
   * v.push_back(1);
   * v[0];  // retorna 3
   * v.size();  // retorna 3
   * v.pop_back();
   * v.size();  // retorna 2
   * ```
   */
  
  template <typename T>
  class Vector {
    T *data_;
    int size_;
    int capacity_;

    // mantenemos que size_ <= capacity_ y que tras push_back y pop_back
    // la capacidad no usada no puede superar a size_ (*)
    
    // Realloca l'array intern amb una nova capacitat,
    // copiant els elements existents.
    void reallocate_(int new_capacity);

    static constexpr int initial_capacity_ = 4;

  public:
    /*
    typedef T *iterator; 
    typedef const T *const_iterator;

    esto funciona, pero si quisieramos un typedef para un vector<T>
    y luego poder instanciar T=int por ejemplo, sería mucho mas lio
    */
   
    using iterator = T *;
    using const_iterator = const T *;


    // Constructoras

    /**
     * @brief Construeix un vector buit. Θ(1).
     */
    Vector() : data_(nullptr), size_(0), capacity_(0) {}

    /**
     * @brief Construeix un vector de mida `n` amb valors per defecte. Θ(n).
     *
     * @param n La mida del vector.
     * @pre n >= 0.
     */
    
    Vector(int n) { //: data_(nullptr), size_(0), capacity_(0) {
      assert(n >= 0, "Vector::Vector(int): mida negativa!");
      data_ = new T[n];
      size_ = n;
      capacity_ = n;
    }

    /**
     * @brief Construeix un vector de mida `n` amb tots els elements iguals a `x`. Θ(n).
     *
     * @param n La mida del vector.
     * @param x El valor inicial de cada element.
     * @pre n >= 0.
     */
    Vector(int n, const T& x); // ver al final

    /////////////////////////////////////////////////////////////////////


    // Big Three: constructora de copia, destructora, redefinicion de la asignacion
    /**
     * @brief Construeix un vector com a còpia d'un altre vector. Θ(n).
     *
     * @param other El `Vector` del qual copiar.
     */
    Vector(const Vector& other); // ver al final

    /**
     * @brief Destrueix el vector i allibera la memòria. Θ(n).
     */
    ~Vector() {
      delete[] data_;
    }

    /**
     * @brief Assigna el contingut d'un altre vector a aquest. Θ(n).
     *
     * @param other El `Vector` del qual copiar.
     */
    Vector& operator=(const Vector& other); // ver al final
    
    /////////////////////////////////////////////////////////////////////

    // Acceso mediante []: dos versiones, ref y ref const
    /**
     * @brief Retorna una referència a l'element a la posició `i`. Θ(1).
     *
     * @param i L'índex de l'element.
     * @pre 0 <= i < size().
     */
    T& operator[](int i) {
      assert(i >= 0 && i < size_, "Vector::operator[]: índex fora de rang!");
      return data_[i];
    }

    /**
     * @brief Retorna una referència constant a l'element a la posició `i`. Θ(1).
     *
     * @param i L'índex de l'element.
     * @pre 0 <= i < size().
     */
    const T& operator[](int i) const {
      assert(i >= 0 && i < size_, "Vector::operator[]: índex fora de rang!");
      return data_[i];
    }
    /////////////////////////////////////////////////////////////////////

    // Consultoras:
    /**
     * @brief Retorna el nombre d'elements del vector. Θ(1).
     */
    int size() const {
      return size_;
    }

    /**
     * @brief Retorna la capacitat actual del vector. Θ(1).
     */
    int capacity() const {
      return capacity_;
    }

    /**
     * @brief Retorna `true` si el vector és buit, `false` en cas contrari. Θ(1).
     */
    bool empty() const {
      return size_ == 0;
    }

    /////////////////////////////////////////////////////////////////////

    // Modificadoras:

    /**
     * @brief Afegeix un element al final del vector. Θ(1) amortitzat.
     *
     * Si la mida arriba a la capacitat, es duplica la capacitat.
     *
     * @param x L'element a afegir.
     */
    void push_back(const T& x);  // ver al final

    /**
     * @brief Treu l'últim element del vector. Θ(1) amortitzat.
     *
     * Si la mida baixa per sota de la meitat de la capacitat,
     * es redueix la capacitat a la meitat.
     *
     * @pre El vector no és buit.
     */
    void pop_back();  // ver al final

    /**
     * @brief Buida el vector i allibera la memòria. Θ(1).
     */
    void clear() {
      // Una alternativa seria simplement posar `size_` a 0 sense
      // alliberar la memòria, mantenint la capacitat per a futures
      // insercions (que és el que fa `std::vector::clear()`).
      delete[] data_;
      data_ = nullptr;
      size_ = 0;
      capacity_ = 0;
    }

    /**
     * @brief Canvia la mida del vector a `n`. Θ(n) en el pitjor cas.
     *
     * Si `n > size()`, els nous elements tenen el valor per defecte de `T`.
     * Si `n < size()`, els elements sobrants es descarten.
     * Si cal, es realloca la memòria.
     *
     * @param n La nova mida.
     * @pre n >= 0.
     */
    void resize(int n);  // ver al final

    /**
     * @brief Canvia la mida del vector a `n`. Θ(n) en el pitjor cas.
     *
     * Si `n > size()`, els nous elements tenen el valor x.
     * Si `n < size()`, els elements sobrants es descarten.
     * Si cal, es realloca la memòria.
     *
     * @param n La nova mida.
     * @pre n >= 0.
     */
    void resize(int n, const T& x);  // ver al final
    
    /**
     * @brief Reserva capacitat per a almenys `n` elements. Θ(n) en el pitjor cas.
     *
     * Si `n <= capacity()`, no fa res.
     *
     * @param n La capacitat mínima desitjada.
     */
    void reserve(int n);  // ver al final
    
    /////////////////////////////////////////////////////////////////////

    // Iteradores:
    
    /**
     * @brief Retorna un iterador al primer element. Θ(1).
     */
    iterator begin() {
      return data_;
    }

    /**
     * @brief Retorna un iterador constant al primer element. Θ(1).
     */
    const_iterator begin() const {
      return data_;
    }

    /**
     * @brief Retorna un iterador a la posició posterior a l'últim element. Θ(1).
     */
    iterator end() {
      return data_ + size_; // cada unidad que se suma representa una posicion del array
    }

    /**
     * @brief Retorna un iterador constant a la posició posterior a l'últim element. Θ(1).
     */
    const_iterator end() const {
      return data_ + size_;
    }

    /////////////////////////////////////////////////////////////////////
    
  };

  // Implementació dels mètodes fora de la classe

  template <typename T>
  void Vector<T>::reallocate_(int new_capacity) {
    T *new_data = new T[new_capacity]; // array destino
    int new_size = std::min(new_capacity, size_);
    // no siempre se copia hacia vectores mas grandes; ver pop_back 
    for (int i = 0; i < new_size; ++i) {
      new_data[i] = data_[i];
    }
    delete[] data_; // se libera lo antiguo y se actualizan los campos
    data_ = new_data;
    capacity_ = new_capacity;
    size_ = new_size;
  }

  template <typename T>
  Vector<T>::Vector(int n, const T& x) {// : data_(nullptr), size_(0), capacity_(0) {
    assert(n >= 0, "Vector::Vector(int, const T&): mida negativa!");
    data_ = new T[n];
    size_ = n;
    capacity_ = n;
    for (int i = 0; i < n; ++i) {
      data_[i] = x;
    }
  }

  template <typename T>
  Vector<T>::Vector(const Vector& other)
    : data_(new T[other.capacity_]), size_(other.size_), capacity_(other.capacity_) {
    for (int i = 0; i < size_; ++i) {
      data_[i] = other.data_[i];
    }
  }

  template <typename T>
  Vector<T>& Vector<T>::operator=(const Vector& other) {
    if (this != &other) {
      delete[] data_;
      capacity_ = other.capacity_;
      size_ = other.size_;
      data_ = new T[capacity_];
      for (int i = 0; i < size_; ++i) {
	data_[i] = other.data_[i];
      }
    }
    return *this;
  }

  template <typename T>
  void Vector<T>::push_back(const T& x) {
    // si el push_back se produce con size = capacity y son 0,
    // reserva una capacity constante, en caso contrario duplica la capacity
    if (size_ == capacity_) {
      reallocate_(capacity_ == 0 ? initial_capacity_ : 2 * capacity_);
    }
    data_[size_] = x;
    ++size_;
  }

  template <typename T>
  void Vector<T>::pop_back() {
    assert(size_ > 0, "Vector::pop_back: vector buit!");
    --size_;
    // si el size queda demasiado pequeño, se divide la capacity
    if (size_ < capacity_ / 2) {
      reallocate_(capacity_ / 2);
    }
  }

  template <typename T>
  void Vector<T>::resize(int n) {
    assert(n >= 0, "Vector::resize: mida negativa!");
    reallocate_(n);
    size_ = n;
  }

  template <typename T>
  void Vector<T>::resize(int n, const T& x) {
    assert(n >= 0, "Vector::resize: mida negativa!");
    if (n > capacity_) {
      reallocate_(n);
    }
    for (int i = size_; i < n; ++i) {
      data_[i] = x;
    }
    size_ = n;
  }

  template <typename T>
  void Vector<T>::reserve(int n) {
    assert(n >= 0, "Vector::reserve: capacitat negativa!");
    if (n > capacity_) {
      reallocate_(n);
    }
  }

}  // namespace pro2

#endif

// algunos buenos ejercicios: implementar insert y delete