array.ts

import { Array } from "array";
import { ArrayBufferView } from "arraybuffer";
import { COMPARATOR } from "util/sort";

// Array<T> has the same layout as ArrayBufferView
assert(offsetof<ArrayBufferView>("buffer") == offsetof<i32[]>("buffer"));
assert(offsetof<ArrayBufferView>("dataStart") == offsetof<i32[]>("dataStart"));
assert(offsetof<ArrayBufferView>("byteLength") == offsetof<i32[]>("byteLength"));

// Obtains the internal capacity of an array from its backing buffer.
function internalCapacity<T>(array: Array<T>): i32 {
  // the memory region used by the backing buffer might still be larger in that the ArrayBuffer
  // pre-allocates a power of 2 sized buffer itself and reuses it as long as it isn't exceeded.
  var buffer: ArrayBuffer = array.buffer;
  return buffer.byteLength >> alignof<T>();
}

// Checks if two arrays are equal
function isArraysEqual<T>(a: Array<T>, b: Array<T>, len: i32 = 0): bool {
  if (!len) {
    len = a.length;
    if (len != b.length) return false;
    if (a == b) return true;
  }
  for (let i = 0; i < len; i++) {
    if (isFloat<T>()) {
      if (isNaN(a[i]) && isNaN(b[i])) continue;
      if (Math.signbit(a[i]) != Math.signbit(b[i])) return false;
    }
    if (a[i] != b[i]) return false;
  }
  return true;
}

var arr = new Array<i32>();

// Array.isArray ///////////////////////////////////////////////////////////////////////////////////

class Ref {
  constructor(public v: i32 = 0) {}
  toString(): string {
    return "[object Object]";
  }
}

{
  assert(!Array.isArray(<i32[] | null>null));
  assert(!Array.isArray(new Ref()));
  assert(!Array.isArray(new Uint8Array(1)));
  assert(!Array.isArray(<i32>1));
  assert(!Array.isArray("abc"));

  assert(Array.isArray(arr));
}

// Array#fill //////////////////////////////////////////////////////////////////////////////////////
{
  let arr8: u8[] = [1, 2, 3, 4, 5];

  arr8.fill(1, 1, 3);
  assert(isArraysEqual<u8>(arr8, [1, 1, 1, 4, 5]));

  arr8.fill(0);
  assert(isArraysEqual<u8>(arr8, [0, 0, 0, 0, 0]));

  arr8.fill(1, 0, -3);
  assert(isArraysEqual<u8>(arr8, [1, 1, 0, 0, 0]));

  arr8.fill(2, -2);
  assert(isArraysEqual<u8>(arr8, [1, 1, 0, 2, 2]));

  arr8.fill(0, 1, 0);
  assert(isArraysEqual<u8>(arr8, [1, 1, 0, 2, 2]));

  arr8.fill(<u8>-1);
  assert(isArraysEqual<u8>(arr8, [<u8>-1, <u8>-1, <u8>-1, <u8>-1, <u8>-1]));
}

{
  let arr32: u32[] = [1, 2, 3, 4, 5];

  arr32.fill(1, 1, 3);
  assert(isArraysEqual<u32>(arr32, [1, 1, 1, 4, 5]));

  arr32.fill(0);
  assert(isArraysEqual<u32>(arr32, [0, 0, 0, 0, 0]));

  arr32.fill(1, 0, -3);
  assert(isArraysEqual<u32>(arr32, [1, 1, 0, 0, 0]));

  arr32.fill(2, -2);
  assert(isArraysEqual<u32>(arr32, [1, 1, 0, 2, 2]));

  arr32.fill(0, 1, 0);
  assert(isArraysEqual<u32>(arr32, [1, 1, 0, 2, 2]));

  arr32.fill(-1);
  assert(isArraysEqual<u32>(arr32, [-1, -1, -1, -1, -1]));
}

{
  let arrf32: f32[] = [0.5, 1.0, 1.5, 2.5, 3.0];

  arrf32.fill(1.0, 1, 3);
  assert(isArraysEqual<f32>(arrf32, [0.5, 1., 1., 2.5, 3.]));

  arrf32.fill(0.0);
  assert(isArraysEqual<f32>(arrf32, [0., 0., 0., 0., 0.]));

  arrf32.fill(1.0, 0, -3);
  assert(isArraysEqual<f32>(arrf32, [1., 1., 0., 0., 0.]));

  arrf32.fill(2.0, -2);
  assert(isArraysEqual<f32>(arrf32, [1., 1., 0., 2., 2.]));

  arrf32.fill(0.0, 1, 0);
  assert(isArraysEqual<f32>(arrf32, [1., 1., 0., 2., 2.]));

  arrf32.fill(-1.0);
  assert(isArraysEqual<f32>(arrf32, [-1., -1., -1., -1., -1.]));

  arrf32.fill(-0.0);
  assert(isArraysEqual<f32>(arrf32, [-0., -0., -0., -0., -0.]));
}

// Array#push/pop //////////////////////////////////////////////////////////////////////////////////

