Statistics
| Branch: | Tag: | Revision:

root / lib / utils / algo.py @ 81f7ea25

History | View | Annotate | Download (7.3 kB)

1 4fd029cf Michael Hanselmann
#
2 4fd029cf Michael Hanselmann
#
3 4fd029cf Michael Hanselmann
4 4fd029cf Michael Hanselmann
# Copyright (C) 2006, 2007, 2010, 2011 Google Inc.
5 4fd029cf Michael Hanselmann
#
6 4fd029cf Michael Hanselmann
# This program is free software; you can redistribute it and/or modify
7 4fd029cf Michael Hanselmann
# it under the terms of the GNU General Public License as published by
8 4fd029cf Michael Hanselmann
# the Free Software Foundation; either version 2 of the License, or
9 4fd029cf Michael Hanselmann
# (at your option) any later version.
10 4fd029cf Michael Hanselmann
#
11 4fd029cf Michael Hanselmann
# This program is distributed in the hope that it will be useful, but
12 4fd029cf Michael Hanselmann
# WITHOUT ANY WARRANTY; without even the implied warranty of
13 4fd029cf Michael Hanselmann
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 4fd029cf Michael Hanselmann
# General Public License for more details.
15 4fd029cf Michael Hanselmann
#
16 4fd029cf Michael Hanselmann
# You should have received a copy of the GNU General Public License
17 4fd029cf Michael Hanselmann
# along with this program; if not, write to the Free Software
18 4fd029cf Michael Hanselmann
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 4fd029cf Michael Hanselmann
# 02110-1301, USA.
20 4fd029cf Michael Hanselmann
21 4fd029cf Michael Hanselmann
"""Utility functions with algorithms.
22 4fd029cf Michael Hanselmann

23 4fd029cf Michael Hanselmann
"""
24 4fd029cf Michael Hanselmann
25 4fd029cf Michael Hanselmann
import re
26 7d444d59 Michael Hanselmann
import time
27 9c709b31 René Nussbaumer
import itertools
28 4fd029cf Michael Hanselmann
29 6d0accae Michael Hanselmann
from ganeti import compat
30 6d0accae Michael Hanselmann
from ganeti.utils import text
31 6d0accae Michael Hanselmann
32 4fd029cf Michael Hanselmann
33 7d4da09e Michael Hanselmann
_SORTER_GROUPS = 8
34 7d4da09e Michael Hanselmann
_SORTER_RE = re.compile("^%s(.*)$" % (_SORTER_GROUPS * "(\D+|\d+)?"))
35 4fd029cf Michael Hanselmann
_SORTER_DIGIT = re.compile("^\d+$")
36 4fd029cf Michael Hanselmann
37 4fd029cf Michael Hanselmann
38 4fd029cf Michael Hanselmann
def UniqueSequence(seq):
39 4fd029cf Michael Hanselmann
  """Returns a list with unique elements.
40 4fd029cf Michael Hanselmann

41 4fd029cf Michael Hanselmann
  Element order is preserved.
42 4fd029cf Michael Hanselmann

43 4fd029cf Michael Hanselmann
  @type seq: sequence
44 4fd029cf Michael Hanselmann
  @param seq: the sequence with the source elements
45 4fd029cf Michael Hanselmann
  @rtype: list
46 4fd029cf Michael Hanselmann
  @return: list of unique elements from seq
47 4fd029cf Michael Hanselmann

48 4fd029cf Michael Hanselmann
  """
49 4fd029cf Michael Hanselmann
  seen = set()
50 4fd029cf Michael Hanselmann
  return [i for i in seq if i not in seen and not seen.add(i)]
