如何将子/父关系合并到排序函数中
How can I incorporate a child/parent relationship into a sort function?
我想按事件对象的开始日期对事件对象数组进行排序,但有些事件有父对象,如果某个事件有父事件,则应按开始日期顺序显示,其同级事件紧跟在父事件之后。
我已经交换了以下代码的各种排列,但似乎无法正确排序。
我试图将其放入排序函数的原因是,该函数被交给了一个时间轴显示,该显示将动态添加/删除事件。
JSFiddle显示我的结果与预期结果:http://jsfiddle.net/8q0786p5/
var toJsDates = function(arr){
for(var i=0;i<arr.length;i++){
arr[i].start = new Date(arr[i].start);
}
}
var checkOrder = function(arr){
var output = "<table><tr><th>index</th><th>expected</th><th>got</th></tr>";
for(var i=0;i<arr.length && i < eventsInCorrectOrder.length;i++){
output += "<tr><td>"+i+"</td><td>"+eventsInCorrectOrder[i].id+"</td>";
if(arr[i].id == eventsInCorrectOrder[i].id){
output += "<td style='"color:green;'">"+arr[i].id+" - GOOD</td>";
}
else{
output += "<td style='"color:red;'">"+arr[i].id+" - WRONG</td>";
}
output += "</tr>";
}
output += "</table>";
document.body.innerHTML += output;
}
var events = [
{id: 1, content: 'item 1', start: '2013-04-20'},
{id: 2, content: 'item 2', start: '2013-01-14'},
{id: 3, content: 'item 3', start: '2013-04-18'},
{id: 4, content: 'item 4', start: '2013-04-16'},
{id: 5, content: 'item 5', start: '2013-04-25'},
{id: 6, content: 'item 6', start: '2013-09-21'},
{id: 7, content: 'item 7', start: '2013-04-23'},
{id: 8, content: 'item 8', start: '2013-04-11'},
{id: 9, content: 'item 9', start: '2013-04-10'},
{id: 10, content: 'item 10', start: '2013-04-13'},
{id: 11, content: 'item 11', start: '2013-04-15'},
{id: 12, content: 'item 12', start: '2013-08-22'},
{id: 21, content: 'item 13', start: '2013-06-21'},
{id: 22, content: 'item 14', start: '2013-04-17'},
{id: 23, content: 'item 15', start: '2013-04-17'},
{id: 24, content: 'item 16', start: '2013-04-10'},
{id: 25, content: 'item 17', start: '2013-04-24'},
{id: 26, content: 'item 18', start: '2013-04-23'},
{id: 27, content: 'item 19', start: '2013-04-28'},
{id: 28, content: 'item 20', start: '2013-04-19'},
{id: 29, content: 'item 21', start: '2013-04-05'},
{id: 42, content: 'A Project', start: '2013-04-23'},
{id: 43, content: 'Initial Mtg', start: '2013-04-24', parentId: 42},
{id: 44, content: 'Mid-term Mtg', start: '2013-04-28', parentId: 42},
{id: 45, content: 'Final Mtg', start: '2013-05-09', parentId: 42},
{id: 46, content: 'B Project', start: '2013-04-23'},
{id: 47, content: 'IPC', start: '2013-04-23', parentId: 46},
{id: 48, content: 'MPC', start: '2013-04-25', parentId: 46},
{id: 49, content: 'FPC', start: '2013-05-02', parentId: 46},
{id: 50, content: 'Standalone Meeting', start: '2013-04-23'},
];
var getEventById = function(id){
for(var i=0;i<events.length;i++){
if(events[i].id == i) return events[i];
}
return false;
}
var eventsInCorrectOrder = [
{id: 2, content: 'item 2', start: '2013-01-14'},
{id: 29, content: 'item 21', start: '2013-04-05'},
{id: 9, content: 'item 9', start: '2013-04-10'},
{id: 24, content: 'item 16', start: '2013-04-10'},
{id: 8, content: 'item 8', start: '2013-04-11'},
{id: 10, content: 'item 10', start: '2013-04-13'},
{id: 11, content: 'item 11', start: '2013-04-15'},
{id: 4, content: 'item 4', start: '2013-04-16'},
{id: 22, content: 'item 14', start: '2013-04-17'},
{id: 23, content: 'item 15', start: '2013-04-17'},
{id: 3, content: 'item 3', start: '2013-04-18'},
{id: 28, content: 'item 20', start: '2013-04-19'},
{id: 1, content: 'item 1', start: '2013-04-20'},
{id: 21, content: 'item 13', start: '2013-06-21'},
{id: 12, content: 'item 12', start: '2013-08-22'},
{id: 7, content: 'item 7', start: '2013-04-23'},
{id: 26, content: 'item 18', start: '2013-04-23'},
{id: 42, content: 'A Project', start: '2013-04-23'},
{id: 43, content: 'Initial Mtg', start: '2013-04-24', parentId: 42},
{id: 44, content: 'Mid-term Mtg', start: '2013-04-28', parentId: 42},
{id: 45, content: 'Final Mtg', start: '2013-05-09', parentId: 42},
{id: 46, content: 'B Project', start: '2013-04-23'},
{id: 47, content: 'IPC', start: '2013-04-23', parentId: 46},
{id: 50, content: 'Standalone Meeting', start: '2013-04-23'},
{id: 25, content: 'item 17', start: '2013-04-24'},
{id: 5, content: 'item 5', start: '2013-04-25'},
{id: 27, content: 'item 19', start: '2013-04-28'},
{id: 48, content: 'MPC', start: '2013-04-25', parentId: 46},
{id: 49, content: 'FPC', start: '2013-05-02', parentId: 46},
{id: 6, content: 'item 6', start: '2013-09-21'}
];
// Normally this is handled elsewhere, just for demonstration purposes
toJsDates(events);
toJsDates(eventsInCorrectOrder);
// Test the events for correctness
document.body.innerHTML += "<h1>Unsorted events</h1>";
checkOrder(events);
// Sort function to use
var sortEventsFunc = function(a,b){
var ap,bp;
// Both have a parent
if(a.parentId && b.parentId){
ap = getEventById(a.parentId);
bp = getEventById(b.parentId);
// Different parents
if(ap.id != bp.id){
a = ap;
b = bp;
}
}
// A has a parent
else if(a.parentId){
ap = getEventById(a.parentId);
if(b.id == ap.parentId){
return 1; // favor b
}
a = ap;
}
// B has a parent
else if(b.parentId){
bp = getEventById(b.parentId);
if(a.id == bp.parentId){
return -1; // favor a
}
b = bp;
}
var dateDiff = b.start - a.start;
if(dateDiff == 0){
return b.id - a.id;
}
return dateDiff;
}
// Sort the events and try again
events = events.sort(sortEventsFunc);
document.body.innerHTML += "<h1>Sorted events</h1>";
checkOrder(events);
// Verify the checkOrder function
document.body.innerHTML += "<h1>Pre-sorted events to verify</h1>";
checkOrder(eventsInCorrectOrder);
这可能不是最有效的方法,所以如果没有太多事件,这是一个很好的解决方案。
没有对象的JS:
var newEvents = [];
var childEvents = [];
var parentEvents = [];
$.each(events, function (i, e) {
e.start = new Date(e.start);
if (e.end) {
e.end = new Date(e.end);
}
});
events.sort(function (a, b) {
return a.start - b.start;
});
$.each(events, function (i, e) {
if (e.parentId) {
childEvents.push(e);
} else {
parentEvents.push(e);
}
});
$.each(parentEvents, function (i, e) {
newEvents.push(e);
$.each(childEvents, function (childIndex, child) {
if (child.parentId == e.id) {
newEvents.push(child);
}
});
});
$.each(newEvents, function (i, e) {
console.log(e.content);
});
Fiddle示例
另一种方法是,您可以将关系添加到对象的构建方式中——您可以将子事件创建为父事件的属性,然后您可以对parent/childred:进行排序
var addRelationships = function(){
$.each(events,function(i,e){
if(e.parentId){
for(var i=0;i<events.length;i++){
var parent = events[i];
if(parent.id == e.parentId){
e.parent = parent;
}
if(!parent.children){
parent.children = [e];
}
else{
parent.children.push(e);
}
}
}
});
}
events.sort(function(a,b){
if(a.children && $.inArray(b, a.children)){// b is a's child
return -1;//favor parent a
}
else if(b.children && $.inArray(a, b.children)){// a is b's child
return 1;//favor parent b
}
if(a.parent && b.parent){//both have parent
if(a.parent.id == b.parent.id){//same parent
return a.start - b.start;// standard sorting
}
else{
return a.parent.start - b.parent.start;// sort by parent
}
}
else if(a.parent){
a = a.parent;
}
else if(b.parent){
b = b.parent;
}
return a.start - b.start;
});
events = mergeSort(events, ['group', 'id']);
function mergeSort(objArr, props, direction, start, end) {
var tmp;
if (typeof start == 'undefined') {
start = 0;
}
if (typeof end == 'undefined') {
end = objArr.length - 1;
}
if (typeof direction == 'undefined' || direction >= 0) {
direction = 1; // asc
} else {
direction = -1; // desc
}
tmp = end - start;
if (tmp == 0) {
return [objArr[start]];
} else if (tmp == 1) {
if (compare(objArr[start], objArr[end], props) * direction > 0) {
return [objArr[end], objArr[start]];
} else {
return [objArr[start], objArr[end]];
}
} else if (tmp >= 2) {
tmp = Math.floor(start + tmp / 2);
var t1 = mergeSort(objArr, props, direction, start, tmp);
var t2 = mergeSort(objArr, props, direction, tmp + 1, end);
var ret = [];
var c1 = 0, c2 = 0;
for (;;) {
if (compare(t1[c1], t2[c2], props) * direction > 0) {
ret.push(t2[c2]);
if (++c2 == t2.length) {
for (tmp = c1; tmp < t1.length; tmp++) {
ret.push(t1[tmp]);
}
break;
}
} else {
ret.push(t1[c1]);
if (++c1 == t1.length) {
for (tmp = c2; tmp < t2.length; tmp++) {
ret.push(t2[tmp]);
}
break;
}
}
}
return ret;
}
return [];
}
function compare(a, b, props) {
for (var i = 0; i < props.length; i++) {
if (typeof a[props[i]] == 'undefined') {
if (typeof b[props[i]] == 'undefined') {
continue;
} else {
return -1;
}
} else if (typeof b[props[i]] == 'undefined') {
return 1;
}
if (a[props[i]] < b[props[i]]) {
return -1;
} else if (a[props[i]] > b[props[i]]) {
return 1;
}
}
return 0;
}
http://jsfiddle.net/ddtwxa6p/
计划B
events.sort(function(a, b) {
var props = ['group', 'id'];
for (var i = 0; i < props.length; i++) {
if (a[props[i]] < b[props[i]]) {
return -1;
} else if (a[props[i]] > b[props[i]]) {
return 1;
}
}
return 0;
});
"分组依据">
events = groupBy(events, 'id', 'parentId');
function groupBy(objArr, id, parentId) {
var i,j, parents = [], pids = {};
for (i = 0; i < objArr.length; i++) {
if (typeof objArr[i][parentId] != 'undefined') {
if (typeof pids[objArr[i][parentId]] == 'undefined') {
pids[objArr[i][parentId]] = [];
}
pids[objArr[i][parentId]].push(i);
} else {
parents.push(objArr[i]);
}
}
var ret = [];
for (i = 0; i < parents.length; i++) {
ret.push(parents[i]);
if (typeof pids[parents[i][id]] == 'undefined') { continue;}
for (j = 0; j < pids[parents[i][id]].length; j++) {
ret.push(objArr[pids[parents[i][id]][j]]);
}
}
return ret;
}
http://jsfiddle.net/ddtwxa6p/3/
在创建输出之前,可以对父对象进行排序(每组中的子对象相同(。如果存在parentId无效的子项,则会忽略这些子项。因为算法是稳定的,所以您也可以提前对objArray进行排序(即按id排序(,然后一切都应该是您想要的,而不需要任何额外的排序。
相关文章:
- 如何合并不同集合的游标并按日期排序
- 将两个Json提要合并为一个,并按时间排序
- 根据搜索项按相关性合并和排序多个JavaScript数组
- 用Javascript实现了带有合并排序算法的反转计数
- JSON 合并、数组推送和排序和删除双精度
- 合并排序实现在 Javascript 中不起作用
- JavaScript 中的合并排序返回重复的元素
- 在 JavaScript 中合并多个排序对象数组的最有效方法是什么?
- 合并然后排序 2 个源
- 修改合并排序以在 JavaScript 中计算反转
- 在 Javascript 中实现合并排序
- 合并排序 - 自下而上比自上而下更快
- 合并来自多个 URL 的 JSON 数据并根据键对其进行排序
- 对具有匹配值的 JSON 键进行排序和合并
- 如何根据对象(而不是数组)的属性执行合并排序
- javascript 2D数组-排序和合并
- buble对数组进行排序,并在不使用javascript内置函数的情况下将它们合并
- 如何使用Javascript合并两个json并对时间值进行排序
- 在javascript中合并排序的简单实现
- Javascript合并/排序致命错误