array.js

'use strict';

let List = require("./list.js");
let Primitive_array = require("./primitive_array.js");
let Primitive_exceptions = require("./primitive_exceptions.js");

let init = ((length, f) => Array.from({ length }, f));

function make(len, x) {
  return init(len, param => x);
}

function unsafe_sub(array, offset, length) {
  return array.slice(offset, offset + length | 0);
}

function concat(list) {
  return List.fold_left((arr1, arr2) => arr1.concat(arr2), [], list);
}

function create_float(len) {
  return init(len, param => 0.0);
}

function make_matrix(sx, sy, init$1) {
  let x = [];
  let res = init(sx, param => x);
  for (let x$1 = 0; x$1 < sx; ++x$1) {
    res[x$1] = init(sy, param => init$1);
  }
  return res;
}

function append(a1, a2) {
  let l1 = a1.length;
  if (l1 === 0) {
    return a2.slice();
  } else if (a2.length === 0) {
    return unsafe_sub(a1, 0, l1);
  } else {
    return a1.concat(a2);
  }
}

function sub(a, ofs, len) {
  if (ofs < 0 || len < 0 || ofs > (a.length - len | 0)) {
    throw {
      RE_EXN_ID: "Invalid_argument",
      _1: "Array.sub",
      Error: new Error()
    };
  }
  return unsafe_sub(a, ofs, len);
}

function fill(a, ofs, len, v) {
  if (ofs < 0 || len < 0 || ofs > (a.length - len | 0)) {
    throw {
      RE_EXN_ID: "Invalid_argument",
      _1: "Array.fill",
      Error: new Error()
    };
  }
  for (let i = ofs, i_finish = ofs + len | 0; i < i_finish; ++i) {
    a[i] = v;
  }
}

function blit(a1, ofs1, a2, ofs2, len) {
  if (len < 0 || ofs1 < 0 || ofs1 > (a1.length - len | 0) || ofs2 < 0 || ofs2 > (a2.length - len | 0)) {
    throw {
      RE_EXN_ID: "Invalid_argument",
      _1: "Array.blit",
      Error: new Error()
    };
  }
  for (let i = 0; i < len; ++i) {
    a2[ofs2 + i | 0] = a1[ofs1 + i | 0];
  }
}

function iter(f, a) {
  for (let i = 0, i_finish = a.length; i < i_finish; ++i) {
    f(a[i]);
  }
}

function iter2(f, a, b) {
  if (a.length !== b.length) {
    throw {
      RE_EXN_ID: "Invalid_argument",
      _1: "Array.iter2: arrays must have the same length",
      Error: new Error()
    };
  }
  for (let i = 0, i_finish = a.length; i < i_finish; ++i) {
    f(a[i], b[i]);
  }
}

function map(f, a) {
  let l = a.length;
  if (l === 0) {
    return [];
  }
  let x = f(a[0]);
  let r = init(l, param => x);
  for (let i = 1; i < l; ++i) {
    r[i] = f(a[i]);
  }
  return r;
}

function map2(f, a, b) {
  let la = a.length;
  let lb = b.length;
  if (la !== lb) {
    throw {
      RE_EXN_ID: "Invalid_argument",
      _1: "Array.map2: arrays must have the same length",
      Error: new Error()
    };
  }
  if (la === 0) {
    return [];
  }
  let x = f(a[0], b[0]);
  let r = init(la, param => x);
  for (let i = 1; i < la; ++i) {
    r[i] = f(a[i], b[i]);
  }
  return r;
}

function iteri(f, a) {
  for (let i = 0, i_finish = a.length; i < i_finish; ++i) {
    f(i, a[i]);
  }
}

function mapi(f, a) {
  let l = a.length;
  if (l === 0) {
    return [];
  }
  let x = f(0, a[0]);
  let r = init(l, param => x);
  for (let i = 1; i < l; ++i) {
    r[i] = f(i, a[i]);
  }
  return r;
}

function to_list(a) {
  let _i = a.length - 1 | 0;
  let _res = /* [] */0;
  while (true) {
    let res = _res;
    let i = _i;
    if (i < 0) {
      return res;
    }
    _res = {
      hd: a[i],
      tl: res
    };
    _i = i - 1 | 0;
    continue;
  };
}

function list_length(_accu, _param) {
  while (true) {
    let param = _param;
    let accu = _accu;
    if (!param) {
      return accu;
    }
    _param = param.tl;
    _accu = accu + 1 | 0;
    continue;
  };
}

