Java代写:SER222 Implementing An Abstract Data Type

实现一个矩阵的抽象数据类型,能实现矩阵的算术方法。

Summary

Using immutability, we will construct a reliable class for handling matrices. We will also discuss a basic suite of tests for this new class.

Background

Our goal will be to implement an “immutable matrix ADT”. Although some of that terminology should be familiar, some may not be. There is an optional appendix later in this document, that discusses mutability in a bit more detail than the textbook. The class we will construct will support computing basic matrix operations like addition and subtraction.
At first, a class for handling matrices might seem a little boring. However, matrices are an extremely valuable mathematical tool. Many algorithms in mathematics and scientific computing are built in terms of matrix operations. Matrices serve as a common language in which many mathematical problems many be expressed. The idea being if we have many problems that can be solved in the same way (i.e., a bunch of matrix operations), then we need only devise a single program (one that processes matrices) in order to solve all problems that are stated in that way… This is nice because we can optimize the piece of software that works with matrices, and see speedups for every problem that is expressed as matrices. Anyway, matrices are very common - computing matrix operations is pretty much all supercomputers do. Thus, implementing a matrix is useful - in fact, libraries that provide linear algebra operations (e.g., LINPACK) are among the most widely used in scientific and engineering research. Finding the fastest algorithms to compute matrix operations is very active area of research. People have built entire careers out of designing fast matrix processing algorithms!
This document is separated into four sections: Background, Requirements, Testing, and Submission. You have almost finished reading the Background section already. In Requirements, we will discuss what is expected of you in this homework. In Testing, we give some sample testing code for the matrix class, discuss how it works, and give some general pointers on how tests should be designed. Lastly, Submission discusses how your source code should be submitted on BlackBoard. At the very end of the document, there is an Appendix with optional reading on mutability. If you are confident with mutability, you may skip it.

Requirements

For this assignment, you will implement the provided matrix interface (see Matrix.java). This interface file defines not only which methods you must implement, but gives documentation that describes how they should work. Already provided for you is a base file to modify. The base contains an currently empty matrix class as well as some simple testing code. In order for it to be a reliable type, we will implement it as an immutable type. Creating this ADT will involve creating 9 methods:

  • MyMatrix(int[][] matrix) - a constructor. [4 points]
  • public int getElement(int y, int x) - see interface. [2 points]
  • public int getRows() - see interface. [2 points]
  • public int getColumns() - see interface. [2 points]
  • public MyMatrix scale(int scalar) - see interface. [5 points]
  • public MyMatrix plus(Matrix other) - see interface. [5 points]
  • public MyMatrix minus(Matrix other) - see interface. [5 points]
  • boolean equals(Object other) - see interface. [5 points] (Hint: see Point2D from earlier.)
  • String toString() - see interface. [5 points].

Be aware that some of the methods throw exceptions - this should be implemented.

Testing

Whenever you build a piece of software, you want to have some level of certitude that that piece of software does what you expect. This means testing! For this initial homework, you are provided with a set of simple tests to check if your program is functioning correctly. In the future, you may need to create your own tests. The following code is included in base file:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int [][] data1 = new int[0][0];
int [][] data2 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int [][] data3 = {{1, 4, 7}, {2, 5, 8}, {3, 6, 9}};

Matrix m1 = new base(data1);
Matrix m2 = new base(data2);
Matrix n3 = new base(data3);

System.out.println("m1 --> Rows: " + m1.getRows() + " Cols: " + m1.getColumns());
System.out.println("m2 --> Rows: " + m2.getRows() + " Cols: " + m2.getColumns());
System.out.println("m3 --> Rows: " + m3.getRows() + " Cols: " + m3.getColumns());

// check for reference issues
System.out.println("m2 --> \n" + m2);
data2[1][1] = 101;
System.out.println("m2 --> \n" + m2);

// test equals
System.out.println("m2 == null: " + m2.equals(null));
System.out.println("m3 == \"MATRIX\": " + m2.equals("MATRIX"));
System.out.println("m2 == m1: " + m2.equals(m1));
System.out.println("m2 == m2: " + m2.equals(m2));
System.out.println("m2 == m3: " + m2.equals(m3));

Let’s consider this code and its output. The first few lines of the code just create matrix data using 2D arrays. These are just setting up for our new class, we aren’t actually using it yet. The next step sees us creating a Matrix object for each array (m1, m2, m3). Next, we get to the actual testing. First, we display the size (rows and columns) for each matrix. The values we get should match the dimension of the 2D arrays that were created (0x0, 3x3, 3x3).
The next check is to see if we have correctly implemented our matrix as an immutable class. We display the contents of m2, make change in data2 (that was used to create m2), and then display the contents of m2 again. Recall that an object that is immutable should not change state - good thing that’s what we see in the output. The middle value does not change from 5 to 101. If it was not an immutable object, then changing the value inside of data2 would have the (potentially unintended) side effect of changing what is stored in m2. (Remember that arrays, like data2, are passed as references.)
Next, we check if equals has been implemented properly. Based on what’s being compared, equals should return true or false. If we compare a matrix to a null variable, a string, or a matrix containing different values, then it should return false. If we compare it to itself, or a matrix containing the same data, then it should return true.
Having verified that the class is immutable and supports comparison, we check if it supports the operations that should be implemented. For this homework, you are being given the output of these operations, and so can check you result versus ours. In the future, this might not be the case. You may have to run an algorithm by hand to determine what output should be expected. Note that the process of running it by hand will help you to understand the data structure (or algorithm) and may make it easier to implement. In addition to testing matrix operations that should work, we should also test operations that do not work. In this class, that would be when trying to add or subtract matrix with different size. For now, this code is commented, since running it should throw an exception.
Some basic principles: 1) test every method that is implemented. This gives us a basic level of code coverage (the amount of code used by tests) over a significant fraction of the code base. It would be even better if we had test cases that used each possible line of code in our program but that can become very difficult. 2) Test “edge cases”. That is, potentially special values that may invoke uncommon parts of the code base. For example, one of the first tests is to create a 0x0 matrix. While this matrix might not be practical, its parameters are unique and may cause issues. Typically one aims to test where an input changes significantly. For example, if the input was an integer, we might test some large position number, 1, 0, -1, and some large negative number. Note that we don’t really need to test several large numbers. Chances are, if one works, then the others will as well. We want to minimize our testing work by looking inputs as their character changes (e.g., goes from positive to negative in this example).

