ViewVC Help

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

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

Comparing jsr166/src/test/tck/TreeMapTest.java (file contents):
Revision 1.2 by dl, Tue Mar 22 01:30:22 2005 UTC vs.
Revision 1.3 by dl, Wed Apr 19 15:10:54 2006 UTC

#	Line 230 | Line 230 | public class TreeMapTest extends JSR166T
230		*/
231		public void testDescendingEntrySet() {
232		TreeMap map = map5();
233	<	Set s = map.descendingEntrySet();
233	>	Set s = map.descendingMap().entrySet();
234		assertEquals(5, s.size());
235		Iterator it = s.iterator();
236		while (it.hasNext()) {
#	Line 263 | Line 263 | public class TreeMapTest extends JSR166T
263		*/
264		public void testDescendingEntrySetToArray() {
265		TreeMap map = map5();
266	<	Set s = map.descendingEntrySet();
266	>	Set s = map.descendingMap().entrySet();
267		Object[] ar = s.toArray();
268		assertEquals(5, ar.length);
269		for (int i = 0; i < 5; ++i) {
#	Line 592 | Line 592 | public class TreeMapTest extends JSR166T
592		*/
593		public void testSubMapContents() {
594		TreeMap map = map5();
595	<	NavigableMap sm = map.navigableSubMap(two, four);
595	>	NavigableMap sm = map.navigableSubMap(two, true, four, false);
596		assertEquals(two, sm.firstKey());
597		assertEquals(three, sm.lastKey());
598		assertEquals(2, sm.size());
#	Line 630 | Line 630 | public class TreeMapTest extends JSR166T
630
631		public void testSubMapContents2() {
632		TreeMap map = map5();
633	<	NavigableMap sm = map.navigableSubMap(two, three);
633	>	NavigableMap sm = map.navigableSubMap(two, true, three, false);
634		assertEquals(1, sm.size());
635		assertEquals(two, sm.firstKey());
636		assertEquals(two, sm.lastKey());
#	Line 665 | Line 665 | public class TreeMapTest extends JSR166T
665		*/
666		public void testHeadMapContents() {
667		TreeMap map = map5();
668	<	NavigableMap sm = map.navigableHeadMap(four);
668	>	NavigableMap sm = map.navigableHeadMap(four, false);
669		assertTrue(sm.containsKey(one));
670		assertTrue(sm.containsKey(two));
671		assertTrue(sm.containsKey(three));
#	Line 691 | Line 691 | public class TreeMapTest extends JSR166T
691		*/
692		public void testTailMapContents() {
693		TreeMap map = map5();
694	<	NavigableMap sm = map.navigableTailMap(two);
694	>	NavigableMap sm = map.navigableTailMap(two, true);
695		assertFalse(sm.containsKey(one));
696		assertTrue(sm.containsKey(two));
697		assertTrue(sm.containsKey(three));
#	Line 735 | Line 735 | public class TreeMapTest extends JSR166T
735		assertEquals("E", e.getValue());
736		assertFalse(i.hasNext());
737
738	<	NavigableMap ssm = sm.navigableTailMap(four);
738	>	NavigableMap ssm = sm.navigableTailMap(four, true);
739		assertEquals(four, ssm.firstKey());
740		assertEquals(five, ssm.lastKey());
741		assertTrue(ssm.remove(four) != null);
#	Line 743 | Line 743 | public class TreeMapTest extends JSR166T
743		assertEquals(3, sm.size());
744		assertEquals(4, map.size());
745		}
746	+
747	+	Random rnd = new Random(666);
748	+	BitSet bs;
749	+
750	+	/**
751	+	* Submaps of submaps subdivide correctly
752	+	*/
753	+	public void testRecursiveSubMaps() {
754	+	int mapSize = 1000;
755	+	Class cl = TreeMap.class;
756	+	NavigableMap<Integer, Integer> map = newMap(cl);
757	+	bs = new BitSet(mapSize);
758	+
759	+	populate(map, mapSize);
760	+	check(map,                 0, mapSize - 1, true);
761	+	check(map.descendingMap(), 0, mapSize - 1, false);
762	+
763	+	mutateMap(map, 0, mapSize - 1);
764	+	check(map,                 0, mapSize - 1, true);
765	+	check(map.descendingMap(), 0, mapSize - 1, false);
766	+
767	+	bashSubMap(map.navigableSubMap(0, true, mapSize, false),
768	+	0, mapSize - 1, true);
769	+	}
770	+
771	+	static NavigableMap<Integer, Integer> newMap(Class cl) {
772	+	NavigableMap<Integer, Integer> result = null;
773	+	try {
774	+	result = (NavigableMap<Integer, Integer>) cl.newInstance();
775	+	} catch(Exception e) {
776	+	fail();
777	+	}
778	+	assertEquals(result.size(), 0);
779	+	assertFalse(result.keySet().iterator().hasNext());
780	+	return result;
781	+	}
782	+
783	+	void populate(NavigableMap<Integer, Integer> map, int limit) {
784	+	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
785	+	int key = rnd.nextInt(limit);
786	+	put(map, key);
787	+	}
788	+	}
789	+
790	+	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
791	+	int size = map.size();
792	+	int rangeSize = max - min + 1;
793	+
794	+	// Remove a bunch of entries directly
795	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
796	+	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
797	+	}
798	+
799	+	// Remove a bunch of entries with iterator
800	+	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
801	+	if (rnd.nextBoolean()) {
802	+	bs.clear(it.next());
803	+	it.remove();
804	+	}
805	+	}
806	+
807	+	// Add entries till we're back to original size
808	+	while (map.size() < size) {
809	+	int key = min + rnd.nextInt(rangeSize);
810	+	assertTrue(key >= min && key<= max);
811	+	put(map, key);
812	+	}
813	+	}
814	+
815	+	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
816	+	int size = map.size();
817	+	int rangeSize = max - min + 1;
818	+
819	+	// Remove a bunch of entries directly
820	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
821	+	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
822	+	}
823	+
824	+	// Remove a bunch of entries with iterator
825	+	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
826	+	if (rnd.nextBoolean()) {
827	+	bs.clear(it.next());
828	+	it.remove();
829	+	}
830	+	}
831	+
832	+	// Add entries till we're back to original size
833	+	while (map.size() < size) {
834	+	int key = min - 5 + rnd.nextInt(rangeSize + 10);
835	+	if (key >= min && key<= max) {
836	+	put(map, key);
837	+	} else {
838	+	try {
839	+	map.put(key, 2 * key);
840	+	fail();
841	+	} catch(IllegalArgumentException e) {
842	+	// expected
843	+	}
844	+	}
845	+	}
846	+	}
847	+
848	+	void put(NavigableMap<Integer, Integer> map, int key) {
849	+	if (map.put(key, 2 * key) == null)
850	+	bs.set(key);
851	+	}
852	+
853	+	void remove(NavigableMap<Integer, Integer> map, int key) {
854	+	if (map.remove(key) != null)
855	+	bs.clear(key);
856	+	}
857	+
858	+	void bashSubMap(NavigableMap<Integer, Integer> map,
859	+	int min, int max, boolean ascending) {
860	+	check(map, min, max, ascending);
861	+	check(map.descendingMap(), min, max, !ascending);
862	+
863	+	mutateSubMap(map, min, max);
864	+	check(map, min, max, ascending);
865	+	check(map.descendingMap(), min, max, !ascending);
866	+
867	+	// Recurse
868	+	if (max - min < 2)
869	+	return;
870	+	int midPoint = (min + max) / 2;
871	+
872	+	// headMap - pick direction and endpoint inclusion randomly
873	+	boolean incl = rnd.nextBoolean();
874	+	NavigableMap<Integer,Integer> hm = map.navigableHeadMap(midPoint, incl);
875	+	if (ascending) {
876	+	if (rnd.nextBoolean())
877	+	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
878	+	else
879	+	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
880	+	false);
881	+	} else {
882	+	if (rnd.nextBoolean())
883	+	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
884	+	else
885	+	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
886	+	true);
887	+	}
888	+
889	+	// tailMap - pick direction and endpoint inclusion randomly
890	+	incl = rnd.nextBoolean();
891	+	NavigableMap<Integer,Integer> tm = map.navigableTailMap(midPoint,incl);
892	+	if (ascending) {
893	+	if (rnd.nextBoolean())
894	+	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
895	+	else
896	+	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
897	+	false);
898	+	} else {
899	+	if (rnd.nextBoolean()) {
900	+	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
901	+	} else {
902	+	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
903	+	true);
904	+	}
905	+	}
906	+
907	+	// subMap - pick direction and endpoint inclusion randomly
908	+	int rangeSize = max - min + 1;
909	+	int[] endpoints = new int[2];
910	+	endpoints[0] = min + rnd.nextInt(rangeSize);
911	+	endpoints[1] = min + rnd.nextInt(rangeSize);
912	+	Arrays.sort(endpoints);
913	+	boolean lowIncl = rnd.nextBoolean();
914	+	boolean highIncl = rnd.nextBoolean();
915	+	if (ascending) {
916	+	NavigableMap<Integer,Integer> sm = map.navigableSubMap(
917	+	endpoints[0], lowIncl, endpoints[1], highIncl);
918	+	if (rnd.nextBoolean())
919	+	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
920	+	endpoints[1] - (highIncl ? 0 : 1), true);
921	+	else
922	+	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
923	+	endpoints[1] - (highIncl ? 0 : 1), false);
924	+	} else {
925	+	NavigableMap<Integer,Integer> sm = map.navigableSubMap(
926	+	endpoints[1], highIncl, endpoints[0], lowIncl);
927	+	if (rnd.nextBoolean())
928	+	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
929	+	endpoints[1] - (highIncl ? 0 : 1), false);
930	+	else
931	+	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
932	+	endpoints[1] - (highIncl ? 0 : 1), true);
933	+	}
934	+	}
935	+
936	+	/**
937	+	* min and max are both inclusive.  If max < min, interval is empty.
938	+	*/
939	+	void check(NavigableMap<Integer, Integer> map,
940	+	final int min, final int max, final boolean ascending) {
941	+	class ReferenceSet {
942	+	int lower(int key) {
943	+	return ascending ? lowerAscending(key) : higherAscending(key);
944	+	}
945	+	int floor(int key) {
946	+	return ascending ? floorAscending(key) : ceilingAscending(key);
947	+	}
948	+	int ceiling(int key) {
949	+	return ascending ? ceilingAscending(key) : floorAscending(key);
950	+	}
951	+	int higher(int key) {
952	+	return ascending ? higherAscending(key) : lowerAscending(key);
953	+	}
954	+	int first() {
955	+	return ascending ? firstAscending() : lastAscending();
956	+	}
957	+	int last() {
958	+	return ascending ? lastAscending() : firstAscending();
959	+	}
960	+	int lowerAscending(int key) {
961	+	return floorAscending(key - 1);
962	+	}
963	+	int floorAscending(int key) {
964	+	if (key < min)
965	+	return -1;
966	+	else if (key > max)
967	+	key = max;
968	+
969	+	// BitSet should support this! Test would run much faster
970	+	while (key >= min) {
971	+	if (bs.get(key))
972	+	return(key);
973	+	key--;
974	+	}
975	+	return -1;
976	+	}
977	+	int ceilingAscending(int key) {
978	+	if (key < min)
979	+	key = min;
980	+	else if (key > max)
981	+	return -1;
982	+	int result = bs.nextSetBit(key);
983	+	return result > max ? -1 : result;
984	+	}
985	+	int higherAscending(int key) {
986	+	return ceilingAscending(key + 1);
987	+	}
988	+	private int firstAscending() {
989	+	int result = ceilingAscending(min);
990	+	return result > max ? -1 : result;
991	+	}
992	+	private int lastAscending() {
993	+	int result = floorAscending(max);
994	+	return result < min ? -1 : result;
995	+	}
996	+	}
997	+	ReferenceSet rs = new ReferenceSet();
998	+
999	+	// Test contents using containsKey
1000	+	int size = 0;
1001	+	for (int i = min; i <= max; i++) {
1002	+	boolean bsContainsI = bs.get(i);
1003	+	assertEquals(bsContainsI, map.containsKey(i));
1004	+	if (bsContainsI)
1005	+	size++;
1006	+	}
1007	+	assertEquals(map.size(), size);
1008	+
1009	+	// Test contents using contains keySet iterator
1010	+	int size2 = 0;
1011	+	int previousKey = -1;
1012	+	for (int key : map.keySet()) {
1013	+	assertTrue(bs.get(key));
1014	+	size2++;
1015	+	assertTrue(previousKey < 0 ||
1016	+	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1017	+	previousKey = key;
1018	+	}
1019	+	assertEquals(size2, size);
1020	+
1021	+	// Test navigation ops
1022	+	for (int key = min - 1; key <= max + 1; key++) {
1023	+	assertEq(map.lowerKey(key), rs.lower(key));
1024	+	assertEq(map.floorKey(key), rs.floor(key));
1025	+	assertEq(map.higherKey(key), rs.higher(key));
1026	+	assertEq(map.ceilingKey(key), rs.ceiling(key));
1027	+	}
1028	+
1029	+	// Test extrema
1030	+	if (map.size() != 0) {
1031	+	assertEq(map.firstKey(), rs.first());
1032	+	assertEq(map.lastKey(), rs.last());
1033	+	} else {
1034	+	assertEq(rs.first(), -1);
1035	+	assertEq(rs.last(),  -1);
1036	+	try {
1037	+	map.firstKey();
1038	+	fail();
1039	+	} catch(NoSuchElementException e) {
1040	+	// expected
1041	+	}
1042	+	try {
1043	+	map.lastKey();
1044	+	fail();
1045	+	} catch(NoSuchElementException e) {
1046	+	// expected
1047	+	}
1048	+	}
1049	+	}
1050	+
1051	+	static void assertEq(Integer i, int j) {
1052	+	if (i == null)
1053	+	assertEquals(j, -1);
1054	+	else
1055	+	assertEquals((int) i, j);
1056	+	}
1057	+
1058	+	static boolean eq(Integer i, int j) {
1059	+	return i == null ? j == -1 : i == j;
1060	+	}
1061
1062		}

Diff Legend

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