00001 typedef unsigned long dword;
00002 #define BIT_BANK_SIZE 63
00003
00005 class BitStack{
00006 struct bank_st{
00007 dword map[BIT_BANK_SIZE];
00008 bank_st *prev;
00009 }*list;
00010 int index;
00011 void NewBank();
00012 public:
00013 BitStack();
00014 ~BitStack();
00015 void Clear();
00016 void Push(bool);
00017 bool Pop();
00018 };
00019
00020 BitStack::BitStack()
00021 {
00022 list=0;
00023 index=BIT_BANK_SIZE*32;
00024 }
00025
00026
00027 BitStack::~BitStack()
00028 {
00029 Clear();
00030 }
00031
00032
00033 void BitStack::Clear()
00034 {
00035 while(list) {
00036 bank_st *prev=list->prev;
00037 delete list;
00038 list=prev;
00039 }
00040 }
00041
00042 void BitStack::Push(bool bit)
00043 {
00044 if(index>=BIT_BANK_SIZE*32) NewBank();
00045 if(bit) list->map[index/32]|=1<<(index&31);
00046 else list->map[index/32]&=~(1<<(index&31));
00047 index++;
00048 }
00049
00051 bool BitStack::Pop()
00052 {
00053 bool res;
00054 if(!list) return true;
00055 index--;
00056 res=!!(list->map[index/32]&(1<<(index&31)));
00057 if(!index) {
00058 bank_st *prev=list->prev;
00059 delete list;
00060 list=prev;
00061 index=BIT_BANK_SIZE*32;
00062 }
00063 return res;
00064 }
00065
00066 void BitStack::NewBank()
00067 {
00068 bank_st *temp=new bank_st;
00069
00070 temp->prev=list;
00071 list=temp;
00072 index=0;
00073 }
00074
00075
00076