// Dynamic array implemented from scratch (what JS Array does internally)
class DynamicArray {
  #data;
  #size = 0;
  #capacity;

  constructor(initialCapacity = 4) {
    this.#capacity = initialCapacity;
    this.#data = new Array(this.#capacity);
  }

  get length() { return this.#size; }

  // O(1) — Read by index
  get(i) {
    if (i < 0 || i >= this.#size) throw new RangeError(`Index ${i} out of bounds`);
    return this.#data[i];
  }

  // O(1) amortized — Append to end
  push(value) {
    if (this.#size === this.#capacity) this.#resize(); // O(n) but rare
    this.#data[this.#size++] = value;
  }

  // O(1) amortized — Remove from end
  pop() {
    if (this.#size === 0) throw new Error('Empty array');
    const val = this.#data[--this.#size];
    // Shrink at 25% utilization to reclaim memory (avoid thrashing)
    if (this.#size > 0 && this.#size === Math.floor(this.#capacity / 4)) {
      this.#resize(Math.floor(this.#capacity / 2));
    }
    return val;
  }

  // O(n) — Insert at arbitrary index (shifts elements right)
  insert(i, value) {
    if (this.#size === this.#capacity) this.#resize();
    for (let j = this.#size; j > i; j--) this.#data[j] = this.#data[j - 1];
    this.#data[i] = value;
    this.#size++;
  }

  // O(n) — Double the internal buffer (copy all elements)
  #resize(newCapacity = this.#capacity * 2) {
    const newData = new Array(newCapacity);
    for (let i = 0; i < this.#size; i++) newData[i] = this.#data[i];
    this.#data = newData;
    this.#capacity = newCapacity;
    // Amortized: each element is copied at most O(log n) times across all resizes
  }

  [Symbol.iterator]() {
    let i = 0;
    return { next: () => i < this.#size
      ? { value: this.#data[i++], done: false }
      : { done: true }
    };
  }
}

// Usage
const da = new DynamicArray();
for (let i = 0; i < 10; i++) da.push(i * 10); // Resizes happen internally at 4, 8
console.log(da.get(5)); // 50 — O(1)
da.pop();               // removes 90

// In practice just use:
const arr = [];
arr.push(1, 2, 3); // JS Array IS a dynamic array