# Unique code search algorithm rewritten in almost pure ReQL

In my previous post regarding generating the unique codes out of the free codes.
That implementation was based on a JavaScript function that accepted a strategy to be invoked each time a binary search iteration is in progress.
I also mentioned that due this it will do *log n* queries to the RethinkDB database, and I assumpted that it can be fully ReQL based.
Yes, it can be executed fully on the RethinkDB side being re-implemented in pure ReQL.
Almost.
Let's see how.

Thanksfully, RethinkDB supports two basic functions like `range`

and `fold`

.
How could they help it?
Well, it's clear about `range`

: it just serves the purpose of making iterations.
What about `fold`

?
Using the `fold`

iteration it can share the state between the iterations generated from the `range`

above.

Let's see.

const findFreeValue = (min, max, hasFree) => r.branch( // if min/max difference is at least 1 (min is closed, max is open) ... r(max).sub(min).eq(1), // ... then report no values r.error('all values in use'), // ... else do search with maximum number of steps required for the binary search r.range(Math.ceil(Math.log2((max - min)))) .fold({l: min, r: max}, (a, _) => a.do(() => { // get the floored middle between l and r const m = a('r').sub(a('l')).div(2).floor().add(a('l')); return r.branch( // randomly get the "first" strategy r.random().lt(0.5), // use left-first then right-second r.branch( // if there's anything free between l and m, ... hasFree(a('l'), m), // ... then move the right to the middle r.do(() => a.merge({r: m})), // else if there's anything free between l and r, ... hasFree(m, a('r')), // ... then move the left to middle r.do(() => a.merge({l: m})), // ... otherwise nothing left r.error('all values in use') ), // otherwise use right-first then left-second r.branch( hasFree(m, a('r')), r.do(() => a.merge({l: m})), hasFree(a('l'), m), r.do(() => a.merge({r: m})), r.error('all values in use') ) ); }) ) // l always points to a free value .do(a => a('l')) );

Note that we must calculate the number of iterations before the execute the query, because we cannot break the loop implemented with `fold`

.
It would be awesome if `fold`

could do this.
Also, this why I said "almost" above regarding the algorithm fullness in ReQL: RethinDB does not support logarithms, so we're cheating there a bit.
Next, all the `fold`

operation is responsible for is sharing the state of two variables, `l`

and `r`

, between iterations.
Note that we can update the accumulator state on each iteration by applying the `merge`

operator.

Now, this is how it can be used after all:

findFreeValue(256, (codeL, codeR) => r.db('test') .table('codes') .between(codeL, codeR, { index: 'code' }) .count() .do(count => r(codeR).sub(codeL).gt(count)) );

I think it's pretty cool and saves the amount of queries suggested in the previous approach.
Sadly, this is the second time I need to break the `fold`

and have no ReQL operator to do it.