001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.util;
007:
008: /**
009: * A list of bits.
010: */
011: public class BitField {
012:
013: private long[] data = new long[10];
014: private static final int ADDRESS_BITS = 6;
015: private static final int BITS = 64;
016: private static final int ADDRESS_MASK = BITS - 1;
017:
018: public int getLastSetBit() {
019: int i = (data.length << ADDRESS_BITS) - 1;
020: while (i >= 0) {
021: if (get(i)) {
022: return i;
023: }
024: i--;
025: }
026: return -1;
027: }
028:
029: public int nextSetBit(int fromIndex) {
030: int i = fromIndex >> ADDRESS_BITS;
031: int max = data.length;
032: int maxAddress = data.length << ADDRESS_BITS;
033: for (; i < max; i++) {
034: if (data[i] == 0) {
035: continue;
036: }
037: for (int j = Math.max(fromIndex, i << ADDRESS_BITS); j < maxAddress; j++) {
038: if (get(j)) {
039: return j;
040: }
041: }
042: }
043: return -1;
044: }
045:
046: public int nextClearBit(int fromIndex) {
047: int i = fromIndex >> ADDRESS_BITS;
048: int max = data.length;
049: for (; i < max; i++) {
050: if (data[i] == -1) {
051: continue;
052: }
053: for (int j = Math.max(fromIndex, i << ADDRESS_BITS);; j++) {
054: if (!get(j)) {
055: return j;
056: }
057: }
058: }
059: return fromIndex;
060: }
061:
062: public long getLong(int i) {
063: int addr = getAddress(i);
064: if (addr >= data.length) {
065: return 0;
066: }
067: return data[addr];
068: }
069:
070: public boolean get(int i) {
071: int addr = getAddress(i);
072: if (addr >= data.length) {
073: return false;
074: }
075: return (data[addr] & getBitMask(i)) != 0;
076: }
077:
078: public void set(int i) {
079: int addr = getAddress(i);
080: checkCapacity(addr);
081: data[addr] |= getBitMask(i);
082: }
083:
084: public void clear(int i) {
085: int addr = getAddress(i);
086: if (addr >= data.length) {
087: return;
088: }
089: data[addr] &= ~getBitMask(i);
090: }
091:
092: private int getAddress(int i) {
093: return i >> ADDRESS_BITS;
094: }
095:
096: private long getBitMask(int i) {
097: return 1L << (i & ADDRESS_MASK);
098: }
099:
100: private void checkCapacity(int size) {
101: while (size >= data.length) {
102: int newSize = data.length == 0 ? 1 : data.length * 2;
103: long[] d = new long[newSize];
104: System.arraycopy(data, 0, d, 0, data.length);
105: data = d;
106: }
107: }
108:
109: public void setRange(int start, int len, boolean value) {
110: for (int end = start + len; start < end; start++) {
111: set(start, value);
112: }
113: }
114:
115: private void set(int i, boolean value) {
116: if (value) {
117: set(i);
118: } else {
119: clear(i);
120: }
121: }
122:
123: }
|