set ~ a simple collectin of unique elements, associative keys
multiset ~ allows duplicate elements ( bag )
#include <set>
A ∪ B
A ∩ B
A - B
( A ∪ B ) - ( A ∩ B )
= ( A - B ) ∪ ( B - A )
A 
B
A = B iff A
A B
and B A
bit vector ( bitset ) is a collection of bits ~ 101011
similar to vector<bool> but differs in
template argument is an integer
#include <bitset>
#include <vector>
template <int N>
class bitSet {
protected:
vector<int> data;
int indexValue( int index ) //inline implementation
{
return index / 32;
}
int mask ( int index )
{
return 1 << ( index % 32 );
}
public:
//constructors
bitSet();
bitSet( bitSet<N> & b );
//bit level operators
void set();
void set( int index );
bool test( int index );
void reset ( int index );
//set operations
void operator |= ( bitSet<N> &rhs );
//....
};
|
|
|
template<int N>bitSet<N>::bitSet( bitSet<N> & b )
{
//duplicate the same vector
data = vector<int> ( b.data );
}
|
template<int N> void bitSet<N>::set()
//all bits set to 1
{
int n = data.size();
for ( int i = 0; i < n; i++ )
data[i] = ~0;
}
|
|
|
|
|
|
|
template<int N> void bitSet<N>:: operator |= ( bitSet<N> &rhs )
{
int n = data.size();
for ( int i = 0; i < n; i++ )
data[i] |= rhs.data[i];
}
|
//fbitios.h
#ifndef FBITIOS_H
#define FBITIOS_H
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <fstream>
#include <string.h>
#include <set>
#include <bitset>
typedef unsigned int ui;
typedef unsigned long ul;
typedef unsigned char uc;
class bitFileIO{
private:
bitset<32> ins;
bitset<32> outs;
fstream ifs, ofs;
int ins_pos;
int outs_pos;
int progress_indicator;
enum { max_bits = 32 };
public:
bitFileIO ( char *argv_in, char *argv_out ); //constructors
int inputBit(); //input one bit from file
void outputBit( int bit ); //output one bit to file
long inputBits( int n ); //input n bits from file
void outputBits ( ul data, int n ); //output n bits to file
void closeOutput(); //close_output
void closeInput(); //close input
};
#endif
|
//fbitios.cpp
//@Author T.L. Yu
#include "fbitios.h"
bitFileIO :: bitFileIO( char *argv_in, char *argv_out )
{
ifs.open( argv_in, ios::in );
if ( ifs.fail() ) {
cout << "error open file " << argv_in << endl;
exit( 1 );
}
ofs.open( argv_out, ios::out );
if ( ifs.fail() ) {
cout << "error open file " << argv_out << endl;
exit( 1 );
}
ins_pos = outs_pos = 0;
progress_indicator = 0;
}
//read one bit from file
int bitFileIO :: inputBit()
{
int value;
if ( ins_pos == 0 ) {
char c = ifs.get();
if ( ifs.eof() ) {
//cout << "Out of data" << endl;
return -1;
}
if ( !(progress_indicator++ & 0x0fff) ){
cout << "." << flush;
}
ins = ( ul ) c;
}
int i = ins_pos++;
if ( ins_pos > 7 )
ins_pos = 0;
return( ins[i] ? 1 : 0 );
}
//output one bit
void bitFileIO :: outputBit ( int bit )
{
if ( bit )
outs.set( outs_pos ); //set bit to 1
else
outs.reset( outs_pos ); //set bit to 0
if ( outs_pos == 7 ) {
char c = ( char ) outs.to_ulong();
ofs.put ( c );
if ( ofs.fail() ) {
cout << "\nfatal error in output bit " << endl;
}
outs_pos = 0; //reset output position
if ( !(progress_indicator++ & 0x0fff) ){
cout << "." << flush;
}
} else
++outs_pos;
} // OutputBit()
//read n bits from file
long bitFileIO :: inputBits( int n )
{
if ( n > max_bits - 1 ) {
cout << "Cannot handle " << n << " bits at one time";
return -2;
}
bitset<32> value;
int pos = 0;
while ( pos < n ) {
if ( ins_pos == 0 ) {
char c = ifs.get();
if ( ifs.eof() ) {
//cout << "Out of data" << endl;
return -1;
}
if ( !(progress_indicator++ & 0x0fff) ){
cout << "." << flush;
}
ins = ( ul ) c;
} //if ( read one char )
int i = ins_pos++;
if ( ins_pos > 7 )
ins_pos = 0;
if ( ins[i] )
value.set( pos ); //a 1
else
value.reset( pos ); // a 0
++pos; //points to next bit position
} //while
return ( (long) value.to_ulong() ); //return the n-bit value
} //inputBits()
//output n bits to file
void bitFileIO :: outputBits( ul data, int n )
{
bitset<32> value = data;
int pos = 0;
while ( pos < n ) {
if ( value[pos++] ) //test the bit of input value
outs.set( outs_pos ); //set bit to 1
else
outs.reset( outs_pos ); //set bit to 0
if ( outs_pos == 7 ) {
char c = ( char ) outs.to_ulong();
ofs.put ( c );
if ( ofs.fail() ) {
cout << "\nfatal error in output bit " << endl;
}
outs_pos = 0; //reset output position
if ( !(progress_indicator++ & 0x0fff) ){
cout << "." << flush;
}
} else
++outs_pos;
}
} /* outputBits() */
//push out remaining bits to file
void bitFileIO :: closeOutput ()
{
if ( outs_pos != 0 ){
for ( int i = outs_pos; i < 7; ++i )
outs[i] = 0;
ofs.put( ( char ) outs.to_ulong() );
}
ofs.close();
}
void bitFileIO :: closeInput()
{
ifs.close();
}
|
//f_test.cpp
#include "fbitios.h"
void main( int argc, char *argv[] )
{
if ( argc < 3 ) {
cout << "Usage: " << *argv << " infile outfile " << endl;
exit ( 1 );
}
argv++;
char *in = *argv++;
char *out = *argv;
bitFileIO bf( in, out );
/*
//uncomment these few lines if you want to to test inputBit(), outputBit()
int c;
while ( ( c = bf.inputBit() ) >= 0 )
bf.outputBit( c ) ;
*/
long x;
while ( ( x = bf.inputBits( 9 ) ) >= 0 )
bf.outputBits( x, 9 );
bf.closeInput();
bf.closeOutput();
}
|