Class: Sqreen::Node

Inherits:
Struct
  • Object
show all
Defined in:
lib/sqreen/node.rb

Overview

bit starts at 0 (most significant)

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ Node

Returns a new instance of Node.

Raises:

  • (ArgumentError) 


11
12
13
14
 
# File 'lib/sqreen/node.rb', line 11

def initialize(*args)
  super
  raise ArgumentError, 'no bit given' if bit.nil?
end

Instance Attribute Details

#bit ⇒ Object

Returns the value of attribute bit

Returns:

  • (Object) —

    the current value of bit



10
11
12
 
# File 'lib/sqreen/node.rb', line 10

def bit
  @bit
end

#l ⇒ Object

Returns the value of attribute l

Returns:

  • (Object) —

    the current value of l



10
11
12
 
# File 'lib/sqreen/node.rb', line 10

def l
  @l
end

#parent ⇒ Object

Returns the value of attribute parent

Returns:

  • (Object) —

    the current value of parent



10
11
12
 
# File 'lib/sqreen/node.rb', line 10

def parent
  @parent
end

#prefix ⇒ Object

Returns the value of attribute prefix

Returns:

  • (Object) —

    the current value of prefix



10
11
12
 
# File 'lib/sqreen/node.rb', line 10

def prefix
  @prefix
end

#r ⇒ Object

Returns the value of attribute r

Returns:

  • (Object) —

    the current value of r



10
11
12
 
# File 'lib/sqreen/node.rb', line 10

def r
  @r
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


16
17
18
 
# File 'lib/sqreen/node.rb', line 16

def empty?
  prefix.nil?
end

#walk(max_bits, empty_nodes = false) ⇒ Object

cover the whole tree



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/sqreen/node.rb', line 21

def walk(max_bits, empty_nodes = false)
  xstack = Array.new(max_bits + 1)
  sidx = 0 # stack index
  xhead = self
  xcur = xhead
  until xcur.nil?
    yield xcur unless xcur.empty? && !empty_nodes

    if xcur.l
      if xcur.r
        xstack[sidx] = xcur.r
        sidx += 1
      end
      xcur = xcur.l
    elsif xcur.r
      xcur = xcur.r
    elsif sidx.nonzero?
      sidx -= 1
      xcur = xstack[sidx]
    else
      xcur = nil
    end
  end
end