gavo.utils.algotricks module

Some fundamental algorithms not found in the standard library.

class gavo.utils.algotricks.DeferringDict

Bases: dict

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 interface classes in the registry code,, since they usually need the entire system up before they can sensibly be built.

You can assign either a single function or a tuple of a callable and its positional and keyword arguments to each key.

iteritems() → Iterator[Tuple[str, Any]]

class gavo.utils.algotricks.IndexedGraph(edges: List[Tuple[IgNode, IgNode]])

Bases: Generic[IgNode]

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: IgNode, goTo: IgNode) → None

getEdge() → Tuple[IgNode, IgNode]

returns a random edge.

It raises an IndexError if the graph is empty.

getSomeRootNode() → IgNode

returns an arbitrary element of rootNodes.

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

removeEdge(comeFrom: IgNode, goTo: IgNode) → None

gavo.utils.algotricks.chunk(items: ~typing.List[~gavo.utils.algotricks.T], getChunkTitle: ~typing.Callable[[~gavo.utils.algotricks.T], str], getKey: ~typing.Callable = <function <lambda>>) → List[Tuple[str, List[T]]]

returns items in a chunked form.

getChunkTitle(item)->chunk title is a function returning the chunk title, getKey(chunk)->sort key a function returning a sort key for the chunks (default is just the chunk title, 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: Sequence[T], t2: Sequence[T]) → int

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

gavo.utils.algotricks.identity(val: T) → T

gavo.utils.algotricks.pathSort(paths: Sequence[str]) → List[str]

returns paths sorted in a way that parents are in front of their children. Missing parents are inserted.

>>> pathSort(["a/b/c"])
['a', 'a/b', 'a/b/c']

>>> pathSort(["/a/b/c", "/x/y", "/a/b/x", "/a/c"])
['', '/a', '/a/b', '/a/b/c', '/a/b/x', '/a/c', '/x', '/x/y']

gavo.utils.algotricks.topoSort(edges: List[Tuple[IgNode, IgNode]]) → List[IgNode]

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: Sequence[Hashable]) → List[Hashable]

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).