CI3130 Introduction to Containers — the ADT's and Basic API's

CISC 3130
Data Structures
Containers I
Introduction to Containers — ADT's; Motivation & Examples

Overview

A container/collection is a data type whose primary purpose is to contain a group of objects.

The various containers are distinguished by their storage/retrieval properties
- where can insertions and/or removals be performed
- are duplicates permitted
- is knowing the number of elements useful
As we go through the operations, think about the opportunities for leveraging not just within a containers but between containers.

ADT's Revisited

An ADT is normally specified by its set of legal values and operations.
- For containers, the values are generically the elements that can be placed into the container.
- In general, these values are treated an 'things' to be held in the container and thus their particular type is not relevant to the operations of the container (add, remove).
In this lecture, we will be examining ADT's only
- The next lecture that discusses a simple implementation will deal with the actual data structure.
Remember, an ADT is defined by its behavior only; no mention is made of its implementation. As such, we will present each ADT as an interface, which essentially is a list of the class' public method with any implementation details omitted.

The Containers/Collections

We'll start off with a class analogous to the built-in array as its operations, and semantics are familiar (we did the same thing back in Lecture 1, where we originally introduced this class). We do this to illustrate how we will be presenting the rest of the containers. In each case, we will have:

a brief description of the container
a brief overview of the container's operations and their semantics
a diagram illustrating the operations
a Java interface with the operations
motivating examples of the container's usage
output of a demo illustrating the container in action
- In the corresponding lab, you will be writing the code for each demo using containers from the Java Collection Framework (JCF). This will help you get acquainted with the JCF.

Array

A 1-dimensional collection of elements randomly accessed by their index/position/offset from the beginning of the array.

Overview

The fundamental underlying container
fixed size
- size and capacity are the same, i.e., represents max elements, not current number placed into array
  - maintaining some notion of size requires additional logic and operations (e.g., an append)
random access only
- no notion of appending, inserting, or removing
the entire physical space is accessible
- don't have to place values in locations 0 … n-1 to access location n

Operations

get: random access of element at a specified position
set: random access modification of element at specified position
length: number of elements
- We will use length instead of size to
  - emphasize the capacity-like aspect (instead of the logical size) of the number of elements
  - maintain the logical connection to the built-in array (which uses length rather than size)

Interface

interface Array<E> {
	E get(int index);
	void set(int index, E value);
	int length();
}

Motivation and Examples

'bedrock' for all other homogeneous containers
vector/matrix in mathematics
frame buffer in graphics

Demo Code and Output

I'm showing this demo because there's no real Array contain in the JCF so there's nothing for you to play with

class ArrayDemo {
	public static void main(String [] args) {
		System.out.println("========== Array ==========");
		Array<Integer> array = new Array<>();

		System.out.println("length: " + array.length());
		System.out.println();

		System.out.println("===== Setting (then Printing) =====");
		for (int i = 0; i < array.length(); i++)
			array.set(i, i * 10);
		System.out.println(array);

		System.out.println();
		System.out.println("===== Getting =====");
		for (int i = 0; i < array.length(); i++)
			System.out.print(array.get(i) + (i < array.length() - 1 ? ", " : ""));
		System.out.println();
	}
}

Notes
Each of the containers is presented in the context of a demo app that 'shows off' the capabilities of the container.

What the demo is doing:

An Array object is created and its length is printed
The set method is used to populate the array, following which the array is printed using toString
The array is then iterated, the individual elements retrieved and printed (as individual integers)
We probably should print the value of the length method somewhere, but the correctness of that value can be indirectly seen given the value of length is used as the limit of the iteration, which is working correctly

========== Array ==========
length: 100

===== Setting then Printing =====
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260, \
	270, 280, 290, 300, 310, 320, 330, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500, \
	510, 520, 530, 540, 550, 560, 570, 580, 590, 600, 610, 620, 630, 640, 650, 660, 670, 680, 690, 700, 710, 720, 730, 740, \
	750, 760, 770, 780, 790, 800, 810, 820, 830, 840, 850, 860, 870, 880, 890, 900, 910, 920, 930, 940, 950, 960, 970, 980, 990}

