/**
 *   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,
 * with no more than Integer.MAX_VALUE items.
 */
public class LongRange extends ASeq implements Counted, IChunkedSeq, IReduce, IDrop {

private static final long serialVersionUID = -1467242400566893909L;

// 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 int count;

private LongRange(long start, long end, long step, int count){
    this.start = start;
    this.end = end;
    this.step = step;
    this.count = count;
}

private LongRange(IPersistentMap meta, long start, long end, long step, int count){
    super(meta);
    this.start = start;
    this.end = end;
    this.step = step;
    this.count = count;
}

// returns exact size of remaining items OR throws ArithmeticException for overflow case
static 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), step > 0 ? -1 : 1) / step;
}

public static ISeq create(long end) {
    if(end > 0) {
        try {
            return new LongRange(0L, end, 1L, Math.toIntExact(rangeCount(0L, end, 1L)));
        } catch(ArithmeticException e) {
            return Range.create(end);  // count > Integer.MAX_VALUE
        }
    } else {
        return PersistentList.EMPTY;
    }
}

public static ISeq create(long start, long end) {
    if(start >= end) {
        return PersistentList.EMPTY;
    } else {
        try {
            return new LongRange(start, end, 1L, Math.toIntExact(rangeCount(start, end, 1L)));
        } catch(ArithmeticException e) {
            return Range.create(start, end);
        }
    }
}

public static ISeq create(final long start, long end, long step) {
    if(step > 0) {
        if(end <= start) return PersistentList.EMPTY;
        try {
            return new LongRange(start, end, step, Math.toIntExact(rangeCount(start, end, step)));
        } catch(ArithmeticException e) {
            return Range.create(start, end, step);
        }
    } else if(step < 0) {
        if(end >= start) return PersistentList.EMPTY;
        try {
            return new LongRange(start, end, step, Math.toIntExact(rangeCount(start, end, step)));
        } catch(ArithmeticException e) {
            return Range.create(start, end, step);
        }
    } 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, count);
}

public Object first() {
    return start;
}

public ISeq next() {
    if(count > 1) {
        return new LongRange(start + step, end, step, count-1);
    } else {
        return null;
    }
}

private static final int CHUNK_SIZE = 32;

public IChunk chunkedFirst() {
    return new LongChunk(start, step, Math.min(count, CHUNK_SIZE));
}

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

public ISeq chunkedMore() {
    if(count <= CHUNK_SIZE) {
        return PersistentList.EMPTY;
    } else {
        return LongRange.create(start + (step * CHUNK_SIZE), end, step);
    }

}

public Sequential drop(int n) {
    if(n <= 0) {
        return this;
    } else if(n < count) {
        return new LongRange(start+(step*n), end, step, count - n);
    } else {
        return null;
    }
}

public int count() {
    return count;
}

public Object reduce(IFn f) {
    Object acc = start;
    long i = start + step;
    int n = count;
    while(n > 1) {
        acc = f.invoke(acc, i);
        if (acc instanceof Reduced) return ((Reduced)acc).deref();
        i += step;
        n--;
    }
    return acc;
}

public Object reduce(IFn f, Object val) {
    Object acc = val;
    int n = count;
    long i = start;
    do {
        acc = f.invoke(acc, i);
        if (RT.isReduced(acc)) return ((Reduced)acc).deref();
        i += step;
        n--;
    } while(n > 0);
    return acc;
}

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

class LongRangeIterator implements Iterator {
    private long next;
    private int remaining;

    public LongRangeIterator() {
        this.next = start;
        this.remaining = count;
    }

    public boolean hasNext() {
        return remaining > 0;
    }

    public Object next() {
        if (remaining > 0) {
            long ret = next;
            next = next + step;
            remaining = remaining - 1;
            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;
    }

}
}