ViewVC Help

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

root/jsr166/jsr166/src/main/java/util/TreeMap.java

Comparing jsr166/src/main/java/util/TreeMap.java (file contents):
Revision 1.4 by dl, Tue Mar 22 01:30:10 2005 UTC vs.
Revision 1.8 by dl, Sat Apr 2 11:29:42 2005 UTC

#	Line 5 | Line 5
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
8	<	package java.util;
8	>	package java.util;
9
10
11		/**
12		* Red-Black tree based implementation of the <tt>NavigableMap</tt> interface.
13		* This class guarantees that the map will be in ascending key order, sorted
14	<	* according to the <i>natural order</i> for the key's class (see
14	>	* according to the <i>natural order</i> for the keys' class (see
15		* <tt>Comparable</tt>), or by the comparator provided at creation time,
16		* depending on which constructor is used.<p>
17		*
#	Line 61 | Line 61 | package java.util;
61		* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
62		* Therefore, it would be wrong to write a program that depended on this
63		* exception for its correctness:   <i>the fail-fast behavior of iterators
64	<	* should be used only to detect bugs.</i><p>
64	>	* should be used only to detect bugs.</i>
65		*
66		* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
67		* and its views represent snapshots of mappings at the time they were
#	Line 542 | Line 542 | public class TreeMap<K,V>
542		* @param key key with which the specified value is to be associated.
543		* @param value value to be associated with the specified key.
544		*
545	<	* @return previous value associated with specified key, or <tt>null</tt>
545	>	* @return the previous value associated with specified key, or <tt>null</tt>
546		*         if there was no mapping for key.  A <tt>null</tt> return can
547		*         also indicate that the map previously associated <tt>null</tt>
548		*         with the specified key.
#	Line 559 | Line 559 | public class TreeMap<K,V>
559		incrementSize();
560		root = new Entry<K,V>(key, value, null);
561		return null;
562	<	}
562	>	}
563
564		while (true) {
565		int cmp = compare(key, t.key);
#	Line 591 | Line 591 | public class TreeMap<K,V>
591		* Removes the mapping for this key from this TreeMap if present.
592		*
593		* @param  key key for which mapping should be removed
594	<	* @return previous value associated with specified key, or <tt>null</tt>
594	>	* @return the previous value associated with specified key, or <tt>null</tt>
595		*         if there was no mapping for key.  A <tt>null</tt> return can
596		*         also indicate that the map previously associated
597		*         <tt>null</tt> with the specified key.
#	Line 658 | Line 658 | public class TreeMap<K,V>
658		/**
659		* Returns a key-value mapping associated with the least
660		* key in this map, or <tt>null</tt> if the map is empty.
661	<	*
662	<	* @return an Entry with least key, or <tt>null</tt>
661	>	*
662	>	* @return an Entry with least key, or <tt>null</tt>
663		* if the map is empty.
664		*/
665		public Map.Entry<K,V> firstEntry() {
#	Line 670 | Line 670 | public class TreeMap<K,V>
670		/**
671		* Returns a key-value mapping associated with the greatest
672		* key in this map, or <tt>null</tt> if the map is empty.
673	<	* The returned entry does <em>not</em> support
674	<	* the <tt>Entry.setValue</tt> method.
675	<	*
673	>	*
674		* @return an Entry with greatest key, or <tt>null</tt>
675		* if the map is empty.
676		*/
#	Line 684 | Line 682 | public class TreeMap<K,V>
682		/**
683		* Removes and returns a key-value mapping associated with
684		* the least key in this map, or <tt>null</tt> if the map is empty.
685	<	*
685	>	*
686		* @return the removed first entry of this map, or <tt>null</tt>
687		* if the map is empty.
688		*/
689		public Map.Entry<K,V> pollFirstEntry() {
690		Entry<K,V> p = getFirstEntry();
691	<	if (p == null)
691	>	if (p == null)
692		return null;
693		Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
694		deleteEntry(p);
#	Line 700 | Line 698 | public class TreeMap<K,V>
698		/**
699		* Removes and returns a key-value mapping associated with
700		* the greatest key in this map, or <tt>null</tt> if the map is empty.
701	<	*
701	>	*
702		* @return the removed last entry of this map, or <tt>null</tt>
703		* if the map is empty.
704		*/
705		public Map.Entry<K,V> pollLastEntry() {
706		Entry<K,V> p = getLastEntry();
707	<	if (p == null)
707	>	if (p == null)
708		return null;
709		Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
710		deleteEntry(p);
#	Line 716 | Line 714 | public class TreeMap<K,V>
714		/**
715		* Returns a key-value mapping associated with the least key
716		* greater than or equal to the given key, or <tt>null</tt> if
717	<	* there is no such entry.
718	<	*
717	>	* there is no such entry.
718	>	*
719		* @param key the key.
720		* @return an Entry associated with ceiling of given key, or
721		* <tt>null</tt> if there is no such Entry.
#	Line 736 | Line 734 | public class TreeMap<K,V>
734		/**
735		* Returns least key greater than or equal to the given key, or
736		* <tt>null</tt> if there is no such key.
737	<	*
737	>	*
738		* @param key the key.
739		* @return the ceiling key, or <tt>null</tt>
740		* if there is no such key.
#	Line 756 | Line 754 | public class TreeMap<K,V>
754		/**
755		* Returns a key-value mapping associated with the greatest key
756		* less than or equal to the given key, or <tt>null</tt> if there
757	<	* is no such entry.
758	<	*
757	>	* is no such entry.
758	>	*
759		* @param key the key.
760		* @return an Entry associated with floor of given key, or <tt>null</tt>
761		* if there is no such Entry.
#	Line 776 | Line 774 | public class TreeMap<K,V>
774		* Returns the greatest key
775		* less than or equal to the given key, or <tt>null</tt> if there
776		* is no such key.
777	<	*
777	>	*
778		* @param key the key.
779		* @return the floor of given key, or <tt>null</tt> if there is no
780		* such key.
#	Line 794 | Line 792 | public class TreeMap<K,V>
792		/**
793		* Returns a key-value mapping associated with the least key
794		* strictly greater than the given key, or <tt>null</tt> if there
795	<	* is no such entry.
796	<	*
795	>	* is no such entry.
796	>	*
797		* @param key the key.
798		* @return an Entry with least key greater than the given key, or
799		* <tt>null</tt> if there is no such Entry.
#	Line 813 | Line 811 | public class TreeMap<K,V>
811		/**
812		* Returns the least key strictly greater than the given key, or
813		* <tt>null</tt> if there is no such key.
814	<	*
814	>	*
815		* @param key the key.
816		* @return the least key greater than the given key, or
817		* <tt>null</tt> if there is no such key.
#	Line 831 | Line 829 | public class TreeMap<K,V>
829		/**
830		* Returns a key-value mapping associated with the greatest
831		* key strictly less than the given key, or <tt>null</tt> if there is no
832	<	* such entry.
833	<	*
832	>	* such entry.
833	>	*
834		* @param key the key.
835		* @return an Entry with greatest key less than the given
836		* key, or <tt>null</tt> if there is no such Entry.
#	Line 850 | Line 848 | public class TreeMap<K,V>
848		/**
849		* Returns the greatest key strictly less than the given key, or
850		* <tt>null</tt> if there is no such key.
851	<	*
851	>	*
852		* @param key the key.
853		* @return the greatest key less than the given
854		* key, or <tt>null</tt> if there is no such key.
#	Line 874 | Line 872 | public class TreeMap<K,V>
872		*/
873		private transient Set<Map.Entry<K,V>> entrySet = null;
874		private transient Set<Map.Entry<K,V>> descendingEntrySet = null;
875	<	private transient Set<K> descendingKeySet = null;
875	>	private transient Set<K> descendingKeySet = null;
876
877		transient Set<K> keySet = null;        // XXX remove when integrated
878		transient Collection<V> values = null; // XXX remove when integrated
#	Line 900 | Line 898 | public class TreeMap<K,V>
898		public Iterator<K> iterator() {
899		return new KeyIterator(getFirstEntry());
900		}
901	<
901	>
902		public int size() {
903		return TreeMap.this.size();
904		}
905	<
905	>
906		public boolean contains(Object o) {
907		return containsKey(o);
908		}
909	<
909	>
910		public boolean remove(Object o) {
911		int oldSize = size;
912		TreeMap.this.remove(o);
913		return size != oldSize;
914		}
915	<
915	>
916		public void clear() {
917		TreeMap.this.clear();
918		}
#	Line 942 | Line 940 | public class TreeMap<K,V>
940		public Iterator<V> iterator() {
941		return new ValueIterator(getFirstEntry());
942		}
943	<
943	>
944		public int size() {
945		return TreeMap.this.size();
946		}
947	<
947	>
948		public boolean contains(Object o) {
949		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
950		if (valEquals(e.getValue(), o))
951		return true;
952		return false;
953		}
954	<
954	>
955		public boolean remove(Object o) {
956		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
957		if (valEquals(e.getValue(), o)) {
#	Line 963 | Line 961 | public class TreeMap<K,V>
961		}
962		return false;
963		}
964	<
964	>
965		public void clear() {
966		TreeMap.this.clear();
967		}
#	Line 992 | Line 990 | public class TreeMap<K,V>
990		public Iterator<Map.Entry<K,V>> iterator() {
991		return new EntryIterator(getFirstEntry());
992		}
993	<
993	>
994		public boolean contains(Object o) {
995		if (!(o instanceof Map.Entry))
996		return false;
#	Line 1001 | Line 999 | public class TreeMap<K,V>
999		Entry<K,V> p = getEntry(entry.getKey());
1000		return p != null && valEquals(p.getValue(), value);
1001		}
1002	<
1002	>
1003		public boolean remove(Object o) {
1004		if (!(o instanceof Map.Entry))
1005		return false;
#	Line 1014 | Line 1012 | public class TreeMap<K,V>
1012		}
1013		return false;
1014		}
1015	<
1015	>
1016		public int size() {
1017		return TreeMap.this.size();
1018		}
1019	<
1019	>
1020		public void clear() {
1021		TreeMap.this.clear();
1022		}
#	Line 1036 | Line 1034 | public class TreeMap<K,V>
1034		* operations.  It does not support the <tt>add</tt> or
1035		* <tt>addAll</tt> operations.
1036		*
1037	<	* @return a set view of the mappings contained in this map, in
1037	>	* @return a set view of the mappings contained in this map, in
1038		* descending key order
1039		* @see Map.Entry
1040		*/
#	Line 1145 | Line 1143 | public class TreeMap<K,V>
1143		* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1144		* to <tt>high</tt>:
1145		* <pre>
1146	<	*     NavigableMap head = m.headMap(high+"\0");
1146	>	*     NavigableMap head = m.navigableHeadMap(high+"\0");
1147		* </pre>
1148		*
1149		* @param toKey high endpoint (exclusive) of the headMap.
#	Line 1185 | Line 1183 | public class TreeMap<K,V>
1183		* are strings.  The following idiom obtains a view containing
1184		* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1185		* greater than <tt>low</tt>: <pre>
1186	<	*     NavigableMap tail = m.tailMap(low+"\0");
1186	>	*     NavigableMap tail = m.navigableTailMap(low+"\0");
1187		* </pre>
1188		*
1189		* @param fromKey low endpoint (inclusive) of the tailMap.
#	Line 1310 | Line 1308 | public class TreeMap<K,V>
1308		}
1309
1310		public boolean isEmpty() {
1311	<	return entrySet.isEmpty();
1311	>	return entrySet().isEmpty();
1312		}
1313
1314		public boolean containsKey(Object key) {
#	Line 1356 | Line 1354 | public class TreeMap<K,V>
1354		}
1355
1356		public Map.Entry<K,V> firstEntry() {
1357	<	TreeMap.Entry<K,V> e = fromStart ?
1357	>	TreeMap.Entry<K,V> e = fromStart ?
1358		getFirstEntry() : getCeilingEntry(fromKey);
1359		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1360		return null;
#	Line 1364 | Line 1362 | public class TreeMap<K,V>
1362		}
1363
1364		public Map.Entry<K,V> lastEntry() {
1365	<	TreeMap.Entry<K,V> e = toEnd ?
1365	>	TreeMap.Entry<K,V> e = toEnd ?
1366		getLastEntry() : getLowerEntry(toKey);
1367		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1368		return null;
#	Line 1372 | Line 1370 | public class TreeMap<K,V>
1370		}
1371
1372		public Map.Entry<K,V> pollFirstEntry() {
1373	<	TreeMap.Entry<K,V> e = fromStart ?
1373	>	TreeMap.Entry<K,V> e = fromStart ?
1374		getFirstEntry() : getCeilingEntry(fromKey);
1375	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1375	>	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1376		return null;
1377		Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1378		deleteEntry(e);
#	Line 1382 | Line 1380 | public class TreeMap<K,V>
1380		}
1381
1382		public Map.Entry<K,V> pollLastEntry() {
1383	<	TreeMap.Entry<K,V> e = toEnd ?
1383	>	TreeMap.Entry<K,V> e = toEnd ?
1384		getLastEntry() : getLowerEntry(toKey);
1385	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1385	>	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1386		return null;
1387		Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1388		deleteEntry(e);
#	Line 1464 | Line 1462 | public class TreeMap<K,V>
1462		return e == null? null : e.key;
1463		}
1464
1465	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1465	>	private transient Set<Map.Entry<K,V>> entrySet = null;
1466
1467		public Set<Map.Entry<K,V>> entrySet() {
1468	<	return entrySet;
1468	>	Set<Map.Entry<K,V>> es = entrySet;
1469	>	return (es != null)? es : (entrySet = new EntrySetView());
1470		}
1471
1472		private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
#	Line 1524 | Line 1523 | public class TreeMap<K,V>
1523		}
1524
1525		private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1526	<	private transient Set<K> descendingKeySetView = null;
1526	>	private transient Set<K> descendingKeySetView = null;
1527
1528		public Set<Map.Entry<K,V>> descendingEntrySet() {
1529		Set<Map.Entry<K,V>> es = descendingEntrySetView;
#	Line 1548 | Line 1547 | public class TreeMap<K,V>
1547		public Iterator<K> iterator() {
1548		return new Iterator<K>() {
1549		private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1550	<
1550	>
1551		public boolean hasNext() { return i.hasNext(); }
1552		public K next() { return i.next().getKey(); }
1553		public void remove() { i.remove(); }
1554		};
1555		}
1556	<
1556	>
1557		public int size() {
1558		return SubMap.this.size();
1559		}
1560	<
1560	>
1561		public boolean contains(Object k) {
1562		return SubMap.this.containsKey(k);
1563		}
#	Line 2164 | Line 2163 | public class TreeMap<K,V>
2163		// Write out size (number of Mappings)
2164		s.writeInt(size);
2165
2166	+	Set<Map.Entry<K,V>> es = entrySet();
2167		// Write out keys and values (alternating)
2168	<	for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2168	>	for (Iterator<Map.Entry<K,V>> i = es.iterator(); i.hasNext(); ) {
2169		Map.Entry<K,V> e = i.next();
2170		s.writeObject(e.getKey());
2171		s.writeObject(e.getValue());

Diff Legend

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