Сортировка массива с использованием нескольких ключей объекта и пользовательской логики сортировки

Question

У меня есть объект, который выглядит следующим образом:

var object = [
    {"begin":0,  "end":20}, 
    {"begin":30, "end":300},
    {"begin":40, "end":60}, 
    {"begin":40, "end":50},
    {"begin":80, "end":100},
    {"begin":80, "end":100},
    {"begin":350,"end":370}
]

Я бы хотел перебрать этот объект и отсортировать его в следующем виде:

0   to 20   -> start here
30  to 300  -> next smallest number from 20 is 30
350 to 370  -> start from previous `end`, next number after 300 is 350.

// now, since there is no larger number than 370, start loop again.
40  to 60   -> start from 40 since this is the smallest unused number
80  to 100  -> next unused smallest number from 60 is 80

// now, since there is no larger unused number than 100, start loop again.
40  to 50
80  to 100

Либо возврат того же массива, либо нового массива будет в порядке.

Любая помощь всегда ценится.

Answer 1

См. Рабочий пример здесь: http://jsfiddle.net/bXNLT/2/

function sortItems(items) {
    items = items.slice() // make a copy
        // sort by "begin", in case the 
        // data isn't pre-sorted
        .sort(function(a,b) {
            return a.begin - b.begin;
        });
    var sorted = [], 
        idx = 0, 
        item;
    while (items.length) {
        // move the current item into the sorted array
        item = items.splice(idx, 1)[0];
        sorted.push(item);
        // find next index
        for (; idx<items.length; idx++) {
            if (items[idx] && items[idx].begin > item.end) {
                break;   
            }
        }
        // reset to 0 if we went too far
        idx = idx < items.length ? idx : 0;
    }
    return sorted;
}

Использование:

var arr = [
    {"begin":0,  "end":20}, 
    {"begin":30, "end":300},
    {"begin":40, "end":60}, 
    {"begin":40, "end":50},
    {"begin":80, "end":100},
    {"begin":80, "end":100},
    {"begin":350,"end":370}
];
sortItems(arr); // sorted as you specify

Answer 2

Для того, что вы хотите сделать, обычная сортировка (даже с пользовательской функцией), скорее всего, не сработает для всего.

Однако вы должны использовать ее, чтобы получить элементы в хорошем порядке длядальнейшая обработка.Сортируйте сначала по началу, затем по концу.

Затем, если вы добавите флаг «грязный» к каждому набору данных, это станет намного проще.

var obj = [
    {"begin":0,  "end":20,   "dirty": false}, 
    {"begin":30, "end":300,  "dirty": false},
    {"begin":40, "end":60,   "dirty": false}, 
    {"begin":40, "end":50,   "dirty": false},
    {"begin":80, "end":100,  "dirty": false},
    {"begin":80, "end":100,  "dirty": false},
    {"begin":350,"end":370,  "dirty": false}
];

function getNextSet(arr)
{
  var ret = [];
  var lastEnd = -1;

  for (var i = 0; i < arr.length; i++)
  {
     if (arr[i].begin >= lastEnd && arr[i].dirty == false)
     {
        ret.push(arr[i]);
        arr[i].dirty = true;
        lastEnd = arr[i].end;
     }
  }

  return ret;
}

// do custom sorting as mentioned in the other answer to get in a good starting state

var set = [];
do {
  set = getNextSet(obj);
  // do whatever
} while (set.length != 0);

Answer 3

В массивах Javascript есть метод sort, который может принимать функцию сравнения в качестве параметра:

var data = [...]; // your data here
data.sort(function(a, b) {
    // insert your logic here
    // return values:
    //  -1 (a less than b)
    //   0 (a equal to b)
    //   1 (a greater than b)
});

На этом сайте есть еще несколько примеров такого подхода .