Guest
|
 Posted: Sat Jan 27, 2007 12:35 am Post subject: Store Int64's in a "range-list" |
 |
|
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.
|
can anybody tell me directions how to make it better?
greetings:
ps:
sorry for my poor english...  |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
