| 5907 | } |
| 5908 | |
| 5909 | function gallopLeft(value, array, start, length, hint, compare) { |
| 5910 | var lastOffset = 0; |
| 5911 | var maxOffset = 0; |
| 5912 | var offset = 1; |
| 5913 | |
| 5914 | if (compare(value, array[start + hint]) > 0) { |
| 5915 | maxOffset = length - hint; |
| 5916 | |
| 5917 | while (offset < maxOffset && compare(value, array[start + hint + offset]) > 0) { |
| 5918 | lastOffset = offset; |
| 5919 | offset = (offset << 1) + 1; |
| 5920 | |
| 5921 | if (offset <= 0) { |
| 5922 | offset = maxOffset; |
| 5923 | } |
| 5924 | } |
| 5925 | |
| 5926 | if (offset > maxOffset) { |
| 5927 | offset = maxOffset; |
| 5928 | } |
| 5929 | |
| 5930 | lastOffset += hint; |
| 5931 | offset += hint; |
| 5932 | } |
| 5933 | else { |
| 5934 | maxOffset = hint + 1; |
| 5935 | while (offset < maxOffset && compare(value, array[start + hint - offset]) <= 0) { |
| 5936 | lastOffset = offset; |
| 5937 | offset = (offset << 1) + 1; |
| 5938 | |
| 5939 | if (offset <= 0) { |
| 5940 | offset = maxOffset; |
| 5941 | } |
| 5942 | } |
| 5943 | if (offset > maxOffset) { |
| 5944 | offset = maxOffset; |
| 5945 | } |
| 5946 | |
| 5947 | var tmp = lastOffset; |
| 5948 | lastOffset = hint - offset; |
| 5949 | offset = hint - tmp; |
| 5950 | } |
| 5951 | |
| 5952 | lastOffset++; |
| 5953 | while (lastOffset < offset) { |
| 5954 | var m = lastOffset + (offset - lastOffset >>> 1); |
| 5955 | |
| 5956 | if (compare(value, array[start + m]) > 0) { |
| 5957 | lastOffset = m + 1; |
| 5958 | } |
| 5959 | else { |
| 5960 | offset = m; |
| 5961 | } |
| 5962 | } |
| 5963 | return offset; |
| 5964 | } |
| 5965 | |
| 5966 | function gallopRight(value, array, start, length, hint, compare) { |