{
  assert(arr.length == 0);
  assert(internalCapacity<i32>(arr) == 8);

  arr.push(42);

  assert(arr[0] == 42);
  assert(arr.length == 1);
  assert(internalCapacity<i32>(arr) == 8);

  let i = arr.pop();

  assert(i == 42);
  assert(arr.length == 0);
  assert(internalCapacity<i32>(arr) == 8);

  arr.push(43);

  assert(arr.length == 1);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 43);

  arr.push(44);

  assert(arr.length == 2);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 43);
  assert(arr[1] == 44);

  arr.push(45);

  assert(arr.length == 3);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 43);
  assert(arr[1] == 44);
  assert(arr[2] == 45);
}

// Array#set:length ///////////////////////////////////////////////////////////////////////////////

{
  let arr: Ref[] = [new Ref(), new Ref()];
  arr.length = 0; // releases unused refs
  assert(arr.length == 0);
}

// Array#at ///////////////////////////////////////////////////////////////////////////////////////

{
  let arr: i32[] = [1, 2, 3, 4];

  assert(arr.at(0) == 1);
  assert(arr.at(3) == 4);
  assert(arr.at(-1) == 4);
  assert(arr.at(-4) == 1);
}

// Array#concat ///////////////////////////////////////////////////////////////////////////////////

{
  let other = new Array<i32>();

  let out = arr.concat(other);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr.length == 3);
  assert(out.length == 3);

  out.concat([]);
  assert(internalCapacity<i32>(arr) == 8);

  assert(out[0] == 43);
  assert(out[1] == 44);
  assert(out[2] == 45);

  other.push(46);
  other.push(47);

  out = arr.concat(other);

  assert(internalCapacity<i32>(arr) == 8);
  assert(other.length == 2);
  assert(out.length == 5);
  assert(out[0] == 43);
  assert(out[1] == 44);
  assert(out[2] == 45);
  assert(out[3] == 46);
  assert(out[4] == 47);

  out.pop();
  assert(out.length == 4);

  // TODO: wait for variable function parameters
  // out = arr.concat(null);
  // assert(out.length == 3);
  // assert(out[2] == 45);

  let source: i32[] = [];
  assert(source.length == 0);
  out = source.concat(arr);
  assert(out.length == 3);
  assert(source.length == 0);
}

// Array#copyWithin ////////////////////////////////////////////////////////////////////////////////

{
  let cwArr: i32[] = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(0, 3), [4, 5, 3, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(1, 3), [1, 4, 5, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(1, 2), [1, 3, 4, 5, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(2, 2), [1, 2, 3, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(0, 3, 4), [4, 2, 3, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(1, 3, 4), [1, 4, 3, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(1, 2, 4), [1, 3, 4, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(0, -2), [4, 5, 3, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(0, -2, -1), [4, 2, 3, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(-4, -3, -2), [1, 3, 3, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(-4, -3, -1), [1, 3, 4, 4, 5]));
  cwArr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(cwArr.copyWithin(-4, -3), [1, 3, 4, 5, 5]));
}

// Array#unshift ///////////////////////////////////////////////////////////////////////////////////

{
  arr.unshift(42);

  assert(arr.length == 4);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 42);
  assert(arr[1] == 43);
  assert(arr[2] == 44);
  assert(arr[3] == 45);

  arr.unshift(41);

  assert(arr.length == 5);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 41);
  assert(arr[1] == 42);
  assert(arr[2] == 43);
  assert(arr[3] == 44);
  assert(arr[4] == 45);
}

// Array#shift /////////////////////////////////////////////////////////////////////////////////////

var i: i32;
{
  i = arr.shift();

  assert(i == 41);
  assert(arr.length == 4);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 42);
  assert(arr[1] == 43);
  assert(arr[2] == 44);
  assert(arr[3] == 45);

  i = arr.pop();

  assert(i == 45);
  assert(arr.length == 3);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 42);
  assert(arr[1] == 43);
  assert(arr[2] == 44);
}

// Array#slice

{
  let result: i32[];
  const elements: i32[] = [3, 5, 7, 9, 11];

  result = elements.slice(2);
  assert(isArraysEqual(result, [7, 9, 11]));

  result = elements.slice(2, 4);
  assert(isArraysEqual(result, [7, 9]));

  result = elements.slice(1, 5);
  assert(isArraysEqual(result, [5, 7, 9, 11]));

  result = elements.slice();
  assert(isArraysEqual(result, elements));

  result = elements.slice(-2);
  assert(isArraysEqual(result, [9, 11]));

  result = elements.slice(2, -1);
  assert(isArraysEqual(result, [7, 9]));

  result = elements.slice(-3, -1);
  assert(isArraysEqual(result, [7, 9]));

  assert(elements.slice(-1, -3).length == 0);
  assert(elements.slice(10).length == 0);
}

// Array#reverse ///////////////////////////////////////////////////////////////////////////////////

{
  arr.reverse();

  assert(arr.length == 3);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 44);
  assert(arr[1] == 43);
  assert(arr[2] == 42);

  arr.push(43);
  arr.push(44);

  let bytes4 = ([0, 1, 2, 3] as u8[]).reverse();
  for (let i = 0, l = bytes4.length; i < l; i++) {
    assert(bytes4[i] == bytes4.length - i - 1);
  }

  let bytes8 = ([0, 1, 2, 3, 4, 5, 6, 7] as u8[]).reverse();
  for (let i = 0, l = bytes8.length; i < l; i++) {
    assert(bytes8[i] == bytes8.length - i - 1);
  }

  let bytes17 = ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] as u8[]).reverse();
  for (let i = 0, l = bytes17.length; i < l; i++) {
    assert(bytes17[i] == bytes17.length - i - 1);
  }

  let shorts7 = ([0, 1, 2, 3, 4, 5, 6] as u16[]).reverse();
  for (let i = 0, l = shorts7.length; i < l; i++) {
    assert(shorts7[i] == shorts7.length - i - 1);
  }

  let shorts8 = ([0, 1, 2, 3, 4, 5, 6, 7] as u16[]).reverse();
  for (let i = 0, l = shorts8.length; i < l; i++) {
    assert(shorts8[i] == shorts8.length - i - 1);
  }

  let shorts9 = ([0, 1, 2, 3, 4, 5, 6, 7, 8] as u16[]).reverse();
  for (let i = 0, l = shorts9.length; i < l; i++) {
    assert(shorts9[i] == shorts9.length - i - 1);
  }
}

