Javaの配列としてのバッグの実装

Question

私は、プロジェクトのために、重複している可能性のある均一な値（任意のJavaオブジェクト、nullを除く）の順序付けられていないコレクションであるバッグデータ構造（マルチセットとも呼ばれます）を実装することになっています。私はインターネットで広範囲に検索しましたが、リストのようなものではなく配列を使用して心を包むのに苦労しており、クラスで配列を使用するための構文を十分に理解していません。

unsupportedoperationexceptionを投げることによって指摘されている場合を除き、すべてのjava.util.collectionを実装する必要があります。はい、アレイを使用する必要があり、それに追加するとき、容量は10増加する必要があります。私の問題は、何をすべきかわからないということです。 含む 方法、 クリア 方法、 全て追加する メソッド、および2番目 コンストラクタ. 。うまくいけば、私が追加した他のすべてがスムーズに実行されることを願っています。コメントブロックにAPI定義を含めました。どんな入力も本当に私を助けてくれるでしょう。

以下にマークが尋ねたように、特定の要素を検索するためにバッグを検索する方法がわかりません。

import java.util.Collection;
import java.util.Iterator;

class Bag<T> implements Collection<T>{
private T[] array;
public int bagSize;


public Bag(){
    array=(T[])new Object[10];
}
public Bag(Collection<T> other ){
    //Not sure what to put here
    //creates a bag containing all of the items passed to it as a Collection<T>
}

public int size() {
    return bagSize; 
}

public boolean isEmpty() {
    if(size()==0)
        return true;
    else
        return false;
}


public boolean contains(Object o) {
    //Not sure what to put here
    /*Returns true if this collection contains the specified element. More formally,
    returns true if and only if this collection contains at least one element e such 
    that (o==null ? e==null : o.equals(e)). */
    return (o.toArray()==null ? this.toArray()==null : o.toArray() == this.toArray());
    }

}


public Iterator<T> iterator() {
    throw new UnsupportedOperationException("not implemented.");
}

public Object[] toArray() {
    return array;

}

public <T> T[] toArray(T[] a) {
    throw new UnsupportedOperationException("not implemented.");
}

public boolean add(T e) {
   if(bagSize>=array.length)
       return false;
   else
   {
       ensureCapacity(bagSize+10);
       array[bagSize]=e;
       bagSize++;
       return true;
   }

}

public boolean remove(Object o) {
    for(int i=0; i<bagSize; i++)
        if(array[i].equals(o)){
            for(int j=i; j<bagSize-1; j++)
                array[j]=array[j+1];
            bagSize--;
            return true;
        }
    return false;

}

public boolean containsAll(Collection<?> c) {
    throw new UnsupportedOperationException("not implemented.");
}

public boolean addAll(Collection<? extends T> c) {
    //Not sure what to put here
    /*Adds all of the elements in the specified collection to this collection  
    (optional operation). The behavior of this operation is undefined if the specified
    collection is modified while the operation is in progress. (This implies that the
    behavior of this call is undefined if the specified collection is this collection,
    and this collection is nonempty.) */
}

public boolean removeAll(Collection<?> c) {
    throw new UnsupportedOperationException("not implemented.");
}

public boolean retainAll(Collection<?> c) {
    throw new UnsupportedOperationException("not implemented.");
}

public void clear() {
    //Not sure what to put here
    /*Removes all of the elements from this collection (optional operation). The
    collection will be empty after this call returns (unless it throws an exception).*/
}

@Override
public int hashCode(){
    throw new UnsupportedOperationException("not implemented.");
}

@Override
public boolean equals(Object e) {
    if (e == null) {
        return false;
    }
    if (getClass() != e.getClass()) {
        return false;
    }
    final Bag<T> other = (Bag<T>) e;
    return true;
}

public void ensureCapacity(int minCapacity){
    T[] biggerArray;
    if(array.length<minCapacity){
        biggerArray=(T[]) new Object[minCapacity];
        System.arraycopy(array, 0, biggerArray, 0, bagSize);
        array=biggerArray; 
    }
}

Answer 1

私はあなたが中に持っているものについて混乱しています contains...あなたは呼んでいます toArray() で Object, 、それはありません toArray() 方法。これは、あなたがやろうとしていることの根本的な誤解を示唆しています。それにもかかわらず、あなたは実際に、コレクションに特定のオブジェクトが含まれているかどうかを確認する方法を知っているようです。 remove それ。あなたの remove メソッドはまったく同じものを返します boolean それを大切にします contains 同じオブジェクトで呼び出された場合。あなたはそれから働くことができると思います。

（あなたの remove 方法では、メモリリークを引き起こす可能性のあるバグがあります。ちなみに...アレイのオブジェクトを左にシフトすると、コレクションに含まれていないアレイスロットを設定しません。 null.)

addAll 非常に簡単です...あなたは与えられています Collection すべてを追加する必要があり、あなたは add 要素を追加できる方法。これらは一緒に行きます。 （addAll 2番目のコンストラクターも実際に実装する必要があります。）

clear シンプルです。それを呼び出した後、アレイはオブジェクトへの参照を持たず、バッグのサイズは0である必要があります。

の実装実装 iterator() かなり多くの人を助けるでしょう Collection 方法（を含む clear）コレクションを使用することで実装できます Iterator （便利な抽象クラス AbstractCollection これを行います）、しかしそれを実装することは、基本を実装するよりも少し難しいです clear それはおそらくそれを使用していません。

また、小さなメモ。

public boolean isEmpty() {
    if(size()==0)
        return true;
    else
        return false;
}

次のように書かれた方が良いでしょう

public boolean isEmpty() {
  return size() == 0;
}

以来 size() == 0 すでにです boolean 表現、 if/else 冗長です。

Answer 2

Guavaのマルチセット実装を参照として使用できます。それはあなたにいくつかのアイデアを与えるでしょうhttp://guava-libraries.googlecode.com/svn/trunk/src/com/google/common/collect/