Module: IPAddrList::Algorithm::BinarySearch

Includes:
Lint
Defined in:
lib/ipaddr_list.rb

Overview

searching ipaddress with binary search.

Instance Method Summary collapse

Instance Method Details

#add(ip) ⇒ Object 



115
116
117
118
119
120
121
 
# File 'lib/ipaddr_list.rb', line 115

def add ip
  unless ip.kind_of? IPAddr
    ip = IPAddr.new(ip.to_s)
  end
  @ip_list.push(ip)
  @ip_list = @ip_list.sort
end

#after_init(ip_list = []) ⇒ Object 



105
106
107
108
109
110
111
112
113
 
# File 'lib/ipaddr_list.rb', line 105

def after_init ip_list=[]
  @ip_list = ip_list.map {|item|
    if item.kind_of? IPAddr
      item
    else
      IPAddr.new(item.to_s)
    end
  }.sort
end

#binary_search(ip, &block) ⇒ Object

binary search SEE ALSO: dsas.blog.klab.org/archives/51293334.html



136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/ipaddr_list.rb', line 136

def binary_search ip, &block
  ipaddr = nil
  if ip.kind_of? IPAddr
    ipaddr = ip
  else
    ipaddr = IPAddr.new(ip)
  end
  min_idx = 0
  max_idx = @ip_list.size - 1
  if @ip_list[max_idx] < ipaddr
    min_idx = max_idx
  elsif @ip_list[min_idx] > ipaddr
    max_idx = min_idx
  else
    span = max_idx - min_idx
    while ( ( span ) > 7 ) do
      middle_idx = span / 2 + min_idx
      middle_ip = @ip_list[ middle_idx ]
      if ipaddr >= middle_ip
        min_idx = middle_idx
      else
        max_idx = middle_idx
      end

      span = max_idx - min_idx
    end
  end

  block.call(ipaddr, min_idx..max_idx)
end

#each(&block) ⇒ Object 



123
124
125
126
 
# File 'lib/ipaddr_list.rb', line 123

def each &block
  @ip_list.each(&block)
  self
end

#include?(ip) ⇒ Boolean

Returns:

  • (Boolean) 


128
129
130
131
132
 
# File 'lib/ipaddr_list.rb', line 128

def include? ip
  binary_search ip do |ipaddr, range|
    range.any? {|idx| @ip_list[idx].include? ipaddr }
  end
end