function of_list(param) {
  if (!param) {
    return [];
  }
  let hd = param.hd;
  let len = list_length(0, param);
  let a = init(len, param => hd);
  let _i = 1;
  let _param = param.tl;
  while (true) {
    let param$1 = _param;
    let i = _i;
    if (!param$1) {
      return a;
    }
    a[i] = param$1.hd;
    _param = param$1.tl;
    _i = i + 1 | 0;
    continue;
  };
}

function fold_left(f, x, a) {
  let r = x;
  for (let i = 0, i_finish = a.length; i < i_finish; ++i) {
    r = f(r, a[i]);
  }
  return r;
}

function fold_right(f, a, x) {
  let r = x;
  for (let i = a.length - 1 | 0; i >= 0; --i) {
    r = f(a[i], r);
  }
  return r;
}

function exists(p, a) {
  let n = a.length;
  let _i = 0;
  while (true) {
    let i = _i;
    if (i === n) {
      return false;
    }
    if (p(a[i])) {
      return true;
    }
    _i = i + 1 | 0;
    continue;
  };
}

function for_all(p, a) {
  let n = a.length;
  let _i = 0;
  while (true) {
    let i = _i;
    if (i === n) {
      return true;
    }
    if (!p(a[i])) {
      return false;
    }
    _i = i + 1 | 0;
    continue;
  };
}

function mem(x, a) {
  let n = a.length;
  let _i = 0;
  while (true) {
    let i = _i;
    if (i === n) {
      return false;
    }
    if (a[i] === x) {
      return true;
    }
    _i = i + 1 | 0;
    continue;
  };
}

function memq(x, a) {
  let n = a.length;
  let _i = 0;
  while (true) {
    let i = _i;
    if (i === n) {
      return false;
    }
    if (x === a[i]) {
      return true;
    }
    _i = i + 1 | 0;
    continue;
  };
}

let Bottom = /* @__PURE__ */Primitive_exceptions.create("Array.Bottom");

function sort(cmp, a) {
  let maxson = (l, i) => {
    let i31 = ((i + i | 0) + i | 0) + 1 | 0;
    let x = i31;
    if ((i31 + 2 | 0) < l) {
      if (cmp(Primitive_array.get(a, i31), Primitive_array.get(a, i31 + 1 | 0)) < 0) {
        x = i31 + 1 | 0;
      }
      if (cmp(Primitive_array.get(a, x), Primitive_array.get(a, i31 + 2 | 0)) < 0) {
        x = i31 + 2 | 0;
      }
      return x;
    }
    if ((i31 + 1 | 0) < l && cmp(Primitive_array.get(a, i31), Primitive_array.get(a, i31 + 1 | 0)) < 0) {
      return i31 + 1 | 0;
    }
    if (i31 < l) {
      return i31;
    }
    throw {
      RE_EXN_ID: Bottom,
      _1: i,
      Error: new Error()
    };
  };
  let trickle = (l, i, e) => {
    try {
      let _i = i;
      while (true) {
        let i$1 = _i;
        let j = maxson(l, i$1);
        if (cmp(Primitive_array.get(a, j), e) <= 0) {
          return Primitive_array.set(a, i$1, e);
        }
        Primitive_array.set(a, i$1, Primitive_array.get(a, j));
        _i = j;
        continue;
      };
    } catch (raw_i) {
      let i$2 = Primitive_exceptions.internalToException(raw_i);
      if (i$2.RE_EXN_ID === Bottom) {
        return Primitive_array.set(a, i$2._1, e);
      }
      throw i$2;
    }
  };
  let bubble = (l, i) => {
    try {
      let _i = i;
      while (true) {
        let i$1 = _i;
        let j = maxson(l, i$1);
        Primitive_array.set(a, i$1, Primitive_array.get(a, j));
        _i = j;
        continue;
      };
    } catch (raw_i) {
      let i$2 = Primitive_exceptions.internalToException(raw_i);
      if (i$2.RE_EXN_ID === Bottom) {
        return i$2._1;
      }
      throw i$2;
    }
  };
  let trickleup = (_i, e) => {
    while (true) {
      let i = _i;
      let father = (i - 1 | 0) / 3 | 0;
      if (i === father) {
        throw {
          RE_EXN_ID: "Assert_failure",
          _1: [
            "array.res",
            294,
            4
          ],
          Error: new Error()
        };
      }
      if (cmp(Primitive_array.get(a, father), e) >= 0) {
        return Primitive_array.set(a, i, e);
      }
      Primitive_array.set(a, i, Primitive_array.get(a, father));
      if (father <= 0) {
        return Primitive_array.set(a, 0, e);
      }
      _i = father;
      continue;
    };
  };
  let l = a.length;
  for (let i = ((l + 1 | 0) / 3 | 0) - 1 | 0; i >= 0; --i) {
    trickle(l, i, Primitive_array.get(a, i));
  }
  for (let i$1 = l - 1 | 0; i$1 >= 2; --i$1) {
    let e = Primitive_array.get(a, i$1);
    Primitive_array.set(a, i$1, Primitive_array.get(a, 0));
    trickleup(bubble(i$1, 0), e);
  }
  if (l <= 1) {
    return;
  }
  let e$1 = Primitive_array.get(a, 1);
  Primitive_array.set(a, 1, Primitive_array.get(a, 0));
  Primitive_array.set(a, 0, e$1);
}

