Monday, July 18, 2011

July 18th, 2011

Iterators
enhanced for loop

String [] horsemen = {"war", "famine" , "pestilence", "death" }
for (String horsemen : horsemen )
System.out.println (horseman) ;

There is an
Iterator interface
Iterable interface

Iterator interface defines methods:
- boolean hasNext () : returns true if next() returns an element
- T next()
- boolean remove()

Scanner testScan = new Scanner (~)
while ( scan.hasNext() ) {
String token = testscan.next() ;
/* code to process token */
}

but....

for (String token : testScan ) ! not legal
because Scanner doesn't implement Iterable

Iterable Specifies iterator ()
- iterator returns an object of type Iterator

ArrayList implements both Iterable, Iterator.
-------
ArrayList arrayListOfFoo = new ArrayList ();
for ( Foo refToFoo : arrayListofFoo {
/* do something * /
}

compared to

ArrayList arrayListOfFoo = new ArrayList() ;
Iterator arrayListIter = arrayListOfFoo.iterator () ;
while (arrayListIter.hasNext() ) {
Foo refToFoo = arrayListIter.next() ;
/* Code to do something */
}



Recall collections of MPs
-unorganised rabble (set)
linear order (list)
nonlinear order (Tree)


public void printlistofMPs ( collection all MPs )
{ for (MemberOfParliment one Mp: all MPs )
{ System.out.print;n(oneMP); }
}

Iterable declares

Iterator iterator()
   * return an object of type Iterator

Iterator declares

boolean hasNext() return true iff a call to next() will return an object

T next() return the next object from the collectionl repeared calls to next() will return every element exactly once Order will depend on the type of collection.

void remove () remove the element

Collection extends Iterable

int size() return the number of things in the underlying collection

boolean add (E e) add a thing to the underlying collection

boolean remove (Object o) remove from the underlying collection to the first thing hat is equal to the object provided as a parameter

public interface List extends Collection

void add (int index, E e) add an element at the specified position

E get (int index) Retrieve the element at the specified position

E remove (int index) Remove the element at the specified position.

Monday, July 11, 2011

June 13th , 2011

Abstract Data Types

Example: Stack ADT
- elements are added and removed from the same end; LIFO (Last In First Out)

push() ==> Add (Push) an element
pop() ==> Remove (pop) an element
peek() ==> Look at the top element w/o removing it


is Empty()
size()

Assume some type T to be held by the stack
where T is just a placeholder

push(T elem)
T pop()
T peek ()
boolean is Empty()


Generic Types
- Some way to postpone specifying a type without some of the hazards of polymorphism.



Animal[] creatures = new Mammal[25];

.
..
...
creatures[1] = new Lizard () ;

This causes a runtime error because Lizard is not a subclass of Mammal.

Generic types allow us to help the compiler by providing additional hints about data types.

Recall the comparable interface

class Apple implements Comparable {
.
..
...
public int compareTo (Object otherObject)
.
..
...
}

Comparable is actually a generic interface :

public interface Comparable   { 
public int compareTo ( T thing) ;
}

To compare Apples to Apples (only!)

class Apple implements Comparable {
.
..
..
public int compareTo (Apple otherApple) {.....} ;

Text uses this language:

"Then, when a generic class is needed, it is instantiated with a specific class used in place of T."

Would be nice to allow:

class Apple implement Comparable , Comparable {.......

But doesnt work!

Subtly wrong - information about the actual type used for T is not part of the runtime hidden bookkeeping information. Generics are enforced by the compiler.

Wednesday, July 6, 2011

July 6th, 2011

Read: 
Chapter 14 Stacks
4.6,4.8 Iterators
9.3
Chapter 15 Queues


Searching :


String [] planets = { "Neptune" , "Uranus", " Saturn", "Jupiter", "Mars", "Earth" , "Venus" , "Mercury:" }

To find a given element, scan the list for a match. O(n) for linear search.
To prove absence, must look at all elements.

Sort planets alphabetically:
Earth, Jupiter, Mars, Mercury, Neptune, Saturn, Uranus, Venus

Each comparison eliminates a portion of the list, because we know from a comparison whether the element we want is earlier or later in the list.

Given a sorted sequence, use binary search
- compare with middle element
- discard the irrelevant 1/2
- repeat with relevant 1/2

Because the problem is reduced by 1/2 with each iteration, in log2 n iterations we will find the element or prove the element is not in the list. O (log2 n)

Effort to sort: n log2 n
Effort for linear search: n
Effort for binary search: log2n

n log2 n + k log2 n <= kn
(n+k) log2 n <= kn
log2 n <= (kn/(n+k))
log2 n <= k/(1+(k/n))
first approx : sort first if log2 n <= k




Collection:
- An object that gathers & organizes other objects.
- It defines the specific ways in which those objects can be accessed and managed.
- The user must interact with the collection only with the prescribed ways of access & management.

Text:
- linear collections are organized in a straight line
- nonlinear collections are not.

Things : Members of Parliament (MP's)

How to organise?

- unorganized rabble :
* a set
* easy to add
* difficult to extract

"member from calgary southwest, conservative, ..."

- linear order (alphabetically by name):
* easier to find ( "Harper")
* can also specify by pos'n.
* insertion requires more effort (find the right place)

- nonlinear order ( geographic )

Why should we accept the restriction of a collection?

Users:
-a relatively small number of Abstract Data Types (collections) cover an enormous range of situations.

Implementor:
the task of implementing an ADT is bounded (manageable ), can concentrate on a good implementation or a relatively small number of methods.