CODEWITHSUNDEEP
javascriptsortingtree
John Whish
John Whish

Reputation: 3036

Sorting a Javascript Tree

I've got some data which has depths in it and I need to render that data showing the nesting by depth. Once the data is rendered, it needs to be sorted so that each 'depth' sorts independently but remains attached it's parent.

So far I've managed to convert the depths to a tree like array of objects and can render based on that. I have sorting in place, but can not figure out how to make the child elements remain relative to the parent.

Here is the code I've written so far:

var data = getData();

// convert the data to a tree structure
var tree = convertToTree(data);


$(function($) {

  init();


  function init() {
    renderTree(tree);
  }

  function renderTree(tree) {
    var $table = $('#tree1');

    var rows = [];

    function renderTreeRow(row) {
      if (row.hasOwnProperty('score')) {
        rows.push([
          '<tr class="depth_' + row.depth + '">',
          '  <td>' + row.label + '</td>',
          '  <td>' + row.row + '</td>',
          '  <td>' + row.depth + '</td>',
          '  <td>' + row.score + '</td>',
          '  <td>' + row.count + '</td>',
          '</tr>'
        ]);
      } else {
        rows.push([
          '<tr class="depth_' + row.depth + ' group_heading">',
          '  <td colspan="5">' + row.label + '</td>',
          '</tr>'
        ]);
      }
      if (row.hasOwnProperty('children') && row.children.length) {
        $.each(row.children, function(i, childRow) {
          renderTreeRow(childRow);
        });
      }
    }

    $.each(tree, function(i, row) {
      renderTreeRow(row);
    });

    $table.find('tbody tr').remove();
    $('tbody', $table).append(rows.join(''));
  }

  $('th[data-sort-asc]').off('.data_sort_asc').on('click.data_sort_asc', function(event) {
      var target = $(event.target).closest('th');
      var sortAscending = target.attr('data-sort-asc') == "true";
      var property = target.attr('data-sort-property');
      var treeSorter = sortByProperty(property, sortAscending);
      treeSorter(tree);
      renderTree(tree);
      // flip sort direction
      target.attr('data-sort-asc', !sortAscending);
      target.find('span').remove().end().append('<span class="glyphicon glyphicon-sort-by-attributes' + (sortAscending ? '' : '-alt') + '" aria-hidden="true"></span>');
    }).append('<span class="glyphicon glyphicon-sort" aria-hidden="true"></span>')
    .css({
      'cursor': 'pointer'
    });

});



function sortByProperty(property, ascending) {
  ascending = ascending !== undefined ? ascending : true;
  var flip = ascending ? 1 : -1;

  function sortTree(arr) {
    function compare(a, b) {
      if (a[property] < b[property]) {
        return -1 * flip;
      }
      if (a[property] > b[property]) {
        return 1 * flip;
      }
      return 0;
    }
    $.each(arr, function(i, el) {
      if (el.hasOwnProperty('children')) {
        sortTree(el.children);
      }
    });
    arr.sort(compare);
  }
  return sortTree;
}

/*
function flatternTree(tree) {
	var ret = [];
	$.each(tree, function(i, row) {
		ret.push(row);
		if(row.hasOwnProperty('children') && row.children.length) {
			ret = ret.concat(flatternTree(row.children));
		}
	});
	return ret;
}
*/

function convertToTree(arr) {
  return treeify(splitToSegments(arr));
}

function splitToSegments(arr) {
  var result = [];
  var accum, segment;

  $.each(arr, function(i, it) {
    if (it.depth === 0) {
      accum = true;
      if (segment && segment.length) {
        result.push(segment);
      }
      segment = [it];
    } else if (accum) {
      segment.push(it);
    }
  });

  if (segment && segment.length) {
    result.push(segment);
  }

  return result;
}

function treeify(arr) {
  return arr.map(function(o) {
    return o.reduce(function(a, b) {
      var lastChild;
      a.children = a.children || [];
      if (a.depth + 1 === b.depth) {
        a.children.push(b);
      } else {
        lastChild = a.children[a.children.length - 1];
        lastChild.children = lastChild.children || [];
        lastChild.children.push(b);
      }
      return a;
    });
  });
}


