PyORAM/src/pyoram/tests/test_virtual_heap.py

   1 import os
   2 import subprocess
   3 import unittest2
   4
   5 import pyoram
   6 from pyoram.util.virtual_heap import \
   7     (VirtualHeap,
   8      SizedVirtualHeap,
   9      max_k_labeled,
  10      calculate_bucket_count_in_heap_with_height,
  11      calculate_bucket_count_in_heap_at_level,
  12      calculate_bucket_level,
  13      calculate_last_common_level,
  14      calculate_necessary_heap_height,
  15      basek_string_to_base10_integer,
  16      numerals,
  17      _clib)
  18
  19 from six.moves import xrange
  20
  21 thisdir = os.path.dirname(os.path.abspath(__file__))
  22 baselinedir = os.path.join(thisdir, "baselines")
  23
  24 try:
  25     has_dot = not subprocess.call(['dot','-?'],
  26                                   stdout=subprocess.PIPE)
  27 except:
  28     has_dot = False
  29
  30 _test_bases = list(xrange(2, 15)) + [max_k_labeled+1]
  31 _test_labeled_bases = list(xrange(2, 15)) + [max_k_labeled]
  32
  33 def _do_preorder(x):
  34     if x.level > 2:
  35         return
  36     yield x.bucket
  37     for c in xrange(x.k):
  38         for b in _do_preorder(x.child_node(c)):
  39             yield b
  40
  41 def _do_postorder(x):
  42     if x.level > 2:
  43         return
  44     for c in xrange(x.k):
  45         for b in _do_postorder(x.child_node(c)):
  46             yield b
  47     yield x.bucket
  48
  49 def _do_inorder(x):
  50     assert x.k == 2
  51     if x.level > 2:
  52         return
  53     for b in _do_inorder(x.child_node(0)):
  54         yield b
  55     yield x.bucket
  56     for b in _do_inorder(x.child_node(1)):
  57         yield b
  58
  59 class TestVirtualHeapNode(unittest2.TestCase):
  60
  61     def test_init(self):
  62         for k in _test_bases:
  63             vh = VirtualHeap(k)
  64             node = vh.Node(0)
  65             self.assertEqual(node.k, k)
  66             self.assertEqual(node.bucket, 0)
  67             self.assertEqual(node.level, 0)
  68             for b in xrange(1, k+1):
  69                 node = vh.Node(b)
  70                 self.assertEqual(node.k, k)
  71                 self.assertEqual(node.bucket, b)
  72                 self.assertEqual(node.level, 1)
  73
  74     def test_level(self):
  75         Node = VirtualHeap(2).Node
  76         self.assertEqual(Node(0).level, 0)
  77         self.assertEqual(Node(1).level, 1)
  78         self.assertEqual(Node(2).level, 1)
  79         self.assertEqual(Node(3).level, 2)
  80         self.assertEqual(Node(4).level, 2)
  81         self.assertEqual(Node(5).level, 2)
  82         self.assertEqual(Node(6).level, 2)
  83         self.assertEqual(Node(7).level, 3)
  84
  85         Node = VirtualHeap(3).Node
  86         self.assertEqual(Node(0).level, 0)
  87         self.assertEqual(Node(1).level, 1)
  88         self.assertEqual(Node(2).level, 1)
  89         self.assertEqual(Node(3).level, 1)
  90         self.assertEqual(Node(4).level, 2)
  91         self.assertEqual(Node(5).level, 2)
  92         self.assertEqual(Node(6).level, 2)
  93         self.assertEqual(Node(7).level, 2)
  94         self.assertEqual(Node(8).level, 2)
  95         self.assertEqual(Node(9).level, 2)
  96         self.assertEqual(Node(10).level, 2)
  97         self.assertEqual(Node(11).level, 2)
  98         self.assertEqual(Node(12).level, 2)
  99         self.assertEqual(Node(13).level, 3)
 100
 101     def test_hash(self):
 102         x1 = VirtualHeap(3).Node(5)
 103         x2 = VirtualHeap(2).Node(5)
 104         self.assertNotEqual(id(x1), id(x2))
 105         self.assertEqual(x1, x2)
 106         self.assertEqual(x1, x1)
 107         self.assertEqual(x2, x2)
 108
 109         all_node_set = set()
 110         all_node_list = list()
 111         for k in _test_bases:
 112             node_set = set()
 113             node_list = list()
 114             Node = VirtualHeap(k).Node
 115             for height in xrange(k+2):
 116                 node = Node(height)
 117                 node_set.add(node)
 118                 all_node_set.add(node)
 119                 node_list.append(node)
 120                 all_node_list.append(node)
 121             self.assertEqual(sorted(node_set),
 122                              sorted(node_list))
 123         self.assertNotEqual(sorted(all_node_set),
 124                             sorted(all_node_list))
 125     def test_int(self):
 126         Node2 = VirtualHeap(2).Node
 127         Node3 = VirtualHeap(3).Node
 128         for b in range(100):
 129             self.assertEqual(int(Node2(b)), b)
 130             self.assertEqual(int(Node3(b)), b)
 131
 132     def test_lt(self):
 133         Node = VirtualHeap(3).Node
 134         self.assertEqual(Node(5) < 4, False)
 135         self.assertEqual(Node(5) < 5, False)
 136         self.assertEqual(Node(5) < 6, True)
 137
 138     def test_le(self):
 139         Node = VirtualHeap(3).Node
 140         self.assertEqual(Node(5) <= 4, False)
 141         self.assertEqual(Node(5) <= 5, True)
 142         self.assertEqual(Node(5) <= 6, True)
 143
 144     def test_eq(self):
 145         Node = VirtualHeap(3).Node
 146         self.assertEqual(Node(5) == 4, False)
 147         self.assertEqual(Node(5) == 5, True)
 148         self.assertEqual(Node(5) == 6, False)
 149
 150     def test_ne(self):
 151         Node = VirtualHeap(3).Node
 152         self.assertEqual(Node(5) != 4, True)
 153         self.assertEqual(Node(5) != 5, False)
 154         self.assertEqual(Node(5) != 6, True)
 155
 156     def test_gt(self):
 157         Node = VirtualHeap(3).Node
 158         self.assertEqual(Node(5) > 4, True)
 159         self.assertEqual(Node(5) > 5, False)
 160         self.assertEqual(Node(5) > 6, False)
 161
 162     def test_ge(self):
 163         Node = VirtualHeap(3).Node
 164         self.assertEqual(Node(5) >= 4, True)
 165         self.assertEqual(Node(5) >= 5, True)
 166         self.assertEqual(Node(5) >= 6, False)
 167
 168     def test_last_common_level_k2(self):
 169         Node = VirtualHeap(2).Node
 170         n0 = Node(0)
 171         n1 = Node(1)
 172         n2 = Node(2)
 173         n3 = Node(3)
 174         n4 = Node(4)
 175         n5 = Node(5)
 176         n6 = Node(6)
 177         n7 = Node(7)
 178         self.assertEqual(n0.last_common_level(n0), 0)
 179         self.assertEqual(n0.last_common_level(n1), 0)
 180         self.assertEqual(n0.last_common_level(n2), 0)
 181         self.assertEqual(n0.last_common_level(n3), 0)
 182         self.assertEqual(n0.last_common_level(n4), 0)
 183         self.assertEqual(n0.last_common_level(n5), 0)
 184         self.assertEqual(n0.last_common_level(n6), 0)
 185         self.assertEqual(n0.last_common_level(n7), 0)
 186
 187         self.assertEqual(n1.last_common_level(n0), 0)
 188         self.assertEqual(n1.last_common_level(n1), 1)
 189         self.assertEqual(n1.last_common_level(n2), 0)
 190         self.assertEqual(n1.last_common_level(n3), 1)
 191         self.assertEqual(n1.last_common_level(n4), 1)
 192         self.assertEqual(n1.last_common_level(n5), 0)
 193         self.assertEqual(n1.last_common_level(n6), 0)
 194         self.assertEqual(n1.last_common_level(n7), 1)
 195
 196         self.assertEqual(n2.last_common_level(n0), 0)
 197         self.assertEqual(n2.last_common_level(n1), 0)
 198         self.assertEqual(n2.last_common_level(n2), 1)
 199         self.assertEqual(n2.last_common_level(n3), 0)
 200         self.assertEqual(n2.last_common_level(n4), 0)
 201         self.assertEqual(n2.last_common_level(n5), 1)
 202         self.assertEqual(n2.last_common_level(n6), 1)
 203         self.assertEqual(n2.last_common_level(n7), 0)
 204
 205         self.assertEqual(n3.last_common_level(n0), 0)
 206         self.assertEqual(n3.last_common_level(n1), 1)
 207         self.assertEqual(n3.last_common_level(n2), 0)
 208         self.assertEqual(n3.last_common_level(n3), 2)
 209         self.assertEqual(n3.last_common_level(n4), 1)
 210         self.assertEqual(n3.last_common_level(n5), 0)
 211         self.assertEqual(n3.last_common_level(n6), 0)
 212         self.assertEqual(n3.last_common_level(n7), 2)
 213
 214         self.assertEqual(n4.last_common_level(n0), 0)
 215         self.assertEqual(n4.last_common_level(n1), 1)
 216         self.assertEqual(n4.last_common_level(n2), 0)
 217         self.assertEqual(n4.last_common_level(n3), 1)
 218         self.assertEqual(n4.last_common_level(n4), 2)
 219         self.assertEqual(n4.last_common_level(n5), 0)
 220         self.assertEqual(n4.last_common_level(n6), 0)
 221         self.assertEqual(n4.last_common_level(n7), 1)
 222
 223         self.assertEqual(n5.last_common_level(n0), 0)
 224         self.assertEqual(n5.last_common_level(n1), 0)
 225         self.assertEqual(n5.last_common_level(n2), 1)
 226         self.assertEqual(n5.last_common_level(n3), 0)
 227         self.assertEqual(n5.last_common_level(n4), 0)
 228         self.assertEqual(n5.last_common_level(n5), 2)
 229         self.assertEqual(n5.last_common_level(n6), 1)
 230         self.assertEqual(n5.last_common_level(n7), 0)
 231
 232         self.assertEqual(n6.last_common_level(n0), 0)
 233         self.assertEqual(n6.last_common_level(n1), 0)
 234         self.assertEqual(n6.last_common_level(n2), 1)
 235         self.assertEqual(n6.last_common_level(n3), 0)
 236         self.assertEqual(n6.last_common_level(n4), 0)
 237         self.assertEqual(n6.last_common_level(n5), 1)
 238         self.assertEqual(n6.last_common_level(n6), 2)
 239         self.assertEqual(n6.last_common_level(n7), 0)
 240
 241         self.assertEqual(n7.last_common_level(n0), 0)
 242         self.assertEqual(n7.last_common_level(n1), 1)
 243         self.assertEqual(n7.last_common_level(n2), 0)
 244         self.assertEqual(n7.last_common_level(n3), 2)
 245         self.assertEqual(n7.last_common_level(n4), 1)
 246         self.assertEqual(n7.last_common_level(n5), 0)
 247         self.assertEqual(n7.last_common_level(n6), 0)
 248         self.assertEqual(n7.last_common_level(n7), 3)
 249
 250     def test_last_common_level_k3(self):
 251         Node = VirtualHeap(3).Node
 252         n0 = Node(0)
 253         n1 = Node(1)
 254         n2 = Node(2)
 255         n3 = Node(3)
 256         n4 = Node(4)
 257         n5 = Node(5)
 258         n6 = Node(6)
 259         n7 = Node(7)
 260         self.assertEqual(n0.last_common_level(n0), 0)
 261         self.assertEqual(n0.last_common_level(n1), 0)
 262         self.assertEqual(n0.last_common_level(n2), 0)
 263         self.assertEqual(n0.last_common_level(n3), 0)
 264         self.assertEqual(n0.last_common_level(n4), 0)
 265         self.assertEqual(n0.last_common_level(n5), 0)
 266         self.assertEqual(n0.last_common_level(n6), 0)
 267         self.assertEqual(n0.last_common_level(n7), 0)
 268
 269         self.assertEqual(n1.last_common_level(n0), 0)
 270         self.assertEqual(n1.last_common_level(n1), 1)
 271         self.assertEqual(n1.last_common_level(n2), 0)
 272         self.assertEqual(n1.last_common_level(n3), 0)
 273         self.assertEqual(n1.last_common_level(n4), 1)
 274         self.assertEqual(n1.last_common_level(n5), 1)
 275         self.assertEqual(n1.last_common_level(n6), 1)
 276         self.assertEqual(n1.last_common_level(n7), 0)
 277
 278         self.assertEqual(n2.last_common_level(n0), 0)
 279         self.assertEqual(n2.last_common_level(n1), 0)
 280         self.assertEqual(n2.last_common_level(n2), 1)
 281         self.assertEqual(n2.last_common_level(n3), 0)
 282         self.assertEqual(n2.last_common_level(n4), 0)
 283         self.assertEqual(n2.last_common_level(n5), 0)
 284         self.assertEqual(n2.last_common_level(n6), 0)
 285         self.assertEqual(n2.last_common_level(n7), 1)
 286
 287         self.assertEqual(n3.last_common_level(n0), 0)
 288         self.assertEqual(n3.last_common_level(n1), 0)
 289         self.assertEqual(n3.last_common_level(n2), 0)
 290         self.assertEqual(n3.last_common_level(n3), 1)
 291         self.assertEqual(n3.last_common_level(n4), 0)
 292         self.assertEqual(n3.last_common_level(n5), 0)
 293         self.assertEqual(n3.last_common_level(n6), 0)
 294         self.assertEqual(n3.last_common_level(n7), 0)
 295
 296         self.assertEqual(n4.last_common_level(n0), 0)
 297         self.assertEqual(n4.last_common_level(n1), 1)
 298         self.assertEqual(n4.last_common_level(n2), 0)
 299         self.assertEqual(n4.last_common_level(n3), 0)
 300         self.assertEqual(n4.last_common_level(n4), 2)
 301         self.assertEqual(n4.last_common_level(n5), 1)
 302         self.assertEqual(n4.last_common_level(n6), 1)
 303         self.assertEqual(n4.last_common_level(n7), 0)
 304
 305         self.assertEqual(n5.last_common_level(n0), 0)
 306         self.assertEqual(n5.last_common_level(n1), 1)
 307         self.assertEqual(n5.last_common_level(n2), 0)
 308         self.assertEqual(n5.last_common_level(n3), 0)
 309         self.assertEqual(n5.last_common_level(n4), 1)
 310         self.assertEqual(n5.last_common_level(n5), 2)
 311         self.assertEqual(n5.last_common_level(n6), 1)
 312         self.assertEqual(n5.last_common_level(n7), 0)
 313
 314         self.assertEqual(n6.last_common_level(n0), 0)
 315         self.assertEqual(n6.last_common_level(n1), 1)
 316         self.assertEqual(n6.last_common_level(n2), 0)
 317         self.assertEqual(n6.last_common_level(n3), 0)
 318         self.assertEqual(n6.last_common_level(n4), 1)
 319         self.assertEqual(n6.last_common_level(n5), 1)
 320         self.assertEqual(n6.last_common_level(n6), 2)
 321         self.assertEqual(n6.last_common_level(n7), 0)
 322
 323         self.assertEqual(n7.last_common_level(n0), 0)
 324         self.assertEqual(n7.last_common_level(n1), 0)
 325         self.assertEqual(n7.last_common_level(n2), 1)
 326         self.assertEqual(n7.last_common_level(n3), 0)
 327         self.assertEqual(n7.last_common_level(n4), 0)
 328         self.assertEqual(n7.last_common_level(n5), 0)
 329         self.assertEqual(n7.last_common_level(n6), 0)
 330         self.assertEqual(n7.last_common_level(n7), 2)
 331
 332     def test_child_node(self):
 333         root = VirtualHeap(2).Node(0)
 334         self.assertEqual(list(_do_preorder(root)),
 335                          [0, 1, 3, 4, 2, 5, 6])
 336         self.assertEqual(list(_do_postorder(root)),
 337                          [3, 4, 1, 5, 6, 2, 0])
 338         self.assertEqual(list(_do_inorder(root)),
 339                          [3, 1, 4, 0, 5, 2, 6])
 340
 341         root = VirtualHeap(3).Node(0)
 342         self.assertEqual(
 343             list(_do_preorder(root)),
 344             [0, 1, 4, 5, 6, 2, 7, 8, 9, 3, 10, 11, 12])
 345         self.assertEqual(
 346             list(_do_postorder(root)),
 347             [4, 5, 6, 1, 7, 8, 9, 2, 10, 11, 12, 3, 0])
 348
 349     def test_parent_node(self):
 350         Node = VirtualHeap(2).Node
 351         self.assertEqual(Node(0).parent_node(),
 352                          None)
 353         self.assertEqual(Node(1).parent_node(),
 354                          Node(0))
 355         self.assertEqual(Node(2).parent_node(),
 356                          Node(0))
 357         self.assertEqual(Node(3).parent_node(),
 358                          Node(1))
 359         self.assertEqual(Node(4).parent_node(),
 360                          Node(1))
 361         self.assertEqual(Node(5).parent_node(),
 362                          Node(2))
 363         self.assertEqual(Node(6).parent_node(),
 364                          Node(2))
 365         self.assertEqual(Node(7).parent_node(),
 366                          Node(3))
 367
 368         Node = VirtualHeap(3).Node
 369         self.assertEqual(Node(0).parent_node(),
 370                          None)
 371         self.assertEqual(Node(1).parent_node(),
 372                          Node(0))
 373         self.assertEqual(Node(2).parent_node(),
 374                          Node(0))
 375         self.assertEqual(Node(3).parent_node(),
 376                          Node(0))
 377         self.assertEqual(Node(4).parent_node(),
 378                          Node(1))
 379         self.assertEqual(Node(5).parent_node(),
 380                          Node(1))
 381         self.assertEqual(Node(6).parent_node(),
 382                          Node(1))
 383         self.assertEqual(Node(7).parent_node(),
 384                          Node(2))
 385         self.assertEqual(Node(8).parent_node(),
 386                          Node(2))
 387         self.assertEqual(Node(9).parent_node(),
 388                          Node(2))
 389         self.assertEqual(Node(10).parent_node(),
 390                          Node(3))
 391         self.assertEqual(Node(11).parent_node(),
 392                          Node(3))
 393         self.assertEqual(Node(12).parent_node(),
 394                          Node(3))
 395         self.assertEqual(Node(13).parent_node(),
 396                          Node(4))
 397
 398     def test_ancestor_node_at_level(self):
 399         Node = VirtualHeap(2).Node
 400         self.assertEqual(Node(0).ancestor_node_at_level(0),
 401                          Node(0))
 402         self.assertEqual(Node(0).ancestor_node_at_level(1),
 403                          None)
 404         self.assertEqual(Node(1).ancestor_node_at_level(0),
 405                          Node(0))
 406         self.assertEqual(Node(1).ancestor_node_at_level(1),
 407                          Node(1))
 408         self.assertEqual(Node(1).ancestor_node_at_level(2),
 409                          None)
 410         self.assertEqual(Node(3).ancestor_node_at_level(0),
 411                          Node(0))
 412         self.assertEqual(Node(3).ancestor_node_at_level(1),
 413                          Node(1))
 414         self.assertEqual(Node(3).ancestor_node_at_level(2),
 415                          Node(3))
 416         self.assertEqual(Node(3).ancestor_node_at_level(3),
 417                          None)
 418
 419         Node = VirtualHeap(3).Node
 420         self.assertEqual(Node(0).ancestor_node_at_level(0),
 421                          Node(0))
 422         self.assertEqual(Node(0).ancestor_node_at_level(1),
 423                          None)
 424         self.assertEqual(Node(1).ancestor_node_at_level(0),
 425                          Node(0))
 426         self.assertEqual(Node(1).ancestor_node_at_level(1),
 427                          Node(1))
 428         self.assertEqual(Node(1).ancestor_node_at_level(2),
 429                          None)
 430         self.assertEqual(Node(4).ancestor_node_at_level(0),
 431                          Node(0))
 432         self.assertEqual(Node(4).ancestor_node_at_level(1),
 433                          Node(1))
 434         self.assertEqual(Node(4).ancestor_node_at_level(2),
 435                          Node(4))
 436         self.assertEqual(Node(4).ancestor_node_at_level(3),
 437                          None)
 438
 439     def test_path_to_root(self):
 440         Node = VirtualHeap(2).Node
 441         self.assertEqual(list(int(n) for n in Node(0).bucket_path_to_root()),
 442                          list(reversed([0])))
 443         self.assertEqual(list(int(n) for n in Node(7).bucket_path_to_root()),
 444                          list(reversed([0, 1, 3, 7])))
 445         self.assertEqual(list(int(n) for n in Node(8).bucket_path_to_root()),
 446                          list(reversed([0, 1, 3, 8])))
 447         self.assertEqual(list(int(n) for n in Node(9).bucket_path_to_root()),
 448                          list(reversed([0, 1, 4, 9])))
 449         self.assertEqual(list(int(n) for n in Node(10).bucket_path_to_root()),
 450                          list(reversed([0, 1, 4, 10])))
 451         self.assertEqual(list(int(n) for n in Node(11).bucket_path_to_root()),
 452                          list(reversed([0, 2, 5, 11])))
 453         self.assertEqual(list(int(n) for n in Node(12).bucket_path_to_root()),
 454                          list(reversed([0, 2, 5, 12])))
 455         self.assertEqual(list(int(n) for n in Node(13).bucket_path_to_root()),
 456                          list(reversed([0, 2, 6, 13])))
 457         self.assertEqual(list(int(n) for n in Node(14).bucket_path_to_root()),
 458                          list(reversed([0, 2, 6, 14])))
 459
 460     def test_path_from_root(self):
 461         Node = VirtualHeap(2).Node
 462         self.assertEqual(list(int(n) for n in Node(0).bucket_path_from_root()),
 463                          [0])
 464         self.assertEqual(list(int(n) for n in Node(7).bucket_path_from_root()),
 465                          [0, 1, 3, 7])
 466         self.assertEqual(list(int(n) for n in Node(8).bucket_path_from_root()),
 467                          [0, 1, 3, 8])
 468         self.assertEqual(list(int(n) for n in Node(9).bucket_path_from_root()),
 469                          [0, 1, 4, 9])
 470         self.assertEqual(list(int(n) for n in Node(10).bucket_path_from_root()),
 471                          [0, 1, 4, 10])
 472         self.assertEqual(list(int(n) for n in Node(11).bucket_path_from_root()),
 473                          [0, 2, 5, 11])
 474         self.assertEqual(list(int(n) for n in Node(12).bucket_path_from_root()),
 475                          [0, 2, 5, 12])
 476         self.assertEqual(list(int(n) for n in Node(13).bucket_path_from_root()),
 477                          [0, 2, 6, 13])
 478         self.assertEqual(list(int(n) for n in Node(14).bucket_path_from_root()),
 479                          [0, 2, 6, 14])
 480
 481     def test_bucket_path_to_root(self):
 482         Node = VirtualHeap(2).Node
 483         self.assertEqual(list(Node(0).bucket_path_to_root()),
 484                          list(reversed([0])))
 485         self.assertEqual(list(Node(7).bucket_path_to_root()),
 486                          list(reversed([0, 1, 3, 7])))
 487         self.assertEqual(list(Node(8).bucket_path_to_root()),
 488                          list(reversed([0, 1, 3, 8])))
 489         self.assertEqual(list(Node(9).bucket_path_to_root()),
 490                          list(reversed([0, 1, 4, 9])))
 491         self.assertEqual(list(Node(10).bucket_path_to_root()),
 492                          list(reversed([0, 1, 4, 10])))
 493         self.assertEqual(list(Node(11).bucket_path_to_root()),
 494                          list(reversed([0, 2, 5, 11])))
 495         self.assertEqual(list(Node(12).bucket_path_to_root()),
 496                          list(reversed([0, 2, 5, 12])))
 497         self.assertEqual(list(Node(13).bucket_path_to_root()),
 498                          list(reversed([0, 2, 6, 13])))
 499         self.assertEqual(list(Node(14).bucket_path_to_root()),
 500                          list(reversed([0, 2, 6, 14])))
 501
 502     def test_bucket_path_from_root(self):
 503         Node = VirtualHeap(2).Node
 504         self.assertEqual(Node(0).bucket_path_from_root(),
 505                          [0])
 506         self.assertEqual(Node(7).bucket_path_from_root(),
 507                          [0, 1, 3, 7])
 508         self.assertEqual(Node(8).bucket_path_from_root(),
 509                          [0, 1, 3, 8])
 510         self.assertEqual(Node(9).bucket_path_from_root(),
 511                          [0, 1, 4, 9])
 512         self.assertEqual(Node(10).bucket_path_from_root(),
 513                          [0, 1, 4, 10])
 514         self.assertEqual(Node(11).bucket_path_from_root(),
 515                          [0, 2, 5, 11])
 516         self.assertEqual(Node(12).bucket_path_from_root(),
 517                          [0, 2, 5, 12])
 518         self.assertEqual(Node(13).bucket_path_from_root(),
 519                          [0, 2, 6, 13])
 520         self.assertEqual(Node(14).bucket_path_from_root(),
 521                          [0, 2, 6, 14])
 522
 523     def test_repr(self):
 524         Node = VirtualHeap(2).Node
 525         self.assertEqual(
 526             repr(Node(0)),
 527             "VirtualHeapNode(k=2, bucket=0, level=0, label='')")
 528         self.assertEqual(
 529             repr(Node(7)),
 530             "VirtualHeapNode(k=2, bucket=7, level=3, label='000')")
 531
 532         Node = VirtualHeap(3).Node
 533         self.assertEqual(
 534             repr(Node(0)),
 535             "VirtualHeapNode(k=3, bucket=0, level=0, label='')")
 536         self.assertEqual(
 537             repr(Node(7)),
 538             "VirtualHeapNode(k=3, bucket=7, level=2, label='10')")
 539
 540         Node = VirtualHeap(5).Node
 541         self.assertEqual(
 542             repr(Node(25)),
 543             "VirtualHeapNode(k=5, bucket=25, level=2, label='34')")
 544
 545         Node = VirtualHeap(max_k_labeled).Node
 546         self.assertEqual(
 547             repr(Node(0)),
 548             ("VirtualHeapNode(k=%d, bucket=0, level=0, label='')"
 549              % (max_k_labeled)))
 550         self.assertEqual(max_k_labeled >= 2, True)
 551         self.assertEqual(
 552             repr(Node(1)),
 553             ("VirtualHeapNode(k=%d, bucket=1, level=1, label='0')"
 554              % (max_k_labeled)))
 555
 556         Node = VirtualHeap(max_k_labeled+1).Node
 557         self.assertEqual(
 558             repr(Node(0)),
 559             ("VirtualHeapNode(k=%d, bucket=0, level=0, label='')"
 560              % (max_k_labeled+1)))
 561         self.assertEqual(
 562             repr(Node(1)),
 563             ("VirtualHeapNode(k=%d, bucket=1, level=1, label='<unknown>')"
 564              % (max_k_labeled+1)))
 565         self.assertEqual(
 566             repr(Node(max_k_labeled+1)),
 567             ("VirtualHeapNode(k=%d, bucket=%d, level=1, label='<unknown>')"
 568              % (max_k_labeled+1,
 569                 max_k_labeled+1)))
 570         self.assertEqual(
 571             repr(Node(max_k_labeled+2)),
 572             ("VirtualHeapNode(k=%d, bucket=%d, level=2, label='<unknown>')"
 573              % (max_k_labeled+1,
 574                 max_k_labeled+2)))
 575
 576     def test_str(self):
 577         Node = VirtualHeap(2).Node
 578         self.assertEqual(
 579             str(Node(0)),
 580             "(0, 0)")
 581         self.assertEqual(
 582             str(Node(7)),
 583             "(3, 0)")
 584
 585         Node = VirtualHeap(3).Node
 586         self.assertEqual(
 587             str(Node(0)),
 588             "(0, 0)")
 589         self.assertEqual(
 590             str(Node(7)),
 591             "(2, 3)")
 592
 593         Node = VirtualHeap(5).Node
 594         self.assertEqual(
 595             str(Node(25)),
 596             "(2, 19)")
 597
 598     def test_label(self):
 599
 600         Node = VirtualHeap(2).Node
 601         self.assertEqual(Node(0).label(), "")
 602         self.assertEqual(Node(1).label(), "0")
 603         self.assertEqual(Node(2).label(), "1")
 604         self.assertEqual(Node(3).label(), "00")
 605         self.assertEqual(Node(4).label(), "01")
 606         self.assertEqual(Node(5).label(), "10")
 607         self.assertEqual(Node(6).label(), "11")
 608         self.assertEqual(Node(7).label(), "000")
 609         self.assertEqual(Node(8).label(), "001")
 610         self.assertEqual(Node(9).label(), "010")
 611         self.assertEqual(Node(10).label(), "011")
 612         self.assertEqual(Node(11).label(), "100")
 613         self.assertEqual(Node(12).label(), "101")
 614         self.assertEqual(Node(13).label(), "110")
 615         self.assertEqual(Node(14).label(), "111")
 616         self.assertEqual(Node(15).label(), "0000")
 617         self.assertEqual(Node(30).label(), "1111")
 618
 619         for k in _test_labeled_bases:
 620             Node = VirtualHeap(k).Node
 621             for b in xrange(calculate_bucket_count_in_heap_with_height(k, 2)+1):
 622                 label = Node(b).label()
 623                 level = Node(b).level
 624                 if label == "":
 625                     self.assertEqual(b, 0)
 626                 else:
 627                     self.assertEqual(
 628                         b,
 629                         basek_string_to_base10_integer(k, label) + \
 630                         calculate_bucket_count_in_heap_with_height(k, level-1))
 631
 632     def test_is_node_on_path(self):
 633         Node = VirtualHeap(2).Node
 634         self.assertEqual(
 635             Node(0).is_node_on_path(
 636                 Node(0)),
 637             True)
 638         self.assertEqual(
 639             Node(0).is_node_on_path(
 640                 Node(1)),
 641             False)
 642         self.assertEqual(
 643             Node(0).is_node_on_path(
 644                 Node(2)),
 645             False)
 646         self.assertEqual(
 647             Node(0).is_node_on_path(
 648                 Node(3)),
 649             False)
 650
 651         Node = VirtualHeap(5).Node
 652         self.assertEqual(
 653             Node(20).is_node_on_path(
 654                 Node(21)),
 655             False)
 656         self.assertEqual(
 657             Node(21).is_node_on_path(
 658                 Node(4)),
 659             True)
 660
 661         Node = VirtualHeap(3).Node
 662         self.assertEqual(
 663             Node(7).is_node_on_path(
 664                 Node(0)),
 665             True)
 666         self.assertEqual(
 667             Node(7).is_node_on_path(
 668                 Node(2)),
 669             True)
 670         self.assertEqual(
 671             Node(7).is_node_on_path(
 672                 Node(7)),
 673             True)
 674         self.assertEqual(
 675             Node(7).is_node_on_path(
 676                 Node(8)),
 677             False)
 678
 679 class TestVirtualHeap(unittest2.TestCase):
 680
 681     def test_init(self):
 682         vh = VirtualHeap(2, blocks_per_bucket=4)
 683         self.assertEqual(vh.k, 2)
 684         self.assertEqual(vh.Node.k, 2)
 685         self.assertEqual(vh.blocks_per_bucket, 4)
 686         vh = VirtualHeap(5, blocks_per_bucket=7)
 687         self.assertEqual(vh.k, 5)
 688         self.assertEqual(vh.Node.k, 5)
 689         self.assertEqual(vh.blocks_per_bucket, 7)
 690
 691     def test_node_label_to_bucket(self):
 692         vh = VirtualHeap(2)
 693         self.assertEqual(vh.node_label_to_bucket(""), 0)
 694         self.assertEqual(vh.node_label_to_bucket("0"), 1)
 695         self.assertEqual(vh.node_label_to_bucket("1"), 2)
 696         self.assertEqual(vh.node_label_to_bucket("00"), 3)
 697         self.assertEqual(vh.node_label_to_bucket("01"), 4)
 698         self.assertEqual(vh.node_label_to_bucket("10"), 5)
 699         self.assertEqual(vh.node_label_to_bucket("11"), 6)
 700         self.assertEqual(vh.node_label_to_bucket("000"), 7)
 701         self.assertEqual(vh.node_label_to_bucket("001"), 8)
 702         self.assertEqual(vh.node_label_to_bucket("010"), 9)
 703         self.assertEqual(vh.node_label_to_bucket("011"), 10)
 704         self.assertEqual(vh.node_label_to_bucket("100"), 11)
 705         self.assertEqual(vh.node_label_to_bucket("101"), 12)
 706         self.assertEqual(vh.node_label_to_bucket("110"), 13)
 707         self.assertEqual(vh.node_label_to_bucket("111"), 14)
 708         self.assertEqual(vh.node_label_to_bucket("0000"), 15)
 709         self.assertEqual(vh.node_label_to_bucket("1111"),
 710                          calculate_bucket_count_in_heap_with_height(2, 4)-1)
 711
 712         vh = VirtualHeap(3)
 713         self.assertEqual(vh.node_label_to_bucket(""), 0)
 714         self.assertEqual(vh.node_label_to_bucket("0"), 1)
 715         self.assertEqual(vh.node_label_to_bucket("1"), 2)
 716         self.assertEqual(vh.node_label_to_bucket("2"), 3)
 717         self.assertEqual(vh.node_label_to_bucket("00"), 4)
 718         self.assertEqual(vh.node_label_to_bucket("01"), 5)
 719         self.assertEqual(vh.node_label_to_bucket("02"), 6)
 720         self.assertEqual(vh.node_label_to_bucket("10"), 7)
 721         self.assertEqual(vh.node_label_to_bucket("11"), 8)
 722         self.assertEqual(vh.node_label_to_bucket("12"), 9)
 723         self.assertEqual(vh.node_label_to_bucket("20"), 10)
 724         self.assertEqual(vh.node_label_to_bucket("21"), 11)
 725         self.assertEqual(vh.node_label_to_bucket("22"), 12)
 726         self.assertEqual(vh.node_label_to_bucket("000"), 13)
 727         self.assertEqual(vh.node_label_to_bucket("222"),
 728                          calculate_bucket_count_in_heap_with_height(3, 3)-1)
 729
 730         for k in xrange(2, max_k_labeled+1):
 731             for h in xrange(5):
 732                 vh = VirtualHeap(k)
 733                 largest_symbol = numerals[k-1]
 734                 self.assertEqual(vh.k, k)
 735                 self.assertEqual(vh.node_label_to_bucket(""), 0)
 736                 self.assertEqual(vh.node_label_to_bucket(largest_symbol * h),
 737                                  calculate_bucket_count_in_heap_with_height(k, h)-1)
 738
 739     def test_ObjectCountAtLevel(self):
 740         for k in _test_bases:
 741             for height in xrange(k+2):
 742                 for blocks_per_bucket in xrange(1, 5):
 743                     vh = VirtualHeap(k, blocks_per_bucket=blocks_per_bucket)
 744                     for l in xrange(height+1):
 745                         cnt = k**l
 746                         self.assertEqual(vh.bucket_count_at_level(l), cnt)
 747                         self.assertEqual(vh.node_count_at_level(l), cnt)
 748                         self.assertEqual(vh.block_count_at_level(l),
 749                                          cnt * blocks_per_bucket)
 750
 751     def test_bucket_to_block(self):
 752         for k in xrange(2, 6):
 753             for blocks_per_bucket in xrange(1, 5):
 754                 heap = VirtualHeap(k, blocks_per_bucket=blocks_per_bucket)
 755                 for b in xrange(20):
 756                     self.assertEqual(heap.bucket_to_block(b),
 757                                      blocks_per_bucket * b)
 758
 759     def test_node_count_at_level(self):
 760         self.assertEqual(VirtualHeap(2).node_count_at_level(0), 1)
 761         self.assertEqual(VirtualHeap(2).node_count_at_level(1), 2)
 762         self.assertEqual(VirtualHeap(2).node_count_at_level(2), 4)
 763         self.assertEqual(VirtualHeap(2).node_count_at_level(3), 8)
 764         self.assertEqual(VirtualHeap(2).node_count_at_level(4), 16)
 765
 766         self.assertEqual(VirtualHeap(3).node_count_at_level(0), 1)
 767         self.assertEqual(VirtualHeap(3).node_count_at_level(1), 3)
 768         self.assertEqual(VirtualHeap(3).node_count_at_level(2), 9)
 769         self.assertEqual(VirtualHeap(3).node_count_at_level(3), 27)
 770         self.assertEqual(VirtualHeap(3).node_count_at_level(4), 81)
 771
 772         self.assertEqual(VirtualHeap(4).node_count_at_level(0), 1)
 773         self.assertEqual(VirtualHeap(4).node_count_at_level(1), 4)
 774         self.assertEqual(VirtualHeap(4).node_count_at_level(2), 16)
 775         self.assertEqual(VirtualHeap(4).node_count_at_level(3), 64)
 776         self.assertEqual(VirtualHeap(4).node_count_at_level(4), 256)
 777
 778     def test_first_node_at_level(self):
 779         self.assertEqual(VirtualHeap(2).first_node_at_level(0), 0)
 780         self.assertEqual(VirtualHeap(2).first_node_at_level(1), 1)
 781         self.assertEqual(VirtualHeap(2).first_node_at_level(2), 3)
 782         self.assertEqual(VirtualHeap(2).first_node_at_level(3), 7)
 783         self.assertEqual(VirtualHeap(2).first_node_at_level(4), 15)
 784
 785         self.assertEqual(VirtualHeap(3).first_node_at_level(0), 0)
 786         self.assertEqual(VirtualHeap(3).first_node_at_level(1), 1)
 787         self.assertEqual(VirtualHeap(3).first_node_at_level(2), 4)
 788         self.assertEqual(VirtualHeap(3).first_node_at_level(3), 13)
 789         self.assertEqual(VirtualHeap(3).first_node_at_level(4), 40)
 790
 791         self.assertEqual(VirtualHeap(4).first_node_at_level(0), 0)
 792         self.assertEqual(VirtualHeap(4).first_node_at_level(1), 1)
 793         self.assertEqual(VirtualHeap(4).first_node_at_level(2), 5)
 794         self.assertEqual(VirtualHeap(4).first_node_at_level(3), 21)
 795         self.assertEqual(VirtualHeap(4).first_node_at_level(4), 85)
 796
 797     def test_last_node_at_level(self):
 798         self.assertEqual(VirtualHeap(2).last_node_at_level(0), 0)
 799         self.assertEqual(VirtualHeap(2).last_node_at_level(1), 2)
 800         self.assertEqual(VirtualHeap(2).last_node_at_level(2), 6)
 801         self.assertEqual(VirtualHeap(2).last_node_at_level(3), 14)
 802         self.assertEqual(VirtualHeap(2).last_node_at_level(4), 30)
 803
 804         self.assertEqual(VirtualHeap(3).last_node_at_level(0), 0)
 805         self.assertEqual(VirtualHeap(3).last_node_at_level(1), 3)
 806         self.assertEqual(VirtualHeap(3).last_node_at_level(2), 12)
 807         self.assertEqual(VirtualHeap(3).last_node_at_level(3), 39)
 808         self.assertEqual(VirtualHeap(3).last_node_at_level(4), 120)
 809
 810         self.assertEqual(VirtualHeap(4).last_node_at_level(0), 0)
 811         self.assertEqual(VirtualHeap(4).last_node_at_level(1), 4)
 812         self.assertEqual(VirtualHeap(4).last_node_at_level(2), 20)
 813         self.assertEqual(VirtualHeap(4).last_node_at_level(3), 84)
 814         self.assertEqual(VirtualHeap(4).last_node_at_level(4), 340)
 815
 816     def test_random_node_up_to_level(self):
 817         for k in xrange(2,6):
 818             heap = VirtualHeap(k)
 819             for l in xrange(4):
 820                 for t in xrange(2 * calculate_bucket_count_in_heap_with_height(k, l)):
 821                     node = heap.random_node_up_to_level(l)
 822                     self.assertEqual(node.level <= l, True)
 823
 824     def test_random_node_at_level(self):
 825         for k in xrange(2,6):
 826             heap = VirtualHeap(k)
 827             for l in xrange(4):
 828                 for t in xrange(2 * calculate_bucket_count_in_heap_at_level(k, l)):
 829                     node = heap.random_node_at_level(l)
 830                     self.assertEqual(node.level == l, True)
 831
 832     def test_first_block_at_level(self):
 833         for blocks_per_bucket in xrange(1, 5):
 834             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 835                              first_block_at_level(0), 0 * blocks_per_bucket)
 836             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 837                              first_block_at_level(1), 1 * blocks_per_bucket)
 838             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 839                              first_block_at_level(2), 3 * blocks_per_bucket)
 840             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 841                              first_block_at_level(3), 7 * blocks_per_bucket)
 842             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 843                              first_block_at_level(4), 15 * blocks_per_bucket)
 844
 845             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 846                              first_block_at_level(0), 0 * blocks_per_bucket)
 847             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 848                              first_block_at_level(1), 1 * blocks_per_bucket)
 849             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 850                              first_block_at_level(2), 4 * blocks_per_bucket)
 851             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 852                              first_block_at_level(3), 13 * blocks_per_bucket)
 853             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 854                              first_block_at_level(4), 40 * blocks_per_bucket)
 855
 856             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 857                              first_block_at_level(0), 0 * blocks_per_bucket)
 858             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 859                              first_block_at_level(1), 1 * blocks_per_bucket)
 860             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 861                              first_block_at_level(2), 5 * blocks_per_bucket)
 862             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 863                              first_block_at_level(3), 21 * blocks_per_bucket)
 864             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 865                              first_block_at_level(4), 85 * blocks_per_bucket)
 866
 867     def test_last_block_at_level(self):
 868         for blocks_per_bucket in xrange(1, 5):
 869             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 870                              last_block_at_level(0), 0 * blocks_per_bucket + (blocks_per_bucket-1))
 871             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 872                              last_block_at_level(1), 2 * blocks_per_bucket + (blocks_per_bucket-1))
 873             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 874                              last_block_at_level(2), 6 * blocks_per_bucket + (blocks_per_bucket-1))
 875             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 876                              last_block_at_level(3), 14 * blocks_per_bucket + (blocks_per_bucket-1))
 877             self.assertEqual(VirtualHeap(2, blocks_per_bucket=blocks_per_bucket).\
 878                              last_block_at_level(4), 30 * blocks_per_bucket + (blocks_per_bucket-1))
 879
 880             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 881                              last_block_at_level(0), 0 * blocks_per_bucket + (blocks_per_bucket-1))
 882             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 883                              last_block_at_level(1), 3 * blocks_per_bucket + (blocks_per_bucket-1))
 884             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 885                              last_block_at_level(2), 12 * blocks_per_bucket + (blocks_per_bucket-1))
 886             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 887                              last_block_at_level(3), 39 * blocks_per_bucket + (blocks_per_bucket-1))
 888             self.assertEqual(VirtualHeap(3, blocks_per_bucket=blocks_per_bucket).\
 889                              last_block_at_level(4), 120 * blocks_per_bucket + (blocks_per_bucket-1))
 890
 891             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 892                              last_block_at_level(0), 0 * blocks_per_bucket + (blocks_per_bucket-1))
 893             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 894                              last_block_at_level(1), 4 * blocks_per_bucket + (blocks_per_bucket-1))
 895             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 896                              last_block_at_level(2), 20 * blocks_per_bucket + (blocks_per_bucket-1))
 897             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 898                              last_block_at_level(3), 84 * blocks_per_bucket + (blocks_per_bucket-1))
 899             self.assertEqual(VirtualHeap(4, blocks_per_bucket=blocks_per_bucket).\
 900                              last_block_at_level(4), 340 * blocks_per_bucket + (blocks_per_bucket-1))
 901
 902     def test_block_to_bucket(self):
 903         self.assertEqual(VirtualHeap(2, blocks_per_bucket=1).block_to_bucket(0), 0)
 904         self.assertEqual(VirtualHeap(2, blocks_per_bucket=1).block_to_bucket(1), 1)
 905         self.assertEqual(VirtualHeap(2, blocks_per_bucket=1).block_to_bucket(2), 2)
 906         self.assertEqual(VirtualHeap(2, blocks_per_bucket=1).block_to_bucket(3), 3)
 907         self.assertEqual(VirtualHeap(2, blocks_per_bucket=1).block_to_bucket(4), 4)
 908
 909         self.assertEqual(VirtualHeap(2, blocks_per_bucket=2).block_to_bucket(0), 0)
 910         self.assertEqual(VirtualHeap(2, blocks_per_bucket=2).block_to_bucket(1), 0)
 911         self.assertEqual(VirtualHeap(2, blocks_per_bucket=2).block_to_bucket(2), 1)
 912         self.assertEqual(VirtualHeap(2, blocks_per_bucket=2).block_to_bucket(3), 1)
 913         self.assertEqual(VirtualHeap(2, blocks_per_bucket=2).block_to_bucket(4), 2)
 914
 915         self.assertEqual(VirtualHeap(2, blocks_per_bucket=3).block_to_bucket(0), 0)
 916         self.assertEqual(VirtualHeap(2, blocks_per_bucket=3).block_to_bucket(1), 0)
 917         self.assertEqual(VirtualHeap(2, blocks_per_bucket=3).block_to_bucket(2), 0)
 918         self.assertEqual(VirtualHeap(2, blocks_per_bucket=3).block_to_bucket(3), 1)
 919         self.assertEqual(VirtualHeap(2, blocks_per_bucket=3).block_to_bucket(4), 1)
 920
 921         self.assertEqual(VirtualHeap(2, blocks_per_bucket=4).block_to_bucket(0), 0)
 922         self.assertEqual(VirtualHeap(2, blocks_per_bucket=4).block_to_bucket(1), 0)
 923         self.assertEqual(VirtualHeap(2, blocks_per_bucket=4).block_to_bucket(2), 0)
 924         self.assertEqual(VirtualHeap(2, blocks_per_bucket=4).block_to_bucket(3), 0)
 925         self.assertEqual(VirtualHeap(2, blocks_per_bucket=4).block_to_bucket(4), 1)
 926
 927     def test_root_node(self):
 928         for k in range(2, 6):
 929             for blocks_per_bucket in range(1, 5):
 930                 heap = VirtualHeap(k, blocks_per_bucket=blocks_per_bucket)
 931                 root = heap.root_node()
 932                 self.assertEqual(root, 0)
 933                 self.assertEqual(root.bucket, 0)
 934                 self.assertEqual(root.level, 0)
 935                 self.assertEqual(root.parent_node(), None)
 936
 937 class TestSizedVirtualHeap(unittest2.TestCase):
 938
 939     def test_init(self):
 940         vh = SizedVirtualHeap(2, 8, blocks_per_bucket=4)
 941         self.assertEqual(vh.k, 2)
 942         self.assertEqual(vh.Node.k, 2)
 943         self.assertEqual(vh.blocks_per_bucket, 4)
 944         vh = SizedVirtualHeap(5, 9, blocks_per_bucket=7)
 945         self.assertEqual(vh.k, 5)
 946         self.assertEqual(vh.Node.k, 5)
 947         self.assertEqual(vh.blocks_per_bucket, 7)
 948
 949     def test_height(self):
 950         vh = SizedVirtualHeap(2, 3, blocks_per_bucket=4)
 951         self.assertEqual(vh.height, 3)
 952         vh = SizedVirtualHeap(5, 6, blocks_per_bucket=7)
 953         self.assertEqual(vh.height, 6)
 954
 955     def test_levels(self):
 956         vh = SizedVirtualHeap(2, 3, blocks_per_bucket=4)
 957         self.assertEqual(vh.levels, 4)
 958         vh = SizedVirtualHeap(5, 6, blocks_per_bucket=7)
 959         self.assertEqual(vh.levels, 7)
 960
 961     def test_first_level(self):
 962         vh = SizedVirtualHeap(2, 3, blocks_per_bucket=4)
 963         self.assertEqual(vh.first_level, 0)
 964         vh = SizedVirtualHeap(5, 6, blocks_per_bucket=7)
 965         self.assertEqual(vh.first_level, 0)
 966
 967     def test_last_level(self):
 968         vh = SizedVirtualHeap(2, 3, blocks_per_bucket=4)
 969         self.assertEqual(vh.last_level, 3)
 970         self.assertEqual(vh.last_level, vh.levels-1)
 971         self.assertEqual(vh.last_level, vh.height)
 972         vh = SizedVirtualHeap(5, 6, blocks_per_bucket=7)
 973         self.assertEqual(vh.last_level, 6)
 974         self.assertEqual(vh.last_level, vh.levels-1)
 975         self.assertEqual(vh.last_level, vh.height)
 976
 977     def test_ObjectCount(self):
 978         for k in _test_bases:
 979             for height in xrange(k+2):
 980                 for blocks_per_bucket in xrange(1, 5):
 981                     vh = SizedVirtualHeap(k,
 982                                           height,
 983                                           blocks_per_bucket=blocks_per_bucket)
 984                     cnt = (((k**(height+1))-1)//(k-1))
 985                     self.assertEqual(vh.bucket_count(), cnt)
 986                     self.assertEqual(vh.node_count(), cnt)
 987                     self.assertEqual(vh.block_count(), cnt * blocks_per_bucket)
 988
 989     def test_LeafObjectCount(self):
 990         for k in _test_bases:
 991             for height in xrange(k+2):
 992                 for blocks_per_bucket in xrange(1, 5):
 993                     vh = SizedVirtualHeap(k,
 994                                           height,
 995                                           blocks_per_bucket=blocks_per_bucket)
 996                     self.assertEqual(vh.leaf_bucket_count(),
 997                                      vh.bucket_count_at_level(vh.height))
 998                     self.assertEqual(vh.leaf_node_count(),
 999                                      vh.node_count_at_level(vh.height))
1000                     self.assertEqual(vh.leaf_block_count(),
1001                                      vh.block_count_at_level(vh.height))
1002
1003
1004     def test_FirstLeafObject(self):
1005         vh = SizedVirtualHeap(2, 3, blocks_per_bucket=3)
1006         self.assertEqual(vh.first_leaf_node(), 7)
1007         self.assertEqual(vh.first_leaf_block(), 7*3)
1008
1009     def test_LastLeafObject(self):
1010         vh = SizedVirtualHeap(2, 3, blocks_per_bucket=3)
1011         self.assertEqual(vh.last_leaf_node(), 14)
1012         self.assertEqual(vh.last_leaf_block(), 14*3 + 2)
1013
1014     def test_random_node(self):
1015         for k in xrange(2,6):
1016             height = 3
1017             heap = SizedVirtualHeap(k, height)
1018             for t in xrange(2 * heap.bucket_count()):
1019                 node = heap.random_node()
1020                 self.assertEqual(0 <= node.level <= height, True)
1021
1022     def test_random_leaf_node(self):
1023         for k in xrange(2,6):
1024             height = 3
1025             heap = SizedVirtualHeap(k, height)
1026             for t in xrange(2 * heap.bucket_count()):
1027                 node = heap.random_leaf_node()
1028                 self.assertEqual(node.level, height)
1029
1030     def _assert_file_equals_baselines(self, fname, bname):
1031         with open(fname)as f:
1032             flines = f.readlines()
1033         with open(bname) as f:
1034             blines = f.readlines()
1035         self.assertListEqual(flines, blines)
1036         os.remove(fname)
1037
1038     def test_write_as_dot(self):
1039
1040         for k, h, b, maxl in [(2, 3, 1, None),
1041                               (2, 3, 2, None),
1042                               (3, 3, 1, None),
1043                               (3, 3, 2, None),
1044                               (3, 10, 2, 4),
1045                               (200, 0, 1, None)]:
1046             if maxl is None:
1047                 label = "k%d_h%d_b%d" % (k, h, b)
1048             else:
1049                 label = "k%d_h%d_b%d" % (k, maxl-1, b)
1050             heap = SizedVirtualHeap(k, h, blocks_per_bucket=b)
1051
1052             fname = label+".dot"
1053             with open(os.path.join(thisdir, fname), "w") as f:
1054                 heap.write_as_dot(f, max_levels=maxl)
1055             self._assert_file_equals_baselines(
1056                 os.path.join(thisdir, fname),
1057                 os.path.join(baselinedir, fname))
1058
1059             data = list(range(heap.block_count()))
1060             fname = label+"_data.dot"
1061             with open(os.path.join(thisdir, fname), "w") as f:
1062                 heap.write_as_dot(f, data=data, max_levels=maxl)
1063             self._assert_file_equals_baselines(
1064                 os.path.join(thisdir, fname),
1065                 os.path.join(baselinedir, fname))
1066
1067     def test_save_image_as_pdf(self):
1068
1069         for k, h, b, maxl in [(2, 3, 1, None),
1070                               (2, 3, 2, None),
1071                               (3, 3, 1, None),
1072                               (3, 3, 2, None),
1073                               (3, 10, 2, 4)]:
1074             if maxl is None:
1075                 label = "k%d_h%d_b%d" % (k, h, b)
1076             else:
1077                 label = "k%d_h%d_b%d" % (k, maxl-1, b)
1078             heap = SizedVirtualHeap(k, h, blocks_per_bucket=b)
1079
1080             fname = label+".pdf"
1081             try:
1082                 os.remove(os.path.join(thisdir, fname))
1083             except OSError:                            # pragma: no cover
1084                 pass                                   # pragma: no cover
1085
1086             rc = heap.save_image_as_pdf(os.path.join(thisdir, label),
1087                                         max_levels=maxl)
1088
1089             if not has_dot:
1090                 self.assertEqual(rc, False)
1091             else:
1092                 self.assertEqual(rc, True)
1093                 self.assertEqual(
1094                     os.path.exists(os.path.join(thisdir, fname)), True)
1095                 try:
1096                     os.remove(os.path.join(thisdir, fname))
1097                 except OSError:                        # pragma: no cover
1098                     pass                               # pragma: no cover
1099
1100             data = list(range(heap.block_count()))
1101             fname = label+"_data.pdf"
1102             try:
1103                 os.remove(os.path.join(thisdir, fname))
1104             except OSError:                            # pragma: no cover
1105                 pass                                   # pragma: no cover
1106             rc = heap.save_image_as_pdf(os.path.join(thisdir, fname),
1107                                         data=data,
1108                                         max_levels=maxl)
1109             if not has_dot:
1110                 self.assertEqual(rc, False)
1111             else:
1112                 self.assertEqual(rc, True)
1113                 self.assertEqual(
1114                     os.path.exists(os.path.join(thisdir, fname)), True)
1115                 try:
1116                     os.remove(os.path.join(thisdir, fname))
1117                 except OSError:                        # pragma: no cover
1118                     pass                               # pragma: no cover
1119
1120 class TestMisc(unittest2.TestCase):
1121
1122     def test_calculate_bucket_level(self):
1123         self.assertEqual(calculate_bucket_level(2, 0), 0)
1124         self.assertEqual(calculate_bucket_level(2, 1), 1)
1125         self.assertEqual(calculate_bucket_level(2, 2), 1)
1126         self.assertEqual(calculate_bucket_level(2, 3), 2)
1127         self.assertEqual(calculate_bucket_level(2, 4), 2)
1128         self.assertEqual(calculate_bucket_level(2, 5), 2)
1129         self.assertEqual(calculate_bucket_level(2, 6), 2)
1130         self.assertEqual(calculate_bucket_level(2, 7), 3)
1131
1132         self.assertEqual(calculate_bucket_level(3, 0), 0)
1133         self.assertEqual(calculate_bucket_level(3, 1), 1)
1134         self.assertEqual(calculate_bucket_level(3, 2), 1)
1135         self.assertEqual(calculate_bucket_level(3, 3), 1)
1136         self.assertEqual(calculate_bucket_level(3, 4), 2)
1137         self.assertEqual(calculate_bucket_level(3, 5), 2)
1138         self.assertEqual(calculate_bucket_level(3, 6), 2)
1139         self.assertEqual(calculate_bucket_level(3, 7), 2)
1140         self.assertEqual(calculate_bucket_level(3, 8), 2)
1141         self.assertEqual(calculate_bucket_level(3, 9), 2)
1142         self.assertEqual(calculate_bucket_level(3, 10), 2)
1143         self.assertEqual(calculate_bucket_level(3, 11), 2)
1144         self.assertEqual(calculate_bucket_level(3, 12), 2)
1145         self.assertEqual(calculate_bucket_level(3, 13), 3)
1146
1147         self.assertEqual(calculate_bucket_level(4, 0), 0)
1148         self.assertEqual(calculate_bucket_level(4, 1), 1)
1149         self.assertEqual(calculate_bucket_level(4, 2), 1)
1150         self.assertEqual(calculate_bucket_level(4, 3), 1)
1151         self.assertEqual(calculate_bucket_level(4, 4), 1)
1152
1153         self.assertEqual(calculate_bucket_level(4, 5), 2)
1154         self.assertEqual(calculate_bucket_level(4, 6), 2)
1155         self.assertEqual(calculate_bucket_level(4, 7), 2)
1156         self.assertEqual(calculate_bucket_level(4, 8), 2)
1157
1158         self.assertEqual(calculate_bucket_level(4, 9), 2)
1159         self.assertEqual(calculate_bucket_level(4, 10), 2)
1160         self.assertEqual(calculate_bucket_level(4, 11), 2)
1161         self.assertEqual(calculate_bucket_level(4, 12), 2)
1162
1163         self.assertEqual(calculate_bucket_level(4, 13), 2)
1164         self.assertEqual(calculate_bucket_level(4, 14), 2)
1165         self.assertEqual(calculate_bucket_level(4, 15), 2)
1166         self.assertEqual(calculate_bucket_level(4, 16), 2)
1167
1168         self.assertEqual(calculate_bucket_level(4, 17), 2)
1169         self.assertEqual(calculate_bucket_level(4, 18), 2)
1170         self.assertEqual(calculate_bucket_level(4, 19), 2)
1171         self.assertEqual(calculate_bucket_level(4, 20), 2)
1172
1173         self.assertEqual(calculate_bucket_level(4, 21), 3)
1174
1175     def test_clib_calculate_bucket_level(self):
1176         for k in _test_bases:
1177             for b in xrange(calculate_bucket_count_in_heap_with_height(k, 2)+2):
1178                 self.assertEqual(_clib.calculate_bucket_level(k, b),
1179                                  calculate_bucket_level(k, b))
1180         for k, b in [(89, 14648774),
1181                      (89, 14648775),
1182                      (90, 14648774),
1183                      (90, 14648775)]:
1184             self.assertEqual(_clib.calculate_bucket_level(k, b),
1185                              calculate_bucket_level(k, b))
1186
1187     def test_clib_calculate_last_common_level(self):
1188         for k in range(2, 8):
1189             for b1 in xrange(calculate_bucket_count_in_heap_with_height(k, 2)+2):
1190                 for b2 in xrange(calculate_bucket_count_in_heap_with_height(k, 2)+2):
1191                     self.assertEqual(_clib.calculate_last_common_level(k, b1, b2),
1192                                      calculate_last_common_level(k, b1, b2))
1193         for k in [89,90]:
1194             for b1 in [0, 100, 10000, 14648774, 14648775]:
1195                 for b2 in [0, 100, 10000, 14648774, 14648775]:
1196                     self.assertEqual(_clib.calculate_last_common_level(k, b1, b2),
1197                                      calculate_last_common_level(k, b1, b2))
1198
1199     def test_calculate_necessary_heap_height(self):
1200         self.assertEqual(calculate_necessary_heap_height(2, 1), 0)
1201         self.assertEqual(calculate_necessary_heap_height(2, 2), 1)
1202         self.assertEqual(calculate_necessary_heap_height(2, 3), 1)
1203         self.assertEqual(calculate_necessary_heap_height(2, 4), 2)
1204         self.assertEqual(calculate_necessary_heap_height(2, 5), 2)
1205         self.assertEqual(calculate_necessary_heap_height(2, 6), 2)
1206         self.assertEqual(calculate_necessary_heap_height(2, 7), 2)
1207         self.assertEqual(calculate_necessary_heap_height(2, 8), 3)
1208
1209         self.assertEqual(calculate_necessary_heap_height(3, 1), 0)
1210         self.assertEqual(calculate_necessary_heap_height(3, 2), 1)
1211         self.assertEqual(calculate_necessary_heap_height(3, 3), 1)
1212         self.assertEqual(calculate_necessary_heap_height(3, 4), 1)
1213         self.assertEqual(calculate_necessary_heap_height(3, 5), 2)
1214         self.assertEqual(calculate_necessary_heap_height(3, 6), 2)
1215         self.assertEqual(calculate_necessary_heap_height(3, 7), 2)
1216         self.assertEqual(calculate_necessary_heap_height(3, 8), 2)
1217         self.assertEqual(calculate_necessary_heap_height(3, 9), 2)
1218         self.assertEqual(calculate_necessary_heap_height(3, 10), 2)
1219         self.assertEqual(calculate_necessary_heap_height(3, 11), 2)
1220         self.assertEqual(calculate_necessary_heap_height(3, 12), 2)
1221         self.assertEqual(calculate_necessary_heap_height(3, 13), 2)
1222         self.assertEqual(calculate_necessary_heap_height(3, 14), 3)
1223         self.assertEqual(calculate_necessary_heap_height(3, 15), 3)
1224         self.assertEqual(calculate_necessary_heap_height(3, 16), 3)
1225
1226 if __name__ == "__main__":
1227     unittest2.main()                                    # pragma: no cover