Реализация сумки как массив в Java

Question

Я должен реализовать структуру данных сумки (также называемой мультисетом), неупорядоченную коллекцию однородных значений (любой объект Java, исключая NULL), которые могут иметь дубликаты для проекта. Я сделал обширный поиск в Интернете, но увлекательно разочаровываю разум, используя массивы вместо чего-то вроде списка и не совсем понимаю синтаксис для использования массивов в классе.

Мне нужно реализовать все java.util.collection, за исключением того, как отмечено, выбрасывая отказа от неподтвердующей поддержки. Да, я должен использовать массив и когда я добавляю к нему, емкость должна увеличиться на 10. Моя проблема в том, что я не уверен, что делать с содержит метод, ясно метод, добавить все метод и второй конструктор. Отказ Надеюсь, все остальное, что я добавил, также будет работать гладко. Я включил определение 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 Метод имеет ошибку, которая может привести к утечке памяти, кстати ... когда она сдвигает объекты в массиве влево на 1, он не устанавливает слот массива, который больше не включен в коллекцию, чтобы null.)

addAll довольно просто ... тебе дано Collection элементов, которые все нужно добавить, а у вас есть add Метод, который может добавить элемент. Они идут вместе. (addAll Это все, что вам действительно нужно также реализовать свой второй конструктор.)

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/