Class: BinarySearch::Search

Inherits:
Object
  • Object
show all
Defined in:
lib/binarysearch/search.rb

Constant Summary collapse

INDEX_SIZE =

TODO is there a sizeof(long) ?

4

Instance Method Summary collapse

Constructor Details

#initialize(db, db_idx = nil) ⇒ Search

Returns a new instance of Search.



8
9
10
11
12
13
14
 
# File 'lib/binarysearch/search.rb', line 8

def initialize(db, db_idx=nil)
  @db = File.open(db, 'r')
  db_idx = db + '.idx' if db_idx.nil?
  @db_idx = File.open(db_idx, 'r')
  @db_size = File.stat(db_idx).size / INDEX_SIZE
  @db_pos = 0
end

Instance Method Details

#close ⇒ Object 



16
17
18
19
20
 
# File 'lib/binarysearch/search.rb', line 16

def close
  @db.close
  @db_idx.close
  @db = @db_idx = nil
end

#eq(a, b) ⇒ Object 



70
71
72
 
# File 'lib/binarysearch/search.rb', line 70

def eq(a, b)
  raise 'you must implemented this method!'
end

#gt(a, b) ⇒ Object 



62
63
64
 
# File 'lib/binarysearch/search.rb', line 62

def gt(a, b)
  raise 'you must implemented this method!'
end

#lt(a, b) ⇒ Object 



66
67
68
 
# File 'lib/binarysearch/search.rb', line 66

def lt(a, b)
  not gt(a, b) and not eq(a, b)
end

#parse(what) ⇒ Object 



58
59
60
 
# File 'lib/binarysearch/search.rb', line 58

def parse(what)
  raise 'you must implemented this method!'
end

#read(offset) ⇒ Object 



51
52
53
54
55
56
 
# File 'lib/binarysearch/search.rb', line 51

def read(offset)
  @db_idx.seek(offset * INDEX_SIZE)
  pos = @db_idx.readbytes(INDEX_SIZE).unpack('L')[0]
  @db.seek(pos)
  parse(@db.gets)
end

#search(record) ⇒ Object 



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
 
# File 'lib/binarysearch/search.rb', line 22

def search(record)
  from = 0
  to = @db_size - 1

  pivot = nil
  while from < to
    middle = (from + to) / 2

    pivot = read(middle)

    if lt(record, pivot)
      to = middle
      next
    elsif gt(record, pivot)
      from = middle + 1
      next
    end

    result = nil
    result = pivot if eq(record, pivot)
    return result
  end

  if from == to
    pivot = read(from)
    return pivot if eq(pivot, pivot)
  end
end