root / test / ganeti.utils.algo_unittest.py @ d60946d9
History | View | Annotate | Download (10.2 kB)
| 1 |
#!/usr/bin/python
|
|---|---|
| 2 |
#
|
| 3 |
|
| 4 |
# Copyright (C) 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 |
|
| 22 |
"""Script for testing ganeti.utils.algo"""
|
| 23 |
|
| 24 |
import unittest |
| 25 |
import random |
| 26 |
import operator |
| 27 |
|
| 28 |
from ganeti import constants |
| 29 |
from ganeti.utils import algo |
| 30 |
|
| 31 |
import testutils |
| 32 |
|
| 33 |
|
| 34 |
class TestUniqueSequence(unittest.TestCase): |
| 35 |
"""Test case for UniqueSequence"""
|
| 36 |
|
| 37 |
def _test(self, input, expected): |
| 38 |
self.assertEqual(algo.UniqueSequence(input), expected) |
| 39 |
|
| 40 |
def runTest(self): |
| 41 |
# Ordered input
|
| 42 |
self._test([1, 2, 3], [1, 2, 3]) |
| 43 |
self._test([1, 1, 2, 2, 3, 3], [1, 2, 3]) |
| 44 |
self._test([1, 2, 2, 3], [1, 2, 3]) |
| 45 |
self._test([1, 2, 3, 3], [1, 2, 3]) |
| 46 |
|
| 47 |
# Unordered input
|
| 48 |
self._test([1, 2, 3, 1, 2, 3], [1, 2, 3]) |
| 49 |
self._test([1, 1, 2, 3, 3, 1, 2], [1, 2, 3]) |
| 50 |
|
| 51 |
# Strings
|
| 52 |
self._test(["a", "a"], ["a"]) |
| 53 |
self._test(["a", "b"], ["a", "b"]) |
| 54 |
self._test(["a", "b", "a"], ["a", "b"]) |
| 55 |
|
| 56 |
|
| 57 |
class TestFindDuplicates(unittest.TestCase): |
| 58 |
"""Test case for FindDuplicates"""
|
| 59 |
|
| 60 |
def _Test(self, seq, expected): |
| 61 |
result = algo.FindDuplicates(seq) |
| 62 |
self.assertEqual(result, algo.UniqueSequence(result))
|
| 63 |
self.assertEqual(set(result), set(expected)) |
| 64 |
|
| 65 |
def test(self): |
| 66 |
self._Test([], [])
|
| 67 |
self._Test([1, 2, 3], []) |
| 68 |
self._Test([9, 8, 8, 0, 5, 1, 7, 0, 6, 7], [8, 0, 7]) |
| 69 |
for exp in [[1, 2, 3], [3, 2, 1]]: |
| 70 |
self._Test([1, 1, 2, 2, 3, 3], exp) |
| 71 |
|
| 72 |
self._Test(["A", "a", "B"], []) |
| 73 |
self._Test(["a", "A", "a", "B"], ["a"]) |
| 74 |
self._Test("Hello World out there!", ["e", " ", "o", "r", "t", "l"]) |
| 75 |
|
| 76 |
self._Test(self._Gen(False), []) |
| 77 |
self._Test(self._Gen(True), range(1, 10)) |
| 78 |
|
| 79 |
@staticmethod
|
| 80 |
def _Gen(dup): |
| 81 |
for i in range(10): |
| 82 |
yield i
|
| 83 |
if dup:
|
| 84 |
for _ in range(i): |
| 85 |
yield i
|
| 86 |
|
| 87 |
|
| 88 |
class TestNiceSort(unittest.TestCase): |
| 89 |
def test(self): |
| 90 |
self.assertEqual(algo.NiceSort([]), [])
|
| 91 |
self.assertEqual(algo.NiceSort(["foo"]), ["foo"]) |
| 92 |
self.assertEqual(algo.NiceSort(["bar", ""]), ["", "bar"]) |
| 93 |
self.assertEqual(algo.NiceSort([",", "."]), [",", "."]) |
| 94 |
self.assertEqual(algo.NiceSort(["0.1", "0.2"]), ["0.1", "0.2"]) |
| 95 |
self.assertEqual(algo.NiceSort(["0;099", "0,099", "0.1", "0.2"]), |
| 96 |
["0,099", "0.1", "0.2", "0;099"]) |
| 97 |
|
| 98 |
data = ["a0", "a1", "a99", "a20", "a2", "b10", "b70", "b00", "0000"] |
| 99 |
self.assertEqual(algo.NiceSort(data),
|
| 100 |
["0000", "a0", "a1", "a2", "a20", "a99", |
| 101 |
"b00", "b10", "b70"]) |
| 102 |
|
| 103 |
data = ["a0-0", "a1-0", "a99-10", "a20-3", "a0-4", "a99-3", "a09-2", |
| 104 |
"Z", "a9-1", "A", "b"] |
| 105 |
self.assertEqual(algo.NiceSort(data),
|
| 106 |
["A", "Z", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2", |
| 107 |
"a20-3", "a99-3", "a99-10", "b"]) |
| 108 |
self.assertEqual(algo.NiceSort(data, key=str.lower), |
| 109 |
["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2", |
| 110 |
"a20-3", "a99-3", "a99-10", "b", "Z"]) |
| 111 |
self.assertEqual(algo.NiceSort(data, key=str.upper), |
| 112 |
["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2", |
| 113 |
"a20-3", "a99-3", "a99-10", "b", "Z"]) |
| 114 |
|
| 115 |
def testLargeA(self): |
| 116 |
data = [ |
| 117 |
"Eegah9ei", "xij88brTulHYAv8IEOyU", "3jTwJPtrXOY22bwL2YoW", |
| 118 |
"Z8Ljf1Pf5eBfNg171wJR", "WvNJd91OoXvLzdEiEXa6", "uHXAyYYftCSG1o7qcCqe", |
| 119 |
"xpIUJeVT1Rp", "KOt7vn1dWXi", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH", |
| 120 |
"cPRi0lM7HLnSuWA2G9", "KVQqLPDjcPjf8T3oyzjcOsfkb", |
| 121 |
"guKJkXnkULealVC8CyF1xefym", "pqF8dkU5B1cMnyZuREaSOADYx", |
| 122 |
] |
| 123 |
self.assertEqual(algo.NiceSort(data), [
|
| 124 |
"3jTwJPtrXOY22bwL2YoW", "Eegah9ei", "KOt7vn1dWXi", |
| 125 |
"KVQqLPDjcPjf8T3oyzjcOsfkb", "WvNJd91OoXvLzdEiEXa6", |
| 126 |
"Z8Ljf1Pf5eBfNg171wJR", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH", |
| 127 |
"cPRi0lM7HLnSuWA2G9", "guKJkXnkULealVC8CyF1xefym", |
| 128 |
"pqF8dkU5B1cMnyZuREaSOADYx", "uHXAyYYftCSG1o7qcCqe", |
| 129 |
"xij88brTulHYAv8IEOyU", "xpIUJeVT1Rp" |
| 130 |
]) |
| 131 |
|
| 132 |
def testLargeB(self): |
| 133 |
data = [ |
| 134 |
"inst-0.0.0.0-0.0.0.0",
|
| 135 |
"inst-0.1.0.0-0.0.0.0",
|
| 136 |
"inst-0.2.0.0-0.0.0.0",
|
| 137 |
"inst-0.2.1.0-0.0.0.0",
|
| 138 |
"inst-0.2.2.0-0.0.0.0",
|
| 139 |
"inst-0.2.2.0-0.0.0.9",
|
| 140 |
"inst-0.2.2.0-0.0.3.9",
|
| 141 |
"inst-0.2.2.0-0.2.0.9",
|
| 142 |
"inst-0.2.2.0-0.9.0.9",
|
| 143 |
"inst-0.20.2.0-0.0.0.0",
|
| 144 |
"inst-0.20.2.0-0.9.0.9",
|
| 145 |
"inst-10.020.2.0-0.9.0.10",
|
| 146 |
"inst-15.020.2.0-0.9.1.00",
|
| 147 |
"inst-100.020.2.0-0.9.0.9",
|
| 148 |
|
| 149 |
# Only the last group, not converted to a number anymore, differs
|
| 150 |
"inst-100.020.2.0a999",
|
| 151 |
"inst-100.020.2.0b000",
|
| 152 |
"inst-100.020.2.0c10",
|
| 153 |
"inst-100.020.2.0c101",
|
| 154 |
"inst-100.020.2.0c2",
|
| 155 |
"inst-100.020.2.0c20",
|
| 156 |
"inst-100.020.2.0c3",
|
| 157 |
"inst-100.020.2.0c39123",
|
| 158 |
] |
| 159 |
|
| 160 |
rnd = random.Random(16205)
|
| 161 |
for _ in range(10): |
| 162 |
testdata = data[:] |
| 163 |
rnd.shuffle(testdata) |
| 164 |
assert testdata != data
|
| 165 |
self.assertEqual(algo.NiceSort(testdata), data)
|
| 166 |
|
| 167 |
class _CallCount: |
| 168 |
def __init__(self, fn): |
| 169 |
self.count = 0 |
| 170 |
self.fn = fn
|
| 171 |
|
| 172 |
def __call__(self, *args): |
| 173 |
self.count += 1 |
| 174 |
return self.fn(*args) |
| 175 |
|
| 176 |
def testKeyfuncA(self): |
| 177 |
# Generate some random numbers
|
| 178 |
rnd = random.Random(21131)
|
| 179 |
numbers = [rnd.randint(0, 10000) for _ in range(999)] |
| 180 |
assert numbers != sorted(numbers) |
| 181 |
|
| 182 |
# Convert to hex
|
| 183 |
data = [hex(i) for i in numbers] |
| 184 |
datacopy = data[:] |
| 185 |
|
| 186 |
keyfn = self._CallCount(lambda value: str(int(value, 16))) |
| 187 |
|
| 188 |
# Sort with key function converting hex to decimal
|
| 189 |
result = algo.NiceSort(data, key=keyfn) |
| 190 |
|
| 191 |
self.assertEqual([hex(i) for i in sorted(numbers)], result) |
| 192 |
self.assertEqual(data, datacopy, msg="Input data was modified in NiceSort") |
| 193 |
self.assertEqual(keyfn.count, len(numbers), |
| 194 |
msg="Key function was not called once per value")
|
| 195 |
|
| 196 |
class _TestData: |
| 197 |
def __init__(self, name, value): |
| 198 |
self.name = name
|
| 199 |
self.value = value
|
| 200 |
|
| 201 |
def testKeyfuncB(self): |
| 202 |
rnd = random.Random(27396)
|
| 203 |
data = [] |
| 204 |
for i in range(123): |
| 205 |
v1 = rnd.randint(0, 5) |
| 206 |
v2 = rnd.randint(0, 5) |
| 207 |
data.append(self._TestData("inst-%s-%s-%s" % (v1, v2, i), |
| 208 |
(v1, v2, i))) |
| 209 |
rnd.shuffle(data) |
| 210 |
assert data != sorted(data, key=operator.attrgetter("name")) |
| 211 |
|
| 212 |
keyfn = self._CallCount(operator.attrgetter("name")) |
| 213 |
|
| 214 |
# Sort by name
|
| 215 |
result = algo.NiceSort(data, key=keyfn) |
| 216 |
|
| 217 |
self.assertEqual(result, sorted(data, key=operator.attrgetter("value"))) |
| 218 |
self.assertEqual(keyfn.count, len(data), |
| 219 |
msg="Key function was not called once per value")
|
| 220 |
|
| 221 |
def testNiceSortKey(self): |
| 222 |
self.assertEqual(algo.NiceSortKey(""), |
| 223 |
([None] * algo._SORTER_GROUPS) + [""]) |
| 224 |
self.assertEqual(algo.NiceSortKey("Hello World"), |
| 225 |
["Hello World"] +
|
| 226 |
([None] * int(algo._SORTER_GROUPS - 1)) + [""]) |
| 227 |
self.assertEqual(algo.NiceSortKey("node1.net75.bld3.example.com"), |
| 228 |
["node", 1, ".net", 75, ".bld", 3, ".example.com", |
| 229 |
None, ""]) |
| 230 |
|
| 231 |
|
| 232 |
class TestInvertDict(unittest.TestCase): |
| 233 |
def testInvertDict(self): |
| 234 |
test_dict = { "foo": 1, "bar": 2, "baz": 5 }
|
| 235 |
self.assertEqual(algo.InvertDict(test_dict),
|
| 236 |
{ 1: "foo", 2: "bar", 5: "baz"})
|
| 237 |
|
| 238 |
|
| 239 |
class TestInsertAtPos(unittest.TestCase): |
| 240 |
def test(self): |
| 241 |
a = [1, 5, 6] |
| 242 |
b = [2, 3, 4] |
| 243 |
self.assertEqual(algo.InsertAtPos(a, 1, b), [1, 2, 3, 4, 5, 6]) |
| 244 |
self.assertEqual(algo.InsertAtPos(a, 0, b), b + a) |
| 245 |
self.assertEqual(algo.InsertAtPos(a, len(a), b), a + b) |
| 246 |
self.assertEqual(algo.InsertAtPos(a, 2, b), [1, 5, 2, 3, 4, 6]) |
| 247 |
|
| 248 |
|
| 249 |
class TimeMock: |
| 250 |
def __init__(self, values): |
| 251 |
self.values = values
|
| 252 |
|
| 253 |
def __call__(self): |
| 254 |
return self.values.pop(0) |
| 255 |
|
| 256 |
|
| 257 |
class TestRunningTimeout(unittest.TestCase): |
| 258 |
def setUp(self): |
| 259 |
self.time_fn = TimeMock([0.0, 0.3, 4.6, 6.5]) |
| 260 |
|
| 261 |
def testRemainingFloat(self): |
| 262 |
timeout = algo.RunningTimeout(5.0, True, _time_fn=self.time_fn) |
| 263 |
self.assertAlmostEqual(timeout.Remaining(), 4.7) |
| 264 |
self.assertAlmostEqual(timeout.Remaining(), 0.4) |
| 265 |
self.assertAlmostEqual(timeout.Remaining(), -1.5) |
| 266 |
|
| 267 |
def testRemaining(self): |
| 268 |
self.time_fn = TimeMock([0, 2, 4, 5, 6]) |
| 269 |
timeout = algo.RunningTimeout(5, True, _time_fn=self.time_fn) |
| 270 |
self.assertEqual(timeout.Remaining(), 3) |
| 271 |
self.assertEqual(timeout.Remaining(), 1) |
| 272 |
self.assertEqual(timeout.Remaining(), 0) |
| 273 |
self.assertEqual(timeout.Remaining(), -1) |
| 274 |
|
| 275 |
def testRemainingNonNegative(self): |
| 276 |
timeout = algo.RunningTimeout(5.0, False, _time_fn=self.time_fn) |
| 277 |
self.assertAlmostEqual(timeout.Remaining(), 4.7) |
| 278 |
self.assertAlmostEqual(timeout.Remaining(), 0.4) |
| 279 |
self.assertEqual(timeout.Remaining(), 0.0) |
| 280 |
|
| 281 |
def testNegativeTimeout(self): |
| 282 |
self.assertRaises(ValueError, algo.RunningTimeout, -1.0, True) |
| 283 |
|
| 284 |
|
| 285 |
class TestJoinDisjointDicts(unittest.TestCase): |
| 286 |
def setUp(self): |
| 287 |
self.non_empty_dict = {"a": 1, "b": 2} |
| 288 |
self.empty_dict = dict() |
| 289 |
|
| 290 |
def testWithEmptyDicts(self): |
| 291 |
self.assertEqual(self.empty_dict, algo.JoinDisjointDicts(self.empty_dict, |
| 292 |
self.empty_dict))
|
| 293 |
self.assertEqual(self.non_empty_dict, algo.JoinDisjointDicts( |
| 294 |
self.empty_dict, self.non_empty_dict)) |
| 295 |
self.assertEqual(self.non_empty_dict, algo.JoinDisjointDicts( |
| 296 |
self.non_empty_dict, self.empty_dict)) |
| 297 |
|
| 298 |
def testNonDisjoint(self): |
| 299 |
self.assertRaises(AssertionError, algo.JoinDisjointDicts, |
| 300 |
self.non_empty_dict, self.non_empty_dict) |
| 301 |
|
| 302 |
def testCommonCase(self): |
| 303 |
dict_a = {"TEST1": 1, "TEST2": 2}
|
| 304 |
dict_b = {"TEST3": 3, "TEST4": 4}
|
| 305 |
|
| 306 |
result = dict_a.copy() |
| 307 |
result.update(dict_b) |
| 308 |
|
| 309 |
self.assertEqual(result, algo.JoinDisjointDicts(dict_a, dict_b))
|
| 310 |
self.assertEqual(result, algo.JoinDisjointDicts(dict_b, dict_a))
|
| 311 |
|
| 312 |
|
| 313 |
if __name__ == "__main__": |
| 314 |
testutils.GanetiTestProgram() |