51 4fd029cf Michael Hanselmann
52 4fd029cf Michael Hanselmann
53 cdf71b12 Andrea Spadaccini
def JoinDisjointDicts(dict_a, dict_b):
54 cdf71b12 Andrea Spadaccini
  """Joins dictionaries with no conflicting keys.
55 cdf71b12 Andrea Spadaccini

56 cdf71b12 Andrea Spadaccini
  Enforces the constraint that the two key sets must be disjoint, and then
57 cdf71b12 Andrea Spadaccini
  merges the two dictionaries in a new dictionary that is returned to the
58 cdf71b12 Andrea Spadaccini
  caller.
59 cdf71b12 Andrea Spadaccini

60 cdf71b12 Andrea Spadaccini
  @type dict_a: dict
61 cdf71b12 Andrea Spadaccini
  @param dict_a: the first dictionary
62 cdf71b12 Andrea Spadaccini
  @type dict_b: dict
63 cdf71b12 Andrea Spadaccini
  @param dict_b: the second dictionary
64 cdf71b12 Andrea Spadaccini
  @rtype: dict
65 cdf71b12 Andrea Spadaccini
  @return: a new dictionary containing all the key/value pairs contained in the
66 cdf71b12 Andrea Spadaccini
  two dictionaries.
67 cdf71b12 Andrea Spadaccini

68 cdf71b12 Andrea Spadaccini
  """
69 cdf71b12 Andrea Spadaccini
  assert not (set(dict_a) & set(dict_b)), ("Duplicate keys found while joining"
70 cdf71b12 Andrea Spadaccini
                                           " %s and %s" % (dict_a, dict_b))
71 cdf71b12 Andrea Spadaccini
  result = dict_a.copy()
72 cdf71b12 Andrea Spadaccini
  result.update(dict_b)
73 cdf71b12 Andrea Spadaccini
  return result
74 cdf71b12 Andrea Spadaccini
75 cdf71b12 Andrea Spadaccini
76 4fd029cf Michael Hanselmann
def FindDuplicates(seq):
77 4fd029cf Michael Hanselmann
  """Identifies duplicates in a list.
78 4fd029cf Michael Hanselmann

79 4fd029cf Michael Hanselmann
  Does not preserve element order.
80 4fd029cf Michael Hanselmann

81 4fd029cf Michael Hanselmann
  @type seq: sequence
82 4fd029cf Michael Hanselmann
  @param seq: Sequence with source elements
83 4fd029cf Michael Hanselmann
  @rtype: list
84 4fd029cf Michael Hanselmann
  @return: List of duplicate elements from seq
85 4fd029cf Michael Hanselmann

86 4fd029cf Michael Hanselmann
  """
87 4fd029cf Michael Hanselmann
  dup = set()
88 4fd029cf Michael Hanselmann
  seen = set()
89 4fd029cf Michael Hanselmann
90 4fd029cf Michael Hanselmann
  for item in seq:
91 4fd029cf Michael Hanselmann
    if item in seen:
92 4fd029cf Michael Hanselmann
      dup.add(item)
93 4fd029cf Michael Hanselmann
    else:
94 4fd029cf Michael Hanselmann
      seen.add(item)
95 4fd029cf Michael Hanselmann
96 4fd029cf Michael Hanselmann
  return list(dup)
97 4fd029cf Michael Hanselmann
98 4fd029cf Michael Hanselmann
99 4fd029cf Michael Hanselmann
def _NiceSortTryInt(val):
100 4fd029cf Michael Hanselmann
  """Attempts to convert a string to an integer.
101 4fd029cf Michael Hanselmann

102 4fd029cf Michael Hanselmann
  """
103 4fd029cf Michael Hanselmann
  if val and _SORTER_DIGIT.match(val):
104 4fd029cf Michael Hanselmann
    return int(val)
105 4fd029cf Michael Hanselmann
  else:
106 4fd029cf Michael Hanselmann
    return val
107 4fd029cf Michael Hanselmann
108 4fd029cf Michael Hanselmann
109 7d4da09e Michael Hanselmann
def NiceSortKey(value):
110 4fd029cf Michael Hanselmann
  """Extract key for sorting.
111 4fd029cf Michael Hanselmann

112 4fd029cf Michael Hanselmann
  """
113 4fd029cf Michael Hanselmann
  return [_NiceSortTryInt(grp)
114 4fd029cf Michael Hanselmann
          for grp in _SORTER_RE.match(value).groups()]
