This repository has been archived by the owner on Dec 16, 2022. It is now read-only.
/
sequences.py
85 lines (67 loc) · 2.67 KB
/
sequences.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import bisect
import random
from collections import abc
from typing import Sequence, Optional, Union
class ShuffledSequence(abc.Sequence):
"""
Produces a shuffled view of a sequence, such as a list.
This assumes that the inner sequence never changes. If it does, the results
are undefined.
"""
def __init__(self, inner_sequence: Sequence, indices: Optional[Sequence[int]] = None):
self.inner = inner_sequence
self.indices: Sequence[int]
if indices is None:
self.indices = list(range(len(inner_sequence)))
random.shuffle(self.indices)
else:
self.indices = indices
def __len__(self) -> int:
return len(self.indices)
def __getitem__(self, i: Union[int, slice]):
if isinstance(i, int):
return self.inner[self.indices[i]]
else:
return ShuffledSequence(self.inner, self.indices[i])
def __contains__(self, item) -> bool:
for i in self.indices:
if self.inner[i] == item:
return True
return False
class SlicedSequence(ShuffledSequence):
"""
Produces a sequence that's a slice into another sequence, without copying the elements.
This assumes that the inner sequence never changes. If it does, the results
are undefined.
"""
def __init__(self, inner_sequence: Sequence, s: slice):
super().__init__(inner_sequence, range(*s.indices(len(inner_sequence))))
class ConcatenatedSequence(abc.Sequence):
"""
Produces a sequence that's the concatenation of multiple other sequences, without
copying the elements.
This assumes that the inner sequence never changes. If it does, the results
are undefined.
"""
def __init__(self, *sequences: Sequence):
self.sequences = sequences
self.cumulative_sequence_lengths = [0]
for sequence in sequences:
self.cumulative_sequence_lengths.append(
self.cumulative_sequence_lengths[-1] + len(sequence)
)
def __len__(self):
return self.cumulative_sequence_lengths[-1]
def __getitem__(self, i: Union[int, slice]):
if isinstance(i, int):
if i < 0:
i += len(self)
if i < 0 or i >= len(self):
raise IndexError("list index out of range")
sequence_index = bisect.bisect_right(self.cumulative_sequence_lengths, i) - 1
i -= self.cumulative_sequence_lengths[sequence_index]
return self.sequences[sequence_index][i]
else:
return SlicedSequence(self, i)
def __contains__(self, item) -> bool:
return any(s.__contains__(item) for s in self.sequences)