ResizingArrayBag.java
4.55 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/******************************************************************************
* Compilation: javac ResizingArrayBag.java
* Execution: java ResizingArrayBag
* Dependencies: StdIn.java StdOut.java
*
* Bag implementation with a resizing array.
*
******************************************************************************/
package edu.princeton.cs.algs4;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* The {@code ResizingArrayBag} class represents a bag (or multiset) of
* generic items. It supports insertion and iterating over the
* items in arbitrary order.
* <p>
* This implementation uses a resizing array.
* See {@link LinkedBag} for a version that uses a singly-linked list.
* The <em>add</em> operation takes constant amortized time; the
* <em>isEmpty</em>, and <em>size</em> operations
* take constant time. Iteration takes time proportional to the number of items.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class ResizingArrayBag<Item> implements Iterable<Item> {
private Item[] a; // array of items
private int n; // number of elements on bag
/**
* Initializes an empty bag.
*/
public ResizingArrayBag() {
a = (Item[]) new Object[2];
n = 0;
}
/**
* Is this bag empty?
* @return true if this bag is empty; false otherwise
*/
public boolean isEmpty() {
return n == 0;
}
/**
* Returns the number of items in this bag.
* @return the number of items in this bag
*/
public int size() {
return n;
}
// resize the underlying array holding the elements
private void resize(int capacity) {
assert capacity >= n;
Item[] temp = (Item[]) new Object[capacity];
for (int i = 0; i < n; i++)
temp[i] = a[i];
a = temp;
}
/**
* Adds the item to this bag.
* @param item the item to add to this bag
*/
public void add(Item item) {
if (n == a.length) resize(2*a.length); // double size of array if necessary
a[n++] = item; // add item
}
/**
* Returns an iterator that iterates over the items in the bag in arbitrary order.
* @return an iterator that iterates over the items in the bag in arbitrary order
*/
public Iterator<Item> iterator() {
return new ArrayIterator();
}
// an iterator, doesn't implement remove() since it's optional
private class ArrayIterator implements Iterator<Item> {
private int i = 0;
public boolean hasNext() { return i < n; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return a[i++];
}
}
/**
* Unit tests the {@code ResizingArrayBag} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
ResizingArrayBag<String> bag = new ResizingArrayBag<String>();
bag.add("Hello");
bag.add("World");
bag.add("how");
bag.add("are");
bag.add("you");
for (String s : bag)
StdOut.println(s);
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/