===== Getting =====
0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260, \
	270, 280, 290, 300, 310, 320, 330, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500, \
	510, 520, 530, 540, 550, 560, 570, 580, 590, 600, 610, 620, 630, 640, 650, 660, 670, 680, 690, 700, 710, 720, 730, 740, \ 
	750, 760, 770, 780, 790, 800, 810, 820, 830, 840, 850, 860, 870, 880, 890, 900, 910, 920, 930, 940, 950, 960, 970, 980, 990

Notes

In all the outputs in this lecture, a \ at the end of the line indicates that the actual output line continues without a line break; the newline is there only to provide reasonable formatting on the web page.

Sequence (position-accessed)

Sequences are ordered lists of elements that have a position within the sequence. The element are accessed strictly by that position

Arrays are technically (primitive) sequences, but since they're the building blocks of all these containers, we presented it separately.
Sequence and list are used interchangeably.
The following are all examples of sequence containers with various restrictions; we will present the full list/sequence container last.

Stack

A stack exhibits LIFO (lat-in-first-out) storage retrieval. It is a container in which insertion/removal is done from one end of the container.

insertion/removal from one (same) end only
LIFO storage/retrieval

Operations

push: adds an element to the top of the stack
pop: removes (and returns) the element at the top of the stack
isEmpty: true if stack contains no elements

interface Stack<E> {
	void push(T value)
	T pop()
	boolean isEmpty()
}

push and pop are the original, traditional names of the stack operations and they are often (always?) used in place of the more uniform add and remove

Motivation and Examples

Real-life
- company seniority list
- navigating a maze
- 'just because' … it's easy to maintain and access
  - given a pile of boxes to which you want to add/remove a box, would you rather add/remove it to/from the top or bottom?
Computer Science
- container used to implement 'Back' button of a browser
- run-time call stack
  - return points
  - exception chaining
  - local variables and recursion
- depth-first search of web pages
- backtracking

Demo Output

Each of the containers is presented in the context of a demo app that 'shows off' the capabilities of the container.
- The output is presented here, the lab for this lecture is for you to write the specified JCF code to reproduce this output
- Each of these containers has one or more possible implementations in the JCF; you will be coding the app for each of them. They are listed both here and elaborated on in the lab itself.

Relevant JCF types: Deque, ArrayList, LinkedList

========== Stack ==========
{} (true)

Pushing
-------
0 -> {0} (false)
10 -> {0, 10} (false)
20 -> {0, 10, 20} (false)
30 -> {0, 10, 20, 30} (false)
40 -> {0, 10, 20, 30, 40} (false)
50 -> {0, 10, 20, 30, 40, 50} (false)
60 -> {0, 10, 20, 30, 40, 50, 60} (false)
70 -> {0, 10, 20, 30, 40, 50, 60, 70} (false)
80 -> {0, 10, 20, 30, 40, 50, 60, 70, 80} (false)
90 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)

Popping
-------
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 90
{0, 10, 20, 30, 40, 50, 60, 70, 80} (false) -> 80
{0, 10, 20, 30, 40, 50, 60, 70} (false) -> 70
{0, 10, 20, 30, 40, 50, 60} (false) -> 60
{0, 10, 20, 30, 40, 50} (false) -> 50
{0, 10, 20, 30, 40} (false) -> 40
{0, 10, 20, 30} (false) -> 30
{0, 10, 20} (false) -> 20
{0, 10} (false) -> 10
{0} (false) -> 0
{} (true)

Notes What the demo is doing:

A Stack object is created and then printed
The stack is populated using the push method; both the value being pushed as well as the current (post-push) value of the stack are printed for each push
The stack is then popped until empty, and the pre-pop stack and the retrieved values are both printed

Queue (Single-ended)

A data type typically used for some form of scheduling. In the simplest case (the FIFO queue below), items are inserted at one end (the back or rear) and removed from the other (front or head)

FIFO Queue

Overview

A (fifo) queue exhibits FIFO (first-in-first-out) storage retrieval. It is a container in which elements are added at one end and removed from the other.

