summaryrefslogtreecommitdiff
path: root/graphics/asymptote/tests/template/imports
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/asymptote/tests/template/imports')
-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.asy41
-rw-r--r--graphics/asymptote/tests/template/imports/zip.asy5
11 files changed, 947 insertions, 0 deletions
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..9f47aa5797
--- /dev/null
+++ b/graphics/asymptote/tests/template/imports/structTemplate.asy
@@ -0,0 +1,41 @@
+// 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();
+
+StartTest(Lib.testName + ': Unraveling and accessing static member');
+from T unravel global;
+int g = global;
+EndTest(); \ No newline at end of file
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