summaryrefslogtreecommitdiff
path: root/graphics/asymptote/tests/template/imports/sortedset.asy
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/asymptote/tests/template/imports/sortedset.asy')
-rw-r--r--graphics/asymptote/tests/template/imports/sortedset.asy208
1 files changed, 208 insertions, 0 deletions
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