dsa.deque

  1""" Module containing deque classes. """
  2
  3class Deque:
  4    """ 
  5    A static deque implementation that supports appending and popping elements 
  6    from both ends, with a fixed capacity.
  7    """
  8    def __init__(self, capacity: int=10):
  9        """ 
 10        Initialize a deque with a fixed capacity.
 11
 12        Args:
 13            capacity (int): The initial size of the deque (default is 10).
 14        """
 15        self._array = [None] * capacity
 16        self._left = -1
 17        self._right = 0
 18        self.count = 0
 19        
 20    def push_front(self, element):
 21        """
 22        Push an element at the front of the deque. (synonym for append_left)
 23        Raises an exception when the deque is full.
 24
 25        Args:
 26            element: The element to append.
 27
 28        Raises:
 29            Exception: If the deque is full.
 30        """
 31        self.append_left(element)
 32
 33    def push_back(self, element):
 34        """
 35        Push an element at the back of the deque. (synonym for append_right)
 36        Raises an exception when the deque is full.
 37
 38        Args:
 39            element: The element to append.
 40
 41        Raises:
 42            Exception: If the deque is full.
 43        """
 44        self.append_right(element)
 45
 46    def pop_front(self):
 47        """
 48        Pop an element from the front of the deque. (synonym for pop_left)
 49        Raises an exception if the deque is empty.
 50
 51        Returns:
 52            The leftmost element of the deque.
 53
 54        Raises:
 55            Exception: If the deque is empty.
 56        """
 57        return self.pop_left()
 58
 59    def pop_back(self):
 60        """
 61        Pop an element from the back of the deque. (synonym for pop_right)
 62        Raises an exception if the deque is empty.
 63
 64        Returns:
 65            The rightmost element of the deque.
 66
 67        Raises:
 68            Exception: If the deque is empty.
 69        """
 70        return self.pop_right() 
 71    
 72    def front(self):
 73        """
 74        Get the element at the front of the deque without removing it.
 75        Raises an exception if the deque is empty.
 76
 77        Returns:
 78            The leftmost element.
 79
 80        Raises:
 81            Exception: If the deque is empty.
 82        """
 83        return self.peek_left()
 84    
 85    def back(self):
 86        """
 87        Get the element at the back of the deque without removing it.
 88        Raises an exception if the deque is empty.
 89
 90        Returns:
 91            The rightmost element.
 92
 93        Raises:
 94            Exception: If the deque is empty.
 95        """
 96        return self.peek_right()
 97
 98    def append_left(self, element):
 99        """
100        Append an element to the left of the deque. Raises an exception when the deque is full.
101
102        Args:
103            element: The element to append.
104
105        Raises:
106            Exception: If the deque is full.
107        """
108        if self.count >= self.capacity():
109            raise Exception("Deque Full")
110        if self._left < 0:
111            self._left = self.capacity() - 1
112        self._array[self._left] = element
113        self._left -= 1
114        self.count += 1
115        
116    def append_right(self, element):
117        """
118        Append an element to the right of the deque. Raises an exception when the deque is full.
119
120        Args:
121            element: The element to append.
122
123        Raises:
124            Exception: If the deque is full.
125        """
126        if self.count >= self.capacity():
127            raise Exception("Deque Full")
128        if self._right > self.capacity() - 1:
129            self._right = 0
130        self._array[self._right] = element
131        self._right += 1
132        self.count += 1
133
134    def pop_left(self):
135        """
136        Remove and return the element from the left of the deque. Raises an exception if the deque is empty.
137
138        Returns:
139            The leftmost element of the deque.
140
141        Raises:
142            Exception: If the deque is empty.
143        """
144        if self.is_empty():
145            raise Exception("Empty Deque")
146
147        element = self._array[self._left + 1]
148        self._left += 1
149        if self._left + 1 >= len(self._array):
150            self._left = -1
151        self.count -= 1
152        return element
153    
154    def pop_right(self):
155        """
156        Pop an element from right the deque. Raise an exception if the deque is empty.
157
158        Returns:
159            The rightmost element of the deque.
160
161        Raises:
162            Exception: If the deque is empty.
163        """
164        if self.is_empty():
165            raise Exception("Empty Deque")
166        element = self._array[self._right - 1]
167        self.count -= 1
168
169        self._right -= 1
170        if self._right < 0:
171            self._right = len(self._array) - 1
172        return element
173
174    def peek_left(self):
175        """
176        Get the element at the left of the deque without removing it.
177        Raises an exception if the deque is empty.
178
179        Returns:
180            The leftmost element.
181
182        Raises:
183            Exception: If the deque is empty.
184        """
185        if self.is_empty():
186            raise Exception("Empty deque")
187        return self._array[self._left + 1]
188
189    def peek_right(self):
190        """
191        Get the element at the right of the deque without removing it.
192        Raises an exception if the deque is empty.
193
194        Returns:
195            The rightmost element.
196
197        Raises:
198            Exception: If the deque is empty.
199        """
200        if self.is_empty():
201            raise Exception("Empty deque")
202        return self._array[self._right - 1]
203    
204    def is_empty(self) -> bool:
205        """
206        Return a Boolean on whether the deque is empty or not.
207        """
208        return self.count == 0
209
210    @classmethod
211    def from_list(cls, alist: list):
212        """
213        Create a deque from a given list. Raises an exception if list exceeds the deque's capacity.
214
215        Args:
216            alist: The list to initialize the deque with.
217
218        Returns:
219            a deque instance with elements from the list.
220
221        Raises:
222            Exception: If list exceeds the deque's capacity.
223        """
224        dq = cls()
225        for e in alist:
226            dq.append_right(e)
227        return dq
228
229    def to_list(self):
230        """
231        Convert the deque's contents into a list.
232
233        Returns:
234            A list containg the elements in the deque.
235        """
236        arr = []
237        for i in range(self.count):
238            index = (i + self._left + 1) % len(self._array) 
239            arr.append(self._array[index])
240        return arr
241
242    def capacity(self) -> int:
243        """
244        Get the maximum capacity of the deque.
245
246        Returns:
247            The capacity of the deque.
248        """
249        return len(self._array)
250    
251    def __len__(self) -> int:
252        """
253        Get the number of elements in the deque.
254
255        Returns:
256            The count of elements.
257        """
258        return self.count
259    
260    def __repr__(self):
261        """
262        String representation of the deque for debugging purposes.
263
264        Returns:
265            A string displaying the contents and size of the deque.
266        """
267        arr = []
268        for i in range(self.count):
269            index = (i + self._left + 1) % len(self._array) 
270            arr.append(str(self._array[index]))
271        arrstr = ", ".join(arr)
272        return f"[{arrstr}] Count: {self.count} Capacity: {len(self._array)}" # {self.array}"
273    
274class DynamicDeque(Deque):
275    """ 
276    A dynamic deque implementation that adjusts its capacity as needed.
277    """
278    def grow(self):
279        """ 
280        Helper method to double the capacity of the deque.
281        """
282        new_array = [ None ] * self.capacity() * 2
283        
284        # copy elements
285        for i in range(self.count):
286            index = (i + self._left + 1) % len(self._array) 
287            new_array[i] = self._array[index]
288
289        self._array = new_array
290        self._left = -1
291        self._right = self.count
292
293    def shrink(self):
294        """ 
295        Helper method to halve the capacity of the deque. 
296        """
297        if self.capacity() < 10:
298            return
299
300        new_capacity = self.capacity() // 2
301        new_array = [ None ] * new_capacity
302        
303        # copy elements
304        for i in range(self.count):
305            index = (i + self._left + 1) % len(self._array) 
306            new_array[i] = self._array[index]
307
308        self._array = new_array
309        self._left = -1
310        self._right = self.count
311
312
313    def check_capacity(self):
314        """ 
315        Helper method to adjust the capacity of the deque based on its count:
316        if count >= capacity, grow the deque
317        if count <= 1/4 of capacity, shrink the deque
318        """
319        if self.count >= self.capacity():
320            self.grow()
321        elif self.count * 4 <= self.capacity():
322            self.shrink()
323        
324    def append_left(self, element):
325        """
326        Append an element to the left, adjusting capacity if needed.
327
328        Args:
329            element: The element to append.
330         """
331        self.check_capacity()
332        super().append_left(element)
333        
334    def append_right(self, element):
335        """
336        Append an element to the right, adjusting capacity if needed.
337
338        Args:
339            element: The element to append.
340        """
341        self.check_capacity()
342        super().append_right(element)
343
344    def pop_left(self):
345        """
346        Remove and return the element from the left, adjusting capacity if needed.
347
348        Returns:
349            The leftmost element.
350        """
351        self.check_capacity()
352        return super().pop_left()
353
354
355    def pop_right(self):
356        """
357        Remove and return the element from the right, adjusting capacity if needed.
358
359        Returns:
360            The rightmost element.
361        """
362        self.check_capacity()
363        return super().pop_right()