辅导Data structures Assignment、辅导java IterableQueue 、辅导java 数据结构编程

Introduction

Data structures are a core part of the design of most applications. In this first assignment you will

implement three concrete data types that will be used in a simulation of an air traffic management

system. The simulation is based on the OneSKY Australia project, which will provide integrated air

traffic management for all of Australia’s airspace.

Details

You will implement and test three different data structures. The data structures are a Cube (a threedimensional

array-like structure), IterableQueue and an Iterator that can iterate over the

IterableQueue. You are provided with Java interfaces to define these abstract data types (ADTs).

You are also provided with initial shells of the classes for the concrete data types (CDTs) that you

need to implement. You are provided with some initial JUnit tests for the CDTs. You will need to

implement further JUnit tests to fully test your CDTs.

The Cube ADT is a collection that holds items in a three-dimensional grid layout. Each item in the

grid is accessed by an (x, y, z) coordinate tuple. The Cube<T> interface defines the public methods

and behaviours of the ADT. You need to implement the BoundedCube<T> class to provide a

concrete implementation of the data structure.

The IterableQueue ADT is a collection that holds items in the order in which they are added. A

queue is commonly referred to as a “first-in, first-out” collection, meaning that the first item added

to the queue will be the first item removed from the queue. This queue is iterable meaning that it

is possible to access each element in the queue, starting at the front of the queue and progressing

towards the end of the queue. The IterableQueue<T> interface defines the public methods and

behaviours of the ADT. IterableQueue<T> extends the Iterable<T> interface, meaning that

you will need to implement the iterator method defined in java.lang.Iterable. You do not

need to implement the forEach and spliterator default methods defined in the Iterable<T>

interface. You need to implement the TraversableQueue<T> class to provide a concrete

implementation of the data structure.

The iterator method in the TraversableQueue<T> class will need to return an object that

implements the java.util.Iterator interface. This object will need to be able to iterate over

all the elements in an IterableQueue and provide access to each element in turn. The iterator

will start at the front of the queue and progress towards the end of the queue. If elements are

dequeued while the iterator is iterating over the queue, it is possible that there will no longer be an

element at the iterator’s position in the queue. If this happens the iterator’s next method should

throw a java.util.NoSuchElementException. One approach to implementing the iterator is

to make it a private inner class in the TraversableQueue class.

Two JUnit test classes are provided: BoundedCubeTest and TraversableQueueTest. They are

written using JUnit 4 and use the Hamcrest matcher framework. These provide a few initial tests of

the CDTs you need to implement. You will need to implement further JUnit tests of your CDTs. Your

own JUnit tests should be in classes called: MyBoundedCubeTest and MyTraversableQueueTest.

You do not need to duplicate the provided tests in your test classes. Do not add tests to the provided

JUnit test classes. Your JUnit tests must be written using JUnit 4 but do not need to use the Hamcrest

matcher framework.

COMP3506 / 7505 Semester 2, 2018

You are also provided with a very simple air traffic management simulator that makes use of the

CDTs. It provides both an automated and interactive mode of operation. Interactive mode is started

by launching the application with no command line parameters (e.g. java OneSky). Automatic

mode is started by launching the application with two command line parameters, one to indicate

auto mode and the other being the number of iterations of the simulation (e.g. java OneSky auto

1000). You do not need to implement any features in the simulator. It is provided simply as an

example of how the ADTs could be used.

Constraints

You may not change anything in the provided ADT interfaces. You may not move any provided

classes or interfaces to different packages. You may not provide any public methods in the CDT

classes that are not implementations of the methods defined in their interfaces. You may not use

anything from the Java Collections framework in the JDK, aside from the Iterable and Iterator

interfaces that are used by the provided ADT interfaces. You may make use of the Comparable or

Comparator interfaces, if you wish, in your solution. Your implementations of the CDTs must be

based on basic Java language constructs and not data structure or algorithm libraries. You may not

add or remove methods to or from the provided JUnit test classes. You must provide public

constructors for the CDT classes that correspond to the CDT object creation in the provided JUnit

test classes.

Your code must compile using the standard Oracle JDK version 8 or Open JDK version 8. It is not

acceptable that your code only works in your IDE. Note that IntelliJ provides inaccurate code

coverage data for test cases.

You may provide as many other public, and non-public, constructors as you see fit for your CDT

classes. You may add extra non-public data members or methods to the CDT classes. Use these to

keep the method logic simple and to avoid repeating code. You may add non-public classes to the

design to help with the implementation of your CDTs.

Design Considerations

The OneSky simulation application is meant to be able to represent the entire Australian airspace.

For simplicity we will say that the Australian airspace is a cube that is 5321 kilometres from west to

east, by 3428 kilometres from north to south, by 35 kilometres high. This corresponds to latitudes

