EmbeddedPkg: Extend NvVarStoreFormattedLib LIBRARY_CLASS

[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.2 / Lib / test / test_heapq.py

"""Unittests for heapq."""\r
\r
import sys\r
import random\r
\r
from test import test_support\r
from unittest import TestCase, skipUnless\r
\r
py_heapq = test_support.import_fresh_module('heapq', blocked=['_heapq'])\r
c_heapq = test_support.import_fresh_module('heapq', fresh=['_heapq'])\r
\r
# _heapq.nlargest/nsmallest are saved in heapq._nlargest/_smallest when\r
# _heapq is imported, so check them there\r
func_names = ['heapify', 'heappop', 'heappush', 'heappushpop',\r
              'heapreplace', '_nlargest', '_nsmallest']\r
\r
class TestModules(TestCase):\r
    def test_py_functions(self):\r
        for fname in func_names:\r
            self.assertEqual(getattr(py_heapq, fname).__module__, 'heapq')\r
\r
    @skipUnless(c_heapq, 'requires _heapq')\r
    def test_c_functions(self):\r
        for fname in func_names:\r
            self.assertEqual(getattr(c_heapq, fname).__module__, '_heapq')\r
\r
\r
class TestHeap(TestCase):\r
    module = None\r
\r
    def test_push_pop(self):\r
        # 1) Push 256 random numbers and pop them off, verifying all's OK.\r
        heap = []\r
        data = []\r
        self.check_invariant(heap)\r
        for i in range(256):\r
            item = random.random()\r
            data.append(item)\r
            self.module.heappush(heap, item)\r
            self.check_invariant(heap)\r
        results = []\r
        while heap:\r
            item = self.module.heappop(heap)\r
            self.check_invariant(heap)\r
            results.append(item)\r
        data_sorted = data[:]\r
        data_sorted.sort()\r
        self.assertEqual(data_sorted, results)\r
        # 2) Check that the invariant holds for a sorted array\r
        self.check_invariant(results)\r
\r
        self.assertRaises(TypeError, self.module.heappush, [])\r
        try:\r
            self.assertRaises(TypeError, self.module.heappush, None, None)\r
            self.assertRaises(TypeError, self.module.heappop, None)\r
        except AttributeError:\r
            pass\r
\r
    def check_invariant(self, heap):\r
        # Check the heap invariant.\r
        for pos, item in enumerate(heap):\r
            if pos: # pos 0 has no parent\r
                parentpos = (pos-1) >> 1\r
                self.assertTrue(heap[parentpos] <= item)\r
\r
    def test_heapify(self):\r
        for size in range(30):\r
            heap = [random.random() for dummy in range(size)]\r
            self.module.heapify(heap)\r
            self.check_invariant(heap)\r
\r
        self.assertRaises(TypeError, self.module.heapify, None)\r
\r
    def test_naive_nbest(self):\r
        data = [random.randrange(2000) for i in range(1000)]\r
        heap = []\r
        for item in data:\r
            self.module.heappush(heap, item)\r
            if len(heap) > 10:\r
                self.module.heappop(heap)\r
        heap.sort()\r
        self.assertEqual(heap, sorted(data)[-10:])\r
\r
    def heapiter(self, heap):\r
        # An iterator returning a heap's elements, smallest-first.\r
        try:\r
            while 1:\r
                yield self.module.heappop(heap)\r
        except IndexError:\r
            pass\r
\r
    def test_nbest(self):\r
        # Less-naive "N-best" algorithm, much faster (if len(data) is big\r
        # enough <wink>) than sorting all of data.  However, if we had a max\r
        # heap instead of a min heap, it could go faster still via\r
        # heapify'ing all of data (linear time), then doing 10 heappops\r
        # (10 log-time steps).\r
        data = [random.randrange(2000) for i in range(1000)]\r
        heap = data[:10]\r
        self.module.heapify(heap)\r
        for item in data[10:]:\r
            if item > heap[0]:  # this gets rarer the longer we run\r
                self.module.heapreplace(heap, item)\r
        self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:])\r
\r
        self.assertRaises(TypeError, self.module.heapreplace, None)\r
        self.assertRaises(TypeError, self.module.heapreplace, None, None)\r
        self.assertRaises(IndexError, self.module.heapreplace, [], None)\r
\r
    def test_nbest_with_pushpop(self):\r
        data = [random.randrange(2000) for i in range(1000)]\r
        heap = data[:10]\r
        self.module.heapify(heap)\r
        for item in data[10:]:\r
            self.module.heappushpop(heap, item)\r
        self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:])\r
        self.assertEqual(self.module.heappushpop([], 'x'), 'x')\r
\r
    def test_heappushpop(self):\r
        h = []\r
        x = self.module.heappushpop(h, 10)\r
        self.assertEqual((h, x), ([], 10))\r
