Last active
April 29, 2024 13:55
-
-
Save coderodde/a1aedecee548951fc8bdbb283005dadd to your computer and use it in GitHub Desktop.
My MSc thesis research program.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Scanner; | |
public class DemoRepl { | |
public static void main(String[] args) { | |
Scanner scanner = new Scanner(System.in); | |
DynamicTableStack array = new DynamicTableStack(3, 3); | |
while (true) { | |
try { | |
System.out.print(">>> "); | |
String line = scanner.nextLine().trim(); | |
String[] tokens = line.split("\\s+"); | |
if (tokens[0].equals("new")) { | |
int m = Integer.parseInt(tokens[1]); | |
int d = Integer.parseInt(tokens[2]); | |
array = new DynamicTableStack(m, d); | |
System.out.println(array); | |
} else if (tokens[0].equals("print")) { | |
System.out.println(array); | |
} else if (tokens[0].equals("add")) { | |
int k = tokens.length > 1 ? Integer.parseInt(tokens[1]) : 1; | |
int work = array.add(k); | |
System.out.printf("Work: %d.\n", work); | |
System.out.println(array); | |
} else if (tokens[0].equals("cond")) { | |
int n = tokens.length > 1 ? | |
Integer.parseInt(tokens[1]) : | |
array.size(); | |
System.out.println(array.getCondition(n)); | |
} else if (tokens[0].equals("remove")) { | |
int k = tokens.length > 1 ? Integer.parseInt(tokens[1]) : 1; | |
int work = array.remove(k); | |
System.out.printf("Work: %d.\n", work); | |
System.out.println(array); | |
} else if (tokens[0].equals("alln")) { | |
int workClosedForm = array.getWork(array.size()); | |
int workRecursive = array.getWorkRecursively(array.size()); | |
DynamicTableStack arr = new DynamicTableStack(array); | |
int workDischarge = arr.discharge(); | |
System.out.printf( | |
"Closed form work: " + | |
"%d, recursive: %d, discharged: %d.\n", | |
workClosedForm, | |
workRecursive, | |
workDischarge); | |
} else if (tokens[0].equals("work")) { | |
int n = Integer.parseInt(tokens[1]); | |
System.out.println(array.getWork(n)); | |
} else if (tokens[0].equals("rwork")) { | |
int n = Integer.parseInt(tokens[1]); | |
System.out.println(array.getWorkRecursively(n)); | |
} else if (tokens[0].equals("discharge")) { | |
DynamicTableStack other = new DynamicTableStack(array); | |
System.out.println(other.discharge()); | |
} else if (tokens[0].equals("exit") | |
|| tokens[0].equals("quit")) { | |
System.out.println("Bye!"); | |
System.exit(0); | |
} else if (tokens[0].equals("help")) { | |
System.out.println( | |
""" | |
HELP MESSAGE: | |
add - Add an element. | |
add k - Add k elements. | |
alln - Print the total works. | |
cond - Delegates to 'cond size'. | |
cond n - Print condition for n. | |
discharge - Discharge the entire array. | |
exit - Halt this program. | |
new m d - Create new array. | |
print - Print the array. | |
quit - Halt this program. | |
remove - Remove an element. | |
remove k - Remove k elements. | |
rwork n - Get work recursively for n parameter. | |
work n - Get work for n parameter. | |
help - Print this help message. | |
"""); | |
} | |
} catch (Exception ex) { | |
System.out.printf("Error: %s.\n", ex.getMessage()); | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public final class DynamicTableStack { | |
private final int m; | |
private final int d; | |
private int capacity; | |
private int size = 0; | |
private int expansions = 0; | |
DynamicTableStack(int m, int d) { | |
this.m = m; | |
this.d = d; | |
this.capacity = m; | |
} | |
DynamicTableStack(DynamicTableStack array) { | |
this.m = array.m; | |
this.d = array.d; | |
this.capacity = array.capacity; | |
this.expansions = array.expansions; | |
this.size = array.size; | |
} | |
/** | |
* Get the {@code m} parameter (the initial, minimal capacity). | |
* | |
* @return the {@code m} parameter. | |
*/ | |
int getM() { | |
return m; | |
} | |
/** | |
* Get the {@code d} parameter (the increment/decrement size). | |
* | |
* @return the {@code d} parameter. | |
*/ | |
int getD() { | |
return d; | |
} | |
/** | |
* Adds a single element to the end of this dynamic table. | |
* | |
* @return the total number of steps made. | |
*/ | |
int add() { | |
if (isFull()) { | |
capacity += d; | |
size++; | |
return m + 1 + d * (expansions++); | |
} | |
size++; | |
return 1; | |
} | |
/** | |
* Adds {@code k} elements to the tail of this dynamic table. | |
* | |
* @param k the number of elements to add. | |
* | |
* @return the total number of work steps done. | |
*/ | |
int add(int k) { | |
int work = 0; | |
for (int i = 0; i < k; i++) { | |
work += add(); | |
} | |
return work; | |
} | |
/** | |
* Removes the rightmost (last) element from this dynamic table. | |
* | |
* @return the number of work steps made. | |
*/ | |
int remove() { | |
if (size > m && shouldContract()) { | |
capacity -= d; | |
size--; | |
return m + 1 + (--expansions) * d; | |
} else { | |
size--; | |
return 1; | |
} | |
} | |
/** | |
* Remove {@code k} elements from the tail of the dynamic table. | |
* | |
* @param k the requested number of elements to remove. | |
* | |
* @return the total number of work steps. | |
*/ | |
int remove(int k) { | |
int count = 0; | |
for (int i = 0, end = Math.min(size, k); i < end; i++) { | |
count += remove(); | |
} | |
return count; | |
} | |
/** | |
* Returns the number of elements in this dynamic table. | |
* | |
* @return the number of elements in this dynamic table. | |
*/ | |
int size() { | |
return size; | |
} | |
/** | |
* Returns the current capacity of this dynamic table. | |
* | |
* @return the current capacity of this dynamic table. | |
*/ | |
int getCapacity() { | |
return capacity; | |
} | |
/** | |
* Checks whether the contraction condition is met. | |
* | |
* @param n the target dynamic table size. | |
* | |
* @return {@code true} iff the condition is met. | |
*/ | |
boolean getCondition(int n) { | |
return (n - m - 1) % d == 0; | |
} | |
/** | |
* Checks whether the contraction condition is met for the current dynamic | |
* table size. | |
* | |
* @return {@code true} iff the condition is met. | |
*/ | |
boolean getCondition() { | |
return getCondition(size); | |
} | |
/** | |
* Clears the entire dynamic table and returns the total number of steps. | |
* | |
* @return the total number of steps. | |
*/ | |
int discharge() { | |
return remove(size); | |
} | |
/** | |
* Gets the number of steps needed to remove {@code n} elements from this | |
* dynamic table. | |
* | |
* @param n the target size parameter. | |
* | |
* @return the total number of steps. | |
*/ | |
int getWork(int n) { | |
return n + getSum(n); | |
} | |
/** | |
* Same as {@link #getWork(int) }, but computes its value via a recursive | |
* formula. | |
* | |
* @param n the target size parameter. | |
* | |
* @return the total number of steps. | |
*/ | |
int getWorkRecursively(int n) { | |
if (n == 0) { | |
return 0; | |
} | |
int x = n - 1 - m; | |
return (x % d == 0 ? n : 1) + getWorkRecursively(n - 1); | |
} | |
/** | |
* Computes the sum term for the {@link #getWork(int) }. | |
* | |
* @param n the target dynamic table size. | |
* | |
* @return the sum term. | |
*/ | |
private int getSum(int n) { | |
int sum = 0; | |
int endIndex = (int)(Math.ceil((double)(n - m) / | |
(double)(d) | |
) | |
) - 1; | |
int startIndex = 0; | |
for (int i = startIndex; i <= endIndex; i++) { | |
sum += d * i + m; | |
} | |
return sum; | |
} | |
@Override | |
public String toString() { | |
StringBuilder sb = new StringBuilder(); | |
for (int i = 0; i < size; i++) { | |
if (i > 0 && (i - m) % d == 0) { | |
sb.append("|"); | |
} | |
sb.append("X"); | |
} | |
for (int i = size; i < getCurrentCapacity(); i++) { | |
sb.append("."); | |
} | |
return sb.toString(); | |
} | |
/** | |
* Returns the current capacity. | |
* | |
* @return the current capacity. | |
*/ | |
private int getCurrentCapacity() { | |
return m + d * expansions; | |
} | |
/** | |
* Returns {@code true} iff the dynamic table should contract. | |
* | |
* @return a boolean value indicating whether the dynamic table should | |
* contract. | |
*/ | |
private boolean shouldContract() { | |
return getCurrentCapacity() - size == d - 1; | |
} | |
/** | |
* Returns {@code true} iff the dynamic table is full. | |
* | |
* @return a boolean value indicating whether they dynamic table is full. | |
*/ | |
private boolean isFull() { | |
return size == capacity; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import org.junit.Test; | |
import static org.junit.Assert.*; | |
public class DynamicTableStackTest { | |
private DynamicTableStack array; | |
@Test | |
public void testAdd_0args() { | |
array = new DynamicTableStack(2, 3); | |
assertEquals(0, array.size()); | |
assertEquals(2, array.getCapacity()); | |
assertEquals(1, array.add()); | |
assertEquals(1, array.size()); | |
assertEquals(2, array.getCapacity()); | |
assertEquals(1, array.add()); | |
assertEquals(2, array.size()); | |
assertEquals(2, array.getCapacity()); | |
assertEquals(3, array.add()); | |
assertEquals(3, array.size()); | |
assertEquals(5, array.getCapacity()); | |
} | |
@Test | |
public void testAdd_int() { | |
array = new DynamicTableStack(2, 3); | |
assertEquals(2, array.add(2)); | |
assertEquals(2, array.size()); | |
assertEquals(4, array.add(2)); | |
assertEquals(4, array.size()); | |
assertEquals(5, array.getCapacity()); | |
} | |
@Test | |
public void testRemove_0args() { | |
array = new DynamicTableStack(2, 3); | |
array.add(8); | |
assertEquals(1, array.remove()); | |
assertEquals(7, array.size()); | |
assertEquals(1, array.remove()); | |
assertEquals(6, array.size()); | |
assertEquals(6, array.remove()); | |
assertEquals(5, array.size()); | |
assertEquals(1, array.remove()); | |
assertEquals(4, array.size()); | |
assertEquals(1, array.remove()); | |
assertEquals(3, array.size()); | |
assertEquals(3, array.remove()); | |
assertEquals(2, array.size()); | |
assertEquals(1, array.remove()); | |
assertEquals(1, array.size()); | |
assertEquals(1, array.remove()); | |
assertEquals(0, array.size()); | |
} | |
@Test | |
public void testRemove_int() { | |
array = new DynamicTableStack(2, 3); | |
array.add(8); | |
// Here, array = xx|xxx|xxx | |
assertEquals(1 + 1 + 6, array.remove(3)); | |
assertEquals(1 + 1 + 3, array.remove(3)); | |
assertEquals(1 + 1, array.remove(2)); | |
} | |
@Test | |
public void testDischargeGetWork() { | |
array = new DynamicTableStack(2, 3); | |
array.add(100); | |
for (int i = 0; i < array.size(); i++) { | |
DynamicTableStack aux = new DynamicTableStack(array.getM(), array.getD()); | |
aux.add(i); | |
assertEquals(array.getWork(i), aux.discharge()); | |
assertEquals(array.getWork(i), array.getWorkRecursively(i)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment