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 |