couchdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Kosta Welke <ko...@fillibach.de>
Subject CouchDB book: Ordering Lists
Date Tue, 15 Dec 2009 10:11:52 GMT
Hi all,

first of all, I'm not sure if this is the right list to post feedback on the book. I didn't
want to use the "comment" function, as my experience (on other pages) is that I'll never know
if anyone even read the comment.

On http://books.couchdb.org/relax/reference/recipes, "Ordering Lists":

You propose to use floats to sort lists, which can be rearranged or where an arbitrary amount
of items can be inserted between any two items.

What about solving the issue by sorting strings? Strings can be as long as they want without
any floating point precision getting in the way.

To insert in a list, insert in the middle of the existing 'boundaries'. For inserting items
at the beginning or end, the boundaries are "a".charCodeAt(0)-1 (which is "`") and "z".CharCodeAt(0)+1
(which is "{"). If you want, you can extend that to more printable characters or even unprintable
ones.

So, for the first item, the middle of the boundaries "`" and "{" is "m" (verify using String.fromCharCode(("`".charCodeAt(0)
+ "{".charCodeAt(0))/2)

{  "title":"Remember the Milk",
  "sort_order": "m" }

Now, we insert a second item afterwards between "m" and "{", which is "t":

{"title":"Call Fred",
 "sort_order": "t" }

An item between these two would have sort_order "p".

If we ever have the case of inserting between two consequtive characters, like "q" and "r"
(i.e. where (a+b)/2 == min(a,b)), we extend the sort_order of the new item by one character,
so it's "qm".

In general, when trying to find the middle between two strings, we find the first occurence
where the strings differ. If you can squeeze something in between, do it. If not, try to squeeze
in the middle between the next character of the first string and "{". If that's not possible,
try to squeeze in the middle between "`" and the next character of the second string. If that's
not possible, extend the first string by "m".

E.g. you want to insert between "qmbz" and "qmca". They share the prefix "qm", the first difference
is the third character, which is "b" and "c" respectively. We cant squeeze in something between
b and c, so we try to squeeze something between the next character "z" and "{", which is not
possible. We also cannot squeeze anything between the next character from the second string,
which is "a", and "`". So our best bet is to extend the first string by "m". The result is
"qmbzm".

If the first string would have been "qmby", the result would have been "qmbz". If the first
string would have been "qmbz" and the second "qmcb", the result would have been "qmca".

What do you think? It's a little more complicated than calculating the average of two floats,
but the complicatedness stems from fixing the issue of limited precision.

Of course, other ways of achieving something similar is to use an array of integers (best
would be int32 so that JavaScript can handle). 

Cheers,
Kosta
Mime
View raw message