# Does RunLengthEncoding class provide abstraction and encapsulation?

This review is in continuation with Part I mentioned in query.

As part of the assignment given in Part II from this link, here is the solution:

Ocean

/* Ocean.java */

package Project1;

/**
* The Ocean class defines an object that models an ocean full of sharks and
* fish.
* @author mohet01
*
*/
class Ocean {

/**
* Define any variables associated with an Ocean object here. These
* variables MUST be private.
*
*/
//width of an Ocean
private final int width;
//height of an Ocean
private final int height;

/**
* Below data member is the number of simulation time steps that a Shark
*  can live through without eating.
*/
private static int starveTime;

/**
*  Do not rename these constants.  WARNING:  if you change the numbers, you
*  will need to recompile Test4.java.
*
*/

public final static int EMPTY = 0;
public final static int SHARK = 1;
public final static int FISH = 2;

/*
* This method provides the starvation time in the Ocean for sharks
*/
public static int getStarvationTime(){
return starveTime;
}

/*
* This method provides the starvation time in the Ocean for sharks
*/
public static void setStarvationTime(int starveTime){
Ocean.starveTime = starveTime;
}

/*
* I preferred, 2d array of references to Critter objects
* rather than List. Reasons(correct me),
* 1) To display an array of ocean, it adds more logic in paint() method.
* 2) Checking 8 nearest neighbors of each Critter looks inefficient,
* For example: for an ocean of SEEFE
*                              FEEFE a 2x2 ocean, If i maintain
* a list of Critter for this 2x2 ocean, i need to traverse
* S->E->E->F->E->F to get my first nearest neighbor of Shark,
* In contrast, With 2d array, I would just use modulo operation as
* mentioned in update() method.  Let us see what happens!!!
*
*/
private Critter[][] oceanMatrix;

/**
* Constructor that creates an empty ocean with below dimension
*
* @param width
*            is the width of the ocean.
* @param height
*            is the height of the ocean.
*
*/
public Ocean(int width, int height){
this.oceanMatrix = new Critter[height][width];
this.width = width;
this.height = height;
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) {
oceanMatrix[row][col] = new Empty(row,col);
}
}
}

/**
* This method adds Critter in an ocean.
* @param object
*              is the Critter object to be added in Ocean.
*/
Point p = object.getLocation();
int x = p.getX();
int y = p.getY();
/*
* I understand that, location property make sense to be be moved
* to corresponding Critter<type> class as it's property, which i did, But
* also captured location property of a Critter Object in Ocean class(with
* above 3 lines of code) which is redundant and not relevant, But 2d array
* is more efficient than list, for checking neighbor in update() method.
* Are we Breaking SRS????
* So, Instead of List am using 2d array. Let us see what happens!!!
*/
oceanMatrix[x][y] = object;
}

/**
* This method returns either Critter Object reference
*
* @param x
*            is the x-coordinate of the cell whose contents are queried.
* @param y
*            is the y-coordinate of the cell whose contents are queried.
*/
public Critter cellContents(int x, int y) {
return oceanMatrix[x][y];
}

/**
* getWidth() returns the width of an ocean Object.
*
* @return
*          the width of the ocean.
*
*/
public int getWidth() {
return this.width;
}

/**
* getHeight() returns the height of an Ocean object.
*
* @return
*          the height of the Ocean.
*/

public int getHeight() {
return this.height;
}

/**
* timeStep() performs a simulation time step as described in README.
*
* @return
*          an ocean representing the elapse of one time Step.
*/

public Ocean timeStep() {

Ocean nextTimeStepSea = new Ocean(width, height);

for (int row = 0; row < this.height; row++) {
for (int col = 0; col < this.width; col++) {
Critter creature = this.cellContents(row, col);
}
}
return nextTimeStepSea;
}

/**
*  The following method is required for Part II.
*/

/**
*  addShark() (with three parameters) places a shark in cell (x, y) if the
*  cell is empty.  The shark's hunger is represented by the third parameter.
*  If the cell is already occupied, leave the cell as it is.  You will need
*  this method to help convert run-length encodings to Oceans.
*  @param x is the x-coordinate of the cell to place a shark in.
*  @param y is the y-coordinate of the cell to place a shark in.
*  @param feeding is an integer that indicates the shark's hunger.  You may
*         encode it any way you want; for instance, "feeding" may be the
*         last timestep the shark was fed, or the amount of time that has
*         passed since the shark was last fed, or the amount of time left
*         before the shark will starve.  It's up to you, but be consistent.
*/

