ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/tck/TreeSetTest.java

Comparing jsr166/src/test/tck/TreeSetTest.java (file contents):
Revision 1.1 by dl, Tue Dec 28 16:15:59 2004 UTC vs.
Revision 1.2 by dl, Wed Apr 19 15:10:54 2006 UTC

#	Line 684 | Line 684 | public class TreeSetTest extends JSR166T
684		assertEquals(4, set.size());
685		}
686
687	+	Random rnd = new Random(666);
688	+	BitSet bs;
689	+
690	+	/**
691	+	* Subsets of subsets subdivide correctly
692	+	*/
693	+	public void testRecursiveSubSets() {
694	+	int setSize = 1000;
695	+	Class cl = TreeSet.class;
696	+
697	+	NavigableSet<Integer> set = newSet(cl);
698	+	bs = new BitSet(setSize);
699	+
700	+	populate(set, setSize);
701	+	check(set,                 0, setSize - 1, true);
702	+	check(set.descendingSet(), 0, setSize - 1, false);
703	+
704	+	mutateSet(set, 0, setSize - 1);
705	+	check(set,                 0, setSize - 1, true);
706	+	check(set.descendingSet(), 0, setSize - 1, false);
707	+
708	+	bashSubSet(set.navigableSubSet(0, true, setSize, false),
709	+	0, setSize - 1, true);
710	+	}
711	+
712	+	static NavigableSet<Integer> newSet(Class cl) {
713	+	NavigableSet<Integer> result = null;
714	+	try {
715	+	result = (NavigableSet<Integer>) cl.newInstance();
716	+	} catch(Exception e) {
717	+	fail();
718	+	}
719	+	assertEquals(result.size(), 0);
720	+	assertFalse(result.iterator().hasNext());
721	+	return result;
722	+	}
723	+
724	+	void populate(NavigableSet<Integer> set, int limit) {
725	+	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
726	+	int element = rnd.nextInt(limit);
727	+	put(set, element);
728	+	}
729	+	}
730	+
731	+	void mutateSet(NavigableSet<Integer> set, int min, int max) {
732	+	int size = set.size();
733	+	int rangeSize = max - min + 1;
734	+
735	+	// Remove a bunch of entries directly
736	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
737	+	remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
738	+	}
739	+
740	+	// Remove a bunch of entries with iterator
741	+	for(Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
742	+	if (rnd.nextBoolean()) {
743	+	bs.clear(it.next());
744	+	it.remove();
745	+	}
746	+	}
747	+
748	+	// Add entries till we're back to original size
749	+	while (set.size() < size) {
750	+	int element = min + rnd.nextInt(rangeSize);
751	+	assertTrue(element >= min && element<= max);
752	+	put(set, element);
753	+	}
754	+	}
755	+
756	+	void mutateSubSet(NavigableSet<Integer> set, int min, int max) {
757	+	int size = set.size();
758	+	int rangeSize = max - min + 1;
759	+
760	+	// Remove a bunch of entries directly
761	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
762	+	remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
763	+	}
764	+
765	+	// Remove a bunch of entries with iterator
766	+	for(Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
767	+	if (rnd.nextBoolean()) {
768	+	bs.clear(it.next());
769	+	it.remove();
770	+	}
771	+	}
772	+
773	+	// Add entries till we're back to original size
774	+	while (set.size() < size) {
775	+	int element = min - 5 + rnd.nextInt(rangeSize + 10);
776	+	if (element >= min && element<= max) {
777	+	put(set, element);
778	+	} else {
779	+	try {
780	+	set.add(element);
781	+	fail();
782	+	} catch(IllegalArgumentException e) {
783	+	// expected
784	+	}
785	+	}
786	+	}
787	+	}
788	+
789	+	void put(NavigableSet<Integer> set, int element) {
790	+	if (set.add(element))
791	+	bs.set(element);
792	+	}
793	+
794	+	void remove(NavigableSet<Integer> set, int element) {
795	+	if (set.remove(element))
796	+	bs.clear(element);
797	+	}
798	+
799	+	void bashSubSet(NavigableSet<Integer> set,
800	+	int min, int max, boolean ascending) {
801	+	check(set, min, max, ascending);
802	+	check(set.descendingSet(), min, max, !ascending);
803	+
804	+	mutateSubSet(set, min, max);
805	+	check(set, min, max, ascending);
806	+	check(set.descendingSet(), min, max, !ascending);
807	+
808	+	// Recurse
809	+	if (max - min < 2)
810	+	return;
811	+	int midPoint = (min + max) / 2;
812	+
813	+	// headSet - pick direction and endpoint inclusion randomly
814	+	boolean incl = rnd.nextBoolean();
815	+	NavigableSet<Integer> hm = set.navigableHeadSet(midPoint, incl);
816	+	if (ascending) {
817	+	if (rnd.nextBoolean())
818	+	bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true);
819	+	else
820	+	bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),
821	+	false);
822	+	} else {
823	+	if (rnd.nextBoolean())
824	+	bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false);
825	+	else
826	+	bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,
827	+	true);
828	+	}
829	+
830	+	// tailSet - pick direction and endpoint inclusion randomly
831	+	incl = rnd.nextBoolean();
832	+	NavigableSet<Integer> tm = set.navigableTailSet(midPoint,incl);
833	+	if (ascending) {
834	+	if (rnd.nextBoolean())
835	+	bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true);
836	+	else
837	+	bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,
838	+	false);
839	+	} else {
840	+	if (rnd.nextBoolean()) {
841	+	bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false);
842	+	} else {
843	+	bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),
844	+	true);
845	+	}
846	+	}
847	+
848	+	// subSet - pick direction and endpoint inclusion randomly
849	+	int rangeSize = max - min + 1;
850	+	int[] endpoints = new int[2];
851	+	endpoints[0] = min + rnd.nextInt(rangeSize);
852	+	endpoints[1] = min + rnd.nextInt(rangeSize);
853	+	Arrays.sort(endpoints);
854	+	boolean lowIncl = rnd.nextBoolean();
855	+	boolean highIncl = rnd.nextBoolean();
856	+	if (ascending) {
857	+	NavigableSet<Integer> sm = set.navigableSubSet(
858	+	endpoints[0], lowIncl, endpoints[1], highIncl);
859	+	if (rnd.nextBoolean())
860	+	bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
861	+	endpoints[1] - (highIncl ? 0 : 1), true);
862	+	else
863	+	bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
864	+	endpoints[1] - (highIncl ? 0 : 1), false);
865	+	} else {
866	+	NavigableSet<Integer> sm = set.navigableSubSet(
867	+	endpoints[1], highIncl, endpoints[0], lowIncl);
868	+	if (rnd.nextBoolean())
869	+	bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
870	+	endpoints[1] - (highIncl ? 0 : 1), false);
871	+	else
872	+	bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
873	+	endpoints[1] - (highIncl ? 0 : 1), true);
874	+	}
875	+	}
876	+
877	+	/**
878	+	* min and max are both inclusive.  If max < min, interval is empty.
879	+	*/
880	+	void check(NavigableSet<Integer> set,
881	+	final int min, final int max, final boolean ascending) {
882	+	class ReferenceSet {
883	+	int lower(int element) {
884	+	return ascending ?
885	+	lowerAscending(element) : higherAscending(element);
886	+	}
887	+	int floor(int element) {
888	+	return ascending ?
889	+	floorAscending(element) : ceilingAscending(element);
890	+	}
891	+	int ceiling(int element) {
892	+	return ascending ?
893	+	ceilingAscending(element) : floorAscending(element);
894	+	}
895	+	int higher(int element) {
896	+	return ascending ?
897	+	higherAscending(element) : lowerAscending(element);
898	+	}
899	+	int first() {
900	+	return ascending ? firstAscending() : lastAscending();
901	+	}
902	+	int last() {
903	+	return ascending ? lastAscending() : firstAscending();
904	+	}
905	+	int lowerAscending(int element) {
906	+	return floorAscending(element - 1);
907	+	}
908	+	int floorAscending(int element) {
909	+	if (element < min)
910	+	return -1;
911	+	else if (element > max)
912	+	element = max;
913	+
914	+	// BitSet should support this! Test would run much faster
915	+	while (element >= min) {
916	+	if (bs.get(element))
917	+	return(element);
918	+	element--;
919	+	}
920	+	return -1;
921	+	}
922	+	int ceilingAscending(int element) {
923	+	if (element < min)
924	+	element = min;
925	+	else if (element > max)
926	+	return -1;
927	+	int result = bs.nextSetBit(element);
928	+	return result > max ? -1 : result;
929	+	}
930	+	int higherAscending(int element) {
931	+	return ceilingAscending(element + 1);
932	+	}
933	+	private int firstAscending() {
934	+	int result = ceilingAscending(min);
935	+	return result > max ? -1 : result;
936	+	}
937	+	private int lastAscending() {
938	+	int result = floorAscending(max);
939	+	return result < min ? -1 : result;
940	+	}
941	+	}
942	+	ReferenceSet rs = new ReferenceSet();
943	+
944	+	// Test contents using containsElement
945	+	int size = 0;
946	+	for (int i = min; i <= max; i++) {
947	+	boolean bsContainsI = bs.get(i);
948	+	assertEquals(bsContainsI, set.contains(i));
949	+	if (bsContainsI)
950	+	size++;
951	+	}
952	+	assertEquals(set.size(), size);
953	+
954	+	// Test contents using contains elementSet iterator
955	+	int size2 = 0;
956	+	int previousElement = -1;
957	+	for (int element : set) {
958	+	assertTrue(bs.get(element));
959	+	size2++;
960	+	assertTrue(previousElement < 0 || (ascending ?
961	+	element - previousElement > 0 : element - previousElement < 0));
962	+	previousElement = element;
963	+	}
964	+	assertEquals(size2, size);
965	+
966	+	// Test navigation ops
967	+	for (int element = min - 1; element <= max + 1; element++) {
968	+	assertEq(set.lower(element), rs.lower(element));
969	+	assertEq(set.floor(element), rs.floor(element));
970	+	assertEq(set.higher(element), rs.higher(element));
971	+	assertEq(set.ceiling(element), rs.ceiling(element));
972	+	}
973	+
974	+	// Test extrema
975	+	if (set.size() != 0) {
976	+	assertEq(set.first(), rs.first());
977	+	assertEq(set.last(), rs.last());
978	+	} else {
979	+	assertEq(rs.first(), -1);
980	+	assertEq(rs.last(),  -1);
981	+	try {
982	+	set.first();
983	+	fail();
984	+	} catch(NoSuchElementException e) {
985	+	// expected
986	+	}
987	+	try {
988	+	set.last();
989	+	fail();
990	+	} catch(NoSuchElementException e) {
991	+	// expected
992	+	}
993	+	}
994	+	}
995	+
996	+	static void assertEq(Integer i, int j) {
997	+	if (i == null)
998	+	assertEquals(j, -1);
999	+	else
1000	+	assertEquals((int) i, j);
1001	+	}
1002	+
1003	+	static boolean eq(Integer i, int j) {
1004	+	return i == null ? j == -1 : i == j;
1005	+	}
1006	+
1007		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines