ANMIAN

/******************************************
/* element.h
/* 목적 : 링크드리스트 구성을 위한 구성요소
/* 작성 : bluelimn
/******************************************/

#ifndef element_H
#define element_H

class Element
{
private:
 int data;
 Element* link;
public:
 Element():data(0),link(NULL){}
 Element(int data, Element* link = NULL):data(data), link(link){}
 int getData(){return data;}
 void setData(int value){data = value;}
 Element* getLink(){return link;}
 void setLink(Element* link){this->link = link;}
};

#endif

/******************************************
/* mySet.h
/* 목적 : 집합구성과 연산
/* 작성 : bluelimn
/******************************************/

#ifndef mySets_H
#define mySets_H
#include "element.h"
class MySets
{
private:
 Element* root;
public:
 MySets(){root = new Element();}
 MySets(Element* root):root(root)
 {
  if(root == NULL) root = new Element();
 }
 ~MySets();
 Element* getRoot(){return root;}
 bool insertElement(int value);
 bool deleteElement(int value);
 bool isEmpty();
 void viewElements();
};

static class SetsOperator
{
public:
 static MySets* setsUnion(MySets* set1, MySets* set2);
 static MySets* setsIntersection(MySets* set1, MySets* set2);
 static MySets* setsRelativeComplement(MySets* set1, MySets* set2);
};
#endif

/******************************************
/* mySet.cpp
/* 목적 : 집합구성과 연산
/* 작성 : bluelimn
/******************************************/
#include <iostream>
#include "mySets.h"
using namespace std;

/**********************************************
/* MySets 클레스 구현
**********************************************/
MySets::~MySets()
{
 Element* current = root;
 Element* pre_node = current;
 while(current != NULL)
 {
  current = current->getLink();
  delete pre_node;
  pre_node = current;
 }
}

bool MySets::isEmpty()
{
 if(root->getLink() == NULL) return true;
 return false;
}

//heap으로 구현하는 것이 적당하나 이 source에서는 linked list로 구현
bool MySets::insertElement(int value)
{
 Element* current = root;
 Element* pre_node = current;
 // 오름차순으로 insert sorting한다
 // 새로운 값이 들어갈 자리 확인(입력할 값보다 큰값 앞이거나 리스트의 마지막
 while((current != NULL) && (current->getData() < value))
 {
  pre_node = current;
  current = current->getLink();
 }
 Element* newNode = new Element(value, pre_node->getLink());  //입력할 노드
 pre_node->setLink(newNode);
 return true;
}

//리스트에서 같은 값을 찾아 가장 먼저 나오는 값을 지운다
bool MySets::deleteElement(int value)
{
 Element* current = root;
 Element* pre_node = current;
 while((current->getLink() != NULL) && (current->getData() < value))
 {
  pre_node = current;
  current = current->getLink();
 }

if(current->getData() != value) return false;     //찾는 값이 리스트에 없음

pre_node->setLink(current->getLink());
 delete current;
 return true;
}

void MySets::viewElements()
{
 Element* current = root->getLink();
 while(current != NULL)
 {
  cout << current->getData() << "  ";
  current = current->getLink();
 }
 cout << endl;
}


/**********************************************
/* SetsOperator 클레스 구현
**********************************************/
//합집합
MySets* SetsOperator::setsUnion(MySets *set1, MySets *set2)
{
 Element* root1 = set1->getRoot();
 Element* root2 = set2->getRoot();
 Element* result = new Element();
 Element* temp = result;

 root1 = root1->getLink();
 root2 = root2->getLink();
 while((root1 != NULL) && (root2 != NULL))
 {
  if ( root1->getData() < root2->getData() )
  {
   temp->setLink(new Element(root1->getData(), NULL));
   root1 = root1->getLink();
   temp = temp->getLink();
  }
  else if ( root1->getData() > root2->getData() )
  {
   temp->setLink(new Element(root2->getData(), NULL));
   root2 = root2->getLink();
   temp = temp->getLink();
  }
  else
  {
   temp->setLink(new Element(root1->getData(), NULL));
   root1 = root1->getLink();
   root2 = root2->getLink();
   temp = temp->getLink();
  }
 }
 if(root1 == NULL && root2 != NULL) temp->setLink(root2);
 else if(root2 == NULL && root1 != NULL) temp->setLink(root1);

return new MySets(result);
}
//교집합
MySets* SetsOperator::setsIntersection(MySets *set1, MySets *set2)
{
 Element* root1 = set1->getRoot();
 Element* root2 = set2->getRoot();
 Element* result = new Element();
 Element* temp = result;

 root1 = root1->getLink();
 root2 = root2->getLink();
 while((root1 != NULL) && (root2 != NULL))
 {
  if ( root1->getData() < root2->getData() )
  {
   root1 = root1->getLink();
  }
  else if ( root1->getData() > root2->getData() )
  {
   root2 = root2->getLink();
  }
  else
  {
   temp->setLink(new Element(root1->getData(), NULL));
   root1 = root1->getLink();
   root2 = root2->getLink();
   temp = temp->getLink();
  }
 }

return new MySets(result);
}
//차집합
MySets* SetsOperator::setsRelativeComplement(MySets *set1, MySets *set2)
{
 Element* root1 = set1->getRoot();
 Element* root2 = set2->getRoot();
 Element* result = new Element();
 Element* temp = result;

 root1 = root1->getLink();
 root2 = root2->getLink();
 while((root1 != NULL) && (root2 != NULL))
 {
  if ( root1->getData() < root2->getData() )
  {
   temp->setLink(new Element(root1->getData(), NULL));
   root1 = root1->getLink();
   temp = temp->getLink();
  }
  else if ( root1->getData() > root2->getData() )
  {
   temp->setLink(new Element(root2->getData(), NULL));
   root2 = root2->getLink();
   temp = temp->getLink();
  }
  else
  {
   root1 = root1->getLink();
   root2 = root2->getLink();
  }
 }
 if(root1 == NULL && root2 != NULL) temp->setLink(root2);
 else if(root2 == NULL && root1 != NULL) temp->setLink(root1);

return new MySets(result);
}

/******************************************
/* insertSortWithSets.cpp
/* 목적 : 두 집합의 차집합, 합집합, 교집합 연산
/* 작성 : bluelimn
/******************************************/

#include <iostream>
#include "mySets.h"
using namespace std;

int main()
{
 MySets* x = new MySets();
 MySets* y = new MySets();
 x->insertElement(10);
 x->insertElement(20);
 x->insertElement(70);
 x->insertElement(50);
 x->insertElement(30);
 x->insertElement(40);
 x->deleteElement(40);
 x->insertElement(41);
 cout << "x : ";
 x->viewElements();
 
 y->insertElement(20);
 y->insertElement(70);
 y->insertElement(10);
 y->insertElement(30);
 y->insertElement(40);
 y->deleteElement(50);
 y->deleteElement(70);
 y->insertElement(-50);
 cout << "y : ";
 y->viewElements();

 cout << "합집합 : ";
 MySets* tmp_uni = SetsOperator::setsUnion(x,y);
 tmp_uni->viewElements();

 cout << "교집합 : ";
 MySets* tmp_int = SetsOperator::setsIntersection(x,y);
 tmp_int->viewElements();

 cout << "차집합 : ";
 MySets* tmp_rel = SetsOperator::setsRelativeComplement(x,y);
 tmp_rel->viewElements();

 return 0;
}