\$\begingroup\$\$\endgroup\$
3Introduction
After getting stuck with a Pythonish integerrange in C++, I rewrote the facility in Java. In Python you can say:
>>> range(38, 0, -3)[38, 35, 32, 29, 26, 23, 20, 17, 14, 11, 8, 5, 2]
In Java you can say:
for (int i : range(10)) { ...}
or, if need be:
List<Integer> list = new ArrayList<>(range(100, -100, -7));
Implementation
Range.java:
package net.coderodde.util;import java.util.ArrayList;import java.util.Arrays;import java.util.Collection;import java.util.Iterator;import java.util.List;import java.util.NoSuchElementException;/** * This class implements an iterator over an arithmetic progression of integers. * * @author Rodion "rodde" Efremov * @version 1.6 (Dec 1, 2015) */public class Range implements Iterable<Integer>, Collection<Integer> { private final int start; private final int step; private final int end; public static Range range(int start, int end, int step) { return new Range(start, end, step); } public static Range range(int start, int end) { return new Range(start, end); } public static Range range(int end) { return new Range(end); } public Range(int start, int end, int step) { if (step == 0) { throw new IllegalArgumentException("The step is zero."); } this.start = start; this.step = step; this.end = end; } public Range(int start, int end) { this(start, end, 1); } public Range(int end) { this(0, end); } @Override public Iterator<Integer> iterator() { if (start <= end) { return new AscendingRangeIterator(start, step, (step < 0 ? start : end)); } else { return new DescendingRangeIterator(start, step, (step > 0 ? start : end)); } } @Override public int size() { if (start <= end) { if (step < 0) { return 0; } int rangeLength = end - start; return rangeLength / step + (rangeLength % step != 0 ? 1 : 0); } else { if (step > 0) { return 0; } int rangeLength = start - end; return rangeLength / -step + (rangeLength % -step != 0 ? 1 : 0); } } @Override public boolean isEmpty() { return size() == 0; } @Override public boolean contains(Object o) { if (!(o instanceof Integer)) { return false; } if (start <= end) { if (step < 0) { return false; } Integer other = (Integer) o; if (other < start || other >= end) { return false; } return (other - start) % step == 0; } else { if (step > 0) { return false; } Integer other = (Integer) o; if (other > start || other <= end) { return false; } return (start - other) % -step == 0; } } @Override public Object[] toArray() { Object[] array = new Object[size()]; // We could have iterated using the iterator, yet we optimize this a bit if (start <= end) { if (step > 0) { for (int j = 0, i = start; i < end; i += step, ++j) { array[j] = i; } } } else { if (step < 0) { for (int j = 0, i = start; i > end; i += step, ++j) { array[j] = i; } } } return array; } @SuppressWarnings("unchecked") @Override public <T> T[] toArray(T[] a) { T[] ret; int size = size(); if (a.length < size) { ret = Arrays.copyOf(a, size); } else { ret = a; } if (start <= end) { if (step > 0) { for (int i = start, j = 0; i < end; i += step, ++j) { ret[j] = (T) Integer.valueOf(i); } } } else { if (step < 0) { for (int i = start, j = 0; i > end; i += step, ++j) { ret[j] = (T) Integer.valueOf(i); } } } if (size < ret.length) { ret[size] = null; } return ret; } @Override public boolean add(Integer e) { throw new UnsupportedOperationException( "Adding to Range is not supported."); } @Override public boolean remove(Object o) { throw new UnsupportedOperationException( "Removing from Range is not supported."); } @Override public boolean containsAll(Collection<?> c) { for (Object o : c) { if (!contains(o)) { return false; } } return true; } @Override public boolean addAll(Collection<? extends Integer> c) { throw new UnsupportedOperationException( "Adding to Range is not supported."); } @Override public boolean removeAll(Collection<?> c) { throw new UnsupportedOperationException( "Removing from Range is not supported."); } @Override public boolean retainAll(Collection<?> c) { throw new UnsupportedOperationException( "Retaining in Range is not supported."); } @Override public void clear() { throw new UnsupportedOperationException( "Clearing a Range is not supported."); } private final class AscendingRangeIterator implements Iterator<Integer> { private int value; private final int step; private final int boundValue; AscendingRangeIterator(int value, int step, int boundValue) { this.value = value; this.step = step; this.boundValue = boundValue; } @Override public boolean hasNext() { return value < boundValue; } @Override public Integer next() { if (!hasNext()) { throw new NoSuchElementException("Iteration exceeded."); } int ret = value; value += step; return ret; } } private final class DescendingRangeIterator implements Iterator<Integer> { private int value; private final int step; private final int boundValue; DescendingRangeIterator(int value, int step, int boundValue) { this.value = value; this.step = Math.abs(step); this.boundValue = boundValue; } @Override public boolean hasNext() { return value > boundValue; } @Override public Integer next() { if (!hasNext()) { throw new NoSuchElementException("Iteration exceeded."); } int ret = value; value -= step; return ret; } } public static void main(String[] args) { Range r = range(100, 10, -3); List<Integer> list = new ArrayList<>(r); int j = 0; for (int i : r) { System.out.printf("%3d : %3d\n", i, list.get(j++)); } }}RangeTest.java:
package net.coderodde.util;import java.util.ArrayList;import java.util.HashSet;import java.util.Iterator;import java.util.List;import java.util.Set;import org.junit.Test;import static org.junit.Assert.*;import static net.coderodde.util.Range.*;public class RangeTest { @Test public void testRange_3args() { ///////////////////////////////////////////////////////// List<Integer> list = new ArrayList<>(range(37, -11, -5)); ///////////////////////////////////////////////////////// assertEquals(10, list.size()); for (int i = 37, j = 0; i > -11; i -= 5, ++j) { assertEquals(Integer.valueOf(i), list.get(j)); } Range r = range(10, 50, 7); assertTrue(r.contains(10)); assertTrue(r.contains(17)); assertTrue(r.contains(24)); assertTrue(r.contains(31)); assertTrue(r.contains(38)); assertTrue(r.contains(45)); assertEquals(6, r.size()); Iterator<Integer> iterator = r.iterator(); for (int i = 10; i < 50; i += 7) { assertTrue(iterator.hasNext()); assertEquals(Integer.valueOf(i), iterator.next()); } assertFalse(iterator.hasNext()); for (int i = -100; i < 10; ++i) { assertFalse(r.contains(i)); } for (int i = 50; i < 100; ++i) { assertFalse(r.contains(i)); } //// for (int step = -1; step > -10; --step) { r = range(5, 50, step); assertEquals(0, r.size()); assertFalse(r.iterator().hasNext()); } for (int step = 1; step < 10; ++step) { r = range(50, 5, step); assertEquals(0, r.size()); assertFalse(r.iterator().hasNext()); } } @Test public void testRange_int_int() { Range r = range(10, 17); for (int i = 10; i < 17; ++i) { assertTrue(r.contains(i)); } assertEquals(7, r.size()); Iterator<Integer> iterator = r.iterator(); for (int i = 10; i < 17; ++i) { assertTrue(iterator.hasNext()); assertEquals(Integer.valueOf(i), iterator.next()); } assertFalse(iterator.hasNext()); for (int i = -100; i < 10; ++i) { assertFalse(r.contains(i)); } for (int i = 17; i < 100; ++i) { assertFalse(r.contains(i)); } } @Test public void testRange_int() { Range r = range(5); for (int i = 0; i < 5; ++i) { assertTrue(r.contains(i)); } assertEquals(5, r.size()); Iterator<Integer> iterator = r.iterator(); for (int i = 0; i < 5; ++i) { assertTrue(iterator.hasNext()); assertEquals(Integer.valueOf(i), iterator.next()); } assertFalse(iterator.hasNext()); } @Test public void testIterator() { Range r = range(50, 1, -3); assertEquals(17, r.size()); Iterator<Integer> iterator = r.iterator(); assertEquals(Integer.valueOf(50), iterator.next()); assertEquals(Integer.valueOf(47), iterator.next()); assertEquals(Integer.valueOf(44), iterator.next()); assertEquals(Integer.valueOf(41), iterator.next()); assertEquals(Integer.valueOf(38), iterator.next()); assertEquals(Integer.valueOf(35), iterator.next()); assertEquals(Integer.valueOf(32), iterator.next()); assertEquals(Integer.valueOf(29), iterator.next()); assertEquals(Integer.valueOf(26), iterator.next()); assertEquals(Integer.valueOf(23), iterator.next()); assertEquals(Integer.valueOf(20), iterator.next()); assertEquals(Integer.valueOf(17), iterator.next()); assertEquals(Integer.valueOf(14), iterator.next()); assertEquals(Integer.valueOf(11), iterator.next()); assertEquals(Integer.valueOf(8), iterator.next()); assertEquals(Integer.valueOf(5), iterator.next()); assertEquals(Integer.valueOf(2), iterator.next()); assertFalse(iterator.hasNext()); } @Test public void testSize() { Range r = range(10, 2, -2); assertEquals(4, r.size()); r = range(2, 10, 2); assertEquals(4, r.size()); r = range(10, 2, 2); assertEquals(0, r.size()); r = range(2, 10, -2); assertEquals(0, r.size()); } @Test public void testIsEmpty() { Range r = range(0); assertTrue(r.isEmpty()); r = range(20, 33, 3); assertFalse(r.isEmpty()); r = range(20, 33, -3); assertTrue(r.isEmpty()); r = range(33, 20, -3); assertFalse(r.isEmpty()); r = range(33, 20, 3); assertTrue(r.isEmpty()); } @Test public void testContains() { Range r = range(10, 0, 2); for (int i = 0; i <= 10; i += 2) { assertFalse(r.contains(i)); } r = range(10, 1, -2); for (int i = 10; i > 1; i -= 2) { assertTrue(r.contains(i)); } r = range(10, 0, -2); for (int i = 10; i > 0; i -= 2) { assertTrue(r.contains(i)); } r = range(10, -1, -2); for (int i = 10; i >= 0; i -= 2) { assertTrue(r.contains(i)); } //// r = range(20, 50, 4); for (int i = 20; i < 50; i += 4) { assertTrue(r.contains(i)); } } @Test public void testToArray_0args() { Range r = range(-10, 10, 2); Object[] arr = r.toArray(); assertEquals(10, arr.length); for (int i = 0, j = -10; i < arr.length; ++i, j += 2) { assertEquals(j, arr[i]); } r = range(10, -10, -2); arr = r.toArray(); assertEquals(10, arr.length); for (int i = 0, j = 10; i < arr.length; ++i, j -= 2) { assertEquals(j, arr[i]); } } @Test public void testToArray_GenericType() { Range r = range(37, 21, -1); Integer[] input = new Integer[4]; Integer[] array = r.toArray(input); assertFalse(input == array); assertEquals(r.size(), array.length); input = new Integer[50]; for (int i = 0; i < input.length; ++i) { input[i] = Integer.valueOf(-1); } array = r.toArray(input); assertTrue(array == input); assertNull(input[r.size()]); for (int i = r.size() + 1; i < input.length; ++i) { assertEquals(Integer.valueOf(-1), input[i]); } } public void testContainsAll() { Range r = range(20, 3, -3); Set<Integer> set = new HashSet<>(); set.add(20); set.add(14); set.add(11); assertTrue(r.containsAll(set)); set.add(19); assertFalse(r.containsAll(set)); } @Test(expected = UnsupportedOperationException.class) public void testAdd() { range(10).add(1); } @Test(expected = UnsupportedOperationException.class) public void testRemove() { range(10).remove(1); } @Test(expected = UnsupportedOperationException.class) public void testAddAll() { range(2, 12).addAll(new HashSet<>()); } @Test(expected = UnsupportedOperationException.class) public void testRemoveAll() { range(2, 12).removeAll(new HashSet<>()); } @Test(expected = UnsupportedOperationException.class) public void testRetainAll() { range(2, 12).retainAll(new HashSet<>()); } @Test(expected = UnsupportedOperationException.class) public void testClear() { range(5).clear(); }}As always, any critique is much appreciated.
- 5\$\begingroup\$instead of implementing
Collection, I would add a simpleasListmethod that would iterate and create a List from the range (because the way it is now, it seems the only use of being a Collection is to pass it to the ArrayList constructor. It would also remove half the code - less chance of bug.) For example:github.com/smaspe/FunctionalIterables/blob/master/src/main/java/…\$\endgroup\$njzk2– njzk22015-12-01 21:54:27 +00:00CommentedDec 1, 2015 at 21:54 - \$\begingroup\$Follow-up question\$\endgroup\$200_success– 200_success2015-12-02 09:33:46 +00:00CommentedDec 2, 2015 at 9:33
- 1\$\begingroup\$Of course, if Jython is available as an alternative... ;)\$\endgroup\$Wayne Werner– Wayne Werner2015-12-02 14:04:20 +00:00CommentedDec 2, 2015 at 14:04
3 Answers3
\$\begingroup\$\$\endgroup\$
2Minor point.
The step is zero
is an odd error message. Wouldn't it be better to actual explain the problem, ie.
The step cannot be zero
The user (hopefully) knows what paramaters they've supplied, what you need to tell them is that the parameter is invalid.
As@200_success pointed out in a comment, Python follows this with its own error messages:
Python 2
ValueError: range() step argument must not be zero
Python 3
ValueError: range() arg 3 must not be zero
- 4\$\begingroup\$I consider that minor point to be quite major\$\endgroup\$Pharap– Pharap2015-12-02 12:00:04 +00:00CommentedDec 2, 2015 at 12:00
- 3\$\begingroup\$Also; please tell what itshould be. For example: The step is 0. It should be greater than 0. This might seem 'too much', but people need more brainpower processing negations.\$\endgroup\$Rob Audenaerde– Rob Audenaerde2015-12-02 14:40:51 +00:00CommentedDec 2, 2015 at 14:40
\$\begingroup\$
\$\endgroup\$
10If you're targeting Java 8, then you should make anIntStream and aPrimitiveIterator.OfInt instead. You can do more interesting manipulations with anIntStream, and the primitive types would be more efficient than the boxed types.
In fact, there is already anIntStream.range(startInclusive, endExclusive) function. You could simply.map() that to anotherIntStream with astep other than 1.
You have threerange(…) functions and three correspondingRange(…) constructors. I suggest that you make a design decision and stick with it. FromPEP 20 (The Zen of Python):
There should be one-- and preferably only one --obvious way to do it.
Assuming that you want three staticrange(…) functions, then they should all call oneprivate Range(int start, int stop, int step) constructor.
Python's documentation calls the three parametersstart,stop, andstep, and you should, too. Alternatively, adopt Java 8'sstartInclusive,endExclusive terminology.
I think you would be better off with oneRangeIterator class. ItshasNext() method can just decide what to do based on whether thestep is positive or negative.
Since the iterator is not a static inner class, it can access thestart,stop, andstep of the outer class instead of making a copy.
You could write less code if you extendedAbstractCollection instead of implementingCollection from scratch.
To implement an unmodifiable collection, the programmer needs only to extend this class and provide implementations for the
iteratorandsizemethods. (The iterator returned by theiteratormethod must implementhasNextandnext.)
I would also overridecontains() for efficiency.size() andcontains() would be better implemented using a bit of math instead of all those conditionals.
With all of the changes suggested above, there can be a lot less code:
public class Range extends AbstractCollection<Integer> implements Iterable<Integer> { private final int start, stop, step; public static Range range(int start, int stop, int step) { return new Range(start, stop, step); } public static Range range(int start, int stop) { return range(start, stop, 1); } public static Range range(int stop) { return range(0, stop); } private Range(int start, int stop, int step) { if (step == 0) { throw new IllegalArgumentException("The step must not be zero."); } this.start = start; this.stop = stop; this.step = step; } @Override public int size() { return Math.max(0, step >= 0 ? (stop + step - 1 - start) / step : (stop + step + 1 - start) / step); } @Override public boolean contains(Object o) { try { int n = (int)o; boolean inBounds = step >= 0 ? (start <= n) && (n < stop) : (start >= n) && (n > stop); return inBounds && (n - start) % step == 0; } catch (ClassCastException notAnInt) { return false; } } @Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { private int value = start; @Override public boolean hasNext() { return step >= 0 ? value < stop : value > stop; } @Override public Integer next() { if (!hasNext()) { throw new NoSuchElementException("Iteration exceeded."); } try { return value; } finally { value += step; } } }; }}
- \$\begingroup\$But ArrayList doesn't accept an AbstractCollection as constructor parameter (which I suspect is the main use of implementing
Collectionin this case)\$\endgroup\$njzk2– njzk22015-12-01 22:05:43 +00:00CommentedDec 1, 2015 at 22:05 - 1\$\begingroup\$@njzk2 What do you mean? Why does that matter?\$\endgroup\$200_success– 200_success2015-12-01 23:07:26 +00:00CommentedDec 1, 2015 at 23:07
- 2\$\begingroup\$The range call looks odd Range.range(…). Wouldn't a call chain be better in this situation? Range.stop(exclusive).start(inclusive).step(step)\$\endgroup\$Eyal– Eyal2015-12-02 00:08:18 +00:00CommentedDec 2, 2015 at 0:08
- 2\$\begingroup\$@200_success acknowledged. Though some things work well on one language and not as much on the next. We should aim to capture purpose of the original function and implement it in the java way.\$\endgroup\$Eyal– Eyal2015-12-02 00:14:47 +00:00CommentedDec 2, 2015 at 0:14
- 1\$\begingroup\$For the
contains()method, using exceptions in unexceptional cases is usually frowned upon.if (o instanceof Integer) return false; int n =...would be better.\$\endgroup\$Ypnypn– Ypnypn2015-12-02 01:22:31 +00:00CommentedDec 2, 2015 at 1:22
\$\begingroup\$\$\endgroup\$
1In Python 3,range returns a sequence which is exactly what you made. In Python 2 however,range eagerly produces a list, which would cut your code into a single function, returning an integer list. (I dont know Java to show example code.) I am not saying you should make anything different, just pointing that out.
Also, I am not sure if incompatible type should result in returning false or an exception. Maybe you can provide some precedence for this behavior?
- \$\begingroup\$Thoughmost of the popular Python packages support Python3. Sure there are people stuck in the Python 2 world, but there are more and more incentives for people to port/use Python 3 now.\$\endgroup\$Wayne Werner– Wayne Werner2015-12-02 14:09:40 +00:00CommentedDec 2, 2015 at 14:09
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.