Transcript System.out.println(i.next())

‫פיתוח מונחה עצמים –‬
‫שפת ‪JAVA‬‬
‫מבני נתונים‬
‫‪References‬‬
‫‪ ‬קורס "שיטות בהנדסת תוכנה"‪ ,‬הפקולטה למדעי‬
‫המחשב‪ ,‬הטכניון‪.‬‬
‫‪ ‬קורס "מערכות מידע מבוזרות"‪ ,‬הפקולטה‬
‫להנדסת תעשייה וניהול‪ ,‬הטכניון‪.‬‬
Collections -- ‫אוספים‬
 A collection (sometimes called a container) is simply an
object that groups multiple elements into a single unit.
 Collections are used to store, retrieve and manipulate data,
and to transmit data from one method to another.
Interfaces:
Java Collection Framework
Implementations:
java.util package -‫ נמצאים ב‬collections -‫ כל ה‬
 ArrayList – Resizable array implementation of the List interface
 Arrays - This class contains various methods for manipulating arrays (such
as sorting and searching).
 Collections - This class consists exclusively of static methods that operate on
or return collections.(binary search, fill, min, max (according to
specific comparator), etc)
 Hash table - This class implements a hashtable, which maps keys to values.
 LinkedList - Linked list implementation of the List interface.
 Stack - The Stack class represents a last-in-first-out (LIFO) stack of objects
 Vector - The Vector class implements a growable array of objects.
Iterator
• A mechanism for iterating over a collection’s elements.
• Represented by the Iterator interface.
• Iterator allows the caller to remove elements from the
underlying collection during the iteration with well-defined
semantics
–The only safe way to modify a collection during iteration
• For more information see jdk documentation java.util.Iterator
 ListIterator – extends from Iterator, can be found in List interface
(hence all classes implementing List, such as LinkedList).
It has additional functions, i.e. getPrevious() …
Example - Iterator
static void filter(Collection c)
{
for (Iterator it = c.iterator() ; it.hasNext(); )
if (!cond(it.next()))
it.remove();
}
static void filter(Collection c)
{
Iterator it = c.iterator();
while (it.hasNext())
if (!cond(it.next()))
it.remove();
}
Example: List
private static void swap(List a, int i, int j)
{
Object tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
http://java.sun.com/j2se/1.4.2/docs/api/
Exampe: List (cont)
public static void replace(List l, Object val, List newVals)
{
for (ListIterator i = l.listIterator(); i.hasNext() ; ) {
// more suffisticated way: if (val==null ? i.next()==null : val.equals(i.next())) {
if(val == null && (i.next() == null)||
(val != null && val.equals(i.next()))){
i.remove();
for (Iterator j = newVals.iterator(); j.hasNext(); )
i.add(j.next());
}
}
}
The add method inserts a new element into
the list, immediately before the current
cursor position
(this is the way add(Object) function works)
Example: Map
import java.util.*;
public class Freq {
public static void main(String args[])
{
Map m = new HashMap();
for (int i=0; i<args.length; i++) {
m.put(args[i], “value=”+args[i]);
}
System.out.println(m.size() + " distinct words detected:");
System.out.println(m);
}
}
http://java.sun.com/j2se/1.4.2/docs/api/
Example: Map (cont)
for (Iterator i = m.keySet().iterator() ; i.hasNext() ; )
System.out.println(i.next());
for (Iterator i = m.values().iterator(); i.hasNext() ; )
System.out.println(i.next());
for (Iterator i = m.entrySet().iterator(); i.hasNext() ; ) {
Map.Entry e = (Map.Entry)i.next();
System.out.println(e.getKey() + ": " + e.getValue());
}
SortedMap Interface
• A Map that maintains its entries in ascending order
– According to keys' natural order
or
– According to a Comparator provided at creation time.
• Map operations
– Iterator traverses elements in any of the sorted map's collection-views in keyorder.
• Additional Operations
– Range view
– End points
– Comparator access
• For more information, see java.util.SortedMap in jdk documentation
• Class TreeMap implements SortedMap
Example - TreeMap
package test;
import java.util.*;
public class sortedMapCheck {
public static void main(String[] args){
TreeMap map = new TreeMap();
SortedMap subMap = null;
int size = 10;
for(int i = 0; i < size; i++){
Integer key = new Integer(i);
map.put(key,"obj"+key.toString());
obj0 | obj9
obj1 | obj8
obj2 | obj7
obj3 | obj6
obj4 | obj5
obj5 | obj4
obj6 | obj3
obj7 | obj2
obj8 | obj1
obj9 | obj0
}
for(int i = 0; i < size; i++){
System.out.println(map.get(new Integer(i)) + " | " + map.get(new Integer(size-i-1)));
}
Example – TreeMap (cont.)
// here we loose ordering
Iterator it = map.values().iterator(); // map.values() returns Collection
for(; it.hasNext();)
System.out.println(it.next());
Smallest key of subMap =2
Largest key of subMap = 5
subMap = map.subMap(new Integer(2),new Integer(6));
System.out.println("Smallest key of subMap ="+subMap.firstKey());
System.out.println("Largest key of subMap = "+subMap.lastKey());
for(int i = ((Integer)subMap.firstKey()).intValue();
i < ((Integer)subMap.lastKey()).intValue()+1; i++){
System.out.println(subMap.get(new Integer(i)));
}
}
}
obj2
obj3
obj4
obj5