Mailing-List: contact dev-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@couchdb.apache.org
Received-SPF: neutral (nike.apache.org: local policy)
From: Kosta Welke <kosta@fillibach.de>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Subject: CouchDB book: Ordering Lists
Date: Tue, 15 Dec 2009 11:11:52 +0100
Message-Id: <848E6B2B-7F98-4E30-97B1-607A38BFF3A0@fillibach.de>
To: dev@couchdb.apache.org
Mime-Version: 1.0 (Apple Message framework v1077)

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 =3D=3D 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).=20

Cheers,
Kosta=