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.5 by dl, Tue Mar 22 16:48:32 2005 UTC vs.
Revision 1.10 by jsr166, Mon Apr 18 05:18:29 2005 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
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 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;
878	<
879	<	transient Set<K> keySet = null;        // XXX remove when integrated
880	<	transient Collection<V> values = null; // XXX remove when integrated
875	>	private transient Set<K> descendingKeySet = null;
876
877		/**
878		* Returns a Set view of the keys contained in this map.  The set's
#	Line 900 | Line 895 | public class TreeMap<K,V>
895		public Iterator<K> iterator() {
896		return new KeyIterator(getFirstEntry());
897		}
898	<
898	>
899		public int size() {
900		return TreeMap.this.size();
901		}
902	<
902	>
903		public boolean contains(Object o) {
904		return containsKey(o);
905		}
906	<
906	>
907		public boolean remove(Object o) {
908		int oldSize = size;
909		TreeMap.this.remove(o);
910		return size != oldSize;
911		}
912	<
912	>
913		public void clear() {
914		TreeMap.this.clear();
915		}
#	Line 942 | Line 937 | public class TreeMap<K,V>
937		public Iterator<V> iterator() {
938		return new ValueIterator(getFirstEntry());
939		}
940	<
940	>
941		public int size() {
942		return TreeMap.this.size();
943		}
944	<
944	>
945		public boolean contains(Object o) {
946		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
947		if (valEquals(e.getValue(), o))
948		return true;
949		return false;
950		}
951	<
951	>
952		public boolean remove(Object o) {
953		for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
954		if (valEquals(e.getValue(), o)) {
#	Line 963 | Line 958 | public class TreeMap<K,V>
958		}
959		return false;
960		}
961	<
961	>
962		public void clear() {
963		TreeMap.this.clear();
964		}
#	Line 992 | Line 987 | public class TreeMap<K,V>
987		public Iterator<Map.Entry<K,V>> iterator() {
988		return new EntryIterator(getFirstEntry());
989		}
990	<
990	>
991		public boolean contains(Object o) {
992		if (!(o instanceof Map.Entry))
993		return false;
#	Line 1001 | Line 996 | public class TreeMap<K,V>
996		Entry<K,V> p = getEntry(entry.getKey());
997		return p != null && valEquals(p.getValue(), value);
998		}
999	<
999	>
1000		public boolean remove(Object o) {
1001		if (!(o instanceof Map.Entry))
1002		return false;
#	Line 1014 | Line 1009 | public class TreeMap<K,V>
1009		}
1010		return false;
1011		}
1012	<
1012	>
1013		public int size() {
1014		return TreeMap.this.size();
1015		}
1016	<
1016	>
1017		public void clear() {
1018		TreeMap.this.clear();
1019		}
#	Line 1036 | Line 1031 | public class TreeMap<K,V>
1031		* operations.  It does not support the <tt>add</tt> or
1032		* <tt>addAll</tt> operations.
1033		*
1034	<	* @return a set view of the mappings contained in this map, in
1034	>	* @return a set view of the mappings contained in this map, in
1035		* descending key order
1036		* @see Map.Entry
1037		*/
#	Line 1145 | Line 1140 | public class TreeMap<K,V>
1140		* the key-value mappings in <tt>m</tt> whose keys are less than or equal
1141		* to <tt>high</tt>:
1142		* <pre>
1143	<	*     NavigableMap head = m.headMap(high+"\0");
1143	>	*     NavigableMap head = m.navigableHeadMap(high+"\0");
1144		* </pre>
1145		*
1146		* @param toKey high endpoint (exclusive) of the headMap.
#	Line 1185 | Line 1180 | public class TreeMap<K,V>
1180		* are strings.  The following idiom obtains a view containing
1181		* all of the key-value mappings in <tt>m</tt> whose keys are strictly
1182		* greater than <tt>low</tt>: <pre>
1183	<	*     NavigableMap tail = m.tailMap(low+"\0");
1183	>	*     NavigableMap tail = m.navigableTailMap(low+"\0");
1184		* </pre>
1185		*
1186		* @param fromKey low endpoint (inclusive) of the tailMap.
#	Line 1310 | Line 1305 | public class TreeMap<K,V>
1305		}
1306
1307		public boolean isEmpty() {
1308	<	return entrySet.isEmpty();
1308	>	return entrySet().isEmpty();
1309		}
1310
1311		public boolean containsKey(Object key) {
#	Line 1356 | Line 1351 | public class TreeMap<K,V>
1351		}
1352
1353		public Map.Entry<K,V> firstEntry() {
1354	<	TreeMap.Entry<K,V> e = fromStart ?
1354	>	TreeMap.Entry<K,V> e = fromStart ?
1355		getFirstEntry() : getCeilingEntry(fromKey);
1356		if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1357		return null;
#	Line 1364 | Line 1359 | public class TreeMap<K,V>
1359		}
1360
1361		public Map.Entry<K,V> lastEntry() {
1362	<	TreeMap.Entry<K,V> e = toEnd ?
1362	>	TreeMap.Entry<K,V> e = toEnd ?
1363		getLastEntry() : getLowerEntry(toKey);
1364		if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1365		return null;
#	Line 1372 | Line 1367 | public class TreeMap<K,V>
1367		}
1368
1369		public Map.Entry<K,V> pollFirstEntry() {
1370	<	TreeMap.Entry<K,V> e = fromStart ?
1370	>	TreeMap.Entry<K,V> e = fromStart ?
1371		getFirstEntry() : getCeilingEntry(fromKey);
1372	<	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1372	>	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1373		return null;
1374		Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1375		deleteEntry(e);
#	Line 1382 | Line 1377 | public class TreeMap<K,V>
1377		}
1378
1379		public Map.Entry<K,V> pollLastEntry() {
1380	<	TreeMap.Entry<K,V> e = toEnd ?
1380	>	TreeMap.Entry<K,V> e = toEnd ?
1381		getLastEntry() : getLowerEntry(toKey);
1382	<	if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
1382	>	if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
1383		return null;
1384		Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
1385		deleteEntry(e);
#	Line 1464 | Line 1459 | public class TreeMap<K,V>
1459		return e == null? null : e.key;
1460		}
1461
1462	<	private transient Set<Map.Entry<K,V>> entrySet = new EntrySetView();
1462	>	private transient Set<Map.Entry<K,V>> entrySet = null;
1463
1464		public Set<Map.Entry<K,V>> entrySet() {
1465	<	return entrySet;
1465	>	Set<Map.Entry<K,V>> es = entrySet;
1466	>	return (es != null)? es : (entrySet = new EntrySetView());
1467		}
1468
1469		private class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
#	Line 1524 | Line 1520 | public class TreeMap<K,V>
1520		}
1521
1522		private transient Set<Map.Entry<K,V>> descendingEntrySetView = null;
1523	<	private transient Set<K> descendingKeySetView = null;
1523	>	private transient Set<K> descendingKeySetView = null;
1524
1525		public Set<Map.Entry<K,V>> descendingEntrySet() {
1526		Set<Map.Entry<K,V>> es = descendingEntrySetView;
#	Line 1548 | Line 1544 | public class TreeMap<K,V>
1544		public Iterator<K> iterator() {
1545		return new Iterator<K>() {
1546		private Iterator<Entry<K,V>> i = descendingEntrySet().iterator();
1547	<
1547	>
1548		public boolean hasNext() { return i.hasNext(); }
1549		public K next() { return i.next().getKey(); }
1550		public void remove() { i.remove(); }
1551		};
1552		}
1553	<
1553	>
1554		public int size() {
1555		return SubMap.this.size();
1556		}
1557	<
1557	>
1558		public boolean contains(Object k) {
1559		return SubMap.this.containsKey(k);
1560		}
#	Line 2164 | Line 2160 | public class TreeMap<K,V>
2160		// Write out size (number of Mappings)
2161		s.writeInt(size);
2162
2163	+	Set<Map.Entry<K,V>> es = entrySet();
2164		// Write out keys and values (alternating)
2165	<	for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2165	>	for (Iterator<Map.Entry<K,V>> i = es.iterator(); i.hasNext(); ) {
2166		Map.Entry<K,V> e = i.next();
2167		s.writeObject(e.getKey());
2168		s.writeObject(e.getValue());

Diff Legend

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