class Vec[T] {
  var array: Array[T] = nil;
  var length: Int = 0;

  fun get(idx: Int) -> T {
    if idx < 0 || idx >= self.length {
      fatalError("index out of bounds for vector");
    }

    return self.array.get(idx);
  }

  fun set(idx: Int, val: T) {
    if idx < 0 || idx >= self.length {
      fatalError("index out of bounds for vector");
    }

    self.array.set(idx, val);
  }

  fun push(val: T) {
    var newcap = self.capacity();

    if self.length == newcap {
      if newcap == 0 {
        newcap = 4;
      } else {
        newcap = newcap * 2;
      }

      let newarray = Array[T](newcap);
      arrayCopy[T](self.array, 0, newarray, 0, self.length);
      self.array = newarray;
    }

    self.array.set(self.length, val);
    self.length = self.length + 1;
  }

  fun pop() -> T {
    if self.length == 0 {
      fatalError("no element left to pop");
    }

    let newlength = self.length - 1;
    let temp = self.array.get(newlength);

    // set popped element to nil so that GC can collect object
    // not necessary for primitive types
    self.array.set(newlength, defaultValue[T]());

    self.length = newlength;

    return temp;
  }

  fun trimToLen() {
    if self.length != self.capacity() {
      if self.length == 0 {
        self.array = nil;
      } else {
        let newarray = Array[T](self.length);
        arrayCopy[T](self.array, 0, newarray, 0, self.length);
        self.array = newarray;
      }
    }
  }

  fun removeAt(var ind: Int) -> T {
    assert(ind < self.length);
    let temp = self.get(ind);
    let len = self.length;

    while ind < len - 1 {
      self.set(ind, self.get(ind+1));
      ind = ind + 1;
    }

    self.set(ind, defaultValue[T]());
    self.length = ind;

    return temp;
  }

  fun length() -> Int {
    return self.length;
  }

  fun is_empty() -> Bool {
    self.length == 0
  }

  fun capacity() -> Int {
    if self.array === nil {
      return 0;
    } else {
      return self.array.length();
    }
  }

  fun first() -> T {
    assert(self.length > 0);
    return self.array.get(0);
  }

  fun last() -> T {
    let len = self.length;
    assert(len > 0);
    return self.array.get(len-1);
  }
}

fun removeItem[T: Equals](vec: Vec[T], elem: T) {
  var i = 0;

  while i < vec.length() {
    if vec.get(i).equals(elem) {
      vec.removeAt(i);
    } else {
      i = i + 1;
    }
  }
}