X-Git-Url: https://code.grnet.gr/git/ganeti-local/blobdiff_plain/7d444d5965e5928f8cbbd533921437c1ab95754e..3f73b3ae4743de04ab5a64261d5e434829cdcba8:/lib/utils/algo.py

diff --git a/lib/utils/algo.py b/lib/utils/algo.py
index 3cccaa8..ec8ce34 100644
--- a/lib/utils/algo.py
+++ b/lib/utils/algo.py
@@ -24,10 +24,14 @@
 
 import re
 import time
+import itertools
 
+from ganeti import compat
+from ganeti.utils import text
 
-_SORTER_RE = re.compile("^%s(.*)$" % (8 * "(\D+|\d+)?"))
-_SORTER_DIGIT = re.compile("^\d+$")
+
+_SORTER_GROUPS = 8
+_SORTER_RE = re.compile("^%s(.*)$" % (_SORTER_GROUPS * "(\D+|\d+)?"))
 
 
 def UniqueSequence(seq):
@@ -45,6 +49,29 @@ def UniqueSequence(seq):
   return [i for i in seq if i not in seen and not seen.add(i)]
 
 
+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.
+
+  @type dict_a: dict
+  @param dict_a: the first dictionary
+  @type dict_b: dict
+  @param dict_b: the second dictionary
+  @rtype: dict
+  @return: a new dictionary containing all the key/value pairs contained in the
+  two dictionaries.
+
+  """
+  assert not (set(dict_a) & set(dict_b)), ("Duplicate keys found while joining"
+                                           " %s and %s" % (dict_a, dict_b))
+  result = dict_a.copy()
+  result.update(dict_b)
+  return result
+
+
 def FindDuplicates(seq):
   """Identifies duplicates in a list.
 
@@ -72,13 +99,13 @@ def _NiceSortTryInt(val):
   """Attempts to convert a string to an integer.
 
   """
-  if val and _SORTER_DIGIT.match(val):
+  if val and val.isdigit():
     return int(val)
   else:
     return val
 
 
-def _NiceSortKey(value):
+def NiceSortKey(value):
   """Extract key for sorting.
 
   """
@@ -107,13 +134,116 @@ def NiceSort(values, key=None):
 
   """
   if key is None:
-    keyfunc = _NiceSortKey
+    keyfunc = NiceSortKey
   else:
-    keyfunc = lambda value: _NiceSortKey(key(value))
+    keyfunc = lambda value: NiceSortKey(key(value))
 
   return sorted(values, key=keyfunc)
 
 
+def InvertDict(dict_in):
+  """Inverts the key/value mapping of a dict.
+
+  @param dict_in: The dict to invert
+  @return: the inverted dict
+
+  """
+  return dict(zip(dict_in.values(), dict_in.keys()))
+
+
+def InsertAtPos(src, pos, other):
+  """Inserts C{other} at given C{pos} into C{src}.
+
+  @note: This function does not modify C{src} in place but returns a new copy
+
+  @type src: list
+  @param src: The source list in which we want insert elements
+  @type pos: int
+  @param pos: The position where we want to start insert C{other}
+  @type other: list
+  @param other: The other list to insert into C{src}
+  @return: A copy of C{src} with C{other} inserted at C{pos}
+
+  """
+  new = src[:pos]
+  new.extend(other)
+  new.extend(src[pos:])
+
+  return new
+
+
+def SequenceToDict(seq, key=compat.fst):
+  """Converts a sequence to a dictionary with duplicate detection.
+
+  @type seq: sequen
+  @param seq: Input sequence
+  @type key: callable
+  @param key: Function for retrieving dictionary key from sequence element
+  @rtype: dict
+
+  """
+  keys = map(key, seq)
+
+  duplicates = FindDuplicates(keys)
+  if duplicates:
+    raise ValueError("Duplicate keys found: %s" % text.CommaJoin(duplicates))
+
+  assert len(keys) == len(seq)
+
+  return dict(zip(keys, seq))
+
+
+def _MakeFlatToDict(data):
+  """Helper function for C{FlatToDict}.
+
+  This function is recursively called
+
+  @param data: The input data as described in C{FlatToDict}, already splitted
+  @returns: The so far converted dict
+
+  """
+  if not compat.fst(compat.fst(data)):
+    assert len(data) == 1, \
+      "not bottom most element, found %d elements, expected 1" % len(data)
+    return compat.snd(compat.fst(data))
+
+  keyfn = lambda e: compat.fst(e).pop(0)
+  return dict([(k, _MakeFlatToDict(list(g)))
+               for (k, g) in itertools.groupby(sorted(data), keyfn)])
+
+
+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 C{field_sep}.
+
+  This would then return::
+
+    {
+      "foo": {
+        "bar": {"key1": "data1", "key2": "data2"},
+        "baz": {"key3" :"data3" },
+        },
+    }
+
+  @type data: list of tuple
+  @param data: Input list to convert
+  @type field_sep: str
+  @param field_sep: The separator for the first field of the tuple
+  @returns: A dict based on the input list
+
+  """
+  return _MakeFlatToDict([(keys.split(field_sep), value)
+                          for (keys, value) in data])
+
+
 class RunningTimeout(object):
   """Class to calculate remaining timeout when doing several operations.