115 4fd029cf Michael Hanselmann
116 4fd029cf Michael Hanselmann
117 4fd029cf Michael Hanselmann
def NiceSort(values, key=None):
118 4fd029cf Michael Hanselmann
  """Sort a list of strings based on digit and non-digit groupings.
119 4fd029cf Michael Hanselmann

120 4fd029cf Michael Hanselmann
  Given a list of names C{['a1', 'a10', 'a11', 'a2']} this function
121 4fd029cf Michael Hanselmann
  will sort the list in the logical order C{['a1', 'a2', 'a10',
122 4fd029cf Michael Hanselmann
  'a11']}.
123 4fd029cf Michael Hanselmann

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

128 4fd029cf Michael Hanselmann
  @type values: list
129 4fd029cf Michael Hanselmann
  @param values: the names to be sorted
130 4fd029cf Michael Hanselmann
  @type key: callable or None
131 4fd029cf Michael Hanselmann
  @param key: function of one argument to extract a comparison key from each
132 4fd029cf Michael Hanselmann
    list element, must return string
133 4fd029cf Michael Hanselmann
  @rtype: list
134 4fd029cf Michael Hanselmann
  @return: a copy of the name list sorted with our algorithm
135 4fd029cf Michael Hanselmann

136 4fd029cf Michael Hanselmann
  """
137 4fd029cf Michael Hanselmann
  if key is None:
138 7d4da09e Michael Hanselmann
    keyfunc = NiceSortKey
139 4fd029cf Michael Hanselmann
  else:
140 7d4da09e Michael Hanselmann
    keyfunc = lambda value: NiceSortKey(key(value))
141 4fd029cf Michael Hanselmann
142 4fd029cf Michael Hanselmann
  return sorted(values, key=keyfunc)
143 7d444d59 Michael Hanselmann
144 7d444d59 Michael Hanselmann
145 0a9a0e5a René Nussbaumer
def InvertDict(dict_in):
146 0a9a0e5a René Nussbaumer
  """Inverts the key/value mapping of a dict.
147 0a9a0e5a René Nussbaumer

148 0a9a0e5a René Nussbaumer
  @param dict_in: The dict to invert
149 d5fca545 Iustin Pop
  @return: the inverted dict
150 0a9a0e5a René Nussbaumer

151 0a9a0e5a René Nussbaumer
  """
152 0a9a0e5a René Nussbaumer
  return dict(zip(dict_in.values(), dict_in.keys()))
153 0a9a0e5a René Nussbaumer
154 0a9a0e5a René Nussbaumer
155 d60946d9 René Nussbaumer
def InsertAtPos(src, pos, other):
156 d60946d9 René Nussbaumer
  """Inserts C{other} at given C{pos} into C{src}.
157 d60946d9 René Nussbaumer

158 d60946d9 René Nussbaumer
  @note: This function does not modify C{src} in place but returns a new copy
159 d60946d9 René Nussbaumer

160 d60946d9 René Nussbaumer
  @type src: list
161 d60946d9 René Nussbaumer
  @param src: The source list in which we want insert elements
162 d60946d9 René Nussbaumer
  @type pos: int
163 d60946d9 René Nussbaumer
  @param pos: The position where we want to start insert C{other}
164 d60946d9 René Nussbaumer
  @type other: list
165 d60946d9 René Nussbaumer
  @param other: The other list to insert into C{src}
166 d60946d9 René Nussbaumer
  @return: A copy of C{src} with C{other} inserted at C{pos}
167 d60946d9 René Nussbaumer

168 d60946d9 René Nussbaumer
  """
169 d60946d9 René Nussbaumer
  new = src[:pos]
170 d60946d9 René Nussbaumer
  new.extend(other)
171 d60946d9 René Nussbaumer
  new.extend(src[pos:])
172 d60946d9 René Nussbaumer
173 d60946d9 René Nussbaumer
  return new