// Array#indexOf ///////////////////////////////////////////////////////////////////////////////////

{
  i = arr.indexOf(44);
  assert(i == 0);

  i = arr.indexOf(42);
  assert(i == 2);

  i = arr.indexOf(45);
  assert(i == - 1);

  i = arr.indexOf(43, 100);
  assert(i == - 1);

  i = arr.indexOf(43, -100);
  assert(i == 1);

  i = arr.indexOf(43, -2);
  assert(i == 3);

  i = arr.indexOf(43, -4);
  assert(i == 1);

  i = arr.indexOf(43, 0);
  assert(i == 1);

  i = arr.indexOf(43, 1);
  assert(i == 1);

  i = arr.indexOf(43, 2);
  assert(i == 3);

  assert(([NaN] as f32[]).indexOf(NaN) == -1);
  assert(([NaN] as f64[]).indexOf(NaN) == -1);
}

// Array#lastIndexOf

{
  const numbers: i32[] = [2, 5, 9, 2];
  assert(numbers.lastIndexOf(2) == 3);
  assert(numbers.lastIndexOf(7) == -1);
  assert(numbers.lastIndexOf(2, 3) == 3);
  assert(numbers.lastIndexOf(2, 2) == 0);
  assert(numbers.lastIndexOf(2, -2) == 0);
  assert(numbers.lastIndexOf(2, -1) == 3);

}

// Array#includes //////////////////////////////////////////////////////////////////////////////////

{
  let includes = arr.includes(44);
  assert(includes == true);

  includes = arr.includes(42);
  assert(includes == true);

  includes = arr.includes(45);
  assert(includes == false);

  includes = arr.includes(43, 100);
  assert(includes == false);

  includes = arr.includes(43, -100);
  assert(includes == true);

  includes = arr.includes(43, -2);
  assert(includes == true);

  includes = arr.includes(43, -4);
  assert(includes == true);

  includes = arr.includes(43, 0);
  assert(includes == true);

  includes = arr.includes(43, 1);
  assert(includes == true);

  includes = arr.includes(43, 2);
  assert(includes == true);

  assert(([NaN] as f32[]).includes(NaN));
  assert(([NaN] as f64[]).includes(NaN));

  arr.splice(1, 1);

  assert(arr.length == 4);
  assert(internalCapacity<i32>(arr) == 8);
  assert(arr[0] == 44);
  assert(arr[1] == 42);
}

// Array#splice ////////////////////////////////////////////////////////////////////////////////////

{
  let sarr: i32[] = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(0), [1, 2, 3, 4, 5]));
  assert(isArraysEqual<i32>(sarr, []));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(0, 0), []));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3, 4, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(2), [3, 4, 5]));
  assert(isArraysEqual<i32>(sarr, [1, 2]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(2, 2), [3, 4]));
  assert(isArraysEqual<i32>(sarr, [1, 2, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(0, 1), [1]));
  assert(isArraysEqual<i32>(sarr, [2, 3, 4, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(-1), [5]));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3, 4]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(-2), [4, 5]));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(-2, 1), [4]));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(-7, 1), [1]));
  assert(isArraysEqual<i32>(sarr, [2, 3, 4, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(-2, -1), []));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3, 4, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(1, -2), []));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3, 4, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(4, 0), []));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3, 4, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(7, 0), []));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3, 4, 5]));

  sarr = [1, 2, 3, 4, 5];
  assert(isArraysEqual<i32>(sarr.splice(7, 5), []));
  assert(isArraysEqual<i32>(sarr, [1, 2, 3, 4, 5]));

  let refArr: Ref[] = [];
  let spliced = refArr.splice(1, 2);
  assert(spliced.length == 0);
  assert(refArr.length == 0);

  refArr = [new Ref(1), new Ref(2), new Ref(3), new Ref(4), new Ref(5)];
  spliced = refArr.splice(2, 2);

  assert(spliced.length == 2);
  assert(spliced[0].v == 3);
  assert(spliced[1].v == 4);

  assert(refArr.length == 3);
  assert(refArr[0].v == 1);
  assert(refArr[1].v == 2);
  assert(refArr[2].v == 5);

  let refArr2: (Ref | null)[] = [new Ref(1), null, new Ref(2)];
  let spliced2 = refArr2.splice(0, 1);

  assert(spliced2.length == 1);
  assert(spliced2[0]!.v == 1);

  assert(refArr2.length == 2);
  assert(refArr2[0] == null);
  assert(refArr2[1]!.v == 2);
}

