IntArrayBag 클래스

코드 설명

/****************************************************************************** 
* IntArrayBag 클래스는 int 숫자들의 컬렉션(가방)을 나타냅니다.
* 동일한 숫자가 여러 번 포함될 수 있습니다.
*
* @note
*   (1) 이 가방의 용량은 생성 후 변경이 가능하지만,
*       최대 용량은 머신의 사용 가능한 메모리에 의해 제한됩니다.
*       생성자, addItem, clone, union 등의 메서드는 메모리가 부족하면 
*       OutOfMemoryError를 발생시킬 수 있습니다.
*   <p>
*   (2) 가방의 최대 용량은 정수 최대값인 2,147,483,647 (Integer.MAX_VALUE)를 초과할 수 없습니다.
*       이를 초과하려 할 경우 산술 오버플로우로 인해 실패합니다.
*   <p>
*   (3) 이 클래스의 알고리즘은 느린 선형 방식이기 때문에, 큰 데이터셋에서는 성능이 저조할 수 있습니다.
*
******************************************************************************/
public class IntArrayBag implements Cloneable
{
   // IntArrayBag 클래스의 불변식 (Invariant):
   //   1. 가방에 있는 요소 수는 manyItems 변수에 저장되며, 이 값은 data.length를 넘지 않습니다.
   //   2. 가방이 비어 있을 때는 data 배열의 내용은 상관없습니다.
   //      가방이 비어 있지 않다면, 요소는 data[0]부터 data[manyItems-1]까지 저장되며,
   //      그 외 영역의 값은 중요하지 않습니다.
   private int[] data;
   private int manyItems;

   /**
    * 초기 용량 10으로 빈 가방을 생성합니다.
    * @postcondition
    *   이 가방은 비어 있으며 초기 용량은 10입니다.
    * @exception OutOfMemoryError
    *   new int[10]을 위한 메모리가 부족한 경우 발생합니다.
    */
   public IntArrayBag() {
      final int INITIAL_CAPACITY = 10;
      manyItems = 0;
      data = new int[INITIAL_CAPACITY];
   }

   /**
    * 지정된 초기 용량으로 빈 가방을 생성합니다.
    * @param initialCapacity
    *   이 가방의 초기 용량
    * @precondition
    *   initialCapacity는 0 이상이어야 합니다.
    * @postcondition
    *   이 가방은 비어 있으며 지정된 초기 용량을 가집니다.
    * @exception IllegalArgumentException
    *   initialCapacity가 음수인 경우 발생합니다.
    * @exception OutOfMemoryError
    *   메모리 부족으로 배열을 만들 수 없는 경우 발생합니다.
    */
   public IntArrayBag(int initialCapacity) {
      if (initialCapacity < 0)
         throw new IllegalArgumentException("The initialCapacity is negative: " + initialCapacity);
      data = new int[initialCapacity];
      manyItems = 0;
   }

   /**
    * 가방에 새로운 요소를 하나 추가합니다.
    * @param element
    *   추가할 요소
    * @postcondition
    *   요소의 복사본이 가방에 추가됩니다.
    * @exception OutOfMemoryError
    *   용량 확장 시 메모리 부족한 경우 발생합니다.
    */
   public void add(int element) {
      if (manyItems == data.length) {
         ensureCapacity((manyItems + 1) * 2);
      }
      data[manyItems++] = element;
   }

   /**
    * 여러 요소를 가방에 한 번에 추가합니다.
    * @param elements
    *   추가할 요소들 (가변 인자)
    * @postcondition
    *   요소들의 복사본이 가방에 추가됩니다.
    * @exception OutOfMemoryError
    *   용량 확장 시 메모리 부족한 경우 발생합니다.
    */
   public void addMany(int... elements) {
      if (manyItems + elements.length > data.length) {
         ensureCapacity((manyItems + elements.length) * 2);
      }
      System.arraycopy(elements, 0, data, manyItems, elements.length);
      manyItems += elements.length;
   }

   /**
    * 다른 가방의 모든 요소를 이 가방에 추가합니다.
    * @param addend
    *   추가할 다른 가방
    * @precondition
    *   addend는 null이 아니어야 합니다.
    * @postcondition
    *   addend의 모든 요소가 이 가방에 추가됩니다.
    * @exception NullPointerException
    *   addend가 null인 경우 발생합니다.
    * @exception OutOfMemoryError
    *   메모리 부족 시 발생합니다.
    */
   public void addAll(IntArrayBag addend) {
      if (addend == null) throw new NullPointerException("addend cannot be null.");
      ensureCapacity(manyItems + addend.manyItems);
      System.arraycopy(addend.data, 0, data, manyItems, addend.manyItems);
      manyItems += addend.manyItems;
   }

