Tree node using an array of hashes

Question

I have the following array of hashes:

[
  {key: 1, reference: 'reference', path: '.../public/shared/file_1.txt', type: 'public'},
  {key: 2, reference: 'reference', path: '.../public/shared/file_2.txt', type: 'public'},
  {key: 3, reference: 'reference', path: '.../public/shared/sub_folder/file_3.txt', type: 'public'},
  {key: 4, reference: 'reference', path: '.../public/shared/sub_folder/file_4.txt', type: 'public'},
  {key: 5, reference: 'reference', path: '.../log/file_5.txt', type: 'log'},
  {key: 5, reference: 'reference', path: '.../tmp/cache/file_6.txt', type: 'log'},
]

Then using the path structure of each node I would like create a Tree like this:

[
  { 
    key: 'root', folder: true, title: 'root',
    children: [
                {
                  key: 'public', folder: true, title: 'public',
                  children: [
                              {
                                key: 'shared', folder: true, title: 'shared',
                                children: [ 
                                            { key: 1, title: 'file_1.txt' },
                                            { key: 2, title: 'file_2.txt' },
                                            {
                                              key: 'sub_folder', folder: true, title: 'sub_folder',
                                              children: [
                                                { key: 3, title: 'file_3.txt' },
                                                { key: 4, title: 'file_4.txt' }
                                              ]
                                            }
                                          ]
                              }
                            ]
                },
                {
                  key: 'log', folder: true, title: 'log', children: [ { key: 5, title: 'file_5.txt' } ]
                },
                {
                  key: 'tmp', folder: true, title: 'tmp',
                  children: [
                              { key: 'cache', folder: true, title: 'cache', children: [ { key: 6, title: 'file_6.txt' } }
                            ]
                }
              ]
  }
]

Would be possible to create that structure using the path of each node? I'm using Ruby on Rails.

DjezzzL · Accepted Answer · 2017-05-27 17:04:42Z

1

You could define class like this one online repl:

class Tree 
  attr_reader :array, :tree

  def initialize(array)
    @array = array
    create_tree!
  end

  private

  def create_tree!
    @tree = []
    array.each do |hash|
      process_path(hash[:path].gsub('...', 'root').split('/'))
    end
  end

  def process_path(array)
    current = @tree
    array.each do |folder_or_file|
      if persist = current.find { |hash| hash[:key] == folder_or_file }
        current = persist[:children]
      else
        current << {
          key: folder_or_file,
          folder: folder_or_file['.'].nil?,
          title: folder_or_file,
          children: []
        }
        current = current.last[:children]
      end
    end
  end
end

arr = [
  {key: 1, reference: 'reference', path: '.../public/shared/file_1.txt', type: 'public'},
  {key: 2, reference: 'reference', path: '.../public/shared/file_2.txt', type: 'public'},
  {key: 3, reference: 'reference', path: '.../public/shared/sub_folder/file_3.txt', type: 'public'},
  {key: 4, reference: 'reference', path: '.../public/shared/sub_folder/file_4.txt', type: 'public'},
  {key: 5, reference: 'reference', path: '.../log/file_5.txt', type: 'log'},
  {key: 5, reference: 'reference', path: '.../tmp/cache/file_6.txt', type: 'log'},
]

Tree.new(arr).tree

answered May 27, 2017 at 17:04

DjezzzL

8456 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Cary Swoveland Over a year ago

It appears a small mod would be required if file names were not required suffixes.

Cary Swoveland · Accepted Answer · 2017-05-28 05:58:21Z

I have provided a recursive solution.

Code

def doit(arr)
  a = arr.map do |g|
    *front, last = ['root', *g[:path][4..-1].split('/')]
    [front, { key: g[:key], title: last }]
  end
  recurse a
end

def recurse(a)
  a.reject { |dirs, _| dirs.empty? }. 
    group_by { |dirs,_| dirs.shift }.
    map do |dir,v|
      empty, non_empty = v.partition { |d,_| d.empty? }
      { key: dir, folder: true, title: dir,
        children: [*empty.map(&:last), *recurse(non_empty)] }
    end
end

Example

arr = [
  { key: 1, reference: 'reference', path: '.../public/shared/file_1.txt',
    type: 'public' },
  { key: 2, reference: 'reference', path: '.../public/shared/file_2.txt',
    type: 'public' },
  { key: 3, reference: 'reference', path: '.../public/shared/sub_folder/file_3.txt',
    type: 'public' },
  { key: 4, reference: 'reference', path: '.../public/shared/sub_folder/file_4.txt',
    type: 'public' },
  { key: 5, reference: 'reference', path: '.../log/file_5.txt',
    type: 'log' },
  { key: 6, reference: 'reference', path: '.../tmp/cache/file_6.txt',
    type: 'log' }
]

We may now construct the desired array from arr:

doit arr 
  #=> [{:key=>"root", :folder=>true, :title=>"root", :children=>
  #     [{:key=>"public", :folder=>true, :title=>"public", :children=>
  #       [{:key=>"shared", :folder=>true, :title=>"shared", :children=>
  #         [{:key=>1, :title=>"file_1.txt"},
  #          {:key=>2, :title=>"file_2.txt"},
  #          {:key=>"sub_folder", :folder=>true, :title=>"sub_folder",
  #           :children=>[{:key=>3, :title=>"file_3.txt"},
  #                       {:key=>4, :title=>"file_4.txt"}
  #                      ]
  #          }
  #         ]
  #        }
  #       ]
  #      },
  #      {:key=>"log", :folder=>true, :title=>"log",
  #       :children=>[{:key=>5, :title=>"file_5.txt"}]
  #      },
  #      {:key=>"tmp", :folder=>true, :title=>"tmp",
  #       :children=>[{:key=>"cache", :folder=>true, :title=>"cache",
  #                    :children=>[{:key=>6, :title=>"file_6.txt"}]
  #                   }
  #                  ]
  #      }
  #     ]
  #    }
  #   ]

Explanation

The steps are as follows (for arr in the example),

In doit

  a = arr.map do |g|
    *front, last = ['root', *g[:path][4..-1].split('/')]
    [front, { key: g[:key], title: last }]
  end
    #=> [[["root", "public", "shared"], {:key=>1, :title=>"file_1.txt"}],
    #    [["root", "public", "shared"], {:key=>2, :title=>"file_2.txt"}],
    #    [["root", "public", "shared", "sub_folder"], {:key=>3, :title=>"file_3.txt"}],
    #    [["root", "public", "shared", "sub_folder"], {:key=>4, :title=>"file_4.txt"}],
    #    [["root", "log"], {:key=>5, :title=>"file_5.txt"}],
    #    [["root", "tmp", "cache"], {:key=>6, :title=>"file_6.txt"}]]

Breaking this down, we perform the following calculations.

The first element of arr is passed to map's block and becomes the value of the block variableg`:

  g = arr.first
    #=> {:key=>1, :reference=>"reference",
    #    :path=>".../public/shared/file_1.txt", :type=>"public"}

The block calculations are then performed.

b = g[:path]
  #=> ".../public/shared/file_1.txt"
c = b[4..-1]
  #=> "public/shared/file_1.txt"
d = c.split('/')
  #=> ["public", "shared", "file_1.txt"]
e = ['root', *d]
  #=> ["root", "public", "shared", "file_1.txt"]
*front, last = e
  #=> ["root", "public", "shared", "file_1.txt"]
front
  #=> ["root", "public", "shared"]
last
  #=> "file_1.txt"
f = g[:key]
  #=>
[front, { key: f, title: last }]
  #=> [["root", "public", "shared"], {:key=>1, :title=>"file_1.txt"}]

The mapping of the remaining elements of arr is similar.

The array a above is passed to recurse. The first step is to remove any elements [d, h] (d being an array of directories, h a hash) for which d is empty. This is a technical requirement that needed deeper in the recursion, after one or more hashes are added to the array that is the value of :children.

m = a.reject { |dirs, _| dirs.empty? }
  #=> a (no elements are removed)

The next step is group elements [dirs, h] of m by the first element of dirs. I've used dirs.shift in the block below to also remove that element from the array dirs.

n = m.group_by { |dirs,_| dirs.shift }
  #=> {"root"=>[ 
  #     [["public", "shared"], {:key=>1, :title=>"file_1.txt"}],
  #     [["public", "shared"], {:key=>2, :title=>"file_2.txt"}],
  #     [["public", "shared", "sub_folder"], {:key=>3, :title=>"file_3.txt"}],
  #     [["public", "shared", "sub_folder"], {:key=>4, :title=>"file_4.txt"}],
  #     [["log"], {:key=>5, :title=>"file_5.txt"}],
  #     [["tmp", "cache"], {:key=>6, :title=>"file_6.txt"}]
  #    ]
  #   }

The first element of n is now passed to map's block and the block variables are assigned:

dir, v = n.first
  #=> ["root", [
  #      [["public", "shared"], {:key=>1, :title=>"file_1.txt"}],
  #      [["public", "shared"], {:key=>2, :title=>"file_2.txt"}], 
  #      [["public", "shared", "sub_folder"], {:key=>3, :title=>"file_3.txt"}],
  #      [["public", "shared", "sub_folder"], {:key=>4, :title=>"file_4.txt"}],
  #      [["log"], {:key=>5, :title=>"file_5.txt"}],
  #      [["tmp", "cache"], {:key=>6, :title=>"file_6.txt"}]
  #    ]
  #   ]
dir
  #=> "root"
v #=> [[["public", "shared"], {:key=>1, :title=>"file_1.txt"}],
  #    ...
  #    [["tmp", "cache"], {:key=>6, :title=>"file_6.txt"}]
  #   ]

The block calculation is then performed.

  empty, non_empty =  v.partition { |d,_| d.empty? }
  empty
    #=> []
  non_empty
    #=> [[["public", "shared"], {:key=>1, :title=>"file_1.txt"}],
    #    [["public", "shared"], {:key=>2, :title=>"file_2.txt"}], 
    #    [["public", "shared", "sub_folder"], {:key=>3, :title=>"file_3.txt"}],
    #    [["public", "shared", "sub_folder"], {:key=>4, :title=>"file_4.txt"}],
    #    [["log"], {:key=>5, :title=>"file_5.txt"}],
    #    [["tmp", "cache"], {:key=>6, :title=>"file_6.txt"}]
    #   ]
  p = empty.map(&:last)
    #=> []
  { key: dir, folder: true, title: dir,
    children: [*p, *recurse(non_empty)] }
    #=> { key: 'root', folder: true, title: 'root',
    #     children: [*[], *recurse(non_empty)] }

The value of the last key :children reduces to [*recurse(non_empty)]. As shown, recurse is now called recursively, with argument non-empty.

The remaining calculations are similar but things get a bit different when recurse is passed an array having one or more elements for which the dirs array contains a single element, resulting in the associated hash being added to an array that is the value of a key :children. To fully understand the calculations it may be necessary to add some puts statements to the code.

Collectives™ on Stack Overflow

Tree node using an array of hashes

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related