Tree to nested set algo (copied from collectiveidea/awesome_nested_set)

tree.rb

module CollectiveIdea #:nodoc:
  module Acts #:nodoc:
    module NestedSet #:nodoc:
      class Tree
        attr_reader :model, :validate_nodes
        attr_accessor :indices

        delegate :left_column_name, :right_column_name, :quoted_parent_column_full_name,
                 :order_for_rebuild, :scope_for_rebuild, :counter_cache_column_name,
                 :to => :model

        def initialize(model, validate_nodes)
          @model = model
          @validate_nodes = validate_nodes
          @indices = {}
        end

        def rebuild!
          # Don't rebuild a valid tree.
          return true if model.valid?

          root_nodes.each do |root_node|
            # setup index for this scope
            indices[scope_for_rebuild.call(root_node)] ||= 0
            set_left_and_rights(root_node)
            reset_counter_cache(root_node)
          end
        end

        private

        def increment_indice!(node)
          indices[scope_for_rebuild.call(node)] += 1
        end

        def set_left_and_rights(node)
          set_left!(node)
          # find
          node_children(node).each { |n| set_left_and_rights(n) }
          set_right!(node)

          node.save!(:validate => validate_nodes)
        end

        def node_children(node)
          model.where(["#{quoted_parent_column_full_name} = ? #{scope_for_rebuild.call(node)}", node.primary_id]).
                order(order_for_rebuild)
        end

        def root_nodes
          model.where("#{quoted_parent_column_full_name} IS NULL").order(order_for_rebuild)
        end

        def set_left!(node)
          node[left_column_name] = increment_indice!(node)
        end

        def set_right!(node)
          node[right_column_name] = increment_indice!(node)
        end

        def reset_counter_cache(node)
          return unless counter_cache_column_name
          node.class.reset_counters(node.id, :children)

          node.children.each do |child|
            reset_counter_cache(child)
          end
        end
      end
    end
  end
end

TreeToSetService.php

<?php namespace App\Model\Menu;

use Illuminate\Support\Collection;

class TreeToSetService
{
    public $indices = [];
    private $leftColumnName = 'lft';
    private $rightColumnName = 'rgt';
    private $nodeScope = 'version_id';

    public function treeArrayToInsert($rootNode)
    {
        $this->setUpIndices($rootNode);
        $rootNode = $this->setLeftAndRights($rootNode);

        return $this->flattenTree($rootNode, new Collection())->toArray();
    }

    private function setUpIndices($node)
    {
        if (!isset($this->indices[$this->scopeForBuild($node)])) {
            $this->indices[$this->scopeForBuild($node)] = 0;
        }
    }

    private function scopeForBuild($node)
    {
        $scope = $node[$this->nodeScope];

        return $scope;
    }

    private function incrementIndex($node)
    {
        $this->indices[$this->scopeForBuild($node)] += 1;

        return $this->indices[$this->scopeForBuild($node)];
    }

    private function setLeftAndRights($node)
    {
        $node = $this->setLeft($node);

        foreach ($this->childNodes($node) as $i => $child) {
            $child = $this->setLeftAndRights($child);
            $node['children'][$i] = $child;
        }

        $node = $this->setRight($node);

        return $node;
    }

    private function childNodes($node)
    {
        $children = [];

        if (isset($node['children'])) {
            $children = $node['children'];
            unset($node['children']);
        }

        return $children;
    }

    private function flattenTree(array $item, Collection $rows, $parentId = null, $depth = 0)
    {
        $item['depth'] = $depth;
        $item['parent_id'] = $parentId;

        if (isset($item['children'])) {
            foreach ($this->childNodes($item) as $child) {
                $this->flattenTree($child, $rows, $item['navigation_item_id'], $depth + 1);
            }

            unset($item['children']);
        }

        $rows->push($item);

        return $rows;
    }

    private function setLeft($node)
    {
        $node[$this->leftColumnName] = $this->incrementIndex($node);

        return $node;
    }

    private function setRight($node)
    {
        $node[$this->rightColumnName] = $this->incrementIndex($node);

        return $node;
    }

    private function resetIndices($node)
    {
        $this->indices[$this->scopeForBuild($node)] = 0;
    }
}