1 //******************************************************************************
2 //
3 // File: Range.java
4 // Package: edu.rit.util
5 // Unit: Class edu.rit.util.Range
6 //
7 // This Java source file is copyright (C) 2007 by Alan Kaminsky. All rights
8 // reserved. For further information, contact the author, Alan Kaminsky, at
9 // ark@cs.rit.edu.
10 //
11 // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
12 // software; you can redistribute it and/or modify it under the terms of the GNU
13 // General Public License as published by the Free Software Foundation; either
14 // version 3 of the License, or (at your option) any later version.
15 //
16 // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
18 // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
19 //
20 // Linking this library statically or dynamically with other modules is making a
21 // combined work based on this library. Thus, the terms and conditions of the GNU
22 // General Public License cover the whole combination.
23 //
24 // As a special exception, the copyright holders of this library give you
25 // permission to link this library with independent modules to produce an
26 // executable, regardless of the license terms of these independent modules, and
27 // to copy and distribute the resulting executable under terms of your choice,
28 // provided that you also meet, for each linked independent module, the terms
29 // and conditions of the license of that module. An independent module is a module
30 // which is not derived from or based on this library. If you modify this library,
31 // you may extend this exception to your version of the library, but you are not
32 // obligated to do so. If you do not wish to do so, delete this exception
33 // statement from your version.
34 //
35 // A copy of the GNU General Public License is provided in the file gpl.txt. You
36 // may also obtain a copy of the GNU General Public License on the World Wide
37 // Web at http://www.gnu.org/licenses/gpl.html.
38 //
39 //******************************************************************************
40 package edu.rit.util;
41
42 import java.io.Externalizable;
43 import java.io.IOException;
44 import java.io.ObjectInput;
45 import java.io.ObjectOutput;
46 import java.io.Serial;
47
48 /**
49 * Class Range provides a range of type <code>int</code>. A range object has the
50 * following attributes: <B>lower bound</B> <I>L</I>, <B>upper bound</B>
51 * <I>U</I>, <B>stride</B> <I>S</I>, and <B>length</B> <I>N</I>. A range object
52 * represents the following set of integers: {<I>L</I>, <I>L</I>+<I>S</I>,
53 * <I>L</I>+2*<I>S</I>, . . . , <I>L</I>+(<I>N</I>-1)*<I>S</I>}, where <I>U</I>
54 * = <I>L</I>+(<I>N</I>-1)*<I>S</I>.
55 * <P>
56 * You construct a range object by specifying the lower bound, upper bound, and
57 * stride. If the stride is omitted, the default stride is 1. The length is
58 * determined automatically. If the lower bound is greater than the upper bound,
59 * the range's length is 0 (an empty range).
60 * <P>
61 * You can use a range object to control a for loop like this:
62 * <PRE>
63 * Range range = new Range (0, N-1);
64 * int lb = range.lb();
65 * int ub = range.ub();
66 * for (int i = lb; i <= ub; ++ i)
67 * . . .
68 * </PRE> Note that the range is from <code>lb()</code> to <code>ub()</code> inclusive,
69 * so the appropriate test in the for loop is <code>i <= ub</code>. Also note
70 * that it usually reduces the running time to call <code>ub()</code> once, store
71 * the result in a local variable, and use the local variable in the for loop
72 * test, than to call <code>ub()</code> directly in the for loop test.
73 * <P>
74 * You can use a range object with a stride greater than 1 to control a for loop
75 * like this:
76 * <PRE>
77 * Range range = new Range (0, N-1, 2);
78 * int lb = range.lb();
79 * int ub = range.ub();
80 * int stride = range.stride();
81 * for (int i = lb; i <= ub; i += stride)
82 * . . .
83 * </PRE>
84 *
85 * @author Alan Kaminsky
86 * @version 30-May-2007
87 */
88 public class Range
89 implements Externalizable {
90
91 // Hidden data members.
92 @Serial
93 private static final long serialVersionUID = -155434844308312282L;
94
95 int lb;
96 int stride;
97 int length;
98 int ub;
99
100 // Exported constructors.
101 /**
102 * Construct a new range object representing an empty range.
103 */
104 public Range() {
105 this.lb = 0;
106 this.stride = 1;
107 this.length = 0;
108 setUb();
109 }
110
111 /**
112 * Construct a new range object with the given lower bound and upper bound.
113 * The stride is 1. The range object represents the following set of
114 * integers: {<I>L</I>, <I>L</I>+1, <I>L</I>+2, . . . , <I>U</I>}. The
115 * range's length <I>N</I> is <I>U</I>-<I>L</I>+1.
116 * <P>
117 * <I>Note:</I> <I>L</I> > <I>U</I> is allowed and stands for an empty
118 * range.
119 *
120 * @param lb Lower bound <I>L</I>.
121 * @param ub Upper bound <I>U</I>.
122 */
123 public Range(int lb,
124 int ub) {
125 this.lb = lb;
126 this.stride = 1;
127 this.length = Math.max(ub - lb + 1, 0);
128 setUb();
129 }
130
131 /**
132 * Construct a new range object with the given lower bound, upper bound, and
133 * stride. The stride must be greater than or equal to 1. The range object
134 * represents the following set of integers: {<I>L</I>, <I>L</I>+<I>S</I>,
135 * <I>L</I>+2*<I>S</I>, . . . , <I>L</I>+(<I>N</I>-1)*<I>S</I>}, where the
136 * range's length <I>N</I> is such that <I>L</I>+(<I>N</I>-1)*<I>S</I> is
137 * the largest integer less than or equal to <I>U</I>. Note that the actual
138 * upper bound of the range, <I>L</I>+(<I>N</I>-1)*<I>S</I>, may not be the
139 * same as <I>U</I>.
140 * <P>
141 * <I>Note:</I> <I>L</I> > <I>U</I> is allowed and stands for an empty
142 * range.
143 *
144 * @param lb Lower bound <I>L</I>.
145 * @param ub Upper bound <I>U</I>.
146 * @param stride Stride <I>S</I> >= 1.
147 * @exception IllegalArgumentException (unchecked exception) Thrown if
148 * <I>S</I> < 1.
149 */
150 public Range(int lb,
151 int ub,
152 int stride) {
153 if (stride < 1) {
154 throw new IllegalArgumentException("Range(): stride = " + stride + " illegal");
155 }
156 this.lb = lb;
157 this.stride = stride;
158 this.length = Math.max((ub - lb + stride) / stride, 0);
159 setUb();
160 }
161
162 /**
163 * Construct a new range object that is a copy of the given range object.
164 *
165 * @param range Range object to copy.
166 */
167 public Range(Range range) {
168 this.lb = range.lb;
169 this.stride = range.stride;
170 this.length = range.length;
171 this.ub = range.ub;
172 }
173
174 // Exported operations.
175 /**
176 * Returns this range's lower bound.
177 *
178 * @return Lower bound.
179 */
180 public int lb() {
181 return lb;
182 }
183
184 /**
185 * Returns this range's upper bound.
186 *
187 * @return Upper bound.
188 */
189 public int ub() {
190 return ub;
191 }
192
193 /**
194 * Returns this range's stride.
195 *
196 * @return Stride.
197 */
198 public int stride() {
199 return stride;
200 }
201
202 /**
203 * Returns this range's length.
204 *
205 * @return Length.
206 */
207 public int length() {
208 return length;
209 }
210
211 /**
212 * Determine if this range contains the given value. This range contains the
213 * given value if <code>this.lb()</code> <= <code>val</code> <=
214 * <code>this.ub()</code>. (The stride does not affect the outcome.)
215 *
216 * @param value Value to test.
217 * @return True if this range contains the given <code>value</code>, false
218 * otherwise.
219 */
220 public boolean contains(int value) {
221 return this.lb <= value && value <= this.ub;
222 }
223
224 /**
225 * Determine if this range contains the given range. This range contains the
226 * given range if <code>this.lb()</code> <= <code>range.lb()</code> and
227 * <code>range.ub()</code> <= <code>this.ub()</code>. (The strides do not affect
228 * the outcome.)
229 *
230 * @param range Range to test.
231 * @return True if this range contains the given <code>range</code>, false
232 * otherwise.
233 */
234 public boolean contains(Range range) {
235 return this.lb <= range.lb && range.ub <= this.ub;
236 }
237
238 /**
239 * Partition this range and return one subrange. This range is split up into
240 * subranges; the <code>size</code> argument specifies the number of subranges.
241 * This range is divided as equally as possible among the subranges; the
242 * lengths of the subranges differ by at most 1. The subranges are numbered
243 * 0, 1, . . . <code>size-1</code>. This method returns the subrange whose
244 * number is <code>rank</code>.
245 * <P>
246 * Note that if <code>size</code> is greater than the length of this range, the
247 * returned subrange may be empty.
248 *
249 * @param size Number of subranges, <code>size</code> >= 1.
250 * @param rank Rank of the desired subrange, 0 <= <code>rank</code> <
251 * <code>size</code>.
252 * @return Subrange.
253 * @exception IllegalArgumentException (unchecked exception) Thrown if
254 * <code>size</code> or <code>rank</code> is out of bounds.
255 */
256 public Range subrange(int size,
257 int rank) {
258 // Verify preconditions.
259 if (size < 1) {
260 throw new IllegalArgumentException("Range.subrange(): size = " + size + " illegal");
261 }
262 if (0 > rank || rank >= size) {
263 throw new IllegalArgumentException("Range.subrange(): rank = " + rank + " illegal");
264 }
265
266 // Split this range.
267 Range result = new Range();
268 int sublen = this.length / size;
269 int subrem = this.length % size;
270 if (rank < subrem) {
271 ++sublen;
272 result.lb = this.lb + (rank * sublen) * this.stride;
273 } else {
274 result.lb = this.lb + (subrem + rank * sublen) * this.stride;
275 }
276 result.stride = this.stride;
277 result.length = sublen;
278 result.setUb();
279 return result;
280 }
281
282 /**
283 * Partition this range and return all the subranges. This range is split up
284 * into subranges; the <code>size</code> argument specifies the number of
285 * subranges. This range is divided as equally as possible among the
286 * subranges; the lengths of the subranges differ by at most 1. The
287 * subranges are returned in an array with indexes 0, 1, . . .
288 * <code>size-1</code>.
289 * <P>
290 * Note that if <code>size</code> is greater than the length of this range, some
291 * of the returned subranges may be empty.
292 *
293 * @param size Number of subranges, size >= 1.
294 * @return Array of subranges.
295 * @exception IllegalArgumentException (unchecked exception) Thrown if
296 * <code>size</code> is out of bounds.
297 */
298 public Range[] subranges(int size) {
299 // Verify preconditions.
300 if (size < 1) {
301 throw new IllegalArgumentException("Range.subranges(): size = " + size + " illegal");
302 }
303
304 // Allocate storage for subranges.
305 Range[] result = new Range[size];
306
307 // Compute subranges.
308 int sublen = this.length / size;
309 int subrem = this.length % size;
310 int x = this.lb;
311 ++sublen;
312 for (int i = 0; i < subrem; ++i) {
313 Range result_i = new Range();
314 result_i.lb = x;
315 x += sublen * this.stride;
316 result_i.stride = this.stride;
317 result_i.length = sublen;
318 result_i.setUb();
319 result[i] = result_i;
320 }
321 --sublen;
322 for (int i = subrem; i < size; ++i) {
323 Range result_i = new Range();
324 result_i.lb = x;
325 x += sublen * this.stride;
326 result_i.stride = this.stride;
327 result_i.length = sublen;
328 result_i.setUb();
329 result[i] = result_i;
330 }
331
332 return result;
333 }
334
335 /**
336 * Slice off a chunk of this range and return the chunk. Considering this
337 * range as a set of integers from the lower bound to the upper bound, the
338 * first <code>N1</code> integers are sliced off and discarded, then the next
339 * <code>N2</code> integers are sliced off to form a chunk, and the chunk is
340 * returned. If after removing the first <code>N1</code> integers there are
341 * fewer than <code>N2</code> integers left, a chunk consisting of all the
342 * remaining integers is returned; this may be an empty chunk.
343 *
344 * @param N1 Number of integers to discard (must be >= 0).
345 * @param N2 Number of integers to include in the chunk (must be >= 0).
346 * @return Chunk.
347 * @exception IllegalArgumentException (unchecked exception) Thrown if
348 * <code>N1</code> or <code>N2</code> is out of bounds.
349 */
350 public Range chunk(int N1,
351 int N2) {
352 // Verify preconditions.
353 if (N1 < 0) {
354 throw new IllegalArgumentException("Range.chunk(): N1 = " + N1 + " illegal");
355 }
356 if (N2 < 0) {
357 throw new IllegalArgumentException("Range.chunk(): N2 = " + N2 + " illegal");
358 }
359
360 Range result = new Range();
361 result.lb = this.lb + N1 * this.stride;
362 result.stride = this.stride;
363 result.length = Math.min(N2, Math.max(0, this.length - N1));
364 result.setUb();
365 return result;
366 }
367
368 /**
369 * {@inheritDoc}
370 *
371 * Determine if this range is equal to the given object. Two ranges are
372 * equal if they both have the same lower bound, stride, and length.
373 */
374 public boolean equals(Object obj) {
375 return obj instanceof Range
376 && this.lb == ((Range) obj).lb
377 && this.stride == ((Range) obj).stride
378 && this.length == ((Range) obj).length;
379 }
380
381 /**
382 * Returns a hash code for this range.
383 *
384 * @return a int.
385 */
386 public int hashCode() {
387 return (((this.lb << 10) + this.stride) << 10) + this.length;
388 }
389
390 /**
391 * Returns a string version of this range. If the stride is 1, the format is
392 * <code>"<I>L</I>..<I>U</I>"</code>, where <I>L</I> is the lower bound and
393 * <I>U</I> is the upper bound. If the stride is greater than 1, the format
394 * is <code>"<I>L</I>..<I>U</I>;<I>S</I>"</code>, where <I>L</I> is the lower
395 * bound, <I>U</I> is the upper bound, and <I>S</I> is the stride.
396 *
397 * @return a {@link java.lang.String} object.
398 */
399 public String toString() {
400 StringBuilder b = new StringBuilder();
401 b.append(lb);
402 b.append("..");
403 b.append(ub);
404 if (stride > 1) {
405 b.append(';');
406 b.append(stride);
407 }
408 return b.toString();
409 }
410
411 /**
412 * {@inheritDoc}
413 *
414 * Write this range to the given object output stream.
415 * @exception IOException Thrown if an I/O error occurred.
416 */
417 public void writeExternal(ObjectOutput out)
418 throws IOException {
419 out.writeInt(lb);
420 out.writeInt(stride);
421 out.writeInt(length);
422 }
423
424 /**
425 * {@inheritDoc}
426 *
427 * Read this range from the given object input stream.
428 * @exception IOException Thrown if an I/O error occurred.
429 */
430 public void readExternal(ObjectInput in)
431 throws IOException {
432 lb = in.readInt();
433 stride = in.readInt();
434 length = in.readInt();
435 setUb();
436 }
437
438 // Hidden operations.
439 /**
440 * Set the upper bound of this range based on the lower bound, stride, and
441 * length.
442 */
443 private void setUb() {
444 ub = lb + (length - 1) * stride;
445 }
446
447 // Unit test main program.
448 // /**
449 // * Unit test main program.
450 // */
451 // public static void main
452 // (String[] args)
453 // {
454 // if (args.length != 4)
455 // {
456 // System.err.println ("Usage: edu.rit.util.Range <lb> <ub> <stride> <size>");
457 // System.exit (1);
458 // }
459 // int lb = Integer.parseInt (args[0]);
460 // int ub = Integer.parseInt (args[1]);
461 // int stride = Integer.parseInt (args[2]);
462 // int size = Integer.parseInt (args[3]);
463 // Range range = new Range (lb, ub, stride);
464 // System.out.println
465 // ("Range = " + range + ", length = " + range.length());
466 // for (int rank = 0; rank < size; ++ rank)
467 // {
468 // Range subrange = range.subrange (size, rank);
469 // System.out.println
470 // ("Subrange rank " + rank + " = " + subrange +
471 // ", length = " + subrange.length());
472 // }
473 // Range[] subranges = range.subranges (size);
474 // for (int rank = 0; rank < size; ++ rank)
475 // {
476 // System.out.println
477 // ("Subranges[" + rank + "] = " + subranges[rank] +
478 // ", length = " + subranges[rank].length());
479 // }
480 // }
481 }