// Array#findIndex /////////////////////////////////////////////////////////////////////////////////

{
  arr[0] = 0;
  arr[1] = 1;
  arr[2] = 2;
  arr[3] = 3;

  i = arr.findIndex((value: i32) => value == 0);

  assert(i == 0);

  i = arr.findIndex((value: i32) => value == 1);
  assert(i == 1);

  i = arr.findIndex((value: i32) => value == 100);
  assert(i == -1);

  // Test side effect push
  i = arr.findIndex((value: i32, _: i32, array: Array<i32>) => {
    array.push(100); // push side effect should not affect this method by spec
    return value == 100;
  });
  // array should be changed, but this method result should be calculated for old array length
  assert(i == -1);
  assert(arr.length == 8);
  i = arr.findIndex((value: i32) => value == 100);
  assert(i != -1);

  arr.pop();
  arr.pop();
  arr.pop();
  arr.pop();

  // Test side effect pop
  i = arr.findIndex((value: i32, _: i32, array: Array<i32>) => {
    array.pop(); // popped items shouldn't be looked up, and we shouldn't go out of bounds
    return value == 100;
  });
  // only 2 first items was looked up, since last 2 was removed by .pop()
  assert(i == -1);
  assert(arr.length == 2);

  arr.push(2);
  arr.push(3);
}

// Array#findLastIndex /////////////////////////////////////////////////////////////////////////////

{
  let intArr = [0, 1, 2, 3];

  i = intArr.findLastIndex(value => value == 0);

  assert(i == 0);

  i = intArr.findLastIndex(value => value == 1);
  assert(i == 1);

  i = intArr.findLastIndex(value => value == 100);
  assert(i == -1);

  // Test side effect pop
  i = intArr.findLastIndex((value, _, array) => {
    // @ts-ignore
    array.pop(); // popped items shouldn't be looked up, and we shouldn't go out of bounds
    return value == 100;
  });

  assert(i == -1);
}

// Array#every /////////////////////////////////////////////////////////////////////////////////////

{
  let every = arr.every((value: i32) => value >= 0);
  assert(every == true);

  every = arr.every((value: i32) => value <= 0);
  assert(every == false);

  // Test side effect push
  every = arr.every((value: i32, _: i32, array: Array<i32>) => {
    array.push(100); // push side effect should not affect this method by spec
    return value < 10;
  });
  // array should be changed, but this method result should be calculated for old array length
  assert(every == true);
  assert(arr.length == 8);
  every = arr.every((value: i32) => value < 10);
  assert(every == false);

  arr.pop();
  arr.pop();
  arr.pop();
  arr.pop();

  // Test side effect pop
  every = arr.every((value: i32, _: i32, array: Array<i32>) => {
    array.pop(); // popped items shouldn't be looked up, and we shouldn't go out of bounds
    return value < 3;
  });
  // only 2 first items was looked up, since last 2 was removed by .pop()
  assert(every == true);
  assert(arr.length == 2);

  arr.push(2);
  arr.push(3);
}

// Array#some //////////////////////////////////////////////////////////////////////////////////////

{
  let some = arr.some((value: i32) => value >= 3);
  assert(some == true);

  some = arr.some((value: i32) => value <= -1);
  assert(some == false);

  // Test side effect push
  some = arr.some((value: i32, _: i32, array: Array<i32>) => {
    array.push(100); // push side effect should not affect this method by spec
    return value > 10;
  });
  // array should be changed, but this method result should be calculated for old array length
  assert(some == false);
  assert(arr.length == 8);
  some = arr.some((value: i32) => value > 10);
  assert(some == true);

  arr.pop();
  arr.pop();
  arr.pop();
  arr.pop();

  // Test side effect pop
  some = arr.some((value: i32, _: i32, array: Array<i32>) => {
    array.pop(); // popped items shouldn't be looked up, and we shouldn't go out of bounds
    return value > 3;
  });
  // only 2 first items was looked up, since last 2 was removed by .pop()
  assert(some == false);
  assert(arr.length == 2);

  arr.push(2);
  arr.push(3);
}

