Main Page | Modules | Namespace List | Data Structures | File List | Data Fields | Globals

Bitmap Processing


Data Structures

class  Bitmap16
 A vertical representation of the data. More...

class  Bitmap32
 A vertical representation of the data. More...

class  Bitmap4
 A vertical representation of the data. More...

class  Bitmap64
 A vertical representation of the data. More...

class  Bitmap8
 A vertical representation of the data. More...

class  SeqBitmap
 A representation of a sequence (or an item). More...


Defines

#define DEBUG_SEQBITMAPCOUNT

Functions

void SeqBitmap::Init ()
 Initialize the lookup tables to be used by this SeqBitmap.

void SeqBitmap::MemAlloc (int size4, int size8, int size16, int size32, int size64)
 Initialize all SeqBitmap memory for duration of program.

void SeqBitmap::MemDealloc ()
 Delete all of SeqBitmap's memory.

void SeqBitmap::Destroy ()
void SeqBitmap::Or (const SeqBitmap &b1, const SeqBitmap &b2)
 Bitwise OR 2 SeqBitmaps and store the result.

void SeqBitmap::And (const SeqBitmap &b1, const SeqBitmap &b2)
 Bitwise AND 2 SeqBitmaps and store the result.

int SeqBitmap::Count ()
 find the support of this bitmap

void SeqBitmap::CreateSBitmap (const SeqBitmap &iBitmap)
 create a s-bitmap from an i-bitmap

void SeqBitmap::CreateCBitmap (const SeqBitmap &iBitmap)
 create a cbitmap from an i-bitmap

void SeqBitmap::PrintBitmap (ofstream &testFile)
 Print bitmap to an output stream.

void SeqBitmap::CountSmaller (int &size4, int &size8, int &size16, int &size32, int &size64, ostream &out)
 Returns the sizes to allocate for the new compressed f1 bitmap.

void SeqBitmap::Compress4 (SeqBitmap *refBitmap, SeqBitmap *compBitmap, int &pos4)
 Compress the Bitmap4 component of a SeqBitmap to a compressed SeqBitmap.

void SeqBitmap::Compress8 (SeqBitmap *refBitmap, SeqBitmap *compBitmap, int &pos4, int &pos8)
 Compress the Bitmap8 component of a SeqBitmap to a compressed SeqBitmap.

void SeqBitmap::Compress16 (SeqBitmap *refBitmap, SeqBitmap *compBitmap, int &pos4, int &pos8, int &pos16)
 Compress the Bitmap16 component of a SeqBitmap to a compressed SeqBitmap.

void SeqBitmap::Compress32 (SeqBitmap *refBitmap, SeqBitmap *compBitmap, int &pos4, int &pos8, int &pos16, int &pos32)
 Compress the Bitmap32 component of a SeqBitmap to a compressed SeqBitmap.

void SeqBitmap::Compress64 (SeqBitmap *refBitmap, SeqBitmap *compBitmap, int &pos4, int &pos8, int &pos16, int &pos32, int &pos64)
 Compress the Bitmap64 component of a SeqBitmap to a compressed SeqBitmap.

void SeqBitmap::printSizes (ostream &out)

Variables

const int NUM_BITMAP = 5
 number of different bitmaps in SeqBitmap

const int BITMAP_LENGTH [5]
 the size of each customer data in each bitmap

const int SIZE_BYTE = 8
const int SIZE_INT = sizeof(int)
const int SIZE_UINT = sizeof(unsigned int)
const int SIZE_USHORT = sizeof(unsigned short)
const int SHORT_PER_INT = SIZE_UINT / SIZE_USHORT
const int BITS_PER_INT = SIZE_UINT * SIZE_BYTE
const int BITS_PER_SHORT = SIZE_USHORT * SIZE_BYTE
const unsigned int Bit32Table [32]
 Bit32Table[i] contains a 1 at only position i.

const int Bit16Table [16]
 Bit16Table[i] contains a 1 at only position i.

const char CountTable [256]
 CountTable[i] contains the number of 1's in the byte value of i.

