You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@groovy.apache.org by pa...@apache.org on 2016/06/28 09:17:57 UTC
groovy git commit: GROOVY-7629 and GROOVY-5426: Use StepIterator for
all stepping, avoid calls to size()
Repository: groovy
Updated Branches:
refs/heads/master 19a9bf5d0 -> 37f147dd8
GROOVY-7629 and GROOVY-5426: Use StepIterator for all stepping, avoid calls to size()
Project: http://git-wip-us.apache.org/repos/asf/groovy/repo
Commit: http://git-wip-us.apache.org/repos/asf/groovy/commit/37f147dd
Tree: http://git-wip-us.apache.org/repos/asf/groovy/tree/37f147dd
Diff: http://git-wip-us.apache.org/repos/asf/groovy/diff/37f147dd
Branch: refs/heads/master
Commit: 37f147dd803ef17d41c6b58b18c59d95e7fc2157
Parents: 19a9bf5
Author: Thibault Kruse <th...@gmx.de>
Authored: Wed Oct 14 15:45:11 2015 +0200
Committer: paulk <pa...@asert.com.au>
Committed: Tue Jun 28 18:28:46 2016 +1000
----------------------------------------------------------------------
src/main/groovy/lang/ObjectRange.java | 211 ++++++++++++++++++-----------
1 file changed, 130 insertions(+), 81 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/groovy/blob/37f147dd/src/main/groovy/lang/ObjectRange.java
----------------------------------------------------------------------
diff --git a/src/main/groovy/lang/ObjectRange.java b/src/main/groovy/lang/ObjectRange.java
index f108433..529b070 100644
--- a/src/main/groovy/lang/ObjectRange.java
+++ b/src/main/groovy/lang/ObjectRange.java
@@ -232,55 +232,18 @@ public class ObjectRange extends AbstractList implements Range {
if (index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + " should not be negative");
}
- if (index >= size()) {
- throw new IndexOutOfBoundsException("Index: " + index + " is too big for range: " + this);
- }
- Object value;
- if (reverse) {
- value = to;
+ StepIterator iter = new StepIterator(this, 1);
- for (int i = 0; i < index; i++) {
- value = decrement(value);
- }
- } else {
- value = from;
- for (int i = 0; i < index; i++) {
- value = increment(value);
+ Object value = iter.next();
+ for (int i = 0; i < index; i++) {
+ if (!iter.hasNext()) {
+ throw new IndexOutOfBoundsException("Index: " + index + " is too big for range: " + this);
}
+ value = iter.next();
}
return value;
}
- public Iterator iterator() {
- return new Iterator() {
- private int index;
- private Object value = reverse ? to : from;
-
- public boolean hasNext() {
- return index < size();
- }
-
- public Object next() {
- if (index++ > 0) {
- if (index > size()) {
- value = null;
- } else {
- if (reverse) {
- value = decrement(value);
- } else {
- value = increment(value);
- }
- }
- }
- return value;
- }
-
- public void remove() {
- ObjectRange.this.remove(index);
- }
- };
- }
-
/**
* Checks whether a value is between the from and to values of a Range
*
@@ -327,17 +290,14 @@ public class ObjectRange extends AbstractList implements Range {
BigInteger sizeNum = toNum.subtract(fromNum).add(new BigDecimal(1.0)).toBigInteger();
size = sizeNum.intValue();
} else {
- // let's brute-force calculate the size
- size = 0;
- Comparable first = from;
- Comparable value = from;
- while (compareTo(to, value) >= 0) {
- value = (Comparable) increment(value);
- size++;
- // handle back to beginning due to modulo incrementing
- if (compareTo(first, value) >= 0) break;
+ // let's brute-force calculate the size by iterating start to end
+ Iterator iter = new StepIterator(this, 1);
+ int tempsize = 0;
+ while (iter.hasNext()) {
+ tempsize++;
+ iter.next();
}
- }
+ size = tempsize; }
}
return size;
}
@@ -346,9 +306,6 @@ public class ObjectRange extends AbstractList implements Range {
if (fromIndex < 0) {
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
}
- if (toIndex > size()) {
- throw new IndexOutOfBoundsException("toIndex = " + toIndex);
- }
if (fromIndex > toIndex) {
throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
@@ -356,7 +313,28 @@ public class ObjectRange extends AbstractList implements Range {
return new EmptyRange(from);
}
- return new ObjectRange((Comparable) get(fromIndex), (Comparable) get(--toIndex), reverse);
+ // Performance detail:
+ // not using get(fromIndex), get(toIndex) in the following to avoid stepping over elements twice
+ StepIterator iter = new StepIterator(this, 1);
+
+ Object value = iter.next();
+ int i = 0;
+ for (; i < fromIndex; i++) {
+ if (!iter.hasNext()) {
+ throw new IndexOutOfBoundsException("Index: " + i + " is too big for range: " + this);
+ }
+ value = iter.next();
+ }
+ Object fromValue = value;
+ for (;i < toIndex - 1; i++) {
+ if (!iter.hasNext()) {
+ throw new IndexOutOfBoundsException("Index: " + i + " is too big for range: " + this);
+ }
+ value = iter.next();
+ }
+ Object toValue = value;
+
+ return new ObjectRange((Comparable) fromValue, (Comparable) toValue, reverse);
}
public String toString() {
@@ -374,7 +352,7 @@ public class ObjectRange extends AbstractList implements Range {
* Also see containsWithinBounds.
*/
public boolean contains(Object value) {
- Iterator it = iterator();
+ Iterator it = new StepIterator(this, 1);
if (value == null) return false;
while (it.hasNext()) {
try {
@@ -387,38 +365,109 @@ public class ObjectRange extends AbstractList implements Range {
}
public void step(int step, Closure closure) {
- if (step == 0) {
- if (compareTo(from, to) != 0) {
+ if (step == 0 && compareTo(from, to) == 0) {
+ return; // from == to and step == 0, nothing to do, so return
+ }
+ StepIterator iter = new StepIterator(this, step);
+ while (iter.hasNext()) {
+ closure.call(iter.next());
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Iterator iterator() {
+ // non thread-safe iterator
+ final Iterator innerIterator = new StepIterator(this, 1);
+ Iterator safeIterator = new Iterator() {
+ @Override
+ public synchronized boolean hasNext() {
+ return innerIterator.hasNext();
+ }
+ @Override
+ public synchronized Object next() {
+ return innerIterator.next();
+ }
+ @Override
+ public void remove() {
+ innerIterator.remove();
+ }
+ };
+ return safeIterator;
+ }
+ /**
+ * convenience class to serve in other methods.
+ * It's not thread-safe, and lazily produces the next element only on calls of hasNext() or next()
+ */
+ private static class StepIterator implements Iterator {
+ // actual step, can be +1 when desired step is -1 and direction is from high to low
+ private final int step;
+ private final ObjectRange range;
+ private int index = -1;
+ private Comparable value;
+ private boolean nextFetched = true;
+ private StepIterator(ObjectRange range, final int desiredStep) {
+ if (desiredStep == 0 && range.compareTo(range.getFrom(), range.getTo()) != 0) {
throw new GroovyRuntimeException("Infinite loop detected due to step size of 0");
+ }
+ this.range = range;
+ if (range.isReverse()) {
+ this.step = -desiredStep;
} else {
- return; // from == to and step == 0, nothing to do, so return
+ this.step = desiredStep;
+ }
+ if (this.step > 0) {
+ value = range.getFrom();
+ } else {
+ value = range.getTo();
}
}
-
- if (reverse) {
- step = -step;
+ public void remove() {
+ this.range.remove(index);
}
- if (step > 0) {
- Comparable first = from;
- Comparable value = from;
- while (compareTo(value, to) <= 0) {
- closure.call(value);
- for (int i = 0; i < step; i++) {
- value = (Comparable) increment(value);
- if (compareTo(value, first) <= 0) return;
- }
+ public Object next() {
+ // not thread safe
+ if (!nextFetched) {
+ value = peek();
+ nextFetched = true;
}
- } else {
- step = -step;
- Comparable first = to;
- Comparable value = to;
- while (compareTo(value, from) >= 0) {
- closure.call(value);
+ nextFetched = false;
+ index++;
+ return value;
+ }
+ public boolean hasNext() {
+ // not thread safe
+ if (!nextFetched) {
+ value = peek();
+ nextFetched = true;
+ }
+ return value != null;
+ }
+ private Comparable peek() {
+ if (step > 0) {
+ Comparable peekValue = value;
for (int i = 0; i < step; i++) {
- value = (Comparable) decrement(value);
- if (compareTo(value, first) >= 0) return;
+ peekValue = (Comparable) range.increment(peekValue);
+ // handle back to beginning due to modulo incrementing
+ if (range.compareTo(peekValue, range.from) <= 0) return null;
+ }
+ if (range.compareTo(peekValue, range.to) <= 0) {
+ return peekValue;
+ }
+ } else {
+ int positiveStep = -step;
+ Comparable peekValue = value;
+ for (int i = 0; i < positiveStep; i++) {
+ peekValue = (Comparable) range.decrement(peekValue);
+ // handle back to beginning due to modulo decrementing
+ if (range.compareTo(peekValue, range.to) >= 0) return null;
+ }
+ if (range.compareTo(peekValue, range.from) >= 0) {
+ return peekValue;
}
}
+ return null;
}
}