Hi,
just for the records: I've came up myself with an alternative solution
to store
an ordered list. The basic idea is to calculate order keys from a set
of
characters such that I can always insert items in front of the list
and at the
end of the list and also between any two items. I never need to change
any
existing ordering key. You only need the keys for the two neighbors
(or just
the first or last key in the list when inserting at the beginning or
end). The key
creation is fairly efficient to tasks like always inserting items at
the end of
the list or at the beginning of the list or for example always at the
second
position in the list. A random insertion is fine too. The efficiency
in all
those very different situations is based on some randomness in the new
key
creation processes, but this is the whole interesting thing here.
André
-------- order_key.py ----- (the beef) ----------------
# -*- encoding: utf-8 -*-
# The MIT License
#
# Copyright (c) 2009 André Wobst <wob...@users.sourceforge.net>
#
# Permission is hereby granted, free of charge, to any person
obtaining a copy
# of this software and associated documentation files (the
"Software"), to deal
# in the Software without restriction, including without limitation
the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or
sell
# copies of the Software, and to permit persons to whom the Software
is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN
# THE SOFTWARE.
"""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."""
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
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)
-------- order_key.py ----- (example) ----------------
# -*- encoding: utf-8 -*-
import random
from sqlalchemy import create_engine, MetaData, Table, Column,
Integer, String, Unicode, ForeignKey, UniqueConstraint
from sqlalchemy.orm import sessionmaker, mapper, relation
import order_key
metadata = MetaData()
list_table = Table("list", metadata,
Column("id", Integer, primary_key=True),
Column("name", Unicode))
item_table = Table("item", metadata,
Column("id", Integer, primary_key=True),
Column("name", Unicode),
Column("list_order", String, nullable=False),
Column("list_id", Integer, ForeignKey("list.id"),
nullable=False),
UniqueConstraint("list_id", "list_order"))
class List(object):
def __init__(self, name):
self.name = name
def __repr__(self):
return "<List %s>" % self.name
def insert_item(self, pos, item):
if self.items:
if p == 0:
item.list_order = order_key.before_key(l.items
[0].list_order)
elif p == len(l.items):
item.list_order = order_key.after_key(l.items
[-1].list_order)
else:
item.list_order = order_key.middle_key(l.items
[p-1].list_order, l.items[p].list_order)
else:
item.list_order = order_key.init_key()
self.items.insert(pos, item)
class Item(object):
def __init__(self, name):
self.name = name
def __repr__(self):
return "<Item %s part of %s>" % (self.name, self.list)
mapper(List, list_table,
properties={"items": relation(Item,
backref="list",
order_by=
[item_table.c.list_order])})
mapper(Item, item_table)
engine = create_engine("postgres:///list")
metadata.bind = engine
list_table.create()
item_table.create()
l = List(u"list")
for i in range(1000):
p = random.randint(0, len(l.items))
i = Item(u"%05i" % i)
l.insert_item(p, i)
Session = sessionmaker(engine)
session = Session()
session.add(l)
session.commit()
session.close()
engine.dispose()
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sqlalchemy" group.
To post to this group, send email to sqlalchemy@googlegroups.com
To unsubscribe from this group, send email to
sqlalchemy+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sqlalchemy?hl=en
-~----------~----~----~----~------~----~------~--~---