174 d60946d9 René Nussbaumer
175 d60946d9 René Nussbaumer
176 6d0accae Michael Hanselmann
def SequenceToDict(seq, key=compat.fst):
177 6d0accae Michael Hanselmann
  """Converts a sequence to a dictionary with duplicate detection.
178 6d0accae Michael Hanselmann

179 6d0accae Michael Hanselmann
  @type seq: sequen
180 6d0accae Michael Hanselmann
  @param seq: Input sequence
181 6d0accae Michael Hanselmann
  @type key: callable
182 6d0accae Michael Hanselmann
  @param key: Function for retrieving dictionary key from sequence element
183 6d0accae Michael Hanselmann
  @rtype: dict
184 6d0accae Michael Hanselmann

185 6d0accae Michael Hanselmann
  """
186 6d0accae Michael Hanselmann
  keys = map(key, seq)
187 6d0accae Michael Hanselmann
188 6d0accae Michael Hanselmann
  duplicates = FindDuplicates(keys)
189 6d0accae Michael Hanselmann
  if duplicates:
190 6d0accae Michael Hanselmann
    raise ValueError("Duplicate keys found: %s" % text.CommaJoin(duplicates))
191 6d0accae Michael Hanselmann
192 6d0accae Michael Hanselmann
  assert len(keys) == len(seq)
193 6d0accae Michael Hanselmann
194 6d0accae Michael Hanselmann
  return dict(zip(keys, seq))
195 6d0accae Michael Hanselmann
196 6d0accae Michael Hanselmann
197 9c709b31 René Nussbaumer
def _MakeFlatToDict(data):
198 9c709b31 René Nussbaumer
  """Helper function for C{FlatToDict}.
199 9c709b31 René Nussbaumer

200 9c709b31 René Nussbaumer
  This function is recursively called
201 9c709b31 René Nussbaumer

202 9c709b31 René Nussbaumer
  @param data: The input data as described in C{FlatToDict}, already splitted
203 9c709b31 René Nussbaumer
  @returns: The so far converted dict
204 9c709b31 René Nussbaumer

205 9c709b31 René Nussbaumer
  """
206 9c709b31 René Nussbaumer
  if not compat.fst(compat.fst(data)):
207 9c709b31 René Nussbaumer
    assert len(data) == 1, \
208 9c709b31 René Nussbaumer
      "not bottom most element, found %d elements, expected 1" % len(data)
209 9c709b31 René Nussbaumer
    return compat.snd(compat.fst(data))
210 9c709b31 René Nussbaumer
211 9c709b31 René Nussbaumer
  keyfn = lambda e: compat.fst(e).pop(0)
212 9c709b31 René Nussbaumer
  return dict([(k, _MakeFlatToDict(list(g)))
213 9c709b31 René Nussbaumer
               for (k, g) in itertools.groupby(sorted(data), keyfn)])
214 9c709b31 René Nussbaumer
215 9c709b31 René Nussbaumer
216 9c709b31 René Nussbaumer
def FlatToDict(data, field_sep="/"):
217 9c709b31 René Nussbaumer
  """Converts a flat structure to a fully fledged dict.
218 9c709b31 René Nussbaumer

219 9c709b31 René Nussbaumer
  It accept a list of tuples in the form::
220 9c709b31 René Nussbaumer

221 9c709b31 René Nussbaumer
    [
222 9c709b31 René Nussbaumer
      ("foo/bar", {"key1": "data1", "key2": "data2"}),
223 9c709b31 René Nussbaumer
      ("foo/baz", {"key3" :"data3" }),
224 9c709b31 René Nussbaumer
    ]
225 9c709b31 René Nussbaumer

226 9c709b31 René Nussbaumer
  where the first element is the key separated by C{field_sep}.
227 9c709b31 René Nussbaumer

228 9c709b31 René Nussbaumer
  This would then return::
229 9c709b31 René Nussbaumer

230 9c709b31 René Nussbaumer
    {
231 9c709b31 René Nussbaumer
      "foo": {
232 9c709b31 René Nussbaumer
        "bar": {"key1": "data1", "key2": "data2"},
233 9c709b31 René Nussbaumer
        "baz": {"key3" :"data3" },
234 9c709b31 René Nussbaumer
        },
235 9c709b31 René Nussbaumer
    }
236 9c709b31 René Nussbaumer

237 9c709b31 René Nussbaumer
  @type data: list of tuple
238 9c709b31 René Nussbaumer
  @param data: Input list to convert
239 9c709b31 René Nussbaumer
  @type field_sep: str
240 9c709b31 René Nussbaumer
  @param field_sep: The separator for the first field of the tuple
241 9c709b31 René Nussbaumer
  @returns: A dict based on the input list
242 9c709b31 René Nussbaumer

243 9c709b31 René Nussbaumer
  """
