在 Java 中将 Bag 实现为数组

Bag implementation as array in Java

提问by user481211

I'm supposed to implement a bag data structure (also called a multiset), an unordered collection of homogeneous values (any Java object, excluding null) that may have duplicates, for a project. I've done extensive searching on the internet but have a hard time wrapping my mind around using arrays instead of something like List and don't quite understand the syntax for using arrays in a class.

我应该为一个项目实现一个包数据结构（也称为多集），一个无序的同构值集合（任何 Java 对象，不包括空值），可能有重复项。我已经在互联网上进行了大量搜索，但很难集中精力使用数组而不是 List 之类的东西，并且不太了解在类中使用数组的语法。

I need to implement all of java.util.Collection except as noted by throwing an UnsupportedOperationException. Yes, I HAVE to use an array and when I add to it, the capacity must increase by 10. My problem is that I'm not sure what to do about the containsmethod, clearmethod, addAllmethod, and a second constructor. Hopefully everything else I've added will also run smoothly. I've included the API definition in comment blocks. Any input at all would really help me.

我需要实现所有 java.util.Collection 除非抛出 UnsupportedOperationException 。是的，我必须使用一个数组，当我添加到它时，容量必须增加 10。我的问题是我不确定如何处理contains方法、clear方法、addAll方法和第二个构造函数。希望我添加的其他所有内容也能顺利运行。我已经在注释块中包含了 API 定义。任何输入都会真正帮助我。

As Mark asked below, I don't understand how to search through the bag to search for a particular element.

正如马克在下面问的那样，我不明白如何搜索包来搜索特定元素。

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; 
    }
}

回答by ColinD

I'm confused about what you have inside contains... you're calling toArray()on an Object, which doesn't have a toArray()method. This suggests some fundamental misunderstanding of what you're trying to do. Despite that, you actually do seem to know how to check if the collection contains a given object, because you have to find the object in order to removeit. Your removemethod returns the exact same booleanvalue that containswould have if called with the same object. I think you can work from that.

我对你里面的东西感到困惑contains......你正在调用toArray()一个Object没有toArray()方法的 。这表明您对您正在尝试做的事情存在一些根本性的误解。尽管如此，您实际上似乎知道如何检查集合是否包含给定对象，因为您必须找到该对象才能找到remove它。您的remove方法返回的boolean值contains与使用相同对象调用时的值完全相同。我认为你可以从中工作。

(Your removemethod has a bug that could cause a memory leak, by the way... when it shifts the objects in the array to the left by 1, it doesn't set the array slot that is no longer included in the collection to null.)

（remove顺便说一下，您的方法有一个可能导致内存泄漏的错误......当它将数组中的对象向左移动 1 时，它不会将不再包含在集合中的数组槽设置为null.)

addAllis quite simple... you're given a Collectionof elements that all need to be added, and you have an addmethod that can add an element. These go together. (addAllis all you really need to implement your second constructor as well.)

addAll很简单......你得到了一个Collection所有需要add添加的元素，并且你有一个可以添加元素的方法。这些一起去。（这addAll也是您真正需要实现第二个构造函数的全部内容。）

clearis also simple. After calling it, your array needs to have no references to any objects and the size of your bag needs to be 0. Just think about how you can do that.

clear也很简单。调用它后，您的数组不需要引用任何对象，并且您的包的大小需要为 0。想想如何做到这一点。

A working implementation of iterator()would help you quite a bit as many Collectionmethods (including clear) can be implemented by making use of the collection's Iterator(the convenient abstract class AbstractCollectiondoes this), but implementing that is a bit more difficult than just implementing a basic clearthat doesn't use it probably.

的工作实现iterator()将帮助您很多Collection方法（包括clear）可以通过使用集合的Iterator（方便的抽象类AbstractCollection执行此操作）来实现，但是实现它比仅仅实现一个clear没有的基本方法要困难一些可能不会使用它。

Also, a small note.

另外，一个小笔记。

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

would be better written as:

最好写成：

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

Since size() == 0is already a booleanexpression, the if/elseis redundant.

由于size() == 0已经是一个boolean表达式，所以if/else是多余的。

回答by Aravind Yarram

You can use the guava's Multiset implementation as a reference. That will give you some idea http://guava-libraries.googlecode.com/svn/trunk/src/com/google/common/collect/

您可以使用 guava 的 Multiset 实现作为参考。这会给你一些想法 http://guava-libraries.googlecode.com/svn/trunk/src/com/google/common/collect/