Abstract Data Types
•	Importance of abstraction
•	Definition
•	Examples
•	List ADT
•	Array implementation
Importance of abstraction
•	Abstraction allows us to generalize and to focus on what is important
•	Ex: emoticons like :) show emotion using the eyes and mouth
•	Your ears don't say much about your emotion
•	Ex: Road signs -- Squiggly lines to warn of curves in road
•	Ex: Algorithm is an abstraction of a program
•	All programs using the same algorithm share things in common
OO and abstraction
•	Koenig, Ruminations on C++, pp. 368-369 (ISBN 0201423391)
•	"The biggest conceptual change in going from C to C++ is in learning to stop thinking about the structure of your program and think first about the behavior of the program's data.... The operations that a class supports -- its interface -- are usually more important than its structure, because we can more easily change the structure than the interface."
ADT Examples
•	Number
•	Supported operations: arithmetic (+,-,*,/), comparison (<,>, ...)
•	Possible types: integers, real numbers, fractions
•	Even these types have multiple implementations: short vs. int, 1's complement vs. 2's complement
•	Focusing on supported operations allows us to cover all numbers
•	Ex: to search a sorted list of numbers, can compare target with any element of the list
•	If target < element, continue search earlier in the list
ADT Examples
•	String (ADT)
•	Supported operations?
•	Possible implementations?
•	Stop-watch
•	Data that is being modeled? Operations?
•	Need to be able to start timing, stop timing, read value, reset to zero
•	Need to have time advance (might read from system or simulate)
List ADT
•	Domain: ordered group of objects
•	example of a container class : contains elements
•	elements are of the same type (ItemType)
•	Supports:
•	MakeEmpty : initialize list to be empty
•	IsFull : returns true if list is full, false if not
•	LengthIs : returns # elements in list
List ADT, continued
•	Supports:
•	InsertItem
•	DeleteItem
•	ResetList -- point to first element again
•	GetNextItem -- move to next item
•	ResetList and GetNextItem both help generalize the common task of looping (iterating) through the elements of a list
List ADT, continued
•	Supports:
•	RetrieveItem --  
•	returns matching element if it exists and true to show it is found
•	returns false if not matched 
•	Assumes element type supports comparison
•	How can abstract data types help us with this requirement?
ItemType
•	The type of the elements of the list
•	Want to support list of any kind of data
•	ItemType class defines requirements for how we define the data
•	ComparedTo(ItemType item)
•	returns one of enumeration: LESS, GREATER, EQUAL
•	Print(/*output stream*/) -- to print value
List ADT, continued
•	Many more possible operations
•	Why might we limit the set of operations?
•	"Strive for class interfaces that are complete and minimal"
•	Meyers, Effective C++, 1st ed., item 18, ISBN 0201563649
Array implementation
•	Represent list by an array
•	Declare array as data member (instance variable) inside UnsortedType class
•	Somewhere, need to store size of array
•	(Java stores size automatically -- arrayVariable.length gives size)
•	keep track of number of elements in list
•	to implement LengthIs(), return stored number
Adding to the list
•	array[length++] = newValue;
•	This has a serious flaw ... what is it?
Adding to the list (improved)
•	if (length < capacity)
•	    array[length++] = newValue;
•	else // either throw an exception or extend size of list
•	What would you have to do to change the size of the list?
•	Could anything still go wrong?
IsFull, MakeEmpty
•	For simplicity, text sample code assumes length is not exceeded
•	IsFull operation can help programmer avoid adding to full list
•	return (length == MAX_ITEMS);
•	MAX_ITEMS is defined as maximum capacity of list
•	MakeEmpty is really a constructor
•	length = 0;   // iterator info handled separately -- see below
Deleting from the list
•	Algorithm 1:
•	Find item in list
•	Shift items which follow to delete this item
•	Subtract one from length
Deleting (continued)
•	Algorithm 2:
•	Find item in list
•	Copy last item in list into this position
•	List is unsorted, so no need to keep same order
•	Subtract one from length
Deleting (continued)
•	// using Algorithm 2
•	while (item.ComparedTo(info[location]) != EQUAL)
•	    location++;
•	info[location] = info[length-1];
•	length--;
RetrieveItem Algorithm
•	Need to indicate whether found or not -- use a "flag" variable found
•	Initialize found to false
•	Will stop as soon as item is found -- use another flag variable moreToSearch
•	Initialize to  have not examined Info(last)
•	does not specify implementation
RetrieveItem Algorithm
•	while more to search and not found
•	compare item to retrieve (from parameter) with next item
•	if GREATER or LESS, move to next item and update moreToSearch
•	if EQUAL, found is true, item to retrieve is current item
RetrieveItem (cont'd)
•	Implementation: found, item are reference parameters
•	int location = 0;  // index
•	found = false;
•	bool moreToSearch = location < length;
•	// if location == length, end of list has been reached
RetrieveItem (cont'd)
•	while (moreToSearch && !found) {
•	    switch(item.ComparedTo(info[location])) {
•	        case LESS:
•	        case GREATER : location++;
•	            moreToSearch = location < length;
•	            break;
        RetrieveItem (cont'd)
•	        case EQUAL: 
•	            found = true;
•	            item = info[location];
•	            break;
•	} /* switch */  } /* while */
Iterator methods
•	ResetList
•	currentPos = -1;
•	GetNextItem
•	currentPos++;
•	item = info[currentPos];
Using the List implementation
•	Print a list
•	int length; ItemType item;
•	list.ResetList();
•	length = list.LengthIs();
Using the List implementation (cont'd)
•	for (int counter = 1; counter <= length; counter++) {
•	    list.GetNextItem(item);
•	    item.Print(dataFile);
•	}
Comments
•	Using the ADT interface, little of the code suggests how the list is implemented
•	On the other hand, lots of calls to methods
Big O
•	What is the order of complexity of the InsertItem operation? 
•	if we throw an exception? if we extend the size of the list?
•	For the DeleteItem operation? the RetrieveItem operation?