Sunbelt Computer Software

PL/B Language Development and Support

python/data_structures/queues/queue_by_list.py at master · althetinkerer/python · GitHub

138 lines (115 loc) · 2.97 KB

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

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

"""Queue represented by a Python list"""

from collections.abc import Iterable

class QueueByList[T]:

def __init__(self, iterable: Iterable[T] | None = None) -> None:

"""

>>> QueueByList()

Queue(())

>>> QueueByList([10, 20, 30])

Queue((10, 20, 30))

>>> QueueByList((i**2 for i in range(1, 4)))

Queue((1, 4, 9))

"""

self.entries: list[T] = list(iterable or [])

def __len__(self) -> int:

"""

>>> len(QueueByList())

0

>>> from string import ascii_lowercase

>>> len(QueueByList(ascii_lowercase))

26

>>> queue = QueueByList()

>>> for i in range(1, 11):

... queue.put(i)

>>> len(queue)

10

>>> for i in range(2):

... queue.get()

1

2

>>> len(queue)

8

"""

return len(self.entries)

def __repr__(self) -> str:

"""

>>> queue = QueueByList()

>>> queue

Queue(())

>>> str(queue)

'Queue(())'

>>> queue.put(10)

>>> queue

Queue((10,))

>>> queue.put(20)

>>> queue.put(30)

>>> queue

Queue((10, 20, 30))

"""

return f"Queue({tuple(self.entries)})"

def put(self, item: T) -> None:

"""Put `item` to the Queue

>>> queue = QueueByList()

>>> queue.put(10)

>>> queue.put(20)

>>> len(queue)

2

>>> queue

Queue((10, 20))

"""

self.entries.append(item)

def get(self) -> T:

"""

Get `item` from the Queue

>>> queue = QueueByList((10, 20, 30))

>>> queue.get()

10

>>> queue.put(40)

>>> queue.get()

20

>>> queue.get()

30

>>> len(queue)

1

>>> queue.get()

40

>>> queue.get()

Traceback (most recent call last):

...

IndexError: Queue is empty

"""

if not self.entries:

raise IndexError("Queue is empty")

return self.entries.pop(0)

def rotate(self, rotation: int) -> None:

"""Rotate the items of the Queue `rotation` times

>>> queue = QueueByList([10, 20, 30, 40])

>>> queue

Queue((10, 20, 30, 40))

>>> queue.rotate(1)

>>> queue

Queue((20, 30, 40, 10))

>>> queue.rotate(2)

>>> queue

Queue((40, 10, 20, 30))

"""

put = self.entries.append

get = self.entries.pop

for _ in range(rotation):

put(get(0))

def get_front(self) -> T:

"""Get the front item from the Queue

>>> queue = QueueByList((10, 20, 30))

>>> queue.get_front()

10

>>> queue

Queue((10, 20, 30))

>>> queue.get()

10

>>> queue.get_front()

20

"""

return self.entries[0]

if __name__ == "__main__":

from doctest import testmod

testmod()