Back to index

python3.2  3.2.2
Public Member Functions | Public Attributes | Static Public Attributes
test.test_heapq.TestHeapC Class Reference
Inheritance diagram for test.test_heapq.TestHeapC:
Inheritance graph
[legend]
Collaboration diagram for test.test_heapq.TestHeapC:
Collaboration graph
[legend]

List of all members.

Public Member Functions

def test_push_pop
def check_invariant
def test_heapify
def test_naive_nbest
def heapiter
def test_nbest
def test_nbest_with_pushpop
def test_heappushpop
def test_heapsort
def test_merge
def test_merge_stability
def test_nsmallest
def test_nlargest
def test_comparison_operator

Public Attributes

 x

Static Public Attributes

 module = c_heapq

Detailed Description

Definition at line 222 of file test_heapq.py.


Member Function Documentation

def test.test_heapq.TestHeap.check_invariant (   self,
  heap 
) [inherited]

Definition at line 59 of file test_heapq.py.

00059 
00060     def check_invariant(self, heap):
00061         # Check the heap invariant.
00062         for pos, item in enumerate(heap):
00063             if pos: # pos 0 has no parent
00064                 parentpos = (pos-1) >> 1
00065                 self.assertTrue(heap[parentpos] <= item)

Here is the call graph for this function:

Here is the caller graph for this function:

def test.test_heapq.TestHeap.heapiter (   self,
  heap 
) [inherited]

Definition at line 84 of file test_heapq.py.

00084 
00085     def heapiter(self, heap):
00086         # An iterator returning a heap's elements, smallest-first.
00087         try:
00088             while 1:
00089                 yield self.module.heappop(heap)
00090         except IndexError:
00091             pass

Here is the caller graph for this function:

Definition at line 194 of file test_heapq.py.

00194 
00195     def test_comparison_operator(self):
00196         # Issue 3051: Make sure heapq works with both __lt__
00197         # For python 3.0, __le__ alone is not enough
00198         def hsort(data, comp):
00199             data = [comp(x) for x in data]
00200             self.module.heapify(data)
00201             return [self.module.heappop(data).x for i in range(len(data))]
00202         class LT:
00203             def __init__(self, x):
00204                 self.x = x
00205             def __lt__(self, other):
00206                 return self.x > other.x
00207         class LE:
00208             def __init__(self, x):
00209                 self.x = x
00210             def __le__(self, other):
00211                 return self.x >= other.x
00212         data = [random.random() for i in range(100)]
00213         target = sorted(data, reverse=True)
00214         self.assertEqual(hsort(data, LT), target)
00215         self.assertRaises(TypeError, data, LE)
00216 

Here is the call graph for this function:

def test.test_heapq.TestHeap.test_heapify (   self) [inherited]

Definition at line 66 of file test_heapq.py.

00066 
00067     def test_heapify(self):
00068         for size in range(30):
00069             heap = [random.random() for dummy in range(size)]
00070             self.module.heapify(heap)
00071             self.check_invariant(heap)
00072 
00073         self.assertRaises(TypeError, self.module.heapify, None)

Here is the call graph for this function:

def test.test_heapq.TestHeap.test_heappushpop (   self) [inherited]

Definition at line 119 of file test_heapq.py.

00119 
00120     def test_heappushpop(self):
00121         h = []
00122         x = self.module.heappushpop(h, 10)
00123         self.assertEqual((h, x), ([], 10))
00124 
00125         h = [10]
00126         x = self.module.heappushpop(h, 10.0)
00127         self.assertEqual((h, x), ([10], 10.0))
00128         self.assertEqual(type(h[0]), int)
00129         self.assertEqual(type(x), float)
00130 
00131         h = [10];
00132         x = self.module.heappushpop(h, 9)
00133         self.assertEqual((h, x), ([10], 9))
00134 
00135         h = [10];
00136         x = self.module.heappushpop(h, 11)
00137         self.assertEqual((h, x), ([11], 10))

Here is the call graph for this function:

def test.test_heapq.TestHeap.test_heapsort (   self) [inherited]

Definition at line 138 of file test_heapq.py.

00138 
00139     def test_heapsort(self):
00140         # Exercise everything with repeated heapsort checks
00141         for trial in range(100):
00142             size = random.randrange(50)
00143             data = [random.randrange(25) for i in range(size)]
00144             if trial & 1:     # Half of the time, use heapify
00145                 heap = data[:]
00146                 self.module.heapify(heap)
00147             else:             # The rest of the time, use heappush
00148                 heap = []
00149                 for item in data:
00150                     self.module.heappush(heap, item)
00151             heap_sorted = [self.module.heappop(heap) for i in range(size)]
00152             self.assertEqual(heap_sorted, sorted(data))

Here is the call graph for this function:

def test.test_heapq.TestHeap.test_merge (   self) [inherited]

Definition at line 153 of file test_heapq.py.

00153 
00154     def test_merge(self):
00155         inputs = []
00156         for i in range(random.randrange(5)):
00157             row = sorted(random.randrange(1000) for j in range(random.randrange(10)))
00158             inputs.append(row)
00159         self.assertEqual(sorted(chain(*inputs)), list(self.module.merge(*inputs)))
00160         self.assertEqual(list(self.module.merge()), [])

Here is the call graph for this function:

