//******************************************************************************
//
// File: Range.java
// Package: edu.rit.util
// Unit: Class edu.rit.util.Range
//
// This Java source file is copyright (C) 2007 by Alan Kaminsky. All rights
// reserved. For further information, contact the author, Alan Kaminsky, at
// ark@cs.rit.edu.
//
// This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
// software; you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// PJ is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
// A PARTICULAR PURPOSE. See the GNU General Public License for more details.
//
// A copy of the GNU General Public License is provided in the file gpl.txt. You
// may also obtain a copy of the GNU General Public License on the World Wide
// Web at http://www.gnu.org/licenses/gpl.html.
//
//******************************************************************************
package edu.rit.util;
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
/**
* Class Range provides a range of type int. A range object has the
* following attributes: lower bound L, upper bound
* U, stride S, and length N. A range object
* represents the following set of integers: {L, L+S,
* L+2*S, . . . , L+(N-1)*S}, where U
* = L+(N-1)*S.
*
* You construct a range object by specifying the lower bound, upper bound, and
* stride. If the stride is omitted, the default stride is 1. The length is
* determined automatically. If the lower bound is greater than the upper bound,
* the range's length is 0 (an empty range).
*
* You can use a range object to control a for loop like this:
*
* Range range = new Range (0, N-1);
* int lb = range.lb();
* int ub = range.ub();
* for (int i = lb; i <= ub; ++ i)
* . . .
*
* Note that the range is from lb() to ub() inclusive, so the
* appropriate test in the for loop is i <= ub. Also note that it
* usually reduces the running time to call ub() once, store the result
* in a local variable, and use the local variable in the for loop test, than to
* call ub() directly in the for loop test.
*
* You can use a range object with a stride greater than 1 to control a for loop
* like this:
*
* Range range = new Range (0, N-1, 2);
* int lb = range.lb();
* int ub = range.ub();
* int stride = range.stride();
* for (int i = lb; i <= ub; i += stride)
* . . .
*
*
* @author Alan Kaminsky
* @version 30-May-2007
*/
public class Range
implements Externalizable
{
// Hidden data members.
private static final long serialVersionUID = -155434844308312282L;
int lb;
int stride;
int length;
int ub;
// Exported constructors.
/**
* Construct a new range object representing an empty range.
*/
public Range()
{
this.lb = 0;
this.stride = 1;
this.length = 0;
setUb();
}
/**
* Construct a new range object with the given lower bound and upper bound.
* The stride is 1. The range object represents the following set of
* integers: {L, L+1, L+2, . . . , U}. The
* range's length N is U-L+1.
*
* Note: L > U is allowed and stands for an empty
* range.
*
* @param lb Lower bound L.
* @param ub Upper bound U.
*/
public Range
(int lb,
int ub)
{
this.lb = lb;
this.stride = 1;
this.length = Math.max (ub-lb+1, 0);
setUb();
}
/**
* Construct a new range object with the given lower bound, upper bound, and
* stride. The stride must be greater than or equal to 1. The range object
* represents the following set of integers: {L, L+S,
* L+2*S, . . . , L+(N-1)*S}, where the
* range's length N is such that L+(N-1)*S is
* the largest integer less than or equal to U. Note that the actual
* upper bound of the range, L+(N-1)*S, may not be the
* same as U.
*
* Note: L > U is allowed and stands for an empty
* range.
*
* @param lb Lower bound L.
* @param ub Upper bound U.
* @param stride Stride S >= 1.
*
* @exception IllegalArgumentException
* (unchecked exception) Thrown if S < 1.
*/
public Range
(int lb,
int ub,
int stride)
{
if (stride < 1)
{
throw new IllegalArgumentException
("Range(): stride = " + stride + " illegal");
}
this.lb = lb;
this.stride = stride;
this.length = Math.max ((ub-lb+stride)/stride, 0);
setUb();
}
/**
* Construct a new range object that is a copy of the given range object.
*
* @param range Range object to copy.
*/
public Range
(Range range)
{
this.lb = range.lb;
this.stride = range.stride;
this.length = range.length;
this.ub = range.ub;
}
// Exported operations.
/**
* Returns this range's lower bound.
*
* @return Lower bound.
*/
public int lb()
{
return lb;
}
/**
* Returns this range's upper bound.
*
* @return Upper bound.
*/
public int ub()
{
return ub;
}
/**
* Returns this range's stride.
*
* @return Stride.
*/
public int stride()
{
return stride;
}
/**
* Returns this range's length.
*
* @return Length.
*/
public int length()
{
return length;
}
/**
* Determine if this range contains the given value. This range contains the
* given value if this.lb() <= val <=
* this.ub(). (The stride does not affect the outcome.)
*
* @param value Value to test.
*
* @return True if this range contains the given value, false
* otherwise.
*/
public boolean contains
(int value)
{
return this.lb <= value && value <= this.ub;
}
/**
* Determine if this range contains the given range. This range contains the
* given range if this.lb() <= range.lb() and
* range.ub() <= this.ub(). (The strides do not affect
* the outcome.)
*
* @param range Range to test.
*
* @return True if this range contains the given range, false
* otherwise.
*/
public boolean contains
(Range range)
{
return this.lb <= range.lb && range.ub <= this.ub;
}
/**
* Partition this range and return one subrange. This range is split up into
* subranges; the size argument specifies the number of subranges.
* This range is divided as equally as possible among the subranges; the
* lengths of the subranges differ by at most 1. The subranges are numbered
* 0, 1, . . . size-1. This method returns the subrange whose
* number is rank.
*
* Note that if size is greater than the length of this range, the
* returned subrange may be empty.
*
* @param size Number of subranges, size >= 1.
* @param rank Rank of the desired subrange, 0 <= rank <
* size.
*
* @return Subrange.
*
* @exception IllegalArgumentException
* (unchecked exception) Thrown if size or rank is out
* of bounds.
*/
public Range subrange
(int size,
int rank)
{
// Verify preconditions.
if (size < 1)
{
throw new IllegalArgumentException
("Range.subrange(): size = " + size + " illegal");
}
if (0 > rank || rank >= size)
{
throw new IllegalArgumentException
("Range.subrange(): rank = " + rank + " illegal");
}
// Split this range.
Range result = new Range();
int sublen = this.length / size;
int subrem = this.length % size;
if (rank < subrem)
{
++ sublen;
result.lb = this.lb + (rank * sublen) * this.stride;
}
else
{
result.lb = this.lb + (subrem + rank * sublen) * this.stride;
}
result.stride = this.stride;
result.length = sublen;
result.setUb();
return result;
}
/**
* Partition this range and return all the subranges. This range is split up
* into subranges; the size argument specifies the number of
* subranges. This range is divided as equally as possible among the
* subranges; the lengths of the subranges differ by at most 1. The
* subranges are returned in an array with indexes 0, 1, . . .
* size-1.
*
* Note that if size is greater than the length of this range, some
* of the returned subranges may be empty.
*
* @param size Number of subranges, size >= 1.
*
* @return Array of subranges.
*
* @exception IllegalArgumentException
* (unchecked exception) Thrown if size is out of bounds.
*/
public Range[] subranges
(int size)
{
// Verify preconditions.
if (size < 1)
{
throw new IllegalArgumentException
("Range.subranges(): size = " + size + " illegal");
}
// Allocate storage for subranges.
Range[] result = new Range [size];
// Compute subranges.
int sublen = this.length / size;
int subrem = this.length % size;
int x = this.lb;
++ sublen;
for (int i = 0; i < subrem; ++ i)
{
Range result_i = new Range();
result_i.lb = x;
x += sublen * this.stride;
result_i.stride = this.stride;
result_i.length = sublen;
result_i.setUb();
result[i] = result_i;
}
-- sublen;
for (int i = subrem; i < size; ++ i)
{
Range result_i = new Range();
result_i.lb = x;
x += sublen * this.stride;
result_i.stride = this.stride;
result_i.length = sublen;
result_i.setUb();
result[i] = result_i;
}
return result;
}
/**
* Slice off a chunk of this range and return the chunk. Considering this
* range as a set of integers from the lower bound to the upper bound, the
* first N1 integers are sliced off and discarded, then the next
* N2 integers are sliced off to form a chunk, and the chunk is
* returned. If after removing the first N1 integers there are
* fewer than N2 integers left, a chunk consisting of all the
* remaining integers is returned; this may be an empty chunk.
*
* @param N1 Number of integers to discard (must be >= 0).
* @param N2 Number of integers to include in the chunk (must be >= 0).
*
* @return Chunk.
*
* @exception IllegalArgumentException
* (unchecked exception) Thrown if N1 or N2 is out of
* bounds.
*/
public Range chunk
(int N1,
int N2)
{
// Verify preconditions.
if (N1 < 0)
{
throw new IllegalArgumentException
("Range.chunk(): N1 = " + N1 + " illegal");
}
if (N2 < 0)
{
throw new IllegalArgumentException
("Range.chunk(): N2 = " + N2 + " illegal");
}
Range result = new Range();
result.lb = this.lb + N1 * this.stride;
result.stride = this.stride;
result.length = Math.min (N2, Math.max (0, this.length - N1));
result.setUb();
return result;
}
/**
* Determine if this range is equal to the given object. Two ranges are
* equal if they both have the same lower bound, stride, and length.
*
* @param obj Object to test.
*
* @return True if this range is equal to obj, false otherwise.
*/
public boolean equals
(Object obj)
{
return
obj instanceof Range &&
this.lb == ((Range) obj).lb &&
this.stride == ((Range) obj).stride &&
this.length == ((Range) obj).length;
}
/**
* Returns a hash code for this range.
*/
public int hashCode()
{
return (((this.lb << 10) + this.stride) << 10) + this.length;
}
/**
* Returns a string version of this range. If the stride is 1, the format is
* "L..U", where L is the lower bound and
* U is the upper bound. If the stride is greater than 1, the format
* is "L..U;S", where L is the lower
* bound, U is the upper bound, and S is the stride.
*/
public String toString()
{
StringBuilder b = new StringBuilder();
b.append (lb);
b.append ("..");
b.append (ub);
if (stride > 1)
{
b.append (';');
b.append (stride);
}
return b.toString();
}
/**
* Write this range to the given object output stream.
*
* @param out Object output stream.
*
* @exception IOException
* Thrown if an I/O error occurred.
*/
public void writeExternal
(ObjectOutput out)
throws IOException
{
out.writeInt (lb);
out.writeInt (stride);
out.writeInt (length);
}
/**
* Read this range from the given object input stream.
*
* @param in Object input stream.
*
* @exception IOException
* Thrown if an I/O error occurred.
*/
public void readExternal
(ObjectInput in)
throws IOException
{
lb = in.readInt();
stride = in.readInt();
length = in.readInt();
setUb();
}
// Hidden operations.
/**
* Set the upper bound of this range based on the lower bound, stride, and
* length.
*/
private void setUb()
{
ub = lb + (length - 1) * stride;
}
// Unit test main program.
// /**
// * Unit test main program.
// */
// public static void main
// (String[] args)
// {
// if (args.length != 4)
// {
// System.err.println ("Usage: edu.rit.util.Range ");
// System.exit (1);
// }
// int lb = Integer.parseInt (args[0]);
// int ub = Integer.parseInt (args[1]);
// int stride = Integer.parseInt (args[2]);
// int size = Integer.parseInt (args[3]);
// Range range = new Range (lb, ub, stride);
// System.out.println
// ("Range = " + range + ", length = " + range.length());
// for (int rank = 0; rank < size; ++ rank)
// {
// Range subrange = range.subrange (size, rank);
// System.out.println
// ("Subrange rank " + rank + " = " + subrange +
// ", length = " + subrange.length());
// }
// Range[] subranges = range.subranges (size);
// for (int rank = 0; rank < size; ++ rank)
// {
// System.out.println
// ("Subranges[" + rank + "] = " + subranges[rank] +
// ", length = " + subranges[rank].length());
// }
// }
}
Ads help maintain this website.