Contents

# typed: ignore

# Copyright (c) 2015 Sqreen. All Rights Reserved.
# Please refer to our terms for more information: https://www.sqreen.com/terms.html

# TODO: move to Sqreen::IP::Trie

module Sqreen
  # bit starts at 0 (most significant)
  Node = Struct.new(:bit, :prefix, :l, :r, :parent) do
    def initialize(*args)
      super
      raise ArgumentError, 'no bit given' if bit.nil?
    end

    def empty?
      prefix.nil?
    end

    # cover the whole tree
    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
  end
end

Version data entries

10 entries across 10 versions & 1 rubygems

Version	Path
sqreen-1.25.1	lib/sqreen/node.rb
sqreen-1.25.0	lib/sqreen/node.rb
sqreen-1.24.3	lib/sqreen/node.rb
sqreen-1.24.2	lib/sqreen/node.rb
sqreen-1.24.1	lib/sqreen/node.rb
sqreen-1.24.0	lib/sqreen/node.rb
sqreen-1.23.2	lib/sqreen/node.rb
sqreen-1.23.1	lib/sqreen/node.rb
sqreen-1.23.0	lib/sqreen/node.rb
sqreen-1.22.1	lib/sqreen/node.rb