// Array#forEach ///////////////////////////////////////////////////////////////////////////////////

{
  i = 0;
  arr.forEach((value: i32) => { i += value; });
  assert(i == 6);

  // Test side effect push
  i = 0;
  arr.forEach((value: i32, _: i32, array: Array<i32>) => {
    array.push(100); // push side effect should not affect this method by spec
    i += value;
  });
  // array should be changed, but this method result should be calculated for old array length
  assert(i == 6);
  assert(arr.length == 8);
  i = 0;
  arr.forEach((value: i32) => { i += value; });
  assert(i == 406);

  arr.pop();
  arr.pop();
  arr.pop();
  arr.pop();

  // Test side effect pop
  i = 0;
  arr.forEach((value: i32, _: i32, array: Array<i32>) => {
    array.pop(); // popped items shouldn't be looked up, and we shouldn't go out of bounds
    i += value;
  });
  // only 2 first items was looked up, since last 2 was removed by .pop()
  assert(i == 1);
  assert(arr.length == 2);

  arr.push(2);
  arr.push(3);

  // Test rehash action effec
  arr.forEach((value: i32, index: i32, array: Array<i32>) => {
    if (index == 0) {
      for (let i = 0; i < 4; i++) {
        array.pop();
      }
      for (let i = 0; i < 100; i++) {
        array.push(100 + i);
      }
      for (let i = 0; i < 100; i++) {
        array.pop();
      }
      for (let i = 0; i < 100; i++) {
        array.push(i + 200);
      }
    }
    if (index == 2) {
      assert(value == 202);
    }
  });
  assert(arr.length == 100);
  for (let i = 0; i < 100; i++) {
    arr.pop();
  }
  arr.push(0);
  arr.push(1);
  arr.push(2);
  arr.push(3);
}

// Array#map ///////////////////////////////////////////////////////////////////////////////////////

{
  let arrStr1 = arr.map((value: i32) => value.toString());

  let newArr = arr.map((value: i32) => <f32>value);
  assert(newArr.length == 4);
  assert(newArr[0] == <f32>arr[0]);

  // Test side effect push
  i = 0;
  arr.map<i32>((value: i32, _: i32, array: Array<i32>) => {
    array.push(100); // push side effect should not affect this method by spec
    i += value;
    return value;
  });
  assert(i == 6);
  assert(arr.length == 8);

  i = 0;
  arr.map<i32>((value: i32) => {
    i += value;
    return value;
  });
  assert(i == 406);

  arr.pop();
  arr.pop();
  arr.pop();
  arr.pop();

  // Test side effect pop
  i = 0;
  arr.map<i32>((value: i32, _: i32, array: Array<i32>) => {
    array.pop(); // popped items shouldn't be looked up, and we shouldn't go out of bounds
    i += value;
    return value;
  });
  // only 2 first items was looked up, since last 2 was removed by .pop()
  assert(i == 1);
  assert(arr.length == 2);

  arr.push(2);
  arr.push(3);
}

// Array#filter ////////////////////////////////////////////////////////////////////////////////////

{
  let filteredArr: i32[] = arr.filter((value: i32) => value >= 2);
  assert(filteredArr.length == 2);

  // Test side effect push
  i = 0;
  arr.filter((value: i32, _: i32, array: Array<i32>) => {
    array.push(100); // push side effect should not affect this method by spec
    i += value;
    return value >= 2;
  });
  assert(i == 6);
  assert(arr.length == 8);

  i = 0;
  arr.filter((value: i32) => {
    i += value;
    return value >= 2;
  });
  assert(i == 406);

  arr.pop();
  arr.pop();
  arr.pop();
  arr.pop();

  // Test side effect pop
  i = 0;
  arr.filter((value: i32, _: i32, array: Array<i32>) => {
    array.pop(); // popped items shouldn't be looked up, and we shouldn't go out of bounds
    i += value;
    return value >= 2;
  });
  // only 2 first items was looked up, since last 2 was removed by .pop()
  assert(i == 1);
  assert(arr.length == 2);

  arr.push(2);
  arr.push(3);
}

// Array#reduce ////////////////////////////////////////////////////////////////////////////////////

{
  i = arr.reduce<i32>(((prev: i32, current: i32): i32 => prev + current), 0);
  assert(i == 6);

  // init value
  i = arr.reduce(((prev: i32, current: i32): i32 => prev + current), 4);
  assert(i == 10);

  let boolVal = arr.reduce(((prev: bool, current: i32): bool => prev || current > 2), false);
  assert(boolVal == true);

  boolVal = arr.reduce<bool>(((prev: bool, current: i32): bool => prev || current > 100), false);
  assert(boolVal == false);

  // Test side effect push
  i = arr.reduce<i32>(((prev: i32, current: i32, _: i32, array: Array<i32>): i32 => {
    array.push(1); // push side effect should not affect this method by spec
    return prev + current;
  }), 0);
  // array should be changed, but this method result should be calculated for old array length
  assert(i == 6);
  assert(arr.length == 8);
  i = arr.reduce(((prev: i32, current: i32): i32 => prev + current), 0);
  assert(i == 10);

  arr.pop();
  arr.pop();
  arr.pop();
  arr.pop();

  // Test side effect pop
  i = arr.reduce(((prev: i32, current: i32, _: i32, array: Array<i32>): i32 => {
    array.pop(); // popped items shouldn't be reduced, and we shouldn't go out of bounds
    return prev + current;
  }), 0);
  // only 2 first items was reduced, since last 2 was removed by .pop()
  assert(i == 1);
  assert(arr.length == 2);

  arr.push(2);
  arr.push(3);
}

