array_sorted_list.py

"""
    Array-based implementation of SortedList ADT.
    Items to store should be of time ListItem.
"""

from referential_array import ArrayR
from sorted_list import *
from typing import TypeVar, Generic
T = TypeVar('T')

__author__ = 'Maria Garcia de la Banda and Brendon Taylor. Modified by Alexey Ignatiev and Graeme Gange'
__docformat__ = 'reStructuredText'

class ArraySortedList(SortedList[T]):
    """ SortedList ADT implemented with arrays. """
    MIN_CAPACITY = 1

    def __init__(self, max_capacity: int) -> None:
        """ ArraySortedList object initialiser. """

        # first, calling the basic initialiser
        SortedList.__init__(self)

        # initialising the internal array
        size = max(self.MIN_CAPACITY, max_capacity)
        self.array = ArrayR(size)
        self.order = "increasing"

    def reset(self):
        """ Reset the list. """
        SortedList.__init__(self)

    def __getitem__(self, index: int) -> ListItem:
        """ Magic method. Return the element at a given position. """
        return self.array[index]

    def __setitem__(self, index: int, item: T) -> None:
        """ Magic method. Insert the item at a given position,
            if possible (!). Shift the following elements to the right.
        """
        if self.is_empty() or \
                (index == 0 and item.key <= self[index].key) or \
                (index == len(self) and self[index - 1].key <= item.key) or \
                (index > 0 and self[index - 1].key <= item.key <= self[index].key):

            if self.is_full():
                self._resize()

            self._shuffle_right(index)
            self.array[index] = item
        else:
            # the list isn't empty and the item's position is wrong wrt. its neighbourghs
            raise IndexError('Element should be inserted in sorted order')

    def __contains__(self, item: ListItem):
        """ Checks if value is in the list. """
        for i in range(len(self)):
            if self.array[i] == item:
                return True
        return False

    def _shuffle_right(self, index: int) -> None:
        """ Shuffle items to the right up to a given position. """
        for i in range(len(self), index, -1):
            self.array[i] = self.array[i - 1]

    def _shuffle_left(self, index: int) -> None:
        """ Shuffle items starting at a given position to the left. """
        for i in range(index, len(self)):
            self.array[i] = self.array[i + 1]

    def _resize(self) -> None:
        """ Resize the list. """
        # doubling the size of our list
        new_array = ArrayR(2 * len(self.array))

        # copying the contents
        for i in range(self.length):
            new_array[i] = self.array[i]

        # referring to the new array
        self.array = new_array

    def delete_at_index(self, index: int) -> ListItem:
        """ Delete item at a given position. """
        if index >= len(self):
            raise IndexError('No such index in the list')
        item = self.array[index]
        self.length -= 1
        self._shuffle_left(index)
        return item

    def index(self, item: ListItem) -> int:
        """ Find the position of a given item in the list. """
        pos = self._index_to_add(item)
        if pos < len(self) and self[pos] == item:
            return pos
        raise ValueError('item not in list')

    def is_full(self):
        """ Check if the list is full. """
        return len(self) >= len(self.array)

    def add(self, item: ListItem) -> None:
        """ Add new element to the list. """
        if self.is_full():
            self._resize()
        
        if self.order == "decreasing":
            self.increasing_order()
            self.add_pokemon_decreasing(item)
        
        else:
            # find where to place it
            position = self._index_to_add(item)

            self[position] = item
            self.length += 1

        if self.order == "decreasing":
            self.decreasing_order()

    def _index_to_add(self, item: ListItem) -> int:
        """ Find the position where the new item should be placed. """

        low = 0
        high = len(self) - 1

        while low <= high:
            mid = (low + high) // 2
            if self[mid].key < item.key:
                low = mid + 1
            elif self[mid].key > item.key:
                high = mid - 1
            else:
                return mid

        return low

    def add_pokemon_decreasing(self, pokemon: ListItem):
        """ Add a pokemon to the list when it is in decreasing order"""
        index = -1
        for i in range(len(self) - 1, -1, -1):
            if pokemon.key >= self.array[i].key:
                index = i
                break
        if index == -1 and len(self) == 0:
            self._shuffle_right(0)
            self.array[0] = pokemon
            self.length += 1

        elif index == -1 and len(self) == 1:
            self._shuffle_right(0)
            self.array[0] = pokemon
            self.length += 1
        else:
            self._shuffle_right(index)
            self.array[index + 1] = pokemon
            self.length += 1
    
    def reverse_order(self):
        """ Reverses the current order of the sorted array list"""
        if self.order == "increasing":
            self.order = "decreasing"
            self.decreasing_order()
        elif self.order == "decreasing":
            self.order = "increasing"
            self.increasing_order()

    def increasing_order(self):
        """Makes sorted list ascending order"""
        n = len(self)
        for j in range(n - 1, 0, -1):
            swapped = False
            for i in range(j):
                if self[i].key >= self[i + 1].key:
                    self.swap(i, i + 1)
                    swapped = True
            if not swapped:
                break

    def decreasing_order(self):
        """Makes sorted list descending order"""
        n = len(self)
        for j in range(n - 1, 0, -1):
            swapped = False
            for i in range(j):
                if self[i].key <= self[i + 1].key:
                    self.swap(i, i + 1)
                    swapped = True
            if not swapped:
                break

    def swap(self, i, j):
        """ Swaps two adjacent elements"""
        self.array[i], self.array[j] = self.array[j], self.array[i]