Class: Gran::PathTree

Inherits:
Object
  • Object
show all
Includes:
Loggable
Defined in:
lib/gran/pathtree.rb

Overview

Provides a tree structure where each node is the basename of either a directory or a file. The pathname of a node is the concatenation of all basenames from the root node to the node in question, given as a Pathname object.

Each node must have a unique pathname within the tree it is part of.

A node can contain an associated ‘data’ object.

The following paths: basedir/file_1 basedir/file_2 basedir/dir1/file_3 basedir/dir1/file_4 basedir/dir2/dir3/file_5

are thus represented by the following path tree:

basedir

file_1
file_2
dir1
  file_3
  file_4
dir2
  dir3
    file_5

Tree info

see www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Loggable

included, #logger, #logger=

Constructor Details

#initialize(path, data = nil, parent = nil) ⇒ PathTree

Returns a new instance of PathTree.

Raises:

  • (ArgumentError) 


43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/gran/pathtree.rb', line 43

def initialize(path, data = nil, parent = nil)
  p = clean(path)
  raise ArgumentError, "Can not instantiate node with path == '.'" if p.to_s == "."
  raise ArgumentError, "Trying to create a non-root node using an absolute path" if p.absolute? && !parent.nil?

  head = p.descend.first

  @name = head
  @children = []
  @data = nil
  @parent = parent

  tail = p.relative_path_from(head)
  if tail.to_s == "."
    @data = data
    return
  end

  add_descendants(tail, data)
end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method

#method_missing(m) ⇒ Object

delegate method calls not implemented by PathTree to the associated ‘data’ object



423
424
425
426
427
 
# File 'lib/gran/pathtree.rb', line 423

def method_missing(m, ...)
  return super if data.nil?

  data.send(m, ...)
end

Instance Attribute Details

#abs_root ⇒ Object (readonly)

Returns the value of attribute abs_root.



40
41
42
 
# File 'lib/gran/pathtree.rb', line 40

def abs_root
  @abs_root
end

#children ⇒ Object (readonly)

Returns the value of attribute children.



40
41
42
 
# File 'lib/gran/pathtree.rb', line 40

def children
  @children
end

#data ⇒ Object

Returns the value of attribute data.



40
41
42
 
# File 'lib/gran/pathtree.rb', line 40

def data
  @data
end

#name ⇒ Object

Returns the value of attribute name.



40
41
42
 
# File 'lib/gran/pathtree.rb', line 40

def name
  @name
end

#parent ⇒ Object

Returns the value of attribute parent.



40
41
42
 
# File 'lib/gran/pathtree.rb', line 40

def parent
  @parent
end

Class Method Details

.build_from_fs(fs_point, prune: false) ⇒ Object

Builds a PathTree with its root as the given file system dir or file

fs_point

an absolute or relative path to a file or directory that

already exists in the file system.

prune

if false, add the entire, absolute, path to the fs_point to

the PathTree. If true, use only the basename of the fs_point as the root of the PathTree

You can submit a filter predicate that determine if a specific path shall be part of the PathTree or not ->(Pathname) { return true/false}

return

the node corresponding to the given fs_point in the resulting

pathtree or nil if no nodes matched the given predicate filter

Example

Build a pathtree containing all files under the “mydir” directory that ends with ‘.jpg’. The resulting tree will contain the absolute path to ‘mydir’ as nodes (eg ‘/home/gunnar/mydir’)

t = PathTree.build_from_fs(“./mydir”,true ) { |p| p.extname == “.jpg” }

Raises:

  • (ArgumentError) 


401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
 
# File 'lib/gran/pathtree.rb', line 401

def self.build_from_fs(fs_point, prune: false)
  top_node = Pathname.new(fs_point).cleanpath
  raise ArgumentError, "The path '#{fs_point}' does not exist in the file system!" unless top_node.exist?

  t = nil
  top_node.find do |path|
    p = Pathname.new(path)

    if (block_given? && yield(p)) || !block_given?
      t.nil? ? t = PathTree.new(p) : t.add_path(p)
    end
  end
  return nil if t.nil?

  # always return the entry node but prune the parents if
  # users wishes
  entry_node = t.node(top_node, from_root: true)
  (prune ? entry_node.dup : entry_node)
end

Instance Method Details

#add_descendants(path, data = nil) ⇒ Object

create a subtree from the given path and add it to this node

return

the leaf node for the added subtree

Raises:

  • (ArgumentError) 


104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/gran/pathtree.rb', line 104

