TinyBitSet.java revision 674060f01e9090cd21b3c5656cc3204912ad17a6
1ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.org/* 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org * Copyright 2003 The Apache Software Foundation 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org * 443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen * Licensed under the Apache License, Version 2.0 (the "License"); 543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen * you may not use this file except in compliance with the License. 643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen * You may obtain a copy of the License at 7196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org * 8196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org * http://www.apache.org/licenses/LICENSE-2.0 95de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org * 10196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org * Unless required by applicable law or agreed to in writing, software 11196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org * distributed under the License is distributed on an "AS IS" BASIS, 12196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org * See the License for the specific language governing permissions and 14196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org * limitations under the License. 15196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org */ 16196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.orgpackage org.mockito.cglib.core; 17196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org 18d0bddc653152f270a27fe32d5d7b0f5c0fa3b00cmachenbach@chromium.orgpublic class TinyBitSet { 19196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org private static int[] T = new int[256]; 20196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org private int value = 0; 21196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org 22196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org private static int gcount(int x) { 2343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen int c = 0; 2471affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org while (x != 0) { 2571affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org c++; 2643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen x &= (x - 1); 2710480471c0db59c51c15e57d2a3489551d61b273jkummerow@chromium.org } 28ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org return c; 29ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org } 30ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org 31ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org static { 32ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org for(int j = 0; j < 256; j++) { 33ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org T[j] = gcount(j); 34ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org } 35d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org } 36d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org 37d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org private static int topbit(int i) { 38d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org int j; 39d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org for (j = 0; i != 0; i ^= j) { 40c73d55b355913690124f3ee70c344035431cdd3ayangguo@chromium.org j = i & -i; 41c73d55b355913690124f3ee70c344035431cdd3ayangguo@chromium.org } 42c73d55b355913690124f3ee70c344035431cdd3ayangguo@chromium.org return j; 43c73d55b355913690124f3ee70c344035431cdd3ayangguo@chromium.org } 44c73d55b355913690124f3ee70c344035431cdd3ayangguo@chromium.org 45c73d55b355913690124f3ee70c344035431cdd3ayangguo@chromium.org private static int log2(int i) { 46c73d55b355913690124f3ee70c344035431cdd3ayangguo@chromium.org int j = 0; 47c73d55b355913690124f3ee70c344035431cdd3ayangguo@chromium.org for (j = 0; i != 0; i >>= 1) { 48ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org j++; 49ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org } 50ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org return j; 51ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org } 52ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org 53ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org public int length() { 54ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org return log2(topbit(value)); 55ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org } 56ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org 57ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org public int cardinality() { 58d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org int w = value; 59ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org int c = 0; 60d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org while (w != 0) { 617ca89addc38b7479d2d7526d2043283ab7480ffcdanno@chromium.org c += T[w & 255]; 62d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org w >>= 8; 63d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org } 64d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org return c; 65ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org } 66d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org 67d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org public boolean get(int index) { 68d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org return (value & (1 << index)) != 0; 69d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org } 70d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org 71d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org public void set(int index) { 72d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org value |= (1 << index); 73d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org } 74d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org 75d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org public void clear(int index) { 76d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org value &= ~(1 << index); 77d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org } 78d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org} 79d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org