#line 860 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
  
  
  #line 878 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
  Unbounded Variable length object array.
  open class Darray
  {
  #line 889 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    private struct darray_ctl[T]
    {
      a: varray[T];
      resize: size * size --> size;
    }
  
  #line 905 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    This is the default array resize function.
    If we run out of space, allocate what we have + 50%.
    If we need less than half the allocated space, return the requested size + 50%.
    Otherwise return the existing allocated space.
    cfun dflt_resize(old_max:size, requested:size):size=
    {
      // GOTCHA: don't forget that division has a higher precedence than multiplication!
      // sensible minimum size of 20, except if zero length
      if requested == 0uz return 0uz;
      if requested < 20uz return 20uz;
      if requested < old_max / 2uz return (3uz * requested) / 2uz;
      if requested > old_max return (requested * 3uz) / 2uz;
      return old_max;
    }
  
  #line 926 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    Type of a darray.
    type darray[T] = new &darray_ctl[T];
  
  #line 939 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    Force a resize.
    Similar to C++ vector reserve function.
    proc do_resize[T] (pd: darray[T], new_size: size)
    {
      var old = (_repr_ pd)*.a;
      (_repr_ pd).a <- varray[T] (new_size, (len old), (fun(i:size)=>old.i));
    }
  
  #line 949 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    Make an empty darray, give it 20 slots for no particular reason.
    ctor[T] darray[T] () =>
      _make_darray[T]$ new darray_ctl[T](varray[T] 20uz , dflt_resize);
  
    Make a darray from an array
    ctor[T,N] darray[T] (a:array[T,N]) =>
      _make_darray[T]$ new darray_ctl[T]( varray[T] a, dflt_resize);
  
    Make a darray from a varray
    ctor[T] darray[T] (a:varray[T]) =>
      _make_darray[T]$ new darray_ctl[T]( varray[T] a, dflt_resize);
  
    Make a darray from a darray (copy)
    ctor[T] darray[T] (a:darray[T]) => darray ((_repr_ a)*.a);
  
  
    make a darray of a certain size initialised with some default value
    ctor[T] darray[T] (n:size, default:T) => darray[T] (varray[T](n,default));
  
  #line 970 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    Basic array value stuff.
    instance[v] ArrayValue[darray[v],v] {
      fun len (a:darray[v])=> len (_repr_ a)*.a;
      fun unsafe_get (a:darray[v], i:size) => (_repr_ a)*.a.i;
    }
  
  #line 978 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    Basic array object stuff.
    instance[v] ArrayObject[darray[v],v] {
      proc unsafe_set (b:darray[v],  n:size, x:v) => unsafe_set ((_repr_ b)*.a,n,x);
      fun unsafe_get_ref (b:darray[v],  n:size) : &v => unsafe_get_ref ((_repr_ b)*.a,n);
    }
  
  #line 986 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    Contrue as contiguous store.
    instance[v] ContiguousArrayObject[darray[v],v] {
      fun stl_begin(b:darray[v]) => stl_begin b._repr_*.a;
      fun stl_end(b:darray[v]) => stl_end b._repr_*.a;
    }
  
  #line 998 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    Pop a value from the end.
    Same as pop_back in C++.
    proc pop[t](a:darray[t]) {
      pop (_repr_ a)*.a;
      newsize := (_repr_ a)*.resize (maxlen (_repr_ a)*.a, len (_repr_ a)*.a);
      if newsize != maxlen (_repr_ a)*.a call do_resize (a,newsize);
    }
  
    Push a value onto the end.
    Same as push_back in C++.
    proc += [t] (a:&darray[t],v:t) {
      push_back (*a, v);
    }
  
    Push a value onto the end.
    Same as push_back in C++.
    proc push_back[t] (a:darray[t], v:t) {
      r := _repr_ a;
      newsize := r*.resize (maxlen r*.a, len r*.a + 1uz);
      if newsize != maxlen r*.a call do_resize(a,newsize);
      push_back (r*.a, v); // hack to workaround compiler error Address non variable
    }
  
    insert
    proc insert[t] (a:darray[t], i:int, v:t)
    {
      var r = _repr_ a;
      newsize := r*.resize (maxlen r*.a, len r*.a + 1uz);
      if newsize != maxlen r*.a call do_resize(a,newsize);
      r = _repr_ a;
      insert (r*.a,i,v);
    }
  
    Erase an element, note doesn't resize the varray,
    probably should ..
    proc erase[t] (a:darray[t], i:int) => erase ((_repr_ a)*.a,i);
  
    Erase multiple elements, note doesn't resize the varray,
    probably should ..
    proc erase[t] (a:darray[t], first:int, last:int) =>
      erase ((_repr_ a)*.a, first,last);
  
  #line 1042 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
    // uses _repr_ so has to be in the module
    instance[T with Show[T]] Str[Darray::darray[T]] {
      Convert an array to a string,
      provided the element type is convertible.
      fun str (x:darray[T])=> str (_repr_ x)*.a;
    }
  
  }
  
  #line 1054 "/home/travis/build/felix-lang/felix/src/packages/arrays.fdoc"
  Construe a darray as a Set.
  instance[T with Eq[T]] Set[darray[T],T] {
   element membership test.
   fun \(\in\) (x:T, a:darray[T]) : bool = {
     for var i in 0uz upto len a -1uz
       if a.i == x return true
     ;
     return false;
   }
  }
  
  open[T] Show[Darray::darray[T]];
  open[T] Set[Darray::darray[T],T];
  
  open[T] ArrayValue[darray[T], T];
  open[T] ArrayObject[darray[T], T];
  open[T] ContiguousArrayObject[darray[T], T];