Section 1
ADTs, Data Structures, Java Generics
Hello, I’am Mia
Hi! I’m Rachel
Icebreaker Activity!
Abstract Data Type (ADT)
From lecture:
Mathematical description of a “thing” with set of operations on that “thing”
Main Idea:
Based on the point of view from the USER (as opposed to the implementer)
3 Descriptors:
Data Structure
From lecture:
A specific organization of data and family of algorithms for implementing an ADT
Main Idea:
Based on the point of view from the IMPLEMENTER (as opposed to the user)
i.e. it is the specification (data + algorithms) of an ADT
e.g. stack can use an underlying array data structure and specific pop/push algorithms
List Abstract Data Type
Summary/Idea: An indexable collection of items held in a sequence
Identify List operations:
Identify List Data Structures:
List Abstract Data Type
Summary/Idea: An indexable collection of items held in a sequence
Identify List operations:
Identify List Data Structures:
Stack Abstract Data Type
Summary/Idea: A collection of items accesses in LIFO order
Identify Stack Operations:
Identify Stack Data Structures:
Stack Abstract Data Type
Summary/Idea: A collection of items accesses in LIFO order
Identify Stack Operations:
Identify Stack Data Structures:
Queue Abstract Data Type
Summary/Idea: A collection of items accessed in FIFO order
Identify Queue Operations:
Identify Queue Data Structures:
Queue Abstract Data Type
Summary/Idea: A collection of items accessed in FIFO order
Identify Queue Operations:
Identify Queue Data Structures:
Set Abstract Data Type
Summary/Idea: An unordered collection of items without duplicates
Identify Set Operations:
Identify Set Data Structures:
Set Abstract Data Type
Summary/Idea: An unordered collection of items without duplicates
Identify Set Operations:
Identify Set Data Structures:
Pair ADT
Idea: One object which holds an ordered pair of items
Operations:
Data Structure:
IntPair Data structure
public class IntPair {
private int first;
private int second;
public IntPair(int first, int second){
this.first = first;
this.second = second;
}
public int getFirst(){
return first;
}
public int getSecond(){
return second;
}
public void setFirst(int newFirst){
this.first = newFirst;
}
public void setSecond(int newSecond){
this.second = newSecond;
}
}
IntPair Data structure
public class IntPair {
private int first;
private int second;
public IntPair(int first, int second){
this.first = first;
this.second = second;
}
public int getFirst(){
return first;
}
public int getSecond(){
return second;
}
public void setFirst(int newFirst){
this.first = newFirst;
}
public void setSecond(int newSecond){
this.second = newSecond;
}
}
Potential restrictions?
Pair ADT
Idea: One object which holds an ordered pair of items
Operations:
Data Structure:
IntPair Data structure
public class IntPair {
private int first;
private int second;
public IntPair(int first, int second){
this.first = first;
this.second = second;
}
public int getFirst(){
return first;
}
public int getSecond(){
return second;
}
public void setFirst(int newFirst){
this.first = newFirst;
}
public void setSecond(int newSecond){
this.second = newSecond;
}
}
This Pair data structure is set up to work exclusively with Integers. We cannot easily use this to hold pairs of doubles, strings, nodes, etc.
We would need to re-implement the class for each type!
Java Generics
Java Generics
ArrayList<String> myArrayList = new ArrayList<>();
Java Generics
Compare to: Methods and parameters
public void myMethod(int amount)
public class myClass<T>
Similar to how method parameters allow us to write code that works for many different values, generics allow us to write code that works for many different types.
Java Generics
Note: different programming languages solve this problem in different ways, we’re just presenting on how Java does it.
LikePair Data structure
public class LikePair<T> {
private T first;
private T second;
public LikePair(T first, T second){
this.first = first;
this.second = second;
}
public T getFirst(){
return first;
}
public T getSecond(){
return second;
}
public void setFirst(T newFirst){
this.first = newFirst;
}
public void setSecond(T newSecond){
this.second = newSecond;
}
}
Using generics we essentially treat the type itself as a field in the class.
We put <T> to indicate that the type that the pair will contain will be called “T”, and now we can use it just like we might use int or String!
UnlikePair Data structure
public class UnlikePair<A,B> {
private A first;
private B second;
public UnlikePair(T first, T second){
this.first = first;
this.second = second;
}
public T getFirst(){
return first;
}
public T getSecond(){
return second;
}
public void setFirst(T newFirst){
this.first = newFirst;
}
public void setSecond(T newSecond){
this.second = newSecond;
}
}
We can even have multiple types!
Here, the first item will be of type A, the second item will be of type B.
What do we need to update in the rest of the implementation?
UnlikePair Data structure
public class UnlikePair<A,B> {
private A first;
private B second;
public UnlikePair(A first, B second){
this.first = first;
this.second = second;
}
public A getFirst(){
return first;
}
public B getSecond(){
return second;
}
public void setFirst(A newFirst){
this.first = newFirst;
}
public void setSecond(B newSecond){
this.second = newSecond;
}
}
We can even have multiple types!
Here, the first item will be of type A, the second item will be of type B.
What do we need to update in the rest of the implementation?
LikeAnimalPair Data structure
public class LikeAnimalPair<T extends Animal> {
private T first;
private T second;
public LikeAnimalPair(T first, T second){
this.first = first;
this.second = second;
}
public T getFirst(){
return first;
}
public T getSecond(){
return second;
}
public void setFirst(T newFirst){
this.first = newFirst;
}
public void setSecond(T newSecond){
this.second = newSecond;
}
public String toString(){
return "(" + first + "," + second+ ")";
}
}
Suppose we wanted to be able to assume that a type inherited from a particular class.
We can actually use the “extends” keyword to require a generic type to have a superclass!
In this example, both items need to be the same animal
1. TypeSubtypePair - page 1
The first item is of some type, the second item is of a subtype of the first
What should go here?
public class TypeSubtypePair < >{� private A first;� private B second;� public TypeSubtypePair(A first, B second){� this.first = first;� this.second = second;� }� public A getFirst(){� return first;� }� public B getSecond(){� return second;� }� public void setFirst(A newFirst){� this.first = newFirst;� }� public void setSecond(B newSecond){� this.second = newSecond;� }� public String toString(){� return "(" + first + "," + second+ ")";� }�}
1. TypeSubtypePair - page 1
The first item is of some type, the second item is of a subtype of the first
What should go here?
A, B extends A
B extends A indicates that A is a superclass of B, or that B is a subtype of A
public class TypeSubtypePair <A, B extends A>{� private A first;� private B second;� public TypeSubtypePair(A first, B second){� this.first = first;� this.second = second;� }� public A getFirst(){� return first;� }� public B getSecond(){� return second;� }� public void setFirst(A newFirst){� this.first = newFirst;� }� public void setSecond(B newSecond){� this.second = newSecond;� }� public String toString(){� return "(" + first + "," + second+ ")";� }�}
2. IntOtherPair - page 2
The first item is an integer, the second item is some other type.
2. IntOtherPair - page 2
Why not <int, T> ?
Your turn!
Implement the following pair data structures:
3. ItemPairPair
4. ItemArrayPair
5. ComparablePair (challenge!!!)