Java-数据结构-Bag（单链表）

  1 package model.API;
  2 
  3 
  4 import java.util.Iterator;
  5 import java.util.NoSuchElementException;
  6 
  7 public class bag<E> implements Cloneable, Iterable<E> {
  8     private E[] data;
  9     private int manyItems;
 10 
 11     public Iterator<E> iterator() {
 12         return new bagIterator();
 13     }
 14 
 15     private class bagIterator implements Iterator<E> {
 16         private int current = 0;
 17 
 18         public boolean hasNext() {
 19             return current < size();
 20         }
 21 
 22         public E next() {
 23             if (!hasNext()) {
 24                 throw new NoSuchElementException();
 25             }
 26             return data[current++];
 27         }
 28 
 29     }
 30 
 31     public bag() {
 32         final int INITIAL_CAPACITY = 10;
 33         manyItems = 0;
 34         data = (E[]) new Object[INITIAL_CAPACITY];
 35     }
 36 
 37     public bag(int initialCapacity) {
 38         if (initialCapacity < 0)
 39             throw new IllegalArgumentException("The initialCapacity is negative: " + initialCapacity);
 40         manyItems = 0;
 41         data = (E[]) new Object[initialCapacity];
 42     }
 43 
 44     public int size() {
 45         return manyItems;
 46     }
 47 
 48     public int getCapacity() {
 49         return data.length;
 50     }
 51 
 52     public void ensureCapacity(int minimumCapacity) {
 53         E biggerArray[];
 54         if (data.length < minimumCapacity) {
 55             biggerArray = (E[]) new Object[minimumCapacity];
 56             System.arraycopy(data, 0, biggerArray, 0, manyItems);
 57             data = biggerArray;
 58         }
 59     }
 60 
 61     public void add(E element) {
 62         if (manyItems == data.length) {
 63             ensureCapacity((manyItems + 1) * 2);
 64         }
 65         data[manyItems++] = element;
 66     }
 67 
 68     public void addAll(bag<E> addend) {
 69         ensureCapacity(manyItems + addend.manyItems);
 70         System.arraycopy(addend.data, 0, data, manyItems, addend.manyItems);
 71         manyItems += addend.manyItems;
 72     }
 73 
 74     //相当于一个数组,能够传入0个至n个参数
 75     public void addMany(E... elements) {
 76         if (manyItems + elements.length > data.length) {
 77             ensureCapacity((manyItems + elements.length) * 2);
 78         }
 79         System.arraycopy(elements, 0, data, manyItems, elements.length);
 80         manyItems += elements.length;
 81     }
 82 
 83     public bag<E> clone() {
 84         bag<E> copy;
 85         try {
 86             copy = (bag<E>) super.clone();
 87         } catch (CloneNotSupportedException e) {
 88             throw new RuntimeException("This class does not implement Cloneable");
 89         }
 90         copy.data = data.clone();
 91         return copy;
 92     }
 93 
 94     public boolean remove(E target) {
 95         int index;
 96         for (index = 0; (index < manyItems) && !target.equals(data[index]); index++) ;//对象比较
 97         if (index == manyItems) return false;
 98         else {
 99             data[index] = data[--manyItems];
100             return true;
101         }
102     }
103 
104     public int removeMany(E... targets) {
105         int count = 0;
106         for (E target : targets)
107             if (remove(target))
108                 count++;
109         return count;
110     }
111 
112     public void trimToSize() {
113         E[] trimmedArray;
114         if (data.length != manyItems) {
115             trimmedArray = (E[]) new Object[manyItems];
116             System.arraycopy(data, 0, trimmedArray, 0, manyItems);
117             data = trimmedArray;
118         }
119     }
120 
121 }
~~Jason_liu O(∩_∩)O