BOLT nearest neighbour

closestStraightCity.js

// const shaukote = require('./shaukote');
const { performance } = require('perf_hooks');

function closestStraightCity(c, x, y, q) {
  let resArray = []; // ["city",..,q]

  // HashX: {
  //  '1': [city:[y,prev,next],city:[y,prev,next],...]
  //  '2': {city:[y,prev,next],city:[y,prev,next],...}
  // }
  // HashY: {
  //  '1': {city:[x,prev,next],city:[x,prev,next],...}
  //  '2': {city:[x,prev,next],city:[x,prev,next],...}
  // }

  // EXAMPLE:
  // {
  //   '1': {
  //     london: { y: 1, prev: null, next: 'warsaw' },
  //     warsaw: { y: 2, prev: 'london', next: 'hackerland' },
  //     hackerland: { y: 3, prev: 'warsaw', next: 'city2' },
  //     city2: { y: 4, prev: 'hackerland', next: null }
  //   },
  //   '2': { city3: { y: 5, prev: null, next: null } }
  // }

  const hashX = {};
  const hashY = {};
  const hashC = {};

  for (let i = 0; i < c.length; i++) {
    !hashX[x[i]] ? (hashX[x[i]] = [[y[i], c[i]]]) : hashX[x[i]].push([y[i], c[i]]);
    !hashY[y[i]] ? (hashY[y[i]] = [[x[i], c[i]]]) : hashY[y[i]].push([x[i], c[i]]);
    hashC[c[i]] = [x[i], y[i]];
  }

  for (const [key, value] of Object.entries(hashX)) {
    value.length > 1 ? value.sort((a, b) => a[0] - b[0]) : null;
    let tmpObj = {};
    for (const [i, el] of value.entries()) {
      let assign = {
        [el[1]]: {
          y: el[0],
          prev: !i ? null : value[i - 1][1],
          next: i === value.length - 1 ? null : value[i + 1][1],
        },
      };

      Object.assign(tmpObj, assign);
    }
    hashX[key] = tmpObj;
  }

  for (const [key, value] of Object.entries(hashY)) {
    value.length > 1 ? value.sort((a, b) => a[0] - b[0]) : null;
    let tmpObj = {};
    for (const [i, el] of value.entries()) {
      let assign = {
        [el[1]]: {
          x: el[0],
          prev: !i ? null : value[i - 1][1],
          next: i === value.length - 1 ? null : value[i + 1][1],
        },
      };

      Object.assign(tmpObj, assign);
    }
    hashY[key] = tmpObj;
  }

  // TODO: ✅ сформировать ответ
  for (const qCity of q) {
    let tmpRes = [];

    // if n<m push "NONE" for m[i] where i > n.length-1
    if (hashC[qCity]) {
      let x = hashC[qCity][0];
      let y = hashC[qCity][1];

      // TODO: сразу проверять min(tmpRes,newTmpRes)
      // если равны -> сравнивать по алфавиту
      // в итоге избавмся от tmpRes.sort()
      !hashX[x][hashX[x][qCity].prev]
        ? null
        : tmpRes.push([y - hashX[x][hashX[x][qCity].prev].y, hashX[x][qCity].prev]);
      !hashX[x][hashX[x][qCity].next]
        ? null
        : tmpRes.push([hashX[x][hashX[x][qCity].next].y - y, hashX[x][qCity].next]);
      !hashY[y][hashY[y][qCity].prev]
        ? null
        : tmpRes.push([x - hashY[y][hashY[y][qCity].prev].x, hashY[y][qCity].prev]);
      !hashY[y][hashY[y][qCity].next]
        ? null
        : tmpRes.push([hashY[y][hashY[y][qCity].next].x - x, hashY[y][qCity].next]);
      if (!tmpRes.length) {
        resArray.push('NONE');
      } else {
        tmpRes.sort((a, b) => a[0] - b[0]);
        let min = tmpRes[0][0];
        tmpRes.filter(e => e[0] === min);

        // TODO: alphabetically smaller name (i.e. 'ab' < 'aba' < 'abb')
        // просто a[1] < b[1] не работает, почему?
        // (a, b) => (a[1] < b[1] ? -1 : 1) - alphabetically sort function.

        // TODO: разобраться с str.localCompre()
        tmpRes.sort((a, b) => (a[1] < b[1] ? -1 : 1));
        resArray.push(tmpRes[0][1]);
      }
      // console.log(tmpRes);
      // !tmpRes.length ? resArray.push('NONE') : resArray.push();
    } else {
      resArray.push('NONE');
    }
  }
  // console.log(hashX);
  // console.log(hashY);
  // console.log(hashC);
  // console.log(resArray);

  return resArray;
}

// const n = 5;
// const m = 5;
// const c = ['x', 'ab', 'aba', 'abb'];
// const x = [2, 1, 2, 3];
// const y = [2, 2, 3, 2];
// const q = ['x'];
// const res = ['ab'];

// big numbers

const n = Math.pow(10, 5);
const m = Math.pow(10, 5);
const c = Array.from(Array(n), (el, index) => 'city-' + index);
const x = Array.from(Array(n), (el, index) => index);
const y = Array.from(Array(n), (el, index) => index);
const q = Array.from(Array(m), (el, index) => 'city-' + index);

let start = performance.now();
closestStraightCity(c, x, y, q);
// shaukote(c, x, y, q);
let end = performance.now();

console.log(`Execution time:${end - start} ms`);
console.log(process.memoryUsage());

module.exports = closestStraightCity;
//
//