In this programming assignment, you will be implementing basic functionalities of an image editor program.
1.You will first implement a Stack data structure with methods outlined in the table in Part-1.
2.Using your Stack implementation, you will design and implement the image editor functionalities outlined in the table in Part-2.
3.Two major components: Stack.java and ImageEditor.java, you only need to edit these two java files.
4.Don't forget to edit the README.md and follow the coding style like in previous assignments.
5.You will be also provided with some samples test cases in TestMyBasic.java, TestMyResizable.java, TestImageEditor.java. Feel free to add more test cases to test your methods. Since, you will not be graded on these files, so you don't have to submit them.
Note: Read the writeup completely before getting started.
A stack is a linear data structure, which follows a LIFO (Last in First Out) or FILO (First In Last Out) strategy to perform the operations. A real-life example of a stack would be dinner plates stacked over one another in a restaurant. The basic operations in a stack are the following: push, pop, and isEmpty. You will be implementing a stack that supports more operations than these three. see image.
The two most common ways to implement a stack are using either an array or a linked list. In this assignment, you will be using primitive array in Java to implement stack.
1.1 Growable and Shrinkable Stack:
A Stack, in general, has a fixed capacity, i.e. the number of elements that it can hold, but in this assignment, you will be implementing a stack that can have:
1.fixed capacity: a push operation will throw a StackOverflowError if the stack is full. see image.
2.growable capacity: if the stack is x% full, a push operation will first double the capacity of the stack and then add the element. This is decided by load_factor, for example, let's say load_factor=0.5, it means when your stack is 50% filled then, double the stack capacity and add the element to the top. ;(0.5 <= load_factor <= 1.0) see image.
3.growable as well as shrinkable capacity: The stack expands and shrinks according to the load_factor and the shrink_factor. As described before in #2, the stack grows in capacity during push operation based on load_factor. When the stack is y% full, a pop operation will first halve the capacity of the stack and then return the top element in the stack. This is decided by shrink_factor, for example, let's say shrink_factor=0.4, it means when your stack is 40% filled then, halve the stack capacity and add return element at the top. (0 < shrink_factor <= 0.5) see image.
1.2 Constructors:
The following are the constructors for Stack class in file Stack.java that you have to implement.
| Constructor | Description |
| Stack (int capacity) | Initializes a stack with fixed capacity, it doesnt grow or shrink. |
| Stack (int capacity, float load_factor) | Initializes the stack with some initial capacity, but it can grow in size, load_factor decides when to grow. |
| Stack (int capacity, float load_factor, float shrink_factor) | Initializes the stack with some initial capacity. It can grow in size, load_factor decides when to grow. It can also shrink in size, shrink_factor decides when to shrink. |
1.3 Public Methods:
The following are the methods of the Stack class in file Stack.java that you have to implement.
| Method Name | Method Description | Exceptions to throw |
| boolean isEmpty() | Check if Stack is empty, when there are no elements in the stack | None |
| void clear() | Remove all elements from Stack. It doesn't change the capacity of the stack. | None |
| E pop() | Removes the object at the top of the stack and returns it. It also shrinks the size of the stack as described in Section 1.1, if the stack was initialized with constructor: Stack (int capacity, float load_factor, float shrink_factor) | Throw EmptyStackException if the stack is empty. |
| void push(E element) | Adds an element at the top of the stack. It also grows the size of the stack as described in Section 1.1, if the stack was initialized with constructor Stack (int capacity, float load_factor) (Please note: depending on the version of startercode you downloaded, the header might say this should return a boolean, please download the starter code again, or change the header to void) | 1. Throw StackOverflowError if the stack is full(which will happen when stack cant grow.) 2. Throws NullPointerException if the user tries to push null. |
| boolean isFull() | Check if Stack is full. Returns true if stack is full, false otherwise. | None |
| E peek() | Returns the element at the top of the stack without removing it from the stack. | Throw EmptyStackException if the stack is empty. |
| int currentSize() | Returns the total number of current elements in the stack not the capacity of stack. | None |
| E[] multiPop(int k) | Pop k elements from the stack and returns them as an array. If the k > currentSize(), then returns all the elements as array. | Throw EmptyStackException if the stack is empty. |
| void multiPush(E[] array) | Adds all the element from the array at the top of the stack one by one. | 1. Throw StackOverflowError if the stack is full(which will happen when stack cant grow.) 2. Throws NullPointerException if any element in the input array is null. |
| void reverse() | Reverse the elements in the stack. Ex: a < -> b < -> c (c is the top element) stack.peek() => c stack.reverse() c < -> b < -> a (a is at the top now) stack.peek() => a | Throw EmptyStackException if the stack is empty. |
| boolean pushUnique(E element) | Adds an element at the top of the stack, only if the current top element of the stack is not the same as the element that we want to push. Return True, if it was a success or else False. | 1. Throw StackOverflowError if the stack is full(which will happen when stack cant grow.) 2. Throws NullPointerException if the user tries to push null. |
| int search(E e) | Returns the distance of the element from the top of the stack. It returns 1-based position if the element is found else return -1. Ex: a < -> b < -> c (c is the top of stack) search(c) => 1, (index of c which is top of stack) search(a) => 3, (index of a from top of stack) | Throw EmptyStackException if stack is empty. |
| int getCapacity() | Returns the total capacity of stack, the maximum number of elements it can store currently. Ex: a < -> b < -> c < -> < -> < -> getCapacity() => 5, (c is top element and stack can still accommodate 2 more elements) | None |
2.1 Grayscale image
Now using this stack, you will implement basic functionalities of an image editor for a gray-scale image. A gray-scale image is represented by a 2D array of integers where each pixel is presented by the value at i, j th index. The value of each pixel is an integer in the range 0 to 255, inclusive. The value 0 means dark pixel and 255 means a white pixel. Example of a random grayscale image that we see: see image.
Example of a 5x5 pixel gray-scale image that a computer sees:
(You can say this grayscale image has 5 rows and 5 columns)
0 11 123 0 111
10 12 45 8 25
19 10 50 0 255
44 21 60 7 44
22 244 70 1 22
Real life image editor programs can edit a group of pixels in one go, but in order to keep the implementation of our image editor simple, you will be editing only one pixel at a time using the edit functions: "delete", blur and sharpen. You will also implement undo and redo functions, which changes the history of edit commands
When the "undo" function is called, it reverses the effect of the most recent called edit function. The behavior of the redo function is slightly different from undo. When the redo function is called, it executes the most recent edit function undone by the undo command. Therefore, in order to achieve such functionality, you will have to maintain the history of commands that have been undone by the undo command. Also, the redo history is cleared when a new edit function(delete or blur or sharpen) is called/executed.
Example of sequence of function Calls:
>> delete
>> blur
>> undo
>> undone the blur
>> sharpen
>> delete
>> undo
>> undone the delete
>> redo
>> redo the delete
2.3 Constructors:
The following are the constructors for ImageEditor class in file ImageEditor.java that you have to implement.
| Constructor | Description |
| ImageEditor (int[][] image) | Initializes an ImageEditor with image data |
2.4 Public Methods:
The following are the methods of the ImageEditor class in file ImageEditor.java that you have to implement, command/function is used interchangeably and they mean the same, pixel/value is used interchangeably and they mean the same.
| Method Name | Method Description | Exceptions to throw |
| void delete(int i, int j ) (removing some content of the image) | Set the value of at location i,j to 0. | Throw IndexOutOfBoundsException if the given location (i,j) does not exist. |
| boolean undo( ) | Reverse the effect of last executed edit function(which can be any of "delete", "blur", "sharpen"). Returns False if there is no edit function to be undone else True. | None |
| boolean redo( ) | Execute the most recent function undone by undo command. Returns False, if there was no such command to execute else True. | None |
| int [][] getImage( ) | Returns the current 2D image. | None |
|
(decreasing brightness of the image) | Blurs the pixel/value at location i, j. It basically decreases the sharpness of a pixel by multiplying the current pixel value with blur_factor. Eg. blur(i, j, 0.2) Because our 2D image has only integer values. Always round the new value to the nearest integer, before putting it back in image(i, j). | 1. Throw IndexOutOfBoundsException if the given cell does not exist. 2. Throw IllegalArgumentException if blur_factor is not in range: 0 |
| void sharpen(int i, int j, float sharpen_factor) (increasing brightness of image) | Sharpen the pixel/value at location i, j. It basically changes the intensity of pixel by multiplying the current pixel value with sharpen_factor. Also, always sharpen_factor =1 Eg. sharpen(i, j, 1.5) Just like in "blur", round the new value to the nearest integer, before putting it back in image(i, j). Since our image is grayscale, each pixel can only have a value ranging from 0 to 255, so if new_value(i,j) 255, set it to 255. | 1. Throw IndexOutOfBoundsException if the given cell does not exist. 2. Throw IllegalArgumentException if sharpen_factor is < 1. |