Module: LeftLeaningRedBlackTree::Printable

Included in:
TreeNode
Defined in:
lib/left_leaning_red_black_tree/printable.rb

Instance Method Summary collapse

Instance Method Details

#all_elements_nil?(nodes) ⇒ Boolean

Returns:

  • (Boolean) 


72
73
74
75
76
77
78
79
80
 
# File 'lib/left_leaning_red_black_tree/printable.rb', line 72

def all_elements_nil?(nodes)
  nodes.each do |node|
    if !node.null?
      return false
    end
  end

  true
end

#max_level ⇒ Object 



68
69
70
 
# File 'lib/left_leaning_red_black_tree/printable.rb', line 68

def max_level
  [@left.max_level, @right.max_level].max + 1
end

#print_node(nodes, level, max_level) ⇒ Object 



3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/left_leaning_red_black_tree/printable.rb', line 3

def print_node(nodes, level, max_level)
  if nodes.empty? || all_elements_nil?(nodes)
    return
  end

  floor = max_level - level
  endge_lines = 2 ** ([floor - 1, 0].max)
  first_spaces = (2 ** floor) - 1
  between_spaces = (2 ** (floor + 1)) - 1

  print_white_spaces(first_spaces)

  new_nodes = []
  nodes.each do |node|
      if node.key.nil?
        new_nodes << NullNode.new
        new_nodes << NullNode.new
        print " "
      else
        print(node.key)
        new_nodes << node.left
        new_nodes << node.right
      end

      print_white_spaces(between_spaces)
  end
  puts

  1.upto(endge_lines) do |i|
      nodes.each do |node|
          print_white_spaces(first_spaces - i)
          if node.key.nil?
              print_white_spaces(endge_lines + endge_lines + i + 1)
              next
          end

          if node.left.key.nil?
            print_white_spaces(1)
          else
            print "/"
          end

          print_white_spaces(i + i - 1)

          if node.right.key.nil?
            print_white_spaces(1)
          else
            print "\\"
          end

          print_white_spaces(endge_lines + endge_lines - i)
      end

      puts
  end

  print_node(new_nodes, level + 1, max_level)
end

#print_white_spaces(count) ⇒ Object 



62
63
64
65
66
 
# File 'lib/left_leaning_red_black_tree/printable.rb', line 62

def print_white_spaces(count)
  count.times do
    print " "
  end
end