244 9c709b31 René Nussbaumer
  return _MakeFlatToDict([(keys.split(field_sep), value)
245 9c709b31 René Nussbaumer
                          for (keys, value) in data])
246 9c709b31 René Nussbaumer
247 9c709b31 René Nussbaumer
248 7d444d59 Michael Hanselmann
class RunningTimeout(object):
249 7d444d59 Michael Hanselmann
  """Class to calculate remaining timeout when doing several operations.
250 7d444d59 Michael Hanselmann

251 7d444d59 Michael Hanselmann
  """
252 7d444d59 Michael Hanselmann
  __slots__ = [
253 7d444d59 Michael Hanselmann
    "_allow_negative",
254 7d444d59 Michael Hanselmann
    "_start_time",
255 7d444d59 Michael Hanselmann
    "_time_fn",
256 7d444d59 Michael Hanselmann
    "_timeout",
257 7d444d59 Michael Hanselmann
    ]
258 7d444d59 Michael Hanselmann
259 7d444d59 Michael Hanselmann
  def __init__(self, timeout, allow_negative, _time_fn=time.time):
260 7d444d59 Michael Hanselmann
    """Initializes this class.
261 7d444d59 Michael Hanselmann

262 7d444d59 Michael Hanselmann
    @type timeout: float
263 7d444d59 Michael Hanselmann
    @param timeout: Timeout duration
264 7d444d59 Michael Hanselmann
    @type allow_negative: bool
265 7d444d59 Michael Hanselmann
    @param allow_negative: Whether to return values below zero
266 7d444d59 Michael Hanselmann
    @param _time_fn: Time function for unittests
267 7d444d59 Michael Hanselmann

268 7d444d59 Michael Hanselmann
    """
269 7d444d59 Michael Hanselmann
    object.__init__(self)
270 7d444d59 Michael Hanselmann
271 7d444d59 Michael Hanselmann
    if timeout is not None and timeout < 0.0:
272 7d444d59 Michael Hanselmann
      raise ValueError("Timeout must not be negative")
273 7d444d59 Michael Hanselmann
274 7d444d59 Michael Hanselmann
    self._timeout = timeout
275 7d444d59 Michael Hanselmann
    self._allow_negative = allow_negative
276 7d444d59 Michael Hanselmann
    self._time_fn = _time_fn
277 7d444d59 Michael Hanselmann
278 7d444d59 Michael Hanselmann
    self._start_time = None
279 7d444d59 Michael Hanselmann
280 7d444d59 Michael Hanselmann
  def Remaining(self):
281 7d444d59 Michael Hanselmann
    """Returns the remaining timeout.
282 7d444d59 Michael Hanselmann

283 7d444d59 Michael Hanselmann
    """
284 7d444d59 Michael Hanselmann
    if self._timeout is None:
285 7d444d59 Michael Hanselmann
      return None
286 7d444d59 Michael Hanselmann
287 7d444d59 Michael Hanselmann
    # Get start time on first calculation
288 7d444d59 Michael Hanselmann
    if self._start_time is None:
289 7d444d59 Michael Hanselmann
      self._start_time = self._time_fn()
290 7d444d59 Michael Hanselmann
291 7d444d59 Michael Hanselmann
    # Calculate remaining time
292 7d444d59 Michael Hanselmann
    remaining_timeout = self._start_time + self._timeout - self._time_fn()
293 7d444d59 Michael Hanselmann
294 7d444d59 Michael Hanselmann
    if not self._allow_negative:
295 7d444d59 Michael Hanselmann
      # Ensure timeout is always >= 0
296 7d444d59 Michael Hanselmann
      return max(0.0, remaining_timeout)
297 7d444d59 Michael Hanselmann
298 7d444d59 Michael Hanselmann
    return remaining_timeout