// Array#reduceRight ///////////////////////////////////////////////////////////////////////////////

{
  i = arr.reduceRight<i32>(((prev: i32, current: i32): i32 => prev + current), 0);
  assert(i == 6);

  // init value
  i = arr.reduceRight(((prev: i32, current: i32): i32 => prev + current), 4);
  assert(i == 10);

  let boolVal = arr.reduceRight<bool>(((prev: bool, current: i32): bool => prev || current > 2), false);
  assert(boolVal == true);

  boolVal = arr.reduceRight(((prev: bool, current: i32): bool => prev || current > 100), false);
  assert(boolVal == false);

  // Test side effect push
  i = arr.reduceRight<i32>(((prev: i32, current: i32, _: i32, array: Array<i32>): i32 => {
    array.push(1); // push side effect should not affect this method by spec
    return prev + current;
  }), 0);
  // array should be changed, but this method result should be calculated for old array length
  assert(i == 6);
  assert(arr.length == 8);
  i = arr.reduceRight(((prev: i32, current: i32): i32 => prev + current), 0);
  assert(i == 10);

  arr.pop();
  arr.pop();
  arr.pop();
  arr.pop();

  // Test side effect pop
  i = arr.reduceRight(((prev: i32, current: i32, _: i32, array: Array<i32>): i32 => {
    array.pop(); // popped items should be reduced
    return prev + current;
  }), 0);

  assert(i == 6);
  assert(arr.length == 0);

  arr.push(0);
  arr.push(1);
  arr.push(2);
  arr.push(3);
}

// Array#sort //////////////////////////////////////////////////////////////////////////////////////

// Checks if an array is properly sorted
function isSorted<T>(data: Array<T>, comparator: (a: T, b: T) => i32 = COMPARATOR<T>()): bool {
  for (let i = 1, len = data.length; i < len; i++) {
    if (comparator(data[i - 1], data[i]) > 0) return false;
  }
  return true;
}

function createReverseOrderedArray(size: i32): Array<i32> {
  var arr = new Array<i32>(size);
  for (let i = 0; i < size; i++) {
    arr[i] = size - 1 - i;
  }
  return arr;
}

NativeMath.seedRandom(reinterpret<u64>(JSMath.random()));

function createRandomOrderedArray(size: i32): Array<i32> {
  var arr = new Array<i32>(size);
  for (let i = 0; i < size; i++) {
    arr[i] = <i32>(NativeMath.random() * size);
  }
  return arr;
}

function createReverseOrderedNestedArray(size: i32): Array<Array<i32>> {
  var arr = new Array<Array<i32>>(size);
  for (let i = 0; i < size; i++) {
    let inner = new Array<i32>(1);
    inner[0] = size - 1 - i;
    arr[i] = inner;
  }
  return arr;
}

class Proxy<T> {
  constructor(public x: T) {}
}

class Dim {
  height: i32;
  width: i32;
}

function createReverseOrderedElementsArray(size: i32): Array<Proxy<i32>> {
  var arr = new Array<Proxy<i32>>(size);
  for (let i = 0; i < size; i++) {
    arr[i] = new Proxy<i32>(size - 1 - i);
  }
  return arr;
}

const charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-,.+/\\[]{}()<>*&$%^@#!?";

let inputStabArr: Array<Dim> = [
  { height: 100, width: 80  },
  { height: 90,  width: 90  },
  { height: 70,  width: 95  },
  { height: 100, width: 100 },
  { height: 80,  width: 110 },
  { height: 110, width: 115 },
  { height: 100, width: 120 },
  { height: 70,  width: 125 },
  { height: 70,  width: 130 },
  { height: 100, width: 135 },
  { height: 75,  width: 140 },
  { height: 70,  width: 140 }
];

let outputStabArr: Array<Dim> = [
  { height: 70,  width: 95  },
  { height: 70,  width: 125 },
  { height: 70,  width: 130 },
  { height: 70,  width: 140 },
  { height: 75,  width: 140 },
  { height: 80,  width: 110 },
  { height: 90,  width: 90  },
  { height: 100, width: 80  },
  { height: 100, width: 100 },
  { height: 100, width: 120 },
  { height: 100, width: 135 },
  { height: 110, width: 115 }
];

function createRandomString(len: i32): string {
  var result = "";

  for (let i = 0; i < len; i++) {
    result += charset.charAt(<i32>(NativeMath.floor(NativeMath.random() * charset.length)));
  }
  return result;
}