Submission

The submission for this programming assignment has only one part: source code submission.
Writeup: For this assignment, no write up is required.
Source Code:
Please rename and submit your code as “LastNameMatrix.java” The class inside of your file will also need to be renamed from base. There is no need to turn in the interface file (Matrix.java).

Appendix: Reference Types and Mutability

In this appendix, we review the idea of reference types in Java, and how mutability is impacted by it. Recall the Point2D example from our discussion of abstract data types. Consider what would happen if we ran the following code that used Point2D:

1
2
3
4
5
6
7
8
9
10
11
public class PointTester {
public static void doSomething(Point2D p) {
p.scale(5);
}
public static void main(String[] args) {
Point2D point = new Point2D(10, 10);
System.out.println(point.toString());
doSomething(point);
System.out.println(point.toString());
}
}

If we were to run this, we would get:

X: 10 Y : 10
X: 50 Y : 50

As you probably suspected, even though the call to scale happens inside of the doSomething() method instead of in the main, when main prints out the contents of the point for the second time, the x and y values have changed. This happens because classes are what is called a
reference typ e. For primitive types, such as int or double, when variables are passed around as parameters, their value is copied. Changing a int parameter in a method won’t change it’s value in the original caller. However, objects are not copied. Instead, Java passes a copy of the address where the object is stored in system memory. Since an address is passed, the method will know here to go and access the information (the state) that defines the class. In our example, when doSomething() is called , it is passed (via a parameter) the address of the Point2D that the main created. When the call to scale() is made on p inside of doSomething(), it changes the x and y values inside of the Point2D object that main created. Thus, when doSomething() completes and main displays the x/y values, it shows them as being five times larger. (Note that in addition to objects, arrays are also treated as reference types.) Thus we can see that the Point2D class is
can change. The opposite of this is an immutable class. At first, having a mutable class seems completely reasonable - how else would implement something like scaling the point? Why would you even want to?
Let’s start with the second question: Say we’re using the Point2D class in a game, and doSomething() is a method that displays a zoomed in version of the screen. If we’re implementing zoom, so everything appears larger, it makes sense it would scale the point to be larger. What happens if we run doSomething() to zoom in, but doSomething() lacks the code (e.g., p.scale(1/5)) to undo the zoom operation? Well, in that case doSomething() would finish without any issue, but then over in main, we would be left with the enlarged point. Not good! This happened because main allowed doSomething() to “mess around” with the information inside the point. Consider another potential issue, this time in a scientific calculation. If you have a massive matrix storing the simulation data for the analysis of a cancerous protein, you don’t want to
accidentally change the data while analyzing it - that would ruin the results! Our goal should be to design reliable a data type (class) that does not allow that to occur… an immutable one.
The basic idea of a immutable class isn’t that complicated: a class without any mutators, or shared references. But then how do we implement scale? Instead of having methods like void scale(double factor) that change the contents of the object, we will have methods like Point2D scale(double factor) that return a new copy of the point. Now, it is true that using immutable types can make your code must more safe (less error prone), but should remember that it will typically be slower than mutable implementation. (FYI, if you go on to study programming languages, you will encounter a programming language called LISP where all data is immutable.) It can be relatively straightforward to write an immutable type, the following needs to happen:

  • Mutators: These must be removed - there should be no way for someone to change the values inside of the class after it has been created. (When you go to complete the homework, you will find this has already been set up for you in the interface file.)
  • Constructors: We must make sure that no “reference types” (e.g., another object, or an array) leak into the object via the constructor. If this happens, our class will contain as instance data, some other object which is not immutable AND which may be accessible by another part of the program. Then, our object as a whole won’t be immutable either. The solution is to manually make a copy of any objects or arrays that are passed into the class we are building. The copy will then be unique to us, and will be effectively immutable (assuming we also make sure to leave it alone).

Consider the task making Point2D immutable. There are three methods we would need to change: setX, setY, and scale. These are only methods that can change the state of the point. Previously setX(int X) would change the value of the x member variable. When refactoring this object to immutable, we rewrite setX() so it returns a Point2D (instead of void), where the new point is built from the new x value being set and the existing y value. The same thing happens for setY(). scale() is a little different. There, we must change it to return a new point, but both x and y will change since they are both scaled.