function getData() {
  // rows of data that we get, we have depth but not nested as parent>child relationships. The order & depth determines parent>child relationship
    var payload = [
    {row: 1, group: "group_30", "depth": 0, "label": "TOP"},
    {row: 2, group: "group_30", "depth": 1, "score": 10, "count": 600, "label": "A1"},
    {row: 3, group: "group_30", "depth": 2, "score": 10, "count": 100, "label": "A1>2-1"},
    {row: 4, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "A1>2-1>3-1"},
    {row: 5, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "A1>2-1>3-2"},
    {row: 6, group: "group_30", "depth": 2, "score": 20, "count": 200, "label": "A1>2-2"},
    {row: 7, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "A1>2-2>3-1"},
    {row: 8, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "A1>2-2>3-2"},
    {row: 9, group: "group_30", "depth": 2, "score": 30, "count": 300, "label": "A1>2-3"},
    {row: 10, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "A1>2-3>3-1"},
    {row: 11, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "A1>2-3>3-2"},
    {row: 12, group: "group_30", "depth": 1, "score": 10000, "count": 10, "label": "B1"},
    {row: 13, group: "group_30", "depth": 2, "score": 1000, "count": 1, "label": "B1>2-1"},
    {row: 14, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "B1>2-1>3-1"},
    {row: 15, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "B1>2-1>3-2"},
    {row: 16, group: "group_30", "depth": 2, "score": 3000, "count": 3, "label": "B1>2-2"},
    {row: 17, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "B1>2-2>3-1"},
    {row: 18, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "B1>2-2>3-2"},
    {row: 19, group: "group_30", "depth": 2, "score": 6000, "count": 6, "label": "B1>2-3"},
    {row: 20, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "B1>2-3>3-1"},
    {row: 21, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "B1>2-3>3-2"}
  ];
  return payload;
}
/* Styles go here */

.depth_0 {
  background-color: #B2A788;
}
.depth_1 {
  background-color: #7686B2;
}
.depth_2 {
  background-color: #9BC2CC;
}
.depth_3 {
  background-color: #DCE5FF;
}
.group_heading td {
  border-bottom: 3px solid #BFB8A5
}
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>

<p>Clicking the headers should sort each 'grouping' independantly, so that child elements appear directly after the parent. When the parent is sorted the child elements should move with it. Thanks!</p>

<table id="tree1" class="table">
  <thead>
    <tr>
      <th>label</th>
      <th data-sort-asc="true" data-sort-property="row">row</th>
      <th data-sort-asc="true" data-sort-property="depth">depth</th>
      <th data-sort-asc="true" data-sort-property="score">score</th>
      <th data-sort-asc="true" data-sort-property="count">count</th>
    </tr>
  </thead>
  <tbody>

  </tbody>
</table>

Thanks for any thoughts!

Upvotes: 2

Views: 794

Answers (1)

John Whish
John Whish

Reputation: 3036

Answering my own question - I expect there is a more elegant way to do this, but posting in case it helps others. Suggestions to improve it are welcome.

var data = getData();

// convert the data to a tree structure
var tree = convertToTree(data);


$(function($) {

  init();


  function init() {
    renderTree(tree);
  }

  function renderTree(tree) {
    var $table = $('#tree1');

    var rows = [];

    function renderTreeRow(row) {
      if (row.hasOwnProperty('score')) {
        rows.push([
          '<tr class="depth_' + row.depth + '">',
          '  <td>' + row.label + '</td>',
          '  <td>' + row.row + '</td>',
          '  <td>' + row.depth + '</td>',
          '  <td>' + row.score + '</td>',
          '  <td>' + row.count + '</td>',
          '</tr>'
        ]);
      } else {
        rows.push([
          '<tr class="depth_' + row.depth + ' group_heading">',
          '  <td colspan="5">' + row.label + '</td>',
          '</tr>'
        ]);
      }
      if (row.hasOwnProperty('children') && row.children.length) {
        $.each(row.children, function(i, childRow) {
          renderTreeRow(childRow);
        });
      }
    }

    $.each(tree, function(i, row) {
      renderTreeRow(row);
    });

    $table.find('tbody tr').remove();
    $('tbody', $table).append(rows.join(''));
  }

  $('th[data-sort-asc]').off('.data_sort_asc').on('click.data_sort_asc', function(event) {
      var target = $(event.target).closest('th');
      var sortAscending = target.attr('data-sort-asc') == "true";
      var property = target.attr('data-sort-property');
      var treeSorter = sortByProperty(property, sortAscending);
      treeSorter(tree);
      renderTree(tree);
      // flip sort direction
      target.attr('data-sort-asc', !sortAscending);
      target.find('span').remove().end().append('<span class="glyphicon glyphicon-sort-by-attributes' + (sortAscending ? '' : '-alt') + '" aria-hidden="true"></span>');
    }).append('<span class="glyphicon glyphicon-sort" aria-hidden="true"></span>')
    .css({
      'cursor': 'pointer'
    });

});