public void addShark(int x, int y, int feeding) {
if (this.cellContents(x, y).getClass().getName().equals("Empty")){
}
}

/**
*  addFish() places a fish in cell (x, y) if the cell is empty.  If the
*  cell is already occupied, leave the cell as it is.
*  @param x is the x-coordinate of the cell to place a fish in.
*  @param y is the y-coordinate of the cell to place a fish in.
*/

public void addFish(int x, int y) {
if (this.cellContents(x, y).getClass().getName().equals("Empty")){
}
}

}


RunLengthEncoding

/* RunLengthEncoding.java */

package Project1;

/**
*  The RunLengthEncoding class defines an object that run-length encodes an
*  Ocean object.  Descriptions of the methods you must implement appear below.
*  They include constructors of the form
*
*      public RunLengthEncoding(int i, int j, int starveTime);
*      public RunLengthEncoding(int i, int j, int starveTime,
*                               int[] runTypes, int[] runLengths) {
*      public RunLengthEncoding(Ocean ocean) {
*
*  that create a run-length encoding of an Ocean having width i and height j,
*  in which sharks starve after starveTime timesteps.
*
*  The first constructor creates a run-length encoding of an Ocean in which
*  every cell is empty.  The second constructor creates a run-length encoding
*  for which the runs are provided as parameters.  The third constructor
*  converts an Ocean object into a run-length encoding of that object.
*
*/

class RunLengthEncoding {

/**
*  Define any variables associated with a RunLengthEncoding object here.
*  These variables MUST be private.
*/

private DList2 list;
private long sizeOfRun;
private int width;
private int height;
private int starveTime;
/**
*  The following methods are required for Part II.
*/

/**
*  RunLengthEncoding() (with three parameters) is a constructor that creates
*  a run-length encoding of an empty ocean having width i and height j,
*  in which sharks starve after starveTime timesteps.
*  @param i is the width of the ocean.
*  @param j is the height of the ocean.
*  @param starveTime is the number of timesteps sharks survive without food.
*/

public RunLengthEncoding(int i, int j, int starveTime) {
this.list = new DList2();
this.list.insertFront(TypeAndSize.Species.EMPTY, i*j);
this.sizeOfRun = 1;
this.width = i;
this.height = j;
this.starveTime = starveTime;
}

/**
*  RunLengthEncoding() (with five parameters) is a constructor that creates
*  a run-length encoding of an ocean having width i and height j, in which
*  sharks starve after starveTime timesteps.  The runs of the run-length
*  encoding are taken from two input arrays.  Run i has length runLengths[i]
*  and species runTypes[i].
*  @param i is the width of the ocean.
*  @param j is the height of the ocean.
*  @param starveTime is the number of timesteps sharks survive without food.
*  @param runTypes is an array that represents the species represented by
*         each run.  Each element of runTypes is Ocean.EMPTY, Ocean.FISH,
*         or Ocean.SHARK.  Any run of sharks is treated as a run of newborn
*         sharks (which are equivalent to sharks that have just eaten).
*  @param runLengths is an array that represents the length of each run.
*         The sum of all elements of the runLengths array should be i * j.
*/

public RunLengthEncoding(int i, int j, int starveTime,
TypeAndSize.Species[] runTypes, int[] runLengths) {
this.list = new DList2();
this.width = i;
this.height = j;
this.starveTime = starveTime;
if(runTypes.length != runLengths.length){
System.out.println("lengths are unequal");
}else{
for(int index=0; index < runTypes.length; index++){
this.list.insertFront(runTypes[index], runLengths[index]);
this.sizeOfRun++;
}
}
}

/**
*  restartRuns() and nextRun() are two methods that work together to return
*  all the runs in the run-length encoding, one by one.  Each time
*  nextRun() is invoked, it returns a different run (represented as a
*  TypeAndSize object), until every run has been returned.  The first time
*  nextRun() is invoked, it returns the first run in the encoding, which
*  contains cell (0, 0).  After every run has been returned, nextRun()
*  returns null, which lets the calling program know that there are no more
*  runs in the encoding.
*
*  The restartRuns() method resets the enumeration, so that nextRun() will
*  once again enumerate all the runs as if nextRun() were being invoked for
*  the first time.
*
*  (Note:  Don't worry about what might happen if nextRun() is interleaved
*/

/**
*  restartRuns() resets the enumeration as described above, so that
*  nextRun() will enumerate all the runs from the beginning.
*/

private void restartRuns() {
this.sizeOfRun = this.list.size;
}

/**
*  nextRun() returns the next run in the enumeration, as described above.
*  If the runs have been exhausted, it returns null.  The return value is
*  a TypeAndSize object, which is nothing more than a way to return two
*  integers at once.
*  @return the next run in the enumeration, represented by a TypeAndSize
*          object.
*/

private TypeAndSize nextRun() {
TypeAndSize obj = null;
if(this.sizeOfRun > 0){
obj = this.list.nTh(this.sizeOfRun);
this.sizeOfRun--;
}
return obj;
}

/**
*  toOcean() converts a run-length encoding of an ocean into an Ocean
*  object.  You will need to implement the three-parameter addShark method
*  in the Ocean class for this method's use.
*  @return the Ocean represented by a run-length encoding.
*/

public Ocean toOcean() {
Ocean sea = new Ocean(this.width, this.height);
TypeAndSize obj = null;
TypeAndSize singleArray[] = new TypeAndSize[this.width*this.height];
int savedIndex = 0;

/*Convert Doubly linked ist to 1d array */
while((obj = nextRun()) != null){
for(int index = savedIndex; index < (savedIndex + obj.runLength); index++){
/* TypeAndSize class is just data storage but not an abstraction */
singleArray[index].runLength = obj.runLength;
singleArray[index].type = obj.type;
}
savedIndex += obj.runLength;
}

/* Convert 1d array to 2d array Ocean */
for(int index =0; index < singleArray.length; index++){
if(singleArray[index].type == TypeAndSize.Species.EMPTY){
// Do nothing because ocean is created with empty objects.
}else if(singleArray[index].type == TypeAndSize.Species.FISH){
}else if(singleArray[index].type == TypeAndSize.Species.SHARK){
}
}

this.restartRuns();
return sea;
}

}


