Transcript Slide 1

Kolekcije objekata
Programski jezici: Java
Kolekcije
MyObject myReference_1;
MyObject myReference_2;
.
.
.
MyObject myReference_n;
MyObject [] myReferences;
MyObjectCollection myReferences;
Nizovi
• Efikasnost – brz pristup pojedinacnim
elementima
• Sve vrednosti moraju biti istog (prostog ili
referencijalnog) tipa – provera se vrsi vec pri
kompajliranju
• Moze da sadrzi vrednosti prostih tipova
podataka
• Nepromenljiv kapacitet – nakon kreiranja objekta
niza, nemoguce je promeniti njegov kapacitet
class Nesto {}
public class ArraySize {
public static void main(String[] args) {
// Niz objekata:
Nesto[] a; // Neinstancirana lokalna promenljiva
Nesto[] b = new Nesto[5]; // "Prazne" (null) reference
Nesto[] c = new Nesto[4];
for(int i = 0; i < c.length; i++)
if(c[i] == null)
c[i] = new Nesto();
// Agregatna inicijalizacija:
Nesto[] d = {
new Nesto(), new Nesto(), new Nesto()
};
// Dinamicka agregatna inicijalizacija:
a = new Nesto[] {
new Nesto(), new Nesto()
};
System.out.println("a.length = " + a.length);
a.length
System.out.println("b.length = " + b.length);
b.length
// Reference unutar niza su
// automatski inicijalizovane na null:
for(int i = 0; i < b.length; i++)
System.out.println("b[" + i + "]=" + b[i]);
System.out.println("c.length = " + c.length);
c.length
System.out.println("d.length = " + d.length);
d.length
a = d;
System.out.println("a.length = " + a.length);
a.length
= 2
= 5
= 4
= 3
= 3
b[0]=null
b[1]=null
b[2]=null
b[3]=null
b[4]=null
// Niz vrednosti prostog tipa:
int[] e; // Null reference
int[] f = new int[5];
int[] g = new int[4];
for(int i = 0; i < g.length; i++)
g[i] = i*i;
int[] h = { 11, 47, 93 };
// Compile error: variable e not initialized:
//!System.out.println("e.length=" + e.length);
System.out.println("f.length = " + f.length);
// Vrednosti prostog tipa su
// automatski inicijalizovani na 0:
for(int i = 0; i < f.length; i++)
System.out.println("f[" + i + "]=" + f[i]);
System.out.println("g.length = " + g.length);
System.out.println("h.length = " + h.length);
e = h;
System.out.println("e.length = " + e.length);
e = new int[] { 1, 2 };
System.out.println("e.length = " + e.length);
}
}
f.length = 5
g.length = 4
h.length = 3
e.length = 3
e.length = 2
f[0]=0
f[1]=0
f[2]=0
f[3]=0
f[4]=0
Nizovi
• Deklaracija: void metod1(Nesto[] argument) {…}
• Nesto[] d = {
new Nesto(), new Nesto(), new Nesto()
};
• metod1(d);
• metod1(new Nesto[] {new Nesto(), new Nesto()});
• a = d; // dodela reference!
• Nesto[] metod2() {
return new Nesto[] {new Nesto(), new Nesto()}
}
Klasa java.util.Arrays
• equals( ) – poređenje jednakosti nizova
• fill( ) – popunjavanje celog niza proizvoljnom
(jednom) vrednošću
• sort( ) – sortiranje niza
• binarySearch( ) – pronalaženje elementa u
sortiranom nizu
• Svi ovi metodi su redefinisani tako da kao svoje
argumente primaju nizove prostih tipova i tipa
Object
• Metod asList( ) – vraća listu elemenata niza
import java.util.*;
public class FillingArrays {
public static String pretvori(int[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(", ");
}
result.append("]");
return result.toString();
}
public static void main(String[] args) {
int size = 6;
// Or get the size from the command line:
if(args.length != 0)
size = Integer.parseInt(args[0]);
int[] niz = new int[size];
Arrays.fill(niz, 10);
System.out.println("niz = " + pretvori(niz));
// Manipulating ranges:
Arrays.fill(niz, 3, 5, 35);
System.out.println("niz = " + pretvori(niz));
}
}
niz = [10, 10, 10, 10, 10, 10]
niz = [10, 10, 10, 35, 35, 10]
Provera jednakosti i poređenje
elemenata niza
• Relacioni operator == proverava jednakost
referenci, ne sadržaj objekata.
• Klasa Object sadrži metod
boolean equals(Object)
import java.util.*;
public class ComparingArrays {
public static void main(String[] args) {
int[] a1 = new int[10];
int[] a2 = new int[10];
Arrays.fill(a1, 47);
Arrays.fill(a2, 47);
System.out.println(Arrays.equals(a1, a2));
a2[3] = 11;
System.out.println(Arrays.equals(a1, a2));
String[] s1 = new String[5];
Arrays.fill(s1, "Hi");
String[] s2 = {"Hi", "Hi", "Hi", "Hi", "Hi"};
System.out.println(Arrays.equals(s1, s2));
}
}
Za referencijalne tipove:
Dva objekta e1 i e2 se smatraju jednakima ako je zadovoljen sledeći uslov:
(e1==null ? e2==null : e1.equals(e2))
•
Ako pisemo novu klasu, možemo da redefinišemo metod equals da bismo dobili korektno
ponašanje kada se vrši provera jednakosti njenih instanci
public class Card { // Class to represent playing cards.
int suit; // Number from 0 to 3 that codes for the suit -// spades, diamonds, clubs or hearts.
int value; // Number from 1 to 13 that represents the value.
public boolean equals(Object obj) {
if (obj == null || ! (obj instanceof Card) ) {
// obj can't be equal to this Card if obj
// is not a Card, or if it is null.
return false;
}
else {
Card other = (Card)obj; // Type-cast obj to a Card.
if (suit == other.suit && value == other.value) {
// The other card has the same suit and value as
// this card, so they should be considered equal.
return true;
}
else
return false;
}
}
... // other methods and constructors
}
Provera jednakosti i poređenje
elemenata niza
• Slican problem se javlja pri sortiranju nizova ili kontejnera. Za
proiyvoljne objekte ne postoji “prirodna” relacija poretka.
• Mora biti definisan metod za poredjenje objekata. Objekti koji bi
trebalo da se porede treba da implementiraju interfejs Comparable
koji sadrzi metod:
public int compareTo(Object obj)
• Vrednost koju vraca obj1.compareTo(obj2) bi po konvenciji trebalo
da bude:
– 0 ako je obj1.equals(obj2) tacno
– 1 ako je obj1 “vece” od obj2
– -1 ako je obj1 “manje” od obj2
• Poziv obj1.compareTo(obj2) se smatra greskom ako obj2 nije istog
tipa kao obj1
• Klasa String
class FullName implements Comparable {
String firstName, lastName;
public boolean equals(Object obj) {
if (obj == null || ! (obj instanceof FullName)) {
return false;
}
else {
FullName other = (FullName)obj;
return firstName.equals(other.firstName)
&& lastName.equals(other.lastName);
}
}
public void compareTo(Object obj) {
Fullname other = (FullName)obj;
// Will cause an error if obj is not a FullName.
if ( lastName.compareTo(other.lastName) < 0 ) {
return -1;
}
if ( lastName.compareTo(other.lastName) > 0 ) {
return 1;
}
else {
return firstName.compareTo(other.firstName);
}
}
... // other methods and constructors
}
Provera jednakosti i poređenje
elemenata niza
• Jos jedan nacin: poseban objekat koji vrsi
poredjenje.
• Mora da implementira interfejs
java.util.Comparator, koji definise metod:
public int compare(Object obj1, Object obj2)
• Povratna vrednost
• Slicnosti i razlike dve priistupa
import java.util.*;
public class StringSorting {
private static Random r = new Random();
private static String ssource =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
private static char[] src = ssource.toCharArray();
private static int len = 5;
public static void fill(String[] a) {
for(int i = 0; i < len; i++) {
char[] buf = new char[len];
for(int i = 0; i < len; i++)
buf[i] = src[r.nextInt(src.length)];
}
a[i] = new String(buf);
}
public static void main(String[] args) {
String[] sa = new String[30];
fill(sa);
System.out.println(
"Before sorting: " + Arrays.asList(sa));
Arrays.sort(sa);
System.out.println(
"After sorting: " + Arrays.asList(sa));
}
}
import java.util.*;
public class AlphabeticComparator implements Comparator {
public int compare(Object o1, Object o2) {
String s1 = (String)o1;
String s2 = (String)o2;
return s1.toLowerCase().compareTo(s2.toLowerCase());
}
}
public class AlphabeticSorting {
...
public static void fill(String[] a) {
...
}
public static void main(String[] args) {
String[] sa = new String[30];
fill(sa);
System.out.println(
"Before sorting: " + Arrays.asList(sa));
Arrays.sort(sa, new AlphabeticComparator());
System.out.println(
"After sorting: " + Arrays.asList(sa));
}
}
Kopiranje nizova
• U klasi System:
public static void arraycopy(Object src,
int srcPos,
Object dest,
int destPos,
int length)
import java.util.*;
public class CopyingArrays {
public static String pretvori(int[] a) {
...
}
public static void main(String[] args) {
int[] i = new int[3];
int[] j = new int[5];
Arrays.fill(i, 47);
Arrays.fill(j, 99);
System.out.println("i = " + pretvori(i));
System.out.println("j = " + pretvori(j));
System.arraycopy(i, 0, j, 0, i.length);
System.out.println("j = " + pretvori(j));
}
}
i = [47, 47, 47]
j = [99, 99, 99, 99, 99]
j = [47, 47, 47, 99, 99]
Kontejneri
• Java 1.0:
– Stari “Collection API” (Vector, Hashtable,
Stack, BitSet, interfejs Enumeration)
• Java 1.2:
– Novi “Collection API” (interfejsi Collection,
List, Set, Map, i specijalizovane klase koje ih
implementiraju)
• Java 1.5:
– Parametrizovani tipovi
Containers
• Collection: a group of individual elements, often with
some rule applied to them. A List must hold the
elements in a particular sequence, and a Set cannot
have any duplicate elements.
• Map: a group of key-value object pairs. At first glance,
this might seem like it ought to be a Collection of pairs,
but when you try to implement it that way the design gets
awkward, so it’s clearer to make it a separate concept.
On the other hand, it’s convenient to look at portions of a
Map by creating a Collection to represent that portion.
Thus, a Map can return a Set of its keys, a Collection of
its values, or a Set of its pairs.
import java.util.*;
public class PrintingContainers {
static Collection fill(Collection c) {
c.add("dog");
c.add("dog");
c.add("cat");
return c;
}
static Map fill(Map m) {
m.put("dog", "Bosco");
m.put("dog", "Spot");
m.put("cat", "Rags");
return m;
}
public static void main(String[] args) {
System.out.println(fill(new ArrayList()));
System.out.println(fill(new HashSet()));
System.out.println(fill(new HashMap()));
}
}
[dog, dog, cat]
[dog, cat]
{dog=Spot, cat=Rags}
Containers: unknown type
•
The “disadvantage” to using the Java containers is that you lose type
information when you put an object into a container. This happens because
the programmer of that container class had no idea what specific type you
wanted to put in the container, and making the container hold only your type
would prevent it from being a general-purpose tool. So instead, the
container holds references to Object, which is the root of all the classes, so
it holds any type. (Of course, this doesn’t include primitive types, since they
aren’t real objects, and thus, are not inherited from anything.) This is a great
solution, except:
– Because the type information is thrown away when you put an object reference
into a container, there’s no restriction on the type of object that can be put into
your container, even if you mean it to hold only, say, cats. Someone could just as
easily put a dog into the container.
– Because the type information is lost, the only thing the container knows that it
holds is a reference to an object. You must perform a cast to the correct type
before you use it.
•
On the up side, Java won’t let you misuse the objects that you put into a
container. If you throw a dog into a container of cats and then try to treat
everything in the container as a cat, you’ll get a RuntimeException when
you pull the dog reference out of the cat container and try to cast it to a cat.
public class Cat {
private int catNumber;
public Cat(int i) { catNumber = i; }
public void id() {
System.out.println("Cat #" + catNumber);
}
}
public class Dog {
private int dogNumber;
public Dog(int i) { dogNumber = i; }
public void id() {
System.out.println("Dog #" + dogNumber);
}
}
import java.util.*;
public class CatsAndDogs {
public static void main(String[] args) {
List cats = new ArrayList();
for(int i = 0; i < 7; i++)
cats.add(new Cat(i));
// Not a problem to add a dog to cats:
cats.add(new Dog(7));
for(int i = 0; i < cats.size(); i++)
((Cat)cats.get(i)).id();
// Dog is detected only at run time
}
}
Making a type-conscious ArrayList
• A more ironclad solution is to create a new class using the ArrayList,
such that it will accept only your type and produce only your type:
import java.util.*;
public class MouseList {
private List list = new ArrayList();
public void add(Mouse m) { list.add(m); }
public Mouse get(int index) {
return (Mouse)list.get(index);
}
public int size() { return list.size(); }
}
Containers: unknown type
• Java 1.5 Note:
• Java 1.5 introduces parameterized types. This makes it possible to
do generic programming in a more type-safe way.
• For example, if Shape is a class, then the type ArrayList<Shape>
represents a list that can only hold values of type Shape.
• The type name ArrayList<Shape> is used like any other type. For
example, to declare a variable and create an object of this type, you
could say "ArrayList<Shape> shapeList = new
ArrayList<Shape>()". The variable shapeList can then be used like
any other ArrayList, except that it can only hold values of type
Shape. Since the compiler knows this, it can enforce this condition
at compile time. Java 1.5 templates still only work with object types,
and not with primitive types.
Iteratori
•
•
Iterator je objekat koji se može koristiti za obilaženje kolekcije.
The Collection interface defines a method that can be used to obtain an
iterator for any collection. If coll is a collection, then coll.iterator() returns an
iterator that can be used to traverse the collection. You should think of the
iterator as a kind of generalized pointer that starts at the beginning of the
collection and can move along the collection from one item to the next.
Iterators are defined by an interface named Iterator. This interface defines
just three methods. If iter refers to an Iterator, then:
– iter.next() -- returns the next item, and advances the iterator. The return value is
of type Object. Note that there is no way to look at an item without advancing the
iterator past that item. If this method is called when no items remain, it will throw
a NoSuchElementException.
– iter.hasNext() -- returns a boolean value telling you whether there are more items
to be processed. You should test this before calling iter.next().
– iter.remove() -- if you call this after calling iter.next(), it will remove the item that
you just saw from the collection. This might produce an
UnsupportedOperationException, if the collection does not support removal of
items.
Iterators
•
Using iterators, we can write code for printing all the items in any collection.
Suppose that coll is of type Collection. Then we can say:
Iterator iter = coll.iterator();
while ( iter.hasNext() ) {
Object item = iter.next();
System.out.println(item);
}
•
The same general form will work for other types of processing. For example,
here is a subroutine that will remove all null values from any collection (as
long as that collection supports removal of values):
void removeNullValues( Collection coll ) {
Iterator iter = coll.iterator():
while ( iter.hasNext() ) {
Object item = iter.next();
if (item == null)
iter.remove();
}
}
Iterators
import java.util.*;
public class CatsAndDogs2 {
public static void main(String[] args) {
List cats = new ArrayList();
for(int i = 0; i < 7; i++)
cats.add(new Cat(i));
Iterator e = cats.iterator();
while(e.hasNext())
((Cat)e.next()).id();
}
}
Iterators
•
Java 1.5 Note: Java 1.5 introduces a new variation on the for loop that makes Iterators unnecessary in many
cases. An iterator is often used to apply the same operation to all the elements in a Collection. In Java 1.5, this
can be done with a for loop something like this: "for (Object x : c) applyOperation(x)", where c is the Collection and
x is the for-loop variable. The notation "for (Object x : c)" has the meaning "for every Object x in the Collection c do
the following." Using this notation, the drawAllShapes example could be written simply as:
void drawAllShapes( Collection shapeCollection ) {
// Precondition: Every item is non-null and belongs to the class Shape.
for (Object obj : shapeCollection) {
Shape figure = (Shape)obj;
figure.draw();
}
}
•
Using the template notation discussed in the previous Java 1.5 Note on this page, this becomes even nicer:
void drawAllShapes( Collection<Shape> shapeCollection ) {
// Precondition: Every item in shapeCollection is non-null.
for (Shape figure : shapeCollection)
figure.draw();
}
•
Note that this works not just for Collection but for other container classes such as ArrayList and Vector. In fact, it
even works for applying the same operation to all the elements in an array.
Wrapper Classes
• As noted above, Java's generic programming does not
apply to the primitive types.
• The Integer object can be used in generic data
structures and in other situations where an object is
required. The int value is stored in a private final
instance variable of the Integer object. If val refers to an
object of type Integer, you can find out what int it
contains by calling the instance method val.intValue().
There is no way to change that value. We say that an
Integer is an immutable object. That is, after it has been
constructed, there is no way to change it. (Similarly, an
object of type String is immutable.)
Wrapper Classes
• Java 1.5 Note: Java 1.5 makes it easier to use the wrapper classes
by introducing automatic conversions between the primitive types
and the wrapper types. For example, it is possible to assign a value
of type int to a variable of type Integer, and vice versa. In Java 1.5,
the statement
• Integer val = new Integer(17)
• could be replaced by
• Integer val = 17
• Similarly, it is possible to pass a value of type double to a function
that has a parameter of type Double.
• All this is especially convenient when working with templates. For
example, if integerList is a variable of type ArrayList<Integer>, you
can say "integerList.add(42)" and it will be automatically interpreted
by the compiler as "integerList.add(new Integer(42))".
Container taxonomy
Container taxonomy
•
The interfaces that are concerned with holding objects are Collection, List,
Set, and Map. Ideally, you’ll write most of your code to talk to these
interfaces, and the only place where you’ll specify the precise type you’re
using is at the point of creation. So you can create a List like this:
List x = new LinkedList();
•
Of course, you can also decide to make x a LinkedList (instead of a generic
List) and carry the precise type information around with x. The beauty (and
the intent) of using the interface is that if you decide you want to change
your implementation, all you need to do is change it at the point of creation,
like this:
List x = new ArrayList();
•
The rest of your code can remain untouched (some of this genericity can
also be achieved with iterators).
Collection functionality
•
•
•
•
•
•
•
•
•
•
•
coll.size() -- returns an int that gives the number of objects in the collection.
coll.isEmpty() -- returns a boolean value which is true if the size of the collection is 0.
coll.clear() -- removes all objects from the collection.
coll.contains(object) -- returns a boolean value that is true if object is in the collection.
coll.add(object) -- adds object to the collection. The parameter can be any Object. Some
collections can contain the value null, while others cannot. This method returns a boolean value
which tells you whether the operation actually modified the collection. For example, adding an
object to a Set has no effect if that object was already in the set.
coll.remove(object) -- removes object from the collection, if it occurs in the collection, and returns
a boolean value that tells you whether the object was found.
coll.containsAll(coll2) -- returns a boolean value that is true if every object in coll2 is also in the
coll. The parameter can be any Collection.
coll.addAll(coll2) -- adds all the objects in the collection coll2 to coll.
coll.removeAll(coll2) -- removes every object from coll that also occurs in the collection coll2.
coll.retainAll(coll2) -- removes every object from coll that does not occur in the collection coll2. It
"retains" only the objects that do occur in coll2.
coll.toArray() -- returns an array of type Object[] that contains all the items in the collection. The
return value can be type-cast to another array type, if appropriate. For example, if you know that
all the items in coll are of type String, then (String[])coll.toArray() gives you an array of Strings
containing all the strings in the collection.
List functionality
• Interface List
• Classes ArrayList and LinkedList
• LinkedList class is more efficient in applications where items will
often be added or removed at the beginning of the list or in the
middle of the list. In an array, these operations require moving a
large number of items up or down one position in the array, to make
a space for a new item or to fill in the hole left by the removal of an
item. In a linked list, nodes can be added or removed at any position
by changing a few pointer values.
• The ArrayList class is more efficient when random access to items is
required. Random access means accessing the n-th item in the list,
for any integer n. This is trivial for an array, but for a linked list it
means starting at the beginning of the list and moving from node to
node along the list for n steps. Operations that can be done
efficiently for both types of lists include sorting and adding an item at
the end of the list.
List Functionality
•
list.get(index) -- returns the Object at position index in the list, where index is an integer. Items
are numbered 0, 1, 2, ..., list.size()-1. The parameter must be in this range, or an
IndexOutOfBoundsException is thrown.
•
list.set(index,obj) -- stores an object obj at position number index in the list, replacing the object
that was there previously. This does not change the number of elements in the list or move any of
the other elements.
•
list.add(index,obj) -- inserts an object obj into the list at position number index. The number of
items in the list increases by one, and items that come after position index move up one position
to make room for the new item. The value of index can be in the range 0 to list.size(), inclusive.
•
list.remove(index) -- removes the object at position number index. Items after this position move
up one space in the list to fill the hole.
•
list.indexOf(obj) -- returns an int that gives the position of obj in the list, if it occurs. If it does not
occur, the return value is -1. If obj occurs more than once in the list, the index of the first
occurrence is returned.
These methods are defined in both the ArrayList class and in the LinkedList class, although they
are only efficient for ArrayLists. The LinkedList class adds a few additional methods, which are not
defined for an ArrayList. If linkedlist is an object of type LinkedList, then
•
linkedlist.getFirst() -- returns the Object that is the first item in the list. The list is not modified.
•
linkedlist.getLast() -- returns the Object that is the last item in the list. The list is not modified.
•
linkedlist.removeFirst() -- removes the first item from the list, and returns that Object as its return
value.
•
linkedlist.removeLast() -- removes the last item from the list, and returns that Object as its return
value.
•
linkedlist.addFirst(obj) -- adds the Object, obj, to the beginning of the list.
•
linkedlist.addLast(obj) -- adds the Object, obj, to the end of the list. (This is exactly the same as
linkedlist.add(obj) and is apparently defined just to keep the naming consistent.)
Stack
import java.util.*;
public class StackL {
private LinkedList list = new LinkedList();
public void push(Object v) { list.addFirst(v); }
public Object top() { return list.getFirst(); }
public Object pop() { return list.removeFirst(); }
public static void main(String[] args) {
StackL stack = new StackL();
for(int i = 0; i < 10; i++)
stack.push(Integer.toString(i));
for(int i = 0; i < 5; i++)
System.out.println(stack.top());
}
}
Queue
import java.util.*;
public class Queue {
private LinkedList list = new LinkedList();
public void addRear(Object v) { list.addFirst(v); }
public Object popFirst() { return list.removeLast(); }
public boolean isEmpty() { return list.isEmpty(); }
public static void main(String[] args) {
Queue queue = new Queue();
for(int i = 0; i < 10; i++)
queue.addRear(Integer.toString(i));
while(!queue.isEmpty())
System.out.println(queue.popFirst());
}
}
ListIterator
•
•
•
•
If list is an object of type List, then the method list.iterator(), defined in the Collection
interface, returns an Iterator that can be used to traverse the list from beginning to
end. However, for Lists, there is a special type of Iterator, called a ListIterator, which
offers additional capabilities. The method list.listIterator() returns a ListIterator for list.
A ListIterator has the usual Iterator methods hasNext() and next(), but it also has
methods hasPrevious() and previous() that make it possible to move backwards in
the list. To understand how these work, its best to think of an iterator as pointing to a
position between two list elements, or at the beginning or end of the list.
If iter is a ListIterator(), iter.next() moves the iterator one space to the right along the
list and returns the item that the iterator passes as it moves. The method
iter.previous() moves the iterator one space to the left along the list and returns the
item that it passes. The method iter.remove() removes an item from the list; the item
that is removed is the item that the iterator passed most recently in a call to either
iter.next() or iter.previous(). There is also a method iter.add(Object) that adds the
specified object to the list at the current position of the iterator. This can be between
two existing items or at the beginning of the list or at the end of the list.
By the way, the lists that are used in the LinkedList class are doubly linked lists. That
is, each node in the list contains two pointers -- one to the next node in the list and
one to the previous node. This makes it possible to implement effeciently both the
next() and previous() methods of a ListIterator. Also, to make the addLast() and
getLast() methods of a LinkedList efficient, the LinkedList class includes an instance
variable that points to the last node in the list.
ListIterator
static void orderedInsert(List list, Comparable newItem) {
// Precondition:
//
//
//
//
// Postcondition:
//
//
The items in list are sorted into ascending
order, according to the compareTo method.
newitem.compareTo(item) must be defined for
each item in the list.
newItem has been added to the list in its
correct position, so that the list is still
sorted into ascending order.
ListIterator iter = list.listIterator();
while (iter.hasNext()) {
Object item = iter.next();
if (newItem.compareTo(item) <= 0) {
// newItem should come BEFORE item in the list.
// Move the iterator back one space so that
// it points to the correct insertion point,
// and end the loop.
iter.previous();
break;
}
}
iter.add(newItem);
}
Sorting Lists
•
Methods for sorting Lists are available as static methods in the class
java.util.Collections. This class contains a variety of static utility methods for
working with collections. The command
Collections.sort(list);
can be used to sort a list into ascending order. The items in the list must
implement the Comparable interface. This method will work, for example,
for lists of Strings. If a Comparator is provided as a second argument:
Collections.sort(list,comparator);
•
then the comparator will be used to compare the items in the list. As
mentioned in the previous section, a Comparator is an object that defines a
compare() method that can be used to compare two objects.
The Collections class has at least two other useful methods for modifying
lists. Collections.shuffle(list) will rearrange the elements of the list into a
random order. Collections.reverse(list) will reverse the order of the
elements, so that the last element is moved to the beginning of the list, the
next-to-last element to the second position, and so on.
Sets
•
•
Interface Set
Classes java.util.TreeSet and java.util.HashSet
•
The objects in a TreeSet should implement the Comparable interface and
that obj1.compareTo(obj2) should be defined in a reasonable way for any
two objects obj1 and obj2 in the set. Alternatively, a Comparator can be
provided as a parameter to the constructor when the TreeSet is created. In
that case, the Comparator will be used to compare objects that are added to
the set.
TreeSet words = new TreeSet();
while there is more data in the input file:
Let word = the next word from the file.
words.add(word);
Iterator iter = words.iterator();
while (iter.hasNext()):
Write iter.next() to the output file.
Sets
TreeSet set = new TreeSet();
set.addAll(coll);
TreeSet set = new TreeSet();
set.addAll(coll);
ArrayList list = new ArrayList();
list.addAll(set);
ArrayList list =
new ArrayList(new TreeSet(coll));
Maps
•
•
Interface Map
Classes TreeMap and HashMap
•
map.get(key) -- returns the Object that is associated by the map to the Object key. If the map
does not associate any value with obj, then the return value is null. Note that it's also possible for
the return value to be null when the map explicitly associates the value null with the key. Referring
to "map.get(key)" is similar to referring to "A[key]" for an array A. (But note that there is nothing
like an IndexOutOfBoundsException for maps.)
map.put(key,value) -- Associates the specified value with the specified key, where key and value
can be any objects. If the map already associated some other value with the key, then the new
value replaces the old one. This is similar to the command "A[key] = value" for an array.
map.putAll(map2) -- if map2 is any other map, this copies all the associations from map2 into
map.
map.remove(key) -- if map associates a value to the specified key, that association is removed
from the map.
map.containsKey(key) -- returns a boolean value that is true if the map associates some value to
the specified key.
map.containsValue(value) -- returns a boolean value that is true if the map associates the
specified value to some key.
map.size() -- returns an int that gives the number of associations in the map.
map.isEmpty() -- returns a boolean value that is true if the map is empty, that is if it contains no
associations.
map.clear() -- removes all associations from the map, leaving it empty.
•
•
•
•
•
•
•
•
map.keySet()
Set keys = map.keySet();
// The set of keys in the map.
Iterator keyIter = keys.iterator();
System.out.println("The map contains the following associations:");
while (keyIter.hasNext()) {
Object key = keyIter.next(); // Get the next key.
Object value = map.get(key); // Get the value for that key.
System.out.println( "
(" + key + "," + value + ")" );
}
map.values() i map.entrySet()
Set entries = map.entrySet();
Iterator entryIter = entries.iterator();
System.out.println("The map contains the following associations:");
while (entryIter.hasNext()) {
Map.Entry entry = (Map.Entry)entryIter.next();
Object key = entry.getKey(); // Get the key from the entry.
Object value = entry.getValue(); // Get the value.
System.out.println( "
(" + key + "," + value + ")" );
}
Submaps
•
•
•
The TreeMap class defines three submap views. A submap is similar to a subset. A submap is a
Map that contains a subset of the keys from the original Map, along with their associated values.
If map is a variable of type TreeMap, then map.subMap(fromKey,toKey) returns a view that
contains all key/value pairs from map whose keys are between fromKey and toKey (including
fromKey and excluding toKey). There are also views map.headMap(toKey) and
map.tailMap(fromKey) which are defined in the obvious way.
Suppose, for example, that blackBook is a TreeMap in which the keys are names and the values
are phone numbers. We can print out all the entries from blackBook where the name begins with
"M" as follows:
Map ems = blackBook.subMap("M","N");
// This submap contains entries for which the key is greater
// than or equal to "M" and strictly less than "N".
if (ems.isEmpty())
System.out.println("No entries beginning with M.");
else {
Iterator iter = ems.entrySet().iterator();
// This iterator will traverse the entries in the submap, ems.
while (iter.hasNext()) {
// Get the next entry and print its key and value.
Map.Entry entry = iter.next();
System.out.println( entry.getKey() + ": " + entry.getValue() );
}
}
hashCode()
•
•
•
The Object class defines the method hashCode(), which returns a value of type int.
When an object, obj, is stored in a hash table that has N locations, a hash code in
the range 0 to N-1 is needed. This hash code can be computed as
Math.abs(obj.hashCode()) % N, the remainder when the absolute value of
obj.hashCode() is divided by N. (The Math.abs is necessary because
obj.hashCode() can be a negative integer, and we need a non-negative number to
use as an array index.)
For hashing to work properly, two objects that are equal according to the equals()
method should have the same hash code. In the Object class, both equals() and
hashCode() are based on the address of the memory location where the object is
stored. However, many classes redefine the equals() method.
If a class redefines the equals() method, and if objects of that class will be used as
keys in hash tables, then the class should also redefine the hashCode() method. For
example, in the String class, the equals method is redefined so that two objects of
type String are considered to be equal if they contain the same sequence of
characters. The hashCode() method is also redefined in the String class, so that the
hash code of a string is computed from the characters in that string rather than from
its location in memory. For Java's standard classes, you can expect equals() and
hashCode() to be correctly defined. However, you might need to define these
methods in classes that you write yourself.
Class String
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if ((anObject != null) && (anObject instanceof String)) {
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) {
char v1[] = value;
char v2[] = anotherString.value;
int i = offset;
int j = anotherString.offset;
while (n-- != 0) {
if (v1[i++] != v2[j++]) {
return false;
}
}
return true;
}
}
return false;
}
Class String
public int hashCode() {
int h = 0;
int off = offset;
char val[] = value;
int len = count;
if (len < 16) {
for (int i = len ; i > 0; i--) {
h = (h * 37) + val[off++];
}
} else {
// only sample some characters
int skip = len / 8;
for (int i = len ; i > 0; i -= skip, off += skip) {
h = (h * 39) + val[off];
}
}
return h;
}