def add_descendants(path, data = nil)
  p = clean(path)
  raise ArgumentError, "Can not add absolute path as descendant!!" if p.absolute?

  # invoked with 'current' name, ignore
  return self if p.to_s == "."

  head = p.descend.first
  tail = p.relative_path_from(head)
  last_segment = tail.to_s == "."

  ch = get_child(head)
  if ch.nil?
    @children << PathTree.new(head, last_segment ? data : nil, self)
    ch = @children.last
  end

  last_segment ? @children.last : ch.add_descendants(tail, data)
end

#add_path(path, data = nil) ⇒ Object

adds a new path to the root of the tree where this node is a member and associates the given data to the leaf of that path.

Raises:

  • (ArgumentError) 


126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/gran/pathtree.rb', line 126

def add_path(path, data = nil)
  p = clean(path)
  raise ArgumentError, "Trying to add already existing path: #{path}" unless node(p, from_root: true).nil?

  # prune any part of the given path that already exists in this
  # tree
  p.ascend do |q|
    n = node(q, from_root: true)
    next if n.nil?

    t = PathTree.new(p.relative_path_from(q).to_s, data)
    n.append_tree(t)
    return self
  end

  # no part of the given path existed within the tree
  raise ArgumentError, "Trying to add path with other root is not supported"
end

#append_tree(root_node) ⇒ Object

adds a copy of the given Pathtree as a subtree to this node. the subtree can not contain nodes that will end up having the same pathname as any existing node in the target tree. Note that ‘data’ attributes will not be copied. The copied Pathtree nodes will thus point to the same data attributes as the original.

Example

  1. Add my/new/tree to /1/2 -> /1/2/my/new/tree

  2. Add /my/new/tree to /1/2 -> ArgumentError - can not add root as subtree

  3. Trying to add ‘new/tree’ to ‘/my’ node in a tree with ‘/my/new/tree’ raises

ArgumentError since the pathname that would result already exists within the target tree.

Raises:

  • (ArgumentError) 


313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
 
# File 'lib/gran/pathtree.rb', line 313

def append_tree(root_node)
  raise ArgumentError, "Trying to append a root node as subtree!" if root_node.pathname.root?

  # make a copy to make sure it is a self-sustaining PathTree
  c = root_node.dup

  # get all leaf paths prepended with this node's name to check for
  # previous existance in this tree.
  p = c.leave_pathnames.collect { |p| Pathname.new(@name) / p }

  # duplicate ourselves to compare paths
  t = dup

  # check that no path in c would collide with existing paths
  common = Set.new(t.leave_pathnames) & Set.new(p)
  unless common.empty?
    str = common.collect { |p| p.to_s }.join(",")
    raise ArgumentError, "Can not append tree due to conflicting paths: #{str}"
  end

  # hook the subtree into this tree
  @children << c
  c.parent = self
end

#count ⇒ Object

returns

the number of nodes in the subtree with this node as

root



230
231
232
233
234
235
236
 
# File 'lib/gran/pathtree.rb', line 230

def count
  result = 0
  traverse_preorder do |level, node|
    result += 1
  end
  result
end

#dir?(path, from_root: true) ⇒ Boolean

Check if a given path exists in the tree as a directory (non-leaf node)

path

a String or Pathname with the path to check

from_root

if true, start the search from the root of the tree

return

true if the path exists and is a directory, false otherwise

Returns:

  • (Boolean) 


273
274
275
276
 
# File 'lib/gran/pathtree.rb', line 273

def dir?(path, from_root: true)
  n = node(path, from_root: from_root)
  !n.nil? && !n.leaf?
end

#dup(parent: nil) ⇒ Object

duplicate this node and all its children but keep the same data references as the originial nodes.

parent

the parent node of the copy, default = nil (the copy

is a root node)

returns

a copy of this node and all its descendents. The copy will

share any ‘data’ references with the original.



71
72
73
74
75
76
 
# File 'lib/gran/pathtree.rb', line 71

def dup(parent: nil)
  d = PathTree.new(@name.dup, @data, parent)

  @children.each { |c| d.children << c.dup(parent: d) }
  d
end

#filter(prune: false) ⇒ Object

Return a new PathTree with the nodes matching the given block

The copy will point to the same node data as the original.

prune

prune all parents to this node from the returned copy

Block

The given block will receive the level (from the entry node) and the node itself for each node.

Returns

the entry node to the new Pathtree or nil if no nodes matched the given block.

Example

copy = original.filter { |l, n| n.data == "smurf" }