int const  SeqBitmap::_lookupTableSize = 0x100
int * SeqBitmap::_numOnesLookupTable = 0
int * SeqBitmap::_compress4LookupTable = 0
unsigned char ** SeqBitmap::_compress8Table = 0
int SeqBitmap::_countOr = 0
int SeqBitmap::_countAnd = 0
int SeqBitmap::_countCount = 0
int SeqBitmap::_countCountZeros = 0
int SeqBitmap::_countCountSmaller = 0
int SeqBitmap::_countCreateSBitmap = 0
int SeqBitmap::_countCreateCBitmap = 0
unsigned int * SeqBitmap::_memory4 = 0
unsigned int * SeqBitmap::_memory8 = 0
unsigned short * SeqBitmap::_memory16 = 0
unsigned int * SeqBitmap::_memory32 = 0
unsigned int * SeqBitmap::_memory64 = 0
int SeqBitmap::_size4 = 0
int SeqBitmap::_size8 = 0
int SeqBitmap::_size16 = 0
int SeqBitmap::_size32 = 0
int SeqBitmap::_size64 = 0

Define Documentation

#define DEBUG_SEQBITMAPCOUNT
 

Definition at line 86 of file SeqBitmap.cpp.

Function Documentation

void SeqBitmap::And (  const SeqBitmap &  b1,
const SeqBitmap &  b2
)  [inherited]
 

Bitwise AND 2 SeqBitmaps and store the result.

Parameters:
b1 the first SeqBitmap
b2 the second SeqBitmap

Definition at line 280 of file SeqBitmap.cpp.

Referenced by FindSequentialPatterns().

void SeqBitmap::Compress16 (  SeqBitmap *  refBitmap,
SeqBitmap *  compBitmap,
int &  pos4,
int &  pos8,
int &  pos16
)  [inherited]
 

Compress the Bitmap16 component of a SeqBitmap to a compressed SeqBitmap.

Parameters:
refBitmap The bitmap specifying which bits can be compressed
compBitmap The bitmap to compress
pos4 The end position of the Bitmap4 in the compressed SeqBitmap
pos8 The end position of the Bitmap8 in the compressed SeqBitmap
pos16 The end position of the Bitmap16 in the compressed SeqBitmap

Definition at line 823 of file SeqBitmap.cpp.

Referenced by Compress().

void SeqBitmap::Compress32 (  SeqBitmap *  refBitmap,
SeqBitmap *  compBitmap,
int &  pos4,
int &  pos8,
int &  pos16,
int &  pos32
)  [inherited]
 

Compress the Bitmap32 component of a SeqBitmap to a compressed SeqBitmap.

Parameters:
refBitmap The bitmap specifying which bits can be compressed
compBitmap The bitmap to compress
pos4 The end position of the Bitmap4 in the compressed SeqBitmap
pos8 The end position of the Bitmap8 in the compressed SeqBitmap
pos16 The end position of the Bitmap16 in the compressed SeqBitmap
pos32 The end position of the Bitmap32 in the compressed SeqBitmap

Definition at line 948 of file SeqBitmap.cpp.

Referenced by Compress().

void SeqBitmap::Compress4 (  SeqBitmap *  refBitmap,
SeqBitmap *  compBitmap,
int &  pos4
)  [inherited]
 

Compress the Bitmap4 component of a SeqBitmap to a compressed SeqBitmap.

Parameters:
refBitmap The bitmap specifying which bits can be compressed
compBitmap The bitmap to compress
pos4 The end position of the Bitmap4 in the compressed SeqBitmap

Definition at line 638 of file SeqBitmap.cpp.

Referenced by Compress().

void SeqBitmap::Compress64 (  SeqBitmap *  refBitmap,
SeqBitmap *  compBitmap,
int &  pos4,
int &  pos8,
int &  pos16,
int &  pos32,
int &  pos64
)  [inherited]
 

Compress the Bitmap64 component of a SeqBitmap to a compressed SeqBitmap.

