ganeti.utils.algo

module documentation

Utility functions with algorithms.

Class	`RunningTimeout`	Class to calculate remaining timeout when doing several operations.
Function	`FindDuplicates`	Identifies duplicates in a list.
Function	`FlatToDict`	Converts a flat structure to a fully fledged dict.
Function	`GetRepeatedKeys`	Return the set of keys defined multiple times in the given dicts.
Function	`InsertAtPos`	Inserts `other` at given `pos` into `src`.
Function	`InvertDict`	Inverts the key/value mapping of a dict.
Function	`JoinDisjointDicts`	Joins dictionaries with no conflicting keys.
Function	`NiceSort`	Sort a list of strings based on digit and non-digit groupings.
Function	`NiceSortKey`	Extract key for sorting.
Function	`SequenceToDict`	Converts a sequence to a dictionary with duplicate detection.
Function	`UniqueSequence`	Returns a list with unique elements.
Class	`_NiceSortAtom`	Helper class providing rich comparison between different types
Function	`_MakeFlatToDict`	Helper function for `FlatToDict`.
Function	`_NiceSortGetKey`	Get a suitable sort key.
Constant	`_SORTER_GROUPS`	Undocumented
Constant	`_SORTER_RE`	Undocumented

def FindDuplicates(seq): ¶

Identifies duplicates in a list.

Does not preserve element order.

Parameters
seq:sequence	Sequence with source elements
Returns
list	List of duplicate elements from seq

def FlatToDict(data, field_sep='/'): ¶

Converts a flat structure to a fully fledged dict.

It accept a list of tuples in the form:

  [
    ("foo/bar", {"key1": "data1", "key2": "data2"}),
    ("foo/baz", {"key3" :"data3" }),
  ]

where the first element is the key separated by field_sep.

This would then return:

  {
    "foo": {
      "bar": {"key1": "data1", "key2": "data2"},
      "baz": {"key3" :"data3" },
      },
  }

Parameters
data:list of tuple	Input list to convert
field_sep:str	The separator for the first field of the tuple
Returns
A dict based on the input list

def GetRepeatedKeys(*dicts): ¶

Return the set of keys defined multiple times in the given dicts.

>>> GetRepeatedKeys({"foo": 1, "bar": 2},
...                 {"foo": 5, "baz": 7}
...                )
set("foo")

Parameters
*dicts:dict	The dictionaries to check for duplicate keys.
Returns
set	Keys used more than once across all dicts

def InsertAtPos(src, pos, other): ¶

Inserts other at given pos into src.

Parameters
src:list	The source list in which we want insert elements
pos:int	The position where we want to start insert `other`
other:list	The other list to insert into `src`
Returns
A copy of `src` with `other` inserted at `pos`
Note
This function does not modify `src` in place but returns a new copy

def InvertDict(dict_in): ¶

Inverts the key/value mapping of a dict.

Parameters
dict_in	The dict to invert
Returns
the inverted dict

def JoinDisjointDicts(dict_a, dict_b): ¶

Joins dictionaries with no conflicting keys.

Enforces the constraint that the two key sets must be disjoint, and then merges the two dictionaries in a new dictionary that is returned to the caller.

Parameters
dict_a:dict	the first dictionary
dict_b:dict	the second dictionary
Returns
dict	a new dictionary containing all the key/value pairs contained in the two dictionaries.

def NiceSort(values, key=None): ¶

Sort a list of strings based on digit and non-digit groupings.

Given a list of names ['a1', 'a10', 'a11', 'a2'] this function will sort the list in the logical order ['a1', 'a2', 'a10', 'a11'].

The sort algorithm breaks each name in groups of either only-digits or no-digits. Only the first eight such groups are considered, and after that we just use what's left of the string.

Parameters
values:list	the names to be sorted
key:callable or None	function of one argument to extract a comparison key from each list element, must return string
Returns
list	a copy of the name list sorted with our algorithm

def NiceSortKey(value): ¶

Extract key for sorting.

def SequenceToDict(seq, key=compat.fst): ¶

Converts a sequence to a dictionary with duplicate detection.

Parameters
seq:sequen	Input sequence
key:callable	Function for retrieving dictionary key from sequence element
Returns
dict	Undocumented

def UniqueSequence(seq): ¶

Returns a list with unique elements.

Element order is preserved.

Parameters
seq:sequence	the sequence with the source elements
Returns
list	list of unique elements from seq

def _MakeFlatToDict(data): ¶

Helper function for FlatToDict.

This function is recursively called

Parameters
data	The input data as described in `FlatToDict`, already splitted
Returns
The so far converted dict

def _NiceSortGetKey(val): ¶

Get a suitable sort key.

Attempt to convert a value to an integer and wrap it in a _NiceSortKey.

_SORTER_GROUPS: int = ¶

Undocumented

Value

_SORTER_RE = ¶

Undocumented

Value

re.compile('^%s(.*)$'%(_SORTER_GROUPS*'(\\D+|\\d+)?'))