DList2

/* DList2.java */

package Project1;

/**
*  A DList2 is a mutable doubly-linked list.  Its implementation is
*  circularly-linked and employs a sentinel (dummy) node at the sentinel
*  of the list.
*/

class DList2 {

/**
*  sentinel references the sentinel node.
*
*  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/

protected DListNode2 sentinel;
protected long size;

/* DList2 invariants:
*  1)  sentinel != null.
*  2)  For any DListNode2 x in a DList2, x.next != null.
*  3)  For any DListNode2 x in a DList2, x.prev != null.
*  4)  For any DListNode2 x in a DList2, if x.next == y, then y.prev == x.
*  5)  For any DListNode2 x in a DList2, if x.prev == y, then y.next == x.
*  6)  size is the number of DListNode2s, NOT COUNTING the sentinel
*      (denoted by "sentinel"), that can be accessed from the sentinel by
*      a sequence of "next" references.
*/

/**
*  DList2() constructor for an empty DList2.
*/
public DList2() {
this.sentinel = new DListNode2();
this.sentinel.next = this.sentinel;
this.sentinel.prev = this.sentinel;
this.size = 0;
}

/**
*  insertFront() inserts an object of type TypeAndSizeAndHungerAndStarveTime at the front of a DList2.
*/
void insertFront(TypeAndSize.Species runType, int runLength) {
DListNode2 newNode = new DListNode2(runType, runLength);
newNode.next = this.sentinel.next;
this.sentinel.next.prev = newNode;
this.sentinel.next = newNode;
this.sentinel.next.prev = this.sentinel;
this.size++;
}

/**
* insertEnd() inserts an object of type TypeAndSizeAndHungerAndStarveTime at the end of a DList2.
* @param runType
* @param runLength
* @param starveTime
*/
void insertEnd(TypeAndSize.Species runType, int runLength){
DListNode2 newNode = new DListNode2(runType, runLength);
newNode.prev = this.sentinel.prev;
this.sentinel.prev.next = newNode;
newNode.next = this.sentinel;
this.sentinel.prev = newNode;
this.size++;
}

/**
*  removeFront() removes the first runObject (and first non-sentinel node) from
*  a DList2.  If the list is empty, do nothing.
*/
void removeFront() {
if(this.size > 0){
this.sentinel.next.next.prev = this.sentinel;
this.sentinel.next = this.sentinel.next.next;
this.size--;
}
}

/**
*  deleteEnd() removes the last runObject (and last non-sentinel node) from
*  a DList2 and returns.  If the list is empty, do nothing.
*/
void deleteEnd() {
if(this.size > 0){
this.sentinel.prev.prev.next=this.sentinel;
this.sentinel.prev=this.sentinel.prev.prev;
this.size--;
}
}

/**
* nTh() returns the nTh node
* @param nTh
* @return
*/
TypeAndSize nTh(long nTh){
DListNode2 node = this.sentinel.next;
int index = 1;
while(index < nTh ){
node = node.next;
index++;
}
return node.runObject;
}

/**
*  toString() returns a String representation of this DList.
*
*  DO NOT CHANGE THIS METHOD.
*
*  @return a String representation of this DList.
*/
public String toString() {
String result = "[  ";
DListNode2 current = sentinel.next;
while (current != sentinel) {
result = result + current.runObject.type + "," + current.runObject.runLength +"  ";
current = current.next;
}
return result + "]";
}

public static void main(String[] args) {
// DO NOT CHANGE THE FOLLOWING CODE.
}
}


