Statistics
| Branch: | Tag: | Revision:

root / lib / utils / algo.py @ adc523ab

History | View | Annotate | Download (4 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 4fd029cf Michael Hanselmann
28 4fd029cf Michael Hanselmann
29 7d4da09e Michael Hanselmann
_SORTER_GROUPS = 8
30 7d4da09e Michael Hanselmann
_SORTER_RE = re.compile("^%s(.*)$" % (_SORTER_GROUPS * "(\D+|\d+)?"))
31 4fd029cf Michael Hanselmann
_SORTER_DIGIT = re.compile("^\d+$")
32 4fd029cf Michael Hanselmann
33 4fd029cf Michael Hanselmann
34 4fd029cf Michael Hanselmann
def UniqueSequence(seq):
35 4fd029cf Michael Hanselmann
  """Returns a list with unique elements.
36 4fd029cf Michael Hanselmann

37 4fd029cf Michael Hanselmann
  Element order is preserved.
38 4fd029cf Michael Hanselmann

39 4fd029cf Michael Hanselmann
  @type seq: sequence
40 4fd029cf Michael Hanselmann
  @param seq: the sequence with the source elements
41 4fd029cf Michael Hanselmann
  @rtype: list
42 4fd029cf Michael Hanselmann
  @return: list of unique elements from seq
43 4fd029cf Michael Hanselmann

44 4fd029cf Michael Hanselmann
  """
45 4fd029cf Michael Hanselmann
  seen = set()
46 4fd029cf Michael Hanselmann
  return [i for i in seq if i not in seen and not seen.add(i)]
47 4fd029cf Michael Hanselmann
48 4fd029cf Michael Hanselmann
49 4fd029cf Michael Hanselmann
def FindDuplicates(seq):
50 4fd029cf Michael Hanselmann
  """Identifies duplicates in a list.
51 4fd029cf Michael Hanselmann

52 4fd029cf Michael Hanselmann
  Does not preserve element order.
53 4fd029cf Michael Hanselmann

54 4fd029cf Michael Hanselmann
  @type seq: sequence
55 4fd029cf Michael Hanselmann
  @param seq: Sequence with source elements
56 4fd029cf Michael Hanselmann
  @rtype: list
57 4fd029cf Michael Hanselmann
  @return: List of duplicate elements from seq
58 4fd029cf Michael Hanselmann

59 4fd029cf Michael Hanselmann
  """
60 4fd029cf Michael Hanselmann
  dup = set()
61 4fd029cf Michael Hanselmann
  seen = set()
62 4fd029cf Michael Hanselmann
63 4fd029cf Michael Hanselmann
  for item in seq:
64 4fd029cf Michael Hanselmann
    if item in seen:
65 4fd029cf Michael Hanselmann
      dup.add(item)
66 4fd029cf Michael Hanselmann
    else:
67 4fd029cf Michael Hanselmann
      seen.add(item)
68 4fd029cf Michael Hanselmann
69 4fd029cf Michael Hanselmann
  return list(dup)
70 4fd029cf Michael Hanselmann
71 4fd029cf Michael Hanselmann
72 4fd029cf Michael Hanselmann
def _NiceSortTryInt(val):
73 4fd029cf Michael Hanselmann
  """Attempts to convert a string to an integer.
74 4fd029cf Michael Hanselmann

75 4fd029cf Michael Hanselmann
  """
76 4fd029cf Michael Hanselmann
  if val and _SORTER_DIGIT.match(val):
77 4fd029cf Michael Hanselmann
    return int(val)
78 4fd029cf Michael Hanselmann
  else:
79 4fd029cf Michael Hanselmann
    return val
80 4fd029cf Michael Hanselmann
81 4fd029cf Michael Hanselmann
82 7d4da09e Michael Hanselmann
def NiceSortKey(value):
83 4fd029cf Michael Hanselmann
  """Extract key for sorting.
84 4fd029cf Michael Hanselmann

85 4fd029cf Michael Hanselmann
  """
86 4fd029cf Michael Hanselmann
  return [_NiceSortTryInt(grp)
87 4fd029cf Michael Hanselmann
          for grp in _SORTER_RE.match(value).groups()]
88 4fd029cf Michael Hanselmann
89 4fd029cf Michael Hanselmann
90 4fd029cf Michael Hanselmann
def NiceSort(values, key=None):
91 4fd029cf Michael Hanselmann
  """Sort a list of strings based on digit and non-digit groupings.
92 4fd029cf Michael Hanselmann

93 4fd029cf Michael Hanselmann
  Given a list of names C{['a1', 'a10', 'a11', 'a2']} this function
94 4fd029cf Michael Hanselmann
  will sort the list in the logical order C{['a1', 'a2', 'a10',
95 4fd029cf Michael Hanselmann
  'a11']}.
96 4fd029cf Michael Hanselmann

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

101 4fd029cf Michael Hanselmann
  @type values: list
102 4fd029cf Michael Hanselmann
  @param values: the names to be sorted
103 4fd029cf Michael Hanselmann
  @type key: callable or None
104 4fd029cf Michael Hanselmann
  @param key: function of one argument to extract a comparison key from each
105 4fd029cf Michael Hanselmann
    list element, must return string
106 4fd029cf Michael Hanselmann
  @rtype: list
107 4fd029cf Michael Hanselmann
  @return: a copy of the name list sorted with our algorithm
108 4fd029cf Michael Hanselmann

109 4fd029cf Michael Hanselmann
  """
110 4fd029cf Michael Hanselmann
  if key is None:
111 7d4da09e Michael Hanselmann
    keyfunc = NiceSortKey
112 4fd029cf Michael Hanselmann
  else:
113 7d4da09e Michael Hanselmann
    keyfunc = lambda value: NiceSortKey(key(value))
114 4fd029cf Michael Hanselmann
115 4fd029cf Michael Hanselmann
  return sorted(values, key=keyfunc)
116 7d444d59 Michael Hanselmann
117 7d444d59 Michael Hanselmann
118 7d444d59 Michael Hanselmann
class RunningTimeout(object):
119 7d444d59 Michael Hanselmann
  """Class to calculate remaining timeout when doing several operations.
120 7d444d59 Michael Hanselmann

121 7d444d59 Michael Hanselmann
  """
122 7d444d59 Michael Hanselmann
  __slots__ = [
123 7d444d59 Michael Hanselmann
    "_allow_negative",
124 7d444d59 Michael Hanselmann
    "_start_time",
125 7d444d59 Michael Hanselmann
    "_time_fn",
126 7d444d59 Michael Hanselmann
    "_timeout",
127 7d444d59 Michael Hanselmann
    ]
128 7d444d59 Michael Hanselmann
129 7d444d59 Michael Hanselmann
  def __init__(self, timeout, allow_negative, _time_fn=time.time):
130 7d444d59 Michael Hanselmann
    """Initializes this class.
131 7d444d59 Michael Hanselmann

132 7d444d59 Michael Hanselmann
    @type timeout: float
133 7d444d59 Michael Hanselmann
    @param timeout: Timeout duration
134 7d444d59 Michael Hanselmann
    @type allow_negative: bool
135 7d444d59 Michael Hanselmann
    @param allow_negative: Whether to return values below zero
136 7d444d59 Michael Hanselmann
    @param _time_fn: Time function for unittests
137 7d444d59 Michael Hanselmann

138 7d444d59 Michael Hanselmann
    """
139 7d444d59 Michael Hanselmann
    object.__init__(self)
140 7d444d59 Michael Hanselmann
141 7d444d59 Michael Hanselmann
    if timeout is not None and timeout < 0.0:
142 7d444d59 Michael Hanselmann
      raise ValueError("Timeout must not be negative")
143 7d444d59 Michael Hanselmann
144 7d444d59 Michael Hanselmann
    self._timeout = timeout
145 7d444d59 Michael Hanselmann
    self._allow_negative = allow_negative
146 7d444d59 Michael Hanselmann
    self._time_fn = _time_fn
147 7d444d59 Michael Hanselmann
148 7d444d59 Michael Hanselmann
    self._start_time = None
149 7d444d59 Michael Hanselmann
150 7d444d59 Michael Hanselmann
  def Remaining(self):
151 7d444d59 Michael Hanselmann
    """Returns the remaining timeout.
152 7d444d59 Michael Hanselmann

153 7d444d59 Michael Hanselmann
    """
154 7d444d59 Michael Hanselmann
    if self._timeout is None:
155 7d444d59 Michael Hanselmann
      return None
156 7d444d59 Michael Hanselmann
157 7d444d59 Michael Hanselmann
    # Get start time on first calculation
158 7d444d59 Michael Hanselmann
    if self._start_time is None:
159 7d444d59 Michael Hanselmann
      self._start_time = self._time_fn()
160 7d444d59 Michael Hanselmann
161 7d444d59 Michael Hanselmann
    # Calculate remaining time
162 7d444d59 Michael Hanselmann
    remaining_timeout = self._start_time + self._timeout - self._time_fn()
163 7d444d59 Michael Hanselmann
164 7d444d59 Michael Hanselmann
    if not self._allow_negative:
165 7d444d59 Michael Hanselmann
      # Ensure timeout is always >= 0
166 7d444d59 Michael Hanselmann
      return max(0.0, remaining_timeout)
167 7d444d59 Michael Hanselmann
168 7d444d59 Michael Hanselmann
    return remaining_timeout