Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
LinkedList utils - singly and doubly linked
Placeholder for naming
package com.blogspot.groglogs.structures;
public class BuySellEntry {
public long buy_date, sell_date;
public double buy_price, sell_price;
public BuySellEntry(long buy_date, double buy_price){
this.buy_date = buy_date;
this.buy_price = buy_price;
this.sell_date = -1;
this.sell_price = -1;
}
public BuySellEntry(long buy_date, double buy_price, long sell_date, double sell_price){
this.buy_date = buy_date;
this.buy_price = buy_price;
this.sell_date = sell_date;
this.sell_price = sell_price;
}
@Override
public boolean equals(Object other){
if(other == null || other.getClass() != this.getClass()) return false;
BuySellEntry bse = (BuySellEntry) other;
return this.buy_date == bse.buy_date
&& this.buy_price == bse.buy_price
&& this.sell_date == bse.sell_date
&& this.sell_price == bse.sell_price
;
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Assert;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import java.util.List;
import java.util.LinkedList;
import static org.junit.Assert.assertEquals;
public class DateListsJTests {
List<DateNode> in;
DateNode out, tmp, res;
@Test
//null or empty lists
public void nullEmpty() {
//null
out = LinkedListUtils.mergeDateLists(in);
assertEquals("null list expected null", null, out);
//empty container
in = new LinkedList<>();
out = LinkedListUtils.mergeDateLists(in);
assertEquals("empty container list expected null", null, out);
//empty contained
tmp = new DateNode();
in = new LinkedList<>();
in.add(tmp);
out = LinkedListUtils.mergeDateLists(in);
assertEquals("empty contained list expected null", null, out);
}
@Test
//only one list, expected same as result
public void onlyOne() {
tmp = new DateNode(1, 10);
tmp.next = new DateNode(11, 20);
in = new LinkedList<>();
in.add(tmp);
out = LinkedListUtils.mergeDateLists(in);
assertEquals("only one input list expected same list", true, out.isEqualList(tmp));
//multiple lists, but only one with values
tmp = new DateNode(1, 10);
tmp.next = new DateNode(11, 20);
in = new LinkedList<>();
in.add(tmp);
in.add(new DateNode());
out = LinkedListUtils.mergeDateLists(in);
assertEquals("only one input list with values expected same list", true, out.isEqualList(tmp));
//multiple lists, but only one with values
tmp = new DateNode(1, 10);
tmp.next = new DateNode(11, 20);
in = new LinkedList<>();
in.add(new DateNode());
in.add(tmp);
in.add(new DateNode());
out = LinkedListUtils.mergeDateLists(in);
assertEquals("only one input list with values expected same list", true, out.isEqualList(tmp));
}
@Test
//more lists, expected output is merge of all
public void moreLists() {
//head missing in list 3 and tail missing in list 1, middle hole in all lists
in = new LinkedList<>();
tmp = new DateNode(5, 10);
tmp.next = new DateNode(11, 20);
in.add(tmp);
tmp = new DateNode(5, 20);
tmp.next = new DateNode(6, 10);
tmp.next.next = new DateNode(12, 20);
in.add(tmp);
tmp = new DateNode(6, 10);
tmp.next = new DateNode(12, 20);
in.add(tmp);
out = LinkedListUtils.mergeDateLists(in);
res = new DateNode(5, 30);
res.next = new DateNode(6, 30);
res.next.next = new DateNode(11, 40);
res.next.next.next = new DateNode(12, 60);
assertEquals("only one input list expected same list", true, out.isEqualList(res));
}
}
package com.blogspot.groglogs.structures;
public class DateNode {
public long date;
public int val;
public DateNode next;
public DateNode(){
this.date = -1;
}
public DateNode(long date, int val){
this.date = date;
this.val = val;
this.next = null;
}
//this node is equal to another if both have same date and val. null nodes can't be compared with this non static method
public boolean isEqual(DateNode node){
if(node == null) return false;
return this.date == node.date && this.val == node.val;
}
//two DateNode lists are same if all elements are same
public boolean isEqualList(DateNode head){
DateNode curr = this, other = head;
while(curr != null){
//at the first difference, return false
if(!curr.isEqual(other)) return false;
curr = curr.next;
other = other.next;
}
//if we reached our end, we just need to make sure the other list has no more elements as well!
return other == null;
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class DoubleLinkedListJTests {
DoubleLinkedListNode input, output;
boolean isEqual = false;
@Test
public void nullEmpty() {
input = null;
output = null;
input = LinkedListUtils.reverseList(input);
assertEquals("reverse null expected null", output, input);
input = new DoubleLinkedListNode();
output = new DoubleLinkedListNode();
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsDataList(output);
assertEquals("reverse empty expected empty", true, isEqual);
}
@Test
public void reverseList() {
//single node
input = new DoubleLinkedListNode(1, "A");
output = new DoubleLinkedListNode(1, "A");
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsDataList(output);
assertEquals("reverse A expected A", true, isEqual);
//multiple nodes
input = new DoubleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
output = new DoubleLinkedListNode(3, "C");
output.addLast(2, "B");
output.addLast(1, "A");
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsDataList(output);
assertEquals("reverse A,B,C expected C,B,A", true, isEqual);
}
}
package com.blogspot.groglogs.structures;
public class DoubleLinkedListNode {
public Integer id;
public String data;
public DoubleLinkedListNode next, prev;
public DoubleLinkedListNode(){
this.id = null;
this.data = null;
this.next = null;
this.prev = null;
}
public DoubleLinkedListNode(Integer id){
this.id = id;
this.data = null;
this.next = null;
this.prev = null;
}
public DoubleLinkedListNode(Integer id, DoubleLinkedListNode prev){
this.id = id;
this.data = null;
this.next = null;
this.prev = prev;
}
public DoubleLinkedListNode(Integer id, String data){
this.id = id;
this.data = data;
this.next = null;
this.prev = null;
}
public DoubleLinkedListNode(Integer id, String data, DoubleLinkedListNode prev){
this.id = id;
this.data = data;
this.next = null;
this.prev = prev;
}
public int length(){
if(this.id == null || this.data == null) return 0;
int count = 0;
DoubleLinkedListNode next = this;
while(next != null){
count++;
next = next.next;
}
return count;
}
public void addLast(Integer id, String data){
DoubleLinkedListNode next = this;
while(next.next != null) next = next.next;
next.next = new DoubleLinkedListNode(id, data, next);
}
public void addLast(Integer id){
DoubleLinkedListNode next = this;
while(next.next != null) next = next.next;
next.next = new DoubleLinkedListNode(id, next);
}
@Override
public boolean equals(Object obj) {
if(obj == null) return false;
if(obj.getClass() != this.getClass()) return false;
DoubleLinkedListNode other = (DoubleLinkedListNode) obj;
return this.id == other.id && this.data == other.data;
}
public boolean equalsData(DoubleLinkedListNode other) {
if(other == null) return false;
return this.data == other.data;
}
public boolean equalsId(DoubleLinkedListNode other) {
if(other == null) return false;
return this.id == other.id;
}
public boolean equalsList(DoubleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
DoubleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equals(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public boolean equalsDataList(DoubleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
DoubleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equalsData(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public boolean equalsIdList(DoubleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
DoubleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equalsId(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public void printList(){
DoubleLinkedListNode next = this;
while(next != null){
System.out.println("id: " + next.id + " - data: " + next.data);
next = next.next;
}
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class LinkedListSumJTests {
SingleLinkedListNode x, y, output, result;
boolean isEqual;
@Test
//null or empty lists
public void nullEmpty() {
x = null;
y = null;
output = LinkedListUtils.sumListsFromLSD(x, y);
assertEquals("null list expected null", null, output);
x = new SingleLinkedListNode();
y = new SingleLinkedListNode();
output = new SingleLinkedListNode(0);
result = LinkedListUtils.sumListsFromLSD(x, y);
assertEquals("empty list expected 0", output.id, result.id);
}
@Test
public void oneEmpty() {
//null + 125 = 125
x = null;
y = new SingleLinkedListNode(5);
y.addLast(2);
y.addLast(1);
result = LinkedListUtils.sumListsFromLSD(x, y);
output = y;
isEqual = output.equalsIdList(result);
assertEquals("null + 125 = 125 expected 5,2,1", true, isEqual);
}
@Test
public void differentLength() {
//4037 + 125 = 4162
x = new SingleLinkedListNode(7);
x.addLast(3);
x.addLast(0);
x.addLast(4);
y = new SingleLinkedListNode(5);
y.addLast(2);
y.addLast(1);
result = LinkedListUtils.sumListsFromLSD(x, y);
output = new SingleLinkedListNode(2);
output.addLast(6);
output.addLast(1);
output.addLast(4);
isEqual = output.equalsIdList(result);
assertEquals("4037 + 125 = 4162 expected 2,6,1,4", true, isEqual);
}
@Test
//have a carry at the last operation
public void carryLast() {
//90 + 10 = 100
x = new SingleLinkedListNode(0);
x.addLast(9);
y = new SingleLinkedListNode(0);
y.addLast(1);
result = LinkedListUtils.sumListsFromLSD(x, y);
output = new SingleLinkedListNode(0);
output.addLast(0);
output.addLast(1);
isEqual = output.equalsIdList(result);
assertEquals("90 + 10 = 100 expected 0,0,1", true, isEqual);
}
@Test
//have multiple carry
public void multipleCarry() {
//999 + 999 = 1998
x = new SingleLinkedListNode(9);
x.addLast(9);
x.addLast(9);
y = x;
result = LinkedListUtils.sumListsFromLSD(x, y);
output = new SingleLinkedListNode(8);
output.addLast(9);
output.addLast(9);
output.addLast(1);
isEqual = output.equalsIdList(result);
assertEquals("999 + 999 = 1998 expected 8,9,9,1", true, isEqual);
}
}
package com.blogspot.groglogs.linkedlistutils;
import com.blogspot.groglogs.structures.*;
import java.util.List;
public class LinkedListUtils {
public static void removeDuplicates(SingleLinkedListNode head){
SingleLinkedListNode curr, prev, next;
curr = head;
//for each single node
while(curr != null){
//track 2 nodes at the same time
prev = curr;
next = prev.next;
//walk the whole list
while(next != null){
/*
if the next node is a duplicate, delete it by linking the previous to the next.next
CAUTION: do NOT move the previous node because we could lose a value
*/
if(next.data == curr.data) prev.next = next.next;
//only move previous if the next one was unique
else prev = prev.next;
//move next to the new next element
if(prev != null) next = prev.next;
}
curr = curr.next;
}
}
//CAUTION: must return a value because otherwise we would not be able to remove the head element
public static SingleLinkedListNode removeKtoLastNode(SingleLinkedListNode head, int k){
if(head == null) return head;
int length = head.length();
/*
list is 1 to length, so check k is in that range
CAUTION: we are removing kth to last so k = 0 means remove last
k = length -1 means remove first
*/
if(k < 0 || k > length - 1) return head;
int n, count = 1;
SingleLinkedListNode prev = head, next;
//find out which element we want to remove
n = length - k;
//if it's the head, just return next
if(n == 1){
return prev.next;
}
//otherwise walk through the list and delete the desired element
while(prev != null){
next = prev.next;
//CAUTION: check with count + 1 so we do not skip the element we want to delete. next will be it!
if(n == count + 1){
if(next != null) prev.next = next.next;
//CAUTION: avoid NullPointerException when we are deleting tail
else prev.next = null;
return head;
}
prev = prev.next;
count++;
}
return head;
}
//CAUTION: must return a value because otherwise we would not be able to remove the head element
public static SingleLinkedListNode removeKtoLastNodePointers(SingleLinkedListNode head, int k){
if(head == null || k < 0) return head;
int fast_idx = 0;
SingleLinkedListNode fast = head, slow = null;
/*
keep two pointers running after each other
the slow one starts k+1 steps after the fast one
when the fast one reaches the end of the list, the slow one should be exactly before the element to remove
*/
while(fast.next != null){
if(slow != null) slow = slow.next;
fast = fast.next;
fast_idx++;
if(fast_idx == k + 1) slow = head;
}
//if the slow one is actually pointing somewhere, remove the following node
if(slow != null) slow.next = slow.next.next;
//otherwise if we want to remove the head (k = list length), just return the next from head
if(fast_idx == k) return head.next;
return head;
}
/*
Given two lists representing integer numbers
with the least significant digit in the head position
return a new list containing the sum
*/
public static SingleLinkedListNode sumListsFromLSD(SingleLinkedListNode x, SingleLinkedListNode y){
if(x == null && y == null) return null;
int carry = 0, curr = 0, val = 0;
SingleLinkedListNode result = null, n = null;
//keep going until we have data in either list and do not forget the last carry!
while(x != null || y != null || carry != 0){
curr = ((x == null || x.id == null) ? 0 : x.id) + ((y == null || y.id == null) ? 0 : y.id) + carry; //x + y + carry
val = curr % 10; //take only LSD
//track if we have a carry
carry = (curr >= 10) ? 1 : 0;
if(n == null){
n = new SingleLinkedListNode(val);
result = n;
}
else{
n.next = new SingleLinkedListNode(val);
n = n.next;
}
//move to next digit
if(x != null) x = x.next;
if(y != null) y = y.next;
}
return result;
}
//reverse doubly linked list
public static DoubleLinkedListNode reverseList(DoubleLinkedListNode head){
if(head == null) return head;
DoubleLinkedListNode prev = null;
while(head != null){
DoubleLinkedListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
//reverse singly linked list
public static SingleLinkedListNode reverseList(SingleLinkedListNode head){
if(head == null) return head;
SingleLinkedListNode prev = null, next, curr = head;
/*
1) track next element
2) reverse current element pointer
3) track current element as previous for next iteration
4) move current element to the next one to handle
*/
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
//at this time this will point to the beginning of the reversed list!
return prev;
}
/*
Given a list of ordered lists as input, where the content is (Date, value), generate as output a list ordered by date
where for each date the value is the total sum of the values for that date in each list. If a list misses that date, use
the previous one, if any. Date is represented as a long.
Eg:
5/5 5/6 6/11 6/12
A 10 20
B 20 10 20
C 10 20
The result has to be:
5/5 5/6 6/11 6/12
O 30 30 40 60
Because we track the following phantom values
5/5 5/6 6/11 6/12
A 10 [10] 20 [20]
B 20 10 [10] 20
C [0] 10 [10] 20
The idea is to collect first all the unique ordered dates from all the lists
Then for each date, selectively move along the lists and either the current value if the dates match
or the previous value if we have a hole
*/
public static DateNode mergeDateLists(List<DateNode> in){
if(in == null || in.isEmpty() || in.size() == 0) return null;
//foreach input list, track the current element. Initialize the pointers here
DateNode[] curr_list_nodes = new DateNode[in.size()];
//this will also be the real number of lists with elements, which might be less than the number of lists if one is empty for example
int idx = -1;
for(DateNode l : in){
//only track it if the list has at least one element
if(l != null && l.date != -1) curr_list_nodes[++idx] = l;
}
//if no list has elements eg they are all empty, return
if(idx == -1) return null;
//from the lists that have elements, collect all the unique dates in increasing order in the output list
boolean has_more = true;
long curr_min = Long.MAX_VALUE;
DateNode out = null, curr_out = null;
//keep going until we have finished all lists
while(has_more){
has_more = false;
//find current min date among the current pointers
for(int i = 0; i < curr_list_nodes.length; i++){
//empty lists can be skipped
if(curr_list_nodes[i] == null) continue;
//only if we found a new minimum we need to keep cycling
if(curr_list_nodes[i].date < curr_min){
has_more = true;
curr_min = curr_list_nodes[i].date;
}
}
//if we have no more elements to check, skip the next part and end the cycle
if(!has_more) break;
//otherwise add new date to the result list
if(curr_out == null) {
curr_out = new DateNode(curr_min, 0);
if(out == null) out = curr_out;
}
else {
curr_out.next = new DateNode(curr_min, 0);
curr_out = curr_out.next;
}
//move all nodes that have the same date forward, cannot do it before because we don't know yet what's the minimum
for(int i = 0; i < curr_list_nodes.length; i++){
if(curr_list_nodes[i] == null) continue;
if(curr_list_nodes[i].date == curr_min) curr_list_nodes[i] = curr_list_nodes[i].next;
}
//reset comparison for next cycle
curr_min = Long.MAX_VALUE;
}
/*
After all dates are collected, foreach date in the res list
sum values from the input lists considering potential holes
*/
DateNode res_node = out;
//reinitialize the pointer array!
idx = -1;
for(DateNode l : in){
//only track it if the list has at least one element
if(l != null && l.date != -1) curr_list_nodes[++idx] = l;
}
while(res_node != null){
//scan all lists every time
for(int i = 0; i < curr_list_nodes.length; i++){
/*
skip empty lists, no need to track if all are empty
because there is at least one node with the same date as the last in the out list
so we will break when res_node.next is null
*/
if(curr_list_nodes[i] == null) continue;
//if the date is same, update value but do not move because of potential holes afterwards
if(curr_list_nodes[i].date == res_node.date)res_node.val += curr_list_nodes[i].val;
//if list date is less than current date, we might have a hole, check if it is the case
else if(curr_list_nodes[i].date < res_node.date){
//do we still have a next node?
if(curr_list_nodes[i].next != null){
//the next date is bigger than the current one, we have the hole, update value using the current one but do not move
if(curr_list_nodes[i].next.date > res_node.date) res_node.val += curr_list_nodes[i].val;
//the next date is the same, we filled the hole, move first and then update the value
else if(curr_list_nodes[i].next.date == res_node.date){
curr_list_nodes[i] = curr_list_nodes[i].next;
res_node.val += curr_list_nodes[i].val;
}
}
//if we do not have a next node, it means we only have holes after us
else res_node.val += curr_list_nodes[i].val;
}
}
res_node = res_node.next;
}
return out;
}
/*
Find the maximum difference between two entries. Must buy first and cannot sell in the same day
Input is already sorted and price cannot be negative
Return null if input is null, empty, less than 2 entries, only decreasing (bad trade day)
*/
public static BuySellEntry getMaxProfit(List<StockEntry> trade_day){
if(trade_day == null || trade_day.isEmpty() || trade_day.size() < 2) return null;
/*
carefully track both current max profit and current result separately
otherwise we could wrongly overwrite the buy data at the end before returning
*/
double curr_max_profit = 0;
StockEntry curr_min_buy = trade_day.get(0);
BuySellEntry out = new BuySellEntry(curr_min_buy.date, curr_min_buy.price);
for(StockEntry e : trade_day){
if(e.price - curr_min_buy.price > curr_max_profit){
curr_max_profit = e.price - curr_min_buy.price;
out.buy_date = curr_min_buy.date;
out.buy_price = curr_min_buy.price;
out.sell_date = e.date;
out.sell_price = e.price;
}
if(e.price < curr_min_buy.price) curr_min_buy = e;
}
if(out.sell_date != -1) return out;
else return null;
}
/*
List zipping means interleaving the list node from the top and bottom of a given list to create a new list
Eg:
A -> B -> C -> D
Returns:
A -> D -> B -> C
*/
public static SingleLinkedListNode zipList(SingleLinkedListNode head){
if(head == null || head.next == null) return head;
/*
slow, fast used to find middle point of the list
end used to reverse second half of the list
first, last used to walk through the two halves of the list
tmp used as aux to link nodes
*/
SingleLinkedListNode slow = head, fast = head, end, first = head, last, tmp;
//find half point of this list
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//split list in two parts and reverse second part
end = slow.next; //start second half here!
slow.next = null; //break first half here!
end = reverseList(end);
last = end;
/*
As long as there are elements in the second half, keep interleaving starting from the second half!
1) track next element from the last
2) link next last element to next first
3) link next first element to last element
4) move first pointer to the next element passing through the added node!
5) move last element to the tracked one
Eg input: A -> B -> C -> D -> E
1st iteration:
F = A -> B -> C
L = E -> D
T = D
E -> B
A -> E
F = B (A, E, B)
L = T = D
A -> E -> B -> C
2nd iteration:
T = null
D -> C
B -> D
F = C (B, D, C)
L = T = null
A -> E -> B -> D -> C
*/
while(last != null){
tmp = last.next;
last.next = first.next;
first.next = last;
first = first.next.next;
last = tmp;
}
return head;
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class RemoveDuplicatesJTests {
SingleLinkedListNode input, output;
boolean isEqual;
@Test
//empty
public void empty() {
input = new SingleLinkedListNode();
output = new SingleLinkedListNode();
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsList(output);
assertEquals("new list expected true", true, isEqual);
}
@Test
public void removeDuplicates() {
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
output = input;
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C expected A,B,C", true, isEqual);
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "A");
input.addLast(3, "B");
input.addLast(4, "A");
input.addLast(5, "C");
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(3, "C");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,A,B,A,C expected A,B,C", true, isEqual);
assertEquals("A,A,B,A,C expected final length 3", 3, input.length());
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "A");
input.addLast(3, "B");
input.addLast(4, "A");
input.addLast(5, "C");
input.addLast(6, "C");
input.addLast(7, "C");
input.addLast(8, "D");
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(3, "C");
output.addLast(4, "D");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,A,B,A,C,C,C,D expected A,B,C,D", true, isEqual);
assertEquals("A,A,B,A,C,C,C,D expected final length 4", 4, input.length());
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "A");
input.addLast(3, "A");
input.addLast(4, "A");
input.addLast(5, "A");
input.addLast(6, "A");
input.addLast(7, "A");
input.addLast(8, "A");
output = new SingleLinkedListNode(1, "A");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,A,A,A,A,A,A,A expected A", true, isEqual);
assertEquals("A,A,A,A,A,A,A,A expected final length 1", 1, input.length());
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "A");
input.addLast(3, "A");
input.addLast(7, "D");
input.addLast(8, "A");
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "D");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,A,A,D,A expected A,D", true, isEqual);
assertEquals("A,A,A,D,A expected final length 2", 2, input.length());
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
input.addLast(7, "D");
input.addLast(8, "D");
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(2, "C");
output.addLast(2, "D");
LinkedListUtils.removeDuplicates(input);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C,D,D expected A,B,C,D", true, isEqual);
assertEquals("A,B,C,D,D expected final length 4", 4, input.length());
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class RemoveKtoLastNodeJTests {
SingleLinkedListNode input, output;
boolean isEqual;
int k;
@Test
//empty
public void empty() {
input = new SingleLinkedListNode();
output = new SingleLinkedListNode();
k = 0;
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsList(output);
assertEquals("new list expected true", true, isEqual);
input = new SingleLinkedListNode();
input.addLast(1, "A");
output = new SingleLinkedListNode();
output.addLast(1, "A");
k = -1;
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsList(output);
assertEquals("k < 0 expected true", true, isEqual);
input = new SingleLinkedListNode();
input.addLast(1, "A");
output = new SingleLinkedListNode();
output.addLast(1, "A");
k = 2;
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsList(output);
assertEquals("k > length expected true", true, isEqual);
}
@Test
public void removeKtoLastNode() {
//remove last node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 0;
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C k = 0 expected A,B", true, isEqual);
assertEquals("A,B,C k = 0 expected length 2", 2, input.length());
//remove middle node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 1;
output = new SingleLinkedListNode(1, "A");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C k = 1 expected A,C", true, isEqual);
assertEquals("A,B,C k = 1 expected length 2", 2, input.length());
//remove first node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 2;
output = new SingleLinkedListNode(2, "B");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C k = 2 expected B,C", true, isEqual);
assertEquals("A,B,C k = 2 expected length 2", 2, input.length());
//cannot remove node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 3;
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNode(input, k);
isEqual = input.equalsDataList(output);
assertEquals("A,B,C k = 3 expected A,B,C", true, isEqual);
assertEquals("A,B,C k = 2 expected length 3", 3, input.length());
}
@Test
//empty
public void emptyPointers() {
input = new SingleLinkedListNode();
output = new SingleLinkedListNode();
k = 0;
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
assertEquals("pointers new list expected null", null, input);
input = new SingleLinkedListNode();
input.addLast(1, "A");
output = new SingleLinkedListNode();
output.addLast(1, "A");
k = -1;
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsList(output);
assertEquals("pointers k < 0 expected true", true, isEqual);
input = new SingleLinkedListNode();
input.addLast(1, "A");
output = new SingleLinkedListNode();
output.addLast(1, "A");
k = 2;
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsList(output);
assertEquals("pointers k > length expected true", true, isEqual);
}
@Test
public void removeKtoLastNodePointer() {
//remove last node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 0;
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsDataList(output);
assertEquals("pointers A,B,C k = 0 expected A,B", true, isEqual);
assertEquals("pointers A,B,C k = 0 expected length 2", 2, input.length());
//remove middle node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 1;
output = new SingleLinkedListNode(1, "A");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsDataList(output);
assertEquals("pointers A,B,C k = 1 expected A,C", true, isEqual);
assertEquals("pointers A,B,C k = 1 expected length 2", 2, input.length());
//remove first node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 2;
output = new SingleLinkedListNode(2, "B");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsDataList(output);
assertEquals("pointers A,B,C k = 2 expected B,C", true, isEqual);
assertEquals("pointers A,B,C k = 2 expected length 2", 2, input.length());
//cannot remove node
input = new SingleLinkedListNode(1, "A");
input.addLast(2, "B");
input.addLast(3, "C");
k = 3;
output = new SingleLinkedListNode(1, "A");
output.addLast(2, "B");
output.addLast(3, "C");
input = LinkedListUtils.removeKtoLastNodePointers(input, k);
isEqual = input.equalsDataList(output);
assertEquals("pointers A,B,C k = 3 expected A,B,C", true, isEqual);
assertEquals("pointers A,B,C k = 2 expected length 3", 3, input.length());
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class SingleLinkedListJTests {
SingleLinkedListNode input, output;
boolean isEqual = false;
@Test
public void nullEmpty() {
input = null;
output = null;
input = LinkedListUtils.reverseList(input);
assertEquals("reverse null expected null", output, input);
input = new SingleLinkedListNode();
output = new SingleLinkedListNode();
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsIdList(output);
assertEquals("reverse empty expected empty", true, isEqual);
}
@Test
public void reverseList() {
//single node
input = new SingleLinkedListNode(1);
output = new SingleLinkedListNode(1);
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsIdList(output);
assertEquals("reverse 1 expected 1", true, isEqual);
//multiple nodes
input = new SingleLinkedListNode(1);
input.addLast(2);
input.addLast(3);
output = new SingleLinkedListNode(3);
output.addLast(2);
output.addLast(1);
input = LinkedListUtils.reverseList(input);
isEqual = input.equalsDataList(output);
assertEquals("reverse 1,2,3 expected 3,2,1", true, isEqual);
}
}
package com.blogspot.groglogs.structures;
public class SingleLinkedListNode {
public Integer id;
public String data;
public SingleLinkedListNode next;
public SingleLinkedListNode(){
this.id = null;
this.data = null;
this.next = null;
}
public SingleLinkedListNode(Integer id){
this.id = id;
this.data = null;
this.next = null;
}
public SingleLinkedListNode(Integer id, String data){
this.id = id;
this.data = data;
this.next = null;
}
public int length(){
if(this.id == null || this.data == null) return 0;
int count = 0;
SingleLinkedListNode next = this;
while(next != null){
count++;
next = next.next;
}
return count;
}
public void addLast(Integer id, String data){
SingleLinkedListNode next = this;
while(next.next != null) next = next.next;
next.next = new SingleLinkedListNode(id, data);
}
public void addLast(Integer id){
SingleLinkedListNode next = this;
while(next.next != null) next = next.next;
next.next = new SingleLinkedListNode(id);
}
@Override
public boolean equals(Object obj) {
if(obj == null) return false;
if(obj.getClass() != this.getClass()) return false;
SingleLinkedListNode other = (SingleLinkedListNode) obj;
return this.id == other.id && this.data == other.data;
}
public boolean equalsData(SingleLinkedListNode other) {
if(other == null) return false;
return this.data == other.data;
}
public boolean equalsId(SingleLinkedListNode other) {
if(other == null) return false;
return this.id == other.id;
}
public boolean equalsList(SingleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
SingleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equals(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public boolean equalsDataList(SingleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
SingleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equalsData(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public boolean equalsIdList(SingleLinkedListNode other){
if(other == null) return false;
if(this.length() != other.length()) return false;
SingleLinkedListNode this_next = this, other_next = other;
while(this_next != null){
if(!this_next.equalsId(other_next)) return false;
this_next = this_next.next;
other_next = other_next.next;
}
return true;
}
public void printList(){
SingleLinkedListNode next = this;
while(next != null){
System.out.println("id: " + next.id + " - data: " + next.data);
next = next.next;
}
}
}
package com.blogspot.groglogs.structures;
public class StockEntry {
public long date;
public double price;
public StockEntry(long date, double price){
this.date = date;
this.price = price;
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.BuySellEntry;
import com.blogspot.groglogs.structures.StockEntry;
import org.junit.Test;
import java.util.LinkedList;
import java.util.List;
import static org.junit.Assert.assertEquals;
public class StockTradeJTests {
List<StockEntry> in;
BuySellEntry out;
@Test
//null or empty
public void nullEmpty() {
in = null;
out = null;
assertEquals("null input expected null", out, LinkedListUtils.getMaxProfit(in));
in = new LinkedList<>();
out = null;
assertEquals("empty input expected null", out, LinkedListUtils.getMaxProfit(in));
in = new LinkedList<>();
in.add(new StockEntry(1, 1));
out = null;
assertEquals("one entry expected null", out, LinkedListUtils.getMaxProfit(in));
}
@Test
//losing day, price always decreasing
public void losingDay() {
//even size
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 50));
in.add(new StockEntry(3, 10));
in.add(new StockEntry(4, 0));
out = null;
assertEquals("losing day even input expected null", out, LinkedListUtils.getMaxProfit(in));
//odd size
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 50));
in.add(new StockEntry(3, 10));
out = null;
assertEquals("losing day odd input expected null", out, LinkedListUtils.getMaxProfit(in));
//even size, double entries
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 100));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 50));
in.add(new StockEntry(5, 10));
in.add(new StockEntry(6, 10));
in.add(new StockEntry(7, 0));
in.add(new StockEntry(8, 0));
out = null;
assertEquals("losing day double even input expected null", out, LinkedListUtils.getMaxProfit(in));
//odd size, double entries
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 100));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 50));
in.add(new StockEntry(5, 10));
in.add(new StockEntry(6, 10));
out = null;
assertEquals("losing day double odd input expected null", out, LinkedListUtils.getMaxProfit(in));
}
@Test
//winning day, price always increasing
public void winningDay() {
//even size, 0 start
in = new LinkedList<>();
in.add(new StockEntry(1, 0));
in.add(new StockEntry(2, 10));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 100));
out = new BuySellEntry(1, 0, 4, 100);
assertEquals("winning day even 0 base input expected boundaries", out, LinkedListUtils.getMaxProfit(in));
//odd size, 0 start
in = new LinkedList<>();
in.add(new StockEntry(1, 0));
in.add(new StockEntry(2, 10));
in.add(new StockEntry(3, 50));
out = new BuySellEntry(1, 0, 3, 50);
assertEquals("winning day odd 0 base input expected boundaries", out, LinkedListUtils.getMaxProfit(in));
//even size, non 0 start
in = new LinkedList<>();
in.add(new StockEntry(1, 1));
in.add(new StockEntry(2, 10));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 100));
out = new BuySellEntry(1, 1, 4, 100);
assertEquals("winning day even non 0 base input expected boundaries", out, LinkedListUtils.getMaxProfit(in));
//odd size, non 0 start
in = new LinkedList<>();
in.add(new StockEntry(1, 1));
in.add(new StockEntry(2, 10));
in.add(new StockEntry(3, 50));
out = new BuySellEntry(1, 1, 3, 50);
assertEquals("winning day odd non 0 base input expected boundaries", out, LinkedListUtils.getMaxProfit(in));
}
@Test
//mixed day, price fluctuates
public void mixedDay() {
//early buy, late sell
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 10));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 100));
out = new BuySellEntry(2, 10, 4, 100);
assertEquals("mixed day input early buy, late sell", out, LinkedListUtils.getMaxProfit(in));
//early buy, early sell
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 10));
in.add(new StockEntry(3, 100));
in.add(new StockEntry(4, 90));
out = new BuySellEntry(2, 10, 3, 100);
assertEquals("mixed day input early buy, early sell", out, LinkedListUtils.getMaxProfit(in));
//late buy, early sell
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 90));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 60));
in.add(new StockEntry(5, 50));
in.add(new StockEntry(6, 40));
out = new BuySellEntry(3, 50, 4, 60);
assertEquals("mixed day input late buy, early sell", out, LinkedListUtils.getMaxProfit(in));
//late buy, late sell
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 90));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 60));
in.add(new StockEntry(5, 50));
in.add(new StockEntry(6, 100));
out = new BuySellEntry(3, 50, 6, 100);
assertEquals("mixed day input late buy, early sell", out, LinkedListUtils.getMaxProfit(in));
}
@Test
//duplicate mixed day, price fluctuates and repeats pattern
public void duplicateMixedDay() {
//early buy, late sell
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 10));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 100));
in.add(new StockEntry(5, 10));
in.add(new StockEntry(6, 50));
in.add(new StockEntry(7, 100));
out = new BuySellEntry(2, 10, 4, 100);
assertEquals("duplicate mixed day input early buy, late sell expected first find", out, LinkedListUtils.getMaxProfit(in));
//early buy, early sell
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 10));
in.add(new StockEntry(3, 100));
in.add(new StockEntry(4, 90));
in.add(new StockEntry(5, 100));
in.add(new StockEntry(6, 10));
in.add(new StockEntry(7, 100));
in.add(new StockEntry(8, 90));
out = new BuySellEntry(2, 10, 3, 100);
assertEquals("duplicate mixed day input early buy, early sell expected first find", out, LinkedListUtils.getMaxProfit(in));
//late buy, early sell
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 90));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 60));
in.add(new StockEntry(5, 50));
in.add(new StockEntry(6, 60));
in.add(new StockEntry(7, 40));
out = new BuySellEntry(3, 50, 4, 60);
assertEquals("duplicate mixed day input late buy, early sell expected first find", out, LinkedListUtils.getMaxProfit(in));
//late buy, late sell
in = new LinkedList<>();
in.add(new StockEntry(1, 100));
in.add(new StockEntry(2, 90));
in.add(new StockEntry(3, 50));
in.add(new StockEntry(4, 60));
in.add(new StockEntry(5, 50));
in.add(new StockEntry(6, 100));
in.add(new StockEntry(7, 50));
in.add(new StockEntry(8, 60));
in.add(new StockEntry(9, 50));
in.add(new StockEntry(10, 100));
out = new BuySellEntry(3, 50, 6, 100);
assertEquals("duplicate mixed day input late buy, early sell expected first find", out, LinkedListUtils.getMaxProfit(in));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.linkedlistutils.LinkedListUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class ZipListJTests {
SingleLinkedListNode input, output;
boolean isEqual;
@Test
public void nullEmpty() {
input = null;
output = null;
input = LinkedListUtils.zipList(input);
assertEquals("null list expected null", output, input);
input = new SingleLinkedListNode();
output = input;
input = LinkedListUtils.zipList(input);
assertEquals("empty list expected empty", output, input);
}
@Test
public void singleNodeZipList() {
input = new SingleLinkedListNode(1);
output = new SingleLinkedListNode(1);
input = LinkedListUtils.zipList(input);
isEqual = input.equalsIdList(output);
assertEquals("null list expected null", true, isEqual);
}
@Test
public void evenNodeZipList() {
input = new SingleLinkedListNode(1);
output = new SingleLinkedListNode(1);
for(int i = 2; i <= 4 ; i++) input.addLast(i);
output.addLast(4);
output.addLast(2);
output.addLast(3);
input = LinkedListUtils.zipList(input);
isEqual = input.equalsIdList(output);
assertEquals("1,2,3,4 list expected 1,4,2,3", true, isEqual);
}
@Test
public void oddNodeZipList() {
input = new SingleLinkedListNode(1);
output = new SingleLinkedListNode(1);
for(int i = 2; i <= 5 ; i++) input.addLast(i);
output.addLast(5);
output.addLast(2);
output.addLast(4);
output.addLast(3);
input = LinkedListUtils.zipList(input);
isEqual = input.equalsIdList(output);
assertEquals("1,2,3,4,5 list expected 1,5,2,4,3", true, isEqual);
}
}