لطفا منتظر باشید ...
2.7 An Integer List
Example 2-7 is a class that implements a list or growable array of
int values. This IntList class
is like the java.util.ArrayList class, but it
works with primitive int values rather than
objects. When you need to store int values and do
not know the number of values in advance (i.e., you
can't use an array), IntList is
much more efficient than using an ArrayList
because there is no need to wrap your int values
in Integer objects. The interesting thing about
this example is not its efficiency, however, but the fact that it is
a real-world example: the code is nontrivial but easy to understand,
and the class actually serves a useful purpose.Also interesting is the fact that this class overrides a number of
methods inherited from Object in order to provide
meaningful implementations. Like the ComplexNumber
class of Example 2-5, this class defines a
toString( ) method to convert its state to a
textual representation that can be displayed in log messages,
debugging statements, and elsewhere. Additionally, it overrides the
equals( ) method to determine if two
IntList objects are equal. It also overrides the
hashCode( ) method to provide a compatible
implementation that ensures that IntList objects
that are equal have the same hash code. This enables
IntList objects to be used as keys in hashtables
such as the java.util.HashMap class.The Object class also defines the clone(
)
or finalize( ) methods, but neither method is recommend
for general use, and IntList does not override
either one. The requirements for the clone( )
method are ill-defined, and it is hard to implement this method
correctly. Instead of providing a clone( ) method,
IntList defines a "copy
constructor" to create a new
IntList that is an exact copy of the old one.In addition to methods inherited from Object, the
IntList class implements the
Comparable interface and its compareTo(
) method. This method defines an ordering for
IntList objects, allowing them to be compared and
sorted.The book Effective Java Programming Language
Guide, by Joshua Bloch (Addison-Wesley), contains a
particularly helpful discussion about implementing the
toString( ), equals( ),
hashCode( ), compareTo( ),
clone( ), and finalize( )
methods.One final feature to note about the IntList
example is that the nonpublic setCapacity(
) method uses an assert
statement to verify that it has been called correctly.
assert was added to the Java language in Java 1.4,
and for backward compatibility, this code will compile only if you
use the -source 1.4 option to
javac:
javac -source 1.4 IntList.java
If you are using Java 1.3 or before, just comment out the
assert keyword to make the class compile. The
Java interpreter does not
test assertions by default. If you develop a program that uses the
IntList class, you should enable assertions during
your development and testing process by passing the
-ea option to the java
command:
java -ea MyIntListTestProgram
If you do this, then each time it is called, the
setCapacity( ) method will verify that it is not
being asked to set the list capacity to less than the list size
(which would mean a loss of data). We'll see test
programs that use the
IntListChapter 10.
Example 2-7. IntList.java
package je3.classes;
/**
* A growable array of primitive int values. It is more efficient than
* ArrayList or Vector because Integer objects are not used.
**/
public class IntList implements Comparable {
// These are the fields of this class.
// They are protected so that subclasses can access them directly.
protected int[ ] data; // This array holds the integers
protected int size; // This is how many it currently holds
// Static final values are constants. This one is private.
private static final int DEFAULT_CAPACITY = 8;
// This no-argument constructor creates an IntList with a default capacity
public IntList( ) { this(DEFAULT_CAPACITY); }
// This constructor allows us to specify the initial size. Useful when
// we have an approximate idea of how big the list will need to be.
public IntList(int initialCapacity) {
// We don't have to set size to zero because newly created objects
// automatically have their fields set to zero, false, and null.
data = new int[initialCapacity]; // Allocate the array
}
// This constructor returns a copy of an existing IntList.
public IntList(IntList original) {
// All arrays are Cloneable, and their clone( ) method is an easy way
// to copy them. Cloneable is ill-defined and hard to implement
// correctly, however, so it is not usually worth making your classes
// cloneable. A copy constructor like this one is a good alternative.
this.data = (int[ ]) original.data.clone( );
this.size = original.size;
}
// Return the number of ints stored in the list
public int size( ) { return size; }
// Return the int stored at the specified index
public int get(int index) {
if (index < 0 || index >= size) // Check that argument is legitimate
throw new IndexOutOfBoundsException(String.valueOf(index));
return data[index];
}
// Append a new value to the list, reallocating if necessary
public void add(int value) {
if (size == data.length) setCapacity(size*2); // realloc if necessary
data[size++] = value; // add value to list
}
// Set the value at the specified index
public void set(int index, int value) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(String.valueOf(index));
data[index] = value;
}
// Shrink the list so that its capacity is the same as its size.
// This is useful to free up unneeded memory when we know the list
// will not have any new values added to it.
public void trim( ) { setCapacity(size); }
// Remove all elements from the list
public void clear( ) { size = 0; }
// Copy the contents of the list into a new array and return that array
public int[ ] toArray( ) {
int[ ] copy = new int[size];
System.arraycopy(data, 0, copy, 0, size);
return copy;
}
// This is a very useful method, especially for logging and debugging.
// Consider overriding it in every class you write.
public String toString( ) {
// Repetitive string contatenation with the + operator is inefficient.
// It is much better to use a StringBuffer here. In Java 1.5, use
// StringBuilder instead.
StringBuffer b = new StringBuffer(size*7); // Guess string length
b.append('['); // Start the array
for(int i = 0; i < size; i++) { // Loop through list elements
if (i > 0) { // If not the first element
b.append(", "); // put a comma before it
if (i%8 == 0) b.append('\n'); // newline every 8 elements
}
b.append(data[i]); // append a number
}
b.append(']'); // end the array.
return b.toString( ); // Return as a string
}
// Does this object contain the same values as the object o?
// This is an Object method that we override. Note that we must also
// override hashCode( ) to match this.
public boolean equals(Object o) {
// If o is the same object as this, then they are equal
if (o == this) return true;
// If o is null or of the wrong type, it is not equal
if (!(o instanceof IntList)) return false;
// It is an IntList, so we can cast it, and compare this to that.
IntList that = (IntList) o;
// If the lists have different sizes, they are not equal
// Note that equal lists may have different array lengths.
if (this.size != that.size) return false;
// If any of their elements differ, then they are not equal
for(int i = 0; i < this.size; i++)
if (this.data[i] != that.data[i]) return false;
// If we get here, then the two lists contain exactly the same values
// in the same positions, so they are equal
return true;
}
// Map this object to an integer hash code used for hashtable data
// structures. Objects that are equal( ) must have the same hashCode( ), so
// we always override this method when we override equals( ).
// Note that non-equal objects may have the same hashCode( ), but we strive
// to minimize that possibility.
public int hashCode( ) {
// It would be legal to just add the values up and return that as
// the hash code, but then the list [1,2,3] would have the same hash
// code as [3,2,1] and [3,3], which is not desired behavior. Using
// multiplication and addition here makes the result dependent on
// order, and spreads codes out across the full range of ints.
int code = 1; // non-zero to hash [0] and [ ] to distinct values
for(int i = 0; i < size; i++)
code = code*997 + data[i]; // ignore overflow
return code;
}
/**
* The compareTo( ) method is defined by the Comparable interface.
* It defines an ordering for IntList objects and allows them to be sorted.
*
* Return a negative value if this object is "less than" the argument.
* Return a postive value if this object is "greater than" the argument.
* Return zero if the two objects are equal.
* The first list value that differs is used to determine ordering.
* If one list is a prefix of the other, then the longer list is greater.
*/
public int compareTo(Object o) {
// Cast the argument to an IntList. This will correctly throw
// CastClassException if the wrong type is passed
IntList that = (IntList) o;
int n = Math.min(this.size, that.size); // get length of shorter list
// Compare elements of the two lists, looking for one that differs
for(int i = 0; i < n; i++) {
if (this.data[i] < that.data[i]) return -1;
if (this.data[i] > that.data[i]) return 1;
}
// If we get here, then the lists are equal, or one is a prefix
// of the other.
return this.size - that.size;
}
// Reallocate the data array to enlarge or shrink it.
// This is a non-public method used internally to grow or trim( ) the array.
protected void setCapacity(int n) {
// We use a Java 1.4 assertion to make sure the class is calling
// this private method correctly. Compile with "-source 1.4" to make
// the compiler recognize this statement and run with "-ea" to make
// the VM actually test the assertion.
// Syntax: assert <condition> : <error message>
assert (n >= size) : (n + "<" +size);
if (n == data.length) return; // Check size
int[ ] newdata = new int[n]; // Allocate the new array
System.arraycopy(data, 0, newdata, 0, size); // Copy data into it
data = newdata; // Replace old array
}
}
