Rookie question about data types (hashtables)

[Anton Vredegoor]

Rainer Deyke" <rainerd at eldwood.com> wrote:

>>     What I would LIKE to have is a hashtable-like structure that lets
>> me retrieve multiple values based on a partial key.

>Sounds like a sorted list would work best.  A binary search (see the bisect
>module) lets find all matches in O(log n) time.

Probably yes. I'm replying just in case someone would like to have
their hash values sorted in alphabetical order too. The code below
might be of interest to hobbyist programmers who don't care about
practical issues :-) (also not tested beyond what you see)

Anton

from string import ascii_lowercase as alc

def antonian_sorted_unrank(k,base,ndig):
    res = []
    while k > -1 :
        r,k = divmod(k,int('1'*ndig,base))
        k,ndig = k-1,ndig-1
        res.append(r)
    return res

def antonian_sorted_rank(seq, base,ndig):
    res = 0
    for x in seq:
        res = x*int('1'*ndig,base)+res+1
        ndig -= 1
    return res-1

def word_rank(word,ndig):
    d = [alc.index(c) for c in word]
    return antonian_sorted_rank(d,len(alc),ndig)

def word_unrank(i,ndig):
    L = antonian_sorted_unrank(i,len(alc),ndig)
    return "".join([alc[j] for j in L])

def test():
    L = ["a","ab","aa","b","bab","ba"]
    maxlen = max(map(len,L))
    print L
    def wu(i): return word_unrank(i,maxlen)
    def wr(w): return word_rank(w,maxlen)
    H = map(wr,L)
    print H
    H.sort()
    print H
    R = map(wu,H)
    print R
    L.sort()
    assert L == R
    
if __name__=='__main__':
    test()