insertion at one end (rear)/last, removal from other (front/first)
FIFO retrieval property
The term queue used just by itself usually means a FIFO (first-in-first-out) queue; however Java treats queue slightly differently, so we'll often use the term FIFO queue

Operations

add: adds element
remove: removes (oldest, least recently added) element
isEmpty

Interface

interface Queue<E> {
	void add(T value)
	T remove()
	boolean isEmpty()
}

Notes

The operations for queue are sometimes known as:
- enqueue and dequeue
- insert and remove

Motivation and Examples

Real-life
- 'fair' line/queue
- pragmatic rotation of perishable produce
Computer Science
- 'fair' scheduling algorithms (e.g. job/process queue)
  - web servers
- data buffers to manage differences in transmission/processing speeds
- breadth-first search of web pages (spider)

Demo Output

Relevant JCF types: Deque, ArrayList, LinkedList

========== FifoQueue ==========
{} (true)

Adding
------
0 -> {0} (false)
10 -> {0, 10} (false)
20 -> {0, 10, 20} (false)
30 -> {0, 10, 20, 30} (false)
40 -> {0, 10, 20, 30, 40} (false)
50 -> {0, 10, 20, 30, 40, 50} (false)
60 -> {0, 10, 20, 30, 40, 50, 60} (false)
70 -> {0, 10, 20, 30, 40, 50, 60, 70} (false)
80 -> {0, 10, 20, 30, 40, 50, 60, 70, 80} (false)
90 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)

