void InsertAndLookup() {

			class re_integer implements Comparable<re_integer> {
				int val;

				public re_integer(int v) {
					val = v;
				}

				@Override
				public int compareTo(re_integer arg0) {
					return arg0.val - val;
				}

			}
			int N = 2000;
			int R = 5000;
			Random rnd = new Random();
			// baseline
			SortedSet<Integer> keys = new TreeSet<Integer>();
			SortedSet<re_integer> keys_reverse = new TreeSet<re_integer>();
			TestComparator cmp = new TestComparator();
			SkipList<Integer, TestComparator> list = new SkipList<Integer, SkipList.TestComparator>(
					cmp);
			for (int i = 0; i < N; i++) {
				int key = rnd.nextInt() % R;
				if (keys.add(key)) {
					keys_reverse.add(new re_integer(key));
					// System.out.println(key);
					list.Insert(key);
				}
			}

			for (int i = 0; i < R; i++) {
				if (list.Contains(i)) {
					ASSERT_TRUE(keys.contains(i));
				} else {
					ASSERT_TRUE(!keys.contains(i));
				}
			}

			// Simple iterator tests
			{
				SkipListIterator<Integer, TestComparator> iter = new SkipListIterator<Integer, SkipList.TestComparator>(
						list);
				ASSERT_TRUE(!iter.Valid());

				iter.Seek(Integer.MIN_VALUE);// different from cpp, 'cause java
												// doesnot support uint64
				ASSERT_TRUE(iter.Valid());
				ASSERT_EQ(keys.first(), iter.key());

				iter.SeekToFirst();
				ASSERT_TRUE(iter.Valid());
				ASSERT_EQ(keys.first(), iter.key());

				iter.SeekToLast();
				ASSERT_TRUE(iter.Valid());
				ASSERT_EQ(keys.last(), iter.key());
			}

			// Forward iteration test
			for (int i = 0; i < R; i++) {
				SkipListIterator<Integer, TestComparator> iter = new SkipListIterator<Integer, SkipList.TestComparator>(
						list);
				iter.Seek(i);

				// Compare against model iterator
				// std::set<Key>::iterator model_iter = keys.lower_bound(i);
				SortedSet<Integer> model_ = keys.tailSet(i);
				Iterator<Integer> model_iter = model_.iterator();
				for (int j = 0; j < 3; j++) {
					if (!model_iter.hasNext()) {
						ASSERT_TRUE(!iter.Valid());
						break;
					} else {
						ASSERT_TRUE(iter.Valid());
						ASSERT_EQ(model_iter.next(), iter.key());
						iter.Next();
					}
				}
			}

			// Backward iteration test
			{
				SkipListIterator<Integer, TestComparator> iter = new SkipListIterator<Integer, SkipList.TestComparator>(
						list);
				iter.SeekToLast();

				// Compare against model iterator
				Iterator<re_integer> model_iter = keys_reverse.iterator();
				for (; model_iter.hasNext();) {
					ASSERT_TRUE(iter.Valid());
					ASSERT_EQ(model_iter.next().val, iter.key());
					iter.Prev();
				}
				ASSERT_TRUE(!iter.Valid());
			}

		}