Board index » delphi » items stored as range in a list

2007-01-29 06:42:35 AM
delphi86
hi!
i need to handle a lot of Int64's in a list, but only store the ranges
of items.
i made a class to store these numbers.
for example i add these numbers:
1,2,3,5,6,10,11,12,13,14,16 (needs 88 bytes)
the class only stores the ranges as:
1-3, 5-6, 10-14, 16 (needs 56 bytes)
so i can keep the needed place as low as possible ()
i made a unit to handle my needs but i think i can be better... :)
here it is:
[code]
unit Unit_Int64List;
interface
uses
Classes;
const
TIntegerSize = SizeOf(Integer);
type
TInt64List = class
private
FList: TList;
FUpdateCount: Integer;
function GetCount: Int64;
function GetRangeCount: Integer;
procedure DeleteRange(Index: Integer);
function FindRangeIndex(const Value: Int64): Integer;
procedure CalcStartIndex(const FromIndex: Integer);
public
constructor Create;
destructor Destroy; override;
function Add(const Value: Int64): Int64;
function FindValue(const Value: Int64): Int64;
procedure Clear;
procedure Compact(const ReCalcStartIndex: Boolean = False);
procedure SaveToStream(F: TStream);
procedure LoadFromStream(F: TStream);
//
property Count: Int64 read GetCount;
property RangeCount: Integer read GetRangeCount;
end;
implementation
uses
SysUtils, Unit_Utils;
type
TInt64RangeItem = class
private
public
StartIndex: Int64;
Start: Int64;
Stop: Int64;
protected
constructor Create(const _Start: Int64; const _Stop: Int64 = 0);
virtual;
published
end;
constructor TInt64RangeItem.Create(const _Start: Int64; const _Stop:
Int64 = 0);
begin
inherited Create;
Start := _Start;
if (_Stop>0) then
Stop := _Stop;
end;
constructor TInt64List.Create;
begin
inherited Create;
FList := TList.Create;
FUpdateCount := 0;
end;
destructor TInt64List.Destroy;
begin
Clear;
FreeAndNil(FList);
inherited Destroy;
end;
function TInt64List.Add(const Value: Int64): Int64;
var
R: TInt64RangeItem;
RangePos: Integer;
function AddValue: Int64;
begin
Result := 0;
R := TInt64RangeItem.Create(Value);
R.Start := Value;
R.Stop := Value;
FList.Insert(RangePos, R);
end;
begin
RangePos := FindRangeIndex(Value);
R := nil;
if (0 <= RangePos) and (RangePos < FList.Count) then
begin
R := TInt64RangeItem(FList[RangePos]);
if (R.Start <= Value) and (Value <= R.Stop) then
Result := R.StartIndex + (Value - R.Start)
else
Result := AddValue;
end else
Result := AddValue;
end;
function TInt64List.FindRangeIndex(const Value: Int64): Integer;
var
Min,Max: Integer;
RangeCursor: TInt64RangeItem;
begin
Min := 0;
Max := (FList.Count-1);
RangeCursor := nil;
Result := 0;
while (Min <= Max) do
begin
Result := (Min + Max ) shr 1;
RangeCursor := TInt64RangeItem(FList[Result]);
if (Value < RangeCursor.Start) then Max := (Result - 1) else
if (Value <= RangeCursor.Stop ) then Break else
Min := (Result + 1);
end;
if (RangeCursor <>nil) then
begin
if (Value < RangeCursor.Start) or
(Value>RangeCursor.Stop ) then
Result := Min;
end;
end;
function TInt64List.FindValue(const Value: Int64): Int64;
var
R: TInt64RangeItem;
RangePos: Integer;
begin
Result := -1;
RangePos := FindRangeIndex(Value);
if (0 <= RangePos ) and
(RangePos < FList.Count) then
begin
R := TInt64RangeItem(FList[RangePos]);
if (R.Start <= Value) and (Value <= R.Stop) then
Result := R.StartIndex + (Value - R.Start);
end;
end;
procedure TInt64List.Clear;
var
I: Integer;
begin
I := (FList.Count-1);
while (I>-1) do
begin
TInt64RangeItem(FList[I]).Free;
Dec(I);
end;
FList.Clear;
FList.Pack;
end;
procedure TInt64List.Compact(const ReCalcStartIndex: Boolean = False);
var
I: Integer;
begin
if (FList.Count>1) then
begin
I := 0;
repeat
if (TInt64RangeItem(FList[I+1]).Start <=
(TInt64RangeItem(FList[I]).Stop+1)) then
begin
TInt64RangeItem(FList[I]).Stop :=
TInt64RangeItem(FList[I+1]).Stop;
DeleteRange(I+1);
end else
Inc(I);
until (I = (FList.Count-1));
if (RecalcStartIndex = True) then
CalcStartIndex(0);
end;
end;
function TInt64List.GetCount: Int64;
var
I: Integer;
R: TInt64RangeItem;
begin
Result := 0;
if (FList.Count>0) then
for I := 0 to (FList.Count-1) do
begin
R := TInt64RangeItem(FList[I]);
Result := Result + (R.Stop - R.Start + 1);
end;
end;
function TInt64List.GetRangeCount: Integer;
begin
Result := FList.Count;
end;
procedure TInt64List.DeleteRange(Index: Integer);
var
R: TInt64RangeItem;
begin
if (Index>= 0 ) and
(Index < FList.Count) then
begin
R := FList[Index];
FList.Delete(Index);
FreeAndNil(R);
end;
end;
procedure TInt64List.CalcStartIndex(const FromIndex: Integer);
var
I,StartIndex: Integer;
Index: Int64;
R: TInt64RangeItem;
begin
if (FList.Count>0) then
begin
StartIndex := FromIndex;
if (StartIndex < 0 ) then StartIndex := 0;
if (StartIndex>(FList.Count-1)) then StartIndex :=
(FList.Count-1);
Index := 0;
for I := StartIndex to (FList.Count-1) do
begin
R := TInt64RangeItem(FList[I]);
R.StartIndex := Index;
Inc(Index, (R.Stop - R.Start + 1));
end;
end;
end;
function CompareRanges(R1, R2: TInt64RangeItem): Integer;
begin
Result := 0;
if (R1 <>R2) then
begin
if (R1.Start < R2.Start) then Result := -1 else
if (R1.Start>R2.Start) then Result := 1 else
begin
if (R1.Stop < R2.Stop) then Result := -1 else
if (R1.Stop>R2.Stop) then Result := 1
else Result := 0;
end;
end;
end;
procedure TInt64List.SaveToStream(F: TStream);
var
I: Integer;
R: TInt64RangeItem;
B: Boolean;
begin
FList.Sort(@CompareRanges);
Compact;
I := FList.Count;
F.Write(I, TIntegerSize);
if (I>0) then
for I := 0 to (FList.Count-1) do
begin
R := TInt64RangeItem(FList[I]);
F.Write(R.Start, 8);
B := (R.Start = R.Stop);
F.Write(B, 1);
if (B = False) then
F.Write(R.Stop, 8);
end;
end;
procedure TInt64List.LoadFromStream(F: TStream);
var
I,C: Integer;
B: Boolean;
V1,V2: Int64;
begin
Clear;
F.Read(C, TIntegerSize);
if (C>0) then
begin
FList.Capacity := C;
for I := 1 to C do
begin
F.Read(V1, 8);
F.Read(B , 1);
if (B = False) then F.Read(V2, 8)
else V2 := V1;
FList.Add(TInt64RangeItem.Create(V1,V2));
end;
end;
CalcStartIndex(0);
end;
end.
[/code]
can anybody tell me directions how to make it better?
greetings:
xcluster
ps:
sorry for my poor english... :)
xcluster
--- posted by geoForum on delphi.newswhat.com
 