8 to 44 degrees south and longitudes 108 to 156 degrees east. It also accounts for the maximum

altitude at which jet aircraft can fly.

For the purposes of the simulation, we will say that aircraft are meant to be separated at all times

by one kilometre. Each cell in the BoundedCube will represent one cubic kilometre. We will also

say that the Australian airspace will contain a maximum of 20,000 aircraft at any one time. Your

BoundedCube design should take into consideration efficient use of memory and must be able to

represent the entire Australian airspace on a computer with 8 GB of memory.

Each cell in the Cube must be able to accommodate more than one aircraft because it is possible

for aircraft to encroach on each other’s space. In the simulation, the addAircraft method in

AirSpace checks to see an aircraft is encroaching on another aircraft’s space.

The purpose of the IterableQueue is to provide an ability to access all elements in the queue. For

the simulation this could be to simulate contacting all aircraft in a single cell of the airspace to warn

that they are too close together. Or, as is done in the interactive mode of the simulation, it allows

simulation of searching for aircraft that have been identified by radar but not yet plotted in the

airspace.

COMP3506 / 7505 Semester 2, 2018

The OneSky simulation is intentionally incomplete and only creates aircraft that are populated into

the airspace. You are not expected to add any new functionality to the simulation. It is provided

solely as a context to be considered when designing the CDTs.

Analysis

In the JavaDoc comments for your CDT classes indicate the run-time efficiency of each public

method. Use big-O notation to indicate efficiency (e.g. O(nlogn)). This should be on a separate line

of the method’s JavaDoc comment, as the last line of the description and before any @param,

@return or @throws tags. When determining run-time efficiency of a method, take into account

any methods that it may call.

In the JavaDoc comments for your CDT classes indicate the memory usage efficiency of the data

structure. This should be in the JavaDoc comment for the class and should be on a separate line,

which is the last line of the description and before any @author, @see or any other tags.

In a comment at the end of each CDT class, provide a justification for the design choices that you

made in implementing the CDT. The justification should consider the run-time and memory space

efficiency of the data structure and methods in the context of the air traffic management simulation.

For the BoundedCube class, ensure that your justification clearly considers memory usage in the

context of the OneSky simulation. In this simulation there will be a proportionally very small number

of occupied cells in the cube data structure. Your justification should compare alternative

approaches to implementing the data structure. If you think your implementation has limitations,

describe an alternative implementation that would be more suitable for the OneSky simulation.

Provide proper bibliographic references and citations for any resources that you use in designing

your implementations of the CDTs or in analysing the CDT design. Follow IEEE referencing standards

and place the bibliographic references at the end of your justification comment in each CDT file.

Submission

You must submit your completed assignment electronically through Blackboard. You should submit

your assignment as a single zip file called assign1.zip (use this name – all lower case). This zip

file must contain the same directory structure provided in the original assign1.zip that contained

the initial code for the assignment. Submissions that do not conform to the requirements (e.g.

different directory structures, packages or classes) may not be marked.

You may submit your assignment multiple times before the deadline – only the last submission will

be marked.

Late submission of the assignment will not be marked. In the event of exceptional personal or

medical circumstances that prevent you from handing in the assignment on time, you may submit

a request for an extension.

See the course profile for details of how to apply for an extension:

http://www.courses.uq.edu.au/student_section_loader.php?section=5&profileId=94208

Requests for extensions must be made no later than 48 hours prior to the submission deadline. The

application and supporting documentation (e.g. medical certificate) must be submitted via my.UQ.

You must retain the original documentation for a minimum period of six months to provide as

verification should you be requested to do so.

Please read the section in the course profile about plagiarism. Submitted assignments will be

electronically checked for potential plagiarism.

COMP3506 / 7505 Semester 2, 2018

Assessment and Marking Criteria

This assignment assesses course learning objectives:

1.1 Understand the internal workings of fundamental data structures and algorithms.

1.2 Determine the running time and memory space usage of common algorithms.

2.1 Adapt or invent new algorithms and data structures for software engineering problems.

2.2 Analyse the performance of algorithms built on fundamental data structures and algorithms.

2.3 Select and justify appropriate combinations of data structures and algorithms to solve

software engineering problems.

Completeness

The marking criteria below are based on the assumption that the entire assignment is completed. A

partially complete assignment will be accepted and marked but the final mark for the assignment

will be capped, based on the amount of work completed. The maximum marks that can be achieved

are:

 5 marks, if the assignment does not compile, based solely on the analysis provided.

 8 marks, if only the TraversableQueue, without an iterator, is implemented.

 12 marks, if only the TraversableQueue, with an iterator, is implemented.

 10 marks, if only the BoundedCube is implemented.

 20 marks, if all parts of the assignment are implemented.

COMP3506 / 7505 Semester 2, 2018