Roll Observatory packages and add a roll script

packages/quiver/test/collection/treeset_test.dart

+// Copyright 2013 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+library quiver.collection.treeset_test;
+
+import 'package:quiver/collection.dart';
+import 'package:test/test.dart';
+
+main() {
+  group("TreeSet", () {
+    group("when empty", () {
+      TreeSet<num> tree;
+      setUp(() {
+        tree = new TreeSet<num>();
+      });
+      test("should actually be empty", () => expect(tree, isEmpty));
+      test("should not contain an element",
+          () => expect(tree.lookup(0), isNull));
+      test("has no element when iterating forward", () {
+        var i = tree.iterator;
+        expect(i.moveNext(), isFalse, reason: "moveNext reports an element");
+        expect(i.current, isNull, reason: "current returns an element");
+      });
+      test("has no element when iterating backward", () {
+        var i = tree.iterator;
+        expect(i.movePrevious(), isFalse,
+            reason: "movePrevious reports an element");
+        expect(i.current, isNull, reason: "current returns an element");
+      });
+    });
+
+    group("with [10, 20, 15]", () {
+      AvlTreeSet<num> tree;
+      setUp(() {
+        tree = new TreeSet<num>()..addAll([10, 20, 15]);
+      });
+      test("lookup succeeds for inserted elements", () {
+        expect(tree.lookup(10), equals(10), reason: "missing 10");
+        expect(tree.lookup(15), equals(15), reason: "missing 15");
+        expect(tree.lookup(20), equals(20), reason: "missing 20");
+      });
+      test("order is correct", () {
+        AvlNode ten = tree.getNode(10);
+        AvlNode twenty = tree.getNode(20);
+        AvlNode fifteen = tree.getNode(15);
+        expect(ten.predecessor, isNull, reason: "10 is the smalled element");
+        expect(ten.successor, equals(fifteen), reason: "15 should follow 10");
+        expect(ten.successor.successor, equals(twenty),
+            reason: "20 should follow 10");
+
+        expect(twenty.successor, isNull, reason: "20 is the largest element");
+        expect(twenty.predecessor, equals(fifteen), reason: "15 is before 20");
+        expect(twenty.predecessor.predecessor, equals(ten),
+            reason: "10 is before 15");
+      });
+    });
+
+    group("with repeated elements", () {
+      TreeSet<num> tree;
+      setUp(() {
+        tree = new TreeSet<num>()..addAll([10, 20, 15, 21, 30, 20]);
+      });
+
+      test("only contains subset", () {
+        var it = tree.iterator;
+        var testList = new List.from([10, 15, 20, 21, 30]);
+        while (it.moveNext()) {
+          expect(it.current, equals(testList.removeAt(0)));
+        }
+        expect(testList.length, equals(0), reason: "valid subset seen in tree");
+      });
+    });
+
+    group("iteration", () {
+      TreeSet<num> tree;
+      setUp(() {
+        tree = new TreeSet<num>()..addAll([10, 20, 15, 21, 30]);
+      });
+
+      test("works bidirectionally", () {
+        var it = tree.iterator;
+        while (it.moveNext());
+        expect(it.movePrevious(), isTrue,
+            reason: "we can backup after walking the entire list");
+        expect(it.current, equals(30),
+            reason: "the last element is what we expect");
+        while (it.movePrevious());
+        expect(it.moveNext(), isTrue,
+            reason: "we can move next after walking to the front of the set");
+        expect(it.current, equals(10),
+            reason: "the first element is what we expect");
+      });
+
+      group("from", () {
+        test("non-inserted midpoint works forward", () {
+          var it = tree.fromIterator(19);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(20));
+        });
+
+        test("non-inserted midpoint works for movePrevious()", () {
+          var it = tree.fromIterator(19);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.movePrevious(), isTrue,
+              reason: "movePrevious() from spot works");
+          expect(it.current, equals(15));
+        });
+
+        test("non-inserted midpoint works reversed", () {
+          var it = tree.fromIterator(19, reversed: true);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(15));
+        });
+
+        test("non-inserted midpoint works reversed, movePrevious()", () {
+          var it = tree.fromIterator(19, reversed: true);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.movePrevious(), isTrue,
+              reason: "movePrevious() from spot works");
+          expect(it.current, equals(20));
+        });
+
+        test("inserted midpoint works forward", () {
+          var it = tree.fromIterator(20);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(20));
+        });
+
+        test("inserted midpoint works reversed", () {
+          var it = tree.fromIterator(20, reversed: true);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(20));
+        });
+
+        test("after the set", () {
+          var it = tree.fromIterator(100);
+          expect(it.current, isNull);
+          expect(it.moveNext(), isFalse, reason: "not following items");
+          expect(it.movePrevious(), isTrue, reason: "backwards movement valid");
+          expect(it.current, equals(30));
+        });
+
+        test("before the set", () {
+          var it = tree.fromIterator(0);
+          expect(it.current, isNull);
+          expect(it.movePrevious(), isFalse, reason: "not previous items");
+          expect(it.moveNext(), isTrue, reason: "forwards movement valid");
+          expect(it.current, equals(10));
+        });
+
+        test("inserted midpoint, non-inclusive, works forward", () {
+          var it = tree.fromIterator(20, inclusive: false);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(21));
+        });
+
+        test("inserted endpoint, non-inclusive, works forward", () {
+          var it = tree.fromIterator(30, inclusive: false);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isFalse, reason: "moveNext() from spot works");
+
+          it = tree.fromIterator(10, inclusive: false);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(15),
+              reason: "non-inclusive start should be 15");
+        });
+
+        test("inserted endpoint, non-inclusive, works backward", () {
+          var it = tree.fromIterator(10, inclusive: false);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.movePrevious(), isFalse,
+              reason: "movePrevious() from spot is null");
+
+          it = tree.fromIterator(30, inclusive: false);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(
+              it.movePrevious(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(21));
+        });
+
+        test("inserted midpoint, non-inclusive, reversed, works forward", () {
+          var it = tree.fromIterator(20, inclusive: false, reversed: true);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(15));
+        });
+
+        test("inserted endpoint, non-inclusive, reversed, works forward", () {
+          var it = tree.fromIterator(30, inclusive: false, reversed: true);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(21));
+
+          it = tree.fromIterator(10, inclusive: false, reversed: true);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(it.moveNext(), isFalse, reason: "moveNext() works");
+        });
+
+        test("inserted endpoint, non-inclusive, reversed, works backward", () {
+          var it = tree.fromIterator(10, inclusive: false, reversed: true);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(
+              it.movePrevious(), isTrue, reason: "moveNext() from spot works");
+          expect(it.current, equals(15));
+
+          it = tree.fromIterator(30, inclusive: false, reversed: true);
+          expect(it.current, isNull, reason: "iteration starts with null");
+          expect(
+              it.movePrevious(), isFalse, reason: "moveNext() from spot works");
+        });
+      });
+
+      group("fails", () {
+        var it;
+        setUp(() => it = tree.iterator);
+
+        test("after tree is cleared", () {
+          tree.clear();
+          var error;
+          try {
+            it.moveNext();
+          } catch (e) {
+            error = e;
+          }
+          expect(error, isConcurrentModificationError);
+        });
+
+        test("after inserting an element", () {
+          tree.add(101);
+          var error;
+          try {
+            it.moveNext();
+          } catch (e) {
+            error = e;
+          }
+          expect(error, isConcurrentModificationError);
+        });
+
+        test("after removing an element", () {
+          tree.remove(10);
+          var error;
+          try {
+            it.moveNext();
+          } catch (e) {
+            error = e;
+          }
+          expect(error, isConcurrentModificationError);
+        });
+      });
+
+      group("still works", () {
+        var it;
+        setUp(() => it = tree.iterator);
+
+        test("when removing non-existing element", () {
+          tree.remove(42);
+          var error;
+          try {
+            it.moveNext();
+          } catch (e) {
+            error = e;
+          }
+          expect(error, isNull, reason: "set was not modified");
+        });
+        test("when adding an already existing element", () {
+          tree.add(10);
+          var error;
+          try {
+            it.moveNext();
+          } catch (e) {
+            error = e;
+          }
+          expect(error, isNull, reason: "set was not modified");
+        });
+      });
+    });
+
+    group("set math", () {
+      /// NOTE: set math with sorted sets should have a performance benifit,
+      /// we do not check the performance, only that the resulting math
+      /// is equivilant to non-sorted sets.
+
+      TreeSet<num> tree;
+      List<num> expectedUnion;
+      List<num> expectedIntersection;
+      List<num> expectedDifference;
+      Set<num> nonSortedTestSet;
+      TreeSet<num> sortedTestSet;
+
+      setUp(() {
+        tree = new TreeSet()..addAll([10, 20, 15, 21, 30, 20]);
+        expectedUnion = [10, 15, 18, 20, 21, 22, 30];
+        expectedIntersection = [10, 15];
+        expectedDifference = [20, 21, 30];
+        nonSortedTestSet = new Set.from([10, 18, 22, 15]);
+        sortedTestSet = new TreeSet()..addAll(nonSortedTestSet);
+      });
+
+      test("union with non sorted set", () =>
+          expect(tree.union(nonSortedTestSet).toList(), equals(expectedUnion)));
+      test("union with sorted set", () =>
+          expect(tree.union(sortedTestSet).toList(), equals(expectedUnion)));
+      test("intersection with non sorted set", () => expect(
+          tree.intersection(nonSortedTestSet).toList(),
+          equals(expectedIntersection)));
+      test("intersection with sorted set", () => expect(
+          tree.intersection(sortedTestSet).toList(),
+          equals(expectedIntersection)));
+      test("difference with non sorted set", () => expect(
+          tree.difference(nonSortedTestSet).toList(),
+          equals(expectedDifference)));
+      test("difference with sorted set", () => expect(
+          tree.difference(sortedTestSet).toList(), equals(expectedDifference)));
+    });
+
+    group("AVL implementaiton", () {
+      /// NOTE: This is implementation specific testing for coverage.
+      /// Users do not have access to [AvlNode] or [AvlTreeSet]
+      test("RightLeftRotation", () {
+        AvlTreeSet<num> tree = new TreeSet<num>();
+        tree.add(10);
+        tree.add(20);
+        tree.add(15);
+
+        AvlNode ten = tree.getNode(10);
+        AvlNode twenty = tree.getNode(20);
+        AvlNode fifteen = tree.getNode(15);
+
+        expect(ten.parent, equals(fifteen));
+        expect(ten.left, equals(null));
+        expect(ten.right, equals(null));
+        expect(ten.balance, equals(0));
+
+        expect(twenty.parent, equals(fifteen));
+        expect(twenty.left, equals(null));
+        expect(twenty.right, equals(null));
+        expect(twenty.balance, equals(0));
+
+        expect(fifteen.parent, equals(null));
+        expect(fifteen.left, equals(ten));
+        expect(fifteen.right, equals(twenty));
+        expect(fifteen.balance, equals(0));
+      });
+      test("LeftRightRotation", () {
+        AvlTreeSet<num> tree = new TreeSet<num>();
+        tree.add(30);
+        tree.add(10);
+        tree.add(20);
+
+        AvlNode thirty = tree.getNode(30);
+        AvlNode ten = tree.getNode(10);
+        AvlNode twenty = tree.getNode(20);
+
+        expect(thirty.parent, equals(twenty));
+        expect(thirty.left, equals(null));
+        expect(thirty.right, equals(null));
+        expect(thirty.balance, equals(0));
+
+        expect(ten.parent, equals(twenty));
+        expect(ten.left, equals(null));
+        expect(ten.right, equals(null));
+        expect(ten.balance, equals(0));
+
+        expect(twenty.parent, equals(null));
+        expect(twenty.left, equals(ten));
+        expect(twenty.right, equals(thirty));
+        expect(twenty.balance, equals(0));
+      });
+
+      test("AVL-LeftRotation", () {
+        AvlTreeSet<num> tree = new TreeSet<num>();
+        tree.add(1);
+        tree.add(2);
+        tree.add(3);
+
+        AvlNode one = tree.getNode(1);
+        AvlNode two = tree.getNode(2);
+        AvlNode three = tree.getNode(3);
+
+        expect(one.parent, equals(two));
+        expect(one.left, equals(null));
+        expect(one.right, equals(null));
+        expect(one.balance, equals(0));
+
+        expect(three.parent, equals(two));
+        expect(three.left, equals(null));
+        expect(three.right, equals(null));
+        expect(three.balance, equals(0));
+
+        expect(two.parent, equals(null));
+        expect(two.left, equals(one));
+        expect(two.right, equals(three));
+        expect(two.balance, equals(0));
+      });
+
+      test("AVL-RightRotation", () {
+        AvlTreeSet<num> tree = new TreeSet<num>();
+        tree.add(3);
+        tree.add(2);
+        tree.add(1);
+
+        AvlNode one = tree.getNode(1);
+        AvlNode two = tree.getNode(2);
+        AvlNode three = tree.getNode(3);
+
+        expect(one.parent, equals(two));
+        expect(one.left, equals(null));
+        expect(one.right, equals(null));
+        expect(one.balance, equals(0));
+
+        expect(three.parent, equals(two));
+        expect(three.left, equals(null));
+        expect(three.right, equals(null));
+        expect(three.balance, equals(0));
+
+        expect(two.parent, equals(null));
+        expect(two.left, equals(one));
+        expect(two.right, equals(three));
+        expect(two.balance, equals(0));
+      });
+    });
+
+    group("nearest search", () {
+      TreeSet<num> tree;
+      setUp(() {
+        tree = new TreeSet<num>(comparator: (num left, num right) {
+          return left - right;
+        })..addAll([300, 200, 100]);
+      });
+
+      test("NEAREST is sane", () {
+        var val = tree.nearest(199);
+        expect(val, equals(200), reason: "199 is closer to 200");
+        val = tree.nearest(201);
+        expect(val, equals(200), reason: "201 is 200");
+        val = tree.nearest(150);
+        expect(val, equals(100), reason: "150 defaults to lower 100");
+      });
+
+      test("LESS_THAN is sane", () {
+        var val = tree.nearest(199, nearestOption: TreeSearch.LESS_THAN);
+        expect(val, equals(100), reason: "199 rounds down to 100");
+      });
+
+      test("GREATER_THAN is sane", () {
+        var val = tree.nearest(101, nearestOption: TreeSearch.GREATER_THAN);
+        expect(val, equals(200), reason: "101 rounds up to 200");
+      });
+    });
+  });
+}