ViewVC Help

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

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

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

Diff Legend

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