1 /*
2  * Copyright (c) 2021, 2023, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.  Oracle designates this
8  * particular file as subject to the "Classpath" exception as provided
9  * by Oracle in the LICENSE file that accompanied this code.
10  *
11  * This code is distributed in the hope that it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14  * version 2 for more details (a copy is included in the LICENSE file that
15  * accompanied this code).
16  *
17  * You should have received a copy of the GNU General Public License version
18  * 2 along with this work; if not, write to the Free Software Foundation,
19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20  *
21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22  * or visit www.oracle.com if you need additional information or have any
23  * questions.
24  */
25 
26 package java.util;
27 
28 import jdk.internal.util.NullableKeyValueHolder;
29 
30 /**
31  * A Map that has a well-defined encounter order, that supports operations at both ends, and
32  * that is reversible. The <a href="SequencedCollection.html#encounter">encounter order</a>
33  * of a {@code SequencedMap} is similar to that of the elements of a {@link SequencedCollection},
34  * but the ordering applies to mappings instead of individual elements.
35  * <p>
36  * The bulk operations on this map, including the {@link #forEach forEach} and the
37  * {@link #replaceAll replaceAll} methods, operate on this map's mappings in
38  * encounter order.
39  * <p>
40  * The view collections provided by the
41  * {@link #keySet keySet},
42  * {@link #values values},
43  * {@link #entrySet entrySet},
44  * {@link #sequencedKeySet sequencedKeySet},
45  * {@link #sequencedValues sequencedValues},
46  * and
47  * {@link #sequencedEntrySet sequencedEntrySet} methods all reflect the encounter order
48  * of this map. Even though the return values of the {@code keySet}, {@code values}, and
49  * {@code entrySet} methods are not sequenced <i>types</i>, the elements
50  * in those view collections do reflect the encounter order of this map. Thus, the
51  * iterators returned by the statements
52  * {@snippet :
53  *     var it1 = sequencedMap.entrySet().iterator();
54  *     var it2 = sequencedMap.sequencedEntrySet().iterator();
55  * }
56  * both provide the mappings of {@code sequencedMap} in that map's encounter order.
57  * <p>
58  * This interface provides methods to add mappings, to retrieve mappings, and to remove
59  * mappings at either end of the map's encounter order.
60  * <p>
61  * This interface also defines the {@link #reversed} method, which provides a
62  * reverse-ordered <a href="Collection.html#view">view</a> of this map.
63  * In the reverse-ordered view, the concepts of first and last are inverted, as
64  * are the concepts of successor and predecessor. The first mapping of this map
65  * is the last mapping of the reverse-ordered view, and vice-versa. The successor of some
66  * mapping in this map is its predecessor in the reversed view, and vice-versa. All
67  * methods that respect the encounter order of the map operate as if the encounter order
68  * is inverted. For instance, the {@link #forEach forEach} method of the reversed view reports
69  * the mappings in order from the last mapping of this map to the first. In addition, all of
70  * the view collections of the reversed view also reflect the inverse of this map's
71  * encounter order. For example,
72  * {@snippet :
73  *     var itr = sequencedMap.reversed().entrySet().iterator();
74  * }
75  * provides the mappings of this map in the inverse of the encounter order, that is, from
76  * the last mapping to the first mapping. The availability of the {@code reversed} method,
77  * and its impact on the ordering semantics of all applicable methods and views, allow convenient
78  * iteration, searching, copying, and streaming of this map's mappings in either forward order or
79  * reverse order.
80  * <p>
81  * A map's reverse-ordered view is generally not serializable, even if the original
82  * map is serializable.
83  * <p>
84  * The {@link Map.Entry} instances obtained by iterating the {@link #entrySet} view, the
85  * {@link #sequencedEntrySet} view, and its reverse-ordered view, maintain a connection to the
86  * underlying map. This connection is guaranteed only during the iteration. It is unspecified
87  * whether the connection is maintained outside of the iteration. If the underlying map permits
88  * it, calling an Entry's {@link Map.Entry#setValue setValue} method will modify the value of the
89  * underlying mapping. It is, however, unspecified whether modifications to the value in the
90  * underlying mapping are visible in the {@code Entry} instance.
91  * <p>
92  * The methods
93  * {@link #firstEntry},
94  * {@link #lastEntry},
95  * {@link #pollFirstEntry}, and
96  * {@link #pollLastEntry}
97  * return {@link Map.Entry} instances that represent snapshots of mappings as
98  * of the time of the call. They do <em>not</em> support mutation of the
99  * underlying map via the optional {@link Map.Entry#setValue setValue} method.
100  * <p>
101  * Depending upon the implementation, the {@code Entry} instances returned by other
102  * means might or might not be connected to the underlying map. For example, consider
103  * an {@code Entry} obtained in the following manner:
104  * {@snippet :
105  *     var entry = sequencedMap.sequencedEntrySet().getFirst();
106  * }
107  * It is not specified by this interface whether the {@code setValue} method of the
108  * {@code Entry} thus obtained will update a mapping in the underlying map, or whether
109  * it will throw an exception, or whether changes to the underlying map are visible in
110  * that {@code Entry}.
111  * <p>
112  * This interface has the same requirements on the {@code equals} and {@code hashCode}
113  * methods as defined by {@link Map#equals Map.equals} and {@link Map#hashCode Map.hashCode}.
114  * Thus, a {@code Map} and a {@code SequencedMap} will compare equals if and only
115  * if they have equal mappings, irrespective of ordering.
116  * <p>
117  * This class is a member of the
118  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
119  * Java Collections Framework</a>.
120  *
121  * @param <K> the type of keys maintained by this map
122  * @param <V> the type of mapped values
123  * @since 21
124  */
125 public interface SequencedMap<K, V> extends Map<K, V> {
126     /**
127      * Returns a reverse-ordered <a href="Collection.html#view">view</a> of this map.
128      * The encounter order of mappings in the returned view is the inverse of the encounter
129      * order of mappings in this map. The reverse ordering affects all order-sensitive operations,
130      * including those on the view collections of the returned view. If the implementation permits
131      * modifications to this view, the modifications "write through" to the underlying map.
132      * Changes to the underlying map might or might not be visible in this reversed view,
133      * depending upon the implementation.
134      *
135      * @return a reverse-ordered view of this map
136      */
reversed()137     SequencedMap<K, V> reversed();
138 
139     /**
140      * Returns the first key-value mapping in this map,
141      * or {@code null} if the map is empty.
142      *
143      * @implSpec
144      * The implementation in this interface obtains the iterator of this map's entrySet.
145      * If the iterator has an element, it returns an unmodifiable copy of that element.
146      * Otherwise, it returns null.
147      *
148      * @return the first key-value mapping,
149      *         or {@code null} if this map is empty
150      */
firstEntry()151     default Map.Entry<K,V> firstEntry() {
152         var it = entrySet().iterator();
153         return it.hasNext() ? new NullableKeyValueHolder<>(it.next()) : null;
154     }
155 
156     /**
157      * Returns the last key-value mapping in this map,
158      * or {@code null} if the map is empty.
159      *
160      * @implSpec
161      * The implementation in this interface obtains the iterator of the entrySet of this map's
162      * reversed view. If the iterator has an element, it returns an unmodifiable copy of
163      * that element. Otherwise, it returns null.
164      *
165      * @return the last key-value mapping,
166      *         or {@code null} if this map is empty
167      */
lastEntry()168     default Map.Entry<K,V> lastEntry() {
169         var it = reversed().entrySet().iterator();
170         return it.hasNext() ? new NullableKeyValueHolder<>(it.next()) : null;
171     }
172 
173     /**
174      * Removes and returns the first key-value mapping in this map,
175      * or {@code null} if the map is empty (optional operation).
176      *
177      * @implSpec
178      * The implementation in this interface obtains the iterator of this map's entrySet.
179      * If the iterator has an element, it calls {@code remove} on the iterator and
180      * then returns an unmodifiable copy of that element. Otherwise, it returns null.
181      *
182      * @return the removed first entry of this map,
183      *         or {@code null} if this map is empty
184      * @throws UnsupportedOperationException if this collection implementation does not
185      *         support this operation
186      */
pollFirstEntry()187     default Map.Entry<K,V> pollFirstEntry() {
188         var it = entrySet().iterator();
189         if (it.hasNext()) {
190             var entry = new NullableKeyValueHolder<>(it.next());
191             it.remove();
192             return entry;
193         } else {
194             return null;
195         }
196     }
197 
198     /**
199      * Removes and returns the last key-value mapping in this map,
200      * or {@code null} if the map is empty (optional operation).
201      *
202      * @implSpec
203      * The implementation in this interface obtains the iterator of the entrySet of this map's
204      * reversed view. If the iterator has an element, it calls {@code remove} on the iterator
205      * and then returns an unmodifiable copy of that element. Otherwise, it returns null.
206      *
207      * @return the removed last entry of this map,
208      *         or {@code null} if this map is empty
209      * @throws UnsupportedOperationException if this collection implementation does not
210      *         support this operation
211      */
pollLastEntry()212     default Map.Entry<K,V> pollLastEntry() {
213         var it = reversed().entrySet().iterator();
214         if (it.hasNext()) {
215             var entry = new NullableKeyValueHolder<>(it.next());
216             it.remove();
217             return entry;
218         } else {
219             return null;
220         }
221     }
222 
223     /**
224      * Inserts the given mapping into the map if it is not already present, or replaces the
225      * value of a mapping if it is already present (optional operation). After this operation
226      * completes normally, the given mapping will be present in this map, and it will be the
227      * first mapping in this map's encounter order.
228      *
229      * @implSpec The implementation in this interface always throws
230      * {@code UnsupportedOperationException}.
231      *
232      * @param k the key
233      * @param v the value
234      * @return the value previously associated with k, or null if none
235      * @throws UnsupportedOperationException if this collection implementation does not
236      *         support this operation
237      */
putFirst(K k, V v)238     default V putFirst(K k, V v) {
239         throw new UnsupportedOperationException();
240     }
241 
242     /**
243      * Inserts the given mapping into the map if it is not already present, or replaces the
244      * value of a mapping if it is already present (optional operation). After this operation
245      * completes normally, the given mapping will be present in this map, and it will be the
246      * last mapping in this map's encounter order.
247      *
248      * @implSpec The implementation in this interface always throws
249      * {@code UnsupportedOperationException}.
250      *
251      * @param k the key
252      * @param v the value
253      * @return the value previously associated with k, or null if none
254      * @throws UnsupportedOperationException if this collection implementation does not
255      *         support this operation
256      */
putLast(K k, V v)257     default V putLast(K k, V v) {
258         throw new UnsupportedOperationException();
259     }
260 
261     /**
262      * Returns a {@code SequencedSet} view of this map's {@link #keySet keySet}.
263      *
264      * @implSpec
265      * The implementation in this interface returns a {@code SequencedSet} instance
266      * that behaves as follows. Its {@link SequencedSet#add add} and {@link
267      * SequencedSet#addAll addAll} methods throw {@link UnsupportedOperationException}.
268      * Its {@link SequencedSet#reversed reversed} method returns the {@link
269      * #sequencedKeySet sequencedKeySet} view of the {@link #reversed reversed} view of
270      * this map. Each of its other methods calls the corresponding method of the {@link
271      * #keySet keySet} view of this map.
272      *
273      * @return a {@code SequencedSet} view of this map's {@code keySet}
274      */
sequencedKeySet()275     default SequencedSet<K> sequencedKeySet() {
276         class SeqKeySet extends AbstractMap.ViewCollection<K> implements SequencedSet<K> {
277             Collection<K> view() {
278                 return SequencedMap.this.keySet();
279             }
280             public SequencedSet<K> reversed() {
281                 return SequencedMap.this.reversed().sequencedKeySet();
282             }
283             public boolean equals(Object other) {
284                 return view().equals(other);
285             }
286             public int hashCode() {
287                 return view().hashCode();
288             }
289         }
290         return new SeqKeySet();
291     }
292 
293     /**
294      * Returns a {@code SequencedCollection} view of this map's {@link #values values} collection.
295      *
296      * @implSpec
297      * The implementation in this interface returns a {@code SequencedCollection} instance
298      * that behaves as follows. Its {@link SequencedCollection#add add} and {@link
299      * SequencedCollection#addAll addAll} methods throw {@link UnsupportedOperationException}.
300      * Its {@link SequencedCollection#reversed reversed} method returns the {@link
301      * #sequencedValues sequencedValues} view of the {@link #reversed reversed} view of
302      * this map. Its {@link Object#equals equals} and {@link Object#hashCode hashCode} methods
303      * are inherited from {@link Object}. Each of its other methods calls the corresponding
304      * method of the {@link #values values} view of this map.
305      *
306      * @return a {@code SequencedCollection} view of this map's {@code values} collection
307      */
sequencedValues()308     default SequencedCollection<V> sequencedValues() {
309         class SeqValues extends AbstractMap.ViewCollection<V> implements SequencedCollection<V> {
310             Collection<V> view() {
311                 return SequencedMap.this.values();
312             }
313             public SequencedCollection<V> reversed() {
314                 return SequencedMap.this.reversed().sequencedValues();
315             }
316         }
317         return new SeqValues();
318     }
319 
320     /**
321      * Returns a {@code SequencedSet} view of this map's {@link #entrySet entrySet}.
322      *
323      * @implSpec
324      * The implementation in this interface returns a {@code SequencedSet} instance
325      * that behaves as follows. Its {@link SequencedSet#add add} and {@link
326      * SequencedSet#addAll addAll} methods throw {@link UnsupportedOperationException}.
327      * Its {@link SequencedSet#reversed reversed} method returns the {@link
328      * #sequencedEntrySet sequencedEntrySet} view of the {@link #reversed reversed} view of
329      * this map. Each of its other methods calls the corresponding method of the {@link
330      * #entrySet entrySet} view of this map.
331      *
332      * @return a {@code SequencedSet} view of this map's {@code entrySet}
333      */
sequencedEntrySet()334     default SequencedSet<Map.Entry<K, V>> sequencedEntrySet() {
335         class SeqEntrySet extends AbstractMap.ViewCollection<Map.Entry<K, V>>
336                 implements SequencedSet<Map.Entry<K, V>> {
337             Collection<Map.Entry<K, V>> view() {
338                 return SequencedMap.this.entrySet();
339             }
340             public SequencedSet<Map.Entry<K, V>> reversed() {
341                 return SequencedMap.this.reversed().sequencedEntrySet();
342             }
343             public boolean equals(Object other) {
344                 return view().equals(other);
345             }
346             public int hashCode() {
347                 return view().hashCode();
348             }
349         }
350         return new SeqEntrySet();
351     }
352 }
353