   /**
    * 이 가방의 복사본을 생성합니다.
    * @return
    *   이 가방의 독립적인 복사본
    * @exception OutOfMemoryError
    *   복사본 생성을 위한 메모리가 부족한 경우 발생합니다.
    */
   public IntArrayBag clone() {
      IntArrayBag answer;
      try {
         answer = (IntArrayBag) super.clone();
      } catch (CloneNotSupportedException e) {
         throw new RuntimeException("This class does not implement Cloneable");
      }
      answer.data = data.clone();
      return answer;
   }

   /**
    * 특정 요소가 가방에 몇 번 나타나는지 셉니다.
    * @param target
    *   찾고자 하는 요소
    * @return
    *   요소의 발생 횟수
    */
   public int countOccurrences(int target) {
      int count = 0;
      for (int i = 0; i < manyItems; i++) {
         if (data[i] == target) count++;
      }
      return count;
   }

   /**
    * 가방의 용량을 최소한 지정된 값 이상으로 확장합니다.
    * @param minimumCapacity
    *   확장할 최소 용량
    * @postcondition
    *   가방의 용량이 minimumCapacity 이상이 됩니다.
    * @exception OutOfMemoryError
    *   메모리 부족으로 인해 확장 불가할 경우 발생합니다.
    */
   public void ensureCapacity(int minimumCapacity) {
      if (data.length < minimumCapacity) {
         int[] biggerArray = new int[minimumCapacity];
         System.arraycopy(data, 0, biggerArray, 0, manyItems);
         data = biggerArray;
      }
   }

   /**
    * 현재 가방의 용량을 반환합니다.
    * @return
    *   가방의 배열 용량
    */
   public int getCapacity() {
      return data.length;
   }

   /**
    * 특정 요소를 가방에서 한 번 제거합니다.
    * @param target
    *   제거할 요소
    * @postcondition
    *   요소가 존재했다면 하나가 제거되고 true를 반환합니다.
    *   존재하지 않았다면 false를 반환합니다.
    */
   public boolean remove(int target) {
      for (int i = 0; i < manyItems; i++) {
         if (data[i] == target) {
            manyItems--;
            data[i] = data[manyItems];
            return true;
         }
      }
      return false;
   }

   /**
    * 가방에 들어있는 요소 수를 반환합니다.
    * @return
    *   현재 요소 수
    */
   public int size() {
      return manyItems;
   }

   /**
    * 가방의 용량을 현재 요소 수에 맞게 줄입니다.
    * @postcondition
    *   배열 용량이 요소 수와 같아집니다.
    * @exception OutOfMemoryError
    *   메모리 부족으로 배열 축소에 실패할 경우 발생합니다.
    */
   public void trimToSize() {
      if (data.length != manyItems) {
         int[] trimmedArray = new int[manyItems];
         System.arraycopy(data, 0, trimmedArray, 0, manyItems);
         data = trimmedArray;
      }
   }

   /**
    * 두 가방을 합쳐 새로운 가방을 생성합니다.
    * @param b1
    *   첫 번째 가방
    * @param b2
    *   두 번째 가방
    * @precondition
    *   b1과 b2는 null이 아니며,
    *   b1.getCapacity() + b2.getCapacity() <= Integer.MAX_VALUE 여야 합니다.
    * @return
    *   두 가방의 합집합
    * @exception NullPointerException
    *   인자가 null인 경우 발생합니다.
    * @exception OutOfMemoryError
    *   새로운 가방 생성에 필요한 메모리가 부족한 경우 발생합니다.
    */
   public static IntArrayBag union(IntArrayBag b1, IntArrayBag b2) {
      if (b1 == null || b2 == null) throw new NullPointerException("One or both bags are null.");
      IntArrayBag answer = new IntArrayBag(b1.getCapacity() + b2.getCapacity());
      System.arraycopy(b1.data, 0, answer.data, 0, b1.manyItems);
      System.arraycopy(b2.data, 0, answer.data, b1.manyItems, b2.manyItems);
      answer.manyItems = b1.manyItems + b2.manyItems;
      return answer;
   }
}

• IntArrayBag은 int [] 배열을 활용하여서 정수들을 저장하는 데이터 타입이다.

private int[] data;
private int manyItems;

• data: 실제로 정수들을 저장하는 배열
• manyItems: 현제 가방에 들어 있는 요소의 개수