Removing
--------
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 0
{10, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 10
{20, 30, 40, 50, 60, 70, 80, 90} (false) -> 20
{30, 40, 50, 60, 70, 80, 90} (false) -> 30
{40, 50, 60, 70, 80, 90} (false) -> 40
{50, 60, 70, 80, 90} (false) -> 50
{60, 70, 80, 90} (false) -> 60
{70, 80, 90} (false) -> 70
{80, 90} (false) -> 80
{90} (false) -> 90
{} (true)

Notes
What the demo is doing:

Similar to the stack demo, the newly created queue is printed
The queue is populated using the add method; both the value being added as well as the current (post-add) value of the queue are printed for each add
Elements are then removed from the queue until the queue is empty; the (pre-removal) queue and the removed elements are both printed

Priority Queue

A priority queue removes the largest (smallest) element in the queue. The challenge is to do this in an efficient manner. We'll investigate that later.

removal of highest priority element

Having the largest/smallest be at one end requires some sort of sorting
Obtaining the largest/smallest upon removal requires searching

Operations

add
remove
isEmpty

, or priority-baseD

interface PriorityQueue<E> {
	void add(T value)
	T remove()
	boolean isEmpty()
}

Motivation and Examples

Real-life
- prioritized (e.g. VIP) line/queue
Computer Science
- real-time OS, or priority-based scheduling algorithms
- sorting (priority queue sort)

Demo Code and Output

Relevant JCF type: PriorityQueue

========== PriorityQueue ==========
{} (true)

Adding
------
251 -> {251} (false)
80 -> {251, 80} (false)
241 -> {251, 80, 241} (false)
828 -> {251, 80, 241, 828} (false)
55 -> {251, 80, 241, 828, 55} (false)
84 -> {251, 80, 241, 828, 55, 84} (false)
375 -> {251, 80, 241, 828, 55, 84, 375} (false)
802 -> {251, 80, 241, 828, 55, 84, 375, 802} (false)
501 -> {251, 80, 241, 828, 55, 84, 375, 802, 501} (false)
389 -> {251, 80, 241, 828, 55, 84, 375, 802, 501, 389} (false)

Removing
--------
{251, 80, 241, 828, 55, 84, 375, 802, 501, 389} (false) -> 828
{251, 80, 241, 55, 84, 375, 802, 501, 389} (false) -> 802
{251, 80, 241, 55, 84, 375, 501, 389} (false) -> 501
{251, 80, 241, 55, 84, 375, 389} (false) -> 389
{251, 80, 241, 55, 84, 375} (false) -> 375
{251, 80, 241, 55, 84} (false) -> 251
{80, 241, 55, 84} (false) -> 241
{80, 55, 84} (false) -> 84
{80, 55} (false) -> 80
{55} (false) -> 55
{} (true)

Notes
What the demo is doing:

Again, the newly created priority queue is printed
Simply populating the priority queue with strictly increasing or decreasing values does properly illustrate its retrieval property of retrieving the largest (or smallest) value, so we populate it using random values (seed=12345, rang=1000); printing the values and post-add queue each time..
We then remove values until empty
- Had this bee a testing app rather than simply a demo, we would have included logic to ensure the values being retrieved so indeed conform to the property of a priority queue (in this case, the largest elements are being removed).

Deque (double-ended queue)

A double-ended queue (deque) provides both LIFO and FIFO storage retrieval (as well as a mixture). It is a container that permits insrtion/removal from either end.

insertion/removal from either end

Operations

addFirst
addLast
removeFirst
removeLast
isEmpty()

Interface

interface Deque<E> {
	void addFirst(E value)
	void addLast(E value)
	E removeFirst()
	E removeLast()
	boolean isEmpty()
}

Motivation and Examples

covers stacks and queues
- If we can find an efficient implementation for a deque (and we will), we can use it as an underlying implementation for them as well
Real-life
- Store with opposite entrances for each parking lot
Computer Science
- bounded browser history

Demo Code and Output

Relevant JCF type: Deque

========== Deque ==========
{} (true)

Adding First and Last Alternately
---------------------------------
0 -> {0} (false)
0 -> {0, 0} (false)
10 -> {10, 0, 0} (false)
10 -> {10, 0, 0, 10} (false)
20 -> {20, 10, 0, 0, 10} (false)
20 -> {20, 10, 0, 0, 10, 20} (false)
30 -> {30, 20, 10, 0, 0, 10, 20} (false)
30 -> {30, 20, 10, 0, 0, 10, 20, 30} (false)
40 -> {40, 30, 20, 10, 0, 0, 10, 20, 30} (false)
40 -> {40, 30, 20, 10, 0, 0, 10, 20, 30, 40} (false)
50 -> {50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40} (false)
50 -> {50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50} (false)
60 -> {60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50} (false)
60 -> {60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60} (false)
70 -> {70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60} (false)
70 -> {70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70} (false)
80 -> {80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70} (false)
80 -> {80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70, 80} (false)
90 -> {90, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70, 80} (false)
90 -> {90, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)

Removing First and Last Alternately
-----------------------------------
{90, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 90
{80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 90
{80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70, 80} (false) -> 80
{70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70, 80} (false) -> 80
{70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70} (false) -> 70
{60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60, 70} (false) -> 70
{60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60} (false) -> 60
{50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60} (false) -> 60
{50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50} (false) -> 50
{40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50} (false) -> 50
{40, 30, 20, 10, 0, 0, 10, 20, 30, 40} (false) -> 40
{30, 20, 10, 0, 0, 10, 20, 30, 40} (false) -> 40
{30, 20, 10, 0, 0, 10, 20, 30} (false) -> 30
{20, 10, 0, 0, 10, 20, 30} (false) -> 30
{20, 10, 0, 0, 10, 20} (false) -> 20
{10, 0, 0, 10, 20} (false) -> 20
{10, 0, 0, 10} (false) -> 10
{0, 0, 10} (false) -> 10
{0, 0} (false) -> 0
{0} (false) -> 0
{} (true)

Notes
What the demo is doing:

As with the priority queue, we have written a demo app, not a testing app; we are more interested in showing off the capabilities of the container, as opposed to testing it thoroughly

The newly created deque is printed

The deque's storage retrieval properties are closer to those of the stack and queue than to the priority queue in the sense it is purely position-based, as opposed to value-based as is true for the priority queue.

As such, we revert to our successive-values for loop we used previously for stacks and queue
However, here we can insert these values at both ends, and we proceed to populate the deque in that manner.

We then remove values alternately from front and back until the deque is empty

Once again, as a test, this is far from adequate, but we're only interested in illustrating the sorage/retrieval properties of the deque, and this does the trick

List

Same as sequence

Overview

random access, insertion/removal from anywhere
contains all the basic operations of a position-based container

Operations

get: random access of element at a specified position
set: random access modification of element at specified position
add: insertion at specified position
remove: remove element at specified position
size: number of elements

Interface

interface List<E> {
	E get(int index);
	void set(int index, E value);
	void add(int index, E value);
	E remove(int index);
	int size();
}

Motivation and Examples

most general of all sequences, no restrictions on insertion/removal, or access
ability to insert/remove anywhere provides support for sorted sequences
think of a train where we may need to put cars into the middle

Demo Code and Output

Relevant JCF type: ArrayList, LinkedList

Notes
What the demo is doing:

In the case of the list, we need to be able to perform insertions at arbitrary locations within the list. As such, the logic gets a bit more involved. We are also a bit more creative with our data in an attempt to clearly illustrate what is going on.
The newly-created list is printed.
We populate the list using increasing successive values (as for array, stack, and queue) and append the values (i.e., add to the end of the list)
- As such, we revert to our successive-values for loop we used previously for stacks and queue
- Notice that we have not provided a one-parameter add method that would append; rather we append by specifying the next available index
  - We'll change this soon enoug, and add a add(value) that will append to the en of the list without our having to specify the index.
We then iterate through the list — much as we did for the Array class above, and retrieve the elements via their index using the get method.
The next step inserts values into the moddle of the list (rather than the end) … this is the signature operations that distinguishes the list from the other containers. We use succesive values so we can follow the pattern easily (again, this is for illustrative, not testing, purposes).
We then perform a conditional remove; i.e., removing those elements from the list that are less than 1000 (these should be our original 'appended' values. This illustrates how we are able to move iteratively through the list and remove elements at arbitrary locations, closing up the holes as we perform the removal.

========== List ==========
size: 0
{} (true)

Appending (adding at end - value @ index)
-----------------------------------------
0 @ 0 -> {0} (false)
10 @ 1 -> {0, 10} (false)
20 @ 2 -> {0, 10, 20} (false)
30 @ 3 -> {0, 10, 20, 30} (false)
40 @ 4 -> {0, 10, 20, 30, 40} (false)
50 @ 5 -> {0, 10, 20, 30, 40, 50} (false)
60 @ 6 -> {0, 10, 20, 30, 40, 50, 60} (false)
70 @ 7 -> {0, 10, 20, 30, 40, 50, 60, 70} (false)
80 @ 8 -> {0, 10, 20, 30, 40, 50, 60, 70, 80} (false)
90 @ 9 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)

Getting
-------
0, 10, 20, 30, 40, 50, 60, 70, 80, 90

Inserting within the List (value @ index)
-----------------------------------------
9000 @ 9 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 9000, 90} (false)
8000 @ 8 -> {0, 10, 20, 30, 40, 50, 60, 70, 8000, 80, 9000, 90} (false)
7000 @ 7 -> {0, 10, 20, 30, 40, 50, 60, 7000, 70, 8000, 80, 9000, 90} (false)
6000 @ 6 -> {0, 10, 20, 30, 40, 50, 6000, 60, 7000, 70, 8000, 80, 9000, 90} (false)
5000 @ 5 -> {0, 10, 20, 30, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 80, 9000, 90} (false)
4000 @ 4 -> {0, 10, 20, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 80, 9000, 90} (false)
3000 @ 3 -> {0, 10, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 80, 9000, 90} (false)
2000 @ 2 -> {0, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 80, 9000, 90} (false)
1000 @ 1 -> {0, 1000, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 80, 9000, 90} (false)
0 @ 0 -> {0, 0, 1000, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 80, 9000, 90} (false)

Removing elements < 1000
------------------------
{0, 0, 1000, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 80, 9000, 90} (false) -> 90 @ 19
{0, 0, 1000, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 80, 9000} (false) -> 80 @ 17
{0, 0, 1000, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 70, 8000, 9000} (false) -> 70 @ 15
{0, 0, 1000, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 60, 7000, 8000, 9000} (false) -> 60 @ 13
{0, 0, 1000, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 50, 6000, 7000, 8000, 9000} (false) -> 50 @ 11
{0, 0, 1000, 10, 2000, 20, 3000, 30, 4000, 40, 5000, 6000, 7000, 8000, 9000} (false) -> 40 @ 9
{0, 0, 1000, 10, 2000, 20, 3000, 30, 4000, 5000, 6000, 7000, 8000, 9000} (false) -> 30 @ 7
{0, 0, 1000, 10, 2000, 20, 3000, 4000, 5000, 6000, 7000, 8000, 9000} (false) -> 20 @ 5
{0, 0, 1000, 10, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000} (false) -> 10 @ 3
{0, 0, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000} (false) -> 0 @ 1
{0, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000} (false) -> 0 @ 0
{1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000}

Associative (value-accessed)

Whereas sequences operate on positions (first, last, top, at a specific index), associative containers operate using the values of the elements.

Bag

Overview

associative container with no restrictions
duplicates are allowed — sometimes called a multiset
insertion/removal by value
membership / containment is basic operation

Operations

add: duplicates are added
remove: removes all occurrences of value
contains: returns true if value is in the bag
isEmpty

Interface

interface Bag<E> {
	void add(T value)
	void remove(T value)
	bool contains(T value)
	boolean isEmpty
}

Motivation and Examples

Real-life
- bag of items with duplicates
Computer Science

Demo Code and Output

No such container in Java, so I'm showing you the demo:

import java.util.*;

public class BagDemo {
	public static void main(String [] args) {
		System.out.println("========== Bag ==========");
		Bag<Integer> bag = new Bag<>();

		System.out.println(bag + " (" + bag.isEmpty() + ")");
		System.out.println();

		System.out.println("Adding");
		System.out.println("------");
		for (int i = 0; i < 10; i++) {
			System.out.print((i * 10) + " -> "); 
			bag.add(i * 10);
			System.out.println(bag + " (" + bag.isEmpty() + ")");
		}

		System.out.println("Adding again");
		System.out.println("------------");
		for (int i = 0; i < 10; i++) {
			System.out.print((i * 10) + " -> "); 
			bag.add(i * 10);
			System.out.println(bag + " (" + bag.isEmpty() + ")");
		}

		System.out.println();
		System.out.println("Search by value");
		System.out.println("---------------");

		for (int i = 0; i < 20; i++) 
			System.out.println((i * 10) + ": " + bag.contains(i*10));

		System.out.println();
		System.out.println("Removing");
		System.out.println("--------");

		Random random = new Random(12345);
		while (!bag.isEmpty()) {
			int value = random.nextInt(10)*10;
			if (bag.contains(value)) {
				System.out.print(bag + " (" + bag.isEmpty() + ")");
				bag.remove(value);
				System.out.println(" -> " + value);
			}
		}
		System.out.println(bag + " (" + bag.isEmpty() + ")");
	}
}

Notes
What the demo is doing:

The newly-created bag is printed.
We populate the bag using increasing successive values (as for array, stack, and queue)
We repeat the previous population step to show how duplicates are permitted in the bag.
- Using a series of successive values in a pattern makes all of this much simpler. (Again a proper test would have to do more than use simple patterns of values).
We then search for a number of values, choosing values to search for from those we inserted into the bag as well as some we didn't.
We remove values until the bag is empty. Again, using a pattern if values makes this logic relatively straightforward.
- Notice that remove removes all occurrences of the value
Finally, the (empty) bag is printed.

========== Bag ==========
{} (true)

Adding
------
0 -> {0} (false)
10 -> {0, 10} (false)
20 -> {0, 10, 20} (false)
30 -> {0, 10, 20, 30} (false)
40 -> {0, 10, 20, 30, 40} (false)
50 -> {0, 10, 20, 30, 40, 50} (false)
60 -> {0, 10, 20, 30, 40, 50, 60} (false)
70 -> {0, 10, 20, 30, 40, 50, 60, 70} (false)
80 -> {0, 10, 20, 30, 40, 50, 60, 70, 80} (false)
90 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
Adding again
------------
0 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0} (false)
10 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10} (false)
20 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20} (false)
30 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20, 30} (false)
40 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20, 30, 40} (false)
50 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20, 30, 40, 50} (false)
60 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20, 30, 40, 50, 60} (false)
70 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20, 30, 40, 50, 60, 70} (false)
80 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20, 30, 40, 50, 60, 70, 80} (false)
90 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)

