vector.lsts

## faster than [type(List<t>)]. should be used when you append or remove data a lot
type Vector<t> implies MustRetain, MustRelease
   = { data: OwnedData<t>[] };

let .release(x: Vector<t>): Nil = (
   if (x.data as USize) != 0 {
      x.data.release;
   };
   mark-as-released(x);
);

let .retain(x: Vector<t>): Vector<t> = (
   if (x.data as USize) != 0 {
      x.data.retain;
   };
   x
);


# new allocations = 0 if capacity==0
#                 | 1
let mk-vector(ty: Type<t>, capacity: USize): Vector<t> = (
   if capacity==0 then Vector(0 as OwnedData<t>[]) else Vector( mk-owned-data(type(t), capacity) )
);

# new allocations = 0
let mk-vector(ty: Type<t>): Vector<t> = (
   mk-vector(type(t), 0)
);

# new allocations = 0 if capacity==0
#                 | 1
let mk-vector(capacity: USize): Vector<t> = (
   if capacity==0 then Vector(0 as OwnedData<t>[]) else Vector( mk-owned-data(type(t), capacity) )
);

# new allocations = 0
let mk-vector(): Vector<t> = (
   mk-vector(type(t), 0)
);

# new allocations = 0
let .length(v: Vector<t>): USize = (
   if (v.data as USize) == 0 then 0 else v.data.occupied
);

# new allocations = 0
let $"[]"(v: Vector<t>, idx: USize): t = (
   v.data[idx]
);

# new allocations = 1
let .realloc(v: Vector<t>, target-capacity: USize): Vector<t> = (
   let new-data = mk-owned-data(type(t), target-capacity);
   let dlo = 0_sz;
   let dhi = v.length;
   while dlo < dhi {
      new-data.push(v[dlo]);
      dlo = dlo + 1;
   };
   Vector( new-data )
);

# TODO: Vector<t> and i: t should have the same type variable and it should unify
# new allocations = 1 if realloc is necessary
#                 | 0
let .push(v: Vector<t>, i: t): Vector<t> = (
   # if this vector is a view, or if it is full, then we need to reallocate
   if (v.data as USize)==0 or v.data.occupied==v.data.capacity {
      let new-capacity = if v.length==0 then 4_sz
      else (v.length >> 1_sz) + v.length; # this is mul 1.5, not 3
      v = v.realloc(new-capacity);
   };
   v.data.push(i);
   v
);

# Note: this *reduces* the size of the vector, so it *never* resizes
# There is no need to return the original vector because it never gets modified
let .pop(v: Vector<t>): t = (
   if v.length == 0 {
      fail("Tried to pop from empty Vector.");
   };
   v.data.pop
);

# TODO: remove after dumping lib1
let .pop-backwards-compatible(v: Vector<t>): (t, Vector<t>) = (
   let e = v.pop();
   (e, v)
);

# new allocations = 0
let cmp(x: Vector<x>, y: Vector<x>): Ord = (
   let r = Equal;
   if not(is(x, y)) {
      let xi = 0_sz;
      let yi = 0_sz;
      while xi < x.length and yi < y.length {
         let xycmp = cmp(x[xi], y[yi]);
         if is(xycmp,LessThan) {
            r = LessThan;
            xi = x.length;
            yi = y.length;
         } else if is(xycmp,GreaterThan) {
            r = GreaterThan;
            xi = x.length;
            yi = y.length;
         } else {
            xi = xi + 1;
            yi = yi + 1;
         }
      };
      if xi < x.length { r = GreaterThan };
      if yi < y.length { r = LessThan };
   };
   r
);

# new allocations = 0
let .sort(v: Vector<t>): Vector<t> = (
   let n = v.length;
   let i = 0_sz;
   if n > 1 then while i < n - 1_sz {
      let swapped = false;
      let j = 0_sz;
      while j < n - i - 1_sz {
         if v[j + 1_sz] < v[j] {
            let tmp = v[j];
            v[j] = v[j + 1_sz];
            v[j + 1_sz] = tmp;
            swapped = true;
         };
         j = j + 1_sz;
      };
      i = i + 1_sz;
      if not(swapped) {
         i = n;
      };
   };
   v
);

# new allocations = 1 if realloc is necessary
#                 | 0
let .buffer-into-string(v: Vector<U8>): String = (
   v.data.retain;
   String(0, v.length, v.data)
);

# new allocations = 1 if realloc is necessary
#                 | 0
let .buffer-into-cstring(v: Vector<U8>): CString = (
   v.push(0);
   v.data.retain;
   v.data.data as CString
);

# new allocations = 0
let $"set[]"( v: Vector<t>, i: USize, val: t ): Nil = (
   if i >= v.length then fail(c"Vector Index Out of Bounds");
   v.data[i] = val;
);

# new allocations = 0
let .reverse(v: Vector<t>): Vector<t> = (
   let vi = 0_sz;
   while vi < (v.length/2) {
      let tmp = v[vi];
      v[vi] = v[v.length - vi - 1];
      v[v.length - vi - 1] = tmp;
      vi = vi + 1;
   };
   v
);

# new allocations = 0
let .into(v: Vector<t>, tt: Type<Vector<t>>): Vector<t> = v;

let .contains(v: Vector<t>, i: t): Bool = (
   let result = false;
   for vector vi in v {
      if vi==i then result = true;
   };
   result
);

let deep-hash(ts: Vector<t>): U64 = (
   let return = 0_u64;
   for vector t0 in ts { return = return + deep-hash(t0); };
   return;
);

let .swap-keys-for-values(kvs: Vector<(k,v)>): Vector<(v,k)> = (
   let swapped = mk-vector(type((v,k)));
   # TODO: fix linear variable bug
   #for vector kv in kvs {
   #   swapped.push((kv.second, kv.first));
   #};
   swapped
);