Sha256: d07d61ecd90f4bb17581d132b9cf375ea20132d1b3104edf28f476729b476d9e

Contents?: true

Size: 1020 Bytes

Versions: 10

Compression:

Stored size: 1020 Bytes

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