Transcript Issues in ATM Network Control - Engineering School Class

CSE 131 Computer Science 1
Module 9: Abstract Data Types
Structure of a Java Program
Lab
RobotController
public void main(…)


Robot
Person
You can define any number of classes in a program
Every program has one and only one main() method
» When you click “Run”, Java executes the statements in main()
» main() can be defined in any class

You can declare a class instance just as a primitive variable. For
example: int x; Robot r;

You can use a class in another class
public class Lab {
Robot r1;
Robot r2;
Person p1;
…
}
‹#›
Java Programs as Interacting Objects
Robot
interface
Robot
Controller
Person
 Objects
interact through interfaces defined by methods
 A method’s signature is its name, its list of formal
parameters and the type of the value it returns
» example: public void turnRight(int distance)
 The
interface for a class is the set of method signatures
(ignore data in some sense)
 The interface is an implicit concept
» But in Java, interface is also an explicit feature
‹#›
Example of an interface
public interface Shape {
public void draw(double x, double y);
public double area();
}
public class Circle implements Shape {
private double radius;
public Circle(double r) { radius = r; }
public void draw(double x, double y) {
…// draw a circle whose top-left corner is (x,y)
}
public double area() {
return Math.PI*radius*radius;
}
}
» An interface is declared using the keyword interface
» Methods in an interface only have signature, but not process
» A class that implements an interface must implement all the methods
declared in the interface.
» The methods must have exactly the same signatures as declared in
the interface.
‹#›
Example of an interface
public interface Shape {
public void draw(double x, double y);
public double area();
}
public class Rectangle implements Shape {
private double width;
private double height;
public Rectangle(double w, double h) {
width = w; height = h;
}
public void draw(double x, double y) {
// draw a rectangle whose top-left corner is (x,y)
}
public double area() {
return width*height;
}
}
» An interface can be (and typically is) implemented by multiple classes
» A class can implement multiple interfaces
•
Needs to implement all the methods in all the interfaces
‹#›
Why Use the Shape Interface?

Interface provides another, higher-level of abstraction
» Extract the common features of a group of classes
» So that we can write general codes that can deal with multiple classes

Consider a video game that shows certain shape when you score, and the
reward you get is decided by the area of the shape
public void scoreAction(Shape s, double x, double y) {
s.draw(x,y);
myScore = myScore + s.area();
}

When the player scores
Circle A= new Circle(1.5);
Rectangle B = new Rectangle(2.0,1.0);
.........
if(scoreType == 1) scoreAction(A, x, y);
else if(scoreType == 2) scoreAction(B, x, y);
Notice that, without the interface Shape, it is impossible to have a
method that takes both Circle and Rectangle as the first input parameter
‹#›
Abstract Data Type (ADT)
 An
Abstract Data Type (ADT) is defined by a set of
possible data values and a set of operations
» example: a dictionary is an ordered list of (word, defn) pairs
with operations lookup(word) and define(word, defn)
» abstract in ADT emphasizes that what matters is the operations
and how they behave, not the underlying representation
» corresponds naturally to a Java class
» often defined using interfaces, to allow for multiple
implementations
 The
Java API defines a variety of ADTs
» List, Set, Map, Stack, Queue
» broadly applicable software building blocks
» in package java.util
‹#›
Collections in Java
 Many
ADTs used to store multiple items of same type
» size is flexible and can change as program runs
» referred to as collections – lists and sets are examples
 Principal
collections in Java
» List<T>: ordered list of items of type T
• implemented by ArrayList<T> and LinkedList<T>
» Set<T>: unordered set of items of type T, with no repeats
• implemented by HashSet<T> and TreeSet<T>
» Map<K,V>: set of (key,value) pairs of types (K,V) with no
repeated keys
• implemented by HashMap<K,V> and TreeMap<K,V>
‹#›
Using Lists
 Some
»
»
»
»
»
methods for List<T>
void add(T x) – insert object x at end of list
void add(int i, T x) – insert object x at position i
T get(int i) – return a reference to the object at position i
void set(int i, T x) – make item i in list refer to x
int indexOf(T x) – return index of first item equal to x
 Combine two lists
void combine(List<Integer> target, List<Integer> source) {
for (int i=0; i<source.size(); i++)
target.add(source.get(i));
}
» can use generalized for-loop to iterate through array, list or
other collection
» items added to the end of the target list
• alternatively, could write: target.add(target.size(), s)
‹#›
Iterators
 The
for-each loop allows us to examine each item in a
list, but does not allow us to remove items
 A ListIterator is an object that can be used to move
through and possibly modify a list
» defined by the ListIterator interface that defines the
applicable methods (hasNext(), next(), set(), remove())
» different list implementations provide their own
implementations of the ListIterator interface
List<Integer> list = new LinkedList<Integer>(); ...
ListIterator<Integer> i = list.listIterator();
while (i.hasNext()) {
Integer s = i.next();
// return item, advance to next
if (s%2 == 0) i.set(0);
if (s%3 == 0) i.remove();
}
» think of iterator as a cursor positioned “between” elements
‹#›
Using Sets
 Some
»
»
»
»
methods for Set<T>
void add(T x) – add x, if no equal item in set
boolean isEmpty() – true if nothing in set
int size() – returns number of elements
boolean contains(T x) – true if set has an item equal to x
 Union and difference
void union(Set<Integer> target, Set<Integer> source) {
for (Integer i : source) target.add(i);
}
» union adds references to objects if no equal objects in set
void diff(Set<Integer> target, Set<Integer> source) {
for (Integer i : source)
if (target.contains(i)) target.remove(i);
}
‹#›
Using Maps
 Some
»
»
»
»
methods for Map<K,V>
V get(K k) – return the value that key k maps to (or null)
void put(T x, V y) – add pair (x, y) to map
V remove(K k) – remove pair with key k and return its value
boolean containsKey(K k) – true if there is a pair with key
equal to k
 Counting words in a list
List<String> words = new ArrayList<String>();
// add strings to list words
Map<String,Integer> wordCnt = new TreeMap<String,Integer>();
for (String w : words) {
if (!wordCnt.containsKey(w)) wordCnt.put(w,1);
else wordCnt.put(w,wordCnt.get(w)+1);
}
» so now wordCnt.get(“abc”) is # of occurrences of “abc”
‹#›