DListNode2

/* DListNode2.java */

package Project1;
/**
*  A DListNode2 is a node in a DList2 (doubly-linked list).
*/

class DListNode2 {

/**
*  item references the item stored in the current node.
*  prev references the previous node in the DList.
*  next references the next node in the DList.
*
*  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/

TypeAndSize runObject;
DListNode2 prev;
DListNode2 next;

/**
*  DListNode2() constructor.
*/
DListNode2() {
this.runObject = null;
this.prev = null;
this.next = null;
}

DListNode2(TypeAndSize.Species runType, int runLength) {
this.runObject = new TypeAndSize(runType, runLength);
this.prev = null;
this.next = null;
}
}


TypeAndSize

/* TypeAndSize.java */

/* DO NOT CHANGE THIS FILE. */
/* YOUR SUBMISSION MUST WORK CORRECTLY WITH _OUR_ COPY OF THIS FILE. */

package Project1;

/**
*  Each TypeAndSize object represents a sequence of identical sharks, fish,
*  or empty cells.  TypeAndSizes are your way of telling the test program
*  what runs appear in your run-length encoding.  TypeAndSizes exist solely
*  so that your program can return two integers at once:  one representing
*  the type (species) of a run, and the other representing the size of a run.
*
*  TypeAndSize objects are not appropriate for representing your run-length
*  encoding, because they do not represent the degree of hunger of a run of
*  sharks.
*
*  @author Jonathan Shewchuk
*/

class TypeAndSize {

Species type;               // runType EMPTY, SHARK, or FISH
int runLength;                   // Number of cells in the run for that runType.

enum Species{EMPTY,SHARK,FISH}

/**
*  Constructor for a TypeAndSize of specified species and run length.
*  @param species is Ocean.EMPTY, Ocean.SHARK, or Ocean.FISH.
*  @param runLength is the number of identical cells in this run.
*  @return the newly constructed Critter.
*/

TypeAndSize(Species species, int runLength) {
if (species == null)    {
System.out.println("TypeAndSize Error:  Illegal species.");
System.exit(1);
}
if (runLength < 1) {
System.out.println("TypeAndSize Error:  runLength must be at least 1.");
System.exit(1);
}
this.type = species;
this.runLength = runLength;

}
}


For the problem statement given below:

Part II: Converting a Run-Length Encoding to an Ocean

For a large ocean, an Ocean object can consume quite a bit of memory or disk space. For long-term storage, we can store an Ocean more efficiently if we represent it as a "run-length encoding." Imagine taking all the rows of cells in the ocean, and connecting them into one long strip. Think of the cells as being numbered thusly:

                   -----------------------------
