1
# ----------------------------------------------------------------------------
3
# Copyright (c) 2006-2008 Alex Holkner
6
# Redistribution and use in source and binary forms, with or without
7
# modification, are permitted provided that the following conditions
10
# * Redistributions of source code must retain the above copyright
11
# notice, this list of conditions and the following disclaimer.
12
# * Redistributions in binary form must reproduce the above copyright
13
# notice, this list of conditions and the following disclaimer in
14
# the documentation and/or other materials provided with the
16
# * Neither the name of pyglet nor the names of its
17
# contributors may be used to endorse or promote products
18
# derived from this software without specific prior written
21
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24
# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25
# COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27
# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29
# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31
# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32
# POSSIBILITY OF SUCH DAMAGE.
33
# ----------------------------------------------------------------------------
34
'''Run list encoding utilities.
39
__docformat__ = 'restructuredtext'
40
__version__ = '$Id: $'
43
def __init__(self, value, count):
48
return 'Run(%r, %d)' % (self.value, self.count)
50
class RunList(object):
51
'''List of contiguous runs of values.
53
A `RunList` is an efficient encoding of a sequence of values. For
54
example, the sequence ``aaaabbccccc`` is encoded as ``(4, a), (2, b),
55
(5, c)``. The class provides methods for modifying and querying the
56
run list without needing to deal with the tricky cases of splitting and
57
merging the run list entries.
59
Run lists are used to represent formatted character data in pyglet. A
60
separate run list is maintained for each style attribute, for example,
61
bold, italic, font size, and so on. Unless you are overriding the
62
document interfaces, the only interaction with run lists is via
65
The length and ranges of a run list always refer to the character
66
positions in the decoded list. For example, in the above sequence,
67
``set_run(2, 5, 'x')`` would change the sequence to ``aaxxxbccccc``.
69
def __init__(self, size, initial):
70
'''Create a run list of the given size and a default value.
74
Number of characters to represent initially.
76
The value of all characters in the run list.
79
self.runs = [_Run(initial, size)]
81
def insert(self, pos, length):
82
'''Insert characters into the run list.
84
The inserted characters will take on the value immediately preceding
85
the insertion point (or the value of the first character, if `pos` is
92
Number of characters to insert.
98
if i <= pos <= i + run.count:
102
def delete(self, start, end):
103
'''Remove characters from the run list.
107
Starting index to remove from.
109
End index, exclusive.
113
for run in self.runs:
116
if i <= start <= i + run.count:
117
trim = min(end - start, i + run.count - start)
121
self.runs = [r for r in self.runs if r.count > 0]
123
# Don't leave an empty list
125
self.runs = [_Run(run.value, 0)]
127
def set_run(self, start, end, value):
128
'''Set the value of a range of characters.
132
Start index of range.
134
End of range, exclusive.
136
Value to set over the range.
142
# Find runs that need to be split
148
for run_i, run in enumerate(self.runs):
150
if i < start < i + count:
152
start_trim = start - i
153
if i < end < i + count:
159
if start_i is not None:
160
run = self.runs[start_i]
161
self.runs.insert(start_i, _Run(run.value, start_trim))
162
run.count -= start_trim
163
if end_i is not None:
165
end_trim -= start_trim
167
if end_i is not None:
168
run = self.runs[end_i]
169
self.runs.insert(end_i, _Run(run.value, end_trim))
170
run.count -= end_trim
172
# Set new value on runs
174
for run in self.runs:
175
if start <= i and i + run.count <= end:
179
# Merge adjacent runs
180
last_run = self.runs[0]
181
for run in self.runs[1:]:
182
if run.value == last_run.value:
183
run.count += last_run.count
187
# Delete collapsed runs
188
self.runs = [r for r in self.runs if r.count > 0]
192
for run in self.runs:
193
yield i, i + run.count, run.value
196
def get_run_iterator(self):
197
'''Get an extended iterator over the run list.
199
:rtype: `RunIterator`
201
return RunIterator(self)
203
def __getitem__(self, index):
204
'''Get the value at a character position.
208
Index of character. Must be within range and non-negative.
213
for run in self.runs:
214
if i <= index < i + run.count:
218
# Append insertion point
220
return self.runs[-1].value
222
assert False, 'Index not in range'
225
return str(list(self))
227
class AbstractRunIterator(object):
228
'''Range iteration over `RunList`.
230
`AbstractRunIterator` objects allow any monotonically non-decreasing
231
access of the iteration, including repeated iteration over the same index.
232
Use the ``[index]`` operator to get the value at a particular index within
233
the document. For example::
235
run_iter = iter(run_list)
237
value = run_iter[0] # non-decreasing access is OK
240
value = run_iter[16] # this is illegal, the index decreased.
242
Using `AbstractRunIterator` to access increasing indices of the value runs
243
is more efficient than calling `RunList.__getitem__` repeatedly.
245
You can also iterate over monotonically non-decreasing ranges over the
246
iteration. For example::
248
run_iter = iter(run_list)
249
for start, end, value in run_iter.ranges(0, 20):
251
for start, end, value in run_iter.ranges(25, 30):
253
for start, end, value in run_iter.ranges(30, 40):
256
Both start and end indices of the slice are required and must be positive.
259
def __getitem__(self, index):
260
'''Get the value at a given index.
262
See the class documentation for examples of valid usage.
266
Document position to query.
271
def ranges(self, start, end):
272
'''Iterate over a subrange of the run list.
274
See the class documentation for examples of valid usage.
278
Start index to iterate from.
280
End index, exclusive.
283
:return: Iterator over (start, end, value) tuples.
286
class RunIterator(AbstractRunIterator):
287
def __init__(self, run_list):
288
self.next = iter(run_list).next
289
self.start, self.end, self.value = self.next()
291
def __getitem__(self, index):
292
while index >= self.end:
293
self.start, self.end, self.value = self.next()
296
def ranges(self, start, end):
297
while start >= self.end:
298
self.start, self.end, self.value = self.next()
299
yield start, min(self.end, end), self.value
300
while end > self.end:
301
self.start, self.end, self.value = self.next()
302
yield self.start, min(self.end, end), self.value
304
class OverriddenRunIterator(AbstractRunIterator):
305
'''Iterator over a `RunIterator`, with a value temporarily replacing
308
def __init__(self, base_iterator, start, end, value):
309
'''Create a derived iterator.
313
Start of range to override
315
End of range to override, exclusive
317
Value to replace over the range
320
self.iter = base_iterator
321
self.override_start = start
322
self.override_end = end
323
self.override_value = value
325
def ranges(self, start, end):
326
if end <= self.override_start or start >= self.override_end:
328
for r in self.iter.ranges(start, end):
331
# Overlap: before, override, after
332
if start < self.override_start < end:
333
for r in self.iter.ranges(start, self.override_start):
335
yield (max(self.override_start, start),
336
min(self.override_end, end),
338
if start < self.override_end < end:
339
for r in self.iter.ranges(self.override_end, end):
342
def __getitem__(self, index):
343
if self.override_start <= index < self.override_end:
344
return self.override_value
346
return self.iter[index]
348
class FilteredRunIterator(AbstractRunIterator):
349
'''Iterate over an `AbstractRunIterator` with filtered values replaced
352
def __init__(self, base_iterator, filter, default):
353
'''Create a filtered run iterator.
356
`base_iterator` : `AbstractRunIterator`
358
`filter` : ``lambda object: bool``
359
Function taking a value as parameter, and returning ``True``
360
if the value is acceptable, and ``False`` if the default value
361
should be substituted.
363
Default value to replace filtered values.
366
self.iter = base_iterator
368
self.default = default
370
def ranges(self, start, end):
371
for start, end, value in self.iter.ranges(start, end):
372
if self.filter(value):
373
yield start, end, value
375
yield start, end, self.default
377
def __getitem__(self, index):
378
value = self.iter[index]
379
if self.filter(value):
383
class ZipRunIterator(AbstractRunIterator):
384
'''Iterate over multiple run iterators concurrently.'''
385
def __init__(self, range_iterators):
386
self.range_iterators = range_iterators
388
def ranges(self, start, end):
389
iterators = [i.ranges(start, end) for i in self.range_iterators]
390
starts, ends, values = zip(*[i.next() for i in iterators])
391
starts = list(starts)
393
values = list(values)
396
yield start, min_end, values
398
for i, iterator in enumerate(iterators):
399
if ends[i] == min_end:
400
starts[i], ends[i], values[i] = iterator.next()
402
def __getitem__(self, index):
403
return [i[index] for i in self.range_iterators]
405
class ConstRunIterator(AbstractRunIterator):
406
'''Iterate over a constant value without creating a RunList.'''
407
def __init__(self, length, value):
412
yield 0, self.length, self.value
414
def ranges(self, start, end):
415
yield start, end, self.value
417
def __getitem__(self, index):