function stable_sort(cmp, a) {
  let merge = (src1ofs, src1len, src2, src2ofs, src2len, dst, dstofs) => {
    let src1r = src1ofs + src1len | 0;
    let src2r = src2ofs + src2len | 0;
    let _i1 = src1ofs;
    let _s1 = Primitive_array.get(a, src1ofs);
    let _i2 = src2ofs;
    let _s2 = Primitive_array.get(src2, src2ofs);
    let _d = dstofs;
    while (true) {
      let d = _d;
      let s2 = _s2;
      let i2 = _i2;
      let s1 = _s1;
      let i1 = _i1;
      if (cmp(s1, s2) <= 0) {
        Primitive_array.set(dst, d, s1);
        let i1$1 = i1 + 1 | 0;
        if (i1$1 >= src1r) {
          return blit(src2, i2, dst, d + 1 | 0, src2r - i2 | 0);
        }
        _d = d + 1 | 0;
        _s1 = Primitive_array.get(a, i1$1);
        _i1 = i1$1;
        continue;
      }
      Primitive_array.set(dst, d, s2);
      let i2$1 = i2 + 1 | 0;
      if (i2$1 >= src2r) {
        return blit(a, i1, dst, d + 1 | 0, src1r - i1 | 0);
      }
      _d = d + 1 | 0;
      _s2 = Primitive_array.get(src2, i2$1);
      _i2 = i2$1;
      continue;
    };
  };
  let isortto = (srcofs, dst, dstofs, len) => {
    for (let i = 0; i < len; ++i) {
      let e = Primitive_array.get(a, srcofs + i | 0);
      let j = (dstofs + i | 0) - 1 | 0;
      while (j >= dstofs && cmp(Primitive_array.get(dst, j), e) > 0) {
        Primitive_array.set(dst, j + 1 | 0, Primitive_array.get(dst, j));
        j = j - 1 | 0;
      };
      Primitive_array.set(dst, j + 1 | 0, e);
    }
  };
  let sortto = (srcofs, dst, dstofs, len) => {
    if (len <= 5) {
      return isortto(srcofs, dst, dstofs, len);
    }
    let l1 = len / 2 | 0;
    let l2 = len - l1 | 0;
    sortto(srcofs + l1 | 0, dst, dstofs + l1 | 0, l2);
    sortto(srcofs, a, srcofs + l2 | 0, l1);
    merge(srcofs + l2 | 0, l1, dst, dstofs + l1 | 0, l2, dst, dstofs);
  };
  let l = a.length;
  if (l <= 5) {
    return isortto(0, a, 0, l);
  }
  let l1 = l / 2 | 0;
  let l2 = l - l1 | 0;
  let x = Primitive_array.get(a, 0);
  let t = init(l2, param => x);
  sortto(l1, t, 0, l2);
  sortto(0, a, l2, l1);
  merge(l2, l1, t, 0, l2, a, 0);
}

let fast_sort = stable_sort;

exports.make = make;
exports.create_float = create_float;
exports.init = init;
exports.make_matrix = make_matrix;
exports.append = append;
exports.concat = concat;
exports.sub = sub;
exports.fill = fill;
exports.blit = blit;
exports.to_list = to_list;
exports.of_list = of_list;
exports.iter = iter;
exports.iteri = iteri;
exports.map = map;
exports.mapi = mapi;
exports.fold_left = fold_left;
exports.fold_right = fold_right;
exports.iter2 = iter2;
exports.map2 = map2;
exports.for_all = for_all;
exports.exists = exists;
exports.mem = mem;
exports.memq = memq;
exports.sort = sort;
exports.stable_sort = stable_sort;
exports.fast_sort = fast_sort;
/* No side effect */