diff options
Diffstat (limited to 'graphics/asymptote/tests/template')
17 files changed, 1881 insertions, 0 deletions
diff --git a/graphics/asymptote/tests/template/functionTest.asy b/graphics/asymptote/tests/template/functionTest.asy new file mode 100644 index 0000000000..770322b2c1 --- /dev/null +++ b/graphics/asymptote/tests/template/functionTest.asy @@ -0,0 +1,20 @@ +import TestLib; + +typedef real F1(string); +typedef string F2(int); + +real f1(string s) { + return length(s); +} + +F2 f2 = operator ecast; + +StartTest("Function type parameters"); + +from 'template/imports/composeFunctions'(R=real, F1=F1, F2=F2, I=int) access + compose; + +real r = compose(f1, f2)(1234567890); +assert(r == 10); + +EndTest();
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/imports/A.asy b/graphics/asymptote/tests/template/imports/A.asy new file mode 100644 index 0000000000..dc737fdb91 --- /dev/null +++ b/graphics/asymptote/tests/template/imports/A.asy @@ -0,0 +1,4 @@ +typedef import(T); + +struct A { +} diff --git a/graphics/asymptote/tests/template/imports/B.asy b/graphics/asymptote/tests/template/imports/B.asy new file mode 100644 index 0000000000..c048a43f46 --- /dev/null +++ b/graphics/asymptote/tests/template/imports/B.asy @@ -0,0 +1 @@ +typedef import(T); diff --git a/graphics/asymptote/tests/template/imports/C.asy b/graphics/asymptote/tests/template/imports/C.asy new file mode 100644 index 0000000000..38e8939bad --- /dev/null +++ b/graphics/asymptote/tests/template/imports/C.asy @@ -0,0 +1,6 @@ +typedef import(T); + +T a=new T; +assert(a.x == 1); + +int global = 17; diff --git a/graphics/asymptote/tests/template/imports/composeFunctions.asy b/graphics/asymptote/tests/template/imports/composeFunctions.asy new file mode 100644 index 0000000000..63678e6c6b --- /dev/null +++ b/graphics/asymptote/tests/template/imports/composeFunctions.asy @@ -0,0 +1,9 @@ +typedef import(R, F1, F2, I); + +typedef R FF(I); + +FF compose(F1 f1, F2 f2) { + return new R(I i) { + return f1(f2(i)); + }; +}
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/imports/notTemplate.asy b/graphics/asymptote/tests/template/imports/notTemplate.asy new file mode 100644 index 0000000000..bd309b07ba --- /dev/null +++ b/graphics/asymptote/tests/template/imports/notTemplate.asy @@ -0,0 +1,4 @@ +struct A { + static int global = 17; + int local = 3; +}
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/imports/notTemplate2.asy b/graphics/asymptote/tests/template/imports/notTemplate2.asy new file mode 100644 index 0000000000..4c9375c3b3 --- /dev/null +++ b/graphics/asymptote/tests/template/imports/notTemplate2.asy @@ -0,0 +1,4 @@ +struct B { + import 'template/imports/notTemplate' as notTemplate; +} +B b;
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/imports/pureset.asy b/graphics/asymptote/tests/template/imports/pureset.asy new file mode 100644 index 0000000000..472a37ccb4 --- /dev/null +++ b/graphics/asymptote/tests/template/imports/pureset.asy @@ -0,0 +1,116 @@ +typedef import(T); + +struct Set_T { + int size(); + bool empty() { + return size() == 0; + } + bool contains(T item); + bool insert(T item); + T replace(T item); // Inserts item, and returns the item that was + // replaced, or emptyresponse if no item was replaced. + T get(T item); + bool delete(T item); + // Calls process on each item in the collection until process returns false. + void forEach(bool process(T item)); +} + +struct NaiveSet_T { + private T[] buffer = new T[0]; + private T emptyresponse; + private bool equiv(T a, T b); + + void operator init(bool equiv(T a, T b), T emptyresponse) { + this.equiv = equiv; + this.emptyresponse = emptyresponse; + } + + int size() { + return buffer.length; + } + + bool contains(T item) { + for (T a : buffer) { + if (equiv(a, item)) { + return true; + } + } + return false; + } + + bool insert(T item) { + if (contains(item)) { + return false; + } + buffer.push(item); + return true; + } + + T replace(T item) { + for (int i = 0; i < buffer.length; ++i) { + if (equiv(buffer[i], item)) { + T old = buffer[i]; + buffer[i] = item; + return old; + } + } + buffer.push(item); + return emptyresponse; + } + + T get(T item) { + for (T a : buffer) { + if (equiv(a, item)) { + return a; + } + } + return emptyresponse; + } + + bool delete(T item) { + for (int i = 0; i < buffer.length; ++i) { + if (equiv(buffer[i], item)) { + buffer[i] = buffer[buffer.length - 1]; + buffer.pop(); + return true; + } + } + return false; + } + + void forEach(bool process(T item)) { + for (T a : buffer) { + if (!process(a)) { + return; + } + } + } + +} + +Set_T operator cast(NaiveSet_T naiveSet) { + Set_T set = new Set_T; + set.size = naiveSet.size; + set.contains = naiveSet.contains; + set.insert = naiveSet.insert; + set.replace = naiveSet.replace; + set.get = naiveSet.get; + set.delete = naiveSet.delete; + set.forEach = naiveSet.forEach; + return set; +} + +T[] operator cast(Set_T set) { + T[] buffer = new T[set.size()]; + int i = 0; + set.forEach(new bool(T item) { + buffer[i] = item; + ++i; + return true; + }); + return buffer; +} + +Set_T makeNaiveSet(bool equiv(T, T), T emptyresponse) { + return NaiveSet_T(equiv, emptyresponse); +}
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/imports/sortedset.asy b/graphics/asymptote/tests/template/imports/sortedset.asy new file mode 100644 index 0000000000..bcef6889e0 --- /dev/null +++ b/graphics/asymptote/tests/template/imports/sortedset.asy @@ -0,0 +1,208 @@ +typedef import(T); + +from "template/imports/pureset"(T=T) access Set_T, operator cast, makeNaiveSet; + +struct SortedSet_T { + int size(); + bool empty() { return size() == 0; } + bool contains(T item); + T get(T item); // Returns the item in the collection that is + // equivalent to item, or emptyresponse if there is no + // such item. + // Returns the least element > item, or emptyresponse if there is no such + // element. + T after(T item); + // Returns the greatest element < item, or emptyresponse if there is no such + // element. + T before(T item); + T firstGEQ(T item) { return contains(item) ? get(item) : after(item); } + T firstLEQ(T item) { return contains(item) ? get(item) : before(item); } + T min(); // Returns emptyresponse if collection is empty. + T popMin(); // Returns emptyresponse if collection is empty. + T max(); // Returns emptyresponse if collection is empty. + T popMax(); // Returns emptyresponse if collection is empty. + bool insert(T item); // Returns true iff the collection is modified. + T replace(T item); // Inserts item, and returns the item that was + // replaced, or emptyresponse if no item was replaced. + bool delete(T item); // Returns true iff the collection is modified. + // Calls process on each item in the collection, in ascending order, + // until process returns false. + void forEach(bool process(T item)); +} + +T[] operator cast(SortedSet_T set) { + T[] result; + set.forEach(new bool(T item) { + result.push(item); + return true; + }); + return result; +} + +Set_T unSort(SortedSet_T sorted_set) { + Set_T set = new Set_T; + set.size = sorted_set.size; + set.empty = sorted_set.empty; + set.contains = sorted_set.contains; + set.insert = sorted_set.insert; + set.replace = sorted_set.replace; + set.get = sorted_set.get; + set.delete = sorted_set.delete; + set.forEach = sorted_set.forEach; + return set; +} + +Set_T operator cast(SortedSet_T) = unSort; + +// For testing purposes, we provide a naive implementation of SortedSet_T. +// This implementation is highly inefficient, but it is correct, and can be +// used to test other implementations of SortedSet_T. +struct NaiveSortedSet_T { + private bool lt(T a, T b); + private T[] buffer = new T[0]; + private T emptyresponse; + + private bool leq(T a, T b) { + return !lt(b, a); + } + private bool gt(T a, T b) { + return lt(b, a); + } + private bool geq(T a, T b) { + return leq(b, a); + } + private bool equiv(T a, T b) { + return leq(a, b) && leq(b, a); + } + + void operator init(bool lessThan(T, T), T emptyresponse) { + this.lt = lessThan; + this.emptyresponse = emptyresponse; + } + + int size() { + return buffer.length; + } + + bool contains(T item) { + for (T possibility : buffer) { + if (equiv(possibility, item)) return true; + } + return false; + } + + T after(T item) { + for (T possibility : buffer) { + if (gt(possibility, item)) return possibility; + } + return emptyresponse; + } + + T before(T item) { + for (int ii = buffer.length - 1; ii >= 0; --ii) { + T possibility = buffer[ii]; + if (lt(possibility, item)) return possibility; + } + return emptyresponse; + } + + T min() { + if (buffer.length == 0) return emptyresponse; + return buffer[0]; + } + + T popMin() { + if (buffer.length == 0) return emptyresponse; + T toreturn = buffer[0]; + buffer.delete(0); + return toreturn; + } + + T max() { + if (buffer.length == 0) return emptyresponse; + return buffer[buffer.length - 1]; + } + + T popMax() { + if (buffer.length == 0) return emptyresponse; + return buffer.pop(); + } + + bool insert(T item) { + for (int i = 0; i < buffer.length; ++i) { + if (equiv(buffer[i], item)) return false; + else if (gt(buffer[i], item)) { + buffer.insert(i, item); + return true; + } + } + buffer.push(item); + return true; + } + + T replace(T item) { + for (int i = 0; i < buffer.length; ++i) { + if (equiv(buffer[i], item)) { + T toreturn = buffer[i]; + buffer[i] = item; + return toreturn; + } + else if (gt(buffer[i], item)) { + buffer.insert(i, item); + return emptyresponse; + } + } + buffer.push(item); + return emptyresponse; + } + + T get(T item) { + for (T possibility : buffer) { + if (equiv(possibility, item)) return possibility; + } + return emptyresponse; + } + + bool delete(T item) { + for (int i = 0; i < buffer.length; ++i) { + if (equiv(buffer[i], item)) { + buffer.delete(i); + return true; + } + } + return false; + } + + void forEach(bool process(T item)) { + for (T item : buffer) { + if (!process(item)) break; + } + } +} + +SortedSet_T operator cast(NaiveSortedSet_T naive) { + SortedSet_T toreturn; + toreturn.size = naive.size; + toreturn.contains = naive.contains; + toreturn.after = naive.after; + toreturn.before = naive.before; + toreturn.min = naive.min; + toreturn.popMin = naive.popMin; + toreturn.max = naive.max; + toreturn.popMax = naive.popMax; + toreturn.insert = naive.insert; + toreturn.replace = naive.replace; + toreturn.get = naive.get; + toreturn.delete = naive.delete; + toreturn.forEach = naive.forEach; + return toreturn; +} + +// Compose cast operators, since implicit casting is not transitive. +T[] operator cast(NaiveSortedSet_T naive) { + return (SortedSet_T)naive; +} + +SortedSet_T makeNaiveSortedSet(bool lessThan(T, T), T emptyresponse) { + return NaiveSortedSet_T(lessThan, emptyresponse); +}
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/imports/splaytree.asy b/graphics/asymptote/tests/template/imports/splaytree.asy new file mode 100644 index 0000000000..d5850482f9 --- /dev/null +++ b/graphics/asymptote/tests/template/imports/splaytree.asy @@ -0,0 +1,549 @@ +typedef import(T); + +from "template/imports/sortedset"(T=T) access + Set_T, + SortedSet_T, + operator cast; + +private struct treenode { + treenode leftchild; + treenode rightchild; + T value; + void operator init(T value) { + this.value = value; + } + + bool inOrder(bool run(T)) { + if (leftchild != null) { + if (!leftchild.inOrder(run)) return false; + } + if (!run(value)) return false; + if (rightchild != null) { + if (!rightchild.inOrder(run)) return false; + } + return true; + } +} + +private struct NodeProgressEnum { + restricted static int num = 0; + private static int make() { + return (++num - 1); + } + static int NOT_STARTED = make(); + static int LEFT_DONE = make(); + static int SELF_DONE = make(); + static int RIGHT_DONE = make(); +} + +private struct NodeInProgress { + treenode node; + int progress = NodeProgressEnum.NOT_STARTED; + void operator init(treenode node) { + this.node = node; + } +} + +void inOrderNonRecursive(treenode root, bool run(T)) { + if (root == null) return; + NodeInProgress[] stack = new NodeInProgress[0]; + stack.cyclic = true; + stack.push(NodeInProgress(root)); + while (stack.length > 0) { + NodeInProgress current = stack[-1]; + if (current.progress == NodeProgressEnum.NOT_STARTED) { + if (current.node.leftchild != null) { + stack.push(NodeInProgress(current.node.leftchild)); + } + current.progress = NodeProgressEnum.LEFT_DONE; + } else if (current.progress == NodeProgressEnum.LEFT_DONE) { + if (!run(current.node.value)) return; + current.progress = NodeProgressEnum.SELF_DONE; + } else if (current.progress == NodeProgressEnum.SELF_DONE) { + if (current.node.rightchild != null) { + stack.push(NodeInProgress(current.node.rightchild)); + } + current.progress = NodeProgressEnum.RIGHT_DONE; + } else { + assert(current.progress == NodeProgressEnum.RIGHT_DONE); + stack.pop(); + } + } +} + + +private treenode splay(treenode[] ancestors, bool lessthan(T a, T b)) { + bool operator < (T a, T b) = lessthan; + + if (ancestors.length == 0) return null; + + treenode root = ancestors[0]; + treenode current = ancestors.pop(); + + while (ancestors.length >= 2) { + treenode parent = ancestors.pop(); + treenode grandparent = ancestors.pop(); + + if (ancestors.length > 0) { + treenode greatparent = ancestors[-1]; + if (greatparent.leftchild == grandparent) { + greatparent.leftchild = current; + } else greatparent.rightchild = current; + } + + bool currentside = (parent.leftchild == current); + bool grandside = (grandparent.leftchild == parent); + + if (currentside == grandside) { // zig-zig + if (currentside) { // both left + treenode B = current.rightchild; + treenode C = parent.rightchild; + + current.rightchild = parent; + parent.leftchild = B; + parent.rightchild = grandparent; + grandparent.leftchild = C; + } else { // both right + treenode B = parent.leftchild; + treenode C = current.leftchild; + + current.leftchild = parent; + parent.leftchild = grandparent; + parent.rightchild = C; + grandparent.rightchild = B; + } + } else { // zig-zag + if (grandside) { // left-right + treenode B = current.leftchild; + treenode C = current.rightchild; + + current.leftchild = parent; + current.rightchild = grandparent; + parent.rightchild = B; + grandparent.leftchild = C; + } else { //right-left + treenode B = current.leftchild; + treenode C = current.rightchild; + + current.leftchild = grandparent; + current.rightchild = parent; + grandparent.rightchild = B; + parent.leftchild = C; + } + } + } + + if (ancestors.length > 0) { + ancestors.pop(); + if (current == root.leftchild) { + treenode B = current.rightchild; + current.rightchild = root; + root.leftchild = B; + } else { + treenode B = current.leftchild; + current.leftchild = root; + root.rightchild = B; + } + } + + return current; +} + +struct SplayTree_T { + private treenode root = null; + restricted int size = 0; + private bool operator < (T a, T b); + private T emptyresponse; + + void operator init(bool lessthan(T,T), T emptyresponse) { + operator< = lessthan; + this.emptyresponse = emptyresponse; + } + + int size() { + return size; + } + + bool empty() { + assert((root == null) == (size == 0)); + return root == null; + } + + bool contains(T value) { + treenode[] parentStack = new treenode[0]; + parentStack.cyclic = true; + parentStack.push(root); + while (true) { + treenode current = parentStack[-1]; + if (current == null) { + parentStack.pop(); + root = splay(parentStack, operator<); + return false; + } + if (value < current.value) { + parentStack.push(current.leftchild); + } else if (current.value < value) { + parentStack.push(current.rightchild); + } else break; + } + root = splay(parentStack, operator<); + return true; + } + + T after(T item) { + treenode[] parentStack = new treenode[0]; + parentStack.cyclic = true; + parentStack.push(root); + T strictUpperBound = emptyresponse; + bool found = false; + while (true) { + treenode current = parentStack[-1]; + if (current == null) { + parentStack.pop(); + root = splay(parentStack, operator<); + return strictUpperBound; + } + if (found || item < current.value) { + strictUpperBound = current.value; + parentStack.push(current.leftchild); + } else { + parentStack.push(current.rightchild); + if (!(current.value < item)) + found = true; + } + } + assert(false, "Unreachable code"); + return emptyresponse; + } + + T before(T item) { + treenode[] parentStack = new treenode[0]; + parentStack.cyclic = true; + parentStack.push(root); + T strictLowerBound = emptyresponse; + bool found = false; + while (true) { + treenode current = parentStack[-1]; + if (current == null) { + parentStack.pop(); + root = splay(parentStack, operator<); + return strictLowerBound; + } + if (found || current.value < item) { + strictLowerBound = current.value; + parentStack.push(current.rightchild); + } else { + parentStack.push(current.leftchild); + if (!(item < current.value)) + found = true; + } + } + assert(false, "Unreachable code"); + return emptyresponse; + } + + T firstGEQ(T item) { + treenode[] parentStack = new treenode[0]; + parentStack.cyclic = true; + parentStack.push(root); + T upperBound = emptyresponse; + while (true) { + treenode current = parentStack[-1]; + if (current == null) { + parentStack.pop(); + root = splay(parentStack, operator<); + return upperBound; + } + if (current.value < item) { + parentStack.push(current.rightchild); + } else if (item < current.value) { + upperBound = current.value; + parentStack.push(current.leftchild); + } else { + root = splay(parentStack, operator<); + return current.value; + } + } + assert(false, "Unreachable code"); + return emptyresponse; + } + + T firstLEQ(T item) { + treenode[] parentStack = new treenode[0]; + parentStack.cyclic = true; + parentStack.push(root); + T lowerBound = emptyresponse; + while (true) { + treenode current = parentStack[-1]; + if (current == null) { + parentStack.pop(); + root = splay(parentStack, operator<); + return lowerBound; + } + if (item < current.value) { + parentStack.push(current.leftchild); + } else if (current.value < item) { + lowerBound = current.value; + parentStack.push(current.rightchild); + } else { + root = splay(parentStack, operator<); + return current.value; + } + } + assert(false, "Unreachable code"); + return emptyresponse; + } + + T min() { + if (root == null) return emptyresponse; + treenode[] ancestors = new treenode[0]; + ancestors.cyclic = true; + treenode current = root; + while (current != null) { + ancestors.push(current); + current = current.leftchild; + } + root = splay(ancestors, operator<); + return root.value; + } + + T popMin() { + if (root == null) return emptyresponse; + treenode[] ancestors = new treenode[0]; + ancestors.cyclic = true; + treenode current = root; + while (current != null) { + ancestors.push(current); + current = current.leftchild; + } + root = splay(ancestors, operator<); + T toReturn = root.value; + root = root.rightchild; + --size; + return toReturn; + } + + T max() { + if (root == null) return emptyresponse; + treenode[] ancestors = new treenode[0]; + ancestors.cyclic = true; + treenode current = root; + while (current != null) { + ancestors.push(current); + current = current.rightchild; + } + root = splay(ancestors, operator<); + return root.value; + } + + T popMax() { + if (root == null) return emptyresponse; + treenode[] ancestors = new treenode[0]; + ancestors.cyclic = true; + treenode current = root; + while (current != null) { + ancestors.push(current); + current = current.rightchild; + } + root = splay(ancestors, operator<); + T toReturn = root.value; + root = root.leftchild; + --size; + return toReturn; + } + + /* + * returns true iff the tree was modified + */ + bool insert(T value) { + if (root == null) { + root = treenode(value); + ++size; + return true; + } + treenode[] ancestors = new treenode[0]; + ancestors.cyclic = true; + ancestors.push(root); + + bool toReturn = false; + + while (!toReturn) { + treenode current = ancestors[-1]; + if (value < current.value) { + if (current.leftchild == null) { + current.leftchild = treenode(value); + toReturn = true; + } + ancestors.push(current.leftchild); + } else if (current.value < value) { + if (current.rightchild == null) { + current.rightchild = treenode(value); + toReturn = true; + } + ancestors.push(current.rightchild); + } else { + root = splay(ancestors, operator<); + return false; + } + } + + root = splay(ancestors, operator<); + ++size; + return true; + } + + T replace(T item) { + if (root == null) { + insert(item); + return emptyresponse; + } + treenode[] ancestors = new treenode[0]; + ancestors.cyclic = true; + ancestors.push(root); + treenode current = root; + while (true) { + if (item < current.value) { + if (current.leftchild == null) { + current.leftchild = treenode(item); + ancestors.push(current.leftchild); + break; + } + ancestors.push(current.leftchild); + current = current.leftchild; + } else if (current.value < item) { + if (current.rightchild == null) { + current.rightchild = treenode(item); + ancestors.push(current.rightchild); + break; + } + ancestors.push(current.rightchild); + current = current.rightchild; + } else { + T toReturn = current.value; + current.value = item; + root = splay(ancestors, operator<); + return toReturn; + } + } + root = splay(ancestors, operator<); + ++size; + return emptyresponse; + } + + T get(T item) { + if (root == null) return emptyresponse; + treenode[] parentStack = new treenode[0]; + parentStack.cyclic = true; + parentStack.push(root); + while (true) { + treenode current = parentStack[-1]; + if (current == null) { + parentStack.pop(); + root = splay(parentStack, operator<); + return emptyresponse; + } + if (item < current.value) { + parentStack.push(current.leftchild); + } else if (current.value < item) { + parentStack.push(current.rightchild); + } else { + root = splay(parentStack, operator<); + return current.value; + } + } + assert(false, "Unreachable code"); + return emptyresponse; + } + + /* + * returns true iff the tree was modified + */ + bool delete(T value) { + treenode[] ancestors = new treenode[0]; + ancestors.cyclic = true; // Makes ancestors[-1] refer to the last entry. + ancestors.push(root); + + while (true) { + treenode current = ancestors[-1]; + if (current == null) { + ancestors.pop(); + root = splay(ancestors, operator<); + return false; + } + if (value < current.value) + ancestors.push(current.leftchild); + else if (current.value < value) + ancestors.push(current.rightchild); + else break; + } + + treenode toDelete = ancestors.pop(); + treenode parent = null; + if (ancestors.length > 0) parent = ancestors[-1]; + + if (toDelete.leftchild == null) { + if (parent != null) { + if (parent.rightchild == toDelete) { + parent.rightchild = toDelete.rightchild; + } else { + parent.leftchild = toDelete.rightchild; + } + } else root = toDelete.rightchild; + } else if (toDelete.rightchild == null) { + if (parent == null) { + root = toDelete.leftchild; + } else if (parent.rightchild == toDelete) { + parent.rightchild = toDelete.leftchild; + } else parent.leftchild = toDelete.leftchild; + } else { + treenode[] innerStack = new treenode[0]; + innerStack.cyclic = true; + treenode current = toDelete.rightchild; + while (current != null) { + innerStack.push(current); + current = current.leftchild; + } + toDelete.rightchild = splay(innerStack, operator<); + toDelete.value = toDelete.rightchild.value; + toDelete.rightchild = toDelete.rightchild.rightchild; + } + + if (parent != null) root = splay(ancestors, operator<); + --size; + return true; + } + + void forEach(bool run(T)) { + inOrderNonRecursive(root, run); + } + +} + +SortedSet_T operator cast(SplayTree_T splaytree) { + SortedSet_T result = new SortedSet_T; + result.size = splaytree.size; + result.empty = splaytree.empty; + result.contains = splaytree.contains; + result.after = splaytree.after; + result.before = splaytree.before; + result.firstGEQ = splaytree.firstGEQ; + result.firstLEQ = splaytree.firstLEQ; + result.min = splaytree.min; + result.popMin = splaytree.popMin; + result.max = splaytree.max; + result.popMax = splaytree.popMax; + result.insert = splaytree.insert; + result.replace = splaytree.replace; + result.get = splaytree.get; + result.delete = splaytree.delete; + result.forEach = splaytree.forEach; + return result; +} + +Set_T operator cast(SplayTree_T splaytree) { + return (SortedSet_T)splaytree; +} + +T[] operator cast(SplayTree_T splaytree) { + return (SortedSet_T)splaytree; +}
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/imports/structTemplate.asy b/graphics/asymptote/tests/template/imports/structTemplate.asy new file mode 100644 index 0000000000..5894d2e280 --- /dev/null +++ b/graphics/asymptote/tests/template/imports/structTemplate.asy @@ -0,0 +1,36 @@ +// Assumption: T is a struct with a static int `global` and a non-static int +// `local`. Lib is a struct with a static string `testName`. +typedef import(T, Lib); +import TestLib; + +StartTest('Accessing static testName'); +Lib.testName; +EndTest(); + +StartTest(Lib.testName + ': new'); +new T; +EndTest(); + +StartTest(Lib.testName + ': Unspecified Declaration'); +T a; +EndTest(); + +StartTest(Lib.testName + ': Initializing to null'); +T b = null; +EndTest(); + +StartTest(Lib.testName + ': Initializing to new'); +T c = new T; +EndTest(); + +StartTest(Lib.testName + ': Access static member'); +int d = T.global; +EndTest(); + +StartTest(Lib.testName + ': Access non-static member'); +int e = c.local; +EndTest(); + +StartTest(Lib.testName + ': Access static member from instance'); +int f = c.global; +EndTest(); diff --git a/graphics/asymptote/tests/template/imports/zip.asy b/graphics/asymptote/tests/template/imports/zip.asy new file mode 100644 index 0000000000..4d02f98b6a --- /dev/null +++ b/graphics/asymptote/tests/template/imports/zip.asy @@ -0,0 +1,5 @@ +typedef import(T); + +T[][] zip(...T[][] arrays) { + return transpose(arrays); +}
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/initTest.asy b/graphics/asymptote/tests/template/initTest.asy new file mode 100644 index 0000000000..7def279138 --- /dev/null +++ b/graphics/asymptote/tests/template/initTest.asy @@ -0,0 +1,23 @@ +access "template/imports/A"(T=int) as a; +unravel a; +access "template/imports/B"(T=A) as b; +unravel b; + +import TestLib; + +StartTest("init"); +A c; +EndTest(); + +StartTest("new"); +struct X { + struct A { + int x=1; + } +} + +X x; + +access "template/imports/C"(T=x.A) as p; + +EndTest(); diff --git a/graphics/asymptote/tests/template/multiImport.asy b/graphics/asymptote/tests/template/multiImport.asy new file mode 100644 index 0000000000..94d5c30feb --- /dev/null +++ b/graphics/asymptote/tests/template/multiImport.asy @@ -0,0 +1,25 @@ +import TestLib; + +StartTest('multiple_imports'); +struct A {int x=1;} +access "template/imports/C"(T=A) as p; +assert(p.global == 17); +p.global = 42; +access "template/imports/C"(T=A) as q; +assert(q.global == 42); +EndTest(); + +StartTest('import_in_function'); +struct B {int x=1;} +void f(int expected, int newValue) { + // Importing inside a function is not recommended practice, but it should + // work. + access "template/imports/C"(T=B) as p; + assert(p.global == expected); + p.global = newValue; +} +f(17, 23); +f(23, 27); +access "template/imports/C"(T=B) as p; +assert(p.global == 27); +EndTest(); diff --git a/graphics/asymptote/tests/template/sortedsetTest.asy b/graphics/asymptote/tests/template/sortedsetTest.asy new file mode 100644 index 0000000000..66dbb88ec1 --- /dev/null +++ b/graphics/asymptote/tests/template/sortedsetTest.asy @@ -0,0 +1,254 @@ +import TestLib; + +StartTest("NaiveSortedSet"); + +from "template/imports/wrapper"(T=int) access + Wrapper_T as wrapped_int, + wrap, + alias; + +bool operator < (wrapped_int a, wrapped_int b) { + return a.t < b.t; +} + +bool operator == (wrapped_int a, wrapped_int b) { + return a.t == b.t; +} + +from "template/imports/pureset"(T=wrapped_int) access + Set_T as Set_wrapped_int, + makeNaiveSet; + +from "template/imports/sortedset"(T=wrapped_int) access + SortedSet_T as SortedSet_wrapped_int, + makeNaiveSortedSet, + operator cast, + unSort; + +struct ActionEnum { + static restricted int numActions = 0; + static private int next() { + return ++numActions - 1; + } + static restricted int INSERT = next(); + static restricted int REPLACE = next(); + static restricted int DELETE = next(); + static restricted int CONTAINS = next(); + static restricted int DELETE_CONTAINS = next(); +} + +from "template/imports/zip"(T=int) access zip; +from mapArray(Src=wrapped_int, Dst=int) access map; +int get(wrapped_int a) { + return a.t; +} + +int[] operator cast(wrapped_int[] a) { + for (wrapped_int x : a) { + assert(!alias(x, null), 'Null element in array'); + } + return map(get, a); +} + +string differences(Set_wrapped_int a, Set_wrapped_int b) { + if (a.size() != b.size()) { + return 'Different sizes: ' + string(a.size()) + ' vs ' + string(b.size()); + } + wrapped_int[] aArray = sort(a, operator<); + int[] aIntArray = map(get, aArray); + wrapped_int[] bArray = sort(b, operator<); + int[] bIntArray = map(get, bArray); + string arrayValues = '[\n'; + bool different = false; + for (int i = 0; i < aIntArray.length; ++i) { + arrayValues += ' [' + format('%5d', aIntArray[i]) + ',' + + format('%5d', bIntArray[i]) + ']'; + if (!alias(aArray[i], bArray[i])) { + arrayValues += ' <---'; + different = true; + } + arrayValues += '\n'; + } + arrayValues += ']'; + // write(arrayValues + '\n'); + if (different) { + return arrayValues; + } + return ''; +} + +string string(int[] a) { + string result = '['; + for (int i = 0; i < a.length; ++i) { + if (i > 0) { + result += ', '; + } + result += string(a[i]); + } + result += ']'; + return result; +} + +string string(bool[] a) { + string result = '['; + for (int i = 0; i < a.length; ++i) { + if (i > 0) { + result += ', '; + } + result += a[i] ? 'true' : 'false'; + } + result += ']'; + return result; +} + +typedef void Action(int ...Set_wrapped_int[]); + +Action[] actions = new Action[ActionEnum.numActions]; +actions[ActionEnum.INSERT] = new void(int maxItem ...Set_wrapped_int[] sets) { + wrapped_int toInsert = wrap(rand() % maxItem); + // write('Inserting ' + string(toInsert.t) + '\n'); + for (Set_wrapped_int s : sets) { + s.insert(toInsert); + } +}; +actions[ActionEnum.REPLACE] = new void(int maxItem ...Set_wrapped_int[] sets) { + wrapped_int toReplace = wrap(rand() % maxItem); + // write('Replacing ' + string(toReplace.t) + '\n'); + wrapped_int[] results = new wrapped_int[]; + for (Set_wrapped_int s : sets) { + results.push(s.replace(toReplace)); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } +}; +actions[ActionEnum.DELETE] = new void(int maxItem ...Set_wrapped_int[] sets) { + wrapped_int toDelete = wrap(rand() % maxItem); + // write('Deleting ' + string(toDelete.t) + '\n'); + bool[] results = new bool[]; + for (Set_wrapped_int s : sets) { + results.push(s.delete(toDelete)); + } + if (results.length > 0) { + bool expected = results[0]; + for (bool r : results) { + assert(r == expected, 'Different results: ' + string(results)); + } + } +}; +actions[ActionEnum.CONTAINS] = new void(int maxItem ...Set_wrapped_int[] sets) +{ + int toCheck = rand() % maxItem; + // write('Checking ' + string(toCheck) + '\n'); + bool[] results = new bool[]; + for (Set_wrapped_int s : sets) { + results.push(s.contains(wrap(toCheck))); + } + if (results.length > 0) { + bool expected = results[0]; + for (bool r : results) { + assert(r == expected, 'Different results: ' + string(results)); + } + } +}; +actions[ActionEnum.DELETE_CONTAINS] = new void(int ...Set_wrapped_int[] sets) { + if (sets.length == 0) { + return; + } + int initialSize = sets[0].size(); + if (initialSize == 0) { + return; + } + int indexToDelete = rand() % initialSize; + int i = 0; + wrapped_int toDelete = null; + bool process(wrapped_int a) { + if (i == indexToDelete) { + toDelete = wrap(a.t); + return false; + } + ++i; + return true; + } + sets[0].forEach(process); + assert(i < initialSize, 'Index out of range'); + // write('Deleting ' + string(toDelete.t) + '\n'); + int i = 0; + for (Set_wrapped_int s : sets) { + assert(s.contains(toDelete), 'Contains failed ' + string(i)); + assert(s.delete(toDelete), 'Delete failed'); + assert(!s.contains(toDelete), 'Contains failed'); + assert(s.size() == initialSize - 1, 'Size failed'); + ++i; + } +}; +real[] increasingProbs = new real[ActionEnum.numActions]; +increasingProbs[ActionEnum.INSERT] = 0.7; +increasingProbs[ActionEnum.REPLACE] = 0.1; +increasingProbs[ActionEnum.DELETE] = 0.05; +increasingProbs[ActionEnum.CONTAINS] = 0.1; +increasingProbs[ActionEnum.DELETE_CONTAINS] = 0.05; +assert(sum(increasingProbs) == 1, 'Probabilities do not sum to 1'); + +real[] decreasingProbs = new real[ActionEnum.numActions]; +decreasingProbs[ActionEnum.INSERT] = 0.1; +decreasingProbs[ActionEnum.REPLACE] = 0.1; +decreasingProbs[ActionEnum.DELETE] = 0.4; +decreasingProbs[ActionEnum.CONTAINS] = 0.1; +decreasingProbs[ActionEnum.DELETE_CONTAINS] = 0.3; +assert(sum(decreasingProbs) == 1, 'Probabilities do not sum to 1'); + +Set_wrapped_int pure_set = makeNaiveSet(operator ==, (wrapped_int)null); +SortedSet_wrapped_int sorted_set = + makeNaiveSortedSet(operator <, (wrapped_int)null); + +int chooseAction(real[] probs) { + real r = unitrand(); + real sum = 0; + for (int i = 0; i < probs.length; ++i) { + sum += probs[i]; + if (r < sum) { + return i; + } + } + return probs.length - 1; +} + +bool isStrictlySorted(wrapped_int[] arr) { + for (int i = 1; i < arr.length; ++i) { + if (!(arr[i - 1] < arr[i])) { + return false; + } + } + return true; +} + +int maxSize = 0; +for (int i = 0; i < 2000; ++i) { + real[] probs = i < 800 ? increasingProbs : decreasingProbs; + int choice = chooseAction(probs); + actions[choice](100, pure_set, sorted_set); + string diffs = differences(pure_set, sorted_set); + assert(diffs == '', 'Pure vs sorted: \n' + diffs); + assert(isStrictlySorted(sorted_set), 'Not sorted'); + maxSize = max(maxSize, pure_set.size()); +} +// write('Max size: ' + string(maxSize) + '\n'); + +// int maxSize = 0; +// for (int i = 0; i < 2000; ++i) { +// real[] probs = i < 800 ? increasingProbs : decreasingProbs; +// int choice = chooseAction(probs); +// actions[choice](1000, pure_set, unSort(sorted_set)); +// string diffs = differences(pure_set, sorted_set); +// assert(diffs == '', 'Pure vs sorted: \n' + diffs); +// maxSize = max(maxSize, pure_set.size()); +// } +// write('Max size: ' + string(maxSize) + '\n'); + +EndTest();
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/splaytreeTest.asy b/graphics/asymptote/tests/template/splaytreeTest.asy new file mode 100644 index 0000000000..3ad5811f26 --- /dev/null +++ b/graphics/asymptote/tests/template/splaytreeTest.asy @@ -0,0 +1,553 @@ + +import TestLib; + +StartTest("SplayTree_as_Set"); + +from "template/imports/wrapper"(T=int) access + Wrapper_T as wrapped_int, + wrap, + alias; + +bool operator < (wrapped_int a, wrapped_int b) { + return a.t < b.t; +} + +bool operator == (wrapped_int a, wrapped_int b) { + return a.t == b.t; +} + +from "template/imports/sortedset"(T=wrapped_int) access + makeNaiveSortedSet, + SortedSet_T as SortedSet_wrapped_int; + +from "template/imports/splaytree"(T=wrapped_int) access + SplayTree_T as SplayTree_wrapped_int, + operator cast; + +struct ActionEnum { + static restricted int numActions = 0; + static private int next() { + return ++numActions - 1; + } + static restricted int INSERT = next(); + static restricted int REPLACE = next(); + static restricted int DELETE = next(); + static restricted int CONTAINS = next(); + static restricted int DELETE_CONTAINS = next(); +} + +from mapArray(Src=wrapped_int, Dst=int) access map; +int get(wrapped_int a) { + return a.t; +} + +int[] operator cast(wrapped_int[] a) { + for (wrapped_int x : a) { + assert(!alias(x, null), 'Null element in array'); + } + return map(get, a); +} + +string differences(SortedSet_wrapped_int a, SortedSet_wrapped_int b) { + if (a.size() != b.size()) { + return 'Different sizes: ' + string(a.size()) + ' vs ' + string(b.size()); + } + wrapped_int[] aArray = a; + int[] aIntArray = aArray; + wrapped_int[] bArray = b; + int[] bIntArray = bArray; + string arrayValues = '[\n'; + bool different = false; + for (int i = 0; i < aIntArray.length; ++i) { + arrayValues += ' [' + format('%5d', aIntArray[i]) + ',' + + format('%5d', bIntArray[i]) + ']'; + if (!alias(aArray[i], bArray[i])) { + arrayValues += ' <---'; + different = true; + } + arrayValues += '\n'; + } + arrayValues += ']'; + // write(arrayValues + '\n'); + if (different) { + return arrayValues; + } + return ''; +} + +string string(int[] a) { + string result = '['; + for (int i = 0; i < a.length; ++i) { + if (i > 0) { + result += ', '; + } + result += string(a[i]); + } + result += ']'; + return result; +} + +string string(bool[] a) { + string result = '['; + for (int i = 0; i < a.length; ++i) { + if (i > 0) { + result += ', '; + } + result += a[i] ? 'true' : 'false'; + } + result += ']'; + return result; +} + +typedef void Action(int ...SortedSet_wrapped_int[]); + +Action[] actions = new Action[ActionEnum.numActions]; +actions[ActionEnum.INSERT] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + wrapped_int toInsert = wrap(rand() % maxItem); + // write('Inserting ' + string(toInsert.t) + '\n'); + for (SortedSet_wrapped_int s : sets) { + s.insert(toInsert); + } + }; +actions[ActionEnum.REPLACE] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + wrapped_int toReplace = wrap(rand() % maxItem); + // write('Replacing ' + string(toReplace.t) + '\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.replace(toReplace)); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } + }; +actions[ActionEnum.DELETE] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + wrapped_int toDelete = wrap(rand() % maxItem); + // write('Deleting ' + string(toDelete.t) + '\n'); + bool[] results = new bool[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.delete(toDelete)); + } + if (results.length > 0) { + bool expected = results[0]; + for (bool r : results) { + assert(r == expected, 'Different results: ' + string(results)); + } + } + }; +actions[ActionEnum.CONTAINS] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + int toCheck = rand() % maxItem; + // write('Checking ' + string(toCheck) + '\n'); + bool[] results = new bool[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.contains(wrap(toCheck))); + } + if (results.length > 0) { + bool expected = results[0]; + for (bool r : results) { + assert(r == expected, 'Different results: ' + string(results)); + } + } + }; +actions[ActionEnum.DELETE_CONTAINS] = + new void(int ...SortedSet_wrapped_int[] sets) { + if (sets.length == 0) { + return; + } + int initialSize = sets[0].size(); + if (initialSize == 0) { + return; + } + int indexToDelete = rand() % initialSize; + int i = 0; + wrapped_int toDelete = null; + bool process(wrapped_int a) { + if (i == indexToDelete) { + toDelete = wrap(a.t); + return false; + } + ++i; + return true; + } + sets[0].forEach(process); + assert(i < initialSize, 'Index out of range'); + // write('Deleting ' + string(toDelete.t) + '\n'); + int i = 0; + for (SortedSet_wrapped_int s : sets) { + assert(s.contains(toDelete), 'Contains failed ' + string(i)); + assert(s.delete(toDelete), 'Delete failed'); + assert(!s.contains(toDelete), 'Contains failed'); + assert(s.size() == initialSize - 1, 'Size failed'); + ++i; + } + }; +real[] increasingProbs = new real[ActionEnum.numActions]; +increasingProbs[ActionEnum.INSERT] = 0.7; +increasingProbs[ActionEnum.REPLACE] = 0.1; +increasingProbs[ActionEnum.DELETE] = 0.05; +increasingProbs[ActionEnum.CONTAINS] = 0.1; +increasingProbs[ActionEnum.DELETE_CONTAINS] = 0.05; +assert(sum(increasingProbs) == 1, 'Probabilities do not sum to 1'); + +real[] decreasingProbs = new real[ActionEnum.numActions]; +decreasingProbs[ActionEnum.INSERT] = 0.1; +decreasingProbs[ActionEnum.REPLACE] = 0.1; +decreasingProbs[ActionEnum.DELETE] = 0.4; +decreasingProbs[ActionEnum.CONTAINS] = 0.1; +decreasingProbs[ActionEnum.DELETE_CONTAINS] = 0.3; +assert(sum(decreasingProbs) == 1, 'Probabilities do not sum to 1'); + +SortedSet_wrapped_int sorted_set = + makeNaiveSortedSet(operator <, (wrapped_int)null); +SplayTree_wrapped_int splayset = + SplayTree_wrapped_int(operator <, (wrapped_int)null); + +int chooseAction(real[] probs) { + real r = unitrand(); + real sum = 0; + for (int i = 0; i < probs.length; ++i) { + sum += probs[i]; + if (r < sum) { + return i; + } + } + return probs.length - 1; +} + +bool isStrictlySorted(wrapped_int[] arr) { + for (int i = 1; i < arr.length; ++i) { + if (!(arr[i - 1] < arr[i])) { + return false; + } + } + return true; +} + +int maxSize = 0; +for (int i = 0; i < 2000; ++i) { + real[] probs = i < 800 ? increasingProbs : decreasingProbs; + int choice = chooseAction(probs); + actions[choice](100, sorted_set, splayset); + string diffs = differences(sorted_set, splayset); + assert(diffs == '', 'Naive vs splayset: \n' + diffs); + assert(isStrictlySorted(splayset), 'Not sorted'); + maxSize = max(maxSize, splayset.size()); +} +EndTest(); + +StartTest("SplayTree_as_SortedSet"); + +struct ActionEnum { + static restricted int numActions = 0; + static private int next() { + return ++numActions - 1; + } + static restricted int CONTAINS = next(); + static restricted int AFTER = next(); + static restricted int BEFORE = next(); + static restricted int FIRST_GEQ = next(); + static restricted int FIRST_LEQ = next(); + static restricted int MIN = next(); + static restricted int POP_MIN = next(); + static restricted int MAX = next(); + static restricted int POP_MAX = next(); + static restricted int INSERT = next(); + static restricted int REPLACE = next(); + static restricted int GET = next(); + static restricted int DELETE = next(); + static restricted int DELETE_CONTAINS = next(); +} + +Action[] actions = new Action[ActionEnum.numActions]; +actions[ActionEnum.CONTAINS] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + int toCheck = rand() % maxItem; + // write('Checking ' + string(toCheck) + '\n'); + bool[] results = new bool[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.contains(wrap(toCheck))); + } + if (results.length > 0) { + bool expected = results[0]; + for (bool r : results) { + assert(r == expected, 'Different results: ' + string(results)); + } + } + }; +actions[ActionEnum.AFTER] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + int toCheck = rand() % maxItem; + // write('After ' + string(toCheck) + '\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.after(wrap(toCheck))); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } + }; +actions[ActionEnum.BEFORE] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + int toCheck = rand() % maxItem; + // write('Before ' + string(toCheck) + '\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.before(wrap(toCheck))); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } + }; +actions[ActionEnum.FIRST_GEQ] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + int toCheck = rand() % maxItem; + // write('First greater or equal ' + string(toCheck) + '\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.firstGEQ(wrap(toCheck))); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } + }; +actions[ActionEnum.FIRST_LEQ] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + int toCheck = rand() % maxItem; + // write('First less or equal ' + string(toCheck) + '\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.firstLEQ(wrap(toCheck))); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } + }; +actions[ActionEnum.MIN] = new void(int ...SortedSet_wrapped_int[] sets) { + // write('Min\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.min()); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } +}; +actions[ActionEnum.POP_MIN] = new void(int ...SortedSet_wrapped_int[] sets) { + // write('Pop min\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.popMin()); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } +}; +actions[ActionEnum.MAX] = new void(int ...SortedSet_wrapped_int[] sets) { + // write('Max\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.max()); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } +}; +actions[ActionEnum.POP_MAX] = new void(int ...SortedSet_wrapped_int[] sets) { + // write('Pop max\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.popMax()); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } +}; +actions[ActionEnum.INSERT] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + wrapped_int toInsert = wrap(rand() % maxItem); + // write('Inserting ' + string(toInsert.t) + '\n'); + for (SortedSet_wrapped_int s : sets) { + s.insert(toInsert); + } + }; +actions[ActionEnum.REPLACE] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + wrapped_int toReplace = wrap(rand() % maxItem); + // write('Replacing ' + string(toReplace.t) + '\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.replace(toReplace)); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } + }; +actions[ActionEnum.GET] = new void(int maxItem ...SortedSet_wrapped_int[] sets) +{ + wrapped_int toGet = wrap(rand() % maxItem); + // write('Getting ' + string(toGet) + '\n'); + wrapped_int[] results = new wrapped_int[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.get(toGet)); + } + if (results.length > 0) { + wrapped_int expected = results[0]; + for (wrapped_int r : results) { + if (!alias(r, expected)) { + assert(false, 'Different results: ' + string(results)); + } + } + } +}; +actions[ActionEnum.DELETE] = + new void(int maxItem ...SortedSet_wrapped_int[] sets) { + wrapped_int toDelete = wrap(rand() % maxItem); + // write('Deleting ' + string(toDelete.t) + '\n'); + bool[] results = new bool[]; + for (SortedSet_wrapped_int s : sets) { + results.push(s.delete(toDelete)); + } + if (results.length > 0) { + bool expected = results[0]; + for (bool r : results) { + assert(r == expected, 'Different results: ' + string(results)); + } + } + }; +actions[ActionEnum.DELETE_CONTAINS] = + new void(int ...SortedSet_wrapped_int[] sets) { + if (sets.length == 0) { + return; + } + int initialSize = sets[0].size(); + if (initialSize == 0) { + return; + } + int indexToDelete = rand() % initialSize; + int i = 0; + wrapped_int toDelete = null; + bool process(wrapped_int a) { + if (i == indexToDelete) { + toDelete = wrap(a.t); + return false; + } + ++i; + return true; + } + sets[0].forEach(process); + assert(i < initialSize, 'Index out of range'); + // write('Deleting ' + string(toDelete.t) + '\n'); + int i = 0; + for (SortedSet_wrapped_int s : sets) { + assert(s.delete(toDelete), 'Delete failed'); + assert(!s.contains(toDelete), 'Contains failed'); + assert(s.size() == initialSize - 1, 'Size failed'); + ++i; + } + }; + +real[] increasingProbs = array(n=ActionEnum.numActions, value=0.0); +// Actions that don't modify the set (except for rebalancing): +increasingProbs[ActionEnum.CONTAINS] = 1 / 2^5; +increasingProbs[ActionEnum.AFTER] = 1 / 2^5; +increasingProbs[ActionEnum.BEFORE] = 1 / 2^5; +increasingProbs[ActionEnum.FIRST_GEQ] = 1 / 2^5; +increasingProbs[ActionEnum.FIRST_LEQ] = 1 / 2^5; +increasingProbs[ActionEnum.MIN] = 1 / 2^5; +increasingProbs[ActionEnum.MAX] = 1 / 2^5; +increasingProbs[ActionEnum.GET] = 1 / 2^5; +// 1/4 probability of this sort of action: +assert(sum(increasingProbs) == 8 / 2^5); +// Actions that might add an element: +increasingProbs[ActionEnum.INSERT] = 1 / 4; +increasingProbs[ActionEnum.REPLACE] = 1 / 4; +assert(sum(increasingProbs) == 3/4); +// Actions that might remove an element: +increasingProbs[ActionEnum.POP_MIN] = 1 / 16; +increasingProbs[ActionEnum.POP_MAX] = 1 / 16; +increasingProbs[ActionEnum.DELETE] = 1 / 16; +increasingProbs[ActionEnum.DELETE_CONTAINS] = 1 / 16; +assert(sum(increasingProbs) == 1, 'Probabilities do not sum to 1'); + +real[] decreasingProbs = copy(increasingProbs); +// Actions that might add an element: +decreasingProbs[ActionEnum.INSERT] = 1 / 8; +decreasingProbs[ActionEnum.REPLACE] = 1 / 8; +// Actions that might remove an element: +decreasingProbs[ActionEnum.POP_MIN] = 1 / 8; +decreasingProbs[ActionEnum.POP_MAX] = 1 / 8; +decreasingProbs[ActionEnum.DELETE] = 1 / 8; +decreasingProbs[ActionEnum.DELETE_CONTAINS] = 1 / 8; +assert(sum(decreasingProbs) == 1, 'Probabilities do not sum to 1'); + +SortedSet_wrapped_int sorted_set = + makeNaiveSortedSet(operator <, (wrapped_int)null); +SplayTree_wrapped_int splayset = + SplayTree_wrapped_int(operator <, (wrapped_int)null); + + +int maxSize = 0; +for (int i = 0; i < 2000; ++i) { + real[] probs = i < 800 ? increasingProbs : decreasingProbs; + int choice = chooseAction(probs); + actions[choice](100, sorted_set, splayset); + string diffs = differences(sorted_set, splayset); + assert(diffs == '', 'Naive vs splayset: \n' + diffs); + assert(isStrictlySorted(splayset), 'Not sorted'); + maxSize = max(maxSize, splayset.size()); +} + +EndTest();
\ No newline at end of file diff --git a/graphics/asymptote/tests/template/structTest.asy b/graphics/asymptote/tests/template/structTest.asy new file mode 100644 index 0000000000..e961397e9f --- /dev/null +++ b/graphics/asymptote/tests/template/structTest.asy @@ -0,0 +1,64 @@ +struct BareStruct { + static string testName = "bare struct"; +} +struct A { + static int global = 17; + int local = 3; +} +access 'template/imports/structTemplate'(T=A, Lib=BareStruct) as bareStruct; + +struct NestedStruct { + static string testName = "nested struct"; +} +struct B { + static struct C { + static int global = 17; + int local = 3; + } +} +access 'template/imports/structTemplate'(T=B.C, Lib=NestedStruct) + as nestedStruct; + +struct InnerStruct { + static string testName = "inner struct"; +} +struct D { + struct E { + static int global = 17; + int local = 3; + } +} +D d; +access 'template/imports/structTemplate'(T=d.E, Lib=InnerStruct) + as innerStruct; + +struct DeeplyNestedStruct { + static string testName = "deeply nested struct"; +} + +struct G { + struct H { + static struct I { + static int global = 17; + int local = 3; + } + } +} +G g; + +access 'template/imports/structTemplate'(T=g.H.I, Lib=DeeplyNestedStruct) + as deeplyNestedStruct; + +struct ImportedStruct { + static string testName = "imported struct"; +} +access 'template/imports/notTemplate' as notTemplate; +access 'template/imports/structTemplate'(T=notTemplate.A, Lib=ImportedStruct) + as importedStruct; + +struct NestedImport { + static string testName = "nested import"; +} +access 'template/imports/notTemplate2' as notTemplate2; +access 'template/imports/structTemplate'(T=notTemplate2.b.A, Lib=NestedImport) + as nestedImport;
\ No newline at end of file |