class Array
Public Instance Methods
bin_search(elem, low = 0, high = -1)
click to toggle source
Binary search for the first elem that is leq elem in this array in the range (low..high-1)
The array is expected to be sorted in descending order.
@param [Object] elem elem to search for @param [Fixnum] low lower bound (inclusive) @param [Fixnum] high upper bound (inclusive, -1 for last element) @return [Fixnum] index of first occurence leq than elem in self, or -1 if not found
# File lib/andromeda/patch/array_bin_search.rb, line 35 def bin_search(elem, low = 0, high = -1) high = size - 1 if high < 0 _bin_search elem, low, high end
tag!() { |e), e| ... }
click to toggle source
Wraps all objects in self into ::Array::Tag
instances using the provided block to extract a key
@return [self]
# File lib/andromeda/patch/array_bin_search.rb, line 45 def tag! ; map! { |e| Tag.new (yield e), e } end
untag!()
click to toggle source
Untags Array::Tag
instances, i.e. replaces them with their value
@return [self]
# File lib/andromeda/patch/array_bin_search.rb, line 51 def untag! ; map! { |e| e.untagged } end
Private Instance Methods
_bin_search(elem, low, high)
click to toggle source
# File lib/andromeda/patch/array_bin_search.rb, line 55 def _bin_search(elem, low, high) last = -1 while low <= high sz = high - low # On 2012 cpus, linear search is slightly faster than binary search # if the number of searched elements is in the range of 50-100 elts return _lin_search elem, low, high if (sz >> 6) mid_index = low + (sz >> 1) if (elem <=> self[mid_index]) == -1 low = mid_index + 1 else last = mid_index high = mid_index - 1 end end return last end
_lin_search(elem, low, high)
click to toggle source
# File lib/andromeda/patch/array_bin_search.rb, line 73 def _lin_search(elem, low, high) cur_index = low while cur_index <= high if (elem <=> self[cur_index]) == -1 then cur_index += 1 else return cur_index end end return -1 end