KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > poi > util > TestBinaryTree


1
2 /* ====================================================================
3    Copyright 2002-2004 Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16 ==================================================================== */

17         
18
19 package org.apache.poi.util;
20
21 import junit.framework.*;
22
23 import java.util.*;
24
25 /**
26  * Class TestBinaryTree
27  *
28  * @author Marc Johnson (mjohnson at apache dot org)
29  */

30
31 public class TestBinaryTree
32     extends TestCase
33 {
34
35     /**
36      * constructor
37      *
38      * @param name
39      */

40
41     public TestBinaryTree(final String JavaDoc name)
42     {
43         super(name);
44     }
45
46     /**
47      * test size() method
48      */

49
50     public void testSize()
51     {
52         Map m = new BinaryTree();
53
54         assertEquals(0, m.size());
55         LocalTestNode nodes[] = makeLocalNodes();
56
57         for (int k = 0; k < nodes.length; k++)
58         {
59             m.put(nodes[ k ].getKey(), nodes[ k ].getValue());
60             assertEquals(k + 1, m.size());
61         }
62         int count = m.size();
63
64         for (int k = 0; k < nodes.length; k++)
65         {
66             m.remove(nodes[ k ].getKey());
67             --count;
68             assertEquals(count, m.size());
69
70             // failed remove should not affect size
71
m.remove(nodes[ k ].getKey());
72             assertEquals(count, m.size());
73         }
74     }
75
76     /**
77      * test IsEmpty() method
78      */

79
80     public void testIsEmpty()
81     {
82         Map m = new BinaryTree();
83
84         assertTrue(m.isEmpty());
85         LocalTestNode nodes[] = makeLocalNodes();
86
87         for (int k = 0; k < nodes.length; k++)
88         {
89             m.put(nodes[ k ].getKey(), nodes[ k ].getValue());
90             assertTrue(!m.isEmpty());
91         }
92         int count = m.size();
93
94         for (int k = 0; k < nodes.length; k++)
95         {
96             m.remove(nodes[ k ].getKey());
97             --count;
98             if (count == 0)
99             {
100                 assertTrue(m.isEmpty());
101             }
102             else
103             {
104                 assertTrue(!m.isEmpty());
105             }
106
107             // failed remove should not affect emptiness
108
m.remove(nodes[ k ].getKey());
109             if (count == 0)
110             {
111                 assertTrue(m.isEmpty());
112             }
113             else
114             {
115                 assertTrue(!m.isEmpty());
116             }
117         }
118     }
119
120     /**
121      * test containsKey() method
122      */

123
124     public void testContainsKey()
125     {
126         Map m = new BinaryTree();
127
128         try
129         {
130             m.containsKey(new Object JavaDoc());
131             fail("should have caught ClassCastException");
132         }
133         catch (ClassCastException JavaDoc ignored)
134         {
135         }
136         try
137         {
138             m.containsKey(null);
139             fail("should have caught NullPointerException");
140         }
141         catch (NullPointerException JavaDoc ignored)
142         {
143         }
144         assertTrue(!m.containsKey("foo"));
145         LocalTestNode nodes[] = makeLocalNodes();
146
147         for (int k = 0; k < nodes.length; k++)
148         {
149             m.put(nodes[ k ].getKey(), nodes[ k ]);
150             assertTrue(m.containsKey(nodes[ k ].getKey()));
151         }
152         assertTrue(!m.containsKey(new Integer JavaDoc(-1)));
153         try
154         {
155             m.containsKey("foo");
156             fail("Should have caught ClassCastException");
157         }
158         catch (ClassCastException JavaDoc ignored)
159         {
160         }
161         for (int k = 0; k < nodes.length; k++)
162         {
163             m.remove(nodes[ k ].getKey());
164             assertTrue(!m.containsKey(nodes[ k ].getKey()));
165         }
166     }
167
168     /**
169      * test containsValue() method
170      */

171
172     public void testContainsValue()
173     {
174         Map m = new BinaryTree();
175         LocalTestNode nodes[] = makeLocalNodes();
176
177         for (int k = 0; k < nodes.length; k++)
178         {
179             m.put(nodes[ k ].getKey(), nodes[ k ]);
180             assertTrue(m.containsValue(nodes[ k ]));
181         }
182         for (int k = 0; k < nodes.length; k++)
183         {
184             m.remove(nodes[ k ].getKey());
185             assertTrue(!m.containsValue(nodes[ k ]));
186         }
187     }
188
189     /**
190      * test get() method
191      */

192
193     public void testGet()
194     {
195         Map m = new BinaryTree();
196
197         try
198         {
199             m.get(new Object JavaDoc());
200             fail("should have caught ClassCastException");
201         }
202         catch (ClassCastException JavaDoc ignored)
203         {
204         }
205         try
206         {
207             m.get(null);
208             fail("should have caught NullPointerException");
209         }
210         catch (NullPointerException JavaDoc ignored)
211         {
212         }
213         assertNull(m.get("foo"));
214         LocalTestNode nodes[] = makeLocalNodes();
215
216         for (int k = 0; k < nodes.length; k++)
217         {
218             m.put(nodes[ k ].getKey(), nodes[ k ]);
219             assertSame(m.get(nodes[ k ].getKey()), nodes[ k ]);
220         }
221         assertNull(m.get(new Integer JavaDoc(-1)));
222         try
223         {
224             m.get("foo");
225             fail("Should have caught ClassCastException");
226         }
227         catch (ClassCastException JavaDoc ignored)
228         {
229         }
230         for (int k = 0; k < nodes.length; k++)
231         {
232             assertNotNull(m.get(nodes[ k ].getKey()));
233             m.remove(nodes[ k ].getKey());
234             assertNull(m.get(nodes[ k ].getKey()));
235         }
236     }
237
238     /**
239      * test put() method
240      */

241
242     public void testPut()
243     {
244         Map m = new BinaryTree();
245
246         try
247         {
248             m.put(new Object JavaDoc(), "foo");
249             fail("should have caught ClassCastException");
250         }
251         catch (ClassCastException JavaDoc ignored)
252         {
253         }
254         try
255         {
256             m.put(null, "foo");
257             fail("should have caught NullPointerException");
258         }
259         catch (NullPointerException JavaDoc ignored)
260         {
261         }
262         try
263         {
264             m.put("foo", null);
265             fail("should have caught NullPointerException");
266         }
267         catch (NullPointerException JavaDoc ignored)
268         {
269         }
270         try
271         {
272             m.put("foo", new Object JavaDoc());
273             fail("should have caught ClassCastException");
274         }
275         catch (ClassCastException JavaDoc ignored)
276         {
277         }
278         LocalTestNode[] nodes = makeLocalNodes();
279
280         for (int k = 0; k < nodes.length; k++)
281         {
282             assertNull(m.put(nodes[ k ].getKey(), nodes[ k ].getValue()));
283             try
284             {
285                 m.put(nodes[ k ].getKey(), "foo");
286             }
287             catch (IllegalArgumentException JavaDoc ignored)
288             {
289             }
290         }
291     }
292
293     /**
294      * test remove() method
295      */

296
297     public void testRemove()
298     {
299         BinaryTree m = new BinaryTree();
300         LocalTestNode nodes[] = makeLocalNodes();
301
302         for (int k = 0; k < nodes.length; k++)
303         {
304             m.put(nodes[ k ].getKey(), nodes[ k ]);
305         }
306         try
307         {
308             m.remove(null);
309             fail("should have caught NullPointerException");
310         }
311         catch (NullPointerException JavaDoc ignored)
312         {
313         }
314         try
315         {
316             m.remove(new Object JavaDoc());
317             fail("should have caught ClassCastException");
318         }
319         catch (ClassCastException JavaDoc ignored)
320         {
321         }
322         assertNull(m.remove(new Integer JavaDoc(-1)));
323         try
324         {
325             m.remove("foo");
326             fail("should have caught ClassCastException");
327         }
328         catch (ClassCastException JavaDoc ignored)
329         {
330         }
331         for (int k = 0; k < nodes.length; k += 2)
332         {
333             Comparable JavaDoc key = nodes[ k ].getKey();
334
335             assertNotNull(m.get(key));
336             assertSame(nodes[ k ], m.remove(key));
337             assertNull(m.remove(key));
338             assertNull(m.get(key));
339         }
340         for (int k = 1; k < nodes.length; k += 2)
341         {
342             Comparable JavaDoc key = nodes[ k ].getKey();
343
344             assertNotNull(m.get(key));
345             assertSame(nodes[ k ], m.remove(key));
346             assertNull(m.remove(key));
347             assertNull(m.get(key));
348         }
349         assertTrue(m.isEmpty());
350     }
351
352     /**
353      * Method testPutAll
354      */

355
356     public void testPutAll()
357     {
358         Map m = new BinaryTree();
359         LocalTestNode nodes[] = makeLocalNodes();
360
361         for (int k = 0; k < nodes.length; k++)
362         {
363             m.put(nodes[ k ].getKey(), nodes[ k ]);
364         }
365         Map m1 = new HashMap();
366
367         m1.put(null, "foo");
368         try
369         {
370             m.putAll(m1);
371             fail("Should have caught NullPointerException");
372         }
373         catch (NullPointerException JavaDoc ignored)
374         {
375         }
376         m1 = new HashMap();
377         m1.put(new Object JavaDoc(), "bar");
378         try
379         {
380             m.putAll(m1);
381             fail("Should have caught ClassCastException");
382         }
383         catch (ClassCastException JavaDoc ignored)
384         {
385         }
386         m1 = new HashMap();
387         m1.put("fubar", null);
388         try
389         {
390             m.putAll(m1);
391             fail("Should have caught NullPointerException");
392         }
393         catch (NullPointerException JavaDoc ignored)
394         {
395         }
396         m1 = new HashMap();
397         m1.put("fubar", new Object JavaDoc());
398         try
399         {
400             m.putAll(m1);
401             fail("Should have caught ClassCastException");
402         }
403         catch (ClassCastException JavaDoc ignored)
404         {
405         }
406         assertEquals(nodes.length, m.size());
407         m = new BinaryTree();
408         m1 = new HashMap();
409         for (int k = 0; k < nodes.length; k++)
410         {
411             m1.put(nodes[ k ].getKey(), nodes[ k ].getValue());
412         }
413         m.putAll(m1);
414         assertEquals(nodes.length, m.size());
415         for (int k = 0; k < nodes.length; k++)
416         {
417             assertSame(nodes[ k ].getValue(), m.get(nodes[ k ].getKey()));
418         }
419     }
420
421     /**
422      * test clear() method
423      */

424
425     public void testClear()
426     {
427         Map m = new BinaryTree();
428         LocalTestNode nodes[] = makeLocalNodes();
429
430         for (int k = 0; k < nodes.length; k++)
431         {
432             m.put(nodes[ k ].getKey(), nodes[ k ].getValue());
433             assertTrue(!m.isEmpty());
434         }
435         assertTrue(!m.isEmpty());
436         for (int k = 0; k < nodes.length; k++)
437         {
438             assertTrue(m.containsKey(nodes[ k ].getKey()));
439             assertTrue(m.containsValue(nodes[ k ].getValue()));
440         }
441         m.clear();
442         assertTrue(m.isEmpty());
443         for (int k = 0; k < nodes.length; k++)
444         {
445             assertTrue(!m.containsKey(nodes[ k ].getKey()));
446             assertTrue(!m.containsValue(nodes[ k ].getValue()));
447         }
448     }
449
450     /**
451      * test keySet() method
452      */

453
454     public void testKeySet()
455     {
456         testKeySet(new BinaryTree());
457         Map m = new BinaryTree();
458         LocalTestNode nodes[] = makeLocalNodes();
459
460         for (int k = 0; k < nodes.length; k++)
461         {
462             m.put(nodes[ k ].getKey(), nodes[ k ]);
463         }
464         testKeySet(m);
465         m = new BinaryTree();
466         for (int k = 0; k < nodes.length; k++)
467         {
468             m.put(nodes[ k ].getKey(), nodes[ k ]);
469         }
470         int count = m.size();
471
472         for (Iterator iter = m.keySet().iterator(); iter.hasNext(); )
473         {
474             iter.next();
475             iter.remove();
476             --count;
477             assertEquals(count, m.size());
478         }
479         assertTrue(m.isEmpty());
480         m = new BinaryTree();
481         for (int k = 0; k < nodes.length; k++)
482         {
483             m.put(nodes[ k ].getKey(), nodes[ k ]);
484         }
485         Set s = m.keySet();
486
487         try
488         {
489             s.remove(null);
490             fail("should have caught NullPointerException");
491         }
492         catch (NullPointerException JavaDoc ignored)
493         {
494         }
495         try
496         {
497             s.remove(new Object JavaDoc());
498             fail("should have caught ClassCastException");
499         }
500         catch (ClassCastException JavaDoc ignored)
501         {
502         }
503         for (int k = 0; k < nodes.length; k++)
504         {
505             Comparable JavaDoc key = nodes[ k ].getKey();
506
507             assertTrue(s.remove(key));
508             assertTrue(!s.contains(key));
509             assertTrue(!m.containsKey(key));
510             assertTrue(!m.containsValue(nodes[ k ]));
511         }
512         assertTrue(m.isEmpty());
513         m = new BinaryTree();
514         Collection c1 = new LinkedList();
515         Collection c2 = new LinkedList();
516
517         c2.add(new Integer JavaDoc(-99));
518         for (int k = 0; k < nodes.length; k++)
519         {
520             m.put(nodes[ k ].getKey(), nodes[ k ]);
521             c1.add(nodes[ k ].getKey());
522             c2.add(nodes[ k ].getKey());
523         }
524         assertTrue(m.keySet().containsAll(c1));
525         assertTrue(!m.keySet().containsAll(c2));
526         m = new BinaryTree();
527         c1 = new LinkedList();
528         c1.add(new Integer JavaDoc(-55));
529         try
530         {
531             m.keySet().addAll(c1);
532             fail("should have caught exception of addAll()");
533         }
534         catch (UnsupportedOperationException JavaDoc ignored)
535         {
536         }
537         for (int k = 0; k < nodes.length; k++)
538         {
539             m.put(nodes[ k ].getKey(), nodes[ k ]);
540             c1.add(nodes[ k ].getKey());
541         }
542         assertTrue(!m.keySet().retainAll(c1));
543         assertEquals(nodes.length, m.size());
544         m = new BinaryTree();
545         c1 = new LinkedList();
546         for (int k = 0; k < nodes.length; k++)
547         {
548             m.put(nodes[ k ].getKey(), nodes[ k ]);
549             if (k % 2 == 1)
550             {
551                 c1.add(nodes[ k ].getKey());
552             }
553         }
554         assertTrue(m.keySet().retainAll(c1));
555         assertEquals(nodes.length / 2, m.size());
556         m = new BinaryTree();
557         c1 = new LinkedList();
558         for (int k = 0; k < nodes.length; k++)
559         {
560             m.put(nodes[ k ].getKey(), nodes[ k ]);
561         }
562         assertTrue(m.keySet().retainAll(c1));
563         assertEquals(0, m.size());
564         m = new BinaryTree();
565         c1 = new LinkedList();
566         for (int k = 0; k < nodes.length; k++)
567         {
568             m.put(nodes[ k ].getKey(), nodes[ k ]);
569         }
570         assertTrue(!m.keySet().removeAll(c1));
571         assertEquals(nodes.length, m.size());
572         m = new BinaryTree();
573         c1 = new LinkedList();
574         for (int k = 0; k < nodes.length; k++)
575         {
576             m.put(nodes[ k ].getKey(), nodes[ k ]);
577             if (k % 2 == 0)
578             {
579                 c1.add(nodes[ k ].getKey());
580             }
581         }
582         assertTrue(m.keySet().removeAll(c1));
583         assertEquals(nodes.length / 2, m.size());
584         m = new BinaryTree();
585         c1 = new LinkedList();
586         for (int k = 0; k < nodes.length; k++)
587         {
588             m.put(nodes[ k ].getKey(), nodes[ k ]);
589             c1.add(nodes[ k ].getKey());
590         }
591         assertTrue(m.keySet().removeAll(c1));
592         assertTrue(m.size() == 0);
593         m = new BinaryTree();
594         for (int k = 0; k < nodes.length; k++)
595         {
596             m.put(nodes[ k ].getKey(), nodes[ k ]);
597         }
598         m.keySet().clear();
599         assertTrue(m.size() == 0);
600     }
601
602     /**
603      * test values() method
604      */

605
606     public void testValues()
607     {
608         testValues(new BinaryTree());
609         Map m = new BinaryTree();
610         LocalTestNode nodes[] = makeLocalNodes();
611
612         for (int k = 0; k < nodes.length; k++)
613         {
614             m.put(nodes[ k ].getKey(), nodes[ k ]);
615         }
616         testValues(m);
617         m = new BinaryTree();
618         for (int k = 0; k < nodes.length; k++)
619         {
620             m.put(nodes[ k ].getKey(), nodes[ k ]);
621         }
622         int count = m.size();
623
624         for (Iterator iter = m.values().iterator(); iter.hasNext(); )
625         {
626             iter.next();
627             iter.remove();
628             --count;
629             assertEquals(count, m.size());
630         }
631         assertTrue(m.isEmpty());
632         m = new BinaryTree();
633         for (int k = 0; k < nodes.length; k++)
634         {
635             m.put(nodes[ k ].getKey(), nodes[ k ]);
636         }
637         count = m.size();
638         Collection s = m.values();
639
640         for (int k = 0; k < count; k++)
641         {
642             assertTrue(s.remove(nodes[ k ]));
643             assertTrue(!s.contains(nodes[ k ]));
644             assertTrue(!m.containsKey(nodes[ k ].getKey()));
645             assertTrue(!m.containsValue(nodes[ k ]));
646         }
647         assertTrue(m.isEmpty());
648         m = new BinaryTree();
649         Collection c1 = new LinkedList();
650         Collection c2 = new LinkedList();
651
652         c2.add(new LocalTestNode(-123));
653         for (int k = 0; k < nodes.length; k++)
654         {
655             m.put(nodes[ k ].getKey(), nodes[ k ]);
656             c1.add(nodes[ k ]);
657             c2.add(nodes[ k ]);
658         }
659         assertTrue(m.values().containsAll(c1));
660         assertTrue(!m.values().containsAll(c2));
661         m = new BinaryTree();
662         c1 = new LinkedList();
663         for (int k = 0; k < nodes.length; k++)
664         {
665             m.put(nodes[ k ].getKey(), nodes[ k ]);
666             c1.add(nodes[ k ]);
667         }
668         try
669         {
670             m.values().addAll(c1);
671             fail("should have caught exception of addAll()");
672         }
673         catch (UnsupportedOperationException JavaDoc ignored)
674         {
675         }
676         m = new BinaryTree();
677         c1 = new LinkedList();
678         for (int k = 0; k < nodes.length; k++)
679         {
680             m.put(nodes[ k ].getKey(), nodes[ k ]);
681             c1.add(nodes[ k ]);
682         }
683         assertTrue(!m.values().retainAll(c1));
684         assertEquals(nodes.length, m.size());
685         m = new BinaryTree();
686         c1 = new LinkedList();
687         for (int k = 0; k < nodes.length; k++)
688         {
689             m.put(nodes[ k ].getKey(), nodes[ k ]);
690             if (k % 2 == 1)
691             {
692                 c1.add(nodes[ k ]);
693             }
694         }
695         assertTrue(m.values().retainAll(c1));
696         assertEquals(nodes.length / 2, m.size());
697         m = new BinaryTree();
698         c1 = new LinkedList();
699         for (int k = 0; k < nodes.length; k++)
700         {
701             m.put(nodes[ k ].getKey(), nodes[ k ]);
702         }
703         assertTrue(m.values().retainAll(c1));
704         assertEquals(0, m.size());
705         m = new BinaryTree();
706         c1 = new LinkedList();
707         for (int k = 0; k < nodes.length; k++)
708         {
709             m.put(nodes[ k ].getKey(), nodes[ k ]);
710         }
711         assertTrue(!m.values().removeAll(c1));
712         assertEquals(nodes.length, m.size());
713         m = new BinaryTree();
714         c1 = new LinkedList();
715         for (int k = 0; k < nodes.length; k++)
716         {
717             m.put(nodes[ k ].getKey(), nodes[ k ]);
718             if (k % 2 == 0)
719             {
720                 c1.add(nodes[ k ]);
721             }
722         }
723         assertTrue(m.values().removeAll(c1));
724         assertEquals(nodes.length / 2, m.size());
725         m = new BinaryTree();
726         c1 = new LinkedList();
727         for (int k = 0; k < nodes.length; k++)
728         {
729             m.put(nodes[ k ].getKey(), nodes[ k ]);
730             c1.add(nodes[ k ]);
731         }
732         assertTrue(m.values().removeAll(c1));
733         assertEquals(0, m.size());
734         m = new BinaryTree();
735         for (int k = 0; k < nodes.length; k++)
736         {
737             m.put(nodes[ k ].getKey(), nodes[ k ]);
738         }
739         m.values().clear();
740         assertEquals(0, m.size());
741     }
742
743     /**
744      * test entrySet() method
745      */

746
747     public void testEntrySet()
748     {
749         testEntrySet(new BinaryTree());
750         Map m = new BinaryTree();
751         LocalTestNode nodes[] = makeLocalNodes();
752
753         for (int k = 0; k < nodes.length; k++)
754         {
755             m.put(nodes[ k ].getKey(), nodes[ k ]);
756         }
757         testEntrySet(m);
758         m = new BinaryTree();
759         for (int k = 0; k < nodes.length; k++)
760         {
761             m.put(nodes[ k ].getKey(), nodes[ k ]);
762         }
763         try
764         {
765             (( Map.Entry ) m.entrySet().iterator().next())
766                 .setValue(new LocalTestNode(-1));
767             fail("Should have caught UnsupportedOperationException");
768         }
769         catch (UnsupportedOperationException JavaDoc ignored)
770         {
771         }
772         int count = m.size();
773
774         for (Iterator iter = m.entrySet().iterator(); iter.hasNext(); )
775         {
776             iter.next();
777             iter.remove();
778             --count;
779             assertEquals(count, m.size());
780         }
781         assertTrue(m.isEmpty());
782         m = new BinaryTree();
783         Collection c1 = new LinkedList();
784
785         for (int k = 0; k < nodes.length; k++)
786         {
787             m.put(nodes[ k ].getKey(), nodes[ k ]);
788             c1.add(nodes[ k ].getKey());
789         }
790         try
791         {
792             m.entrySet().addAll(c1);
793             fail("should have caught exception of addAll()");
794         }
795         catch (UnsupportedOperationException JavaDoc ignored)
796         {
797         }
798         m = new BinaryTree();
799         for (int k = 0; k < nodes.length; k++)
800         {
801             m.put(nodes[ k ].getKey(), nodes[ k ]);
802         }
803         m.entrySet().clear();
804         assertEquals(0, m.size());
805         m = new BinaryTree();
806         for (int k = 0; k < nodes.length; k++)
807         {
808             m.put(nodes[ k ].getKey(), nodes[ k ]);
809         }
810         int x = 0;
811
812         for (Iterator iter = m.entrySet().iterator(); iter.hasNext(); )
813         {
814             Map.Entry entry = ( Map.Entry ) iter.next();
815
816             assertSame(entry.getKey(), nodes[ x ].getKey());
817             assertSame(entry.getValue(), nodes[ x ]);
818             x++;
819         }
820     }
821
822     /**
823      * Method testEquals
824      */

825
826     public void testEquals()
827     {
828         Map m = new BinaryTree();
829         LocalTestNode nodes[] = makeLocalNodes();
830
831         for (int k = 0; k < nodes.length; k++)
832         {
833             m.put(nodes[ k ].getKey(), nodes[ k ]);
834         }
835         assertTrue(!m.equals(null));
836         assertEquals(m, m);
837         Map m1 = new HashMap();
838
839         for (int k = 0; k < nodes.length; k++)
840         {
841             m1.put(nodes[ k ].getKey(), nodes[ k ]);
842         }
843         assertEquals(m, m1);
844         m1 = new BinaryTree();
845         for (int k = 0; k < (nodes.length - 1); k++)
846         {
847             m1.put(nodes[ k ].getKey(), nodes[ k ]);
848         }
849         assertTrue(!m.equals(m1));
850         m1 = new BinaryTree();
851         for (int k = 0; k < nodes.length; k++)
852         {
853             m1.put(nodes[ k ].getKey(), nodes[ k ]);
854         }
855         LocalTestNode node1 = new LocalTestNode(-1000);
856
857         m1.put(node1.getKey(), node1);
858         assertTrue(!m.equals(m1));
859         m1 = new BinaryTree();
860         for (int k = 0; k < nodes.length; k++)
861         {
862             m1.put(nodes[ k ].getKey(), nodes[ nodes.length - (k + 1) ]);
863         }
864         assertTrue(!m.equals(m1));
865         m1 = new BinaryTree();
866         for (int k = nodes.length - 1; k >= 0; k--)
867         {
868             m1.put(nodes[ k ].getKey(), nodes[ k ]);
869         }
870         assertEquals(m, m1);
871     }
872
873     /**
874      * test hashCode() method
875      */

876
877     public void testHashCode()
878     {
879         Map m = new BinaryTree();
880         LocalTestNode nodes[] = makeLocalNodes();
881
882         for (int k = 0; k < nodes.length; k++)
883         {
884             m.put(nodes[ k ].getKey(), nodes[ k ]);
885         }
886         Map m1 = new BinaryTree();
887
888         for (int k = nodes.length - 1; k >= 0; k--)
889         {
890             m1.put(nodes[ k ].getKey(), nodes[ k ]);
891         }
892         assertTrue(m.hashCode() == m1.hashCode());
893     }
894
895     /**
896      * test constructors
897      */

898
899     public void testConstructors()
900     {
901         BinaryTree m = new BinaryTree();
902
903         assertTrue(m.isEmpty());
904         BinaryTree m1 = new BinaryTree(m);
905
906         assertTrue(m1.isEmpty());
907         m1 = new BinaryTree();
908         LocalTestNode nodes[] = makeLocalNodes();
909
910         for (int k = 0; k < nodes.length; k++)
911         {
912             m1.put(nodes[ k ].getKey(), nodes[ k ]);
913         }
914         m = new BinaryTree(m1);
915         assertEquals(m, m1);
916         Map m2 = new HashMap();
917
918         for (int k = 0; k < nodes.length; k++)
919         {
920             m2.put(nodes[ k ].getKey(), nodes[ k ]);
921         }
922         m = new BinaryTree(m2);
923         assertEquals(m, m2);
924
925         // reject duplicated values
926
m2 = new HashMap();
927         m2.put("1", "foo");
928         m2.put("2", "foo");
929         try
930         {
931             m = new BinaryTree(m2);
932             fail("Should have caught IllegalArgumentException");
933         }
934         catch (IllegalArgumentException JavaDoc ignored)
935         {
936         }
937
938         // reject null values
939
m2.put("2", null);
940         try
941         {
942             m = new BinaryTree(m2);
943             fail("Should have caught NullPointerException");
944         }
945         catch (NullPointerException JavaDoc ignored)
946         {
947         }
948
949         // reject non-Comparable values
950
m2.put("2", new Object JavaDoc());
951         try
952         {
953             m = new BinaryTree(m2);
954             fail("Should have caught ClassCastException");
955         }
956         catch (ClassCastException JavaDoc ignored)
957         {
958         }
959
960         // reject incompatible values
961
m2.put("2", new Integer JavaDoc(2));
962         try
963         {
964             m = new BinaryTree(m2);
965             fail("Should have caught ClassCastException");
966         }
967         catch (ClassCastException JavaDoc ignored)
968         {
969         }
970
971         // reject incompatible keys
972
m2.remove("2");
973         m2.put(new Integer JavaDoc(2), "bad key");
974         try
975         {
976             m = new BinaryTree(m2);
977             fail("Should have caught ClassCastException");
978         }
979         catch (ClassCastException JavaDoc ignored)
980         {
981         }
982
983         // reject non-Comparable keys
984
m2.clear();
985         m2.put("1", "foo");
986         m2.put(new Object JavaDoc(), "bad key");
987         try
988         {
989             m = new BinaryTree(m2);
990             fail("Should have caught ClassCastException");
991         }
992         catch (ClassCastException JavaDoc ignored)
993         {
994         }
995     }
996
997     /**
998      * test getKeyForValue() method
999      */

1000
1001    public void testGetKeyForValue()
1002    {
1003        BinaryTree m = new BinaryTree();
1004
1005        try
1006        {
1007            m.getKeyForValue(new Object JavaDoc());
1008            fail("should have caught ClassCastException");
1009        }
1010        catch (ClassCastException JavaDoc ignored)
1011        {
1012        }
1013        try
1014        {
1015            m.getKeyForValue(null);
1016            fail("should have caught NullPointerException");
1017        }
1018        catch (NullPointerException JavaDoc ignored)
1019        {
1020        }
1021        assertNull(m.getKeyForValue("foo"));
1022        LocalTestNode nodes[] = makeLocalNodes();
1023
1024        for (int k = 0; k < nodes.length; k++)
1025        {
1026            m.put(nodes[ k ].getKey(), nodes[ k ]);
1027            assertSame(m.getKeyForValue(nodes[ k ]), nodes[ k ].getKey());
1028        }
1029        assertNull(m.getKeyForValue(new LocalTestNode(-1)));
1030        try
1031        {
1032            m.getKeyForValue("foo");
1033            fail("Should have caught ClassCastException");
1034        }
1035        catch (ClassCastException JavaDoc ignored)
1036        {
1037        }
1038        for (int k = 0; k < nodes.length; k++)
1039        {
1040            assertNotNull(m.getKeyForValue(nodes[ k ]));
1041            m.remove(nodes[ k ].getKey());
1042            assertNull(m.getKeyForValue(nodes[ k ]));
1043        }
1044    }
1045
1046    /**
1047     * test removeValue() method
1048     */

1049
1050    public void testRemoveValue()
1051    {
1052        BinaryTree m = new BinaryTree();
1053        LocalTestNode nodes[] = makeLocalNodes();
1054
1055        for (int k = 0; k < nodes.length; k++)
1056        {
1057            m.put(nodes[ k ].getKey(), nodes[ k ]);
1058        }
1059        try
1060        {
1061            m.removeValue(null);
1062            fail("should have caught NullPointerException");
1063        }
1064        catch (NullPointerException JavaDoc ignored)
1065        {
1066        }
1067        try
1068        {
1069            m.removeValue(new Object JavaDoc());
1070            fail("should have caught ClassCastException");
1071        }
1072        catch (ClassCastException JavaDoc ignored)
1073        {
1074        }
1075        assertNull(m.remove(new Integer JavaDoc(-1)));
1076        try
1077        {
1078            m.removeValue("foo");
1079            fail("should have caught ClassCastException");
1080        }
1081        catch (ClassCastException JavaDoc ignored)
1082        {
1083        }
1084        for (int k = 0; k < nodes.length; k += 2)
1085        {
1086            assertNotNull(m.getKeyForValue(nodes[ k ]));
1087            assertSame(nodes[ k ].getKey(), m.removeValue(nodes[ k ]));
1088            assertNull(m.removeValue(nodes[ k ]));
1089            assertNull(m.getKeyForValue(nodes[ k ]));
1090        }
1091        for (int k = 1; k < nodes.length; k += 2)
1092        {
1093            assertNotNull(m.getKeyForValue(nodes[ k ]));
1094            assertSame(nodes[ k ].getKey(), m.removeValue(nodes[ k ]));
1095            assertNull(m.removeValue(nodes[ k ]));
1096            assertNull(m.getKeyForValue(nodes[ k ]));
1097        }
1098        assertTrue(m.isEmpty());
1099    }
1100
1101    /**
1102     * test entrySetByValue() method
1103     */

1104
1105    public void testEntrySetByValue()
1106    {
1107        testEntrySetByValue(new BinaryTree());
1108        BinaryTree m = new BinaryTree();
1109        LocalTestNode nodes[] = makeLocalNodes();
1110
1111        for (int k = 0; k < nodes.length; k++)
1112        {
1113            m.put(nodes[ k ].getKey(), nodes[ k ]);
1114        }
1115        testEntrySetByValue(m);
1116        m = new BinaryTree();
1117        for (int k = 0; k < nodes.length; k++)
1118        {
1119            m.put(nodes[ k ].getKey(), nodes[ k ]);
1120        }
1121        try
1122        {
1123            (( Map.Entry ) m.entrySetByValue().iterator().next())
1124                .setValue(new LocalTestNode(-1));
1125            fail("Should have caught UnsupportedOperationException");
1126        }
1127        catch (UnsupportedOperationException JavaDoc ignored)
1128        {
1129        }
1130        int count = m.size();
1131
1132        for (Iterator iter = m.entrySetByValue().iterator(); iter.hasNext(); )
1133        {
1134            iter.next();
1135            iter.remove();
1136            --count;
1137            assertEquals(count, m.size());
1138        }
1139        assertTrue(m.isEmpty());
1140        m = new BinaryTree();
1141        Collection c1 = new LinkedList();
1142
1143        for (int k = 0; k < nodes.length; k++)
1144        {
1145            m.put(nodes[ k ].getKey(), nodes[ k ]);
1146            c1.add(nodes[ k ].getKey());
1147        }
1148        try
1149        {
1150            m.entrySetByValue().addAll(c1);
1151            fail("should have caught exception of addAll()");
1152        }
1153        catch (UnsupportedOperationException JavaDoc ignored)
1154        {
1155        }
1156        m = new BinaryTree();
1157        for (int k = 0; k < nodes.length; k++)
1158        {
1159            m.put(nodes[ k ].getKey(), nodes[ k ]);
1160        }
1161        m.entrySetByValue().clear();
1162        assertEquals(0, m.size());
1163        m = new BinaryTree();
1164        for (int k = 0; k < nodes.length; k++)
1165        {
1166            m.put(nodes[ k ].getKey(), nodes[ k ]);
1167        }
1168        int x = 0;
1169
1170        for (Iterator iter = m.entrySetByValue().iterator(); iter.hasNext(); )
1171        {
1172            Map.Entry entry = ( Map.Entry ) iter.next();
1173
1174            assertSame(entry.getKey(), nodes[ x ].getKey());
1175            assertSame(entry.getValue(), nodes[ x ]);
1176            x++;
1177        }
1178    }
1179
1180    /**
1181     * test keySetByValue() method
1182     */

1183
1184    public void testKeySetByValue()
1185    {
1186        testKeySetByValue(new BinaryTree());
1187        BinaryTree m = new BinaryTree();
1188        LocalTestNode nodes[] = makeLocalNodes();
1189
1190        for (int k = 0; k < nodes.length; k++)
1191        {
1192            m.put(nodes[ k ].getKey(), nodes[ k ]);
1193        }
1194        testKeySetByValue(m);
1195        m = new BinaryTree();
1196        for (int k = 0; k < nodes.length; k++)
1197        {
1198            m.put(nodes[ k ].getKey(), nodes[ k ]);
1199        }
1200        int count = m.size();
1201
1202        for (Iterator iter = m.keySetByValue().iterator(); iter.hasNext(); )
1203        {
1204            iter.next();
1205            iter.remove();
1206            --count;
1207            assertEquals(count, m.size());
1208        }
1209        assertTrue(m.isEmpty());
1210        m = new BinaryTree();
1211        for (int k = 0; k < nodes.length; k++)
1212        {
1213            m.put(nodes[ k ].getKey(), nodes[ k ]);
1214        }
1215        Set s = m.keySetByValue();
1216
1217        try
1218        {
1219            s.remove(null);
1220            fail("should have caught NullPointerException");
1221        }
1222        catch (NullPointerException JavaDoc ignored)
1223        {
1224        }
1225        try
1226        {
1227            s.remove(new Object JavaDoc());
1228            fail("should have caught ClassCastException");
1229        }
1230        catch (ClassCastException JavaDoc ignored)
1231        {
1232        }
1233        for (int k = 0; k < nodes.length; k++)
1234        {
1235            Comparable JavaDoc key = nodes[ k ].getKey();
1236
1237            assertTrue(s.remove(key));
1238            assertTrue(!s.contains(key));
1239            assertTrue(!m.containsKey(key));
1240            assertTrue(!m.containsValue(nodes[ k ]));
1241        }
1242        assertTrue(m.isEmpty());
1243        m = new BinaryTree();
1244        Collection c1 = new LinkedList();
1245        Collection c2 = new LinkedList();
1246
1247        c2.add(new Integer JavaDoc(-99));
1248        for (int k = 0; k < nodes.length; k++)
1249        {
1250            m.put(nodes[ k ].getKey(), nodes[ k ]);
1251            c1.add(nodes[ k ].getKey());
1252            c2.add(nodes[ k ].getKey());
1253        }
1254        assertTrue(m.keySetByValue().containsAll(c1));
1255        assertTrue(!m.keySetByValue().containsAll(c2));
1256        m = new BinaryTree();
1257        c1 = new LinkedList();
1258        c1.add(new Integer JavaDoc(-55));
1259        try
1260        {
1261            m.keySetByValue().addAll(c1);
1262            fail("should have caught exception of addAll()");
1263        }
1264        catch (UnsupportedOperationException JavaDoc ignored)
1265        {
1266        }
1267        for (int k = 0; k < nodes.length; k++)
1268        {
1269            m.put(nodes[ k ].getKey(), nodes[ k ]);
1270            c1.add(nodes[ k ].getKey());
1271        }
1272        assertTrue(!m.keySetByValue().retainAll(c1));
1273        assertEquals(nodes.length, m.size());
1274        m = new BinaryTree();
1275        c1 = new LinkedList();
1276        for (int k = 0; k < nodes.length; k++)
1277        {
1278            m.put(nodes[ k ].getKey(), nodes[ k ]);
1279            if (k % 2 == 1)
1280            {
1281                c1.add(nodes[ k ].getKey());
1282            }
1283        }
1284        assertTrue(m.keySetByValue().retainAll(c1));
1285        assertEquals(nodes.length / 2, m.size());
1286        m = new BinaryTree();
1287        c1 = new LinkedList();
1288        for (int k = 0; k < nodes.length; k++)
1289        {
1290            m.put(nodes[ k ].getKey(), nodes[ k ]);
1291        }
1292        assertTrue(m.keySetByValue().retainAll(c1));
1293        assertEquals(0, m.size());
1294        m = new BinaryTree();
1295        c1 = new LinkedList();
1296        for (int k = 0; k < nodes.length; k++)
1297        {
1298            m.put(nodes[ k ].getKey(), nodes[ k ]);
1299        }
1300        assertTrue(!m.keySetByValue().removeAll(c1));
1301        assertEquals(nodes.length, m.size());
1302        m = new BinaryTree();
1303        c1 = new LinkedList();
1304        for (int k = 0; k < nodes.length; k++)
1305        {
1306            m.put(nodes[ k ].getKey(), nodes[ k ]);
1307            if (k % 2 == 0)
1308            {
1309                c1.add(nodes[ k ].getKey());
1310            }
1311        }
1312        assertTrue(m.keySetByValue().removeAll(c1));
1313        assertEquals(nodes.length / 2, m.size());
1314        m = new BinaryTree();
1315        c1 = new LinkedList();
1316        for (int k = 0; k < nodes.length; k++)
1317        {
1318            m.put(nodes[ k ].getKey(), nodes[ k ]);
1319            c1.add(nodes[ k ].getKey());
1320        }
1321        assertTrue(m.keySetByValue().removeAll(c1));
1322        assertTrue(m.size() == 0);
1323        m = new BinaryTree();
1324        for (int k = 0; k < nodes.length; k++)
1325        {
1326            m.put(nodes[ k ].getKey(), nodes[ k ]);
1327        }
1328        m.keySetByValue().clear();
1329        assertTrue(m.size() == 0);
1330    }
1331
1332    /**
1333     * test valuesByValue() method
1334     */

1335
1336    public void testValuesByValue()
1337    {
1338        testValuesByValue(new BinaryTree());
1339        BinaryTree m = new BinaryTree();
1340        LocalTestNode nodes[] = makeLocalNodes();
1341
1342        for (int k = 0; k < nodes.length; k++)
1343        {
1344            m.put(nodes[ k ].getKey(), nodes[ k ]);
1345        }
1346        testValuesByValue(m);
1347        m = new BinaryTree();
1348        for (int k = 0; k < nodes.length; k++)
1349        {
1350            m.put(nodes[ k ].getKey(), nodes[ k ]);
1351        }
1352        int count = m.size();
1353
1354        for (Iterator iter = m.valuesByValue().iterator(); iter.hasNext(); )
1355        {
1356            iter.next();
1357            iter.remove();
1358            --count;
1359            assertEquals(count, m.size());
1360        }
1361        assertTrue(m.isEmpty());
1362        m = new BinaryTree();
1363        for (int k = 0; k < nodes.length; k++)
1364        {
1365            m.put(nodes[ k ].getKey(), nodes[ k ]);
1366        }
1367        count = m.size();
1368        Collection s = m.valuesByValue();
1369
1370        for (int k = 0; k < count; k++)
1371        {
1372            assertTrue(s.remove(nodes[ k ]));
1373            assertTrue(!s.contains(nodes[ k ]));
1374            assertTrue(!m.containsKey(nodes[ k ].getKey()));
1375            assertTrue(!m.containsValue(nodes[ k ]));
1376        }
1377        assertTrue(m.isEmpty());
1378        m = new BinaryTree();
1379        Collection c1 = new LinkedList();
1380        Collection c2 = new LinkedList();
1381
1382        c2.add(new LocalTestNode(-123));
1383        for (int k = 0; k < nodes.length; k++)
1384        {
1385            m.put(nodes[ k ].getKey(), nodes[ k ]);
1386            c1.add(nodes[ k ]);
1387            c2.add(nodes[ k ]);
1388        }
1389        assertTrue(m.valuesByValue().containsAll(c1));
1390        assertTrue(!m.valuesByValue().containsAll(c2));
1391        m = new BinaryTree();
1392        c1 = new LinkedList();
1393        for (int k = 0; k < nodes.length; k++)
1394        {
1395            m.put(nodes[ k ].getKey(), nodes[ k ]);
1396            c1.add(nodes[ k ]);
1397        }
1398        try
1399        {
1400            m.valuesByValue().addAll(c1);
1401            fail("should have caught exception of addAll()");
1402        }
1403        catch (UnsupportedOperationException JavaDoc ignored)
1404        {
1405        }
1406        m = new BinaryTree();
1407        c1 = new LinkedList();
1408        for (int k = 0; k < nodes.length; k++)
1409        {
1410            m.put(nodes[ k ].getKey(), nodes[ k ]);
1411            c1.add(nodes[ k ]);
1412        }
1413        assertTrue(!m.valuesByValue().retainAll(c1));
1414        assertEquals(nodes.length, m.size());
1415        m = new BinaryTree();
1416        c1 = new LinkedList();
1417        for (int k = 0; k < nodes.length; k++)
1418        {
1419            m.put(nodes[ k ].getKey(), nodes[ k ]);
1420            if (k % 2 == 1)
1421            {
1422                c1.add(nodes[ k ]);
1423            }
1424        }
1425        assertTrue(m.valuesByValue().retainAll(c1));
1426        assertEquals(nodes.length / 2, m.size());
1427        m = new BinaryTree();
1428        c1 = new LinkedList();
1429        for (int k = 0; k < nodes.length; k++)
1430        {
1431            m.put(nodes[ k ].getKey(), nodes[ k ]);
1432        }
1433        assertTrue(m.valuesByValue().retainAll(c1));
1434        assertEquals(0, m.size());
1435        m = new BinaryTree();
1436        c1 = new LinkedList();
1437        for (int k = 0; k < nodes.length; k++)
1438        {
1439            m.put(nodes[ k ].getKey(), nodes[ k ]);
1440        }
1441        assertTrue(!m.valuesByValue().removeAll(c1));
1442        assertEquals(nodes.length, m.size());
1443        m = new BinaryTree();
1444        c1 = new LinkedList();
1445        for (int k = 0; k < nodes.length; k++)
1446        {
1447            m.put(nodes[ k ].getKey(), nodes[ k ]);
1448            if (k % 2 == 0)
1449            {
1450                c1.add(nodes[ k ]);
1451            }
1452        }
1453        assertTrue(m.valuesByValue().removeAll(c1));
1454        assertEquals(nodes.length / 2, m.size());
1455        m = new BinaryTree();
1456        c1 = new LinkedList();
1457        for (int k = 0; k < nodes.length; k++)
1458        {
1459            m.put(nodes[ k ].getKey(), nodes[ k ]);
1460            c1.add(nodes[ k ]);
1461        }
1462        assertTrue(m.valuesByValue().removeAll(c1));
1463        assertEquals(0, m.size());
1464        m = new BinaryTree();
1465        for (int k = 0; k < nodes.length; k++)
1466        {
1467            m.put(nodes[ k ].getKey(), nodes[ k ]);
1468        }
1469        m.valuesByValue().clear();
1470        assertEquals(0, m.size());
1471    }
1472
1473    /* ********** START helper methods ********** */
1474    private void testKeySet(final Map m)
1475    {
1476        Set s = m.keySet();
1477
1478        assertEquals(m.size(), s.size());
1479        assertEquals(m.isEmpty(), s.isEmpty());
1480        LocalTestNode node = new LocalTestNode(-1);
1481
1482        m.put(node.getKey(), node);
1483        assertTrue(s.contains(node.getKey()));
1484        assertEquals(m.size(), s.size());
1485        assertEquals(m.isEmpty(), s.isEmpty());
1486        m.remove(node.getKey());
1487        assertTrue(!s.contains(node.getKey()));
1488        assertEquals(m.size(), s.size());
1489        assertEquals(m.isEmpty(), s.isEmpty());
1490        try
1491        {
1492            s.contains(null);
1493            fail("should have caught NullPointerException");
1494        }
1495        catch (NullPointerException JavaDoc ignored)
1496        {
1497        }
1498        try
1499        {
1500            s.contains(new Object JavaDoc());
1501            fail("should have caught ClassCastException");
1502        }
1503        catch (ClassCastException JavaDoc ignored)
1504        {
1505        }
1506        for (int k = 0; k < m.size(); k++)
1507        {
1508            assertTrue(s.contains(new Integer JavaDoc(k)));
1509        }
1510        int count = 0;
1511
1512        for (Iterator iter = s.iterator(); iter.hasNext(); )
1513        {
1514            iter.next();
1515            ++count;
1516        }
1517        assertEquals(count, s.size());
1518
1519        // force the map to have some content
1520
m.put(node.getKey(), node);
1521        Iterator iter = m.keySet().iterator();
1522        LocalTestNode node2 = new LocalTestNode(-2);
1523
1524        m.put(node2.getKey(), node2);
1525        try
1526        {
1527            iter.next();
1528            fail("next() should have thrown an exception after a put");
1529        }
1530        catch (ConcurrentModificationException ignored)
1531        {
1532        }
1533        m.remove(node2.getKey());
1534        iter = s.iterator();
1535        m.remove(node.getKey());
1536        try
1537        {
1538            iter.next();
1539            fail("next() should have thrown an exception after a Map remove");
1540        }
1541        catch (ConcurrentModificationException ignored)
1542        {
1543        }
1544        m.put(node.getKey(), node);
1545        iter = s.iterator();
1546        s.remove(node.getKey());
1547        try
1548        {
1549            iter.next();
1550            fail("next() should have thrown an exception after a Set remove");
1551        }
1552        catch (ConcurrentModificationException ignored)
1553        {
1554        }
1555        iter = s.iterator();
1556        count = 0;
1557        boolean terminated = false;
1558
1559        try
1560        {
1561            while (true)
1562            {
1563                iter.next();
1564                ++count;
1565            }
1566        }
1567        catch (NoSuchElementException ignored)
1568        {
1569            terminated = true;
1570        }
1571        assertTrue(terminated);
1572        assertEquals(m.size(), count);
1573        iter = s.iterator();
1574        try
1575        {
1576            iter.remove();
1577            fail("Should have thrown exception");
1578        }
1579        catch (IllegalStateException JavaDoc ignored)
1580        {
1581        }
1582        m.put(node.getKey(), node);
1583        iter = s.iterator();
1584        iter.next();
1585        m.put(node2.getKey(), node2);
1586        try
1587        {
1588            iter.remove();
1589            fail("should have thrown exception");
1590        }
1591        catch (ConcurrentModificationException ignored)
1592        {
1593        }
1594        Iterator iter2 = s.iterator();
1595
1596        iter2.next();
1597        LocalTestNode node3 = new LocalTestNode(-3);
1598
1599        m.put(node3.getKey(), node3);
1600        try
1601        {
1602            iter2.remove();
1603            fail("should have thrown exception");
1604        }
1605        catch (ConcurrentModificationException ignored)
1606        {
1607        }
1608        int r_count = 0;
1609
1610        for (iter = s.iterator(); iter.hasNext(); )
1611        {
1612            if (iter.next().equals(node.getKey()))
1613            {
1614                try
1615                {
1616                    iter.remove();
1617                    ++r_count;
1618                    iter.remove();
1619                    fail("2nd remove should have failed");
1620                }
1621                catch (IllegalStateException JavaDoc ignored)
1622                {
1623                    assertEquals(1, r_count);
1624                }
1625            }
1626        }
1627        assertEquals(1, r_count);
1628        assertTrue(!s.contains(node.getKey()));
1629        r_count = 0;
1630        m.put(node.getKey(), node);
1631        Object JavaDoc[] a1 = s.toArray();
1632
1633        assertEquals(s.size(), a1.length);
1634        if (a1.length > 1)
1635        {
1636            Comparable JavaDoc first = ( Comparable JavaDoc ) a1[ 0 ];
1637
1638            for (int k = 1; k < a1.length; k++)
1639            {
1640                Comparable JavaDoc second = ( Comparable JavaDoc ) a1[ k ];
1641
1642                assertTrue(first.compareTo(second) < 0);
1643                first = second;
1644            }
1645            iter = s.iterator();
1646            first = ( Comparable JavaDoc ) iter.next();
1647            for (; iter.hasNext(); )
1648            {
1649                Comparable JavaDoc second = ( Comparable JavaDoc ) iter.next();
1650
1651                assertTrue(first.compareTo(second) < 0);
1652                first = second;
1653            }
1654        }
1655        try
1656        {
1657            String JavaDoc array2[] = ( String JavaDoc [] ) s.toArray(new String JavaDoc[ 0 ]);
1658
1659            if (s.size() != 0)
1660            {
1661                fail("should have caught exception creating an invalid array");
1662            }
1663        }
1664        catch (ArrayStoreException JavaDoc ignored)
1665        {
1666        }
1667        Comparable JavaDoc array2[] =
1668            ( Comparable JavaDoc [] ) s.toArray(new Comparable JavaDoc[ 0 ]);
1669        Integer JavaDoc array3[] =
1670            ( Integer JavaDoc [] ) s.toArray(new Integer JavaDoc[ s.size() ]);
1671
1672        if (array3.length > 1)
1673        {
1674            Integer JavaDoc first = array3[ 0 ];
1675
1676            for (int k = 1; k < array3.length; k++)
1677            {
1678                Integer JavaDoc second = array3[ k ];
1679
1680                assertTrue(first.compareTo(second) < 0);
1681                first = second;
1682            }
1683        }
1684        try
1685        {
1686            s.add("foo");
1687            fail("should have thrown an exception");
1688        }
1689        catch (UnsupportedOperationException JavaDoc ignored)
1690        {
1691        }
1692        assertTrue(!s.equals(null));
1693        assertEquals(s, s);
1694        Set hs = new HashSet(s);
1695
1696        assertEquals(s, hs);
1697        assertEquals(hs, s);
1698        assertTrue(s.hashCode() == hs.hashCode());
1699    }
1700
1701    private void testKeySetByValue(final BinaryTree m)
1702    {
1703        Set s = m.keySetByValue();
1704
1705        assertEquals(m.size(), s.size());
1706        assertEquals(m.isEmpty(), s.isEmpty());
1707        LocalTestNode node = new LocalTestNode(-1);
1708
1709        m.put(node.getKey(), node);
1710        assertTrue(s.contains(node.getKey()));
1711        assertEquals(m.size(), s.size());
1712        assertEquals(m.isEmpty(), s.isEmpty());
1713        m.remove(node.getKey());
1714        assertTrue(!s.contains(node.getKey()));
1715        assertEquals(m.size(), s.size());
1716        assertEquals(m.isEmpty(), s.isEmpty());
1717        try
1718        {
1719            s.contains(null);
1720            fail("should have caught NullPointerException");
1721        }
1722        catch (NullPointerException JavaDoc ignored)
1723        {
1724        }
1725        try
1726        {
1727            s.contains(new Object JavaDoc());
1728            fail("should have caught ClassCastException");
1729        }
1730        catch (ClassCastException JavaDoc ignored)
1731        {
1732        }
1733        for (int k = 0; k < m.size(); k++)
1734        {
1735            assertTrue(s.contains(new Integer JavaDoc(k)));
1736        }
1737        int count = 0;
1738
1739        for (Iterator iter = s.iterator(); iter.hasNext(); )
1740        {
1741            iter.next();
1742            ++count;
1743        }
1744        assertEquals(count, s.size());
1745
1746        // force the map to have some content
1747
m.put(node.getKey(), node);
1748        Iterator iter = m.keySetByValue().iterator();
1749        LocalTestNode node2 = new LocalTestNode(-2);
1750
1751        m.put(node2.getKey(), node2);
1752        try
1753        {
1754            iter.next();
1755            fail("next() should have thrown an exception after a put");
1756        }
1757        catch (ConcurrentModificationException ignored)
1758        {
1759        }
1760        m.remove(node2.getKey());
1761        iter = s.iterator();
1762        m.remove(node.getKey());
1763        try
1764        {
1765            iter.next();
1766            fail("next() should have thrown an exception after a Map remove");
1767        }
1768        catch (ConcurrentModificationException ignored)
1769        {
1770        }
1771        m.put(node.getKey(), node);
1772        iter = s.iterator();
1773        s.remove(node.getKey());
1774        try
1775        {
1776            iter.next();
1777            fail("next() should have thrown an exception after a Set remove");
1778        }
1779        catch (ConcurrentModificationException ignored)
1780        {
1781        }
1782        iter = s.iterator();
1783        count = 0;
1784        boolean terminated = false;
1785
1786        try
1787        {
1788            while (true)
1789            {
1790                iter.next();
1791                ++count;
1792            }
1793        }
1794        catch (NoSuchElementException ignored)
1795        {
1796            terminated = true;
1797        }
1798        assertTrue(terminated);
1799        assertEquals(m.size(), count);
1800        iter = s.iterator();
1801        try
1802        {
1803            iter.remove();
1804            fail("Should have thrown exception");
1805        }
1806        catch (IllegalStateException JavaDoc ignored)
1807        {
1808        }
1809        m.put(node.getKey(), node);
1810        iter = s.iterator();
1811        iter.next();
1812        m.put(node2.getKey(), node2);
1813        try
1814        {
1815            iter.remove();
1816            fail("should have thrown exception");
1817        }
1818        catch (ConcurrentModificationException ignored)
1819        {
1820        }
1821        Iterator iter2 = s.iterator();
1822
1823        iter2.next();
1824        LocalTestNode node3 = new LocalTestNode(-3);
1825
1826        m.put(node3.getKey(), node3);
1827        try
1828        {
1829            iter2.remove();
1830            fail("should have thrown exception");
1831        }
1832        catch (ConcurrentModificationException ignored)
1833        {
1834        }
1835        int r_count = 0;
1836
1837        for (iter = s.iterator(); iter.hasNext(); )
1838        {
1839            if (iter.next().equals(node.getKey()))
1840            {
1841                try
1842                {
1843                    iter.remove();
1844                    ++r_count;
1845                    iter.remove();
1846                    fail("2nd remove should have failed");
1847                }
1848                catch (IllegalStateException JavaDoc ignored)
1849                {
1850                    assertEquals(1, r_count);
1851                }
1852            }
1853        }
1854        assertEquals(1, r_count);
1855        assertTrue(!s.contains(node.getKey()));
1856        r_count = 0;
1857        m.put(node.getKey(), node);
1858        Object JavaDoc[] a1 = s.toArray();
1859
1860        assertEquals(s.size(), a1.length);
1861
1862// if (a1.length > 1)
1863
// {
1864
// Comparable first = ( Comparable ) a1[ 0 ];
1865
// for (int k = 1; k < a1.length; k++)
1866
// {
1867
// Comparable second = ( Comparable ) a1[ k ];
1868
// assertTrue(first.compareTo(second) < 0);
1869
// first = second;
1870
// }
1871
// iter = s.iterator();
1872
// first = ( Comparable ) iter.next();
1873
// for (; iter.hasNext(); )
1874
// {
1875
// Comparable second = ( Comparable ) iter.next();
1876
// assertTrue(first.compareTo(second) < 0);
1877
// first = second;
1878
// }
1879
// }
1880
try
1881        {
1882            String JavaDoc array2[] = ( String JavaDoc [] ) s.toArray(new String JavaDoc[ 0 ]);
1883
1884            if (s.size() != 0)
1885            {
1886                fail("should have caught exception creating an invalid array");
1887            }
1888        }
1889        catch (ArrayStoreException JavaDoc ignored)
1890        {
1891        }
1892        Comparable JavaDoc array2[] =
1893            ( Comparable JavaDoc [] ) s.toArray(new Comparable JavaDoc[ 0 ]);
1894        Integer JavaDoc array3[] =
1895            ( Integer JavaDoc [] ) s.toArray(new Integer JavaDoc[ s.size() ]);
1896
1897// if (array3.length > 1)
1898
// {
1899
// Integer first = array3[ 0 ];
1900
// for (int k = 1; k < array3.length; k++)
1901
// {
1902
// Integer second = array3[ k ];
1903
// assertTrue(first.compareTo(second) < 0);
1904
// first = second;
1905
// }
1906
// }
1907
try
1908        {
1909            s.add("foo");
1910            fail("should have thrown an exception");
1911        }
1912        catch (UnsupportedOperationException JavaDoc ignored)
1913        {
1914        }
1915        assertTrue(!s.equals(null));
1916        assertEquals(s, s);
1917        Set hs = new HashSet(s);
1918
1919        assertEquals(s, hs);
1920        assertEquals(hs, s);
1921        assertTrue(s.hashCode() == hs.hashCode());
1922    }
1923
1924    private void testValues(Map m)
1925    {
1926        Collection s = m.values();
1927
1928        assertEquals(m.size(), s.size());
1929        assertEquals(m.isEmpty(), s.isEmpty());
1930        LocalTestNode node = new LocalTestNode(-1);
1931
1932        m.put(node.getKey(), node);
1933        assertEquals(m.size(), s.size());
1934        assertEquals(m.isEmpty(), s.isEmpty());
1935        m.remove(node.getKey());
1936        assertEquals(m.size(), s.size());
1937        assertEquals(m.isEmpty(), s.isEmpty());
1938        assertTrue(!s.contains(node));
1939        for (int k = 0; k < m.size(); k++)
1940        {
1941            assertTrue(s.contains(new LocalTestNode(k)));
1942        }
1943        m.put(node.getKey(), node);
1944        assertTrue(s.contains(node));
1945        m.remove(node.getKey());
1946        assertTrue(!s.contains(node));
1947        int count = 0;
1948
1949        for (Iterator iter = s.iterator(); iter.hasNext(); )
1950        {
1951            iter.next();
1952            ++count;
1953        }
1954        assertEquals(s.size(), count);
1955        LocalTestNode node4 = new LocalTestNode(-4);
1956
1957        m.put(node4.getKey(), node4);
1958        Iterator iter = s.iterator();
1959
1960        m.put(node.getKey(), node);
1961        try
1962        {
1963            iter.next();
1964            fail("next() should have thrown an exception after a put");
1965        }
1966        catch (ConcurrentModificationException ignored)
1967        {
1968        }
1969        iter = s.iterator();
1970        m.remove(node.getKey());
1971        try
1972        {
1973            iter.next();
1974            fail("next() should have thrown an exception after a Map remove");
1975        }
1976        catch (ConcurrentModificationException ignored)
1977        {
1978        }
1979        m.put(node.getKey(), node);
1980        iter = s.iterator();
1981        s.remove(node);
1982        try
1983        {
1984            iter.next();
1985            fail("next() should have thrown an exception after a Set remove");
1986        }
1987        catch (ConcurrentModificationException ignored)
1988        {
1989        }
1990        iter = s.iterator();
1991        count = 0;
1992        boolean terminated = false;
1993
1994        try
1995        {
1996            while (true)
1997            {
1998                iter.next();
1999                ++count;
2000            }
2001        }
2002        catch (NoSuchElementException ignored)
2003        {
2004            terminated = true;
2005        }
2006        assertTrue(terminated);
2007        assertEquals(m.size(), count);
2008        iter = s.iterator();
2009        try
2010        {
2011            iter.remove();
2012            fail("Should have thrown exception");
2013        }
2014        catch (IllegalStateException JavaDoc ignored)
2015        {
2016        }
2017        Iterator iter2 = s.iterator();
2018
2019        try
2020        {
2021            iter2.remove();
2022            fail("Should have thrown exception");
2023        }
2024        catch (IllegalStateException JavaDoc ignored)
2025        {
2026        }
2027        m.put(node.getKey(), node);
2028        iter = s.iterator();
2029        iter.next();
2030        LocalTestNode node2 = new LocalTestNode(-2);
2031
2032        m.put(node2.getKey(), node2);
2033        try
2034        {
2035            iter.remove();
2036            fail("should have thrown exception");
2037        }
2038        catch (ConcurrentModificationException ignored)
2039        {
2040        }
2041        LocalTestNode node3 = new LocalTestNode(-3);
2042
2043        m.put(node3.getKey(), node3);
2044        iter2 = s.iterator();
2045        while (iter2.hasNext())
2046        {
2047            iter2.next();
2048        }
2049        int r_count = 0;
2050
2051        for (iter = s.iterator(); iter.hasNext(); )
2052        {
2053            if (iter.next().equals(node3))
2054            {
2055                try
2056                {
2057                    iter.remove();
2058                    ++r_count;
2059                    iter.remove();
2060                    fail("2nd remove should have failed");
2061                }
2062                catch (IllegalStateException JavaDoc ignored)
2063                {
2064                    assertEquals(1, r_count);
2065                }
2066            }
2067        }
2068        assertEquals(1, r_count);
2069        assertTrue(!s.contains(node3));
2070        Object JavaDoc[] a1 = s.toArray();
2071
2072        assertTrue(a1.length == s.size());
2073        if (a1.length > 1)
2074        {
2075            Comparable JavaDoc first = ( Comparable JavaDoc ) a1[ 0 ];
2076
2077            for (int k = 1; k < a1.length; k++)
2078            {
2079                Comparable JavaDoc second = ( Comparable JavaDoc ) a1[ k ];
2080
2081                assertTrue(first.compareTo(second) < 0);
2082                first = second;
2083            }
2084            iter = s.iterator();
2085            first = ( Comparable JavaDoc ) iter.next();
2086            for (; iter.hasNext(); )
2087            {
2088                Comparable JavaDoc second = ( Comparable JavaDoc ) iter.next();
2089
2090                assertTrue(first.compareTo(second) < 0);
2091                first = second;
2092            }
2093        }
2094        try
2095        {
2096            String JavaDoc array2[] = ( String JavaDoc [] ) s.toArray(new String JavaDoc[ 0 ]);
2097
2098            if (s.size() != 0)
2099            {
2100                fail("should have caught exception creating an invalid array");
2101            }
2102        }
2103        catch (ArrayStoreException JavaDoc ignored)
2104        {
2105        }
2106        m.remove(node.getKey());
2107        m.remove(node2.getKey());
2108        m.remove(node3.getKey());
2109        LocalTestNode array2[] =
2110            ( LocalTestNode [] ) s.toArray(new LocalTestNode[ 0 ]);
2111        LocalTestNode array3[] =
2112            ( LocalTestNode [] ) s.toArray(new LocalTestNode[ s.size() ]);
2113
2114        if (array3.length > 1)
2115        {
2116            LocalTestNode first = array3[ 0 ];
2117
2118            for (int k = 1; k < array3.length; k++)
2119            {
2120                LocalTestNode second = array3[ k ];
2121
2122                assertTrue(first.compareTo(second) < 0);
2123                first = second;
2124            }
2125        }
2126        try
2127        {
2128            s.add(node.getKey());
2129            fail("should have thrown an exception");
2130        }
2131        catch (UnsupportedOperationException JavaDoc ignored)
2132        {
2133        }
2134        assertTrue(!s.equals(null));
2135        assertEquals(s, s);
2136        Set hs = new HashSet(s);
2137
2138        assertTrue(!s.equals(hs));
2139        assertTrue(!hs.equals(s));
2140    }
2141
2142    private void testValuesByValue(BinaryTree m)
2143    {
2144        Collection s = m.valuesByValue();
2145
2146        assertEquals(m.size(), s.size());
2147        assertEquals(m.isEmpty(), s.isEmpty());
2148        LocalTestNode node = new LocalTestNode(-1);
2149
2150        m.put(node.getKey(), node);
2151        assertEquals(m.size(), s.size());
2152        assertEquals(m.isEmpty(), s.isEmpty());
2153        m.remove(node.getKey());
2154        assertEquals(m.size(), s.size());
2155        assertEquals(m.isEmpty(), s.isEmpty());
2156        assertTrue(!s.contains(node));
2157        for (int k = 0; k < m.size(); k++)
2158        {
2159            assertTrue(s.contains(new LocalTestNode(k)));
2160        }
2161        m.put(node.getKey(), node);
2162        assertTrue(s.contains(node));
2163        m.remove(node.getKey());
2164        assertTrue(!s.contains(node));
2165        int count = 0;
2166
2167        for (Iterator iter = s.iterator(); iter.hasNext(); )
2168        {
2169            iter.next();
2170            ++count;
2171        }
2172        assertEquals(s.size(), count);
2173        LocalTestNode node4 = new LocalTestNode(-4);
2174
2175        m.put(node4.getKey(), node4);
2176        Iterator iter = s.iterator();
2177
2178        m.put(node.getKey(), node);
2179        try
2180        {
2181            iter.next();
2182            fail("next() should have thrown an exception after a put");
2183        }
2184        catch (ConcurrentModificationException ignored)
2185        {
2186        }
2187        iter = s.iterator();
2188        m.remove(node.getKey());
2189        try
2190        {
2191            iter.next();
2192            fail("next() should have thrown an exception after a Map remove");
2193        }
2194        catch (ConcurrentModificationException ignored)
2195        {
2196        }
2197        m.put(node.getKey(), node);
2198        iter = s.iterator();
2199        s.remove(node);
2200        try
2201        {
2202            iter.next();
2203            fail("next() should have thrown an exception after a Set remove");
2204        }
2205        catch (ConcurrentModificationException ignored)
2206        {
2207        }
2208        iter = s.iterator();
2209        count = 0;
2210        boolean terminated = false;
2211
2212        try
2213        {
2214            while (true)
2215            {
2216                iter.next();
2217                ++count;
2218            }
2219        }
2220        catch (NoSuchElementException ignored)
2221        {
2222            terminated = true;
2223        }
2224        assertTrue(terminated);
2225        assertEquals(m.size(), count);
2226        iter = s.iterator();
2227        try
2228        {
2229            iter.remove();
2230            fail("Should have thrown exception");
2231        }
2232        catch (IllegalStateException JavaDoc ignored)
2233        {
2234        }
2235        Iterator iter2 = s.iterator();
2236
2237        try
2238        {
2239            iter2.remove();
2240            fail("Should have thrown exception");
2241        }
2242        catch (IllegalStateException JavaDoc ignored)
2243        {
2244        }
2245        m.put(node.getKey(), node);
2246        iter = s.iterator();
2247        iter.next();
2248        LocalTestNode node2 = new LocalTestNode(-2);
2249
2250        m.put(node2.getKey(), node2);
2251        try
2252        {
2253            iter.remove();
2254            fail("should have thrown exception");
2255        }
2256        catch (ConcurrentModificationException ignored)
2257        {
2258        }
2259        LocalTestNode node3 = new LocalTestNode(-3);
2260
2261        m.put(node3.getKey(), node3);
2262        iter2 = s.iterator();
2263        while (iter2.hasNext())
2264        {
2265            iter2.next();
2266        }
2267        int r_count = 0;
2268
2269        for (iter = s.iterator(); iter.hasNext(); )
2270        {
2271            if (iter.next().equals(node3))
2272            {
2273                try
2274                {
2275                    iter.remove();
2276                    ++r_count;
2277                    iter.remove();
2278                    fail("2nd remove should have failed");
2279                }
2280                catch (IllegalStateException JavaDoc ignored)
2281                {
2282                    assertEquals(1, r_count);
2283                }
2284            }
2285        }
2286        assertEquals(1, r_count);
2287        assertTrue(!s.contains(node3));
2288        Object JavaDoc[] a1 = s.toArray();
2289
2290        assertTrue(a1.length == s.size());
2291        try
2292        {
2293            String JavaDoc array2[] = ( String JavaDoc [] ) s.toArray(new String JavaDoc[ 0 ]);
2294
2295            if (s.size() != 0)
2296            {
2297                fail("should have caught exception creating an invalid array");
2298            }
2299        }
2300        catch (ArrayStoreException JavaDoc ignored)
2301        {
2302        }
2303        m.remove(node.getKey());
2304        m.remove(node2.getKey());
2305        m.remove(node3.getKey());
2306        LocalTestNode array2[] =
2307            ( LocalTestNode [] ) s.toArray(new LocalTestNode[ 0 ]);
2308        LocalTestNode array3[] =
2309            ( LocalTestNode [] ) s.toArray(new LocalTestNode[ s.size() ]);
2310
2311        try
2312        {
2313            s.add(node.getKey());
2314            fail("should have thrown an exception");
2315        }
2316        catch (UnsupportedOperationException JavaDoc ignored)
2317        {
2318        }
2319        assertTrue(!s.equals(null));
2320        assertEquals(s, s);
2321        Set hs = new HashSet(s);
2322
2323        assertTrue(!s.equals(hs));
2324        assertTrue(!hs.equals(s));
2325    }
2326
2327    private void testEntrySet(Map m)
2328    {
2329        Set s = m.entrySet();
2330
2331        assertEquals(m.size(), s.size());
2332        assertEquals(m.isEmpty(), s.isEmpty());
2333        LocalTestNode node = new LocalTestNode(-1);
2334
2335        m.put(node.getKey(), node);
2336        assertEquals(m.size(), s.size());
2337        assertEquals(m.isEmpty(), s.isEmpty());
2338        m.remove(node.getKey());
2339        assertEquals(m.size(), s.size());
2340        assertEquals(m.isEmpty(), s.isEmpty());
2341        int count = 0;
2342
2343        for (Iterator iter = s.iterator(); iter.hasNext(); )
2344        {
2345            iter.next();
2346            ++count;
2347        }
2348        assertEquals(s.size(), count);
2349        LocalTestNode node2 = new LocalTestNode(-2);
2350
2351        if (m.size() == 0)
2352        {
2353            m.put(node2.getKey(), node2);
2354        }
2355        Iterator iter = s.iterator();
2356
2357        m.put(node.getKey(), node);
2358        try
2359        {
2360            iter.next();
2361            fail("next() should have thrown an exception after a put");
2362        }
2363        catch (ConcurrentModificationException ignored)
2364        {
2365        }
2366        m.remove(node2.getKey());
2367        iter = s.iterator();
2368        m.remove(node.getKey());
2369        try
2370        {
2371            iter.next();
2372            fail("next() should have thrown an exception after a Map remove");
2373        }
2374        catch (ConcurrentModificationException ignored)
2375        {
2376        }
2377        m.put(node.getKey(), node);
2378        iter = s.iterator();
2379        count = 0;
2380        boolean terminated = false;
2381
2382        try
2383        {
2384            while (true)
2385            {
2386                iter.next();
2387                ++count;
2388            }
2389        }
2390        catch (NoSuchElementException ignored)
2391        {
2392            terminated = true;
2393        }
2394        assertTrue(terminated);
2395        assertEquals(m.size(), count);
2396        iter = s.iterator();
2397        try
2398        {
2399            iter.remove();
2400            fail("Should have thrown exception");
2401        }
2402        catch (IllegalStateException JavaDoc ignored)
2403        {
2404        }
2405        iter = s.iterator();
2406        iter.next();
2407        LocalTestNode node3 = new LocalTestNode(-3);
2408
2409        m.put(node3.getKey(), node3);
2410        try
2411        {
2412            iter.remove();
2413            fail("should have thrown exception");
2414        }
2415        catch (ConcurrentModificationException ignored)
2416        {
2417        }
2418        int r_count = 0;
2419        int when = m.size() / 2;
2420        int timer = 0;
2421
2422        for (iter = s.iterator(); iter.hasNext(); )
2423        {
2424            iter.next();
2425            if (timer == when)
2426            {
2427                try
2428                {
2429                    iter.remove();
2430                    ++r_count;
2431                    iter.remove();
2432                    fail("2nd remove should have failed");
2433                }
2434                catch (IllegalStateException JavaDoc ignored)
2435                {
2436                    assertEquals(1, r_count);
2437                }
2438            }
2439            timer++;
2440        }
2441        assertEquals(1, r_count);
2442        Iterator iter2 = s.iterator();
2443
2444        try
2445        {
2446            iter2.remove();
2447            fail("Should have thrown exception");
2448        }
2449        catch (IllegalStateException JavaDoc ignored)
2450        {
2451        }
2452        iter2 = s.iterator();
2453        while (iter2.hasNext())
2454        {
2455            iter2.next();
2456        }
2457        LocalTestNode node4 = new LocalTestNode(-4);
2458
2459        m.put(node4.getKey(), node4);
2460        try
2461        {
2462            iter2.remove();
2463            fail("should have thrown exception");
2464        }
2465        catch (ConcurrentModificationException ignored)
2466        {
2467        }
2468        Object JavaDoc[] a1 = s.toArray();
2469
2470        assertTrue(a1.length == s.size());
2471        if (a1.length > 1)
2472        {
2473            Map.Entry first = ( Map.Entry ) a1[ 0 ];
2474
2475            for (int k = 1; k < a1.length; k++)
2476            {
2477                Map.Entry second = ( Map.Entry ) a1[ k ];
2478
2479                assertTrue((( Comparable JavaDoc ) first.getKey())
2480                    .compareTo(( Comparable JavaDoc ) second.getKey()) < 0);
2481                first = second;
2482            }
2483            iter = s.iterator();
2484            first = ( Map.Entry ) iter.next();
2485            for (; iter.hasNext(); )
2486            {
2487                Map.Entry second = ( Map.Entry ) iter.next();
2488
2489                assertTrue((( Comparable JavaDoc ) first.getKey())
2490                    .compareTo(( Comparable JavaDoc ) second.getKey()) < 0);
2491                first = second;
2492            }
2493        }
2494        try
2495        {
2496            Integer JavaDoc array2[] = ( Integer JavaDoc [] ) s.toArray(new Integer JavaDoc[ 0 ]);
2497
2498            if (s.size() != 0)
2499            {
2500                fail("should have caught exception creating an invalid array");
2501            }
2502        }
2503        catch (ArrayStoreException JavaDoc ignored)
2504        {
2505        }
2506        Map.Entry array2[] = ( Map.Entry [] ) s.toArray(new Map.Entry[ 0 ]);
2507        Map.Entry array3[] =
2508            ( Map.Entry [] ) s.toArray(new Map.Entry[ s.size() ]);
2509
2510        if (array3.length > 1)
2511        {
2512            Comparable JavaDoc first =
2513                ( Comparable JavaDoc ) (( Map.Entry ) array3[ 0 ]).getKey();
2514
2515            for (int k = 1; k < array3.length; k++)
2516            {
2517                Comparable JavaDoc second =
2518                    ( Comparable JavaDoc ) (( Map.Entry ) array3[ k ]).getKey();
2519
2520                assertTrue(first.compareTo(second) < 0);
2521                first = second;
2522            }
2523        }
2524        try
2525        {
2526            s.add(node.getKey());
2527            fail("should have thrown an exception");
2528        }
2529        catch (UnsupportedOperationException JavaDoc ignored)
2530        {
2531        }
2532        assertTrue(!s.equals(null));
2533        assertEquals("SetEquality 1", s, s);
2534        Set hs = new HashSet(s);
2535
2536        assertEquals("SetEquality 2", s, hs);
2537        assertEquals("SetEquality 3", hs, s);
2538        assertTrue(s.hashCode() == hs.hashCode());
2539    }
2540
2541    private void testEntrySetByValue(BinaryTree m)
2542    {
2543        Set s = m.entrySetByValue();
2544
2545        assertEquals(m.size(), s.size());
2546        assertEquals(m.isEmpty(), s.isEmpty());
2547        LocalTestNode node = new LocalTestNode(-1);
2548
2549        m.put(node.getKey(), node);
2550        assertEquals(m.size(), s.size());
2551        assertEquals(m.isEmpty(), s.isEmpty());
2552        m.remove(node.getKey());
2553        assertEquals(m.size(), s.size());
2554        assertEquals(m.isEmpty(), s.isEmpty());
2555        int count = 0;
2556
2557        for (Iterator iter = s.iterator(); iter.hasNext(); )
2558        {
2559            iter.next();
2560            ++count;
2561        }
2562        assertEquals(s.size(), count);
2563        LocalTestNode node2 = new LocalTestNode(-2);
2564
2565        if (m.size() == 0)
2566        {
2567            m.put(node2.getKey(), node2);
2568        }
2569        Iterator iter = s.iterator();
2570
2571        m.put(node.getKey(), node);
2572        try
2573        {
2574            iter.next();
2575            fail("next() should have thrown an exception after a put");
2576        }
2577        catch (ConcurrentModificationException ignored)
2578        {
2579        }
2580        m.remove(node2.getKey());
2581        iter = s.iterator();
2582        m.remove(node.getKey());
2583        try
2584        {
2585            iter.next();
2586            fail("next() should have thrown an exception after a Map remove");
2587        }
2588        catch (ConcurrentModificationException ignored)
2589        {
2590        }
2591        m.put(node.getKey(), node);
2592        iter = s.iterator();
2593        count = 0;
2594        boolean terminated = false;
2595
2596        try
2597        {
2598            while (true)
2599            {
2600                iter.next();
2601                ++count;
2602            }
2603        }
2604        catch (NoSuchElementException ignored)
2605        {
2606            terminated = true;
2607        }
2608        assertTrue(terminated);
2609        assertEquals(m.size(), count);
2610        iter = s.iterator();
2611        try
2612        {
2613            iter.remove();
2614            fail("Should have thrown exception");
2615        }
2616        catch (IllegalStateException JavaDoc ignored)
2617        {
2618        }
2619        iter = s.iterator();
2620        iter.next();
2621        LocalTestNode node3 = new LocalTestNode(-3);
2622
2623        m.put(node3.getKey(), node3);
2624        try
2625        {
2626            iter.remove();
2627            fail("should have thrown exception");
2628        }
2629        catch (ConcurrentModificationException ignored)
2630        {
2631        }
2632        int r_count = 0;
2633        int when = m.size() / 2;
2634        int timer = 0;
2635
2636        for (iter = s.iterator(); iter.hasNext(); )
2637        {
2638            iter.next();
2639            if (timer == when)
2640            {
2641                try
2642                {
2643                    iter.remove();
2644                    ++r_count;
2645                    iter.remove();
2646                    fail("2nd remove should have failed");
2647                }
2648                catch (IllegalStateException JavaDoc ignored)
2649                {
2650                    assertEquals(1, r_count);
2651                }
2652            }
2653            timer++;
2654        }
2655        assertEquals(1, r_count);
2656        Iterator iter2 = s.iterator();
2657
2658        try
2659        {
2660            iter2.remove();
2661            fail("Should have thrown exception");
2662        }
2663        catch (IllegalStateException JavaDoc ignored)
2664        {
2665        }
2666        iter2 = s.iterator();
2667        while (iter2.hasNext())
2668        {
2669            iter2.next();
2670        }
2671        LocalTestNode node4 = new LocalTestNode(-4);
2672
2673        m.put(node4.getKey(), node4);
2674        try
2675        {
2676            iter2.remove();
2677            fail("should have thrown exception");
2678        }
2679        catch (ConcurrentModificationException ignored)
2680        {
2681        }
2682        Object JavaDoc[] a1 = s.toArray();
2683
2684        assertTrue(a1.length == s.size());
2685        if (a1.length > 1)
2686        {
2687            Map.Entry first = ( Map.Entry ) a1[ 0 ];
2688
2689            for (int k = 1; k < a1.length; k++)
2690            {
2691                Map.Entry second = ( Map.Entry ) a1[ k ];
2692
2693                assertTrue((( Comparable JavaDoc ) first.getKey())
2694                    .compareTo(( Comparable JavaDoc ) second.getKey()) < 0);
2695                first = second;
2696            }
2697            iter = s.iterator();
2698            first = ( Map.Entry ) iter.next();
2699            for (; iter.hasNext(); )
2700            {
2701                Map.Entry second = ( Map.Entry ) iter.next();
2702
2703                assertTrue((( Comparable JavaDoc ) first.getKey())
2704                    .compareTo(( Comparable JavaDoc ) second.getKey()) < 0);
2705                first = second;
2706            }
2707        }
2708        try
2709        {
2710            Integer JavaDoc array2[] = ( Integer JavaDoc [] ) s.toArray(new Integer JavaDoc[ 0 ]);
2711
2712            if (s.size() != 0)
2713            {
2714                fail("should have caught exception creating an invalid array");
2715            }
2716        }
2717        catch (ArrayStoreException JavaDoc ignored)
2718        {
2719        }
2720        Map.Entry array2[] = ( Map.Entry [] ) s.toArray(new Map.Entry[ 0 ]);
2721        Map.Entry array3[] =
2722            ( Map.Entry [] ) s.toArray(new Map.Entry[ s.size() ]);
2723
2724        if (array3.length > 1)
2725        {
2726            Comparable JavaDoc first =
2727                ( Comparable JavaDoc ) (( Map.Entry ) array3[ 0 ]).getValue();
2728
2729            for (int k = 1; k < array3.length; k++)
2730            {
2731                Comparable JavaDoc second =
2732                    ( Comparable JavaDoc ) (( Map.Entry ) array3[ k ]).getValue();
2733
2734                assertTrue(first.compareTo(second) < 0);
2735                first = second;
2736            }
2737        }
2738        try
2739        {
2740            s.add(node.getKey());
2741            fail("should have thrown an exception");
2742        }
2743        catch (UnsupportedOperationException JavaDoc ignored)
2744        {
2745        }
2746        assertTrue(!s.equals(null));
2747        assertEquals("SetEquality 1", s, s);
2748        Set hs = new HashSet(s);
2749
2750        assertEquals("SetEquality 2", s, hs);
2751        assertEquals("SetEquality 3", hs, s);
2752        assertTrue(s.hashCode() == hs.hashCode());
2753    }
2754
2755    private LocalTestNode [] makeLocalNodes()
2756    {
2757        LocalTestNode nodes[] = new LocalTestNode[ 1023 ];
2758
2759        for (int k = 0; k < nodes.length; k++)
2760        {
2761            nodes[ k ] = new LocalTestNode(k);
2762        }
2763        return nodes;
2764    }
2765
2766    /* ********** END helper methods ********** */
2767
2768    /**
2769     * Method main
2770     *
2771     * @param unused_args
2772     */

2773
2774    public static void main(final String JavaDoc unused_args[])
2775    {
2776        junit.textui.TestRunner.run(TestBinaryTree.class);
2777    }
2778}
2779
Popular Tags