function createRandomStringArray(size: i32): Array<string> {
  var arr = new Array<string>(size);
  for (let i = 0; i < size; i++) {
    arr[i] = createRandomString(<i32>(NativeMath.random() * 32));
  }
  return arr;
}

function assertStableSortedForComplexObjects(): void {
  let sorted = inputStabArr.slice(0).sort((a, b) => a.height - b.height);
  let check = true;
  for (let i = 0, len = inputStabArr.length; i < len; i++) {
    let input = sorted[i];
    let target = outputStabArr[i];
    if (input.height != target.height || input.width != target.width) {
      check = false;
      break;
    }
  }
  assert(check);
}

function assertSorted<T>(arr: Array<T>, comparator: (a: T, b: T) => i32 = COMPARATOR<T>()): void {
  assert(isSorted<T>(arr.sort(comparator), comparator));
}

function assertSortedDefault<T>(arr: Array<T>): void {
  assertSorted<T>(arr, COMPARATOR<T>());
}

// Tests for default comparator
{
  let f32ArrayTypedSmall: f32[] = [2.0, -1.0, 0.0];
  f32ArrayTypedSmall.sort();
  assert(isArraysEqual<f32>(f32ArrayTypedSmall, [-1.0, 0.0, 2.0]));

  let f32ArrayTyped: f32[] = [1.0, NaN, -Infinity, 1.00000001, 0.0, -1.0, -2.0, +Infinity];
  f32ArrayTyped.sort();
  assert(isArraysEqual<f32>(f32ArrayTyped, [-Infinity, -2.0, -1.0, 0.0, 1.0, 1.00000001, Infinity, NaN]));

  let f64ArrayTyped: f64[] = [1.0, NaN, -Infinity, 1.000000000000001, 0.0, -1.0, -2.0, +Infinity];
  f64ArrayTyped.sort();
  assert(isArraysEqual<f64>(f64ArrayTyped, [-Infinity, -2.0, -1.0, 0.0, 1.0, 1.000000000000001, Infinity, NaN]));

  let i32ArrayTyped: i32[] = [1, -2, -1, 0, 2];
  i32ArrayTyped.sort();
  assert(isArraysEqual<i32>(i32ArrayTyped, [-2, -1, 0, 1, 2]));

  let u32ArrayTyped: u32[] = [1, 4294967295, 4294967294, 0, 2];
  u32ArrayTyped.sort();
  assert(isArraysEqual<u32>(u32ArrayTyped, [0, 1, 2, 4294967294, 4294967295]));

  let reversed0: i32[] = [];
  let reversed1: i32[] = [1];
  let reversed2: i32[] = [2, 1];
  let reversed4: i32[] = [3, 2, 1, 0];
  let expected4: i32[] = [0, 1, 2, 3];

  let reversed64    = createReverseOrderedArray(64);
  let reversed128   = createReverseOrderedArray(128);
  let reversed1024  = createReverseOrderedArray(1024);
  let reversed10000 = createReverseOrderedArray(10000);

  let randomized512 = createRandomOrderedArray(512);

  // Test sorting with with default comparator

  assertSortedDefault<i32>(reversed0);

  assertSortedDefault<i32>(reversed1);
  assert(isArraysEqual<i32>(reversed1, [1]));

  assertSortedDefault<i32>(reversed2);
  assert(isArraysEqual<i32>(reversed2, [1, 2]));

  assertSortedDefault<i32>(reversed4);
  assert(isArraysEqual<i32>(reversed4, expected4));

  assertSortedDefault<i32>(reversed64);
  assert(isArraysEqual<i32>(reversed64, expected4, 4));

  assertSortedDefault<i32>(reversed128);
  assert(isArraysEqual<i32>(reversed128, expected4, 4));

  assertSortedDefault<i32>(reversed1024);
  assert(isArraysEqual<i32>(reversed1024, expected4, 4));

  assertSortedDefault<i32>(reversed10000);
  assert(isArraysEqual<i32>(reversed10000, expected4, 4));

  assertSortedDefault<i32>(randomized512);

  assertStableSortedForComplexObjects();
}

// Test sorting with custom comparator

{
  let randomized64  = createRandomOrderedArray(64);
  let randomized257 = createRandomOrderedArray(257);

  assertSorted<i32>(randomized64, (a: i32, b: i32) => a - b);
  assertSorted<i32>(randomized64, (a: i32, b: i32) => b - a);

  assertSorted<i32>(randomized257, (a: i32, b: i32) => a - b);
  assertSorted<i32>(randomized257, (a: i32, b: i32) => b - a);
}

// Test sorting complex objects
{
  let reversedNested512 = createReverseOrderedNestedArray(2);
  assertSorted<i32[]>(reversedNested512, (a: i32[], b: i32[]) => a[0] - b[0]);
}

// Test sorting reference elements
{
  let reversedElements512 = createReverseOrderedElementsArray(512);
  assertSorted<Proxy<i32>>(reversedElements512, (a: Proxy<i32>, b: Proxy<i32>) => a.x - b.x);
}

