}

// splitKeys divides the array of keys into 2 so they can update left and right branches in parallel
func (s *smt) splitKeys(keys [][]byte, height int) ([][]byte, [][]byte) {
	for i, key := range keys {
		if bitIsSet(key, height) {
			return keys[:i], keys[i:]
		}
	}
	return keys, nil
}

// maybeAddShortcutToKV adds a shortcut key to the keys array to be updated.

 * to keep track of which items are filtered out of the source list.
 */
public class ImmutableFilteredList<T> extends AbstractList<T> {

    private final List<T> source;
    private final BitSet filter;

    private ImmutableFilteredList(List<T> source, BitSet filter) {
        this.source = source;
        this.filter = filter;
    }

    /**
     * Creates an {@code ImmutableFilteredList} which contains all the elements of {@code source}.

            // Because they are EXTRA attributes, we consider that a
            // candidate which does NOT provide this value is a better match
            int candidateCount = candidateAttributeSets.length;
            BitSet any = new BitSet(candidateCount);
            for (int c = 0; c < candidateCount; c++) {
                ImmutableAttributes candidateAttributeSet = candidateAttributeSets[c];

        table = (BitSet) table.clone();
        // If only we could actually call BitSet.trimToSize() ourselves...
      }
      this.table = table;
    }

    @Override
    public boolean matches(char c) {
      return table.get(c);
    }

    @Override
    void setBits(BitSet bitSet) {
      bitSet.or(table);
    }
  }

  // Static constant implementation classes

package com.google.common.base;

import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.CharMatcher.NamedFastMatcher;
import java.util.BitSet;

/**
 * An immutable version of CharMatcher for smallish sets of characters that uses a hash table with
 * linear probing to check for matches.
 *
 * @author Christopher Swenson
 */

        table = (BitSet) table.clone();
        // If only we could actually call BitSet.trimToSize() ourselves...
      }
      this.table = table;
    }

    @Override
    public boolean matches(char c) {
      return table.get(c);
    }

    @Override
    void setBits(BitSet bitSet) {
      bitSet.or(table);
    }
  }

  // Static constant implementation classes

package com.google.common.base;

import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.CharMatcher.NamedFastMatcher;
import java.util.BitSet;

/**
 * An immutable version of CharMatcher for smallish sets of characters that uses a hash table with
 * linear probing to check for matches.
 *
 * @author Christopher Swenson
 */

   *
   * <p><b>Note:</b> consider representing the array as a {@link java.util.BitSet} instead,
   * replacing {@code Booleans.contains(array, true)} with {@code !bitSet.isEmpty()} and {@code
   * Booleans.contains(array, false)} with {@code bitSet.nextClearBit(0) == sizeOfBitSet}.
   *
   * @param array an array of {@code boolean} values, possibly empty

   *
   * <p><b>Note:</b> consider representing the array as a {@link java.util.BitSet} instead,
   * replacing {@code Booleans.contains(array, true)} with {@code !bitSet.isEmpty()} and {@code
   * Booleans.contains(array, false)} with {@code bitSet.nextClearBit(0) == sizeOfBitSet}.
   *
   * @param array an array of {@code boolean} values, possibly empty

const uintSize = 32 << (^uint(0) >> 63) // 32 or 64

// bitset is a bit array for dense indexes.
type bitset []uint

func newBitset(n int) bitset {
	return make(bitset, (n+uintSize-1)/uintSize)
}

func (bs bitset) Reset() {
	for i := range bs {
		bs[i] = 0
	}
}

func (bs bitset) Set(idx uint32) {
	bs[idx/uintSize] |= 1 << (idx % uintSize)
}

func (bs bitset) Clear(idx uint32) {