Parameters:
refBitmap The bitmap specifying which bits can be compressed
compBitmap The bitmap to compress
pos4 The end position of the Bitmap4 in the compressed SeqBitmap
pos8 The end position of the Bitmap8 in the compressed SeqBitmap
pos16 The end position of the Bitmap16 in the compressed SeqBitmap
pos32 The end position of the Bitmap32 in the compressed SeqBitmap
pos64 The end position of the Bitmap64 in the compressed SeqBitmap

Definition at line 1119 of file SeqBitmap.cpp.

Referenced by Compress().

void SeqBitmap::Compress8 (  SeqBitmap *  refBitmap,
SeqBitmap *  compBitmap,
int &  pos4,
int &  pos8
)  [inherited]
 

Compress the Bitmap8 component of a SeqBitmap to a compressed SeqBitmap.

Parameters:
refBitmap The bitmap specifying which bits can be compressed
compBitmap The bitmap to compress
pos4 The end position of the Bitmap4 in the compressed SeqBitmap
pos8 The end position of the Bitmap8 in the compressed SeqBitmap

Definition at line 728 of file SeqBitmap.cpp.

Referenced by Compress().

int SeqBitmap::Count (   )  [inherited]
 

find the support of this bitmap

Definition at line 307 of file SeqBitmap.cpp.

Referenced by FindSequentialPatterns(), and StartMining().

void SeqBitmap::CountSmaller (  int &  size4,
int &  size8,
int &  size16,
int &  size32,
int &  size64,
ostream &  debugFile
)  [inherited]
 

Returns the sizes to allocate for the new compressed f1 bitmap.

This will only be called by an OR bitmap during compression

Definition at line 474 of file SeqBitmap.cpp.

Referenced by Compress().

void SeqBitmap::CreateCBitmap (  const SeqBitmap &  iBitmap  )  [inherited]
 

create a cbitmap from an i-bitmap

Parameters:
iBitmap the bitmap from which we create s-bitmap

Definition at line 368 of file SeqBitmap.cpp.

Referenced by FindSequentialPatterns().

void SeqBitmap::CreateSBitmap (  const SeqBitmap &  iBitmap  )  [inherited]
 

create a s-bitmap from an i-bitmap

Parameters:
iBitmap the i-bitmap to copy

Definition at line 340 of file SeqBitmap.cpp.

Referenced by FindSequentialPatterns().

void SeqBitmap::Destroy (   )  [static, inherited]
 

Definition at line 220 of file SeqBitmap.cpp.

Referenced by main().

void SeqBitmap::Init (   )  [static, inherited]
 

Initialize the lookup tables to be used by this SeqBitmap.

Definition at line 91 of file SeqBitmap.cpp.

Referenced by main().

void SeqBitmap::MemAlloc (  int  size4,
int  size8,
int  size16,
int  size32,
int  size64
)  [static, inherited]
 

Initialize all SeqBitmap memory for duration of program.

Parameters:
size4 total space required for all bitmap_4's
size8 total space required for all bitmap_8's
size16 total space required for all bitmap_16's
size32 total space required for all bitmap_32's
size64 total space required for all bitmap_64's

Definition at line 185 of file SeqBitmap.cpp.

void SeqBitmap::MemDealloc (   )  [static, inherited]
 

Delete all of SeqBitmap's memory.

Definition at line 209 of file SeqBitmap.cpp.

Referenced by main().

void SeqBitmap::Or (  const SeqBitmap &  b1,
const SeqBitmap &  b2
)  [inherited]
 

Bitwise OR 2 SeqBitmaps and store the result.

Parameters:
b1 the first SeqBitmap
b2 the second SeqBitmap

Definition at line 249 of file SeqBitmap.cpp.

Referenced by CreateOrBitmap().

void SeqBitmap::PrintBitmap (  ofstream &  testFile  )  [inherited]
 

Print bitmap to an output stream.

Parameters:
testFile output file stream

Definition at line 397 of file SeqBitmap.cpp.

void SeqBitmap::printSizes (  ostream &  out  )  [inherited]
 

Definition at line 1372 of file SeqBitmap.cpp.

Variable Documentation

int * SeqBitmap::_compress4LookupTable = 0 [static, inherited]
 