\r
        h = [10]\r
        x = self.module.heappushpop(h, 10.0)\r
        self.assertEqual((h, x), ([10], 10.0))\r
        self.assertEqual(type(h[0]), int)\r
        self.assertEqual(type(x), float)\r
\r
        h = [10];\r
        x = self.module.heappushpop(h, 9)\r
        self.assertEqual((h, x), ([10], 9))\r
\r
        h = [10];\r
        x = self.module.heappushpop(h, 11)\r
        self.assertEqual((h, x), ([11], 10))\r
\r
    def test_heapsort(self):\r
        # Exercise everything with repeated heapsort checks\r
        for trial in xrange(100):\r
            size = random.randrange(50)\r
            data = [random.randrange(25) for i in range(size)]\r
            if trial & 1:     # Half of the time, use heapify\r
                heap = data[:]\r
                self.module.heapify(heap)\r
            else:             # The rest of the time, use heappush\r
                heap = []\r
                for item in data:\r
                    self.module.heappush(heap, item)\r
            heap_sorted = [self.module.heappop(heap) for i in range(size)]\r
            self.assertEqual(heap_sorted, sorted(data))\r
\r
    def test_merge(self):\r
        inputs = []\r
        for i in xrange(random.randrange(5)):\r
            row = sorted(random.randrange(1000) for j in range(random.randrange(10)))\r
            inputs.append(row)\r
        self.assertEqual(sorted(chain(*inputs)), list(self.module.merge(*inputs)))\r
        self.assertEqual(list(self.module.merge()), [])\r
\r
    def test_merge_stability(self):\r
        class Int(int):\r
            pass\r
        inputs = [[], [], [], []]\r
        for i in range(20000):\r
            stream = random.randrange(4)\r
            x = random.randrange(500)\r
            obj = Int(x)\r
            obj.pair = (x, stream)\r
            inputs[stream].append(obj)\r
        for stream in inputs:\r
            stream.sort()\r
        result = [i.pair for i in self.module.merge(*inputs)]\r
        self.assertEqual(result, sorted(result))\r
\r
    def test_nsmallest(self):\r
        data = [(random.randrange(2000), i) for i in range(1000)]\r
        for f in (None, lambda x:  x[0] * 547 % 2000):\r
            for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):\r
                self.assertEqual(self.module.nsmallest(n, data), sorted(data)[:n])\r
                self.assertEqual(self.module.nsmallest(n, data, key=f),\r
                                 sorted(data, key=f)[:n])\r
\r
    def test_nlargest(self):\r
        data = [(random.randrange(2000), i) for i in range(1000)]\r
        for f in (None, lambda x:  x[0] * 547 % 2000):\r
            for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):\r
                self.assertEqual(self.module.nlargest(n, data),\r
                                 sorted(data, reverse=True)[:n])\r
                self.assertEqual(self.module.nlargest(n, data, key=f),\r
                                 sorted(data, key=f, reverse=True)[:n])\r
\r
    def test_comparison_operator(self):\r
        # Issue 3051: Make sure heapq works with both __lt__ and __le__\r
        def hsort(data, comp):\r
            data = map(comp, data)\r
            self.module.heapify(data)\r
            return [self.module.heappop(data).x for i in range(len(data))]\r
        class LT:\r
            def __init__(self, x):\r
                self.x = x\r
            def __lt__(self, other):\r
                return self.x > other.x\r
        class LE:\r
            def __init__(self, x):\r
                self.x = x\r
            def __le__(self, other):\r
                return self.x >= other.x\r
        data = [random.random() for i in range(100)]\r
        target = sorted(data, reverse=True)\r
        self.assertEqual(hsort(data, LT), target)\r
        self.assertEqual(hsort(data, LE), target)\r
\r
\r
class TestHeapPython(TestHeap):\r
    module = py_heapq\r
\r
\r
@skipUnless(c_heapq, 'requires _heapq')\r
class TestHeapC(TestHeap):\r
    module = c_heapq\r
\r
\r
#==============================================================================\r
\r
class LenOnly:\r
    "Dummy sequence class defining __len__ but not __getitem__."\r
    def __len__(self):\r
        return 10\r
\r
class GetOnly:\r
    "Dummy sequence class defining __getitem__ but not __len__."\r
    def __getitem__(self, ndx):\r
        return 10\r
\r
class CmpErr:\r
    "Dummy element that always raises an error during comparison"\r
    def __cmp__(self, other):\r
        raise ZeroDivisionError\r
\r
def R(seqn):\r
    'Regular generator'\r
    for i in seqn:\r
        yield i\r
\r
class G:\r
    'Sequence using __getitem__'\r
    def __init__(self, seqn):\r
        self.seqn = seqn\r
    def __getitem__(self, i):\r
        return self.seqn[i]\r
\r
class I:\r
    'Sequence using iterator protocol'\r
    def __init__(self, seqn):\r
        self.seqn = seqn\r
        self.i = 0\r
    def __iter__(self):\r
        return self\r
    def next(self):\r
        if self.i >= len(self.seqn): raise StopIteration\r
        v = self.seqn[self.i]\r
        self.i += 1\r
        return v\r
