Лучший способ сортировки массива объектов по категориям и бесконечной подкатегории

Question

У меня есть базы данных, которые я буду тянуть массив объектов ниже. Я хочу создать древовидную структуру из него.

Когда parent_id равен nil, это категория верхнего уровня. Если parent_id не равен nil, то это подкатегория значения идентификатора parent_id.

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

[{id: 1, name: "top test 1", parent_id: nil},
 {id: 2, name: "test 2", parent_id: 1},
 {id: 3, name: "test 3", parent_id: 1},
 {id: 4, name: "top test 4", parent_id: nil},
 {id: 5, name: "test 5", parent_id: 3},
 {id: 6, name: "test 6", parent_id: 4},
 {id: 7, name: "test 7", parent_id: 4}]


top test 1
  test 2
  test 3
    test 5
top test 2
  test 6
  test 7

Фактический массив объектов, возвращаемых из БД. Все еще только тестовые данные.

[#<ItemsCategory id: 2, name: "test 2", parent_id: 1, created_at: "2014-03-04 17:58:46", updated_at: "2014-03-04 17:58:46">, 
#<ItemsCategory id: 3, name: "test 3", parent_id: 1, created_at: "2014-03-04 17:23:23", updated_at: "2014-03-04 17:23:23">, 
#<ItemsCategory id: 5, name: "test 4", parent_id: 3, created_at: "2014-03-06 17:48:25", updated_at: "2014-03-06 17:48:25">, 
#<ItemsCategory id: 1, name: "NEW test EDITED", parent_id: nil, created_at: "2014-03-04 17:57:21", updated_at: "2014-03-10 20:50:10">]

Answer 1

Вы можете сделать это так:

Код

def doit(data, indent = 2)
  d = data.each_with_object({}) { |h,g| g[h[:id]] = h }
  d.each {|_,h| h[:ancestor_ids] =
    (h[:top_level_category_id] ? d[h[:parent_id]][:ancestor_ids] :[])+[h[:id]]}
   .values
   .sort_by { |h| h[:ancestor_ids] }
   .each { |h| puts ' '*((h[:ancestor_ids].size-1)*indent) + "#{h[:name]}" }
end

демонстрация

data=[
  {id: 1, name: "parent test 1", parent_id: nil, top_level_category_id: nil},
  {id: 2, name: "test 2", parent_id: 1, top_level_category_id: 1},
  {id: 3, name: "test 3", parent_id: 1, top_level_category_id: 1},
  {id: 4, name: "parent test 4", parent_id: nil, top_level_category_id: nil},
  {id: 5, name: "test 5", parent_id: 3, top_level_category_id: 4},
  {id: 6, name: "test 6", parent_id: 4, top_level_category_id: 4},
  {id: 7, name: "test 7", parent_id: 4, top_level_category_id: 4}
]

doit(data)
parent test 1
  test 2
  test 3
    test 5
parent test 4
  test 6
  test 7

объяснение

Что нам нужно сделать, это добавить еще один элемент хэш (ключ которого я назвал :ancestor_ids), значение которого является массивом хешей :id и всех его предков; т.е. мы хотим добавить следующие элементы в соответствующие хеши:

:ancestor_ids => [1]
:ancestor_ids => [1,2]
:ancestor_ids => [1,3]
:ancestor_ids => [4]
:ancestor_ids => [1,3,5]
:ancestor_ids => [4,6]
:ancestor_ids => [4,7]

Как только у нас есть эти, мы можем использовать sort_by { |h| h[:ancestor_ids] } поместить элементы массива data в правильном порядке. (Если вы не уверены, как упорядочены элементы массива, просмотрите Array#<=>;;.) Также h[:ancestor_ids].size используется для определения необходимого отступа при отображении результатов.

Расчеты идут так: *

d = data.each_with_object({}) { |h,g| g[h[:id]] = h }
  #=> {1=>{:id=>1, :name=>"parent test 1",...},
  #    2=>{:id=>2, :name=>"test 2",...},
  #    3=>{:id=>3, :name=>"test 3",...},
  #    4=>{:id=>4, :name=>"parent test 4",...},
  #    5=>{:id=>5, :name=>"test 5",...},
  #    6=>{:id=>6, :name=>"test 6",...},
  #    7=>{:id=>7, :name=>"test 7",...}} 

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

e = d.each {|_,h| h[:ancestor_ids] =
    (h[:top_level_category_id] ? d[h[:parent_id]][:ancestor_ids]:[])+[h[:id]]}
  #=> {1=>{:id=>1,...,:ancestor_ids=>[1]},
  #    2=>{:id=>2,...,:ancestor_ids=>[1, 2]},
  #    3=>{:id=>3,...,:ancestor_ids=>[1, 3]},
  #    4=>{:id=>4,...,:ancestor_ids=>[4]}
  #    5=>{:id=>5,...,:ancestor_ids=>[1, 3, 5]},
  #    6=>{:id=>6,...,:ancestor_ids=>[4, 6]},
  #    7=>{:id=>7,...,:ancestor_ids=>[4, 7]}}

Это добавляет элемент, ключ которого :ancestor_ids, Нам больше не нужны ключи, поэтому мы будем извлекать значения, сортировать их по :ancestor_ids и отобразить результаты:

f = e.values
  #=> [{:id=>1,...,:ancestor_ids=>[1]},
  #    {:id=>2,...,:ancestor_ids=>[1, 2]},
  #    {:id=>3,...,:ancestor_ids=>[1, 3]},
  #    {:id=>4,...,:ancestor_ids=>[4]}
  #    {:id=>5,...,:ancestor_ids=>[1, 3, 5]},
  #    {:id=>6,...,:ancestor_ids=>[4, 6]},
  #    {:id=>7,...,:ancestor_ids=>[4, 7]}}

g = f.sort_by { |h| h[:ancestor_ids] }
  #=> [{:id=>1,...,:ancestor_ids=>[1]},
  #    {:id=>2,...,:ancestor_ids=>[1, 2]},
  #    {:id=>3,...,:ancestor_ids=>[1, 3]},
  #    {:id=>5,...,:ancestor_ids=>[1, 3, 5]},
  #    {:id=>4,...,:ancestor_ids=>[4]}
  #    {:id=>6,...,:ancestor_ids=>[4, 6]},
  #    {:id=>7,...,:ancestor_ids=>[4, 7]}}

indent = 2
g.each { |h| puts ' '*((h[:ancestor_ids].size-1)*indent) + "#{h[:name]}" }
parent test 1
  test 2
  test 3
    test 5
parent test 4
  test 6
  test 7

Точки

• Вам нужен хеш-элемент, ключ которого :top_level_category_id, учитывая, что :parent_id => nil для элементов верхнего уровня?
• Производственный код вызовет исключение, если при расчете e выше не было элемента d с ключом h[:parent_id] или значение h[:parent_id] не было ключа :ancestor_ids,
• Этот ответ основан на предположении, что для каждого элемента h из Data это не верхний уровень, h[:id] > h[:parent_id] когда h[:parent_id] не ноль. Если строки Data изначально не заказаны :id, они должны быть sort_by"изд :id в качестве первого шага.

* Если вы попытаетесь запустить его дома, он должен работать из командной строки, но IRB и PRY не могут обрабатывать строки, начинающиеся с точки

Answer 2

Требуется один проход по краю списка. Все узлы должны помещаться в памяти вместе; Список ребер должен составлять реальное дерево (т. е. не нужно проверять леса, правильные группы обеспечения доступности баз данных или циклы).

private static final Long DUMMY = null;
Node buildTree( Iterable< ? extends Edge > iedg ) {
    Map< Long, Node > mnod = new HashMap< Long, Node >();

    for ( Edge edg : iedg )
        getNode( mnod, iedg.getParentId() ).addChild(
            getNode( mnod, iedg.getId() ).withName( iedg.getName() )
        );

    return getNode( mnod, DUMMY ).firstChild();
}

private Node getNode( Map< Long, Node > mnod, Long lId ) {
    Node nod = mnod.get( lId );
    if ( null == nod )
        mnod.put( lId, nod = new Node().withId( lId ) );
    return nod;
}