Definition at line 61 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Compress4(), SeqBitmap::Destroy(), and SeqBitmap::Init().

unsigned char ** SeqBitmap::_compress8Table = 0 [static, inherited]
 

Definition at line 62 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Compress16(), SeqBitmap::Compress32(), SeqBitmap::Compress64(), SeqBitmap::Compress8(), SeqBitmap::Destroy(), and SeqBitmap::Init().

int SeqBitmap::_countAnd = 0 [static, inherited]
 

Definition at line 66 of file SeqBitmap.cpp.

Referenced by SeqBitmap::And(), and main().

int SeqBitmap::_countCount = 0 [static, inherited]
 

Definition at line 67 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Count(), and main().

int SeqBitmap::_countCountSmaller = 0 [static, inherited]
 

Definition at line 69 of file SeqBitmap.cpp.

Referenced by SeqBitmap::CountSmaller(), and main().

int SeqBitmap::_countCountZeros = 0 [static, inherited]
 

Definition at line 68 of file SeqBitmap.cpp.

Referenced by main().

int SeqBitmap::_countCreateCBitmap = 0 [static, inherited]
 

Definition at line 71 of file SeqBitmap.cpp.

Referenced by SeqBitmap::CreateCBitmap(), and main().

int SeqBitmap::_countCreateSBitmap = 0 [static, inherited]
 

Definition at line 70 of file SeqBitmap.cpp.

Referenced by SeqBitmap::CreateSBitmap(), and main().

int SeqBitmap::_countOr = 0 [static, inherited]
 

Definition at line 65 of file SeqBitmap.cpp.

Referenced by main(), and SeqBitmap::Or().

int const SeqBitmap::_lookupTableSize = 0x100 [static, inherited]
 

Definition at line 59 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Destroy(), and SeqBitmap::Init().

unsigned short * SeqBitmap::_memory16 = 0 [static, inherited]
 

Definition at line 75 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Deallocate(), SeqBitmap::MemAlloc(), SeqBitmap::MemDealloc(), and SeqBitmap::SeqBitmap().

unsigned int * SeqBitmap::_memory32 = 0 [static, inherited]
 

Definition at line 76 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Deallocate(), SeqBitmap::MemAlloc(), SeqBitmap::MemDealloc(), and SeqBitmap::SeqBitmap().

unsigned int * SeqBitmap::_memory4 = 0 [static, inherited]
 

Definition at line 73 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Deallocate(), SeqBitmap::MemAlloc(), SeqBitmap::MemDealloc(), and SeqBitmap::SeqBitmap().

unsigned int * SeqBitmap::_memory64 = 0 [static, inherited]
 

Definition at line 77 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Deallocate(), SeqBitmap::MemAlloc(), SeqBitmap::MemDealloc(), and SeqBitmap::SeqBitmap().

unsigned int * SeqBitmap::_memory8 = 0 [static, inherited]
 

Definition at line 74 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Deallocate(), SeqBitmap::MemAlloc(), SeqBitmap::MemDealloc(), and SeqBitmap::SeqBitmap().

int * SeqBitmap::_numOnesLookupTable = 0 [static, inherited]
 

Definition at line 60 of file SeqBitmap.cpp.

Referenced by SeqBitmap::Compress16(), SeqBitmap::Compress32(), SeqBitmap::Compress64(), SeqBitmap::Compress8(), SeqBitmap::CountSmaller(), SeqBitmap::Destroy(), and SeqBitmap::Init().

int SeqBitmap::_size16 = 0 [static, inherited]
 

Definition at line 82 of file SeqBitmap.cpp.

Referenced by SeqBitmap::MemAlloc().

int SeqBitmap::_size32 = 0 [static, inherited]
 

Definition at line 83 of file SeqBitmap.cpp.

Referenced by SeqBitmap::MemAlloc().

int SeqBitmap::_size4 = 0 [static, inherited]
 

Definition at line 80 of file SeqBitmap.cpp.

Referenced by SeqBitmap::MemAlloc().

int SeqBitmap::_size64 = 0 [static, inherited]
 

