Сортировка массива Javascript путем сравнения объектов с разными парами ключ-значение

Question

Извините, я не знаю, как сделать более описательный заголовок.Я пытаюсь отсортировать массив ниже:

var joins = [
  {
    "joinType": "INNER JOIN",
    "joinTableName": "country",
    "joinColumnName": "id",
    "foreignTableName": "state",
    "foreignColumnName": "country_id",
    "index": 1
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "state",
    "joinColumnName": "id",
    "foreignTableName": "city",
    "foreignColumnName": "state_id",
    "index": 2
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "city",
    "joinColumnName": "id",
    "foreignTableName": "address",
    "foreignColumnName": "city_id",
    "index": 3
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "address",
    "joinColumnName": "id",
    "foreignTableName": "user",
    "foreignColumnName": "address_id",
    "index": 4
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "user_status",
    "joinColumnName": "id",
    "foreignTableName": "user",
    "foreignColumnName": "status_id",
    "index": 5
  }
]

с помощью кода ниже:

joins.sort((a, b) => {
  if (a.foreignTableName === b.joinTableName) return 1; //b comes first
  else if (a.joinTableName === b.foreignTableName) return -1; //a comes first
  else return 0; //no change
});

Результат:

[
  {
    "joinType": "INNER JOIN",
    "joinTableName": "state",
    "joinColumnName": "id",
    "foreignTableName": "city",
    "foreignColumnName": "state_id",
    "index": 2
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "country",
    "joinColumnName": "id",
    "foreignTableName": "state",
    "foreignColumnName": "country_id",
    "index": 1
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "address",
    "joinColumnName": "id",
    "foreignTableName": "user",
    "foreignColumnName": "address_id",
    "index": 4
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "city",
    "joinColumnName": "id",
    "foreignTableName": "address",
    "foreignColumnName": "city_id",
    "index": 3
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "user_status",
    "joinColumnName": "id",
    "foreignTableName": "user",
    "foreignColumnName": "status_id",
    "index": 5
  }
]

Это не то, что яожидается - я ожидаю, что элементы с индексами 2 и 1 идут после элемента с индексом 3. Что не так?

Чтобы добавить еще некоторые детали, это для создания оператора запроса MySql из определения поля объектатаблица, которая определяет поля бизнес-объекта с использованием данных из базы данных нижнего уровня другой производственной системы.Вышеуказанная часть предназначена для создания подпункта JOIN.

PS, вот что я хочу:

[
  {
    "joinType": "INNER JOIN",
    "joinTableName": "address",
    "joinColumnName": "id",
    "foreignTableName": "user",
    "foreignColumnName": "address_id",
    "index": 4
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "city",
    "joinColumnName": "id",
    "foreignTableName": "address",
    "foreignColumnName": "city_id",
    "index": 3
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "state",
    "joinColumnName": "id",
    "foreignTableName": "city",
    "foreignColumnName": "state_id",
    "index": 2
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "country",
    "joinColumnName": "id",
    "foreignTableName": "state",
    "foreignColumnName": "country_id",
    "index": 1
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "user_status",
    "joinColumnName": "id",
    "foreignTableName": "user",
    "foreignColumnName": "status_id",
    "index": 5
  }
]

Answer 1

Поскольку я не знаю механизм Array.prototype.sort, я попробовал ту же логику с bubbleSort и распечатал шаги и обнаружил проблему.

В начале каждого цикла bubbleSort принимает крайний левый элемент в несортированном массиве как «пузырь» и пытается поменять его на один шаг вправо за раз, если элемент меньше, чем его правый сосед, затем принимает правого соседа как пузырь - то есть, когда пузырь идет к самому правому краю, он содержит самый большой из несортированных элементов.

Моя проблема в том, что элемент в моем целевом наборе не всегда сопоставим с другим, поэтому я не могу выплеснуть «самое большое» вправо - такого «самого большого» нет. элементы в моем целевом наборе являются «частично» заказываемыми: я могу устанавливать заказы среди некоторых из них, но не во всех.

Имея это в виду, я пришел с идеей: я должен отсортировать эти заказываемые элементы в сегменты / цепочки, а затем объединить их. Ниже, я называю это mergeSort (я знаю, что существует известная сортировка слиянием, но я не могу вспомнить ее механизм, поэтому мой может быть несовместим с типичной сортировкой слияния).

function mergeSort(arr, compFn) {
  let res = [];
  while (arr.length > 0) {
    res = res.concat(makeChain(arr.splice(0, 1)[0], compFn));
  }
  return res.filter(n => n);

  function makeChain(obj, compFn) {
    let res = [obj];
    for (let i = 0; i < arr.length; i++) {
      if (isEmpty(arr[i])) return;
      let flag = compFn(obj, arr[i]);
      if (flag < 0) {
        res = res.concat(makeChain(arr.splice(i, 1)[0], compFn));
      } else if (flag > 0) {
        res = makeChain(arr.splice(i, 1)[0], compFn).concat(res);
      }
    }
    return res;
  }

}

Тогда я все еще могу использовать ту же функцию сравнения:

joins = mergeSort(joins, (a, b) => {
  if (a.foreignTableName === b.joinTableName) return 1; //b comes first
  else if (a.joinTableName === b.foreignTableName) return -1; //a comes first
  else return 0; //no change
});

Это сгенерировало отсортированный массив, который я ожидал.

Answer 2

Здесь у вас есть один подход, который сначала назначает level каждому объекту, уровень определяется index корневого предка объекта и level of deep, что объект находится внутри связанного списка, которому он принадлежит к. После добавления этого нового свойства lvl мы просто можем отсортировать, используя это новое свойство. Я не верю, что этот подход будет настолько хорош с точки зрения производительности, но, возможно, мог бы соответствовать вашим потребностям.

var joins = [
  {
    "joinType": "INNER JOIN",
    "joinTableName": "country",
    "joinColumnName": "id",
    "foreignTableName": "state",
    "foreignColumnName": "country_id",
    "index": 1
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "state",
    "joinColumnName": "id",
    "foreignTableName": "city",
    "foreignColumnName": "state_id",
    "index": 2
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "city",
    "joinColumnName": "id",
    "foreignTableName": "address",
    "foreignColumnName": "city_id",
    "index": 3
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "address",
    "joinColumnName": "id",
    "foreignTableName": "user",
    "foreignColumnName": "address_id",
    "index": 4
  },
  {
    "joinType": "INNER JOIN",
    "joinTableName": "user_status",
    "joinColumnName": "id",
    "foreignTableName": "user",
    "foreignColumnName": "status_id",
    "index": 5
  }
];

// Find the object with the table a foreign key is referencing.

const findParent = (fTable) => joins.find(x => x.joinTableName === fTable);

// Recursive method that assigns a level to an object based on the position
// they have on the linked list they belong to.

const getLevel = (fTable, index, lvl) =>
{
    let parent = findParent(fTable);
    return (fTable && parent) ?
           getLevel(parent.foreignTableName, parent.index, lvl + 1) :
           index + "-" + lvl;
}

// Maps the input data to adds the level property to each object.

let newInput = joins.map(obj =>
{
    obj.lvl = getLevel(obj.foreignTableName, obj.index, 0);
    return obj;
});

// Sorts the new generated data based on the level property. Since the
// lvl property is a string, we use "localeCompare()" to compare.

let sortedInput = newInput.sort((a, b) => a.lvl.localeCompare(b.lvl));

// Shows the sorted data.

console.log(sortedInput);