Ranges

credit for this assignment: Finn Voichick and Dennis Cosgrove

Motivation

Coarsening, or n-way split as we tend to call it in this course, comes up a fair amount. In this studio, we will create a Range class and a slice utility method, that allows us to split up our data n-times (depending on what value we pass in) in a consistent organized fashion. This makes sure that each thread is balanced in the work that it does, minimizing the Critical Path Length.

Since we will be utilizing this class throughout the semester in different studios and assignments, it is important that data is split up in a specific way. The tests should help make sure your solution is strictly adhering to the specification.

Background

Iterable and Iterator

Video: DOM NodeList Iterable Demo

Mistakes To Avoid

Warning: Do NOT Parallelize

This exercise is about creating an easier way to split data so that it can be worked on in parallel. The splitting of the data is still done sequentially. That means at no point in this exercise should you be using fork() or join().

Code to Investigate

RangeIterationClient

class:	RangeIterationClient.java	CLIENT
package:	range.client
source folder:	student/src/main/java

Much can be gleaned about how Range and RangeIterator must operate from this client.

First, a new Range from 16 to 24 (exclusive) is created. Invoking the min() and maxExclusive() methods on that instance reveals that the values passed to the constructor have been stored as instance variables for later use.

Then, whether

1. explicitly, via the range's iterator() method and the iterator's hasNext() and next() methods, or
2. via the for each loop

the numbers 16, 17, 18, 19, 20, 21, 22, and 23 are marched through.

RangeIterationClient

Range range = new Range(16, 24); System.out.println(" min: " + range.min()); System.out.println("maxExclusive: " + range.maxExclusive()); System.out.println(); System.out.println("via while loop"); Iterator<Integer> iter = range.iterator(); while (iter.hasNext()) { int i = iter.next(); System.out.println(i); } System.out.println(); System.out.println("via for each loop"); for(int i : range) { System.out.println(i); }

RangeIterationClient Output
min: 16 maxExclusive: 24 via while loop 16 17 18 19 20 21 22 23 via for each loop 16 17 18 19 20 21 22 23

Code to Implement

Warning: There is a Range.java and a Ranges.java. Implement Range.java first

class Range

class:	Range.java
methods:	constructor min maxExclusive iterator
package:	range.exercise
source folder:	student/src/main/java

constructor

method: public Range(int min, int maxExclusive) (sequential implementation only)

To support the required methods below we will need to hang onto the parameter values as instance variables (a.k.a. fields).

min

method: public int min() (sequential implementation only)

maxExclusive

method: public int maxExclusive() (sequential implementation only)

iterator

method: public Iterator<Integer> iterator() (sequential implementation only)

class Range implements the Iterable<Integer> interface. As such, it must implement the iterator method. Use the class RangeIterator outlined in the next section to fulfill this method.

RangeIterator

class:	RangeIterator.java
methods:	constructor hasNext next
package:	range.exercise
source folder:	student/src/main/java

constructor and instance variables

The RangeIterator constructor accepts the Range to iterate over. You will need to hang onto this Range in an instance variable, as well as initializing whatever state is required to support iteration.

RangeIterator(Range range) {
	throw new NotYetImplementedException();
}

hasNext()

To implement the Iterator interface, you must meet the specification of hasNext(), and

next()

the specification for next().

class Ranges

class:	Ranges.java
methods:	slice
package:	range.exercise
source folder:	student/src/main/java

slice

method: public static Range[] slice(int min, int maxExclusive, int numRanges) (sequential implementation only)

Given a range [minInclusive, maxExclusive) and a number of slices to make, return an array of Ranges. Understanding what a Range is and how it is used is important when writing this solution.

The goal is to have each slice's range be the entire array when put together, with no overlap. Some examples are giving below. Working through more examples can be a helpful way of figuring out what code to write if you get stuck.

Tip: For any instance of Range, the minimum is inclusive and the maximum is exclusive. This means for two slices next to each other, range1.getMaxExclusive() is equal to range2.getMinInclusive().

Strict Specification

We are overly strict about the specification of how the data must be sliced up. This is to allow to accurately compare results intermediate results throughout the semester.

Example: array.length=8; numRanges=4

A

A

B

B

C

C

D

D

Slice ID	Min Inclusive	Max Exclusive
0	0	2
1	2	4
2	4	6
3	6	8

Example: array.length=7; numRanges=4

Distribute the remainder 1 each to the lower end slices (the first few slices or the lower index slices).

A

A

B

B

C

C

D

Slice ID	Min Inclusive	Max Exclusive
0	0	2
1	2	4
2	4	6
3	6	7

Warning:Do NOT slice up the data by giving all of the remainder to one slice

A |B |C |D |D |D |D

Giving all the remainder to one range does not most effectively balance the workload!

Testing Your Solution

Correctness

class:	__RangeExerciseTestSuite.java
package:	range.example
source folder:	testing/src/test/java

Pledge, Acknowledgments, Citations

file:

exercise-ranges-pledge-acknowledgments-citations.txt

More info about the Honor Pledge