searchRange returns alreadyPresent to indicate if the key is already in one of our interval16s. If key is alreadyPresent, then whichInterval16 tells you where. If key is not already present, then whichInterval16 is set as follows: a) whichInterval16 == len(rc.iv)-1 if key is beyond our last
(key int, startIndex int, endxIndex int)
| 835 | // The search space is from startIndex to endxIndex. If endxIndex is set to zero, then there |
| 836 | // no upper bound. |
| 837 | func (rc *runContainer16) searchRange(key int, startIndex int, endxIndex int) (whichInterval16 int, alreadyPresent bool, numCompares int) { |
| 838 | n := len(rc.iv) |
| 839 | if n == 0 { |
| 840 | return -1, false, 0 |
| 841 | } |
| 842 | if endxIndex == 0 { |
| 843 | endxIndex = n |
| 844 | } |
| 845 | |
| 846 | // sort.Search returns the smallest index i |
| 847 | // in [0, n) at which f(i) is true, assuming that on the range [0, n), |
| 848 | // f(i) == true implies f(i+1) == true. |
| 849 | // If there is no such index, Search returns n. |
| 850 | |
| 851 | // For correctness, this began as verbatim snippet from |
| 852 | // sort.Search in the Go standard lib. |
| 853 | // We inline our comparison function for speed, and |
| 854 | // annotate with numCompares |
| 855 | // to observe and test that extra bounds are utilized. |
| 856 | i, j := startIndex, endxIndex |
| 857 | for i < j { |
| 858 | h := i + (j-i)/2 // avoid overflow when computing h as the bisector |
| 859 | // i <= h < j |
| 860 | numCompares++ |
| 861 | if !(key < int(rc.iv[h].start)) { |
| 862 | i = h + 1 |
| 863 | } else { |
| 864 | j = h |
| 865 | } |
| 866 | } |
| 867 | below := i |
| 868 | // end std lib snippet. |
| 869 | |
| 870 | // The above is a simple in-lining and annotation of: |
| 871 | /* below := sort.Search(n, |
| 872 | func(i int) bool { |
| 873 | return key < rc.iv[i].start |
| 874 | }) |
| 875 | */ |
| 876 | whichInterval16 = below - 1 |
| 877 | |
| 878 | if below == n { |
| 879 | // all falses => key is >= start of all interval16s |
| 880 | // ... so does it belong to the last interval16? |
| 881 | if key < int(rc.iv[n-1].last())+1 { |
| 882 | // yes, it belongs to the last interval16 |
| 883 | alreadyPresent = true |
| 884 | return |
| 885 | } |
| 886 | // no, it is beyond the last interval16. |
| 887 | // leave alreadyPreset = false |
| 888 | return |
| 889 | } |
| 890 | |
| 891 | // INVAR: key is below rc.iv[below] |
| 892 | if below == 0 { |
| 893 | // key is before the first first interval16. |
| 894 | // leave alreadyPresent = false |
no test coverage detected