In this project, you’ll be expanding the example app we worked on throughout the first few days of the course. You’ll be learning some of the basic ideas of Android programming along with implementing a few basic data structures and patterns in Java. There is an emphasis not on Android UI (which is largely trivia, and I expect you to learn on your own) but instead on good software engineering: code reuse, testing, and thoughtful use of object-oriented design.

This assignment has 100 points, 20 of which are reserved for code style. I will grade code style fairly aggressively, so I strongly recommend taking it seriously. You don’t have to follow the style I would write down to a tee, but you need to make consistent choices about your code.

You will have three weeks to work on this assignment. I expect that good solutions to this project will take a few hundred lines (including logic, tests, etc..), but probably less than 1000. There are a lot of tricky things to learn in this project, especially since it’s in an unfamiliar language and will use concepts that you probably don’t fully understand quite yet. I strongly recommend you take the three-week time on the assignment as an indication of the fact that it will be a decent amount of work, more than you can get done in the last few days.

Good luck! I think this one will hopefully be a lot of fun.

Starter Code

Is available at the following git repo. Just fork this repo into a private repo for yourself.

https://github.com/kmicinski/cs395-p1

Please clone that repo and put it in a private repo. If you don’t have access to a private repo, sign up for a Github educational account (they’ll approve it) and make your repo private. I’m counting on you not to cheat by looking at other people’s repos.

For grading, I’ll have you share your repo with me.

Part 1: Fleshing Out an Implementation (10 points)

For this part of the assignment, you will complete the implementation of several methods in SquirrelList that I’ve left for you to do. All of these functions are marked with TODO in that file, along with a descriptive comment. Specifically, you will be adding the following methods (and their associated tests):

  • A constructor that allows you to create a list from an array
  • isEmpty
  • contains
  • toArray
  • remove
  • addAll
  • clear

You must also write associated tests for all of these methods. I’ve scattered a few throughout, some pass (but the ones that pass do so because the tests aren’t covering all of the behavior). For example, the test for isEmpty passes right now because that method always returns false.

Part 2: Debugging A Faulty Implementation (15 points)

For the first part of the assignment, you will be debugging some faulty code. The broken code is in the remove() function of the iterator for the implementation of SquirrelList.