Search by value
---------------
0: true
10: true
20: true
30: true
40: true
50: true
60: true
70: true
80: true
90: true
100: false
110: false
120: false
130: false
140: false
150: false
160: false
170: false
180: false
190: false

Removing
--------
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 10
{0, 20, 30, 40, 50, 60, 70, 80, 90, 0, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 0
{20, 30, 40, 50, 60, 70, 80, 90, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 80
{20, 30, 40, 50, 60, 70, 90, 20, 30, 40, 50, 60, 70, 90} (false) -> 50
{20, 30, 40, 60, 70, 90, 20, 30, 40, 60, 70, 90} (false) -> 40
{20, 30, 60, 70, 90, 20, 30, 60, 70, 90} (false) -> 20
{30, 60, 70, 90, 30, 60, 70, 90} (false) -> 90
{30, 60, 70, 30, 60, 70} (false) -> 70
{30, 60, 30, 60} (false) -> 60
{30, 30} (false) -> 30
{} (true)

Set

insertion/removal by value
no duplicates

Operations

add: adds value element but only if not already in set
remove: removes value
isEmpty

Interface

interface Set<E> {
	void add(T value)
	void remove(T value)
	boolean isEmpty()
}

Motivation and Examples

Real-life
- registration into a course
- entering a contest
Computer Science
- website spider

Demo Code and Output

Relevant JCF type: HashSet, TreeSet

Notes
What the demo is doing:

The newly-created set is printed.
We populate the bag using increasing successive values (as for array, stack, and queue)
We repeat the previous population step to show how duplicates are ignored in the set.
- Same comment as for bag
We then search for a number of values, choosing values to search for from those we inserted into the bag as well as some we didn't.
We remove values until the bag is empty. Again, using a pattern if values makes this logic relatively straightforward.
Finally, the (empty) bag is printed.

========== Set ==========
{} (true)

Adding
------
0 -> {0} (false)
10 -> {0, 10} (false)
20 -> {0, 10, 20} (false)
30 -> {0, 10, 20, 30} (false)
40 -> {0, 10, 20, 30, 40} (false)
50 -> {0, 10, 20, 30, 40, 50} (false)
60 -> {0, 10, 20, 30, 40, 50, 60} (false)
70 -> {0, 10, 20, 30, 40, 50, 60, 70} (false)
80 -> {0, 10, 20, 30, 40, 50, 60, 70, 80} (false)
90 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
Adding again
------------
0 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
10 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
20 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
30 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
40 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
50 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
60 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
70 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
80 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)
90 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false)

