import java.util.Iterator;
import java.util.NoSuchElementException;
public class PartitionRLIter2 implements Iterator<String> {
private static class IntStack {
private int[] data;
private int size;
private static final String DELIM = " ";
// sum, str, and strlen store redundant state for performance.
// Sum of all data
private int sum;
// Each element of data followed by DELIM
private StringBuilder str;
// For each i, the length of the relevant portion of str when size = i
private int[] strlen;
IntStack(int capacity) {
this.data = new int[capacity];
// Likely worst case is "1 1 ... 1 "
this.str = new StringBuilder(capacity * (1 + DELIM.length()));
this.strlen = new int[capacity];
}
public void fill(int datum) {
for (this.size = 0; this.size < this.data.length; this.size++) {
this.data[this.size] = datum;
this.strlen[this.size] = this.str.length();
this.str.append(String.valueOf(datum)).append(DELIM);
}
this.sum = datum * this.size;
}
public void push(int datum) {
this.strlen[this.size] = this.str.length();
this.data[this.size++] = datum;
this.sum += datum;
this.str.append(String.valueOf(datum)).append(DELIM);
}
public int pop() {
int datum = this.data[--this.size];
this.sum -= datum;
this.str.setLength(this.strlen[this.size]);
return datum;
}
/**
* Shortcut for push(i + pop()), peek()
*/
public int incr(int i) {
if (i != 0) {
int datum = this.data[this.size - 1] += i;
this.sum += i;
this.str.setLength(this.strlen[this.size - 1]);
this.str.append(String.valueOf(datum)).append(DELIM);
}
return this.data[this.size - 1];
}
public boolean isEmpty() {
return this.size == 0;
}
public int sum() {
return this.sum;
}
public String toString() {
return this.str.substring(0, this.str.length() - DELIM.length());
}
}
//////////////////////////////////////////////////////////////////////
private final IntStack stack;
private final int limit;
public PartitionRLIter2(int n) {
if (n <= 0) throw new IllegalArgumentException();
this.limit = n;
this.stack = new IntStack(limit);
this.stack.fill(1);
}
@Override
public boolean hasNext() {
return !this.stack.isEmpty();
}
@Override
public String next() {
if (this.stack.isEmpty()) {
throw new NoSuchElementException();
}
try {
return this.stack.toString();
} finally {
advance();
}
}
private final void advance() {
if (this.stack.pop() == this.limit) {
return;// All the numbers have been gathered into the original
// Allnumber. done That's all, folks!
return;
}
// Increment the previous level. We can never overflow because the
// previous pop decremented the sum by at least one.
int top = this.stack.incr(1);
// Duplicate the top of the stack as many times as possible.
while (this.stack.sum() + top <= this.limit) {
this.stack.push(top);
}
// Increment the top to the limit (if needed).
this.stack.incr(this.limit - this.stack.sum());
// Note stack invariant: values are always nondecreasing going from the
// base to the top.
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PartitionRLIter2 implements Iterator<String> {
private static class IntStack {
private int[] data;
private int size;
private static final String DELIM = " ";
// sum, str, and strlen store redundant state for performance.
// Sum of all data
private int sum;
// Each element of data followed by DELIM
private StringBuilder str;
// For each i, the length of the relevant portion of str when size = i
private int[] strlen;
IntStack(int capacity) {
this.data = new int[capacity];
// Likely worst case is "1 1 ... 1 "
this.str = new StringBuilder(capacity * (1 + DELIM.length()));
this.strlen = new int[capacity];
}
public void fill(int datum) {
for (this.size = 0; this.size < this.data.length; this.size++) {
this.data[this.size] = datum;
this.strlen[this.size] = this.str.length();
this.str.append(String.valueOf(datum)).append(DELIM);
}
this.sum = datum * this.size;
}
public void push(int datum) {
this.strlen[this.size] = this.str.length();
this.data[this.size++] = datum;
this.sum += datum;
this.str.append(String.valueOf(datum)).append(DELIM);
}
public int pop() {
int datum = this.data[--this.size];
this.sum -= datum;
this.str.setLength(this.strlen[this.size]);
return datum;
}
/**
* Shortcut for push(i + pop()), peek()
*/
public int incr(int i) {
if (i != 0) {
int datum = this.data[this.size - 1] += i;
this.sum += i;
this.str.setLength(this.strlen[this.size - 1]);
this.str.append(String.valueOf(datum)).append(DELIM);
}
return this.data[this.size - 1];
}
public boolean isEmpty() {
return this.size == 0;
}
public int sum() {
return this.sum;
}
public String toString() {
return this.str.substring(0, this.str.length() - DELIM.length());
}
}
//////////////////////////////////////////////////////////////////////
private final IntStack stack;
private final int limit;
public PartitionRLIter2(int n) {
if (n <= 0) throw new IllegalArgumentException();
this.limit = n;
this.stack = new IntStack(limit);
this.stack.fill(1);
}
@Override
public boolean hasNext() {
return !this.stack.isEmpty();
}
@Override
public String next() {
if (this.stack.isEmpty()) {
throw new NoSuchElementException();
}
try {
return this.stack.toString();
} finally {
advance();
}
}
private final void advance() {
if (this.stack.pop() == this.limit) {
return; // All done!
}
// Increment the previous level. We can never overflow because the
// previous pop decremented the sum by at least one.
int top = this.stack.incr(1);
// Duplicate the top of the stack as many times as possible.
while (this.stack.sum() + top <= this.limit) {
this.stack.push(top);
}
// Increment the top to the limit (if needed).
this.stack.incr(this.limit - this.stack.sum());
// Note stack invariant: values are always nondecreasing going from the
// base to the top.
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PartitionRLIter2 implements Iterator<String> {
private static class IntStack {
private int[] data;
private int size;
private static final String DELIM = " ";
// sum, str, and strlen store redundant state for performance.
// Sum of all data
private int sum;
// Each element of data followed by DELIM
private StringBuilder str;
// For each i, the length of the relevant portion of str when size = i
private int[] strlen;
IntStack(int capacity) {
this.data = new int[capacity];
// Likely worst case is "1 1 ... 1 "
this.str = new StringBuilder(capacity * (1 + DELIM.length()));
this.strlen = new int[capacity];
}
public void fill(int datum) {
for (this.size = 0; this.size < this.data.length; this.size++) {
this.data[this.size] = datum;
this.strlen[this.size] = this.str.length();
this.str.append(String.valueOf(datum)).append(DELIM);
}
this.sum = datum * this.size;
}
public void push(int datum) {
this.strlen[this.size] = this.str.length();
this.data[this.size++] = datum;
this.sum += datum;
this.str.append(String.valueOf(datum)).append(DELIM);
}
public int pop() {
int datum = this.data[--this.size];
this.sum -= datum;
this.str.setLength(this.strlen[this.size]);
return datum;
}
/**
* Shortcut for push(i + pop()), peek()
*/
public int incr(int i) {
if (i != 0) {
int datum = this.data[this.size - 1] += i;
this.sum += i;
this.str.setLength(this.strlen[this.size - 1]);
this.str.append(String.valueOf(datum)).append(DELIM);
}
return this.data[this.size - 1];
}
public boolean isEmpty() {
return this.size == 0;
}
public int sum() {
return this.sum;
}
public String toString() {
return this.str.substring(0, this.str.length() - DELIM.length());
}
}
//////////////////////////////////////////////////////////////////////
private final IntStack stack;
private final int limit;
public PartitionRLIter2(int n) {
if (n <= 0) throw new IllegalArgumentException();
this.limit = n;
this.stack = new IntStack(limit);
this.stack.fill(1);
}
@Override
public boolean hasNext() {
return !this.stack.isEmpty();
}
@Override
public String next() {
if (this.stack.isEmpty()) {
throw new NoSuchElementException();
}
try {
return this.stack.toString();
} finally {
advance();
}
}
private final void advance() {
if (this.stack.pop() == this.limit) {
// All the numbers have been gathered into the original
// number. That's all, folks!
return;
}
// Increment the previous level. We can never overflow because the
// previous pop decremented the sum by at least one.
int top = this.stack.incr(1);
// Duplicate the top of the stack as many times as possible.
while (this.stack.sum() + top <= this.limit) {
this.stack.push(top);
}
// Increment the top to the limit (if needed).
this.stack.incr(this.limit - this.stack.sum());
// Note stack invariant: values are always nondecreasing going from the
// base to the top.
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
Thanks to @rolfl for showing the way. Besides the performance gains, he also improved next() by throwing NoSuchElementException and by moving most of the code into advance().
I've concluded that his solution is faster due to three factors:
- Caching the
StringBuilder. - Enumerating the values in ascending rather than descending order. It turns out that putting the smaller numbers at the end results in greater churn of the stack. When the size of the stack keeps changing, the cached
StringBuilderis less effective. - Raw array access instead of using
IntStack.
Of those three factors, (3) has only a minor effect. However, if you delegate all the tedious bookkeeping to IntStack, the algorithm in advance() becomes quite understandable. Here is an implementation that reintroduces a smarter IntStack to PartitionRLIter.
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PartitionRLIter2 implements Iterator<String> {
private static class IntStack {
private int[] data;
private int size;
private static final String DELIM = " ";
// sum, str, and strlen store redundant state for performance.
// Sum of all data
private int sum;
// Each element of data followed by DELIM
private StringBuilder str;
// For each i, the length of the relevant portion of str when size = i
private int[] strlen;
IntStack(int capacity) {
this.data = new int[capacity];
// Likely worst case is "1 1 ... 1 "
this.str = new StringBuilder(capacity * (1 + DELIM.length()));
this.strlen = new int[capacity];
}
public void fill(int datum) {
for (this.size = 0; this.size < this.data.length; this.size++) {
this.data[this.size] = datum;
this.strlen[this.size] = this.str.length();
this.str.append(String.valueOf(datum)).append(DELIM);
}
this.sum = datum * this.size;
}
public void push(int datum) {
this.strlen[this.size] = this.str.length();
this.data[this.size++] = datum;
this.sum += datum;
this.str.append(String.valueOf(datum)).append(DELIM);
}
public int pop() {
int datum = this.data[--this.size];
this.sum -= datum;
this.str.setLength(this.strlen[this.size]);
return datum;
}
/**
* Shortcut for push(i + pop()), peek()
*/
public int incr(int i) {
if (i != 0) {
int datum = this.data[this.size - 1] += i;
this.sum += i;
this.str.setLength(this.strlen[this.size - 1]);
this.str.append(String.valueOf(datum)).append(DELIM);
}
return this.data[this.size - 1];
}
public boolean isEmpty() {
return this.size == 0;
}
public int sum() {
return this.sum;
}
public String toString() {
return this.str.substring(0, this.str.length() - DELIM.length());
}
}
//////////////////////////////////////////////////////////////////////
private final IntStack stack;
private final int limit;
public PartitionRLIter2(int n) {
if (n <= 0) throw new IllegalArgumentException();
this.limit = n;
this.stack = new IntStack(limit);
this.stack.fill(1);
}
@Override
public boolean hasNext() {
return !this.stack.isEmpty();
}
@Override
public String next() {
if (this.stack.isEmpty()) {
throw new NoSuchElementException();
}
try {
return this.stack.toString();
} finally {
advance();
}
}
private final void advance() {
if (this.stack.pop() == this.limit) {
return; // All done!
}
// Increment the previous level. We can never overflow because the
// previous pop decremented the sum by at least one.
int top = this.stack.incr(1);
// Duplicate the top of the stack as many times as possible.
while (this.stack.sum() + top <= this.limit) {
this.stack.push(top);
}
// Increment the top to the limit (if needed).
this.stack.incr(this.limit - this.stack.sum());
// Note stack invariant: values are always nondecreasing going from the
// base to the top.
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
lang-java