SortedList - Python

생성일: 2021년 9월 29일 오후 4:53

from enum import Enum

MAX_ITEMS = 100

class Compare(Enum):
    LESS = 0
    GREATER = 1
    EQUAL = 2
    
class ItemType:
    """ Item Type """

    def __init__(self, val):
        """ [1] """
        self.value = val

    def compared_to(self, otherItem):
        """ [2] """
        if self.value < otherItem.value:
            return Compare.LESS
        elif self.value > otherItem.value:
            return Compare.GREATER
        else:
            return Compare.EQUAL
    
    def __str__(self):
        """ [3] """
        return str(self.value)

class SortedType:
    """ Chapter 3: Sorted List """

    def __init__(self):
        """ [4] """
        self.length = 0
        self.info = [0] * MAX_ITEMS
        self.current_pos = -1

    def make_empty(self):
        self.length = 0

    def length_is(self):
        return self.length

    def is_full(self):
        if self.length == MAX_ITEMS:
            return True
        return False

    def insert_item(self, item):
        """ [5] """
        moreToSearch = True
        location = 0
        moreToSearch = (location < self.length)
        while(moreToSearch):
            compared_Result = item.compared_to(self.info[location])
            if(compared_Result == Compare.LESS):
                moreToSearch = False
            elif(compared_Result == Compare.GREATER):
                location += 1
                moreToSearch = (location < self.length)

        index = self.length
        while(index > location):
            self.info[index] = self.info[index - 1]
            index -= 1
        self.info[location] = item
        self.length += 1
        
        

    def retrieve_item(self, item): # Binary Search
        """ [6] """
        midPoint = 0
        first = 0
        last = self.length - 1
        moreToSearch = (first <= last)

        found = False
        while(moreToSearch and not found):
            midPoint = (first + last) // 2
            compared_Result = item.compared_to(self.info[midPoint])
            if(compared_Result == Compare.LESS):
                last = midPoint - 1
                moreToSearch = (first <= last)
            elif(compared_Result == Compare.GREATER):
                first = midPoint + 1
                moreToSearch = (first <= last)
            else:
                found = True
                break
        return found

    def delete_item(self, item):
        """ [7] """
        location = 0
        while(item.compared_to(self.info[location]) != Compare.EQUAL):
            location += 1
        index = location + 1
        while(index < self.length):
            self.info[index -1] = self.info[index]
            index += 1
        self.length -= 1

    def reset_list(self):
        self.current_pos = -1

    def get_next_item(self):
        self.current_pos += 1
        return self.info[self.current_pos]

    def __str__(self):
        """ [8] """
        self.reset_list()
        print_list = []
        for i in range(self.length):
            print_list.append(str(self.get_next_item()))
        return str(" ".join(print_list))

여기서 해맸던 점은 SortedType init에서 처음 info를 선언할때 그냥 self.info = [] 로 선언하고 구현을 하니까 list index out of range 오류가 발생했다. 오류 문구에서는 insert_item함수에서 해당 오류가 발생하고 있다고 나왔다. 검색을 해본 결과 python에서는 비어있는 list에서 list[0]과 같이 접근하거나 해당 list보다 큰 범위의 index에 접근할 때 해당 오류가 뜬다고 한다. 이부분을 해결하기 위해서는 .append나 .insert와 같은 내장 함수를 사용하여 접근해야 한다. 예를들어 info.insert(0, item). 하지만 자료구조의 기본적 전제가 해당 언어의 내장함수 사용을 지양하면서 나만의 자료구조를 만드는 것이기 때문에 이 방법을 사용하지 않았다. 대신 놓친 부분이 있었는데, 바로 MAX_ITEMS이다. c++과는 다르게 python에서는 어레이(리스트)를 처음 선언할때 크기를 지정하지 않아도 알아서 생성이 된다. 따라서 이부분을 간과 했다. 내가 만들고자 하는 list는 그 크기 또한 class 내부에서 컨트롤하고 출력과 변경도 class내부의 length로 조절하기 때문에 처음부터 list를 만들고 info를 선언할 때 MAX_ITEMS만큼의 크기를 지정하고 garbage value( 여기서는 0)으로 채워넣을 수 있었다. 이렇게 하고 나니 insert를 사용하지 않고도 index out of range 오류가 발생하지 않았다. (list에 100개의 크기만큼 0이 꽉 차있기 때문에 그 이하의 인덱스 범위로 접근할 때는 오류가 뜨지 않는다.)

import os
from SortedType import *

if __name__ == '__main__':
    l = SortedType()
    f = open('./data.txt', 'r')
    line = f.readline()
    while line:
        t = int(line)
        i = ItemType(t)
        l.insert_item(i)
        line = f.readline()
    f.close()
    
    print("Before:")
    print(l)
        
    print("After deleting 65:")
    a = ItemType(65)
    l.delete_item(a)
    print(l)
    print()
    
    a = ItemType(3)
    if l.retrieve_item(a) == True:
        print(str(a) + " is in the list.")
    else:
        print(str(a) + " is not in the list.")
        
    a = ItemType(77)
    if l.retrieve_item(a) == True:
        print(str(a) + " is in the list.")
    else:
        print(str(a) + " is not in the list.")