Membership testing
------------------
0: true
10: true
20: true
30: true
40: true
50: true
60: true
70: true
80: true
90: true
100: false
110: false
120: false
130: false
140: false
150: false
160: false
170: false
180: false
190: false

Removing
--------
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 10
{0, 20, 30, 40, 50, 60, 70, 80, 90} (false) -> 0
{20, 30, 40, 50, 60, 70, 80, 90} (false) -> 80
{20, 30, 40, 50, 60, 70, 90} (false) -> 50
{20, 30, 40, 60, 70, 90} (false) -> 40
{20, 30, 60, 70, 90} (false) -> 20
{30, 60, 70, 90} (false) -> 90
{30, 60, 70} (false) -> 70
{30, 60} (false) -> 60
{30} (false) -> 30
{} (true)

Map (Dictionary)

Different than the others; functionality is not quite that of the containers we've been looking at; rather a map is more of a lookup facility

Overview

insertion/removal of key/value pair
lookup (search) by key
set of pairs

Operations

put: add a key/value pair; if it's already there, existing pair is overwritten
get: retrieves value associated with specified key
remove: removes key/value pair corresponding to specified key
contains: true if key is in the map
isEmpty

interface Map<K, V> {
	void put(K key, V value)
	V get(K key)
	void remove(K key)
	bool contains(K key)
	boolean isEmpty()
}

