Instructions
Requirements and Specifications
Source Code
package tests;
public class ListUtilities {
public Node<String> getAllPrefixes(Node<Integer> node, int minLength, int maxLength) {
// result list head and cursor nodes
Node<String> result = null;
Node<String> resultCurrNode = null;
// string for building prefixes
String current = "[";
// source list cursor node
Node<Integer> currNode = node;
// processed nodes counter
int count = 0;
// processing all nodes in the list
while(currNode != null) {
if (current.length() == 1) {
// if current string is empty, adding only int
current += currNode.getElement().toString();
}
else {
// otherwise adding comma and int
current += ", " + currNode.getElement().toString();
}
// increasing counter
count++;
// if counter is between bounds, adding it to result list
if (count >= minLength && count <= maxLength) {
if (result == null) {
// result list is empty now, we have to intitialize head node and cursor
result = new Node<>(current + "]", null);
resultCurrNode = result;
}
else {
// adding new node to the end and moving cursor forward
resultCurrNode.setNext(new Node<>(current + "]", null));
resultCurrNode = resultCurrNode.getNext();
}
}
// moving forward through source list
currNode = currNode.getNext();
}
// returning result list
return result;
}
public Node<Integer> getMergedChain(Node<Integer> nodeA, Node<Integer> nodeB) {
// result list head and cursor nodes
Node<Integer> result = null;
Node<Integer> resultCurrNode = null;
// cursor node for list A
Node<Integer> currNodeA = nodeA;
// cursor node for list B
Node<Integer> currNodeB = nodeB;
// keep iterating until all nodes from both strings are processed
while (currNodeA != null || currNodeB != null) {
// this variable will store element which needed to be added to the result list on current step
int toAdd;
if (currNodeA != null && currNodeB != null) {
// if list A and list B both not processed yet,
// we must choose the least element among two cursor elements
int valA = currNodeA.getElement();
int valB = currNodeB.getElement();
// selecting min element
if (valA < valB) {
toAdd = valA;
// value from A will be added to the result, shifting A cursor
currNodeA = currNodeA.getNext();
}
else {
toAdd = valB;
// value from B will be added to the result, shifting A cursor
currNodeB = currNodeB.getNext();
}
}
else if (currNodeB == null) {
// only A list is not processed
toAdd = currNodeA.getElement();
// value from A will be added to the result, shifting A cursor
currNodeA = currNodeA.getNext();
}
else {
// only B list is not processed
toAdd = currNodeB.getElement();
// value from B will be added to the result, shifting B cursor
currNodeB = currNodeB.getNext();
}
if (result == null) {
// result list is empty now, we have to intitialize head node and cursor
result = new Node<>(toAdd, null);
resultCurrNode = result;
}
else {
// adding new node to the end and moving cursor forward
resultCurrNode.setNext(new Node<>(toAdd, null));
resultCurrNode = resultCurrNode.getNext();
}
}
// returning result list
return result;
}
public Node<Integer> getInterleavedArithmeticFibonacciSequences(int arithStart, int arithDif, int arithSize, int fibSize) {
// arithmetic list head and cursor nodes
Node<Integer> arithmetic = null;
Node<Integer> arithmeticCurrNode = null;
for (int i = 0; i<arithSize; i++) {
if (arithmetic == null) {
// if arithmetic list is empty, only intializing nodes and inserting start value
arithmetic = new Node<>(arithStart, null);
arithmeticCurrNode = arithmetic;
}
else {
// inserting appropriate value to the end of the list
arithmeticCurrNode.setNext(new Node<>(arithStart + i * arithDif, null));
arithmeticCurrNode = arithmeticCurrNode.getNext();
}
}
// fibbonacci list head and cursor nodes
Node<Integer> fib = null;
Node<Integer> fibCurrNode = null;
// fib_0
int prevPrev = 1;
// fib_!
int prev = 1;
// inserting required number of fibbonacci sequence
for (int i = 0; i<fibSize; i++) {
if (i == 0) {
// inserting fib_0 into fib list
fib = new Node<>(prevPrev, null);
fibCurrNode = fib;
}
else if (i == 1) {
// inserting fib_1 into fib list
fibCurrNode.setNext(new Node<>(prev, null));
fibCurrNode = fibCurrNode.getNext();
}
else {
// calculating current fib value
int curr = prevPrev + prev;
// inserting it to the list
fibCurrNode.setNext(new Node<>(curr, null));
fibCurrNode = fibCurrNode.getNext();
// reassigning previous fib values
prevPrev = prev;
prev = curr;
}
}
// now we will merge obtained two lists into the result list, by interleaving
arithmeticCurrNode = arithmetic;
fibCurrNode = fib;
// result list head and cursor nodes
Node<Integer> result = null;
Node<Integer> resultCurrNode = null;
// for interleaving, we need a flag, which shows, from which list was previous entry
boolean prevFib = true;
while(arithmeticCurrNode != null || fibCurrNode != null) {
// variable for value to add
int toAdd;
if (arithmeticCurrNode != null && fibCurrNode != null) {
// both lists are not processed yet
if (prevFib) {
// previous node was from fib list
// inserting value from arithmetic list
toAdd = arithmeticCurrNode.getElement();
arithmeticCurrNode = arithmeticCurrNode.getNext();
prevFib = false;
}
else {
// previous node was from arithmetic list
// inserting value from fib list
toAdd = fibCurrNode.getElement();
fibCurrNode = fibCurrNode.getNext();
prevFib = true;
}
}
else if (fibCurrNode == null) {
// fib list is processed
// inserting value from arithmetic list
toAdd = arithmeticCurrNode.getElement();
arithmeticCurrNode = arithmeticCurrNode.getNext();
}
else {
// arithmetic list is processed
// inserting value from fib list
toAdd = fibCurrNode.getElement();
fibCurrNode = fibCurrNode.getNext();
}
if (result == null) {
// if arithmetic list is empty, only intializing nodes and inserting start value
result = new Node<>(toAdd, null);
resultCurrNode = result;
}
else {
// adding new node to the end and moving cursor forward
resultCurrNode.setNext(new Node<>(toAdd, null));
resultCurrNode = resultCurrNode.getNext();
}
}
// returning result list
return result;
}
public Node<String> getGroupedStrings(Node<String> node, int m, int n) {
// group 1 list head and cursor nodes
Node<String> group1 = null;
Node<String> group1CurrNode = null;
// group 2 list head and cursor nodes
Node<String> group2 = null;
Node<String> group2CurrNode = null;
// group 3 list head and cursor nodes
Node<String> group3 = null;
Node<String> group3CurrNode = null;
// iterating through source list and inserting each value to one of three lists
// value order inside group will be preserved
Node<String> currNode = node;
while(currNode != null) {
String val = currNode.getElement();
if (val.length() < m) {
if (group1 == null) {
group1 = new Node<>(val, null);
group1CurrNode = group1;
}
else {
group1CurrNode.setNext(new Node<>(val, null));
group1CurrNode = group1CurrNode.getNext();
}
}
else if (val.length() < n) {
if (group2 == null) {
group2 = new Node<>(val, null);
group2CurrNode = group2;
}
else {
group2CurrNode.setNext(new Node<>(val, null));
group2CurrNode = group2CurrNode.getNext();
}
}
else {
if (group3 == null) {
group3 = new Node<>(val, null);
group3CurrNode = group3;
}
else {
group3CurrNode.setNext(new Node<>(val, null));
group3CurrNode = group3CurrNode.getNext();
}
}
currNode = currNode.getNext();
}
// now we just need to concatenate 3 obtained list
// doing it by correctly checking nulls
Node<String> result = group1;
Node<String> last = group1CurrNode;
if (last == null) {
result = group2;
}
else {
last.setNext(group2);
}
if (group2 != null) {
last = group2CurrNode;
}
if (last == null) {
result = group3;
}
else {
last.setNext(group3);
}
return result;
}
}
NODE
package tests;
/*
* This Node class is provided to you,
* and you must use it to implement the required class(es) and method(s) in the model package.
* The StarterTests class in the `tests` package suggests what you need to create in the `model` package.
* Where the Node class is needed, you must:
* + Only use the public methods given here.
* + Not add any additional attributes or methods in this Node class.
*/
public class Node<E> {
/*
* Do not modify this class.
* When your submission is graded, the same starter version of the Node class will be used,
* meaning that if you made any changes to this class, they would be wiped out
* and your submitted classes may just stop compiling.
*/
private E element;
private Node<E> next;
/*
* Constructor
*/
public Node(E e, Node<E> n) {
element = e;
next = n;
}
/*
* Accessors
*/
public E getElement() {
return element;
}
public Node<E> getNext() {
return next;
}
/*
* Mutators
*/
public void setElement(E e) {
element = e;
}
public void setNext(Node<E> n) {
next = n;
}
}