|   0  |   1  |   2  |   3  |
-----------------------------
|   4  |   5  |   6  |   7  |
-----------------------------
|   8  |   9  |  10  |  11  |
-----------------------------


Typically, many regions of this strip are "runs" of many empty cells in a row, or many fish in a row, or many equally-hungry sharks in a row. Run-length encoding is a technique in which a sequence of identical consecutive cells are represented as a single record or object. For instance, the following strip of fish (F), sharks fed two timesteps ago (S2), and empty cells (.):

       ------------------------------------------------------
| F | F | F | S2 | S2 | S2 | S2 | S2 | . | . | . | . |
------------------------------------------------------


could be represented with just three records, each representing one "run":

                         ------------------
| F3 | S2,5 | .4 |
------------------


"F3" means that there are three consecutive fish, followed by "S2,5", meaning five consecutive sharks fed two timesteps ago, and then ".4": four empty cells. With this encoding, a huge ocean with just a few fish or sharks can be stored in a tiny amount of memory. (Note, however, that a shark that just ate cannot be represented together with a shark that hasn't eaten in the last timestep. For a correct encoding, you must separate sharks based on their hunger!) If you are familiar with .GIF image files (often encountered on the Web), you might be interested to know that they use run-length encoding to reduce their sizes.

Your task is to implement a RunLengthEncoding class, which represents a run-length encoding as a linked list of "run" objects. It is up to you whether to use a singly- or doubly-linked list, but a doubly-linked list may make Part IV easier.

Because this is a data structures course, please use your own list class(es) or ones you have learned in class. In future courses, it will sometimes make more sense for you to use a linked list class written by somebody else, such as java.util.LinkedList. However, in CS 61B this is forbidden, because I want you to be always aware of exactly how your data structures work. Likewise, you may not use java.util.Vector or other built-in data structures.

Part II(a): Implement two constructors for RunLengthEncodings. One constructs a run-length encoding of an empty ocean, and the other constructs a run-length encoding based on two arrays provided as parameters to the constructor. These arrays represent the runs that your run-length coding should contain, so you are simply converting arrays to a linked list. (See the prototype in RunLengthEncoding.java.)

Part II(b): Your run-length encodings will only be useful if other classes have the ability to read them after you create them. Therefore, implement the nextRun() and restartRuns() methods. These two methods work together to return all the runs in a run-length encoding to an outside application, one by one. Each time nextRun() is invoked, it returns a different run--represented as a TypeAndSize object--until every run has been returned. The first time nextRun() is invoked, it returns the first run in the encoding, which contains cell (0, 0). After every run has been returned, nextRun() returns null, which lets the calling program know that there are no more runs in the encoding.

The restartRuns() method resets the enumeration, so that nextRun() will once again return the first run as if it were being called for the first time. Warning: the test code will not necessarily call restartRuns() before the first time nextRun() is called.

IMPORTANT NOTE on nextRun() and restartRuns(): your methods in the RunLengthEncoding class should never call these methods. The nextRun() and restartRuns() methods are provided so that other classes (specifically, the Test program that autogrades your project) can read the contents of a run-length encoding. If your RunLengthEncoding methods call them, they will mess up the position of the internal pointer for the other classes.

IMPORTANT NOTE on TypeAndSize: The Java "return" keyword only allows you to return one value from a method call. But the nextRun() method needs to return two values--the length of a run, and the type of object it contains. How can it do this? Answer: by returning a "TypeAndSize" object. A TypeAndSize object is nothing more than a way to return two integers at once. That's it. Each time nextRun() is called, it creates a TypeAndSize object (or it will once you've coded it to do so), fills in the values, and returns it to the calling routine, which then throws it away. The TypeAndSize object is part of the predefined interface of your RunLengthEncoding class, so you CANNOT change it, because the calling programs (including the autograder) are relying on you to return TypeAndSize objects according to spec. TypeAndSize objects are NOT suitable as a way to represent a run in your run-length encoding, because they do not encode a shark's hunger.

Part II(c): Implement a toOcean() method in the RunLengthEncoding class, which converts a run-length encoding to an Ocean object. To accomplish this, you will need to implement a new addShark() method in the Ocean class, so that you can specify the hunger of each shark you add to the ocean. This way, you can convert an Ocean to a run-length encoding and back again without forgetting how hungry each shark was.