Motivation and Examples

Real-life
- dictionary (of words)
Computer Science
- compiler symbol table

Demo Code and Output

Relevant JCF type: HashMap, TreeMap

Notes
What the demo is doing:

We populate the map; to make the logic simpler, we use a successive sequence of integers as keys, and their squares as the lookup values
We then do lookup, selecting as our key numbers from within the our initial population range as well as values outside of the range. Again this keeps things simple, yet allows us to see the map in action
Finally we remove the inserted values from the map.

========== Map ==========
Putting
(10: 100) -> {(10, 100)}
(11: 121) -> {(10, 100), (11, 121)}
(12: 144) -> {(10, 100), (11, 121), (12, 144)}
(13: 169) -> {(10, 100), (11, 121), (12, 144), (13, 169)}
(14: 196) -> {(10, 100), (11, 121), (12, 144), (13, 169), (14, 196)}
(15: 225) -> {(10, 100), (11, 121), (12, 144), (13, 169), (14, 196), (15, 225)}
(16: 256) -> {(10, 100), (11, 121), (12, 144), (13, 169), (14, 196), (15, 225), (16, 256)}
(17: 289) -> {(10, 100), (11, 121), (12, 144), (13, 169), (14, 196), (15, 225), (16, 256), (17, 289)}
(18: 324) -> {(10, 100), (11, 121), (12, 144), (13, 169), (14, 196), (15, 225), (16, 256), (17, 289), (18, 324)}
(19: 361) -> {(10, 100), (11, 121), (12, 144), (13, 169), (14, 196), (15, 225), (16, 256), (17, 289), (18, 324), (19, 361)}

