gavo.utils.algotricks module

Some fundamental algorithms not found in the standard library.

class gavo.utils.algotricks.DeferringDict

Bases: dict

is a dictionary that stores tuples of a callable and its arguments and will, on the first access, do the calls.

This is used below to defer the construction of instances in the class resolver to when they are actually used. This is important with interfaces, since they usually need the entire system up before they can sensibly be built.

iteritems()

class gavo.utils.algotricks.IndexedGraph(edges)

Bases: object

is a graph that is indexed by both incoming and outgoing edges.

The constructor argument edges is an iterable of (from, to)-tuples, where both from and to must be hashable.

The class keeps a set rootNodes of “root nodes” (i.e. those with no incoming edges).

To find leaf nodes, you’d have to compute allNodes-set(outgoingIndex).

You may access allNodes, rootNodes, incomingIndex, and outgoingIndex reading, but any external change to them will wreak havoc.

addEdge(comeFrom, goTo)

getEdge()

returns a random edge.

It raises an IndexError if the graph is empty.

getSomeRootNode()

returns an arbitrary element of rootNodes.

This will raise a KeyError if no root nodes are left.

removeEdge(comeFrom, goTo)

gavo.utils.algotricks.chunk(items, getChunkKey, getKeyKey=<function <lambda>>)

returns items in a chunked form.

getChunkKey(item)->chunk key is a function returning the chunk title, getKeyKey(chunk)->sort key a function returning a sort key for the chunks (default is just the chunk key, i.e., chunk[0]

The chunked form is a sequence of pairs of a chunk key and a sequence of items belonging to that chunk.

The internal order within each chunk is not disturbed, so you should sort items as desired before passing things in.

This is supposed to work like this:

>>> chunk(["abakus", "Analysis", "knopf", "Kasper", "kohl"],
...   lambda item: item[0].lower())
[('a', ['abakus', 'Analysis']), ('k', ['knopf', 'Kasper', 'kohl'])]

gavo.utils.algotricks.commonPrefixLength(t1, t2)

returns the length of the common prefix of the sequences t1, t2.

gavo.utils.algotricks.identity(val)

gavo.utils.algotricks.topoSort(edges)

returns a list with the nodes in the graph edges sorted topologically.

edges is a sequence of (from, to)-tuples, where both from and to must be hashable.

A ValueError is raised if the graph is not acyclic.

gavo.utils.algotricks.uniqueItems(seq)

returns a list of the unique items in seq as they appear in seq.

Execept for order and return type, this is essentially like set(seq).