SortedList

생성일: 2021년 9월 17일 오후 10:33

ADT Unsorted List Operations

Transformers

• MakeEmpty
• InsertItem
• DeleteItem

Observers

• IsFull
• LengthIs
• RetrieveItem

Iterators

• ResetList
• GetNextItem

구현

ItemType.h

#pragma once

const int MAX_ITEM = 5;
enum RelationType
{
	LESS,
	EQUAL,
	GREATER
};

class ItemType
{
public:
	RelationType ComparedTo(ItemType otherItem) const;
	void Print() const;
	void Initialize(int number);

private:
	int value;
};

ItemType.cpp

#include "ItemType.h"
#include <iostream>

RelationType ItemType::ComparedTo(ItemType otherItem) const
{
	if (value < otherItem.value)
		return LESS;
	else if (value > otherItem.value)
		return GREATER;
	else
		return EQUAL;
} //두 아이템을 비교하여 enum을 리턴

void ItemType::Print() const
{
	using namespace std;
	cout << value << endl;
}

void ItemType::Initialize(int number)
{
	value = number;
}

Sorted.h

#pragma once
#include "ItemType.h"
#define MAX_ITEMS 50

class SortedType
{
public:
	SortedType();	//Constructor
	bool IsFull() const;	//Observer
	int LenghthIs() const;	//Observer
	bool RetrieveItem(ItemType& item);	//Observer
	void InsertItem(ItemType item);	//Transformer
	void DeleteItem(ItemType item);	//Transformer
	void ResetList();	//Iterator
	void GetNextItem(ItemType& item);	//Iterator

private:
	int length;
	ItemType info[MAX_ITEMS];
	int currentPos;
};

SortedList.cpp

#include <iostream>
#include "ItemType.h"
#include "Sorted.h"

SortedType::SortedType()
{
    length = 0;
}

void SortedType::InsertItem(ItemType item)
{
    //Sequential search 사용
    bool moreToSearch;
    int location = 0;

    moreToSearch = (location < length);
    //item이 insert될 위치를 찾는다.
    while (moreToSearch)
    {
        switch (item.ComparedTo(info[location]))
        {
        case LESS: moreToSearch = false;
            break;
        case GREATER: location++;
            moreToSearch = (location < length);
            break;
        }
    }
    //찾은 위치 다음 자리부터 한칸씩 뒤로 옮긴다.
    for (int index = length; index > location; index--)
    {
        info[index] = info[index - 1];
    }
    //찾은 위치에 item을 넣는다.
    info[location] = item;
    length++;
}

int SortedType::LenghthIs() const
{
    return length;
}

bool SortedType::IsFull() const
{
    return (length == MAX_ITEMS);
}

bool SortedType::RetrieveItem(ItemType& item)
{
    //Binary search(이진 탐색) 사용 (sorted일때 사용가능)
    int midPoint;
    int first = 0;
    int last = length - 1;
    bool moreToSearch = (first <= last);    //first가 last보다 커지면 list안에 해당 item이 없는 것이다.

    bool found = false;
    while (moreToSearch && !found)
    {
        midPoint = (first + last) / 2; //c++에서는 실수가 나오면 버림을 취한다. ex) 4.5 => 4
        switch (item.ComparedTo(info[midPoint]))
        {
        case LESS: last = midPoint - 1;
            moreToSearch = (first <= last);
            break;
        
        case GREATER: first = midPoint + 1;
            moreToSearch = (first <= last);
            break;

        case EQUAL: found = true;
            item = info[midPoint];
            break;
        }
    }
    
    return found;
}

void SortedType::DeleteItem(ItemType item)
{
    //Sequential search 사용

    int location = 0;

    //삭제할 item의 위치 찾기
    while (item.ComparedTo(info[location]) != EQUAL)
        location++;

    //찾은 위치 다음 요소부터 앞으로 한 칸씩 당기기
    for (int index = location + 1; index < length; index++)
    {
        info[index - 1] = info[index];
    }

    length--;

}

void SortedType::ResetList()
{
    currentPos = -1;    //커서를 제일 앞으로 옮긴다.
}

void SortedType::GetNextItem(ItemType& item)
{
    currentPos++;   //커서를 한칸 뒤로 옮기고 item을 가져온다.
    item = info[currentPos];
}

int main()
{
    using namespace std;
    cout << "Hello World!\n";
    SortedType a;
    ItemType item1;
    item1.Initialize(3);

    a.InsertItem(item1);

    cout << a.IsFull() << endl;
    cout << a.LenghthIs() << endl;
}