[BitTorrent] Re: Bencoding: How to sort keys for dictionaries ?

skybuckflying skybuck2000 at hotmail.com
Sun Nov 21 02:24:50 EST 2004



--- In BitTorrent at yahoogroups.com, Brian Dessent <brian at d...> wrote:
> skybuckflying wrote:
> 
> > "Keys must be strings and appear in sorted order (sorted as raw
> > strings, not alphanumerics)."
> 
> It means they're sorted in lexicographical order.  This is a 
frequently
> asked question so search the mailing list archives.

I did that turned up nothing ;)

I did however find this link:

http://www.javaranch.com/maha/Discussions/java_lang_Package/s_compareT
o___-_JavaRanch_Big_Moose_Saloon.htm

So I think a typical sorting algorithm (which uses compares) will 
sort it just fine with a typical string compare function.

Though I am not 100% sure since this document does mention 
a "difference"

So I see two possibilities... 

Possibility 1: "sorting based on the differences"

or

Possibility 2: the string compare function simply returns
-1 Less
0 Equal
1 Greater

And then all the strings are simply sorted like that... 

Yeah possibility 1 probably doesn't make much sense since it would 
give different values depending on which elements are compared...

Anyway my question about why it is needed remains ;)

> 
> > Also why do keys have to be strings.. is that really necessary..
> > (since my implementation can easily handle other stuff as well...
> > though I haven't tried yet for searching for keys :) I might
> > need/make an Equals or so... function for that :) )
> 
> The whole concept a dictionary is to associate key and value pairs. 
> That traditionally means string (scalar) values.  I don't see what 
the
> objection is, the only other thing I can think of that would make 
sense
> as a key value is an integer which can be represented just fine as a
> string.  And yes it is a good idea to require key values to be 
strings
> for consistency.

Well currently my implementation can store both the decoded and 
encoded value.

So in the near future I might make the following search functions for 
the dictionary.

function TBcodedDictionary.FindDecodedKey( BCodedElement : 
TBCodedElement; var KeyIndex : integer ) : boolean;

function TBcodedDictionary.FindEncodedKey( BCodedElement : 
TBCodedElement; var KeyIndex : integer ) : boolean;

BCodedElement is an object which contains
  EncodedString
  DecodedString

So currently I can search for whatever I want.

This would be quite powerfull so why give up this "power" ;)

Well ofcourse the thing could do type checking etc...

So if I would follow the spec really tightly then it would be:

function TBcodedDictionary.FindDecodedKey( BCodedString : 
TBCodedString; var KeyIndex : integer ) : boolean;

function TBcodedDictionary.FindEncodedKey( BCodedString : 
TBCodedString );

But suppose for some wacky reason that in the future the spec is 
changed and BCodedIntegers are now allowed as well then that would 
not be a problem since then I can just use the original/general 
methods as described at the top.

But then why not use it in the first place :) Then it would be the 
user who has to take care ;) and make sure everything for a key is a 
BcodedString ;)

And maybe the general case would be more robust as well... what if 
some other client decides to send a BcodedInteger as a key for the 
dictionary.

My code will simply store it in the dictionary without a problem.

And it could even be found without a problem.

I shooting for general stuff and robust stuff ;)

Bye,
  Skybuck





------------------------ Yahoo! Groups Sponsor --------------------~--> 
$9.95 domain names from Yahoo!. Register anything.
http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 





More information about the BitTorrent mailing list