Java example source code file (LongRange.java)

This example Java source code file (LongRange.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

boundscheck, chunk_size, counted, ichunk, ichunkedseq, iseq, iterator, longchunk, longrange, longrangeiterator, nosuchelementexception, object, reduced, serializable, util

The LongRange.java Java example source code

/**
 *   Copyright (c) Rich Hickey. All rights reserved.
 *   The use and distribution terms for this software are covered by the
 *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
 *   which can be found in the file epl-v10.html at the root of this distribution.
 *   By using this software in any fashion, you are agreeing to be bound by
 * 	 the terms of this license.
 *   You must not remove this notice, or any other, from this software.
 **/

package clojure.lang;

import java.io.Serializable;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Implements the special common case of a finite range based on long start, end, and step.
 */
public class LongRange extends ASeq implements Counted, IChunkedSeq, IReduce {

private static final int CHUNK_SIZE = 32;

// Invariants guarantee this is never an empty or infinite seq
//   assert(start != end && step != 0)
final long start;
final long end;
final long step;
final BoundsCheck boundsCheck;
private volatile LongChunk _chunk;  // lazy
private volatile ISeq _chunkNext;        // lazy
private volatile ISeq _next;             // cached

private static interface BoundsCheck extends Serializable {
    boolean exceededBounds(long val);
}

private static BoundsCheck positiveStep(final long end) {
    return new BoundsCheck() {
        public boolean exceededBounds(long val){
            return (val >= end);
        }
    };
}

private static BoundsCheck negativeStep(final long end) {
    return new BoundsCheck() {
        public boolean exceededBounds(long val){
            return (val <= end);
        }
    };
}

private LongRange(long start, long end, long step, BoundsCheck boundsCheck){
    this.start = start;
    this.end = end;
    this.step = step;
    this.boundsCheck = boundsCheck;
}

private LongRange(long start, long end, long step, BoundsCheck boundsCheck, LongChunk chunk, ISeq chunkNext){
    this.start = start;
    this.end = end;
    this.step = step;
    this.boundsCheck = boundsCheck;
    this._chunk = chunk;
    this._chunkNext = chunkNext;
}

private LongRange(IPersistentMap meta, long start, long end, long step, BoundsCheck boundsCheck, LongChunk chunk, ISeq chunkNext){
    super(meta);
    this.start = start;
    this.end = end;
    this.step = step;
    this.boundsCheck = boundsCheck;
    this._chunk = chunk;
    this._chunkNext = chunkNext;
}

public static ISeq create(long end) {
    if(end > 0)
        return new LongRange(0L, end, 1L, positiveStep(end));
    return PersistentList.EMPTY;
}

public static ISeq create(long start, long end) {
    if(start >= end)
        return PersistentList.EMPTY;
    return new LongRange(start, end, 1L, positiveStep(end));
}

public static ISeq create(final long start, long end, long step) {
    if(step > 0) {
        if(end <= start) return PersistentList.EMPTY;
        return new LongRange(start, end, step, positiveStep(end));
    } else if(step < 0) {
        if(end >= start) return PersistentList.EMPTY;
        return new LongRange(start, end, step, negativeStep(end));
    } else {
        if(end == start) return PersistentList.EMPTY;
        return Repeat.create(start);
    }
}

public Obj withMeta(IPersistentMap meta){
    if(meta == _meta)
        return this;
    return new LongRange(meta, start, end, step, boundsCheck, _chunk, _chunkNext);
}

public Object first() {
    return start;
}

public void forceChunk() {
    if(_chunk != null) return;

    long count;
    try {
        count = rangeCount(start, end, step);
    } catch(ArithmeticException e) {
        // size of total range is > Long.MAX_VALUE so must step to count
        // this only happens in pathological range cases like:
        // (range -9223372036854775808 9223372036854775807 9223372036854775807)
        count = steppingCount(start, end, step);
    }

    if (count > CHUNK_SIZE) { // not last chunk
        long nextStart = start + (step * CHUNK_SIZE);   // cannot overflow, must be < end
        _chunk = new LongChunk(start, step, CHUNK_SIZE);
        _chunkNext = new LongRange(nextStart, end, step, boundsCheck);
    } else {  // last chunk
        _chunk = new LongChunk(start, step, (int) count);   // count must be <= CHUNK_SIZE
    }
}

public ISeq next() {
    if(_next != null)
        return _next;

    forceChunk();
    if(_chunk.count() > 1) {
        LongChunk smallerChunk = _chunk.dropFirst();
        _next = new LongRange(smallerChunk.first(), end, step, boundsCheck, smallerChunk, _chunkNext);
        return _next;
    }
    return chunkedNext();
}

public IChunk chunkedFirst() {
    forceChunk();
    return _chunk;
}

public ISeq chunkedNext() {
    return chunkedMore().seq();
}

public ISeq chunkedMore() {
    forceChunk();
    if(_chunkNext == null)
        return PersistentList.EMPTY;
    return _chunkNext;
}

// fallback count mechanism for pathological cases
// returns either exact count or CHUNK_SIZE+1
long steppingCount(long start, long end, long step) {
    long count = 1;
    long s = start;
    while(count <= CHUNK_SIZE) {
        try {
            s = Numbers.add(s, step);
            if(boundsCheck.exceededBounds(s))
                break;
            else
                count++;
        } catch(ArithmeticException e) {
            break;
        }
    }
    return count;
}

// returns exact size of remaining items OR throws ArithmeticException for overflow case
long rangeCount(long start, long end, long step) {
    // (1) count = ceiling ( (end - start) / step )
    // (2) ceiling(a/b) = (a+b+o)/b where o=-1 for positive stepping and +1 for negative stepping
    // thus: count = end - start + step + o / step
    return Numbers.add(Numbers.add(Numbers.minus(end, start), step), this.step > 0 ? -1 : 1) / step;
}

public int count() {
    try {
        long c = rangeCount(start, end, step);
        if(c > Integer.MAX_VALUE) {
            return Numbers.throwIntOverflow();
        } else {
            return (int) c;
        }
    } catch(ArithmeticException e) {
        // rare case from large range or step, fall back to iterating and counting
        Iterator iter = this.iterator();
        long count = 0;
        while(iter.hasNext()) {
            iter.next();
            count++;
        }

        if(count > Integer.MAX_VALUE)
            return Numbers.throwIntOverflow();
        else
            return (int)count;
    }
}

public Object reduce(IFn f) {
    Object acc = start;
    long i = start + step;
    while(! boundsCheck.exceededBounds(i)) {
        acc = f.invoke(acc, i);
        if (acc instanceof Reduced) return ((Reduced)acc).deref();
        i += step;
    }
    return acc;
}

public Object reduce(IFn f, Object val) {
    Object acc = val;
    long i = start;
    do {
        acc = f.invoke(acc, i);
        if (RT.isReduced(acc)) return ((Reduced)acc).deref();
        i += step;
    } while(! boundsCheck.exceededBounds(i));
    return acc;
}

public Iterator iterator() {
    return new LongRangeIterator();
}

class LongRangeIterator implements Iterator {
    private long next;
    private boolean hasNext;

    public LongRangeIterator() {
        this.next = start;
        this.hasNext = true;
    }

    public boolean hasNext() {
        return hasNext;
    }

    public Object next() {
        if (hasNext) {
            long ret = next;
            try {
                next = Numbers.add(next, step);
                hasNext = ! boundsCheck.exceededBounds(next);
            } catch(ArithmeticException e) {
                hasNext = false;
            }
            return ret;
        } else {
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

private static class LongChunk implements IChunk, Serializable {
    final long start;
    final long step;
    final int count;

    public LongChunk(long start, long step, int count) {
        this.start = start;
        this.step = step;
        this.count = count;
    }

    public long first(){
        return start;
    }

    public Object nth(int i){
        return start + (i * step);
    }

    public Object nth(int i, Object notFound){
        if(i >= 0 && i < count)
            return start + (i * step);
        return notFound;
    }

    public int count(){
        return count;
    }

    public LongChunk dropFirst(){
        if(count <= 1)
            throw new IllegalStateException("dropFirst of empty chunk");
        return new LongChunk(start+step, step, count-1);
    }

    public Object reduce(IFn f, Object init) {
        long x = start;
        Object ret = init;
        for(int i=0; i<count; i++) {
            ret = f.invoke(ret, x);
            if(RT.isReduced(ret))
                return ret;
            x += step;
        }
        return ret;
    }

}
}