Statistics
| Branch: | Tag: | Revision:

root / lib / utils / algo.py @ 364c350f

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

    
36

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

40
  Element order is preserved.
41

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

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

    
51

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

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

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

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

    
74

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

78
  Does not preserve element order.
79

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

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

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

    
95
  return list(dup)
96

    
97

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

101
  """
102
  if val and val.isdigit():
103
    return int(val)
104
  else:
105
    return val
106

    
107

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

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

    
115

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

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

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

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

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

    
141
  return sorted(values, key=keyfunc)
142

    
143

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

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

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

    
153

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

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

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

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

    
172
  return new
173

    
174

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

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

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

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

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

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

    
195

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

199
  This function is recursively called
200

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

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

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

    
214

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

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

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

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

227
  This would then return::
228

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

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

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

    
246

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

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

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

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

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

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

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

    
277
    self._start_time = None
278

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

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

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

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

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

    
297
    return remaining_timeout