Sorting in nested set

Question

Parent 1
 |
 |-Child 1
 |- - Child 1_GrandChild1
 |
 |-Child 2
 |
Parent 2
 |
 |-Child 1
 |- - Child 1_GrandChild1
 |- - Child 1_GrandChild2
 |
 |-Child 2
 |
 |-Child 3
 |- - Child 3_GrandChild1
 |
Parent 3

I want to sort this nested set structure in alphabetical order, parents should be sorted first and then the child and then the grandchildren.

This has already been implemented in awesome nested set gem in rails but it doesn’t give me the grandchildren in sorted order, only the parents are in sorted order. I also tried using order_column property in the model section but I got the same result - that parents were sorted but not the grandchildren. I also checked the question mentioned here and here but it was of no help. How can we approach this problem?

Edit: So it's an array of objects.

Input:

A
 - C
 - B

Output:

A
 - B
 - C

The problem is if I have grandchildren, the existing implementations do not sort it.

How are you representing this data structure in code? Please show an example of how it's built. — max pleaner, Mar 16 '20 at 23:22
Please check your example to confirm it is correct (especially Parent 2, Child 1's children) and show your desired return value for the example, which I assume is an array of strings. If you break up the strings how will you identify the parent and grandparent of, say, `" |- - Child 2_GrandChild2"`? — Cary Swoveland, Mar 17 '20 at 04:35

score 0 · Answer 1 · answered Mar 17 '20 at 06:08

I don't really know if the following is what you are looking for, but if it isn't perhaps you can adapt it to your needs.

str =<<~END
Parent 1
 |
 |-Child 1
 |- - Child 1_GrandChild1
 |
 |-Child 2
 |
Parent 2
 |
 |-Child 1
 |- - Child 1_GrandChild1
 |- - Child 1_GrandChild2
 |
 |-Child 2
 |
 |-Child 3
 |- - Child 3_GrandChild1
 |
Parent 3
END

str.each_line.with_object([]) do |s,arr|
  s.chomp!
  case s
  when /\A\p{Alpha}+\s+\d+\z/
    arr << [0,s]
  when /\A \|\-\p{Alpha}+\s+\d+\z/
    arr << [1,s[/[A-Z].*/]]
  when /\A \|\- \- \p{Alpha}+ \d+\_\p{Alpha}+\d+\z/
    arr << [2,s[/\d.*/]]
  end
end.sort.map(&:last)
  #=> ["Parent 1", "Parent 2", "Parent 3", "Child 1", "Child 1", "Child 2",
  #    "Child 2", "Child 3", "1_GrandChild1", "1_GrandChild1", "1_GrandChild2",
  #    "3_GrandChild1"]

Note that

a = str.each_line.with_object([]) do |s,arr|
  s.chomp!
  case s
  when /\A\p{Alpha}+\s+\d+\z/
    arr << [0,s]
  when /\A \|\-\p{Alpha}+\s+\d+\z/
    arr << [1,s[/[A-Z].*/]]
  when /\A \|\- \- \p{Alpha}+ \d+\_\p{Alpha}+\d+\z/
    arr << [2,s[/\d.*/]]
  end
end
  #=> [[0, "Parent 1"], [1, "Child 1"], [2, "1_GrandChild1"],
  #    [1, "Child 2"], [0, "Parent 2"], [1, "Child 1"],
  #    [2, "1_GrandChild1"], [2, "1_GrandChild2"], [1, "Child 2"],
  #    [1, "Child 3"], [2, "3_GrandChild1"], [0, "Parent 3"]]

sort, therefore, first sorts on the first element of each two-element array then sorts on the second element to break ties:

b = a.sort
  #=> [[0, "Parent 1"], [0, "Parent 2"], [0, "Parent 3"],
  #    [1, "Child 1"], [1, "Child 1"], [1, "Child 2"], [1, "Child 2"],
  #    [1, "Child 3"],
  #    [2, "1_GrandChild1"], [2, "1_GrandChild1"], [2, "1_GrandChild2"],
  #    [2, "3_GrandChild1"]]

Lastly, b.map(&:last) maps each of these two-element arrays into the last element of the array.

Nick Gobin · Answer 2 · 2023-07-17T21:58:50.217

I took a stab at answering this here. I think the solution does what you want by adding the below to the model that acts_as_nested_set:

  def sorted_heir_list(target = self, set = self.descendants)
    sorted_list = [target]
    kids = set.select{|i| i.parent_id == target.id}.sort_by{|j| j.name}
    kids.each do |k|
      sorted_list.concat(sorted_heir_list(k, set))
    end
    sorted_list
  end

Thus, calling category.sorted_heir_list gives a flat array of objects sorted by name, while retaining the heirarchy and only incurring a single DB hit.

Sorting in nested set

2 Answers2