Read RunLengthEncoding.java carefully for an explanation of what methods you must write. The fields of the Ocean class MUST be private, and the RunLengthEncoding class cannot manipulate these fields directly. Hence, the toOcean() method will rely upon the Ocean constructor and the addFish() and addShark() methods.

You cannot change any of the prototypes in RunLengthEncoding.java, and you cannot change the file TypeAndSize.java. Again, we will test your code by calling your methods directly.

I realise that usage of such hard code statements if(singleArray[index].type == TypeAndSize.Species.EMPTY) for instance. will create lot of maintenance issues when you add a new creature in future. But i would like to complete this assignment with given skeleton in the link.

Required method of Ocean class is shown here as previous query has rest of the methods.

Please provide the comments on the solution provided for Part II of this assignment.

Note:For the current design, It would be more helpful to me by knowing the loopholes of this current design wrt abstraction & encapsulation instead of suggesting from-scratch new design.

• @Pimgd As you reviewed Part I, Does it make sense for you to review Part II here? – overexchange Nov 5 '14 at 4:45
• @toto2 Does it make sense to say that, it would be more effective to review this code by you as you already reviewed Part I. – overexchange Nov 5 '14 at 4:47
• Keep in mind that it's not possible to ping people by posting comments on an unrelated post. The people have to be involved with the post via either editing, commenting or answering for you to ping them with a @notification. – Pimgd Nov 5 '14 at 8:48

You broke the rules!

You cannot change any of the prototypes in RunLengthEncoding.java, and you cannot change the file TypeAndSize.java.

http://www.cs.berkeley.edu/~jrs/61bf06/hw/pj1/TypeAndSize.java

/* TypeAndSize.java */

/* DO NOT CHANGE THIS FILE. */
/* YOUR SUBMISSION MUST WORK CORRECTLY WITH _OUR_ COPY OF THIS FILE. */

import java.io.*;

/**
*  Each TypeAndSize object represents a sequence of identical sharks, fish,
*  or empty cells.  TypeAndSizes are your way of telling the test program
*  what runs appear in your run-length encoding.  TypeAndSizes exist solely
*  so that your program can return two integers at once:  one representing
*  the type (species) of a run, and the other representing the size of a run.
*
*  TypeAndSize objects are not appropriate for representing your run-length
*  encoding, because they do not represent the degree of hunger of a run of
*  sharks.
*
*  @author Jonathan Shewchuk
*/

public class TypeAndSize {

public int type;                   // Ocean.EMPTY, Ocean.SHARK, or Ocean.FISH
public int size;                                // Number of cells in the run

/**
*  Constructor for a TypeAndSize of specified species and run length.
*  @param species is Ocean.EMPTY, Ocean.SHARK, or Ocean.FISH.
*  @param runLength is the number of identical cells in this run.
*  @return the newly constructed Critter.
*/

public TypeAndSize(int species, int runLength) {
if ((species != Ocean.EMPTY) && (species != Ocean.SHARK) &&
(species != Ocean.FISH)) {
System.out.println("TypeAndSize Error:  Illegal species.");
System.exit(1);
}
if (runLength < 1) {
System.out.println("TypeAndSize Error:  runLength must be at least 1.");
System.exit(1);
}
this.type = species;
this.size = runLength;
}

}


You defined enum Species{EMPTY,SHARK,FISH} and changed public int type to Species type.

This is not allowed!

(But I would have done it too - at least change public int type to public Species type. Then probably define Species in Critter.)

• I did this to just simplify comparisons in the TypeAndSize() constructor. – overexchange Nov 5 '14 at 8:59
• @overexchange Yes, but when running the code, TypeAndSize.Species will be undefined (Because they use their version) and then your code will fail to compile. – Pimgd Nov 5 '14 at 8:59
• i will make it to Ocean.Species type;. – overexchange Nov 5 '14 at 9:03
• You may not alter TypeAndSize! Those are the restrictions of the assignment. – Pimgd Nov 5 '14 at 9:04
• Yes, Sure the testcase code will fail – overexchange Nov 5 '14 at 9:06