views:

25

answers:

0

Following up my previous bit-twiddling question, now I'm looking to trim down the method that uses that one (though, an unbuffered version, since the life of the array is only this object). This is the iterator method for a power set of some long base; the actual contents of the set isn't stored - it would be a memory hog and individual members are only interesting when one wants to iterate over the set - so the members are generated by the iterator.

However, those members need to be returned in order by size first (instead of lexicographical order) - i.e., "sorted" by bit count.

Below is my (working) first cut; any suggestions from optimization addicts? This one I'm pretty sure has more obvious cuts.

public Iterator<Long> iterator() { return new Iterator<Long>(){

private boolean hasNext = true;
@Override public boolean hasNext() { return hasNext; }

private final long[] split = BitTwiddling.decompose(base);
int size = 0;
private long next = 0;
private long lastOfSize = 0;
private long firstOfSize = 0;

int[] positions = new int[split.length];

@Override
public Long next() {
  long result = next;
  if (next == lastOfSize) {
    if (size == split.length) {
      hasNext = false;
      return result;
    }

    next = (firstOfSize |= split[size]);
    lastOfSize |= split[split.length - ++size]; 

    for(int i=0; i<size; i++) positions[i] = i;

  } else {
    if (positions[size-1] == split.length-1) {
      int index = size-1;
      int ref = split.length - 1;
      while (positions[index] == ref) { index--; next ^= split[ref--]; }
      next ^= split[positions[index]++];
      next |= split[positions[index++]];
      do {
        next |= split[positions[index] = positions[index-1]+1];
      } while (++index < size);
    } else {
      next ^= split[positions[size-1]++];
      next |= split[positions[size-1]];
    }
  }
return result;
}