122 lines
4.3 KiB
Java
122 lines
4.3 KiB
Java
package unit;
|
|
|
|
import java.util.*;
|
|
|
|
/**
|
|
* CompatibleMachineModelTest — CWE-407 cura-0001
|
|
*
|
|
* Models CompatibleMachineModel._update() in cura/Machines/Models/CompatibleMachineModel.py:
|
|
* slow() = O(P * I): for each printer, rebuild list comprehension [item["name"] for item in self.items]
|
|
* fast() = O(P + I): build set once before loop, O(1) membership per printer
|
|
*
|
|
* Parameters: P printers across output devices, I already-added items.
|
|
* Assert: slowOps > fastOps * 5x at P=100, I=100.
|
|
*/
|
|
public class CompatibleMachineModelTest {
|
|
|
|
static long slowOps;
|
|
static long fastOps;
|
|
|
|
/**
|
|
* Slow: O(P * I) — models: if printer.name in [item["name"] for item in self.items]
|
|
* Rebuilds list and scans it for each printer.
|
|
*/
|
|
static List<String> updateSlow(List<String> printerNames) {
|
|
slowOps = 0;
|
|
List<String> items = new ArrayList<>();
|
|
for (String name : printerNames) {
|
|
boolean found = false;
|
|
for (String item : items) { // O(I) scan per printer
|
|
slowOps++;
|
|
if (item.equals(name)) {
|
|
found = true;
|
|
break;
|
|
}
|
|
}
|
|
if (!found) {
|
|
items.add(name);
|
|
}
|
|
}
|
|
return items;
|
|
}
|
|
|
|
/**
|
|
* Fast: O(P + I) — models: seen = {item["name"] for item in self.items}; if name in seen
|
|
* Builds a hash set once, then does O(1) membership per printer.
|
|
*/
|
|
static List<String> updateFast(List<String> printerNames) {
|
|
fastOps = 0;
|
|
List<String> items = new ArrayList<>();
|
|
Set<String> seen = new HashSet<>();
|
|
fastOps += 1; // set construction cost counted once
|
|
for (String name : printerNames) {
|
|
fastOps++; // O(1) hash lookup
|
|
if (!seen.contains(name)) {
|
|
seen.add(name);
|
|
items.add(name);
|
|
}
|
|
}
|
|
return items;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int passed = 0;
|
|
int failed = 0;
|
|
|
|
// Test 1: correctness — duplicates deduplicated
|
|
{
|
|
List<String> names = Arrays.asList(
|
|
"Ultimaker-S5-01", "Ultimaker-S5-02", "Ultimaker-S5-01",
|
|
"Ultimaker-S3-01", "Ultimaker-S5-02"
|
|
);
|
|
List<String> slow = updateSlow(names);
|
|
List<String> fast = updateFast(names);
|
|
Set<String> slowSet = new HashSet<>(slow);
|
|
Set<String> fastSet = new HashSet<>(fast);
|
|
if (slowSet.equals(fastSet) && slow.size() == 3) {
|
|
System.out.println("PASS test1: both methods deduplicate correctly (" + slow.size() + " unique)");
|
|
passed++;
|
|
} else {
|
|
System.out.println("FAIL test1: slow=" + slow + " fast=" + fast);
|
|
failed++;
|
|
}
|
|
}
|
|
|
|
// Test 2: op-count speedup at P=200 printers, 50% duplicate names
|
|
{
|
|
int P = 200;
|
|
List<String> names = new ArrayList<>();
|
|
for (int i = 0; i < P; i++) {
|
|
names.add("Printer-" + (i % (P / 2))); // 50% duplicates
|
|
}
|
|
updateSlow(names);
|
|
long sOps = slowOps;
|
|
updateFast(names);
|
|
long fOps = fastOps;
|
|
double ratio = (double) sOps / fOps;
|
|
if (ratio >= 5.0) {
|
|
System.out.printf("PASS test2: P=%d sOps=%d fOps=%d ratio=%.1fx%n", P, sOps, fOps, ratio);
|
|
passed++;
|
|
} else {
|
|
System.out.printf("FAIL test2: P=%d sOps=%d fOps=%d ratio=%.1fx (want >=5x)%n", P, sOps, fOps, ratio);
|
|
failed++;
|
|
}
|
|
}
|
|
|
|
// Test 3: empty printer list
|
|
{
|
|
List<String> slow = updateSlow(Collections.emptyList());
|
|
List<String> fast = updateFast(Collections.emptyList());
|
|
if (slow.isEmpty() && fast.isEmpty()) {
|
|
System.out.println("PASS test3: empty list handled correctly");
|
|
passed++;
|
|
} else {
|
|
System.out.println("FAIL test3: expected empty, got slow=" + slow + " fast=" + fast);
|
|
failed++;
|
|
}
|
|
}
|
|
|
|
System.out.printf("%nResult: %d/%d tests passed%n", passed, passed + failed);
|
|
if (failed > 0) System.exit(1);
|
|
}
|
|
}
|