function sortByProperty(property, ascending) {
  ascending = ascending !== undefined ? ascending : true;
  var flip = ascending ? 1 : -1;

  function sortTree(arr) {
    function compare(a, b) {
      if (a[property] < b[property]) {
        return -1 * flip;
      }
      if (a[property] > b[property]) {
        return 1 * flip;
      }
      return 0;
    }
    $.each(arr, function(i, el) {
      if (el.hasOwnProperty('children')) {
        sortTree(el.children);
      }
    });
    arr.sort(compare);
  }
  return sortTree;
}

function convertToTree(arr) {
  var result = [];
  var previous;
  var lastDepth = [];

  $.each(arr, function(i, it) {
    previous = arr[i-1]; 
    if (it.depth === 0) { // top level
      result.push(it);
    }
    else if (it.depth > previous.depth) {
      // child of previous
      previous.children = previous.children || [];
      previous.children.push(it);
    }
    else {
      lastDepth[it.depth-1].children = lastDepth[it.depth-1].children || [];
      lastDepth[it.depth-1].children.push(it);
    }
    lastDepth[it.depth] = it;
  });

  return result;
}

function getData() {
  // rows of data that we get, we have depth but not nested as parent>child relationships. The order & depth determines parent>child relationship
    var payload = [
    {row: 1, group: "group_30", "depth": 0, "label": "TOP"},
    {row: 2, group: "group_30", "depth": 1, "score": 10, "count": 600, "label": "A1"},
    {row: 3, group: "group_30", "depth": 2, "score": 10, "count": 100, "label": "A1>2-1"},
    {row: 4, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "A1>2-1>3-1"},
    {row: 5, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "A1>2-1>3-2"},
    {row: 6, group: "group_30", "depth": 2, "score": 20, "count": 200, "label": "A1>2-2"},
    {row: 7, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "A1>2-2>3-1"},
    {row: 8, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "A1>2-2>3-2"},
    {row: 9, group: "group_30", "depth": 2, "score": 30, "count": 300, "label": "A1>2-3"},
    {row: 10, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "A1>2-3>3-1"},
    {row: 11, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "A1>2-3>3-2"},
    {row: 12, group: "group_30", "depth": 1, "score": 10000, "count": 10, "label": "B1"},
    {row: 13, group: "group_30", "depth": 2, "score": 1000, "count": 1, "label": "B1>2-1"},
    {row: 14, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "B1>2-1>3-1"},
    {row: 15, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "B1>2-1>3-2"},
    {row: 16, group: "group_30", "depth": 2, "score": 3000, "count": 3, "label": "B1>2-2"},
    {row: 17, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "B1>2-2>3-1"},
    {row: 18, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "B1>2-2>3-2"},
    {row: 19, group: "group_30", "depth": 2, "score": 6000, "count": 6, "label": "B1>2-3"},
    {row: 20, group: "group_30", "depth": 3, "score": 222, "count": 9, "label": "B1>2-3>3-1"},
    {row: 21, group: "group_30", "depth": 3, "score": 22, "count": 99, "label": "B1>2-3>3-2"}
  ];
  return payload;
}
/* Styles go here */

.depth_0 {
  background-color: #B2A788;
}
.depth_1 {
  background-color: #7686B2;
}
.depth_2 {
  background-color: #9BC2CC;
}
.depth_3 {
  background-color: #DCE5FF;
}
.group_heading td {
  border-bottom: 3px solid #BFB8A5
}
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>


<table id="tree1" class="table">
  <thead>
    <tr>
      <th>label</th>
      <th data-sort-asc="true" data-sort-property="row">row</th>
      <th data-sort-asc="true" data-sort-property="depth">depth</th>
      <th data-sort-asc="true" data-sort-property="score">score</th>
      <th data-sort-asc="true" data-sort-property="count">count</th>
    </tr>
  </thead>
  <tbody>

  </tbody>
</table>

Upvotes: 1

Related Questions