← Back to branch summary

~malept/ubuntu/lucid/python2.6/dev-dependency-fix

« back to all changes in this revision

Viewing changes to Lib/test/test_iterlen.py

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-02-13 12:51:00 UTC
  • Revision ID: james.westby@ubuntu.com-20090213125100-uufgcb9yeqzujpqw
Tags: upstream-2.6.1
Import upstream version 2.6.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
Lib/test/test_iterlen.py
 
1
""" Test Iterator Length Transparency
 
2
 
 
3
Some functions or methods which accept general iterable arguments have
 
4
optional, more efficient code paths if they know how many items to expect.
 
5
For instance, map(func, iterable), will pre-allocate the exact amount of
 
6
space required whenever the iterable can report its length.
 
7
 
 
8
The desired invariant is:  len(it)==len(list(it)).
 
9
 
 
10
A complication is that an iterable and iterator can be the same object. To
 
11
maintain the invariant, an iterator needs to dynamically update its length.
 
12
For instance, an iterable such as xrange(10) always reports its length as ten,
 
13
but it=iter(xrange(10)) starts at ten, and then goes to nine after it.next().
 
14
Having this capability means that map() can ignore the distinction between
 
15
map(func, iterable) and map(func, iter(iterable)).
 
16
 
 
17
When the iterable is immutable, the implementation can straight-forwardly
 
18
report the original length minus the cumulative number of calls to next().
 
19
This is the case for tuples, xrange objects, and itertools.repeat().
 
20
 
 
21
Some containers become temporarily immutable during iteration.  This includes
 
22
dicts, sets, and collections.deque.  Their implementation is equally simple
 
23
though they need to permantently set their length to zero whenever there is
 
24
an attempt to iterate after a length mutation.
 
25
 
 
26
The situation slightly more involved whenever an object allows length mutation
 
27
during iteration.  Lists and sequence iterators are dynanamically updatable.
 
28
So, if a list is extended during iteration, the iterator will continue through
 
29
the new items.  If it shrinks to a point before the most recent iteration,
 
30
then no further items are available and the length is reported at zero.
 
31
 
 
32
Reversed objects can also be wrapped around mutable objects; however, any
 
33
appends after the current position are ignored.  Any other approach leads
 
34
to confusion and possibly returning the same item more than once.
 
35
 
 
36
The iterators not listed above, such as enumerate and the other itertools,
 
37
are not length transparent because they have no way to distinguish between
 
38
iterables that report static length and iterators whose length changes with
 
39
each call (i.e. the difference between enumerate('abc') and
 
40
enumerate(iter('abc')).
 
41
 
 
42
"""
 
43
 
 
44
import unittest
 
45
from test import test_support
 
46
from itertools import repeat
 
47
from collections import deque
 
48
from __builtin__ import len as _len
 
49
 
 
50
n = 10
 
51
 
 
52
def len(obj):
 
53
    try:
 
54
        return _len(obj)
 
55
    except TypeError:
 
56
        try:
 
57
            # note: this is an internal undocumented API,
 
58
            # don't rely on it in your own programs
 
59
            return obj.__length_hint__()
 
60
        except AttributeError:
 
61
            raise TypeError
 
62
 
 
63
class TestInvariantWithoutMutations(unittest.TestCase):
 
64
 
 
65
    def test_invariant(self):
 
66
        it = self.it
 
67
        for i in reversed(xrange(1, n+1)):
 
68
            self.assertEqual(len(it), i)
 
69
            it.next()
 
70
        self.assertEqual(len(it), 0)
 
71
        self.assertRaises(StopIteration, it.next)
 
72
        self.assertEqual(len(it), 0)
 
73
 
 
74
class TestTemporarilyImmutable(TestInvariantWithoutMutations):
 
75
 
 
76
    def test_immutable_during_iteration(self):
 
77
        # objects such as deques, sets, and dictionaries enforce
 
78
        # length immutability  during iteration
 
79
 
 
80
        it = self.it
 
81
        self.assertEqual(len(it), n)
 
82
        it.next()
 
83
        self.assertEqual(len(it), n-1)
 
84
        self.mutate()
 
85
        self.assertRaises(RuntimeError, it.next)
 
86
        self.assertEqual(len(it), 0)
 
87
 
 
88
## ------- Concrete Type Tests -------
 
89
 
 
90
class TestRepeat(TestInvariantWithoutMutations):
 
91
 
 
92
    def setUp(self):
 
93
        self.it = repeat(None, n)
 
