You are probably being recorded (and transcribed) [at least if Sam is here and can get the technology working]
Approximate overview
Comment from student: “I feel like I’m struggling.”
Grid.eqv
. You should be able to pull from
the master to get that fixed.If you’d like to suggest token events, please let me know in advance of class.
TLAs
We are designing an ADT similar to the association lists or hashes that you may have learned in CSC-151.
Generalize arrays so that we can use “any” comparable object as an index rather than just integers. (We use the term “key” rather than “index” just to be confusing.)
public class Dictionary<K,V>
Think about parameter types, return types, exceptions.
public void set(K key, V val) throws NullKeyException
- sets the value assigned to key.
public V get(K key) throws NoSuchKeyException, NullKeyException
- get the value with
the given key.public void remove(K key) throws NullKeyException
- remove entry with the given key.
If there is no such entry, does nothing.public boolean hasKey(K key) throws NullKeyException
- determine if the key exists.public String toString()
- Build a string of the form
“{key:value, key:value, key:value, … key:value}”.public Dictionary<K,V> clone()
- Make a copy of the dictionary.public void swap(K key1, K key2)
- swap the values associated
with key1
and key2
. (Beyond the basics.)public void um(void)
- Pauses.public void updateKey(K oldkey, K newKey)
- change a key.
set(newKey, get(oldKey))
+ remove(oldKey)
public void equals(Dictionary<K,V> other)
- check if the other
dictionary has exactly the same set of key/value pairs as this
dictionary.sort
RuntimeException
).key1
and key2
are equal if key1.equals(key2)
,
which is the Java standard.See whiteboard or assignment.
Pair<K,V> associations;
int size;
get(K key)
- go through the array, and for each element, see if the key
in the pair is equal to the key. If so, return the value. If we run out
of pairs, through a NoSuchKeyException
.
set(K key, V val)
- go through the array. For each elment, see if the
keys match. If so, replace the value. If we run out of elements, add a
new pair. (Perhaps use hasKey
to help.) When adding a new pair, we may
have to grow the array.
Arrays.copyOf(T[] original, int newLength)
public AssociativeArray<K,V> {
Pair<K,V> associations;
@SuppressWarnings
public AssociativeArray() {
this.associations = new (Pair<K,V>) new Object[BASE_SIZE];
this.size = 0;
} // AssociativeArray
} // AssociativeArray<K,V>
boolean hasKey(K key)
- Loop through every single value. If we find a
matching key, return true. If you finish looking at everything, return false.
void remove(K key)
(v1) - Loop through every value. If we find a matching
key, you should have an index. Copy over every element but that one into
a new array.
void remove(K key)
(v2) - Loop through every value. If we find a matching
key, you should have an index. Shift everything up starting at that index.
void remove(K key)
(v3) - Loop through every value. If we find a matching
key, you should have an index. Put a null there. [Sam’s year’s of experience
suggest that putting nulls in the middle may complicate our lives.]
void remove(K key)
(v4) - Loop through every value. If we find a matching
key, you should have an index. Put the last thing there. (The last thing
is at index size-1
.
Linear: Does this grow directly with the number of elements in the AA?
Constant: Is it independent of the number of elements in the AA?
get
- Linear: We have to look at the key/value pairs, and may
potentially look at all of them.
set
- Linear: We have to look at the key/value pairs, …
hasKey
- Linear: We have to look at the key/value pairs
remove (v2)
(shift) - Linear: We have to look at the key/value pairs.
We also have to shift potentially all the key/value pairs.
remove (v4)
(moves the last thing to the right place) - Linear: We
have to look at all the key/value pairs. But we only have constant
work once we’ve found it.
get
.
See the assignment and the repo.
Write tests early. Pull other tests. Tell me when you add tests.
Will we have merge conflicts?
I hope not. But part of the point is to get you used to working on a large collaborative repository.
How are we going to work with two repositories?
The testing repository gets cloned into the middle of the main repository. GitHub + VSCode are smart enough to deal with two overlapping repos.
You will only turn in the code for AssociativeArrays.
Will you add tips for each LA so that we don’t go in the wrong direction?
Part of the broader goal of the course is that you develop skills at figuring out how to describe your skills.
But yes, I will try to add tips. I may also add some verbally in class (or ask you to come up with some).
If we are just having a reading in composition, why do we have to answer an LA on that?
Because you’ve been dealing with the more basic form of composition since you started writing objects, and the LA only asks you to explore the more basic form of composition.
Also: You don’t have to answer tha LA. You can hold off another week or more.
I’m spending significantly more than five hours on mini-projects. Any suggestions?
Ask for help (preferably on the Questions channel) after you’re stuck for five minutes. Generally, if you can’t solve it in five minutes, you also won’t solve it in thirty minutes.
Will the redos for the mini-projects be posted soon?
Yes.
How many group mini-projects will there be?
Probably between three and four.
Do both partners need to turn in a token for a late group mini-project?
Yes.
Will we get grade reports soon?
Yes. Probably this weekend.
Will we get other grades before the grade report?
Probably.
What is a “good commit”?
It has a good description.
It’s not “I committed everything”.
Smaller is better.
Does it count if the commit is on a branch?
Yes.
We couldn’t push and pull. Why?
Next time, send me the message.
If someone has changed the repo, you’ll need to pull before you push.
When you pull, you may get merge conflicts. If you do, read through the file that has the merge conflicts, choose which code to keep, add and commit.
What is going on with the git fetch upstream
?
You are working with a fork of another repository.
That other repository may be updated (e.g.,when Sam realizes he screwed up
Grid.eqv
or Sam adds more tests).
You need a way to upll the updates from the primary repository into your fork (and then into your clone).
Two mechanisms.
Click the magic button on GitHub.
Create an upstream link and type magic commands.
Is the way inheritance works similar to the way that pointers do?
Inheritance requires pointers (or “references”) behind the scenes, but it’s more the concept that you automatically delegate method calls to the parent class, which I’d say is independent of pointers.
What should I do if I want to inherit from three classes, ex SmileStudentTeacherChef? (I felt composition + inheritence could only deal with 2 parent classes.)
Use composition. Composition can handle an arbitrary number of delegated classes. It’s just a bit more work on your end.
Please follow the setup instructions for MP4.
If you like, talk to your parter about MP3.