summaryrefslogtreecommitdiff
path: root/graphics/asymptote/tests/template
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/asymptote/tests/template')
-rw-r--r--graphics/asymptote/tests/template/functionTest.asy20
-rw-r--r--graphics/asymptote/tests/template/imports/A.asy4
-rw-r--r--graphics/asymptote/tests/template/imports/B.asy1
-rw-r--r--graphics/asymptote/tests/template/imports/C.asy6
-rw-r--r--graphics/asymptote/tests/template/imports/composeFunctions.asy9
-rw-r--r--graphics/asymptote/tests/template/imports/notTemplate.asy4
-rw-r--r--graphics/asymptote/tests/template/imports/notTemplate2.asy4
-rw-r--r--graphics/asymptote/tests/template/imports/pureset.asy116
-rw-r--r--graphics/asymptote/tests/template/imports/sortedset.asy208
-rw-r--r--graphics/asymptote/tests/template/imports/splaytree.asy549
-rw-r--r--graphics/asymptote/tests/template/imports/structTemplate.asy36
-rw-r--r--graphics/asymptote/tests/template/imports/zip.asy5
-rw-r--r--graphics/asymptote/tests/template/initTest.asy23
-rw-r--r--graphics/asymptote/tests/template/multiImport.asy25
-rw-r--r--graphics/asymptote/tests/template/sortedsetTest.asy254
-rw-r--r--graphics/asymptote/tests/template/splaytreeTest.asy553
-rw-r--r--graphics/asymptote/tests/template/structTest.asy64
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