#line 610 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
  
  Bounded Variable length arrays, bound set at construction time.
  
  open class Varray
  {
    A varray is just a pointer.
    The current length and bound are maintained by the GC.
    _gc_pointer type varray[t] = "?1*";
  
    An ordinary carray, but owned by the GC.
    ctor[t] carray[t] : varray[t] = "$1";
  
    Create an empty varray with the given bound.
    ctor[t] varray[t]: size =
      "(?1*)(PTF gcp->collector->create_empty_array(&@?1,$1))"
      requires property "needs_gc"
    ;
  
    Raw memory initialisation (really, this belongs in C_hack).
    private proc _init[T]: &T * T = "new((void*)$1) ?1($2);";
  
  
    Construct a varray filled up with a default value.
    ctor[t] varray[t] (bound:size, default:t) = {
      var o = varray[t] bound;
      if bound > 0uz do for var i in 0uz upto bound - 1uz do
        push_back(o, default);
      done done
      return o;
    }
  
    Construct a partially filled varray with a default value computed by a function.
    ctor[t] varray[t] (bound:size, used:size, f:size->t when used <= bound) = {
      var o = varray[t] bound;
      if used > 0uz do for var i in 0uz upto used - 1uz do
        push_back(o, f i);
      done done
      return o;
    }
  
    Construct a full varray from an array.
    // funny, the N isn't explicitly used.
    ctor[t,N] varray[t] (x:array[t,N]) =>
       varray[t] (len x, len x, (fun (i:size):t =>x.i))
    ;
  
    Construct a partially full varray from a varray.
    ctor[t] varray[t] (x:varray[t], maxlen:size) =>
      varray[t] (maxlen, min(maxlen,len x), (fun (i:size):t=> x.i))
    ;
  
    Construct a full varray from a varray (copy constructor).
    ctor[t] varray[t] (x:varray[t]) =>
      varray[t] (len x, len x, (fun (i:size):t=> x.i))
    ;
  
    // Construct a varray from a list
    ctor[t] varray[t] (x:list[t]) = {
      val n = x.len.size;
      var a = varray[t] n;
      iter (proc (v:t) { push_back(a,v); }) x;
      return a;
    }
  
    Construct a varray from a string.
    Include a trailing nul byte.
    ctor varray[char] (var x:string) = {
      var n = x.len; var p = x._unsafe_cstr;
      var v = varray[char] (n + 1);
      var q = v.stl_begin;
      memcpy (q.address, p.address, n);
      q+n <- char "";
      set_used (v,n + 1);
      return v;
    }
  
    private proc set_used[t]: varray[t] * size =
      "PTF gcp->collector->set_used($1,$2);"
      requires property "needs_gc"
    ;
  
    Treat a varray as an ArrayValue.
    instance[v] ArrayValue[varray[v],v] {
      Length of a varray (used).
      fun len: varray[v] -> size =
        "PTF gcp->collector->get_used($1)"
        requires property "needs_gc"
      ;
      Unsafe get value at position.
      fun unsafe_get: varray[v] * size -> v = "$1[$2]";
    }
  
    Treat a varray as an ArrayObject.
    Allows modifications.
    instance[v] ArrayObject[varray[v],v] {
      Store the given value at the given position.
      proc unsafe_set: varray[v] * size * v = "$1[$2]=$3;";
      fun unsafe_get_ref: varray[v] * size -> &v = "$1+$2";
    }
  
    Treat a varray as a ContiguousArrayObject.
    instance[v] ContiguousArrayObject[varray[v],v] {
      STL iterator to start of array.
      fun stl_begin: varray[v] -> +v = "$1";
  
      STL iterator to end of array.
      fun stl_end: varray[v] -> +v = "($1+PTF gcp->collector->get_used($1))";
    }
  
    Get the bound of a varray.
    fun maxlen[t]: varray[t] -> size =
      "PTF gcp->collector->get_count($1)"
      requires property "needs_gc"
    ;
  
    Append a new element to the end of a varray.
    Aborts if you go past the bound.
    proc += [t] (pa:&varray[t],v:t) { push_back (*pa,v); }
  
    Append a new element to the end of a varray.
    Aborts if you go past the bound.
    proc push_back[t] : varray[t] * t = """
      {
        //?1 * _p = *$1;
        size_t n = PTF gcp->collector->get_used($1);
        PTF gcp->collector->incr_used($1,1L);
        new($1+n) ?1($2);
      }
    """
      requires property "needs_gc"
    ;
  
    Pop an element off the end of a varray.
    Aborts if the array is empty.
    proc pop[t] : varray[t] = """
      { // pop varray
        ?1 * _p = $1;
        size_t n = PTF gcp->collector->get_used(_p);
        PTF gcp->collector->incr_used(_p,-1L);
        destroy(_p+n-1); // from flx_compiler_support_bodies
      }
    """
      requires property "needs_gc";
    ;
  
    Erase elements of array between and including first and last.
    Include first and last, intersect with array span.
    Cannot fail.
    proc erase[v] (a:varray[v], first:int, last:int)
    {
      if first > last return;
      var l = a.len.int;
      var b = if first < 0 then 0 else first;
      var e = if last >= l then l - 1 else last;
      var d = e - b + 1;
      if d > 0 do
        for var i in b upto l - d - 1 do
           unsafe_set (a, i.size, unsafe_get (a, size (i + d)));
        done
        var s : carray[v] = a.stl_begin;
        for i in l - d upto l - 1 do
          var p : carray[v] = s + i;
          C_hack::destroy$ -p;
        done
        set_used$ a, (l - d).size;
      done
    }
  
    proc erase[v] (a:varray[v], i:int) => erase (a,i,i);
  
    insert (a,i,v) inserts v in a at position i
    that is, inserts before element i.
    If i is negative, position relative to end,
    that is, -1 is last element, so insert (a,-1,v)
    inserts before the last element (not after!)
    If i equals the length, element is appended.
    If the index is out of range, nothing happens.
    proc insert[t] (a:varray[t], i:int, v:t)
    {
      var l = a.len.int;
      var n = a.maxlen.int;
      if l == n return; // fail: no space
      var ix = if i < 0 then  l - i else i;
      if ix < 0 or ix > l return; // fail: bad index
      if ix == l do
        push_back (a,v);
      else
        assert l > 0;
        push_back (a, a.(l - 1)); // dups last element
        if l - 2 > ix do
          for var j in l - 2 downto ix do // copy from second last pos
             unsafe_set (a, j.size + 1uz, unsafe_get (a, j.size));
          done
        done
        unsafe_set (a, ix.size, v);
      done
    }
  
  
    Traditional map varray to varray.
    fun map[T, U] (_f:T->U) (x:varray[T]): varray[U] = {
      var o = varray[U]$ len(x);
  
      if len x > 0uz do for var i in 0uz upto len(x) - 1uz do
        push_back (o, _f x.i);
      done done
      return o;
    }
  
  }
  
  instance[T with Show[T]] Str[Varray::varray[T]] {
    Convert a varray[T] to a string.
    Requires Show[T]
    fun str (xs:varray[T]) = {
      var o = 'varray(';
  
      if len xs > 0uz do
        o += repr xs.0;
  
        for var i in 1uz upto len xs - 1uz do
          o += ', ' + repr xs.i;
        done
      done
  
      return o + ')';
    }
  }
  
  Treat varray as Set.
  instance[T with Eq[T]] Set[varray[T],T] {
    Check is a value is stored in a varray.
    fun \(\in\) (x:T, a:varray[T]) : bool = {
      if len a > 0uz do
        for var i in 0uz upto len a - 1uz do
          if a.i == x do return true; done
        done
      done
      return false;
    }
  }
  
  open[T] Show[Varray::varray[T]];
  open[T] Set[Varray::varray[T],T];
  open[T] ArrayValue[varray[T], T];
  open[T] ArrayObject[varray[T], T];
  open[T] ContiguousArrayObject[varray[T], T];