// A variable-sized container that can hold both unrestricted types and resources.

module Vector {

  // Vector containing data of type Item.
  native struct T<Element>;

  native public empty<Element>(): Self.T<Element>;

  // Return the length of the vector.
  native public length<Element>(v: &Self.T<Element>): u64;

  // Acquire an immutable reference to the ith element of the vector.
  native public borrow<Element>(v: &Self.T<Element>, i: u64): &Element;

  // Add an element to the end of the vector.
  native public push_back<Element>(v: &mut Self.T<Element>, e: Element);

  // Get mutable reference to the ith element in the vector, abort if out of bound.
  native public borrow_mut<Element>(v: &mut Self.T<Element>, idx: u64): &mut Element;

  // Pop an element from the end of vector, abort if the vector is empty.
  native public pop_back<Element>(v: &mut Self.T<Element>): Element;

  // Destroy the vector, abort if not empty.
  native public destroy_empty<Element>(v: Self.T<Element>);

  // Swaps the elements at the i'th and j'th indices in the vector.
  native public swap<Element>(v: &mut Self.T<Element>, i: u64, j: u64);

  // Reverses the order of the elements in the vector in place.
  public reverse<Element>(v: &mut Self.T<Element>) {
      let front_index: u64;
      let back_index: u64;
      let len: u64;

      len = Self.length<Element>(freeze(copy(v)));

      if (copy(len) == 0) {
          return;
      }
      assert(copy(len) > 0, 0);

      front_index = 0;
      back_index = move(len) - 1;

      while (copy(front_index) < copy(back_index)) {
          Self.swap<Element>(copy(v), copy(front_index), copy(back_index));
          front_index = move(front_index) + 1;
          back_index = move(back_index) - 1;
      }

      return;
  }

  // Moves all of the elements of the `other` vector into the `lhs` vector.
  public append<Element>(lhs: &mut Self.T<Element>, other: Self.T<Element>) {

      Self.reverse<Element>(&mut other);

      while (!Self.is_empty<Element>(&other)) {
          Self.push_back<Element>(
              copy(lhs),
              Self.pop_back<Element>(&mut other)
          );
      }

      Self.destroy_empty<Element>(move(other));
      return;
  }

  // Return true if the vector has no elements
  public is_empty<Element>(v: &Self.T<Element>): bool {
    return Self.length<Element>(move(v)) == 0;
  }

}