Module: Bisect

Defined in:
lib/include/bisect.rb

Class Method Summary collapse

Class Method Details

.bisect_left(list, item, lo = 0, hi = list.size) ⇒ Object 



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
 
# File 'lib/include/bisect.rb', line 4

def bisect_left(list, item, lo = 0, hi = list.size)
	if block_given?
		while lo < hi
			i = (lo + hi - 1) >> 1

			if 0 <= yield(list[i], item)
				hi = i
			else
				lo = i + 1
			end
		end
	else
		while lo < hi
			i = (lo + hi - 1) >> 1

			if 0 <= (list[i] <=> item)
				hi = i
			else
				lo = i + 1
			end
		end
	end

	return hi
end

.bisect_right(list, item, lo = 0, hi = list.size) ⇒ Object 



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
 
# File 'lib/include/bisect.rb', line 30

def bisect_right(list, item, lo = 0, hi = list.size)
	if block_given?
		while lo < hi
			i = (lo + hi - 1) >> 1

			if 0 < yield(list[i], item)
				hi = i
			else
				lo = i + 1
			end
		end
	else
		while lo < hi
			i = (lo + hi - 1) >> 1

			if 0 < (list[i] <=> item)
				hi = i
			else
				lo = i + 1
			end
		end
	end

	return lo
end

.find_ge(list, item, &block) ⇒ Object

Find leftmost item greater than or equal to item



91
92
93
94
 
# File 'lib/include/bisect.rb', line 91

def find_ge(list, item, &block)
	i = bisect_left(list, item, &block)
	return list[i] unless list.size == i
end

.find_gt(list, item, &block) ⇒ Object

Find leftmost value greater than item



85
86
87
88
 
# File 'lib/include/bisect.rb', line 85

def find_gt(list, item, &block)
	i = bisect_right(list, item, &block)
	return list[i] unless list.size == i
end

.find_le(list, item, &block) ⇒ Object

Find rightmost value less than or equal to item



79
80
81
82
 
# File 'lib/include/bisect.rb', line 79

def find_le(list, item, &block)
	i = bisect_right(list, item, &block)
	return list[i - 1] unless 0 == i
end

.find_lt(list, item, &block) ⇒ Object

Find rightmost value less than item



73
74
75
76
 
# File 'lib/include/bisect.rb', line 73

def find_lt(list, item, &block)
	i = bisect_left(list, item, &block)
	return list[i - 1] unless 0 == i
end

.index(list, item, &block) ⇒ Object

Locate the leftmost value exactly equal to item



67
68
69
70
 
# File 'lib/include/bisect.rb', line 67

def index(list, item, &block)
	i = bisect_left(list, item, &block)
	return list[i] == item ? i : nil
end

.insert_left(list, item, lo = 0, hi = list.size, &block) ⇒ Object 



56
57
58
59
 
# File 'lib/include/bisect.rb', line 56

def insert_left(list, item, lo = 0, hi = list.size, &block)
	i = bisect_left(list, item, lo, hi, &block)
	list.insert(i, item)
end

.insert_right(list, item, lo = 0, hi = list.size, &block) ⇒ Object 



61
62
63
64
 
# File 'lib/include/bisect.rb', line 61

def insert_right(list, item, lo = 0, hi = list.size, &block)
	i = bisect_right(list, item, lo, hi, &block)
	list.insert(i, item)
end