Sha256: c14dcba5ae99b72caaae2c2911a710a53aa83ca1e206249ac4cd41d20e6d71bc
Contents?: true
Size: 1019 Bytes
Versions: 29
Compression:
Stored size: 1019 Bytes
Contents
# typed: false
# 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
29 entries across 29 versions & 1 rubygems