|
Java example source code file (LongRange.java)
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; } } } Other Java examples (source code examples)Here is a short list of links related to this Java LongRange.java source code file: |
... this post is sponsored by my books ... | |
![]() #1 New Release! |
![]() FP Best Seller |
Copyright 1998-2024 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.