The above will return a tree with nodes whose data is equal to ‘smurf’

Raises:

  • (InvalidArgument) 


514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
 
# File 'lib/gran/pathtree.rb', line 514

def filter(prune: false)
  raise InvalidArgument, "No block given!" unless block_given?

  # build the filtered copy
  copy = nil
  traverse_preorder do |level, n|
    if yield(level, n)
      p = n.pathname
      copy.nil? ? copy = PathTree.new(p, n.data) : copy.add_path(p, n.data)
    end
  end

  return nil if copy.nil?

  # always return the entry node but return a pruned version if
  # the user wishes
  entry_node = copy.node(pathname, from_root: true)
  (prune ? entry_node.dup : entry_node)
end

#find(sub_str, from_root: false) ⇒ <Type>

Return a list of nodes whose path match the given substring.

Parameters:

  • sub_str (String) —

    a string to search for in the pathnames of the nodes

  • (false) (boolean) —

    from_root True - start search from the root. False - start search from the current node.

Returns:

  • (<Type>) —

    <description>



454
455
456
457
458
459
460
461
462
463
 
# File 'lib/gran/pathtree.rb', line 454

def find(sub_str, from_root: false)
  result = []

  traverse_preorder do |level, node|
    q = from_root ? node.pathname : Pathname(segment) /
      node.pathname.relative_path_from(pathname)
    result << node if q.to_s.include?(sub_str)
  end
  result
end

#leaf? ⇒ Boolean

return

true if the node is a leaf, false otherwise

Returns:

  • (Boolean) 


239
240
241
 
# File 'lib/gran/pathtree.rb', line 239

def leaf?
  @children.length.zero?
end

#leave_pathnames(prune: false) ⇒ Object

return

an array with Pathnames of each full

path for the leaves in this tree



245
246
247
248
249
250
251
252
253
 
# File 'lib/gran/pathtree.rb', line 245

def leave_pathnames(prune: false)
  paths = []
  traverse_postorder do |l, n|
    next unless n.leaf?

    paths << (prune ? n.pathname.relative_path_from(pathname) : n.pathname)
  end
  paths
end

#match(regex, prune: false) ⇒ Object

Return a new PathTree with the nodes whith pathname matching the given regex.

The copy will point to the same node data as the original.

regex

a Regex matching the pathname of the nodes to be included in

the copy

prune

remove all parents to this node in the returned copy

Returns

the entry node in a new PathTree with the nodes with pathnames matching the given regex or nil if no nodes match



477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
 
# File 'lib/gran/pathtree.rb', line 477

def match(regex, prune: false)
  copy = nil

  traverse_preorder do |level, n|
    p = n.pathname
    next unless regex&.match?(p.to_s)

    copy.nil? ? copy = PathTree.new(p, n.data) : copy.add_path(p, n.data)
  end
  return nil if copy.nil?

  # always return the entry node but return a pruned version if
  # the user wishes
  entry_node = copy.node(pathname, from_root: true)
  (prune ? entry_node.dup : entry_node)
end

#node(path, from_root: false) ⇒ Object

Finds the node corresponding to the given path.

path

a String or Pathname with the path to search for

from_root

if true start the search from the root of the tree where

this node is a member. If false, start the search from this node’s children.

return

the node with the given path or nil if the path

does not exist within this pathtree



287
288
289
290
291
292
293
294
295
296
297
298
299
 
# File 'lib/gran/pathtree.rb', line 287

def node(path, from_root: false)
  p = clean(path)
  root = nil

  traverse_preorder do |level, node|
    q = from_root ? node.pathname : node.pathname.relative_path_from(pathname)
    if q == p
      root = node
      break
    end
  end
  root
end

#pathname ⇒ Object

return

a Pathname with the complete path from the root of the

tree where this node is a member to this node (inclusive).



95
96
97
98
99
 
# File 'lib/gran/pathtree.rb', line 95

def pathname
  return @name if @parent.nil?

  (@parent.pathname / @name).cleanpath
end

#relative_path_from(node) ⇒ Object

return

a Pathname containing the relative path to this node as seen from the

given node



376
377
378
 
# File 'lib/gran/pathtree.rb', line 376

def relative_path_from(node)
  pathname.relative_path_from(node.pathname)
end

#respond_to_missing?(method_name, include_private = false) ⇒ Boolean

Returns:

  • (Boolean) 


429
430
431
432
433
 
# File 'lib/gran/pathtree.rb', line 429