Definition at line 161 of file test_heapq.py.

00161 
00162     def test_merge_stability(self):
00163         class Int(int):
00164             pass
00165         inputs = [[], [], [], []]
00166         for i in range(20000):
00167             stream = random.randrange(4)
00168             x = random.randrange(500)
00169             obj = Int(x)
00170             obj.pair = (x, stream)
00171             inputs[stream].append(obj)
00172         for stream in inputs:
00173             stream.sort()
00174         result = [i.pair for i in self.module.merge(*inputs)]
00175         self.assertEqual(result, sorted(result))

def test.test_heapq.TestHeap.test_naive_nbest (   self) [inherited]

Definition at line 74 of file test_heapq.py.

00074 
00075     def test_naive_nbest(self):
00076         data = [random.randrange(2000) for i in range(1000)]
00077         heap = []
00078         for item in data:
00079             self.module.heappush(heap, item)
00080             if len(heap) > 10:
00081                 self.module.heappop(heap)
00082         heap.sort()
00083         self.assertEqual(heap, sorted(data)[-10:])

Here is the call graph for this function:

def test.test_heapq.TestHeap.test_nbest (   self) [inherited]

Definition at line 92 of file test_heapq.py.

00092 
00093     def test_nbest(self):
00094         # Less-naive "N-best" algorithm, much faster (if len(data) is big
00095         # enough <wink>) than sorting all of data.  However, if we had a max
00096         # heap instead of a min heap, it could go faster still via
00097         # heapify'ing all of data (linear time), then doing 10 heappops
00098         # (10 log-time steps).
00099         data = [random.randrange(2000) for i in range(1000)]
00100         heap = data[:10]
00101         self.module.heapify(heap)
00102         for item in data[10:]:
00103             if item > heap[0]:  # this gets rarer the longer we run
00104                 self.module.heapreplace(heap, item)
00105         self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:])
00106 
00107         self.assertRaises(TypeError, self.module.heapreplace, None)
00108         self.assertRaises(TypeError, self.module.heapreplace, None, None)
00109         self.assertRaises(IndexError, self.module.heapreplace, [], None)

Here is the call graph for this function:

Definition at line 110 of file test_heapq.py.

00110 
00111     def test_nbest_with_pushpop(self):
00112         data = [random.randrange(2000) for i in range(1000)]
00113         heap = data[:10]
00114         self.module.heapify(heap)
00115         for item in data[10:]:
00116             self.module.heappushpop(heap, item)
00117         self.assertEqual(list(self.heapiter(heap)), sorted(data)[-10:])
00118         self.assertEqual(self.module.heappushpop([], 'x'), 'x')

Here is the call graph for this function:

def test.test_heapq.TestHeap.test_nlargest (   self) [inherited]

Definition at line 185 of file test_heapq.py.

00185 
00186     def test_nlargest(self):
00187         data = [(random.randrange(2000), i) for i in range(1000)]
00188         for f in (None, lambda x:  x[0] * 547 % 2000):
00189             for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
00190                 self.assertEqual(list(self.module.nlargest(n, data)),
00191                                  sorted(data, reverse=True)[:n])
00192                 self.assertEqual(list(self.module.nlargest(n, data, key=f)),
00193                                  sorted(data, key=f, reverse=True)[:n])

Here is the call graph for this function:

def test.test_heapq.TestHeap.test_nsmallest (   self) [inherited]

Definition at line 176 of file test_heapq.py.

00176 
00177     def test_nsmallest(self):
00178         data = [(random.randrange(2000), i) for i in range(1000)]
00179         for f in (None, lambda x:  x[0] * 547 % 2000):
00180             for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
00181                 self.assertEqual(list(self.module.nsmallest(n, data)),
00182                                  sorted(data)[:n])
00183                 self.assertEqual(list(self.module.nsmallest(n, data, key=f)),
00184                                  sorted(data, key=f)[:n])

Here is the call graph for this function:

def test.test_heapq.TestHeap.test_push_pop (   self) [inherited]

Definition at line 31 of file test_heapq.py.

00031 
00032     def test_push_pop(self):
00033         # 1) Push 256 random numbers and pop them off, verifying all's OK.
00034         heap = []
00035         data = []
00036         self.check_invariant(heap)
00037         for i in range(256):
00038             item = random.random()
00039             data.append(item)
00040             self.module.heappush(heap, item)
00041             self.check_invariant(heap)
00042         results = []
00043         while heap:
00044             item = self.module.heappop(heap)
00045             self.check_invariant(heap)
00046             results.append(item)
00047         data_sorted = data[:]
00048         data_sorted.sort()
00049         self.assertEqual(data_sorted, results)
00050         # 2) Check that the invariant holds for a sorted array
00051         self.check_invariant(results)
00052 
00053         self.assertRaises(TypeError, self.module.heappush, [])
00054         try:
00055             self.assertRaises(TypeError, self.module.heappush, None, None)
00056             self.assertRaises(TypeError, self.module.heappop, None)
00057         except AttributeError:
00058             pass

Here is the call graph for this function:


Member Data Documentation

Reimplemented from test.test_heapq.TestHeap.

Definition at line 223 of file test_heapq.py.

Definition at line 203 of file test_heapq.py.


The documentation for this class was generated from the following file: