19
\$\begingroup\$

Introduction

After getting stuck with a Pythonish integer range 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.

\$\endgroup\$
  • 4
    \$\begingroup\$ instead of implementing Collection, I would add a simple asList method 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 Dec 1 '15 at 21:54
  • \$\begingroup\$ Follow-up question \$\endgroup\$ – 200_success Dec 2 '15 at 9:33
  • \$\begingroup\$ Of course, if Jython is available as an alternative... ;) \$\endgroup\$ – Wayne Werner Dec 2 '15 at 14:04
25
\$\begingroup\$

If you're targeting Java 8, then you should make an IntStream and a PrimitiveIterator.OfInt instead. You can do more interesting manipulations with an IntStream, and the primitive types would be more efficient than the boxed types.

In fact, there is already an IntStream.range(startInclusive, endExclusive) function. You could simply .map() that to another IntStream with a step other than 1.


You have three range(…) functions and three corresponding Range(…) constructors. I suggest that you make a design decision and stick with it. From PEP 20 (The Zen of Python):

There should be one-- and preferably only one --obvious way to do it.

Assuming that you want three static range(…) functions, then they should all call one private Range(int start, int stop, int step) constructor.

Python's documentation calls the three parameters start, stop, and step, and you should, too. Alternatively, adopt Java 8's startInclusive, endExclusive terminology.


I think you would be better off with one RangeIterator class. Its hasNext() method can just decide what to do based on whether the step is positive or negative.

Since the iterator is not a static inner class, it can access the start, stop, and step of the outer class instead of making a copy.


You could write less code if you extended AbstractCollection instead of implementing Collection from scratch.

To implement an unmodifiable collection, the programmer needs only to extend this class and provide implementations for the iterator and size methods. (The iterator returned by the iterator method must implement hasNext and next.)

I would also override contains() for efficiency. size() and contains() 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;
                }
            }
        };
    }
}
\$\endgroup\$
  • \$\begingroup\$ But ArrayList doesn't accept an AbstractCollection as constructor parameter (which I suspect is the main use of implementing Collection in this case) \$\endgroup\$ – njzk2 Dec 1 '15 at 22:05
  • 1
    \$\begingroup\$ @njzk2 What do you mean? Why does that matter? \$\endgroup\$ – 200_success Dec 1 '15 at 23:07
  • 1
    \$\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 Dec 2 '15 at 0:08
  • \$\begingroup\$ @Eyal range(start, stop, step) is the Python model that we want to try to emulate here. If Range.range(…) is too cumbersome, then an import static could help. \$\endgroup\$ – 200_success Dec 2 '15 at 0:10
  • 1
    \$\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 Dec 2 '15 at 0:14
14
\$\begingroup\$

Minor 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

\$\endgroup\$
  • 4
    \$\begingroup\$ I consider that minor point to be quite major \$\endgroup\$ – Pharap Dec 2 '15 at 12:00
  • 3
    \$\begingroup\$ Also; please tell what it should 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\$ – RobAu Dec 2 '15 at 14:40
0
\$\begingroup\$

In 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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.