// Test sorting strings

{
  let randomStringsActual:   (string | null)[] = ["a", "b", "a", "ab", "ba", "", null];
  let randomStringsExpected: (string | null)[] = ["", "a", "a", "ab", "b", "ba", null];

  assertSorted<string | null>(randomStringsActual);
  assert(isArraysEqual<string | null>(randomStringsActual, randomStringsExpected));

  let randomStrings400 = createRandomStringArray(400);
  assertSorted<string>(randomStrings400);
}

// Array#join //////////////////////////////////////////////////////////////////////////////////////

{
  assert((<bool[]>[true, false]).join() == "true,false");
  assert((<i32[]>[1,-2,-3]).join("") == "1-2-3");
  assert((<u32[]>[1, 2, 3]).join("-") == "1-2-3");
  assert((<i32[]>[i32.MIN_VALUE, i32.MIN_VALUE]).join("__") == "-2147483648__-2147483648");
  assert((<f64[]>[0.0, 1.0, -2.0, NaN, -Infinity, Infinity]).join(", ") == "0.0, 1.0, -2.0, NaN, -Infinity, Infinity");
  assert((<Array<string | null>>["", "1", null]).join("") == "1");
  let refArr: (Ref | null)[] = [new Ref(), null, new Ref()];
  assert(refArr.join() == "[object Object],,[object Object]");

  let refArr2: Ref[] = [new Ref(), new Ref()];
  assert(refArr2.join() == "[object Object],[object Object]");
}

// Array#toString //////////////////////////////////////////////////////////////////////////////////
{
  let arr0: i32[] = [];
  let arr1: i32[] = [1];
  let arr2: i32[] = [1,2];
  let arr3: i32[] = [0,1,2,3];

  assert(arr0.toString() == "");
  assert(arr1.toString() == "1");
  assert(arr2.toString() == "1,2");
  assert(arr3.toString() == "0,1,2,3");

  assert((<i8[]>[1, -1, 0]).toString() == "1,-1,0");
  assert((<i8[]>[-128, -127, -128]).toString() == "-128,-127,-128");
  assert((<u16[]>[1, 0xFFFF, 0]).toString() == "1,65535,0");
  assert((<i16[]>[-0x8000, -0xFF]).toString() == "-32768,-255");
  assert((<i32[]>[-0x80000000, -0x80]).toString() == "-2147483648,-128");
  assert((<u64[]>[1, 0xFFFFFFFFFFFFFFFF, 0]).toString() == "1,18446744073709551615,0");
  assert(
    (<i64[]>[-1, -1234567890123456, i64.MIN_VALUE, 0, i64.MAX_VALUE]).toString() ==
    "-1,-1234567890123456,-9223372036854775808,0,9223372036854775807"
  );

  let arrStr: (string | null)[] = ["", "a", "a", "ab", "b", "ba", null];

  assert(arrStr.toString() == ",a,a,ab,b,ba,");
  assert((<Array<string | null>>["1", "2", null, "4"]).toString() == "1,2,,4");

  let subarr32: i32[][] = [[1,2], [3,4]];
  assert(subarr32.toString() == "1,2,3,4");

  let subarr8: u8[][] = [[1,2], [3,4]];
  assert(subarr8.toString() == "1,2,3,4");

  let subarrU32: u32[][][] = [[[1]]];
  assert(subarrU32.toString() == "1");
}

// Array#flat //////////////////////////////////////////////////////////////////////////////////
{
  let plainTarget: i32[][] = [[0], [1, 2, 3], [4, 5, 6], [7, 8, 9]];
  let plainResult = plainTarget.flat();
  assert(plainResult.length == 10);
  for (let i = 0; i < 10; i++) {
    assert(plainResult[i] == i);
  }

  let stringTarget: Array<Array<string | null>> = [["one"], ["two", null, "three"], ["four", "five", "six"], ["seven"]];
  let stringResult = stringTarget.flat();
  let expected = ["one", "two", null, "three", "four", "five", "six", "seven"];
  assert(stringResult.length == 8);
  for (let i = 0; i < expected.length; i++) {
    assert(stringResult[i] == expected[i]);
  }

  let testArray: i32[][] = [[], []];
  assert(testArray.flat().length == 0);

  // see: https://github.com/AssemblyScript/assemblyscript/issues/2018
  let mapTarget: i32[][] = [[1], [2]];
  let mapResult = mapTarget.map<i32[]>(nestedArray => {
    assert(nestedArray.length == 1);
    nestedArray.push(3);
    assert(nestedArray.length == 2);
    return nestedArray;
  }).flat();
  assert(mapResult.length == 4);
  assert(mapResult[0] == 1);
  assert(mapResult[1] == 3);
  assert(mapResult[2] == 2);
  assert(mapResult[3] == 3);
}

// Unleak globals
arr = changetype<Array<i32>>(0);
inputStabArr = changetype<Array<Dim>>(0);
outputStabArr = changetype<Array<Dim>>(0);

__stack_pointer = __heap_base;
__collect();