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