"xcluster" <XXXX@XXXXX.COM>writes
If you haven't used unit tests before, this is an excellent place to start.
It will give you a lot more confidence in your code, make it easier
to change, and probably find some subtle bugs for you.
Also, this looks suspicious:
if (_Stop>0) then
Stop := _Stop;
What should Stop be if _Stop is 0 or -1?
--
HTH,
Brad.
 

hy!
new (improved) version:
<pre>
unit Unit_Int64List;
interface
uses
Classes;
type
TInt64RangeItem = class
private
public
StartIndex: Int64;
Start: Int64;
Stop: Int64;
class function NewInstance: TObject; override;
procedure FreeInstance; override;
protected
constructor Create(const _Start, _Stop: Int64);
published
end;
type
TInt64List = class
private
FList: TList;
FUpdateCount: Integer;
FCount: Int64;
function GetCount: Int64;
function GetRangeCount: Integer;
function FindRangeIndex(const Value: Int64; var Index: Integer):
Boolean;
procedure CalcStartIndex;
function GetRange(Index: Integer): TInt64RangeItem;
public
constructor Create;
destructor Destroy; override;
function Add(const Value: Int64): Int64;
procedure DeleteRange(const Index: Integer);
function Find(const Value: Int64; var Index: Int64): Boolean;
function FindGetPath(const Value: Int64): String;
function IndexOf(const Value: Int64): Int64;
procedure Clear;
procedure Compact(const ReCalcStartIndex: Boolean = False);
procedure SaveToStream(F: TStream);
procedure LoadFromStream(F: TStream);
//
property Count: Int64 read GetCount;
property RangeCount: Integer read
GetRangeCount;
property Ranges[Index: Integer]: TInt64RangeItem read GetRange;
end;
implementation
uses
SysUtils, Unit_Utils;
const
TIntegerSize = SizeOf(Integer);
//
-----------------------------------------------------------------------------
class function TInt64RangeItem.NewInstance: TObject;
type
PClass = ^TClass;
var
P: Pointer;
begin
GetMem(P, Self.InstanceSize); //Allocate Memory for this object
Result := TObject(P); // Set the result
InitInstance(P); // Initialise the Instance
PClass(Result)^ := Self; // Init VMT, don't init fields.
end;
procedure TInt64RangeItem.FreeInstance;
begin
CleanupInstance; // Clean Up
FreeMem(Pointer(Self), Self.InstanceSize); // Free Memeory
end;
constructor TInt64RangeItem.Create(const _Start, _Stop: Int64);
begin
inherited Create;
Start := _Start;
Stop := _Stop;
end;
//
-----------------------------------------------------------------------------
constructor TInt64List.Create;
begin
inherited Create;
FList := TList.Create;
FUpdateCount := 0;
FCount := 0;
end;
destructor TInt64List.Destroy;
begin
Clear;
FreeAndNil(FList);
inherited Destroy;
end;
function TInt64List.Add(const Value: Int64): Int64;
var
R: TInt64RangeItem;
RangePos: Integer;
begin
if (FindRangeIndex(Value, RangePos) = True) then
begin
R := FList.List^[RangePos];
Result := R.StartIndex + (Value - R.Start);
end else
begin
Result := 0;
if (FList.Count>0) then
begin
if (RangePos < FList.Count) then
begin
R := FList.List^[RangePos];
if ((Value+1) = R.Start) then
R.Start := Value
else
if (RangePos>0) then
begin
R := FList.List^[RangePos-1];
if ((R.Stop+1) = Value) then
R.Stop := Value
else
FList.Insert(RangePos, TInt64RangeItem.Create(Value,
Value));
end else
FList.Insert(0, TInt64RangeItem.Create(Value, Value));
end else
begin
R := FList.List^[RangePos-1];
if ((R.Stop+1) = Value) then
R.Stop := Value
else
FList.Add(TInt64RangeItem.Create(Value, Value));
end;
end else
FList.Add(TInt64RangeItem.Create(Value, Value));
Inc(FCount);
end;
end;
procedure TInt64List.DeleteRange(const Index: Integer);
var
R: TInt64RangeItem;
begin
if (Index>= 0 ) and
(Index < FList.Count) then
begin
R := FList.List^[Index];
FList.Delete(Index);
FreeAndNil(R);
end;
end;
function TInt64List.FindRangeIndex(const Value: Int64; var Index:
Integer): Boolean;
var
Low,High,Mid: Integer;
RangeCursor: TInt64RangeItem;
begin
Low := 0;
High := FList.Count - 1;
Mid := 0;
Result := False;
while not Result and ( Low <= High ) do
begin
Mid := (Low + High) shr 1;
RangeCursor := FList.List^[Mid];
if (RangeCursor.Start <= Value) and (Value <= RangeCursor.Stop)
then
Result := True
else
if (Value < RangeCursor.Start) then High := Mid - 1 else
if (Value>RangeCursor.Stop ) then Low := Mid + 1;
end;
if Result then Index := Mid
else Index := Low;
end;
function TInt64List.Find(const Value: Int64; var Index: Int64):
Boolean;
var
R: TInt64RangeItem;
RangePos: Integer;
begin
Index := -1;
Result := FindRangeIndex(Value, RangePos);
if (Result = True) then
begin
R := FList.List^[RangePos];
Index := R.StartIndex + (Value - R.Start);
end;
end;
function TInt64List.FindGetPath(const Value: Int64): String;
var
Low,High,Mid: Int64;
RangeCursor: TInt64RangeItem;
F: Boolean;
V: Int64;
begin
Result := '';
// Find range index
----------------------------------------------------------
F := False;
High := FList.Count - 1;
Low := 0;
Mid := 0;
while not F and ( Low <= High ) do
begin
Mid := (Low + High) div 2;
RangeCursor := FList.List^[Mid];
if (RangeCursor.Start <= Value) and (Value <= RangeCursor.Stop)
then
begin
Result := Result + '11';
F := True;
end else
if (Value < RangeCursor.Start) then
begin
Result := Result + '10';
High := Mid - 1;
end else
if (Value>RangeCursor.Stop ) then
begin
Result := Result + '01';
Low := Mid + 1;
end;
end;
if (F = True) then
begin
// Find index IN range
-----------------------------------------------------
Result := Result + '|';
F := False;
Low := 0;
High := TInt64RangeItem(FList.List^[Mid]).Stop -
TInt64RangeItem(FList.List^[Mid]).Start;
while not F and ( Low <= High ) do
begin
Mid := (Low + High) div 2;
V := TInt64RangeItem(FList.List^[Mid]).Start + Mid;
if (Value = V) then
begin
Result := Result + '11';
F := True;
end else
if (Value < V) then
begin
Result := Result + '10';
High := Mid - 1;
end else
if (Value>V) then
begin
Result := Result + '01';
Low := Mid + 1;
end;
end;
end else
Result := '|';
end;
function TInt64List.IndexOf(const Value: Int64): Int64;
begin
Find(Value, Result);
end;
procedure TInt64List.Clear;
var
I: Integer;
begin
if (FList.Count>0) then
for I := (FList.Count-1) downto 0 do
begin
TInt64RangeItem(FList.List^[I]).Free;
//Dispose(FList.List^[I]);
FList.Delete(I);
end;
FList.Pack;
FList.Clear;
end;
procedure TInt64List.Compact(const ReCalcStartIndex: Boolean = False);
var
I: Integer;
C,N: TInt64RangeItem;
begin
if (FList.Count>1) then
begin
I := 0;
repeat
C := TInt64RangeItem(FList.List^[I ]);
N := TInt64RangeItem(FList.List^[I+1]);
//
if (N.Start <= (C.Stop+1)) then
begin
if (N.Start <= C.Start) then
C.Start := N.Start;
C.Stop := N.Stop;
DeleteRange(I+1);
end else
Inc(I);
until (I = (FList.Count-1));
if (RecalcStartIndex = True) then
CalcStartIndex;
end;
end;
function TInt64List.GetCount: Int64;
begin
Result := FCount;
end;
function TInt64List.GetRangeCount: Integer;
begin
Result := FList.Count;
end;
procedure TInt64List.CalcStartIndex;
var
I: Integer;
R: TInt64RangeItem;
begin
FCount := 0;
if (FList.Count>0) then
for I := 0 to (FList.Count-1) do
begin
R := FList.List^[I];
R.StartIndex := FCount;
Inc(FCount, (R.Stop - R.Start + 1));
end;
end;
function TInt64List.GetRange(Index: Integer): TInt64RangeItem;
begin
Result := nil;
if (0 <= Index) and (Index < FList.Count) then
Result := FList.List^[Index];
end;
procedure TInt64List.SaveToStream(F: TStream);
var
I: Integer;
R: TInt64RangeItem;
V: packed record
V1: Int64; // +8
V2: Int64; // +8
end;
M: TMemoryStream;
procedure FlushBuffer;
begin
M.Seek(0,0);
F.CopyFrom(M, M.Size);
M.Size := 0;
end;
begin
Compact;
if (FList.Count>0) then
begin
M := TMemoryStream.Create;
//
-------------------------------------------------------------------------
for I := 0 to (FList.Count-1) do
begin
R := FList.List^[I];
V.V1 := R.Start;
V.V2 := R.Stop;
M.Write(V, 16);
if (M.Size>65536) then
FlushBuffer;
end;
//
-------------------------------------------------------------------------
FlushBuffer;
FreeAndNil(M);
end;
end;
procedure TInt64List.LoadFromStream(F: TStream);
var
I,C: Integer;
V: packed record
V1: Int64; // +8
V2: Int64; // +8
end;
M: TMemoryStream;
MW: Int64;
RC,RN: TInt64RangeItem;
begin
//
---------------------------------------------------------------------------
Clear;
//
---------------------------------------------------------------------------
M := TMemoryStream.Create;
M.Size := F.Size;
M.CopyFrom(F, F.Size);
M.Seek(0,0);
//
---------------------------------------------------------------------------
C := (M.Size div SizeOf(V));
if (C>0) then
begin
FList.Capacity := C;
for I := 1 to C do
begin
M.Read(V, 16);
FList.Add(TInt64RangeItem.Create(V.V1, V.V2));
end;
end;
FreeAndNil(M);
//
---------------------------------------------------------------------------
CalcStartIndex;
//
---------------------------------------------------------------------------
MW := 0;
for I := 0 to (FList.Count-1) do
begin
RC := FList.List^[I];
if (MW < (RC.Stop-RC.Start)) then
MW := (RC.Stop-RC.Start);
end;
WriteLn('MaxWidth = ',MW:20);
//
---------------------------------------------------------------------------
MW := 0;
for I := 0 to (FList.Count-2) do
begin
RC := FList.List^[I ];
RN := FList.List^[I+1];
if (MW < (RN.Start-RC.Stop)) then
MW := (RN.Start-RC.Stop);
end;
WriteLn('MaxDiff = ',MW:20);
//
---------------------------------------------------------------------------
end;
end.
</pre>
xcluster