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.5 by dl, Sat Apr 19 18:45:18 2008 UTC

#	Line 169 | Line 169 | public class TreeMapTest extends JSR166T
169		Iterator i = s.iterator();
170		Integer last = (Integer)i.next();
171		assertEquals(last, one);
172	+	int count = 1;
173		while (i.hasNext()) {
174		Integer k = (Integer)i.next();
175		assertTrue(last.compareTo(k) < 0);
176		last = k;
177	+	++count;
178		}
179	+	assertEquals(count ,5);
180	+	}
181	+
182	+	/**
183	+	* descending iterator of key set is inverse ordered
184	+	*/
185	+	public void testKeySetDescendingIteratorOrder() {
186	+	TreeMap map = map5();
187	+	NavigableSet s = map.navigableKeySet();
188	+	Iterator i = s.descendingIterator();
189	+	Integer last = (Integer)i.next();
190	+	assertEquals(last, five);
191	+	int count = 1;
192	+	while (i.hasNext()) {
193	+	Integer k = (Integer)i.next();
194	+	assertTrue(last.compareTo(k) > 0);
195	+	last = k;
196	+	++count;
197	+	}
198	+	assertEquals(count ,5);
199		}
200
201		/**
#	Line 185 | Line 207 | public class TreeMapTest extends JSR166T
207		Iterator i = s.iterator();
208		Integer last = (Integer)i.next();
209		assertEquals(last, five);
210	+	int count = 1;
211		while (i.hasNext()) {
212		Integer k = (Integer)i.next();
213		assertTrue(last.compareTo(k) > 0);
214		last = k;
215	+	++count;
216	+	}
217	+	assertEquals(count, 5);
218	+	}
219	+
220	+	/**
221	+	*  descending iterator of descendingKeySet is ordered
222	+	*/
223	+	public void testDescendingKeySetDescendingIteratorOrder() {
224	+	TreeMap map = map5();
225	+	NavigableSet s = map.descendingKeySet();
226	+	Iterator i = s.descendingIterator();
227	+	Integer last = (Integer)i.next();
228	+	assertEquals(last, one);
229	+	int count = 1;
230	+	while (i.hasNext()) {
231	+	Integer k = (Integer)i.next();
232	+	assertTrue(last.compareTo(k) < 0);
233	+	last = k;
234	+	++count;
235		}
236	+	assertEquals(count, 5);
237		}
238
239		/**
#	Line 230 | Line 274 | public class TreeMapTest extends JSR166T
274		*/
275		public void testDescendingEntrySet() {
276		TreeMap map = map5();
277	<	Set s = map.descendingEntrySet();
277	>	Set s = map.descendingMap().entrySet();
278		assertEquals(5, s.size());
279		Iterator it = s.iterator();
280		while (it.hasNext()) {
#	Line 263 | Line 307 | public class TreeMapTest extends JSR166T
307		*/
308		public void testDescendingEntrySetToArray() {
309		TreeMap map = map5();
310	<	Set s = map.descendingEntrySet();
310	>	Set s = map.descendingMap().entrySet();
311		Object[] ar = s.toArray();
312		assertEquals(5, ar.length);
313		for (int i = 0; i < 5; ++i) {
#	Line 592 | Line 636 | public class TreeMapTest extends JSR166T
636		*/
637		public void testSubMapContents() {
638		TreeMap map = map5();
639	<	NavigableMap sm = map.navigableSubMap(two, four);
639	>	NavigableMap sm = map.subMap(two, true, four, false);
640		assertEquals(two, sm.firstKey());
641		assertEquals(three, sm.lastKey());
642		assertEquals(2, sm.size());
#	Line 630 | Line 674 | public class TreeMapTest extends JSR166T
674
675		public void testSubMapContents2() {
676		TreeMap map = map5();
677	<	NavigableMap sm = map.navigableSubMap(two, three);
677	>	NavigableMap sm = map.subMap(two, true, three, false);
678		assertEquals(1, sm.size());
679		assertEquals(two, sm.firstKey());
680		assertEquals(two, sm.lastKey());
#	Line 665 | Line 709 | public class TreeMapTest extends JSR166T
709		*/
710		public void testHeadMapContents() {
711		TreeMap map = map5();
712	<	NavigableMap sm = map.navigableHeadMap(four);
712	>	NavigableMap sm = map.headMap(four, false);
713		assertTrue(sm.containsKey(one));
714		assertTrue(sm.containsKey(two));
715		assertTrue(sm.containsKey(three));
#	Line 691 | Line 735 | public class TreeMapTest extends JSR166T
735		*/
736		public void testTailMapContents() {
737		TreeMap map = map5();
738	<	NavigableMap sm = map.navigableTailMap(two);
738	>	NavigableMap sm = map.tailMap(two, true);
739		assertFalse(sm.containsKey(one));
740		assertTrue(sm.containsKey(two));
741		assertTrue(sm.containsKey(three));
#	Line 735 | Line 779 | public class TreeMapTest extends JSR166T
779		assertEquals("E", e.getValue());
780		assertFalse(i.hasNext());
781
782	<	NavigableMap ssm = sm.navigableTailMap(four);
782	>	NavigableMap ssm = sm.tailMap(four, true);
783		assertEquals(four, ssm.firstKey());
784		assertEquals(five, ssm.lastKey());
785		assertTrue(ssm.remove(four) != null);
#	Line 743 | Line 787 | public class TreeMapTest extends JSR166T
787		assertEquals(3, sm.size());
788		assertEquals(4, map.size());
789		}
790	+
791	+	Random rnd = new Random(666);
792	+	BitSet bs;
793	+
794	+	/**
795	+	* Submaps of submaps subdivide correctly
796	+	*/
797	+	public void testRecursiveSubMaps() {
798	+	int mapSize = 1000;
799	+	Class cl = TreeMap.class;
800	+	NavigableMap<Integer, Integer> map = newMap(cl);
801	+	bs = new BitSet(mapSize);
802	+
803	+	populate(map, mapSize);
804	+	check(map,                 0, mapSize - 1, true);
805	+	check(map.descendingMap(), 0, mapSize - 1, false);
806	+
807	+	mutateMap(map, 0, mapSize - 1);
808	+	check(map,                 0, mapSize - 1, true);
809	+	check(map.descendingMap(), 0, mapSize - 1, false);
810	+
811	+	bashSubMap(map.subMap(0, true, mapSize, false),
812	+	0, mapSize - 1, true);
813	+	}
814	+
815	+	static NavigableMap<Integer, Integer> newMap(Class cl) {
816	+	NavigableMap<Integer, Integer> result = null;
817	+	try {
818	+	result = (NavigableMap<Integer, Integer>) cl.newInstance();
819	+	} catch(Exception e) {
820	+	fail();
821	+	}
822	+	assertEquals(result.size(), 0);
823	+	assertFalse(result.keySet().iterator().hasNext());
824	+	return result;
825	+	}
826	+
827	+	void populate(NavigableMap<Integer, Integer> map, int limit) {
828	+	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
829	+	int key = rnd.nextInt(limit);
830	+	put(map, key);
831	+	}
832	+	}
833	+
834	+	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
835	+	int size = map.size();
836	+	int rangeSize = max - min + 1;
837	+
838	+	// Remove a bunch of entries directly
839	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
840	+	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
841	+	}
842	+
843	+	// Remove a bunch of entries with iterator
844	+	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
845	+	if (rnd.nextBoolean()) {
846	+	bs.clear(it.next());
847	+	it.remove();
848	+	}
849	+	}
850	+
851	+	// Add entries till we're back to original size
852	+	while (map.size() < size) {
853	+	int key = min + rnd.nextInt(rangeSize);
854	+	assertTrue(key >= min && key<= max);
855	+	put(map, key);
856	+	}
857	+	}
858	+
859	+	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
860	+	int size = map.size();
861	+	int rangeSize = max - min + 1;
862	+
863	+	// Remove a bunch of entries directly
864	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
865	+	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
866	+	}
867	+
868	+	// Remove a bunch of entries with iterator
869	+	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
870	+	if (rnd.nextBoolean()) {
871	+	bs.clear(it.next());
872	+	it.remove();
873	+	}
874	+	}
875	+
876	+	// Add entries till we're back to original size
877	+	while (map.size() < size) {
878	+	int key = min - 5 + rnd.nextInt(rangeSize + 10);
879	+	if (key >= min && key<= max) {
880	+	put(map, key);
881	+	} else {
882	+	try {
883	+	map.put(key, 2 * key);
884	+	fail();
885	+	} catch(IllegalArgumentException e) {
886	+	// expected
887	+	}
888	+	}
889	+	}
890	+	}
891	+
892	+	void put(NavigableMap<Integer, Integer> map, int key) {
893	+	if (map.put(key, 2 * key) == null)
894	+	bs.set(key);
895	+	}
896	+
897	+	void remove(NavigableMap<Integer, Integer> map, int key) {
898	+	if (map.remove(key) != null)
899	+	bs.clear(key);
900	+	}
901	+
902	+	void bashSubMap(NavigableMap<Integer, Integer> map,
903	+	int min, int max, boolean ascending) {
904	+	check(map, min, max, ascending);
905	+	check(map.descendingMap(), min, max, !ascending);
906	+
907	+	mutateSubMap(map, min, max);
908	+	check(map, min, max, ascending);
909	+	check(map.descendingMap(), min, max, !ascending);
910	+
911	+	// Recurse
912	+	if (max - min < 2)
913	+	return;
914	+	int midPoint = (min + max) / 2;
915	+
916	+	// headMap - pick direction and endpoint inclusion randomly
917	+	boolean incl = rnd.nextBoolean();
918	+	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
919	+	if (ascending) {
920	+	if (rnd.nextBoolean())
921	+	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
922	+	else
923	+	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
924	+	false);
925	+	} else {
926	+	if (rnd.nextBoolean())
927	+	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
928	+	else
929	+	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
930	+	true);
931	+	}
932	+
933	+	// tailMap - pick direction and endpoint inclusion randomly
934	+	incl = rnd.nextBoolean();
935	+	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
936	+	if (ascending) {
937	+	if (rnd.nextBoolean())
938	+	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
939	+	else
940	+	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
941	+	false);
942	+	} else {
943	+	if (rnd.nextBoolean()) {
944	+	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
945	+	} else {
946	+	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
947	+	true);
948	+	}
949	+	}
950	+
951	+	// subMap - pick direction and endpoint inclusion randomly
952	+	int rangeSize = max - min + 1;
953	+	int[] endpoints = new int[2];
954	+	endpoints[0] = min + rnd.nextInt(rangeSize);
955	+	endpoints[1] = min + rnd.nextInt(rangeSize);
956	+	Arrays.sort(endpoints);
957	+	boolean lowIncl = rnd.nextBoolean();
958	+	boolean highIncl = rnd.nextBoolean();
959	+	if (ascending) {
960	+	NavigableMap<Integer,Integer> sm = map.subMap(
961	+	endpoints[0], lowIncl, endpoints[1], highIncl);
962	+	if (rnd.nextBoolean())
963	+	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
964	+	endpoints[1] - (highIncl ? 0 : 1), true);
965	+	else
966	+	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
967	+	endpoints[1] - (highIncl ? 0 : 1), false);
968	+	} else {
969	+	NavigableMap<Integer,Integer> sm = map.subMap(
970	+	endpoints[1], highIncl, endpoints[0], lowIncl);
971	+	if (rnd.nextBoolean())
972	+	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
973	+	endpoints[1] - (highIncl ? 0 : 1), false);
974	+	else
975	+	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
976	+	endpoints[1] - (highIncl ? 0 : 1), true);
977	+	}
978	+	}
979	+
980	+	/**
981	+	* min and max are both inclusive.  If max < min, interval is empty.
982	+	*/
983	+	void check(NavigableMap<Integer, Integer> map,
984	+	final int min, final int max, final boolean ascending) {
985	+	class ReferenceSet {
986	+	int lower(int key) {
987	+	return ascending ? lowerAscending(key) : higherAscending(key);
988	+	}
989	+	int floor(int key) {
990	+	return ascending ? floorAscending(key) : ceilingAscending(key);
991	+	}
992	+	int ceiling(int key) {
993	+	return ascending ? ceilingAscending(key) : floorAscending(key);
994	+	}
995	+	int higher(int key) {
996	+	return ascending ? higherAscending(key) : lowerAscending(key);
997	+	}
998	+	int first() {
999	+	return ascending ? firstAscending() : lastAscending();
1000	+	}
1001	+	int last() {
1002	+	return ascending ? lastAscending() : firstAscending();
1003	+	}
1004	+	int lowerAscending(int key) {
1005	+	return floorAscending(key - 1);
1006	+	}
1007	+	int floorAscending(int key) {
1008	+	if (key < min)
1009	+	return -1;
1010	+	else if (key > max)
1011	+	key = max;
1012	+
1013	+	// BitSet should support this! Test would run much faster
1014	+	while (key >= min) {
1015	+	if (bs.get(key))
1016	+	return(key);
1017	+	key--;
1018	+	}
1019	+	return -1;
1020	+	}
1021	+	int ceilingAscending(int key) {
1022	+	if (key < min)
1023	+	key = min;
1024	+	else if (key > max)
1025	+	return -1;
1026	+	int result = bs.nextSetBit(key);
1027	+	return result > max ? -1 : result;
1028	+	}
1029	+	int higherAscending(int key) {
1030	+	return ceilingAscending(key + 1);
1031	+	}
1032	+	private int firstAscending() {
1033	+	int result = ceilingAscending(min);
1034	+	return result > max ? -1 : result;
1035	+	}
1036	+	private int lastAscending() {
1037	+	int result = floorAscending(max);
1038	+	return result < min ? -1 : result;
1039	+	}
1040	+	}
1041	+	ReferenceSet rs = new ReferenceSet();
1042	+
1043	+	// Test contents using containsKey
1044	+	int size = 0;
1045	+	for (int i = min; i <= max; i++) {
1046	+	boolean bsContainsI = bs.get(i);
1047	+	assertEquals(bsContainsI, map.containsKey(i));
1048	+	if (bsContainsI)
1049	+	size++;
1050	+	}
1051	+	assertEquals(map.size(), size);
1052	+
1053	+	// Test contents using contains keySet iterator
1054	+	int size2 = 0;
1055	+	int previousKey = -1;
1056	+	for (int key : map.keySet()) {
1057	+	assertTrue(bs.get(key));
1058	+	size2++;
1059	+	assertTrue(previousKey < 0 ||
1060	+	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1061	+	previousKey = key;
1062	+	}
1063	+	assertEquals(size2, size);
1064	+
1065	+	// Test navigation ops
1066	+	for (int key = min - 1; key <= max + 1; key++) {
1067	+	assertEq(map.lowerKey(key), rs.lower(key));
1068	+	assertEq(map.floorKey(key), rs.floor(key));
1069	+	assertEq(map.higherKey(key), rs.higher(key));
1070	+	assertEq(map.ceilingKey(key), rs.ceiling(key));
1071	+	}
1072	+
1073	+	// Test extrema
1074	+	if (map.size() != 0) {
1075	+	assertEq(map.firstKey(), rs.first());
1076	+	assertEq(map.lastKey(), rs.last());
1077	+	} else {
1078	+	assertEq(rs.first(), -1);
1079	+	assertEq(rs.last(),  -1);
1080	+	try {
1081	+	map.firstKey();
1082	+	fail();
1083	+	} catch(NoSuchElementException e) {
1084	+	// expected
1085	+	}
1086	+	try {
1087	+	map.lastKey();
1088	+	fail();
1089	+	} catch(NoSuchElementException e) {
1090	+	// expected
1091	+	}
1092	+	}
1093	+	}
1094	+
1095	+	static void assertEq(Integer i, int j) {
1096	+	if (i == null)
1097	+	assertEquals(j, -1);
1098	+	else
1099	+	assertEquals((int) i, j);
1100	+	}
1101	+
1102	+	static boolean eq(Integer i, int j) {
1103	+	return i == null ? j == -1 : i == j;
1104	+	}
1105
1106		}

Diff Legend

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