1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#
# Just for testing.
#
require 'bsearch'
def prefix_imatch (key, pattern)
len = pattern.length
raise if key == nil
raise if pattern == nil
key[0, len].downcase <=> pattern[0, len].downcase
end
def lookup (dict, pattern)
first = dict.bsearch_first {|x| prefix_imatch x, pattern }
last = dict.bsearch_last {|x| prefix_imatch x, pattern }
range = dict.bsearch_range {|x| prefix_imatch x, pattern }
if first != nil then
raise "#{range.first} != #{first}" unless range.first == first
raise "#{range.last} != #{last}" unless range.last == last + 1
raise unless range == dict.bsearch_range(range) {|x|
prefix_imatch x, pattern }
raise unless range == dict.bsearch_range(first..last) {|x|
prefix_imatch x, pattern }
raise unless range == dict.bsearch_range(first...last + 1) {|x|
prefix_imatch x, pattern }
range.each {|i|
print i + 1, ":", dict[i], "\n"
}
end
end
def check_boundaries (dict)
return if dict.empty?
l = 0
u = dict.length - 1
raise unless (l...(l+1)) == dict.bsearch_range(l..l) {|x| x <=> dict.first}
raise unless (u...(u+1)) == dict.bsearch_range(u..u) {|x| x <=> dict.last}
raise unless (l...l) == dict.bsearch_range(l...l) {|x| x <=> dict.last}
raise unless (u...u) == dict.bsearch_range(u...u) {|x| x <=> dict.last}
end
pattern = ARGV.shift
dict = Array.new
while line = gets
line.chomp!
dict.push line
end
check_boundaries(dict)
lookup(dict, pattern)
|
