Class: PathTree

Inherits:
Object
  • Object
show all
Defined in:
lib/giblish/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

Constructor Details

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

Returns a new instance of PathTree.

Raises:

  • (ArgumentError) 


40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/giblish/pathtree.rb', line 40

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, *args, &block) ⇒ Object

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



409
410
411
412
413
 
# File 'lib/giblish/pathtree.rb', line 409

def method_missing(m, *args, &block)
  return super if data.nil?

  data.send(m, *args, &block)
end

Instance Attribute Details

#abs_root ⇒ Object (readonly)

Returns the value of attribute abs_root.



37
38
39
 
# File 'lib/giblish/pathtree.rb', line 37

def abs_root
  @abs_root
end

#children ⇒ Object (readonly)

Returns the value of attribute children.



37
38
39
 
# File 'lib/giblish/pathtree.rb', line 37

def children
  @children
end

#data ⇒ Object

Returns the value of attribute data.



37
38
39
 
# File 'lib/giblish/pathtree.rb', line 37

def data
  @data
end

#name ⇒ Object

Returns the value of attribute name.



37
38
39
 
# File 'lib/giblish/pathtree.rb', line 37

def name
  @name
end

#parent ⇒ Object

Returns the value of attribute parent.



37
38
39
 
# File 'lib/giblish/pathtree.rb', line 37

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) 


387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
 
# File 'lib/giblish/pathtree.rb', line 387

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) 


101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/giblish/pathtree.rb', line 101

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) 


123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/giblish/pathtree.rb', line 123

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) 


299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
 
# File 'lib/giblish/pathtree.rb', line 299

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



227
228
229
230
231
232
233
 
# File 'lib/giblish/pathtree.rb', line 227

def count
  result = 0
  traverse_preorder do |level, node|
    result += 1
  end
  result
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.



68
69
70
71
72
73
 
# File 'lib/giblish/pathtree.rb', line 68

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) 


478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
 
# File 'lib/giblish/pathtree.rb', line 478

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

#leaf? ⇒ Boolean

return

true if the node is a leaf, false otherwise

Returns:

  • (Boolean) 


236
237
238
 
# File 'lib/giblish/pathtree.rb', line 236

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



242
243
244
245
246
247
248
249
250
 
# File 'lib/giblish/pathtree.rb', line 242

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



441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
 
# File 'lib/giblish/pathtree.rb', line 441

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



273
274
275
276
277
278
279
280
281
282
283
284
285
 
# File 'lib/giblish/pathtree.rb', line 273

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).



92
93
94
95
96
 
# File 'lib/giblish/pathtree.rb', line 92

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



362
363
364
 
# File 'lib/giblish/pathtree.rb', line 362

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

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

Returns:

  • (Boolean) 


415
416
417
418
419
 
# File 'lib/giblish/pathtree.rb', line 415

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

  data.respond_to?(method_name)
end

#root ⇒ Object

return

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



258
259
260
261
262
 
# File 'lib/giblish/pathtree.rb', line 258

def root
  return self if root?

  @parent.root
end

#root? ⇒ Boolean

return

true if this node does not have a parent node

Returns:

  • (Boolean) 


253
254
255
 
# File 'lib/giblish/pathtree.rb', line 253

def root?
  @parent.nil?
end

#segment ⇒ Object

return

a String with the path segment for this node



86
87
88
 
# File 'lib/giblish/pathtree.rb', line 86

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.



219
220
221
222
223
 
# File 'lib/giblish/pathtree.rb', line 219

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 


346
347
348
349
350
351
352
353
354
355
356
357
358
 
# File 'lib/giblish/pathtree.rb', line 346

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 



421
422
423
424
425
426
427
 
# File 'lib/giblish/pathtree.rb', line 421

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}" }



199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/giblish/pathtree.rb', line 199

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}" }



178
179
180
181
182
183
184
 
# File 'lib/giblish/pathtree.rb', line 178

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}" }



156
157
158
159
160
161
162
 
# File 'lib/giblish/pathtree.rb', line 156

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