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<string> 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<string> 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 }