1 /*
2  * Hunt - A refined core library for D programming language.
3  *
4  * Copyright (C) 2018-2019 HuntLabs
5  *
6  * Website: https://www.huntlabs.net/
7  *
8  * Licensed under the Apache-2.0 License.
9  *
10  */
11 
12 module hunt.collection.SortedSet;
13 
14 import hunt.collection.Set;
15 
16 /**
17  * A {@link Set} that further provides a <i>total ordering</i> on its elements.
18  * The elements are ordered using their {@linkplain Comparable natural
19  * ordering}, or by a {@link Comparator} typically provided at sorted
20  * set creation time.  The set's iterator will traverse the set in
21  * ascending element order. Several additional operations are provided
22  * to take advantage of the ordering.  (This interface is the set
23  * analogue of {@link SortedMap}.)
24  *
25  * <p>All elements inserted into a sorted set must implement the <tt>Comparable</tt>
26  * interface (or be accepted by the specified comparator).  Furthermore, all
27  * such elements must be <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt>
28  * (or <tt>comparator.compare(e1, e2)</tt>) must not throw a
29  * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in
30  * the sorted set.  Attempts to violate this restriction will cause the
31  * offending method or constructor invocation to throw a
32  * <tt>ClassCastException</tt>.
33  *
34  * <p>Note that the ordering maintained by a sorted set (whether or not an
35  * explicit comparator is provided) must be <i>consistent with equals</i> if
36  * the sorted set is to correctly implement the <tt>Set</tt> interface.  (See
37  * the <tt>Comparable</tt> interface or <tt>Comparator</tt> interface for a
38  * precise definition of <i>consistent with equals</i>.)  This is so because
39  * the <tt>Set</tt> interface is defined in terms of the <tt>equals</tt>
40  * operation, but a sorted set performs all element comparisons using its
41  * <tt>compareTo</tt> (or <tt>compare</tt>) method, so two elements that are
42  * deemed equal by this method are, from the standpoint of the sorted set,
43  * equal.  The behavior of a sorted set <i>is</i> well-defined even if its
44  * ordering is inconsistent with equals; it just fails to obey the general
45  * contract of the <tt>Set</tt> interface.
46  *
47  * <p>All general-purpose sorted set implementation classes should
48  * provide four "standard" constructors: 1) A void (no arguments)
49  * constructor, which creates an empty sorted set sorted according to
50  * the natural ordering of its elements.  2) A constructor with a
51  * single argument of type <tt>Comparator</tt>, which creates an empty
52  * sorted set sorted according to the specified comparator.  3) A
53  * constructor with a single argument of type <tt>Collection</tt>,
54  * which creates a new sorted set with the same elements as its
55  * argument, sorted according to the natural ordering of the elements.
56  * 4) A constructor with a single argument of type <tt>SortedSet</tt>,
57  * which creates a new sorted set with the same elements and the same
58  * ordering as the input sorted set.  There is no way to enforce this
59  * recommendation, as interfaces cannot contain constructors.
60  *
61  * <p>Note: several methods return subsets with restricted ranges.
62  * Such ranges are <i>half-open</i>, that is, they include their low
63  * endpoint but not their high endpoint (where applicable).
64  * If you need a <i>closed range</i> (which includes both endpoints), and
65  * the element type allows for calculation of the successor of a given
66  * value, merely request the subrange from <tt>lowEndpoint</tt> to
67  * <tt>successor(highEndpoint)</tt>.  For example, suppose that <tt>s</tt>
68  * is a sorted set of strings.  The following idiom obtains a view
69  * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
70  * <tt>high</tt>, inclusive:<pre>
71  *   SortedSet&lt;string&gt; sub = s.subSet(low, high+"\0");</pre>
72  *
73  * A similar technique can be used to generate an <i>open range</i> (which
74  * contains neither endpoint).  The following idiom obtains a view
75  * containing all of the Strings in <tt>s</tt> from <tt>low</tt> to
76  * <tt>high</tt>, exclusive:<pre>
77  *   SortedSet&lt;string&gt; sub = s.subSet(low+"\0", high);</pre>
78  *
79  * <p>This interface is a member of the
80  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
81  * Java Collections Framework</a>.
82  *
83  * @param (E) the type of elements maintained by this set
84  *
85  * @see Set
86  * @see TreeSet
87  * @see SortedMap
88  * @see Collection
89  * @see Comparable
90  * @see Comparator
91  * @see ClassCastException
92  */
93 
94 interface SortedSet(E) : Set!(E) {
95     /**
96      * Returns the comparator used to order the elements in this set,
97      * or <tt>null</tt> if this set uses the {@linkplain Comparable
98      * natural ordering} of its elements.
99      *
100      * @return the comparator used to order the elements in this set,
101      *         or <tt>null</tt> if this set uses the natural ordering
102      *         of its elements
103      */
104     // Comparator<E> comparator();
105 
106     /**
107      * Returns a view of the portion of this set whose elements range
108      * from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
109      * exclusive.  (If <tt>fromElement</tt> and <tt>toElement</tt> are
110      * equal, the returned set is empty.)  The returned set is backed
111      * by this set, so changes in the returned set are reflected in
112      * this set, and vice-versa.  The returned set supports all
113      * optional set operations that this set supports.
114      *
115      * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
116      * on an attempt to insert an element outside its range.
117      *
118      * @param fromElement low endpoint (inclusive) of the returned set
119      * @param toElement high endpoint (exclusive) of the returned set
120      * @return a view of the portion of this set whose elements range from
121      *         <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive
122      * @throws ClassCastException if <tt>fromElement</tt> and
123      *         <tt>toElement</tt> cannot be compared to one another using this
124      *         set's comparator (or, if the set has no comparator, using
125      *         natural ordering).  Implementations may, but are not required
126      *         to, throw this exception if <tt>fromElement</tt> or
127      *         <tt>toElement</tt> cannot be compared to elements currently in
128      *         the set.
129      * @throws NullPointerException if <tt>fromElement</tt> or
130      *         <tt>toElement</tt> is null and this set does not permit null
131      *         elements
132      * @throws IllegalArgumentException if <tt>fromElement</tt> is
133      *         greater than <tt>toElement</tt>; or if this set itself
134      *         has a restricted range, and <tt>fromElement</tt> or
135      *         <tt>toElement</tt> lies outside the bounds of the range
136      */
137     SortedSet!(E) subSet(E fromElement, E toElement);
138 
139     /**
140      * Returns a view of the portion of this set whose elements are
141      * strictly less than <tt>toElement</tt>.  The returned set is
142      * backed by this set, so changes in the returned set are
143      * reflected in this set, and vice-versa.  The returned set
144      * supports all optional set operations that this set supports.
145      *
146      * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
147      * on an attempt to insert an element outside its range.
148      *
149      * @param toElement high endpoint (exclusive) of the returned set
150      * @return a view of the portion of this set whose elements are strictly
151      *         less than <tt>toElement</tt>
152      * @throws ClassCastException if <tt>toElement</tt> is not compatible
153      *         with this set's comparator (or, if the set has no comparator,
154      *         if <tt>toElement</tt> does not implement {@link Comparable}).
155      *         Implementations may, but are not required to, throw this
156      *         exception if <tt>toElement</tt> cannot be compared to elements
157      *         currently in the set.
158      * @throws NullPointerException if <tt>toElement</tt> is null and
159      *         this set does not permit null elements
160      * @throws IllegalArgumentException if this set itself has a
161      *         restricted range, and <tt>toElement</tt> lies outside the
162      *         bounds of the range
163      */
164     SortedSet!(E) headSet(E toElement);
165 
166     /**
167      * Returns a view of the portion of this set whose elements are
168      * greater than or equal to <tt>fromElement</tt>.  The returned
169      * set is backed by this set, so changes in the returned set are
170      * reflected in this set, and vice-versa.  The returned set
171      * supports all optional set operations that this set supports.
172      *
173      * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
174      * on an attempt to insert an element outside its range.
175      *
176      * @param fromElement low endpoint (inclusive) of the returned set
177      * @return a view of the portion of this set whose elements are greater
178      *         than or equal to <tt>fromElement</tt>
179      * @throws ClassCastException if <tt>fromElement</tt> is not compatible
180      *         with this set's comparator (or, if the set has no comparator,
181      *         if <tt>fromElement</tt> does not implement {@link Comparable}).
182      *         Implementations may, but are not required to, throw this
183      *         exception if <tt>fromElement</tt> cannot be compared to elements
184      *         currently in the set.
185      * @throws NullPointerException if <tt>fromElement</tt> is null
186      *         and this set does not permit null elements
187      * @throws IllegalArgumentException if this set itself has a
188      *         restricted range, and <tt>fromElement</tt> lies outside the
189      *         bounds of the range
190      */
191     SortedSet!(E) tailSet(E fromElement);
192 
193     /**
194      * Returns the first (lowest) element currently in this set.
195      *
196      * @return the first (lowest) element currently in this set
197      * @throws NoSuchElementException if this set is empty
198      */
199     E first();
200 
201     /**
202      * Returns the last (highest) element currently in this set.
203      *
204      * @return the last (highest) element currently in this set
205      * @throws NoSuchElementException if this set is empty
206      */
207     E last();
208 
209     /**
210      * Creates a {@code Spliterator} over the elements in this sorted set.
211      *
212      * <p>The {@code Spliterator} reports {@link Spliterator#DISTINCT},
213      * {@link Spliterator#SORTED} and {@link Spliterator#ORDERED}.
214      * Implementations should document the reporting of additional
215      * characteristic values.
216      *
217      * <p>The spliterator's comparator (see
218      * {@link java.util.Spliterator#getComparator()}) must be {@code null} if
219      * the sorted set's comparator (see {@link #comparator()}) is {@code null}.
220      * Otherwise, the spliterator's comparator must be the same as or impose the
221      * same total ordering as the sorted set's comparator.
222      *
223      * @implSpec
224      * The default implementation creates a
225      * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator
226      * from the sorted set's {@code Iterator}.  The spliterator inherits the
227      * <em>fail-fast</em> properties of the set's iterator.  The
228      * spliterator's comparator is the same as the sorted set's comparator.
229      * <p>
230      * The created {@code Spliterator} additionally reports
231      * {@link Spliterator#SIZED}.
232      *
233      * @implNote
234      * The created {@code Spliterator} additionally reports
235      * {@link Spliterator#SUBSIZED}.
236      *
237      * @return a {@code Spliterator} over the elements in this sorted set
238      */
239     // override
240     // default Spliterator!(E) spliterator() {
241     //     return new Spliterators.IteratorSpliterator!(E)(
242     //             this, Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED) {
243     //         override
244     //         Comparator<E> getComparator() {
245     //             return SortedSet.this.comparator();
246     //         }
247     //     };
248     // }
249 }