Getting

5 is not in the map
6 is not in the map
7 is not in the map
8 is not in the map
9 is not in the map
10 maps to 100 in the map
11 maps to 121 in the map
12 maps to 144 in the map
13 maps to 169 in the map
14 maps to 196 in the map
15 maps to 225 in the map
16 maps to 256 in the map
17 maps to 289 in the map
18 maps to 324 in the map
19 maps to 361 in the map
20 is not in the map
21 is not in the map
22 is not in the map
23 is not in the map
24 is not in the map

Removing
10 -> {(11, 121), (12, 144), (13, 169), (14, 196), (15, 225), (16, 256), (17, 289), (18, 324), (19, 361)}
11 -> {(12, 144), (13, 169), (14, 196), (15, 225), (16, 256), (17, 289), (18, 324), (19, 361)}
12 -> {(13, 169), (14, 196), (15, 225), (16, 256), (17, 289), (18, 324), (19, 361)}
13 -> {(14, 196), (15, 225), (16, 256), (17, 289), (18, 324), (19, 361)}
14 -> {(15, 225), (16, 256), (17, 289), (18, 324), (19, 361)}
15 -> {(16, 256), (17, 289), (18, 324), (19, 361)}
16 -> {(17, 289), (18, 324), (19, 361)}
17 -> {(18, 324), (19, 361)}
18 -> {(19, 361)}
19 -> {}

Sorted Associatives

for searching / display purposes
set
map

CISC 3130 Data Structures Containers I Introduction to Containers — ADT's; Motivation & Examples

Overview

ADT's Revisited

The Containers/Collections

Array

Overview

Operations

Interface

Motivation and Examples

Demo Code and Output

Sequence (position-accessed)

Stack

Operations

Motivation and Examples

Demo Output

Queue (Single-ended)

FIFO Queue

Overview

Operations

Interface

Demo Output

Priority Queue

Operations

Motivation and Examples

Demo Code and Output

Deque (double-ended queue)

Operations

Interface

Motivation and Examples

Demo Code and Output

List

Overview

Operations

Interface

Motivation and Examples

Demo Code and Output

Associative (value-accessed)

Bag

Overview

Operations

Interface

Motivation and Examples

Demo Code and Output

Set

Operations

Interface

Motivation and Examples

Demo Code and Output

Map (Dictionary)

Overview

Operations

Motivation and Examples

Demo Code and Output

Sorted Associatives

Summary of Containers and Their Operations

Code Used in This Lecture

CISC 3130
Data Structures
Containers I
Introduction to Containers — ADT's; Motivation & Examples