Set(집합)은 정렬되지 않은 컬렉션으로 중복된 원소가 없다.

집합은 유일하게 구분되는 원소의 모임이다.

집합 만들기

function Set() {
  var items = {};
}

배열이 아닌 객체로 집합을 표현한다.

자바스크립트 객체는 동일한 키로 여러 프로퍼티를 가질 수는 없으므로 집합에서 원소가 중복되지 않는 특성이 그대로 보장된다.

다음은 Set 클래스에서 구현할 메서드이다.

add() : 원소를 추가한다. remove() : 원소를 삭제한다. has() : 어떤 원소가 집합에 포함되어 있는지 여부를 true/false로 반환한다. clear() : 모든 원소를 삭제 size() : 원소의 개수를 반환 values() : 집합의 모든 원소를 배열 형태로 반환

has 메서드

this.has = function(value) {
  return value in items;
};

집합의 모든 원소는 객체에 담겨 있으므로 자바스크립트 in 연산자로 해당 원소가 items 프로퍼티 중 하나인지 확인한다.

아니면

this.has = function(value) {
  return items.hasOwnProperty(value);
};

자바스크립트 객체는 hasOwnProperty 메서드를 상속하는 것을 응용한 것이다. 객체가 어떤 프로퍼티를 갖고 있는지 여부를 조사한다.

add 메서드

새 원소를 추가하는 것이다.

this.add = function(value) {
  if (!this.has(value)) {
    items[value] = value;
    return true;
  }
  return false;
};

value가 이미 집합에 포함되어 있는지 먼저 확인한다 없는 원소라면 value를 넣고 true를 반환, 있는 원소라면 false를 반환해서 추가 여부에 대한 표시를 한다.

remove와 clear 메서드

this.remove = function(value) {
  if (this.has(value)) {
    delete items[value];
    return true;
  }
  return false;
};

삭제할 원소가 집합에 존재하는지 먼저 확인하고 있는 원소라면 원소를 삭제하고 true를 반환한다. 그외는 false를 한다.

삭제할때는 간단하게 delete 연산자로 items에서 해당 프로퍼티를 지운다.

this.clear = function() {
  items = {};
};

집합의 모든 원소를 날릴때는 빈 객체를 할당하면 된다.

size 메서드

size를 구하는 방법은 3가지가 있다.

LinkedList 처럼 add,remove 호출할때 마다 값을 바꿔주는 방법

Object 클래스에 내장된 함수를 이용 하는 방법

this.size = function() {
  return Object.keys(items).length;
};

Object.keys는 객체의 모든 프로퍼티를 배열로 변환한다. 따라서 배열의 length로 원소 개수를 파악할 수 있다.

하지만 비교적 최신 브라우저에서만 제대로 작동한다.

셋째 items의 프로퍼티가 모두 몇 개 인지 세어본다.

this.sizeLegacy = function() {
  var count = 0;
  for (var prop in items) {
    if (items.hasOwnProperty(prop)) {
      ++count;
    }
  }
  return count;
};

items 객체의 프로퍼티를 루프로 순회하면서 유효한지 체크한다. 유효한 프로퍼티라면 count 변수 값을 증가 시키고 마지막에 반환한다.

value 메서드

같은 방법으로 items의 모든 프로퍼티를 추출해 배열 형태로 반환한다.

this.value = function() {
  return Object.keys(items);
};

위의 코드는 비교적 최신 브라우저에서만 작동한다.

this.valueLegacy = function() {
  var keys = [];
  for (var key in items) {
    if (items.hasOwnProperty(key)) {
      keys.push(key);
    }
  }
  return keys;
};

집합 연산

집합에서 사용 가능한 연산은 네가지가 있다.

합집합: 두 집합 중 어느 한쪽이라도 포함된 원소로 구성된 집합을 구한다.

교집합: 두 집합 모두 포함되어 있는 원소로 구성된 집합을 구한다.

차집합: 첫 번쨰 집합에는 있지만 두 번째 집합에는 없는 원소로 구성된 집합을 구한다.

부분집합: 어떤 집합이 다른 집합의 일부인지 확인한다.

합집합

A, B 어느 한쪽에 속하는 원소 x의 집합니다.

this.union = function(otherSet) {
  var unionSet = new Set();
  var values = this.values();
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i]);
  }
  values = otherSet.values();
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i]);
  }
  return unionSet;
};

먼저 합집합 unionSet을 생성한다. 첫 번쨰 집합의 values 메서드로 모든 원소를 추출한뒤 루프로 반복하면서 unionSet에 추가한다

같은 로직을 두번쨰 집합에도 적용한 후 unionSet을 반환한다.

교집합

A에도 속하고 B에도 속하는 원소 x의 집합이다.

this.intersection = function(otherSet) {
  var intersectionSet = new Set();
  var values = this.values();
  for (var i = 0; i < values.length; i++) {
    if (otherSet.has(values[i])) {
      intersection.add(values[i]);
    }
  }
  return intersection;
};

차집합

A에는 속하지만 B에는 속하지 않는 원소 x의 집합이다.

this.difference = function(otherSet) {
  var differenceSet = new Set();
  var values = this.values();
  for (var i = 0; i < values.length; i++) {
    if (!otherSet.has(values[i])) {
      differenceSet.add(values[i]);
    }
  }
  return differenceSet;
};

부분집합

A의 모든 원소는 반드시 B에 존재함을 의미한다.

this.subset = function(otherSet) {
  if (this.size() > otherSet.size()) {
    return false;
  } else {
    var values = this.values();
    for (var i = 0; i < values.length; i++) {
      if (!otherSet.has(values[i])) {
        return false;
      }
    }
    return true;
  }
};

가장 먼저 현재 인스턴스(this)의 크기를 확인한다. this가 otherSet보다 원소가 많다면 이미 부분집합 조건이 맞지 않는다.

부분집합은 비교 대상 집합보다 원소 개수가 같거나 적어야 한다.

그 다음은 원소를 순회하면서 각 원소가 otherSet에 존재하는지 확읺나다.

하나라도 otherSet에 존재하지 않으면 부분집합이 아니므로 바로 false를 반환한다.

루프를 정상 종료했다면 this의 모든 원소가 otherSet에도 있다는 뜻으로 true를 반환한다.