const { assign } = require("./tools");

function searchBlock(state, process) {
  let candidates = state
    .map((block, key) => assign(block, { key }))
    .filter(block => block.id == -1 && block.size >= process.size);

  candidates.sort((blockX, blockY) => {
    const x = blockY.size;
    const y = blockY.size;
    if (x < y) return -1;
    else if (x > y) return 1;
    else return 0;
  });

  return candidates.length != 0 ? candidates[0].key : -1;
}

const getCapacity = state =>
  state
    .filter(block => block.id == -1)
    .reduce((capacity, block) => capacity + block.size, 0);

function insert(state, process, target) {
  const bound = target.from + process.size;

  return target.size == process.size
    ? [assign(target, { id: process.id })]
    : [
        assign(target, { id: process.id, size: process.size }),
        assign(target, { size: target.size - process.size })
      ];
}

function compact(state) {
  const size = getCapacity(state);
  return [...state.filter(block => block.id != -1), { id: -1, size }];
}

function allocate(state, process) {
  const capacity = getCapacity(state);

  if (capacity < process.size) {
    throw new Error("OUT OF MEMORY");
  }

  let idx = searchBlock(state, process);

  if (idx == -1) {
    state = compact(state);
    idx = searchBlock(state, process);
  }

  const target = state[idx];
  const nextState = [
    ...state.slice(0, idx),
    ...insert(state, process, target),
    ...state.slice(idx + 1)
  ];
  const offset = idx;
  return nextState;
}

module.exports = allocate;