94
 
 
95
    def test_no_len_for_infinite_repeat(self):
 
96
        # The repeat() object can also be infinite
 
97
        self.assertRaises(TypeError, len, repeat(None))
 
98
 
 
99
class TestXrange(TestInvariantWithoutMutations):
 
100
 
 
101
    def setUp(self):
 
102
        self.it = iter(xrange(n))
 
103
 
 
104
class TestXrangeCustomReversed(TestInvariantWithoutMutations):
 
105
 
 
106
    def setUp(self):
 
107
        self.it = reversed(xrange(n))
 
108
 
 
109
class TestTuple(TestInvariantWithoutMutations):
 
110
 
 
111
    def setUp(self):
 
112
        self.it = iter(tuple(xrange(n)))
 
113
 
 
114
## ------- Types that should not be mutated during iteration -------
 
115
 
 
116
class TestDeque(TestTemporarilyImmutable):
 
117
 
 
118
    def setUp(self):
 
119
        d = deque(xrange(n))
 
120
        self.it = iter(d)
 
121
        self.mutate = d.pop
 
122
 
 
123
class TestDequeReversed(TestTemporarilyImmutable):
 
124
 
 
125
    def setUp(self):
 
126
        d = deque(xrange(n))
 
127
        self.it = reversed(d)
 
128
        self.mutate = d.pop
 
129
 
 
130
class TestDictKeys(TestTemporarilyImmutable):
 
131
 
 
132
    def setUp(self):
 
133
        d = dict.fromkeys(xrange(n))
 
134
        self.it = iter(d)
 
135
        self.mutate = d.popitem
 
136
 
 
137
class TestDictItems(TestTemporarilyImmutable):
 
138
 
 
139
    def setUp(self):
 
140
        d = dict.fromkeys(xrange(n))
 
141
        self.it = d.iteritems()
 
142
        self.mutate = d.popitem
 
143
 
 
144
class TestDictValues(TestTemporarilyImmutable):
 
145
 
 
146
    def setUp(self):
 
147
        d = dict.fromkeys(xrange(n))
 
148
        self.it = d.itervalues()
 
149
        self.mutate = d.popitem
 
150
 
 
151
class TestSet(TestTemporarilyImmutable):
 
152
 
 
153
    def setUp(self):
 
154
        d = set(xrange(n))
 
155
        self.it = iter(d)
 
156
        self.mutate = d.pop
 
157
 
 
158
## ------- Types that can mutate during iteration -------
 
159
 
 
160
class TestList(TestInvariantWithoutMutations):
 
161
 
 
162
    def setUp(self):
 
163
        self.it = iter(range(n))
 
164
 
 
165
    def test_mutation(self):
 
166
        d = range(n)
 
167
        it = iter(d)
 
168
        it.next()
 
169
        it.next()
 
170
        self.assertEqual(len(it), n-2)
 
171
        d.append(n)
 
172
        self.assertEqual(len(it), n-1)  # grow with append
 
173
        d[1:] = []
 
174
        self.assertEqual(len(it), 0)
 
175
        self.assertEqual(list(it), [])
 
176
        d.extend(xrange(20))
 
177
        self.assertEqual(len(it), 0)
 
178
 
 
179
class TestListReversed(TestInvariantWithoutMutations):
 
180
 
 
181
    def setUp(self):
 
182
        self.it = reversed(range(n))
 
183
 
 
184
    def test_mutation(self):
 
185
        d = range(n)
 
186
        it = reversed(d)
 
187
        it.next()
 
188
        it.next()
 
189
        self.assertEqual(len(it), n-2)
 
190
        d.append(n)
 
191
        self.assertEqual(len(it), n-2)  # ignore append
 
192
        d[1:] = []
 
193
        self.assertEqual(len(it), 0)
 
194
        self.assertEqual(list(it), [])  # confirm invariant
 
195
        d.extend(xrange(20))
 
196
        self.assertEqual(len(it), 0)
 
197
 
 
198
def test_main():
 
199
    unittests = [
 
200
        TestRepeat,
 
201
        TestXrange,
 
202
        TestXrangeCustomReversed,
 
203
        TestTuple,
 
204
        TestDeque,
 
205
        TestDequeReversed,
 
206
        TestDictKeys,
 
207
        TestDictItems,
 
208
        TestDictValues,
 
209
        TestSet,
 
210
        TestList,
 
211
        TestListReversed,
 
212
    ]
 
213
    test_support.run_unittest(*unittests)
 
214
 
 
215
if __name__ == "__main__":
 
216
    test_main()