strorder.py

"""This module generates strings to be used to define an order when sorted as
strings. We call those strings 'keys'. All keys are composed of printable ascii
chars. (The alphabet is actually defined in key_chars.) It is ensured, that you
can always create a 'smaller' or 'larger' key than any key generated by the
functions in this module. Additionally, you can always generate a key, which is
in between two given keys.

Cconventience functions to define insert and append methods in an sqlalchemy
orm class are provided too."""

import random
# Note that we use some randomization to get good performance not only when
# generating middle_keys but also when generating before_keys and after_keys
# frequently. The randomization is fairly "auto-adjusting" by depending on the
# key length.

key_chars = "".join(chr(i) for i in range(33,127))
middle_char = key_chars[len(key_chars)//2]
key_char_index = dict((c, i) for i, c in enumerate(key_chars))



def init_key():
    """Returns an initial order key to be used for the first item."""
    return middle_char


def before_key(key):
    """Returns an order key which is before the passed key."""
    new_key = []
    for i, c in enumerate(key):
        if c is not key_chars[0] and (i == len(key)-1 or not random.randint(0, len(key))):
            new_key.append(key_chars[key_char_index[c]-1])
            if i == len(key)-1:
                new_key.append(middle_char)
            break
        else:
            new_key.append(c)
    else:
        raise RuntimeError("could not insert a key before '%s'" % key)
    new_key = "".join(new_key)
    assert new_key < key
    return new_key


def after_key(key):
    """Returns an order key which is after the passed key."""
    new_key = []
    for c in key:
        if c is not key_chars[-1] and not random.randint(0, len(key)):
            new_key.append(key_chars[key_char_index[c]+1])
            break
        else:
            new_key.append(c)
    else:
        new_key.append(middle_char)
    new_key = "".join(new_key)
    assert key < new_key
    return new_key


def middle_key(key1, key2):
    """Returns an order key which is between the two passed keys. The two keys
    passed to this function must be ordered."""
    assert key1 < key2
    new_key = []
    for i, (c1, c2) in enumerate(zip(key1, key2)):
        if c1 == c2:
            new_key.append(c1)
        elif key_char_index[c1]+1 == key_char_index[c2]:
            new_key.append(c1)
            new_key.extend(after_key(key1[i+1:])) # note that after_key doesn't fail for an empty key
            break
        else:
            new_key.append(key_chars[(key_char_index[c1] + key_char_index[c2])//2])
            break
    else:
        if len(key1) > len(key2):
            new_key.extend(after_key(key1[len(key2):]))
        elif len(key2) > len(key1):
            new_key.extend(before_key(key2[len(key1):]))
        else:
            raise RuntimeError("identical keys?!")
    new_key = "".join(new_key)
    assert key1 < new_key < key2
    return new_key


def insert(list, pos, item):
    """A convenience function to define an insert method on an orm class having
    a list of items.

    To define an insert_item method on the list, do:
        def insert_item(self, pos, item):
            insert(self, pos, item)

    We need to access two column names: the first is the name of the order key
    of the item instance. It is constructed from the class name of the list by
    '%s_order' % list.__class__.__name__.lower(). The second name is the name
    of the 1:N relation in the list instance. It is constructed from the class
    name of the item by '%ss' % item.__class__.__name__.lower(). As we want a
    clean design, these naming rules are enforced here by not being
    overwriteable. This results in strict naming conventions for the relations
    and the class names."""
    list_order_name = "%s_order" % list.__class__.__name__.lower()
    items_name = '%ss' % item.__class__.__name__.lower()
    items = getattr(list, items_name)
    if items:
        if pos == 0:
            setattr(item, list_order_name, before_key(getattr(items[0], list_order_name)))
        elif pos == len(items):
            setattr(item, list_order_name, after_key(getattr(items[-1], list_order_name)))
        else:
            setattr(item, list_order_name, middle_key(getattr(items[pos-1], list_order_name),
                                                      getattr(items[pos], list_order_name)))
    else:
        setattr(item, list_order_name, init_key())
    items.insert(pos, item)


def append(list, item):
    """A convenience function to define an append method on an orm class having
    a list of items. See the detailed info in the insert function above about
    for a use case."""
    list_order_name = "%s_order" % list.__class__.__name__.lower()
    items_name = '%ss' % item.__class__.__name__.lower()
    items = getattr(list, items_name)
    if items:
        setattr(item, list_order_name, after_key(getattr(items[-1], list_order_name)))
    else:
        setattr(item, list_order_name, init_key())
    items.append(item)


if __name__ == "__main__":
    l = [init_key()]
    for i in range(10000):
        p = random.randint(0, len(l))
        if p == 0:
            l.insert(0, before_key(l[0]))
        elif p == len(l):
            l.append(after_key(l[-1]))
        else:
            l.insert(p, middle_key(l[p-1], l[p]))
    assert l == sorted(l)