def respond_to_missing?(method_name, include_private = false)
  return super if data.nil?

  data.respond_to?(method_name)
end

#root ⇒ Object

return

the root node of the tree where this node is a member



261
262
263
264
265
 
# File 'lib/gran/pathtree.rb', line 261

def root
  return self if root?

  @parent.root
end

#root? ⇒ Boolean

return

true if this node does not have a parent node

Returns:

  • (Boolean) 


256
257
258
 
# File 'lib/gran/pathtree.rb', line 256

def root?
  @parent.nil?
end

#segment ⇒ Object

return

a String with the path segment for this node



89
90
91
 
# File 'lib/gran/pathtree.rb', line 89

def segment
  @name.to_s
end

#sort_leaf_first! ⇒ Object

Sort the nodes on each level in the tree in lexical order but put leafs before non-leafs.



222
223
224
225
226
 
# File 'lib/gran/pathtree.rb', line 222

def sort_leaf_first!
  @children.sort! { |a, b| leaf_first(a, b) }
  @children.each(&:sort_leaf_first!)
  self
end

#split_stem ⇒ Object

Splits the node’s path into

  • a ‘stem’, the common path to all nodes in this tree that are on the

same level as this node or closer to the root.

  • a ‘crown’, the remaining path when the stem has been removed from this

node’s pathname

Example

n.split_stem for the following tree:

base
  |- dir
      |- leaf_1
      |- branch
            |- leaf_2

yields

["base/dir", "leaf_1"] when n == leaf_1
["base/dir", "branch/leaf_2"] when n == leaf_2
["base", "dir"] when n == "dir"
[nil, "base"] when n == "base"
return
stem, crown


360
361
362
363
364
365
366
367
368
369
370
371
372
 
# File 'lib/gran/pathtree.rb', line 360

def split_stem
  r = root
  s = pathname.descend do |stem|
    n = r.node(stem, from_root: true)
    break n if n.children.count != 1 || n == self
  end

  if s == self
    [root? ? nil : s.parent.pathname, @name]
  else
    [s.pathname, pathname.relative_path_from(s.pathname)]
  end
end

#to_s ⇒ Object 



435
436
437
438
439
440
441
 
# File 'lib/gran/pathtree.rb', line 435

def to_s
  traverse_preorder do |level, n|
    str = " " * 4 * level + "|-- " + n.segment.to_s
    str += " <#{n.data}>" unless n.data.nil?
    str
  end.join("\n")
end

#traverse_levelorder(level = 0, &block) ⇒ Object

Visits bredth-first left -> right for each level top-down

level

the number of hops from the root node

block

the user supplied block that is executed for every visited node

the level and node are given as block parameters

Returns

A new array containing the values returned by the block

Examples

Get an array with the name of each node together with the level of the node

traverse_levelorder { |level, n| "#{level} #{n.segment}" }



202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/gran/pathtree.rb', line 202

def traverse_levelorder(level = 0, &block)
  result = []
  # the node of the original call
  result << yield(level, self) if level == 0

  # this level
  @children.each do |c|
    result << yield(level + 1, c)
  end

  # next level
  @children.each do |c|
    result.concat(c.traverse_levelorder(level + 1, &block))
  end

  result
end

#traverse_postorder(level = 0, &block) ⇒ Object

Visits depth-first by left -> right -> root

level

the number of hops from the root node

block

the user supplied block that is executed for every visited node

the level and node are given as block parameters

Returns

A new array containing the values returned by the block

Examples

Get an array of each node together with the level of the node

traverse_postorder{ |level, n| "#{level} #{n.segment}" }



181
182
183
184
185
186
187
 
# File 'lib/gran/pathtree.rb', line 181

def traverse_postorder(level = 0, &block)
  result = []
  @children.each do |c|
    result.concat(c.traverse_postorder(level + 1, &block))
  end
  result << yield(level, self)
end

#traverse_preorder(level = 0, &block) ⇒ Object

Visits depth-first by root -> left -> right

level

the number of hops from the root node

block

the user supplied block that is executed for every visited node

the level and node are given as block parameters

Returns

A new array containing the values returned by the block

Examples

Get an array with name of each node together with the level of the node

traverse_preorder{ |level, n| "#{level} #{n.segment}" }



159
160
161
162
163
164
165
 
# File 'lib/gran/pathtree.rb', line 159

def traverse_preorder(level = 0, &block)
  result = [yield(level, self)]
  @children.each do |c|
    result.append(*c.traverse_preorder(level + 1, &block))
  end
  result
end