code.grnet.gr Git - ganeti-local/blob - lib/utils/algo.py

   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
  28
  29 _SORTER_RE = re.compile("^%s(.*)$" % (8 * "(\D+|\d+)?"))
  30 _SORTER_DIGIT = re.compile("^\d+$")
  31
  32
  33 def UniqueSequence(seq):
  34   """Returns a list with unique elements.
  35
  36   Element order is preserved.
  37
  38   @type seq: sequence
  39   @param seq: the sequence with the source elements
  40   @rtype: list
  41   @return: list of unique elements from seq
  42
  43   """
  44   seen = set()
  45   return [i for i in seq if i not in seen and not seen.add(i)]
  46
  47
  48 def FindDuplicates(seq):
  49   """Identifies duplicates in a list.
  50
  51   Does not preserve element order.
  52
  53   @type seq: sequence
  54   @param seq: Sequence with source elements
  55   @rtype: list
  56   @return: List of duplicate elements from seq
  57
  58   """
  59   dup = set()
  60   seen = set()
  61
  62   for item in seq:
  63     if item in seen:
  64       dup.add(item)
  65     else:
  66       seen.add(item)
  67
  68   return list(dup)
  69
  70
  71 def _NiceSortTryInt(val):
  72   """Attempts to convert a string to an integer.
  73
  74   """
  75   if val and _SORTER_DIGIT.match(val):
  76     return int(val)
  77   else:
  78     return val
  79
  80
  81 def _NiceSortKey(value):
  82   """Extract key for sorting.
  83
  84   """
  85   return [_NiceSortTryInt(grp)
  86           for grp in _SORTER_RE.match(value).groups()]
  87
  88
  89 def NiceSort(values, key=None):
  90   """Sort a list of strings based on digit and non-digit groupings.
  91
  92   Given a list of names C{['a1', 'a10', 'a11', 'a2']} this function
  93   will sort the list in the logical order C{['a1', 'a2', 'a10',
  94   'a11']}.
  95
  96   The sort algorithm breaks each name in groups of either only-digits
  97   or no-digits. Only the first eight such groups are considered, and
  98   after that we just use what's left of the string.
  99
 100   @type values: list
 101   @param values: the names to be sorted
 102   @type key: callable or None
 103   @param key: function of one argument to extract a comparison key from each
 104     list element, must return string
 105   @rtype: list
 106   @return: a copy of the name list sorted with our algorithm
 107
 108   """
 109   if key is None:
 110     keyfunc = _NiceSortKey
 111   else:
 112     keyfunc = lambda value: _NiceSortKey(key(value))
 113
 114   return sorted(values, key=keyfunc)
 115
 116
 117 class RunningTimeout(object):
 118   """Class to calculate remaining timeout when doing several operations.
 119
 120   """
 121   __slots__ = [
 122     "_allow_negative",
 123     "_start_time",
 124     "_time_fn",
 125     "_timeout",
 126     ]
 127
 128   def __init__(self, timeout, allow_negative, _time_fn=time.time):
 129     """Initializes this class.
 130
 131     @type timeout: float
 132     @param timeout: Timeout duration
 133     @type allow_negative: bool
 134     @param allow_negative: Whether to return values below zero
 135     @param _time_fn: Time function for unittests
 136
 137     """
 138     object.__init__(self)
 139
 140     if timeout is not None and timeout < 0.0:
 141       raise ValueError("Timeout must not be negative")
 142
 143     self._timeout = timeout
 144     self._allow_negative = allow_negative
 145     self._time_fn = _time_fn
 146
 147     self._start_time = None
 148
 149   def Remaining(self):
 150     """Returns the remaining timeout.
 151
 152     """
 153     if self._timeout is None:
 154       return None
 155
 156     # Get start time on first calculation
 157     if self._start_time is None:
 158       self._start_time = self._time_fn()
 159
 160     # Calculate remaining time
 161     remaining_timeout = self._start_time + self._timeout - self._time_fn()
 162
 163     if not self._allow_negative:
 164       # Ensure timeout is always >= 0
 165       return max(0.0, remaining_timeout)
 166
 167     return remaining_timeout