생성자

public IntArrayBag()

• 기본 용량 10으로 가방을 초기화해준다.
• 내부 배열의 크기는 10으로 되고, 요소의 수는 0이다.

public IntArrayBag(int initialCapacity)

• 원하는 용량으로 초기화가 가능하다.
• 단 음수값이 매개변수로 들어오면 IllegalArgumentException이 발생한다.

메서드

public void add(int element)

• 데이터가 꽉 찼는지 검사하고 꽉 찼다면 용량을 두 배로 늘려 준다.
• 요소를 마지막 위치에 추가해 준다. (data [manyItems] = element)
• manyItem++ 을 해서 요소의 개수를 증가해 준다.

public void addMany(int... elements)

• 여러 인자를 한 번에 추가해 준다. (elements는 가변인자를 활용해 줌)
• elements의 길이와 manyItems의 개수가 배열 공간보다 크다면 2배만큼 확장해 준다.

if (manyItems + elements.length > data.length) {
   ensureCapacity((manyItems + elements.length) * 2);
}

• System.arraycopy()로 elements를 복사해 준다.
• 마지막에 elements.length만큼을 manyItems에 더해준다.

public void addAll(IntArrayBag addend)

• addend가 null인지 먼저 확인해 주고 null인 경우에는 예외 발생해 준다.
• 그다음에는 ensureCapcity로 공간을 미리 확보해 준다.
• System.arraycopy()로 addend.data→this.data 에 복사해 준다.
• manyItems는 addend의 길이만큼 증가시켜 준다.

public int countOccurrences(int target)

• target이 몇 개 있는지 세는 기능을 한다.

public boolean remove(int target)

• target 값을 한 번만 삭제한다.
• 0번부터 끝까지 순회하면서 값을 찾으면 data [manyItems-1]로 현제 위치를 대체해 주고 manyItems은 1을 빼준다.
• 만약 못 찾으면 false를 리턴해준다.

public IntArrayBag clone()

• 가방 전체를 복사해 준다. 
• super.clone()으로 얕은 복사를 해주고 data도. clone으로 깊은 복사를 해준다.
• 완전히 독립적인 복사된 객체를 리턴해준다.

public void ensureCapacity(int minimumCapacity)

• minimumCapcity이상으로 확장해 준다.
• 만약 minmumCapacity보다 작다면 새 배열을 만들고 System.arraycopy() 복사해 준다.

public void trimToSize()

• 배열의 사이즈를 manyItems, 즉 원소의 개수에 맞춰서 줄여준다.
• data.length!=manyItems인 경우에만 작동한다.

public int getCapacity()

• 배열의 전체 크기를 반환해 준다. (=data.length)

public int size()

• 가방에 들어 있는 원소의 개수를 반환해준다. (=manyItems)

public static IntArrayBag union(IntArrayBag b1, IntArrayBag b2)

• 두 가방을 합쳐 새로운 가방을 반환해준다.
• 둘 중에 null 값이 있으면 예외 발생해 준다.
• answer 객체에는 두 객체의 배열 사이즈의 합만큼의 배열을 만들어 준다.
• 그 후에는 System.arraycopy()로 두 배열을 answer에 복사해 준다.
• answer의 manyItems 또한 업데이트해주는 것을 잊으면 안 된다.

실행 예제

public class IntArrayBagTest {
    public static void main(String[] args) {
        IntArrayBag bag1 = new IntArrayBag();
        bag1.add(10);
        bag1.add(20);
        bag1.addMany(30, 40, 20);

        System.out.println("Bag1 Size: " + bag1.size()); // 5
        System.out.println("Occurrences of 20: " + bag1.countOccurrences(20)); // 2

        IntArrayBag bag2 = new IntArrayBag();
        bag2.addMany(50, 60);

        IntArrayBag unionBag = IntArrayBag.union(bag1, bag2);
        System.out.println("Union Bag Size: " + unionBag.size()); // 7

        bag1.remove(20);
        System.out.println("Bag1 Size After Removal: " + bag1.size()); // 4
        System.out.println("Occurrences of 20 after one removal: " + bag1.countOccurrences(20)); // 1

        bag1.trimToSize();
        System.out.println("Bag1 Capacity After Trim: " + bag1.getCapacity()); // 4
    }
}

Bag1 Size: 5
Occurrences of 20: 2
Union Bag Size: 7
Bag1 Size After Removal: 4
Occurrences of 20 after one removal: 1
Bag1 Capacity After Trim: 4