Overview

• Preliminaries.
  • Admin.
  • Questions.
• Detour: Model-View-Controller.
• About HW 10.
• Review: Designing ADTs and Data Structures.
• A Dictionary ADT.
• Simple implementations of dictionaries.

Preliminaries

Admin

• Homework 10 discussed.
• Homework comment: If I find a significant number of formatting errors on your homework, I won't grade it.
• Reminder: Next Tuesday we're going to the Digital Commons roundtable.
• Upcoming extra credit opportunities:
  • Town Hall, today, noon or 7:30 p.m.
  • Learning from Alumni, Thursday, 2:15: Atul Gupta, Trustee
  • CS Extra, Thursday, 4:15: Hilary Mason '00
  • Evening chat with Hilary Mason '00, Thursday, 8-9 pm
  • National Philanthropy Day, Friday (Donate to a charity of your choice)
  • NO CS TABLE THIS WEEK!
  • Innovation Class, Friday, 12:45, ARH 302, Hilary Mason '00
  • Career Connections with Hilary Mason '00, Friday, 4:15-6:30 (???)
  • Swim meet, Saturday, 3pm
  • Digital Commons talk, Monday, November 18, 7:00 p.m. or so
  • CS Department Talk, Wednesday, November 20, noon
  • "Data Sovereignty: The Challenge of Geolocating Data in the Cloud", November 25, 4:15 JRC 101
  • "Gold Fever" by Andrew Sherburne '01 or so, 7:00 p.m., Monday, November 25, ARH 302
  • Tuesday, November 20, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!]

Detour: Model-View-Controller

• How hard would it be to rewrite your calculator to take input from a graphical UI rather than a textual UI?
• Three parts, MVC

About HW 10

Electronic version forthcoming

Policies:

• New partners! (Don't work with the group you've been working with the past assignment or two.)
• You may work alone.

Goals:

• Continue to explore textual UIs, incorporating MVC.
• Work with anonymous inner classes (or alternatives).
• Work with something like priority queues.

Context:

• Handling collections of Ushahidi Incidents.
• Maintain two versions of the collection:
  • The full version, which has all of the info.
  • A working version, from which elements have been selected.

Preparation:

• Assign someone to create a site at crowdmap.com.
  
  • Adam and Justus have suggested GSpot.crowdmap.com.
  • I'd suggest something a bit less controversial.
• You only have to do this ONCE! for the whole class.

Capabilities:

• Enter an Ushahidi server and load the incidents from that server.
• OPTIONAL: Remove elements from the working set that meet certain criteria (predicates), including compound criteria.
• OPTIONAL: Select only the elements from the working set that meet certain criteria, including compound criteria.
• OPTIONAL: Given one or more criteria (including compound criteria), print information on how many incidents in the working set meet the criteria.
• Choose an order in which the elements are reported (using a comparator).
• Get the ten highest-priority incidents
• Reset the working set.

Two UIs

• One for novices, which provides lots of information
• One for experts, which gives almost no information but permits nice concise commands.

Sample session with novice UI

Welcome to UshahidiManager v 0.0
What site do you want to use: https://csc207.crowdmap.com
https;//csc207.crowdmap.com has 107 incidents

Here are the available commands:
   (r)eset the working incident list
   (d)elete elements meeting particular criteria
   (s)elect elements meeting particular criteria
   (c)ount elements meeting particular criteria
   (p)rioritize incidents
   (v)iew the ten highest-priority incidents
   (q)uit

What would you like to do?
> d

How many criteria do you want to use in deleting elements?
> three
Sorry.  That's not something I understand.  Please enter numbers
using digits.
> -2
Sorry. You need to enter a positive number.
>  2
Okay, I'm going to ask you for two criteria.  Do you want (b)oth
of them to hold or (e)ither of them to hold?
> both
Great!

Tell me about criterion 1.  Do you want to filter by (d)ate, 
(n)umber, l(ocation), ...?
> d
What date?
> November 11, 2013
Do you want things (n)ewer than that date, equal to that date,
or (o)lder than that date?
> cold
I'm sorry.  I didn't understand "cold".  
Do you want things (n)ewer than that date, equal to that date,
or (o)lder than that date?
> old
Criterion 1: Incidents older than November 11, 2013.

Tell me about criterion 2.  Do you want to filter by (d)ate,
(n)umber, l(ocation), ...?
> r
You are filtering by report text.  Do you want reports that exclude
or include a particular piece of text?
> include
What text should each report include?
> South Campus
Criterion 2: Incidents that include "South Campus"

Deleting all elements that are older than November 11 and that
include "South Campus" ... Done.
72 incidents remain.

What would you like to do?
> ?
You've forgotten the commands already?  Okay, here we go
   (r)eset the working incident list
   (d)elete elements meeting particular criteria
   (s)elect elements meeting particular criteria
   (c)ount elements meeting particular criteria
   (p)rioritize incidents
   (v)iew the ten highest-priority incidents
   (q)uit

What would you like to do?
> p

Do you want to order by (d)date, (n)umber, lon(g)itude, la(t)itude, ...?
> g
Do you want them ordered by (i)ncreasing or (d)ecreasing longitude?
> i
Criterion 1 for ordering is longitude in increasing order.

Do you care about the ordering if two incidents have the same
longitude?
> yes

Okay, what do you want as the secondary ordering?  
Do you want to order by (d)date, (n)umber, lon(g)itude, la(t)itude, ...?
> t
Do you want them ordered by (i)ncreasing or (d)ecreasing latitude?
> i
Criterion 2 for ordering is latitude in increasing order.

Do you care about the ordering if the two incidents have the same
longtitude and the same latitude?
> no

Reordering elements.  Done.

A session with an expert UI

delete date before 11/11/2013
order by longitude increasing, latitude decreasing

Review: Designing ADTs and Data Structures

• What do we think about as we design an ADT?
  • (What the data are going to be.)
  • Philosophy: How do we think about the data?
  • Purpose: What's the goal of the use of the ADT? Why is it useful?
  • Methods!
  • A name
  • Approach: Maximalist and minimalist
• What do we think about as we design a DS? (Implement the ADT)
  • A name
  • Memory layout - Chunk of memory or small things linked together
  • Fields
  • How do we implement the methods?
  • Efficiency
• And when we do it in Java
  • Standard methods

A Dictionary ADT

• Philosophy: Like arrays, but with indices that don't have to be numbers (and certainly not just 0..n-1)
• Use Cases:
  • Database of people
  • Class directory
  • M-W
  • Symbol table; (let ((a 10) (* a a)))
• Alternate names: Map, Table, Associative Array, Hash
• Note: Two types:
  • The type of the key/index, we'll use K
  • The type of the value, we'll use V

• Methods

  • void put(K key, V value) - add a key/value pair to the dictionary, if there's already a value with that key, replace it
  • V get(K key) - look up the value with key K; if no such value appears, throws an error (can't return the key; it's the wrong type) or return null or a default value.
  • Iterator values();
  • Iterator keys();
  • V delete(K key) - delete the key/value pair with the given key, return the value we just deleted
  • boolean containsKey(K key)
  • boolean containsValue(V value);
  • Collection selectByValue(Predicate p) // Maximalist
  • Collection selectByKey(Predicate p) // Maximalist
  • void clear() - The nuclear option
  • Collection keys(Value v);
  • int size()
  • boolean isFull()
  • boolean isEmpty()

• Observation: Keys are expected to be unique

Simple implementations of dictionaries