asked on

ultra huge array of Bits (Boolean)

i Want to create a bit array , size [1...1E6, 1...1E6] or even a little bit bigger. .-))
I used a TList Object and a Bool-Pointer
max. array size is only 1E5x1E5 . Any Hint thow o blow up my record size?
the function TBitplane.Init_BitArray should run with stepx=1E6.. and function stepy=1E6...

------------------
some trial code
------------------

type
TPointBoolZ = record
// x : Integer; { x index = 0...n, removed, changed to lin. Address }
// y : Integer; { y index = 0...m, removed, changed to lin. Address }
Z : Boolean;
end;

TPointBoolZPtr =^TPointBoolZ;

{ 2D Array of Bool to calc the area of any arbitray gemomatical layouts }
TBitPlane = Class

BitArray : TList;

constructor Create;

private
Upp : FPoint;
Low : FPoint;

deltax : Real;
deltay : Real;

stepX : Integer;
stepY : Integer;

{ Function for discrete geometric (DG) problems }

public

function Init_BitArray : Boolean;

function AddTRect(MyRect : TRect) : Boolean;
function AddTFRect(MyFRect : TFRect) : Boolean;

function AddTCircle(MyRect : TRect) : Boolean;
function AddFCircle(MyFRect : TFRect) : Boolean;

function AddTThickline(MyLine: TThickline): Boolean;

function GetTIndex (MyPoint :FPoint): TPoint;
function GetFPoint (MyPoint :TPoint): FPoint;

function VirtualPoint(I: Integer): TPoint;

function AssignSize(UpperCorner, LowerCorner : FPoint; Sx, Sy : Integer) : Boolean;

function SetBitArray (x,y : Integer; Value : Boolean) : Boolean;

function GetBitArea: real;

function GetFalseCount : Integer;
function GetBitArray(x, y: Integer): Boolean;
end;

{ Calculate from the 1D Array of Bool to 2d Array A[X;Y] }
function TBitplane.VirtualPoint(I : Integer): TPoint;
var V : TPoint;
x,y : Word;
begin
// procedure DivMod(Dividend: Integer; Divisor: Word; var Result, Remainder: Word);
DivMod(i, stepx,y,x);

V.x :=x;
V.y :=y;

result := v;

end;

function TBitplane.Init_BitArray : Boolean;
var x, y : Integer;

SinglePoint : TPointBoolZPtr;
begin

BitArray.Clear;

try
begin
for y:=0 to stepy do
for x := 0 to stepx do
begin

new(SinglePoint);

// SinglePoint^.x := x; { version 1 only }

// SinglePoint^.y := y; { version 1 only }

SinglePoint^.Z := false;

BitArray.Add(SinglePoint);
end;
result := true;
end;
except
result := false;
end;
end;

SOLUTION

Lukasz Zielinski

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

ASKER CERTIFIED SOLUTION

Russell Libby

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

MerijnB

I agree with rlibby.

So the big question is what you need it for, maybe there is a better solution for your problem.

Russell Libby

**IF** you are dealing with a very sparse array/matrix, then there may be some hope. For the education of those not familiar with what a sparse array/matrix is:

http://www.answers.com/topic/sparse-matrix

An example data structure for the handling might look like:

type
PSparseCol = ^TSparseCol;
TSparseCol = packed record
Col: Integer;
Next: PSparseCol;
end;

var
RowArray: Array [1..1000000] of PSparseCol;

The row array is 4MB in size, and contains a singly linked list to each "column" that is in an "on" state (on/set/true/whatever you want to call it). This would allow for a theoretical maximum of 267 million bits being on at once. And by very sparse, I mean VERY sparse, as you would still only be able to address less than 1 percent of the virtual array size.

Russell

SOLUTION

tobjectpascal

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

BdLm

ASKER

many thanks to all of you for the good inputs.

1) the background of the question: I got tons of images (~ xx GByte) building up a map, I have to sum up cerain araes with in these images. Step and repeat with my algo through the whole image would be one idea, but to keep the whole image in one array makes the code quite easy.

2) a sparse matrix approach won't help completly, Im thinking about something like a compressed array , as 0 and 1 's are balanced and once I got a '1' the will always be a certain sequence of '1'. This would also speed my area sum algorithm.