From 5856a2d2c0f611c95231c8ef84384a27394ffc0c Mon Sep 17 00:00:00 2001 From: pkoppstein Date: Sat, 3 Jan 2015 01:05:04 -0500 Subject: simplify implementation of bsearch to use "until" and avoid "last"; tested --- builtin.c | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) (limited to 'builtin.c') diff --git a/builtin.c b/builtin.c index 16f9e156..7201cf6d 100644 --- a/builtin.c +++ b/builtin.c @@ -1614,18 +1614,18 @@ static const char* const jq_builtins[] = { " else . as $in" "" // # state variable: [start, end, answer] "" // # where start and end are the upper and lower offsets to use. - " | last( [0, length-1, null]" - " | while( .[0] <= .[1] ;" - " (if .[2] != null then (.[1] = -1)" // # i.e. break - " else" - " ( ( (.[1] + .[0]) / 2 ) | floor ) as $mid" - " | $in[$mid] as $monkey" - " | if $monkey == target then (.[2] = $mid)" // # success - " elif .[0] == .[1] then (.[1] = -1)" // # failure - " elif $monkey < target then (.[0] = ($mid + 1))" - " else (.[1] = ($mid - 1))" - " end" - " end )))" + " | [0, length-1, null]" + " | until( .[0] > .[1] ;" + " if .[2] != null then (.[1] = -1)" // # i.e. break + " else" + " ( ( (.[1] + .[0]) / 2 ) | floor ) as $mid" + " | $in[$mid] as $monkey" + " | if $monkey == target then (.[2] = $mid)" // # success + " elif .[0] == .[1] then (.[1] = -1)" // # failure + " elif $monkey < target then (.[0] = ($mid + 1))" + " else (.[1] = ($mid - 1))" + " end" + " end )" " | if .[2] == null then" // # compute the insertion point " if $in[ .[0] ] < target then (-2 -.[0])" " else (-1 -.[0])" -- cgit v1.2.3