I have written a passing test for the remove function in the test suite for SquirrelList. It is called list_removeLink`. However, despite my passing test, the function is still broken. I didn’t test enough of the behavior to reveal the bug (moral of the story: write good tests, and don’t expect your tests to cover everything).

In this part of the assignment, your job is to sit and think hard about the implementaito of remove to decide why it is broken. Then, I want you to write a test that fails but should pass. In other words, I want you to write a test that explains the correct behavior you would expect, but fails because the implementation is broken.

  • (5 points) Write a test exhibiting the broken implementation of remove.

Next, I want you to go through the remove function during the execution of the test. To do this, set a breakpoint on the remove function and examine the state of the iterator and the list as the function is executing.

  • (5 points) Show me a screenshot of your debugger during the execution of the remove function.

Last, I want you to fix the implementation of remove so that the test doesn’t break.

  • (5 points) Fix the implementation of remove so that the test no longer breaks.

Part 3: Implementing a Doubly-Linked List (15 points)

In this part of the assignment, I want you to write an implementation of a doubly linked list. A singly-linked list allows us to move forward, e.g., by using calls to next, but doesn’t allow us to move backwards. If we want to get to the previous node in a list, we have to start over from the beginning. A doubly-linked list has links on both sides, so that you can move forwards and backwards.

I’ve provided a skeleton implementation of a doubly linked list for you to extend yourself, which I’ve called SquirrelDoublyLinkedList. As with all of the things you write in this class, you also need a set of tests to go along with your implementation.

For this part, you need to implement all of the methods in the SquirrelDoublyLinkedList class so that all of the tests pass. You must also implement the iterator SquirrelDoublyLinkedListIterator. Along with your iterator, you must think up several tests to show to me that it works.

Right now, all of the tests in SquirrelDoublyLinkedListTest fail. For full points, you must make all of your tests pass. Additionally, you must write (at least one) test that shows that .prev is working correctly. I would do this by making a list that was three nodes long (A, B, and C), going to the third, and then going back two, finally checking to ensure that the thing you get at the end is A.

You will find most of the relevant code for this part in the file SquirrelDoublyLinkedList.java. You should extend the classes in the proper places. Keep in mind that all of the tests for a singly-linked list should still pass for your doubly-linked list. But–additionally–you should add some more tests that allow you to iterate backwards.

  • (5 points) The implementation of SquirrelDoublyLinkedList

  • (5 points) The implementation of SquirrelDoublyLinkedListIterator

  • (5 points) A passing test suite that includes relevant tests for all interesting behavior in the doubly-linked list

Regarding Code Reuse

The implementation of SquirrelList was a decent amount of code. At first glance, it may appear that you have to do a ton of that work again for SquirrelDoublyLinkedLiist. But if you find yourself repeating much code, you’re probably doing something wrong.

In fact, you really shouldn’t have to add that much code at all. The key to getting this part done easily is to realize that double-links are subclasses of single-links, so that any method that can work with single-links can also work on double links.

Part 4: Implementing a Custom Adapter With an Observer (15 points)

Right now, the app’s implementation relies upon SquirrelArrayAdapter, which uses an array to back the data. This is a common adapter for Android, and works well as long as your data fits into an array. But if you want to use a container other than an array, you can also write your own custom adapter.

For this part of the assignment, your task is to implement the custom adapter SquirrelListAdapter. You need to implement all of the methods in that class that I’ve currently left unimplemented. Many of them have standard implementations that should be a few lines.

The major conceptual challenge in this part is implementing the methods registerDataSetObserver and unregisterDataSetObserver. These methods allow setting up an “observer” for the underlying list. In short, an observer is an object that is “watching” for updates from some other object. We’ll talk a little bit about these in class, but observers are useful when some object needs to be updated based on updates to another object. For example, as the underlying list is updated (e.g., by adding more squirrels, as you’ll do in Part 5), the Android framework needs to know to redraw the screen. One way to do this is to have the framework register an observer on the list. The list class must be adapted to hold a list of observers (e.g., as a member variable of type List<Observer>). Then, every time the list changes, it will go through and call each of the observers’ .notify methods to notify them that the list has changed and allow them to do some work. Your task here is to ensure that this works with Android’s DataSetObserver class.

Many of the other methods are fairly routine, but you should take care to read the documentation and ensure you implement them correctly.

This will mostly be all-or-nothing grading in terms of if you were able to get the various parts. I’ll possibly give some partial credit, but don’t expect too much.

Part 5: A Task to Download, Parse, and Add Squirrels (15 points)

In this part of the assignment, you’re going to leverage the observer that you wrote in the last part. The way we’ve written our adapter, it tells the Android system how to draw the dataset in question. So, for example, when you open up the app, it shows you the first ten or so squirrels. The issue is that–once the data is drawn on the screen–it’s done. What happens if the squirrel data changes? E.g., what happens if a squirrel is added to the front of the list? In that case, the view is out of data with the data.

This is the purpose of the observer we just built. To test it out, we need to have something about the squirrel data change. To do this, we’re going to use a “task.”

The purpose of a task is to run computations that might take a long time. The phone is constantly redrawing the screen, processing user clicks, running your code, etc… The problem comes in when you have a piece of code that takes a long time to run. Say, for example, you were to download something from the internet. It may take a few seconds (or even minutes) to complete. During this whole time, if your code is running, you won’t be able to interact with the app at all: it will just feel like the screen is sitting there, totally stale and lifeless.

So realistic applications run multiple threads of computation. One special “main” thread does all of the drawing on the screen, and also processes things like button clicks, etc.. But you can launch other threads. One way to do this is to use Java’s low level Thread interface. You may be familiar with this from other courses. In this assignment, we won’t be using threads explicitly. Instead, we’ll be using a “task”, an abstraction built around threads to allow you to write code that runs in the background without you having to make a thread explicitly. Tasks have some advantages that we’re not going to talk about quite yet.

Start by reading the some of the following on asynctasks (I really recommend Mark Murphy’s book for this):

  • https://developer.android.com/reference/android/os/AsyncTask
  • https://www.journaldev.com/9708/android-asynctask-example-tutorial
  • https://stackoverflow.com/questions/9671546/asynctask-android-example

Your task will download JSON data from a particular URL and “parse” it into Squirrel objects that will be added to the list of squirrels. The JSON that I’ll give you looks like this:

[
  {
    "name": "African Ground Squirrel",
    "location": "Africa"
    "picture": "https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Borstenhoernchen-02.jpg/300px-Borstenhoernchen-02.jpg"
  },
  ...
]

In other words, it’s an array (list) of JSON objects, each with a field for name, location, and picture. You need to extend the task to programmatically download this JSON blob, parse it, and populate your ListView using the data you gleam from it. And it needs to work correctly: after loading the data into the list, you need to be able to click on it and see the right squirrel image (I’m using links to old images, though, so please do let me know if the links stop working and I’ll update the JSON!).

In going about this, you’ll need to use the org.json API included in Android. If you want to add another library and use that instead, you should feel free to do so.

Part 6: Downloading Squirrel Images Asynchronously (5 points)

In the original app I’m giving you, the squirrel picture is just a generic squirrel icon. I want you to figure out how to load an image from the corresponding URL and put it into the squirrel picture.

This part is mostly open-ended exploration on your part. I want you to figure out how to Google for the various things you need to get your work done, and then I want you to string them together to make the app work in the right way. Make sure that you download the image sent in the intent rather than just some fixed image (the image URL should be in the picture part of the intent object).

This part took me a good hour or two: ten minutes to do it, and fifty minutes to debug what was going on.

Part 7: Add Something (5 points)

This part is worth five points. Add something to the app that requires at least ten lines of (Java, not XML) code to function. In other words, you can’t get credit for this part by just messing around with the app’s styling and appearance. Think of something you’d like to add, and add that to the app.

To get full credit for this part, you must also add corresponding tests to show that the feature you wanted to add works.

Write me an email of about 2-3 paragraphs explaining what you did, where the code is at, and how you tested it to be sure it works.

Grading

I will add up all of the points here, which constitute 80% of the grade. The remaining 20% of the grade is based on code style. For full code style, you need to have the following:

  • Good indentation, variable names, proper use of @Override, etc…

  • Thoughtful comments on all complex methods (more than three lines) that follows the JavaDoc conventions and specifies return values, relevant things (e.g., preconditions when you think they’re meaningful) to the method’s operation, which exceptions are thrown, etc.. You don’t have to follow a rote formula, and if in doubt, write less. I reserve the right to take off points if your documentation is way too verbose (programmers have limited time, make comments succinct and to the point) or out of date with the code (this is a big problem when writing docs, keep them up to date).

  • Tests for all of the important parts of your program. This includes both unit tests and integration (/instrumentation) tests. Tests should be both good and orthogonal: I will take off points if I see things like 20 tests that all cover the same behavior in the program. In my experience, new programmers have a bad habit: they tend to write too many tests for simple parts of the code (e.g., getters), and they write too few tests for complex parts of their code. The number of tests you have should scale with the complexity of the code, which is not always related to its line count. Specifically do not write tests for very simple functions like getters and setters.

  • Avoid redundancy. If I see any code duplication, ever, I’m going to take off points. For example, in this assignment, I could have copied all of the code from SquirrelIterator to SquirrelDoublyLinkedListIterator, rather than extending the class. This is an example of redundant code. To understand why this is so important, think about what happens if you were to change SquirrelIterator: you’d likely also want to change SquirrelDoublyLinkedListIterator (since a SquirrelDoublyLinkedList extends from a SquirrelList). If you had to do this manually, it would be a bit frustrating, but it would be even worse if you forgot to do it. This is a frequent source of subtle bugs.

Last, it’s hard to write apps that work. Testing your app to make sure it’s bullet-proof is important, but an often overlooked aspect by students. I want you to write code that works really well. The difference between “kind of working” code and “totally working” code is often pretty vast. So I will deduct 7% from your final grade if–at any point–I was able to observe a crash in the app. I’ll write you to explain the behavior.

Rubric

  • Part 1 (X)/10
  • Part 2 (X)/15
  • Part 3 (X)/15
  • Part 4 (X)/15
  • Part 5 (X)/15
  • Part 6 (X)/5
  • Part 7 (X)/5
  • Style:
    • (X)/5 Low-level things, variable names, indentation, proper annotations
    • (X)/5 Comments on relevant things, following proper javadoc convention
    • (X)/5 Proper testing (Yes, I will take off twice, it’s that important!)
    • (X)/5 Avoiding redundancy, thoughtful object-oriented design
  • Total: 100
  • Adjustment factors:
    • You will lose 7% if I can figure out how to get your app to crash just by using it. I will be taking your app and playing around with it a bit. If–at any time as I run it–I see a crash (for any reason), you will lose 7% off your total grade.
    • +3% if you tackle an especially hard debugging challenge and wrote a test demonstrating the failure, and then fixed the problem. If you do this, write me an email. This is at my discretion. No points awarded (/ don’t email me) if you can’t figure out how to write a test that exhibits the behavior.

Questions to Think About

  • When would using protected be advantageous, versus private?

  • The function registerDataSetObserver allowed you to cleanly separate the implementation of the view updating (done by the Android framework) and the implementation of the underlying data model (the linked list). How does this help us in designing robust code? What would have happened if we had simply stuck the code to update the view inside of the List class? Would that be a good design? (Answer: No, because of separation-of-concerns)

  • If you had done this project over again, what unit test would you have written up front to make your life easier?