1   /*
2    * $Id: TSTSubMapTest.java 208 2010-11-16 18:29:22Z roland $
3    * Copyright (C) 2007 Roland Krueger
4    * Created on 19.01.2010
5    *
6    * Author: Roland Krueger (www.rolandkrueger.info)
7    *
8    * This file is part of RoKlib.
9    *
10   * This library is free software; you can redistribute it and/or
11   * modify it under the terms of the GNU Lesser General Public License
12   * as published by the Free Software Foundation; either version 2.1 of
13   * the License, or (at your option) any later version.
14   *
15   * This library is distributed in the hope that it will be useful, but
16   * WITHOUT ANY WARRANTY; without even the implied warranty of
17   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18   * Lesser General Public License for more details.
19   *
20   * You should have received a copy of the GNU Lesser General Public
21   * License along with this library; if not, write to the Free Software
22   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
23   * USA
24   */
25  package info.rolandkrueger.roklib.util.tstmap.test;
26  
27  import static junit.framework.Assert.*;
28  import info.rolandkrueger.roklib.util.TernarySearchTreeMap;
29  
30  import java.util.ArrayList;
31  import java.util.Arrays;
32  import java.util.Collection;
33  import java.util.HashMap;
34  import java.util.HashSet;
35  import java.util.Iterator;
36  import java.util.List;
37  import java.util.Map;
38  import java.util.Set;
39  import java.util.SortedMap;
40  
41  import org.junit.Before;
42  import org.junit.Ignore;
43  import org.junit.Test;
44  
45  public class TSTSubMapTest
46  {
47    private final static String A = "aaa";
48    private final static String B = "bbb";
49    private final static String C = "ccc";
50    private final static String D = "ddd";
51    private final static String E = "eee";
52    private final static String F = "fff";
53    private final static String G = "ggg";
54  
55    private TernarySearchTreeMap<String> mTestObj;
56  
57    // TODO: test removing boundary values
58    // TODO: test submaps of submaps
59  
60    @Before
61    public void setUp ()
62    {
63      mTestObj = new TernarySearchTreeMap<String> ();
64      mTestObj.put ("", "EMPTY");
65      mTestObj.put (D, D.toUpperCase ());
66      mTestObj.put (F, F.toUpperCase ());
67      mTestObj.put (C, C.toUpperCase ());
68      mTestObj.put (B, B.toUpperCase ());
69      mTestObj.put (A, A.toUpperCase ());
70      mTestObj.put (G, G.toUpperCase ());
71      mTestObj.put (E, E.toUpperCase ());
72    }
73  
74    @Test (expected=IllegalArgumentException.class)
75    public void testSubMapInvalidArguments ()
76    {
77      mTestObj.subMap (F, A);
78    }
79    
80    @Test
81    public void testSubMapGetComparator ()
82    {
83      assertEquals (mTestObj.comparator (), mTestObj.subMap (A, B).comparator ());
84    }
85    
86    @Test
87    public void testFirstKeyFromSubMap_EndpointsInMap ()
88    {
89      // low endpoint is contained in submap
90      assertEquals ("aaa", mTestObj.subMap (A, D).firstKey ());
91    }
92    
93    @Test
94    public void testLastKeyFromSubMap_EndpointsInMap ()
95    {
96      // high endpoint is not contained in the submap
97      assertEquals ("ccc", mTestObj.subMap (A, D).lastKey ());
98    }
99    
100   @Test
101   public void testFirstKeyFromSubMap_EndpointsNotInMap ()
102   {
103     // low endpoint is contained in submap
104     assertEquals ("aaa", mTestObj.subMap ("a", "faaaa").firstKey ());
105   }
106   
107   @Test
108   public void testLastKeyFromSubMap_EndpointsNotInMap ()
109   {
110     // high endpoint is not contained in the submap
111     assertEquals ("eee", mTestObj.subMap ("a", "faaaa").lastKey ());
112   }
113   
114   @Test
115   public void testFirstKeyWithEmptyMap ()
116   {
117     mTestObj.clear ();
118     assertNull (mTestObj.subMap ("ab", "xy").firstKey ());
119   }
120   
121   @Test
122   public void testLastKeyWithEmptyMap ()
123   {
124     mTestObj.clear ();
125     assertNull (mTestObj.subMap ("ab", "xy").lastKey ());
126   }
127   
128   @Test
129   public void testFirstKeyWithEmptySubMap ()
130   {
131     assertNull (mTestObj.subMap ("vvv", "xxx").firstKey ());
132   }
133   
134   @Test
135   public void testLastKeyWithEmptySubMap ()
136   {
137     assertNull (mTestObj.subMap ("vvv", "xxx").lastKey ());
138   }
139   
140   @Test
141   public void testSize_EndpointsInMap ()
142   {
143     assertEquals (3, mTestObj.subMap (A, D).size ());
144   }
145   
146   @Test
147   public void testSize_EndpointsNotInMap ()
148   {
149     assertEquals (4, mTestObj.subMap ("abbb", "faaaa").size ());
150   }
151   
152   @Test
153   public void testSizeForEmptyBaseMap ()
154   {
155     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, "dumbo");
156     mTestObj.clear ();
157     assertEquals (0, subMap.size ());
158   }
159   
160   @Test
161   public void testValues_EndpointsInMap ()
162   {
163     List<String> valueList = new ArrayList<String> (mTestObj.subMap (B, D).values ());
164     Collection<String> expectedValues = Arrays.asList ("BBB", "CCC");
165     assertEquals (expectedValues, valueList);
166   }
167   
168   @Test
169   public void testValues_EndpointsNotInMap ()
170   {
171     List<String> valueList = new ArrayList<String> (mTestObj.subMap ("abbb", "faaaa").values ());
172     Collection<String> expectedValues = Arrays.asList ("BBB", "CCC", "DDD", "EEE");
173     assertEquals (expectedValues, valueList);
174     assertEquals (mTestObj.subMap ("ab", "fa"), mTestObj.subMap (B, F));
175   }
176   
177   @Test (expected=UnsupportedOperationException.class)
178   public void testValuesAddNotSupported ()
179   {
180     mTestObj.subMap ("ab", F).values ().add (null);
181   }
182   
183   @Test (expected=UnsupportedOperationException.class)
184   public void testValuesAddAllNotSupported ()
185   {
186     mTestObj.subMap ("ab", F).values ().addAll (null);
187   }
188   
189   @Test
190   public void testValuesRemove ()
191   {
192     Collection<String> values = mTestObj.subMap (C, E).values ();
193     assertFalse (values.remove (A.toUpperCase ()));
194     assertFalse (values.remove (F.toUpperCase ()));
195     assertTrue (values.remove (D.toUpperCase ()));
196     assertFalse (mTestObj.containsValue (D.toUpperCase ()));
197   }
198   
199   @Test
200   public void testValuesClear ()
201   {
202     Collection<String> values = mTestObj.subMap (C, E).values ();
203     values.clear ();
204     assertEquals (0, values.size ());
205     assertEquals (6, mTestObj.size ());
206     assertFalse (mTestObj.containsKey (C));
207     assertFalse (mTestObj.containsKey (D));
208     assertTrue  (mTestObj.containsKey (E));
209   }
210   
211   @Test
212   public void testValuesContains ()
213   {
214     Collection<String> values = mTestObj.subMap (C, E).values ();
215     assertFalse (values.contains (B.toUpperCase ()));
216     assertTrue  (values.contains (C.toUpperCase ()));
217     assertTrue  (values.contains (D.toUpperCase ()));
218     assertFalse (values.contains (E.toUpperCase ()));
219   }
220   
221   @Test
222   public void testSubMapWithEqualBoundaries ()
223   {
224     assertTrue (mTestObj.subMap (D, D).isEmpty ());
225   }
226   
227   @Test
228   public void testClearSubMapChangesMap ()
229   {
230     Map<CharSequence, String> expected = new HashMap<CharSequence, String> ();
231     expected.putAll (mTestObj);
232     expected.remove (A);
233     expected.remove (B);
234     mTestObj.subMap (A, C).clear ();
235     assertEquals (expected, mTestObj);
236     assertTrue (mTestObj.subMap (A, C).isEmpty ());
237   }
238   
239   @Test
240   public void testClearSubMapWithEqualBoundariesDoesntChangeMap ()
241   {
242     Map<CharSequence, String> expected = new HashMap<CharSequence, String> ();
243     expected.putAll (mTestObj);
244     mTestObj.subMap (D, D).clear ();
245     assertEquals (expected, mTestObj);
246   }
247   
248   @Test
249   public void testClearDisjunctSubMapDoesntChangeMap ()
250   {
251     Map<CharSequence, String> expected = new HashMap<CharSequence, String> ();
252     expected.putAll (mTestObj);
253     mTestObj.subMap ("xxx", "zzz").clear ();
254     assertEquals (expected, mTestObj);
255   }
256   
257   @Test (expected = NullPointerException.class)
258   public void testSubMapWithNullFromKey ()
259   {
260     mTestObj.subMap (null, C);
261   }
262   
263   @Test (expected = NullPointerException.class)
264   public void testSubMapWithNullToKey ()
265   {
266     mTestObj.subMap (C, null);
267   }
268   
269   @Test
270   public void testContainsKeyWithEmptyStringKey ()
271   {
272     SortedMap<CharSequence, String> subMap = mTestObj.subMap ("", "dumbo");
273     assertTrue (subMap.containsKey (""));
274   }
275 
276   @Test
277   public void testContainsKey ()
278   {
279     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, "dumbo");
280     assertFalse (subMap.containsKey (""));
281     assertTrue (subMap.containsKey (C));
282     assertTrue (subMap.containsKey (D));
283     assertFalse (subMap.containsKey (E));
284     assertFalse (subMap.containsKey (A));
285     assertFalse (subMap.containsKey (B));
286     assertFalse (subMap.containsKey ("dumbo"));
287     
288     // add new key to base map, which falls into the range of the submap
289     mTestObj.put ("cd", "CD");
290     assertTrue (subMap.containsKey ("cd"));
291   }
292   
293   @Test
294   public void testContainsValue ()
295   {
296     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, "dumbo");
297     assertTrue (subMap.containsValue (C.toUpperCase ()));
298     assertTrue (subMap.containsValue (D.toUpperCase ()));
299     assertFalse (subMap.containsValue (E.toUpperCase ()));
300     assertFalse (subMap.containsValue (A.toUpperCase ()));
301     assertFalse (subMap.containsValue (B.toUpperCase ()));
302     
303  // add new key to base map, which falls into the range of the submap
304     mTestObj.put ("cd", "CD");
305     assertTrue (subMap.containsValue ("CD"));
306   }
307   
308   @Test
309   public void testGet ()
310   {
311     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, "dumbo");
312     assertEquals (C.toUpperCase (), subMap.get (C));
313     assertEquals (D.toUpperCase (), subMap.get (D));
314     assertNull (subMap.get (A));
315     assertNull (subMap.get (E));
316   }
317   
318   @Test
319   public void testIsEmpty ()
320   {
321     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, "dumbo");
322     assertFalse (subMap.isEmpty ());
323     subMap.clear ();
324     assertTrue (subMap.isEmpty ());
325     assertTrue (mTestObj.subMap ("xxx", "yyy").isEmpty ());
326   }
327   
328   @Test
329   public void testPut ()
330   {
331     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, G);
332     subMap.put ("fargo", "jesses");
333     assertTrue (mTestObj.containsKey ("fargo"));
334     assertTrue (mTestObj.containsValue ("jesses"));
335     assertTrue (subMap.containsKey ("fargo"));
336     assertTrue (subMap.containsValue ("jesses"));
337   }
338   
339   @Test (expected=IllegalArgumentException.class)
340   public void testPutOutsideRange ()
341   {
342     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, G);
343     subMap.put ("illegal", "argument");
344   }
345   
346   @Test
347   public void testPutAll ()
348   {
349     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, G);
350     Map<CharSequence, String> map = new HashMap<CharSequence, String> ();
351     map.put ("dumbo", "elephant");
352     map.put ("elephant", "man");
353     subMap.putAll (map);
354     assertTrue (mTestObj.containsKey ("dumbo"));
355     assertTrue (mTestObj.containsKey ("elephant"));
356     assertTrue (mTestObj.containsValue ("elephant"));
357     assertTrue (mTestObj.containsValue ("man"));
358   }
359   
360   @Test
361   public void testRemove ()
362   {
363     SortedMap<CharSequence, String> subMap = mTestObj.subMap (C, F);
364     String value = subMap.remove (E);
365     assertEquals (E.toUpperCase (), value);
366     assertFalse (subMap.containsKey (E));
367     assertFalse (mTestObj.containsKey (E));
368     
369     // remove keys from outside the boundaries of the submap
370     assertNull (subMap.remove (A));
371     assertTrue (mTestObj.containsKey (A));
372     assertNull (subMap.remove (F));
373     assertTrue (mTestObj.containsKey (F));    
374   }
375   
376   @Test (expected = NullPointerException.class)
377   public void testRemoveNullKey ()
378   {
379     mTestObj.subMap (A, C).remove (null);
380   }
381   
382   @Test
383   public void testKeySet ()
384   {
385     SortedMap<CharSequence, String> subMap = mTestObj.subMap ("baaa", "dzzz");
386     Set<CharSequence> keySet = subMap.keySet ();
387     assertEquals (subMap.size (), keySet.size ());
388     Set<CharSequence> expectedSet = new HashSet<CharSequence> (Arrays.asList (B, C, D));
389     assertEquals (expectedSet, keySet);
390   }
391   
392   @Test (expected=UnsupportedOperationException.class)
393   public void testKeySetAdd ()
394   {
395     mTestObj.subMap ("baaa", "dzzz").keySet ().add (null);
396   }
397   
398   @Test (expected=UnsupportedOperationException.class)
399   public void testKeySetAddAll ()
400   {
401     mTestObj.subMap ("baaa", "dzzz").keySet ().addAll (null);
402   }
403   
404   @Test
405   public void testKeySetClear ()
406   {
407     Set<CharSequence> keySet = mTestObj.subMap ("baaa", "dzzz").keySet ();
408     keySet.clear ();
409     assertTrue (keySet.isEmpty ());
410     assertTrue  (mTestObj.containsKey (A));
411     assertFalse (mTestObj.containsKey (B));
412     assertFalse (mTestObj.containsKey (C));
413     assertFalse (mTestObj.containsKey (D));
414     assertTrue  (mTestObj.containsKey (E));
415     assertTrue  (mTestObj.containsKey (F));
416     assertTrue  (mTestObj.containsKey (G));
417   }
418   
419   @Test
420   public void testKeySetContains ()
421   {
422     Set<CharSequence> keySet = mTestObj.subMap ("baaa", "dzzz").keySet ();
423     assertFalse (keySet.contains (""));
424     assertFalse (keySet.contains (A));
425     assertTrue  (keySet.contains (B));
426     assertTrue  (keySet.contains (C));
427     assertTrue  (keySet.contains (D));
428     assertFalse (keySet.contains (E));
429     assertFalse (keySet.contains (F));
430     assertFalse (keySet.contains (G));
431   }
432   
433   @Test
434   public void testKeySetContainsAll ()
435   {
436     Set<CharSequence> keySet = mTestObj.subMap ("baaa", "dzzz").keySet ();
437     assertTrue (keySet.containsAll (Arrays.asList (B, C, D)));
438     assertFalse (keySet.containsAll (Arrays.asList (A, E, F, G)));
439   }
440   
441   @Test
442   public void testKeySetIsEmpty ()
443   {
444     assertFalse (mTestObj.subMap ("baaa", "dzzz").keySet ().isEmpty ());
445     assertTrue  (mTestObj.subMap ("xxx", "zzz").keySet ().isEmpty ());
446   }
447   
448   @Test
449   public void testKeySetIterator ()
450   {
451     Iterator<CharSequence> it = mTestObj.subMap ("baaa", "dzzz").keySet ().iterator ();
452     assertTrue (it.hasNext ());
453     assertEquals (B, it.next ());
454     assertTrue (it.hasNext ());
455     assertEquals (C, it.next ());
456     assertTrue (it.hasNext ());
457     assertEquals (D, it.next ());
458     assertFalse (it.hasNext ());
459   }
460   
461   @Test
462   public void testKeySetRemove ()
463   {
464     Set<CharSequence> keySet = mTestObj.subMap ("baaa", "dzzz").keySet ();
465     assertTrue (mTestObj.containsKey (C));
466     assertTrue (keySet.remove (C));
467     assertFalse (mTestObj.containsKey (C));
468     assertFalse (keySet.remove (G));
469     assertTrue (mTestObj.containsKey (G));
470   }
471   
472   @Test
473   public void testKeySetRemoveAll ()
474   {
475     Set<CharSequence> keySet = mTestObj.subMap ("baaa", "dzzz").keySet ();
476     // remove keys A, B, and C. Only B and C are expected to be contained by the key set
477     assertTrue (keySet.removeAll (Arrays.asList (A, B, C)));
478     assertFalse (keySet.removeAll (Arrays.asList (A, B, C)));
479     assertFalse (keySet.removeAll (Arrays.asList (G, F)));
480     assertEquals (1, keySet.size ());
481   }
482   
483   @Test
484   public void testKeySetRetainAll ()
485   {
486     Set<CharSequence> keySet = mTestObj.subMap ("baaa", "dzzz").keySet ();
487     assertEquals (3, keySet.size ());
488     assertTrue (keySet.retainAll (Arrays.asList (A, B, C)));
489     assertEquals (2, keySet.size ());
490     assertFalse (keySet.contains (A));
491     assertTrue  (keySet.contains (B));
492     assertTrue  (keySet.contains (C));
493     assertFalse (keySet.contains (D));
494     
495     keySet = mTestObj.subMap ("baaa", "dzzz").keySet ();
496     assertFalse (keySet.retainAll (Arrays.asList (B, C, D)));
497   }
498   
499   @Test
500   public void testEntrySet ()
501   {
502     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", "dzzz").entrySet ();
503     assertEquals (3, entrySet.size ());
504     Iterator<Map.Entry<CharSequence, String>> it = entrySet.iterator ();
505     assertTrue (it.hasNext ());
506     Map.Entry<CharSequence, String> entry = it.next ();
507     assertEquals (entry.getKey (), B);
508     assertEquals (entry.getValue (), B.toUpperCase ());
509     assertEquals (B.toUpperCase (), entry.setValue ("new value"));
510     assertTrue (it.hasNext ());
511     entry = it.next ();
512     assertEquals (entry.getKey (), C);
513     assertEquals (entry.getValue (), C.toUpperCase ());
514     assertEquals (C.toUpperCase (), entry.setValue ("new value"));
515     assertTrue (it.hasNext ());
516     entry = it.next ();
517     assertEquals (entry.getKey (), D);
518     assertEquals (entry.getValue (), D.toUpperCase ());
519     assertEquals (D.toUpperCase (), entry.setValue ("new value"));
520     assertFalse (it.hasNext ());
521     
522     assertEquals ("new value", mTestObj.get (B));
523     assertEquals ("new value", mTestObj.get (C));
524     assertEquals ("new value", mTestObj.get (D));
525   }
526   
527   @Test (expected = IllegalArgumentException.class)
528   public void testSetEntryValueNull ()
529   {
530     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", "dzzz").entrySet ();
531     Iterator<Map.Entry<CharSequence, String>> it = entrySet.iterator ();
532     Map.Entry<CharSequence, String> entry = it.next ();
533     entry.setValue (null);
534   }
535   
536   @Test (expected=UnsupportedOperationException.class)
537   public void testEntrySetAdd ()
538   {
539     mTestObj.subMap ("baaa", "dzzz").entrySet ().add (null);
540   }
541   
542   @Test (expected=UnsupportedOperationException.class)
543   public void testEntrySetAddAll ()
544   {
545     mTestObj.subMap ("baaa", "dzzz").entrySet ().addAll (null);
546   }
547   
548   @Test
549   public void testEntrySetClear ()
550   {
551     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", "dzzz").entrySet ();
552     assertEquals (3, entrySet.size ());
553     entrySet.clear ();
554     assertEquals (5, mTestObj.size ());
555     assertFalse (mTestObj.containsKey (B));
556     assertFalse (mTestObj.containsKey (C));
557     assertFalse (mTestObj.containsKey (D));
558   }
559   
560   @Test
561   public void testEntrySetContains ()
562   {
563     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", "dzzz").entrySet ();
564     assertEquals (3, entrySet.size ());
565     TernarySearchTreeMap<String> expected = new TernarySearchTreeMap<String> ();
566     expected.put (B, B.toUpperCase ());
567     expected.put (C, C.toUpperCase ());
568     expected.put (D, D.toUpperCase ());
569     TernarySearchTreeMap<String> notExpected = new TernarySearchTreeMap<String> ();
570     notExpected.put (A, A.toUpperCase ());
571     notExpected.put (E, E.toUpperCase ());
572     notExpected.put ("baaaa", "not in map");
573     notExpected.put (F, F.toUpperCase ());
574     notExpected.put (G, G.toUpperCase ());
575     for (Iterator<Map.Entry<CharSequence, String>> it = expected.entrySet ().iterator (); it.hasNext ();)
576     {
577       assertTrue (entrySet.contains (it.next ()));
578     }
579     for (Iterator<Map.Entry<CharSequence, String>> it = notExpected.entrySet ().iterator (); it.hasNext ();)
580     {
581       assertFalse (entrySet.contains (it.next ()));
582     }
583     assertFalse (entrySet.contains (mTestObj));
584   }
585   
586   @Test
587   public void testEntrySetContainsAll ()
588   {
589     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", "dzzz").entrySet ();
590     TernarySearchTreeMap<String> expected = new TernarySearchTreeMap<String> ();
591     expected.put (B, B.toUpperCase ());
592     expected.put (C, C.toUpperCase ());
593     expected.put (D, D.toUpperCase ());
594     TernarySearchTreeMap<String> notExpected = new TernarySearchTreeMap<String> ();
595     notExpected.put (A, A.toUpperCase ());
596     notExpected.put (E, E.toUpperCase ());
597     notExpected.put ("baaaa", "not in map");
598     notExpected.put (F, F.toUpperCase ());
599     notExpected.put (G, G.toUpperCase ());
600     assertTrue (entrySet.containsAll (expected.entrySet ()));
601     assertFalse (entrySet.containsAll (notExpected.entrySet ()));
602   }
603   
604   @Test
605   public void testEntrySetIsEmpty ()
606   {
607     assertFalse (mTestObj.subMap ("baaa", "dzzz").entrySet ().isEmpty ());
608     assertTrue  (mTestObj.subMap ("xxx", "zzz").entrySet ().isEmpty ());
609   }
610   
611   @Test
612   public void testEntrySetRemove ()
613   {
614     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", D).entrySet ();
615     assertFalse (entrySet.remove (mTestObj));
616     assertFalse (entrySet.remove (mTestObj.entrySet ().iterator ().next ()));
617     TernarySearchTreeMap<String> map = new TernarySearchTreeMap<String> ();
618     map.put (B, B.toUpperCase ());
619     Map.Entry<CharSequence, String> entry = map.entrySet ().iterator ().next ();
620     assertTrue (entrySet.remove (entry));
621     assertFalse (mTestObj.containsKey (B));
622     assertFalse (entrySet.contains (entry));
623     
624     // removing the upper bound of the entry set will not succeed
625     map.clear ();
626     map.put (D, D.toUpperCase ());
627     entry = map.entrySet ().iterator ().next ();
628     assertFalse (entrySet.remove (entry));
629     
630     map.clear ();
631     map.put ("caaa", "caaa");
632     entry = map.entrySet ().iterator ().next ();
633     assertFalse (entrySet.remove (entry));    
634   }
635   
636   @Test
637   public void testEntrySetRemoveAll ()
638   {
639     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", D).entrySet ();
640     TernarySearchTreeMap<String> map = new TernarySearchTreeMap<String> ();
641     map.put (B, B.toUpperCase ());
642     map.put ("not in map", "");
643     map.put (C, C.toUpperCase ());
644     assertTrue (entrySet.removeAll (map.entrySet ()));
645     assertFalse (mTestObj.containsKey (B));
646     assertFalse (mTestObj.containsKey (C));
647     
648     map.clear ();
649     map.put (D, D.toUpperCase ());
650     map.put (E, E.toUpperCase ());
651     assertFalse (entrySet.removeAll (map.entrySet ()));
652   }
653   
654   @Test
655   public void testEntrySetRetainAll ()
656   {
657     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", F).entrySet ();
658     TernarySearchTreeMap<String> map = new TernarySearchTreeMap<String> ();
659     map.put (B, B.toUpperCase ());
660     map.put ("not in map", "");
661     map.put (C, C.toUpperCase ());
662     
663     assertTrue (entrySet.retainAll (map.entrySet ()));
664     
665     map.put (D, D.toUpperCase ());
666     map.put (E, E.toUpperCase ());
667     assertFalse (entrySet.retainAll (map.entrySet ()));
668   }
669   
670   @Test
671   public void testEntrySetEquals ()
672   {
673     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", E).entrySet ();
674     Map<CharSequence, String> map = new HashMap<CharSequence, String> ();
675     map.put (B, B.toUpperCase ());
676     map.put (C, C.toUpperCase ());
677     map.put (D, D.toUpperCase ());
678     
679     assertTrue  (entrySet.equals (entrySet));
680     assertFalse (entrySet.equals (null));
681     assertTrue  (entrySet.equals (map.entrySet ()));
682     assertTrue  (map.entrySet ().equals (entrySet));
683     
684     map.put ("x", "y");
685     assertFalse (entrySet.equals (map.entrySet ()));
686     assertFalse (map.entrySet ().equals (entrySet));    
687   }
688   
689   @Test
690   public void testEntrySetHashCode ()
691   {
692     Set<Map.Entry<CharSequence, String>> entrySet = mTestObj.subMap ("baaa", E).entrySet ();
693     Map<CharSequence, String> map = new HashMap<CharSequence, String> ();
694     map.put (B, B.toUpperCase ());
695     map.put (C, C.toUpperCase ());
696     map.put (D, D.toUpperCase ());
697     
698     assertEquals (entrySet.hashCode (), map.entrySet ().hashCode ());
699     
700     map.put ("x", "y");
701     assertFalse (entrySet.hashCode () == map.entrySet ().hashCode ());
702   }
703   
704   @Test
705   public void testHeadMap ()
706   {
707     SortedMap<CharSequence, String> headMap = mTestObj.subMap (B, "dumbo").headMap (D);
708     assertEquals (2, headMap.size ());
709     assertTrue (headMap.containsKey (B));
710     assertTrue (headMap.containsKey (C));
711     assertFalse (headMap.containsKey (D));
712   }
713   
714   @Test (expected=IllegalArgumentException.class)
715   public void testHeadMapFailsLowerBound ()
716   {
717     mTestObj.subMap (B, "dumbo").headMap (A);
718   }
719   
720   @Test (expected=IllegalArgumentException.class)
721   public void testHeadMapFailsUpperBound ()
722   {
723     mTestObj.subMap (B, "dumbo").headMap (E);
724   }
725 
726   @Test
727   public void testAddToHeadMap ()
728   {
729     SortedMap<CharSequence, String> headMap = mTestObj.subMap (B, "dumbo").headMap (D);
730     headMap.put ("bcd", "bcd");
731     assertTrue (headMap.containsKey ("bcd"));
732     assertTrue (mTestObj.containsKey ("bcd"));
733   }
734   
735   @Test (expected=IllegalArgumentException.class)
736   public void testAddToHeadMapFails1 ()
737   {
738     SortedMap<CharSequence, String> headMap = mTestObj.subMap (B, "dumbo").headMap (D);
739     headMap.put ("a", "a");
740   }
741   
742   @Test (expected=IllegalArgumentException.class)
743   public void testAddToHeadMapFails2 ()
744   {
745     SortedMap<CharSequence, String> headMap = mTestObj.subMap (B, "dumbo").headMap (D);
746     headMap.put ("dzz", "dzz");
747   }
748   
749   @Test
750   public void testTailMap ()
751   {
752     SortedMap<CharSequence, String> tailMap = mTestObj.subMap (B, "dumbo").tailMap (C);
753     assertEquals (2, tailMap.size ());
754     assertFalse (tailMap.containsKey (B));
755     assertTrue (tailMap.containsKey (C));
756     assertTrue (tailMap.containsKey (D));
757   }
758   
759   @Test (expected=IllegalArgumentException.class)
760   public void testTailMapFailsLowerBound ()
761   {
762     mTestObj.subMap (B, "dumbo").tailMap (A);
763   }
764   
765   @Test (expected=IllegalArgumentException.class)
766   public void testTailMapFailsUpperBound ()
767   {
768     mTestObj.subMap (B, "dumbo").tailMap (E);
769   }
770   
771   @Test
772   public void testAddToTailMap ()
773   {
774     SortedMap<CharSequence, String> tailMap = mTestObj.subMap (B, "dumbo").tailMap (C);
775     tailMap.put ("ccd", "ccd");
776     assertTrue (tailMap.containsKey ("ccd"));
777     assertTrue (mTestObj.containsKey ("ccd"));
778   }
779   
780   @Test (expected=IllegalArgumentException.class)
781   public void testAddToTailMapFails1 ()
782   {
783     mTestObj.subMap (B, "dumbo").tailMap (C).put ("baa", "b");
784   }
785   
786   @Test (expected=IllegalArgumentException.class)
787   public void testAddToTailMapFails2 ()
788   {
789     mTestObj.subMap (B, "dumbo").tailMap (C).put ("dzzz", "z");
790   }
791   
792   @Test
793   public void testSubMapOfSubmap ()
794   {
795     SortedMap<CharSequence, String> subMap = mTestObj.subMap (B, "dumbo").subMap (C, D);
796     assertEquals (1, subMap.size ());
797     assertTrue   (subMap.containsKey (C));
798     assertFalse  (subMap.containsKey (D));
799   }
800   
801   @Test (expected=IllegalArgumentException.class)
802   public void testSubMapOfSubmapFail1 ()
803   {
804     mTestObj.subMap (B, "dumbo").subMap (A, D);
805   }
806   
807   @Test (expected=IllegalArgumentException.class)
808   public void testSubMapOfSubmapFail2 ()
809   {
810     mTestObj.subMap (B, "dumbo").subMap (C, F);
811   }
812   
813   @Test (expected=IllegalArgumentException.class)
814   public void testSubMapOfSubmapFail3 ()
815   {
816     mTestObj.subMap (B, "dumbo").subMap (A, F);
817   }
818   
819   
820 }