Definition at line 84 of file SeqBitmap.cpp.

Referenced by SeqBitmap::MemAlloc().

int SeqBitmap::_size8 = 0 [static, inherited]
 

Definition at line 81 of file SeqBitmap.cpp.

Referenced by SeqBitmap::MemAlloc().

const int Bit16Table[16]
 

Initial value:

    {
        32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1
    }
Bit16Table[i] contains a 1 at only position i.

Definition at line 70 of file Tables.h.

Referenced by Bitmap16::FillEmptyPosition().

const unsigned int Bit32Table[32]
 

Initial value:

    {
        2147483648UL, 1073741824UL, 536870912UL, 268435456UL,
        134217728, 67108864, 33554432, 16777216,
        8388608, 4194304, 2097152, 1048576,
        524288, 262144, 131072, 65536,
        32768, 16384, 8192, 4096,
        2048, 1024, 512, 256,
        128, 64, 32, 16,
        8, 4, 2, 1
    }
Bit32Table[i] contains a 1 at only position i.

Definition at line 57 of file Tables.h.

Referenced by Bitmap8::FillEmptyPosition(), Bitmap64::FillEmptyPosition(), Bitmap4::FillEmptyPosition(), and Bitmap32::FillEmptyPosition().

const int BITMAP_LENGTH[5]
 

Initial value:

    {
        4, 8, 16, 32, 64
    }
the size of each customer data in each bitmap

Definition at line 54 of file SeqBitmap.cpp.

const int BITS_PER_INT = SIZE_UINT * SIZE_BYTE
 

Definition at line 52 of file Tables.h.

Referenced by Bitmap4::Bitmap4(), Bitmap8::Bitmap8(), Bitmap8::CalcSize(), Bitmap4::CalcSize(), Bitmap8::FillEmptyPosition(), Bitmap64::FillEmptyPosition(), Bitmap4::FillEmptyPosition(), and Bitmap32::FillEmptyPosition().

const int BITS_PER_SHORT = SIZE_USHORT * SIZE_BYTE
 

Definition at line 53 of file Tables.h.

Referenced by Bitmap16::FillEmptyPosition().

const char CountTable[256]
 

Initial value:

    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1,
        2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1,
        2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2,
        3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    }
CountTable[i] contains the number of 1's in the byte value of i.

Definition at line 77 of file Tables.h.

const int NUM_BITMAP = 5
 

number of different bitmaps in SeqBitmap

Definition at line 51 of file SeqBitmap.cpp.

const int SHORT_PER_INT = SIZE_UINT / SIZE_USHORT
 

Definition at line 51 of file Tables.h.

Referenced by Bitmap16::Bitmap16(), Bitmap32::Bitmap32(), Bitmap4::Bitmap4(), Bitmap64::Bitmap64(), and Bitmap8::Bitmap8().

const int SIZE_BYTE = 8
 

Definition at line 46 of file Tables.h.

const int SIZE_INT = sizeof(int)
 

Definition at line 47 of file Tables.h.

Referenced by Bitmap8::Init(), Bitmap64::Init(), Bitmap4::Init(), and Bitmap32::Init().

const int SIZE_UINT = sizeof(unsigned int)
 

Definition at line 48 of file Tables.h.

Referenced by Bitmap32::Bitmap32(), Bitmap4::Bitmap4(), Bitmap64::Bitmap64(), Bitmap8::Bitmap8(), Bitmap8::CalcSize(), Bitmap64::CalcSize(), Bitmap4::CalcSize(), Bitmap32::CalcSize(), Bitmap8::Deallocate(), Bitmap64::Deallocate(), Bitmap4::Deallocate(), Bitmap32::Deallocate(), Bitmap64::Init(), Bitmap32::Init(), and Bitmap16::Init().

const int SIZE_USHORT = sizeof(unsigned short)
 

Definition at line 49 of file Tables.h.

Referenced by Bitmap16::Bitmap16(), Bitmap16::CalcSize(), and Bitmap16::Deallocate().

Generated on Thu Mar 11 12:01:54 2004 for SPAM by doxygen 1.3.4