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 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 ());
131             fail("should have caught ClassCastException");
132         }
133         catch (ClassCastException ignored)
134         {
135         }
136         try
137         {
138             m.containsKey(null);
139             fail("should have caught NullPointerException");
140         }
141         catch (NullPointerException 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 (-1)));
153         try
154         {
155             m.containsKey("foo");
156             fail("Should have caught ClassCastException");
157         }
158         catch (ClassCastException 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 ());
200             fail("should have caught ClassCastException");
201         }
202         catch (ClassCastException ignored)
203         {
204         }
205         try
206         {
207             m.get(null);
208             fail("should have caught NullPointerException");
209         }
210         catch (NullPointerException 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 (-1)));
222         try
223         {
224             m.get("foo");
225             fail("Should have caught ClassCastException");
226         }
227         catch (ClassCastException 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 (), "foo");
249             fail("should have caught ClassCastException");
250         }
251         catch (ClassCastException ignored)
252         {
253         }
254         try
255         {
256             m.put(null, "foo");
257             fail("should have caught NullPointerException");
258         }
259         catch (NullPointerException ignored)
260         {
261         }
262         try
263         {
264             m.put("foo", null);
265             fail("should have caught NullPointerException");
266         }
267         catch (NullPointerException ignored)
268         {
269         }
270         try
271         {
272             m.put("foo", new Object ());
273             fail("should have caught ClassCastException");
274         }
275         catch (ClassCastException 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 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 ignored)
312         {
313         }
314         try
315         {
316             m.remove(new Object ());
317             fail("should have caught ClassCastException");
318         }
319         catch (ClassCastException ignored)
320         {
321         }
322         assertNull(m.remove(new Integer (-1)));
323         try
324         {
325             m.remove("foo");
326             fail("should have caught ClassCastException");
327         }
328         catch (ClassCastException ignored)
329         {
330         }
331         for (int k = 0; k < nodes.length; k += 2)
332         {
333             Comparable 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 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 ignored)
374         {
375         }
376         m1 = new HashMap();
377         m1.put(new Object (), "bar");
378         try
379         {
380             m.putAll(m1);
381             fail("Should have caught ClassCastException");
382         }
383         catch (ClassCastException 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 ignored)
394         {
395         }
396         m1 = new HashMap();
397         m1.put("fubar", new Object ());
398         try
399         {
400             m.putAll(m1);
401             fail("Should have caught ClassCastException");
402         }
403         catch (ClassCastException 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 ignored)
493         {
494         }
495         try
496         {
497             s.remove(new Object ());
498             fail("should have caught ClassCastException");
499         }
500         catch (ClassCastException ignored)
501         {
502         }
503         for (int k = 0; k < nodes.length; k++)
504         {
505             Comparable 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 (-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 (-55));
529         try
530         {
531             m.keySet().addAll(c1);
532             fail("should have caught exception of addAll()");
533         }
534         catch (UnsupportedOperationException 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 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 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 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