Betwixt
implements three operations on (a subset of) JavaScript strings:
Betwixt.before(s)
returns a string less thans
Betwixt.after(s)
returns a string greater thans
Betwixt.between(s,t)
returns- a string greater than
s
and less thant
ifs < t
, - a string greater than
t
and less thans
ift < s
, and s
ifs
andt
are equal.
- a string greater than
(We say a subset of JavaScript strings because Betwixt strings are nonempty
and have no trailing null (\u0000
) characters.)
The use case is this: suppose we have a reorderable list — an ordered list where the order can be manually changed by the user. Furthermore, each list item is an independent database record. We want to be able to change the position of an item by changing its order field, without changing any other records in the database (as well as to add an item to the beginning or end of the list, or between any two items in the list).
If we could order the list using real numbers we could do this easily. For
instance, suppose the list is sorted by a field called order
, and there are
two records a
and z
with a.order < z.order
. If we have a fresh record
call new
, we can put it at the start of the list by setting new.order = a.order-1
. We can put it at the end of the list by setting new.order = z.order+1
. And we can put it between a
and z
by setting new.order = (a.order+z.order)/2
. If we have a list with elements a
, b
, and c
in that
order, we can move c
between a
and b
by changing c.order
to
(a.order+b.order)/2
.
Unfortunately, we can't get our hands on actual real numbers, and JavaScript's
Number type (IEEE 64-bit floating point) can run out of precision relatively
quickly: Suppose a.order
is 1 and b.order
is 2, and we insert new1
between a
and z
, new2
between a
and new1
, new3
between a
and
new2
, and so forth, using the method of averaging given above. By the time we
get to new53
, floating point precision limitations will cause new53.order
to be 1 — the same as a.order
. We'll no longer be able to guarantee that our
list is ordered as the user wishes.
But we don't need actual real numbers -- we need what mathematicians call a
dense linear order (without endpoints). Betwixt
implements that — see the
annotated CoffeeScript source for information
about how it's done. The specs may also be
informative.
Betwixt.trim(s)
returnss
with trailing null characters removedBetwixt.validated(s)
is likeBetwixt.trim(s)
, but throws an error if the result would be the empty stringBetwixt.toHex(s)
returns a hexadecimal representation ofs
.Betwixt.midpoint()
returns a string that's a good initial value for the rank of the item in a one-item list — representations of the values above and below the midpoint are equally space-efficient.
One caveat: using Betwixt strings, we can do almost unlimited numbers of the
insertions described above; but if we do, say a million of them, then the
new1000000.order
string will be something like 125,000 bytes long. Things
will probably not be that bad in practice, since changes and insertions are
likely to be more random in real-world applications. And Betwixt tries to
minimize string explosion where it can. In particular, the before and after
methods optimize the common cases where an item is inserted at the beginning or
end of a list.
Dominic Tarr's between npm module is very similar to Betwixt, though less space-efficient.