Statistics
| Branch: | Tag: | Revision:

root / lib / utils / algo.py @ 9c709b31

History | View | Annotate | Download (7.3 kB)

1
#
2
#
3

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

    
21
"""Utility functions with algorithms.
22

23
"""
24

    
25
import re
26
import time
27
import itertools
28

    
29
from ganeti import compat
30
from ganeti.utils import text
31

    
32

    
33
_SORTER_GROUPS = 8
34
_SORTER_RE = re.compile("^%s(.*)$" % (_SORTER_GROUPS * "(\D+|\d+)?"))
35
_SORTER_DIGIT = re.compile("^\d+$")
36

    
37

    
38
def UniqueSequence(seq):
39
  """Returns a list with unique elements.
40

41
  Element order is preserved.
42

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

48
  """
49
  seen = set()
50
  return [i for i in seq if i not in seen and not seen.add(i)]
51

    
52

    
53
def JoinDisjointDicts(dict_a, dict_b):
54
  """Joins dictionaries with no conflicting keys.
55

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

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

68
  """
69
  assert not (set(dict_a) & set(dict_b)), ("Duplicate keys found while joining"
70
                                           " %s and %s" % (dict_a, dict_b))
71
  result = dict_a.copy()
72
  result.update(dict_b)
73
  return result
74

    
75

    
76
def FindDuplicates(seq):
77
  """Identifies duplicates in a list.
78

79
  Does not preserve element order.
80

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

86
  """
87
  dup = set()
88
  seen = set()
89

    
90
  for item in seq:
91
    if item in seen:
92
      dup.add(item)
93
    else:
94
      seen.add(item)
95

    
96
  return list(dup)
97

    
98

    
99
def _NiceSortTryInt(val):
100
  """Attempts to convert a string to an integer.
101

102
  """
103
  if val and _SORTER_DIGIT.match(val):
104
    return int(val)
105
  else:
106
    return val
107

    
108

    
109
def NiceSortKey(value):
110
  """Extract key for sorting.
111

112
  """
113
  return [_NiceSortTryInt(grp)
114
          for grp in _SORTER_RE.match(value).groups()]
115

    
116

    
117
def NiceSort(values, key=None):
118
  """Sort a list of strings based on digit and non-digit groupings.
119

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

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

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

136
  """
137
  if key is None:
138
    keyfunc = NiceSortKey
139
  else:
140
    keyfunc = lambda value: NiceSortKey(key(value))
141

    
142
  return sorted(values, key=keyfunc)
143

    
144

    
145
def InvertDict(dict_in):
146
  """Inverts the key/value mapping of a dict.
147

148
  @param dict_in: The dict to invert
149
  @return: the inverted dict
150

151
  """
152
  return dict(zip(dict_in.values(), dict_in.keys()))
153

    
154

    
155
def InsertAtPos(src, pos, other):
156
  """Inserts C{other} at given C{pos} into C{src}.
157

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

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

168
  """
169
  new = src[:pos]
170
  new.extend(other)
171
  new.extend(src[pos:])
172

    
173
  return new
174

    
175

    
176
def SequenceToDict(seq, key=compat.fst):
177
  """Converts a sequence to a dictionary with duplicate detection.
178

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

185
  """
186
  keys = map(key, seq)
187

    
188
  duplicates = FindDuplicates(keys)
189
  if duplicates:
190
    raise ValueError("Duplicate keys found: %s" % text.CommaJoin(duplicates))
191

    
192
  assert len(keys) == len(seq)
193

    
194
  return dict(zip(keys, seq))
195

    
196

    
197
def _MakeFlatToDict(data):
198
  """Helper function for C{FlatToDict}.
199

200
  This function is recursively called
201

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

205
  """
206
  if not compat.fst(compat.fst(data)):
207
    assert len(data) == 1, \
208
      "not bottom most element, found %d elements, expected 1" % len(data)
209
    return compat.snd(compat.fst(data))
210

    
211
  keyfn = lambda e: compat.fst(e).pop(0)
212
  return dict([(k, _MakeFlatToDict(list(g)))
213
               for (k, g) in itertools.groupby(sorted(data), keyfn)])
214

    
215

    
216
def FlatToDict(data, field_sep="/"):
217
  """Converts a flat structure to a fully fledged dict.
218

219
  It accept a list of tuples in the form::
220

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

226
  where the first element is the key separated by C{field_sep}.
227

228
  This would then return::
229

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

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

243
  """
244
  return _MakeFlatToDict([(keys.split(field_sep), value)
245
                          for (keys, value) in data])
246

    
247

    
248
class RunningTimeout(object):
249
  """Class to calculate remaining timeout when doing several operations.
250

251
  """
252
  __slots__ = [
253
    "_allow_negative",
254
    "_start_time",
255
    "_time_fn",
256
    "_timeout",
257
    ]
258

    
259
  def __init__(self, timeout, allow_negative, _time_fn=time.time):
260
    """Initializes this class.
261

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

268
    """
269
    object.__init__(self)
270

    
271
    if timeout is not None and timeout < 0.0:
272
      raise ValueError("Timeout must not be negative")
273

    
274
    self._timeout = timeout
275
    self._allow_negative = allow_negative
276
    self._time_fn = _time_fn
277

    
278
    self._start_time = None
279

    
280
  def Remaining(self):
281
    """Returns the remaining timeout.
282

283
    """
284
    if self._timeout is None:
285
      return None
286

    
287
    # Get start time on first calculation
288
    if self._start_time is None:
289
      self._start_time = self._time_fn()
290

    
291
    # Calculate remaining time
292
    remaining_timeout = self._start_time + self._timeout - self._time_fn()
293

    
294
    if not self._allow_negative:
295
      # Ensure timeout is always >= 0
296
      return max(0.0, remaining_timeout)
297

    
298
    return remaining_timeout