代写 data structure Java COMP0004 Coursework Part I

COMP0004 Coursework Part I
Purpose: A more complex Java programming task to make sure you understand interfaces, abstract classes, nested classes, inheritance, overriding methods and using exceptions, in preparation for the main project work. There are a number of important concepts covered here, make sure you understand them all.
Submission: There is a single submission deadline for all the coursework in this module: Noon 22nd March 2019. You can complete this part at anytime before the deadline, but it is very strongly recommended that you complete it by the end of Reading Week (14th Feb).
While working on your code, the project files and source code (no compiled code) should be stored in a GitHub repository, so that you are using version control properly.
Marking: This part of the coursework is worth 15% of the module mark.
COMP0004 Part I Coursework
Inadequate (0-39)
Failed to demonstrate a basic understanding of the concepts used in the coursework, or answer the questions. There are fundamental errors, code will not compile, or nothing of significance has been achieved. (F)
Just Adequate (40-49)
Shows a basic understanding, sufficient to achieve a basic pass, but still has serious shortcomings. Code may compile but doesn¡¯t work properly. Not all concepts have been understood or the questions answered correctly.(D)
Competent (50-59)
Reasonable understanding but with some deficiencies. The code compiles and runs, the concepts are largely understood. This is the default for a straightforward, satisfactory answer. (C)
Good (60-69)
A good understanding, with possibly a few minor issues, but otherwise more than satisfactory. The code compiles, runs and demonstrates good design practice. Most expectations have been met. Most questions answered.(B)
Very Good (70-79)
A very good understanding above the standard expectations, demonstrating a clear proficiency in programming. All core questions answered.(A)
Excellent (80-100)
Programming at a level well above expectations, demonstrating expertise in all aspects. This level is used sparingly only where it is fully justified. All questions answered. (A+, A++)
A Bag data structure stores an unordered collection of values, allowing multiple copies of the same value (hence, is not a Set). Bags know how many occurrences (i.e., count) of each distinct value are in its collection. This coursework is about implementing Bag classes, making use of interfaces, an abstract class, inheritance, overridden methods and exceptions. The inspiration for Bags comes from the Smalltalk language. The Java language features needed to implement these classes were covered in the lectures but it would be a good idea to read up on them first.
The goal is to set up a framework that will support several classes providing different concrete Bag implementations. The framework structure is shown below.
This framework is based on the principles used by the data structure classes in the standard Java libraries but is intended to illustrate a range of programming concepts rather than be a practical design for a real framework.
The Iterator interface is defined in the standard Java library and declares the iterator method, so that each value stored in a data structure can be accessed in sequence. Implementing the Iterator interface allows a data-structure object to be used with the enhanced for loop (foreach).
The Bag interface defines the common methods for all Bag classes. Bag extends the Iterator interface, remembering that one interface can extend another. A variable of type Bag can reference any Bag object of a class that implements Bag (or inherits the implements relationship). This
1 of 4

COMP0004 Part I Coursework
enables ¡®Programming to an Interface¡¯, allowing code to be written using the Bag type without needing to be concerned about the exact type of Bag of objects it is working with at runtime.
For the coursework you are given the code of a basic version of the Bag framework, including one example Bag implementation called ArrayBag. You will find this code in a GitHub repository at:
https://github.com/UCLComputerScience/COMP0004Bag
Clone this repo into your directory on your local machine and then load it into IDEA by creating a new Maven project.
The example code uses generics so that the classes and interfaces are parameterised over the type of value held in a Bag. Hence, when declaring a variable of type Bag you would use this syntax:
Bag aBag; // Reference to a Bag of Strings
Some Bag methods are declared as throwing exceptions of type BagException, and a default maximum size is imposed on all bags of 1000 distinct (unique) values (don¡¯t confuse a value, with occurrences of a value). A different maximum size can be specified when a bag object is created. If an attempt is made to to create a bag with size greater than the maximum size, or less than 1, an exception should be thrown. In addition, if adding a value to a bag using the add or addAll methods would cause it to exceed the maximum size an exception should be thrown.
The AbstractBag class is an abstract class that provides common methods for concrete subclasses. This avoids duplicating the methods in the subclasses as they can just be inherited. An example addAll method is implemented, which creates a new Bag and adds the contents of the Bag it is called for and the argument Bag to the new Bag. The new Bag object returned is created using a Factory. A factory is a class that specialises in creating objects. The use of a factory avoids code having to name a specific concrete set class and decouples object creation from class naming. Factory is an example of a Design Pattern.
Class BagFactory implements a basic factory. When a program using Bags is started, the BagFactory is given the name of the Bag class (a String) that it will create objects of. The
2 of 4

BagFactory also implements the Singleton Pattern, meaning that only one instance object of the class can be created when the program is run (see the example code in the Main class included with the framework code).
The complete example Bag implementation class, ArrayBag, uses an Arraylist of Element objects as the private internal data structure used to store the values in the bag. Each Element holds a value (object reference) and an occurrence count.
Private nested classes are used to implement the Iterator interface to enable iteration of the bag object. Don¡¯t confuse Iterable with Iterator. Iterable defines the iterator method, while Iterator defines the next, hasNext and remove methods.
Note that class ArrayBag throws exceptions but does not catch any of its own exceptions. A Bag throws exceptions, while code using a Bag catches any exceptions using try/catch blocks. Make sure you understand the point being made here.
Core Questions
Q1. Implement a concrete class MapBag that uses an HashMap (dictionary) as its private data
structure. You can use the HashMap from the standard Java library.
Q2. Implement a concrete class LinkedListBag that uses a chain of linked list elements as its data structure. Do not use any linked list classes from the standard Java class libraries. A linked list element looks like this:
private static class Element
{
public E value;
public int occurrences;
public Element next;
public Element(E value, int occurrences, Element next)
{
this.value = value;
this.occurrences = occurrences;
this.next = next;
} }
This should be a nested class inside the LinkedListBag class.
Q3. Add a method called toString() to the AbstractBag class, that returns a string representation of the contents of a bag in this style: [ value: occurrences, value: occurrences, … ]
Remember that toString() is a method declared in class Object (the superclass of all other classes), and can be overridden by any of your classes to specialise the way it displays an object¡¯s value as a string. No code in the concrete subclasses should be changed, they can inherit the method you add to AbstractBag.
Q4. Add a removeAllCopies method to class AbstractBag and confirm it works when inherited by all the concrete classes. The method should have this signature and be declared in the Bag interface:
void removeAllCopies();
It makes sure that the occurrence count of all values stored in a Bag is set to one.
Q5. Add a bag subtract method, again in class AbstractBag, that returns a new Bag containing all values and occurrences that occur in the this bag but not the argument bag. The method should have this signature and be declared in the Bag interface:
Bag subtract(Bag bag);
3 of 4
COMP0004 Part I Coursework

Q6. (Harder) Add the ability to save the contents of a Bag to a file using a text representation, and to read the file and re-create the Bag object. Get this working for common types such as Integer, String, Double, etc. Getting file load/save working for any type you can put in a Bag is more complex – see if you can get something working.
Challenge Question
Q7. Modify your code to implement the Comparator interface for comparing values, rather than Comparable, allowing lambdas to be used to specify how comparison is done for the values you store in a Bag. Can you get this working for examples such as Bag> or Bag>?
4 of 4
COMP0004 Part I Coursework