\r
class Ig:\r
    'Sequence using iterator protocol defined with a generator'\r
    def __init__(self, seqn):\r
        self.seqn = seqn\r
        self.i = 0\r
    def __iter__(self):\r
        for val in self.seqn:\r
            yield val\r
\r
class X:\r
    'Missing __getitem__ and __iter__'\r
    def __init__(self, seqn):\r
        self.seqn = seqn\r
        self.i = 0\r
    def next(self):\r
        if self.i >= len(self.seqn): raise StopIteration\r
        v = self.seqn[self.i]\r
        self.i += 1\r
        return v\r
\r
class N:\r
    'Iterator missing next()'\r
    def __init__(self, seqn):\r
        self.seqn = seqn\r
        self.i = 0\r
    def __iter__(self):\r
        return self\r
\r
class E:\r
    'Test propagation of exceptions'\r
    def __init__(self, seqn):\r
        self.seqn = seqn\r
        self.i = 0\r
    def __iter__(self):\r
        return self\r
    def next(self):\r
        3 // 0\r
\r
class S:\r
    'Test immediate stop'\r
    def __init__(self, seqn):\r
        pass\r
    def __iter__(self):\r
        return self\r
    def next(self):\r
        raise StopIteration\r
\r
from itertools import chain, imap\r
def L(seqn):\r
    'Test multiple tiers of iterators'\r
    return chain(imap(lambda x:x, R(Ig(G(seqn)))))\r
\r
class TestErrorHandling(TestCase):\r
    module = None\r
\r
    def test_non_sequence(self):\r
        for f in (self.module.heapify, self.module.heappop):\r
            self.assertRaises((TypeError, AttributeError), f, 10)\r
        for f in (self.module.heappush, self.module.heapreplace,\r
                  self.module.nlargest, self.module.nsmallest):\r
            self.assertRaises((TypeError, AttributeError), f, 10, 10)\r
\r
    def test_len_only(self):\r
        for f in (self.module.heapify, self.module.heappop):\r
            self.assertRaises((TypeError, AttributeError), f, LenOnly())\r
        for f in (self.module.heappush, self.module.heapreplace):\r
            self.assertRaises((TypeError, AttributeError), f, LenOnly(), 10)\r
        for f in (self.module.nlargest, self.module.nsmallest):\r
            self.assertRaises(TypeError, f, 2, LenOnly())\r
\r
    def test_get_only(self):\r
        seq = [CmpErr(), CmpErr(), CmpErr()]\r
        for f in (self.module.heapify, self.module.heappop):\r
            self.assertRaises(ZeroDivisionError, f, seq)\r
        for f in (self.module.heappush, self.module.heapreplace):\r
            self.assertRaises(ZeroDivisionError, f, seq, 10)\r
        for f in (self.module.nlargest, self.module.nsmallest):\r
            self.assertRaises(ZeroDivisionError, f, 2, seq)\r
\r
    def test_arg_parsing(self):\r
        for f in (self.module.heapify, self.module.heappop,\r
                  self.module.heappush, self.module.heapreplace,\r
                  self.module.nlargest, self.module.nsmallest):\r
            self.assertRaises((TypeError, AttributeError), f, 10)\r
\r
    def test_iterable_args(self):\r
        for f in (self.module.nlargest, self.module.nsmallest):\r
            for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):\r
                for g in (G, I, Ig, L, R):\r
                    with test_support.check_py3k_warnings(\r
                            ("comparing unequal types not supported",\r
                             DeprecationWarning), quiet=True):\r
                        self.assertEqual(f(2, g(s)), f(2,s))\r
                self.assertEqual(f(2, S(s)), [])\r
                self.assertRaises(TypeError, f, 2, X(s))\r
                self.assertRaises(TypeError, f, 2, N(s))\r
                self.assertRaises(ZeroDivisionError, f, 2, E(s))\r
\r
\r
class TestErrorHandlingPython(TestErrorHandling):\r
    module = py_heapq\r
\r
\r
@skipUnless(c_heapq, 'requires _heapq')\r
class TestErrorHandlingC(TestErrorHandling):\r
    module = c_heapq\r
\r
\r
#==============================================================================\r
\r
\r
def test_main(verbose=None):\r
    test_classes = [TestModules, TestHeapPython, TestHeapC,\r
                    TestErrorHandlingPython, TestErrorHandlingC]\r
    test_support.run_unittest(*test_classes)\r
\r
    # verify reference counting\r
    if verbose and hasattr(sys, "gettotalrefcount"):\r
        import gc\r
        counts = [None] * 5\r
        for i in xrange(len(counts)):\r
            test_support.run_unittest(*test_classes)\r
            gc.collect()\r
            counts[i] = sys.gettotalrefcount()\r
        print counts\r
\r
if __name__ == "__main__":\r
    test_main(verbose=True)\r