Ignore:
Timestamp:
Jan 1, 2011, 1:34:29 AM (14 years ago)
Author:
george
Message:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Generics/TemplateGenerics/Generic/GenericList.inc

    r101 r107  
    1717    function GetFirst: TGListItem;
    1818    procedure SetCapacity(const AValue: TGListIndex);
     19    procedure SetCapacityOptimized(const NewCapacity: TGListIndex);
    1920    procedure SetLast(AValue: TGListItem);
    2021    procedure SetFirst(AValue: TGListItem);
    2122    procedure Put(Index: TGListIndex; const AValue: TGListItem); virtual;
    22     procedure SetCount(const AValue: TGListIndex);
     23    procedure SetCount(const AValue: TGListIndex); virtual;
    2324    procedure QuickSort(L, R : TGListIndex; Compare: TGListSortCompare);
    2425  public
    … …  
    2829    procedure Assign(Source: TGList); virtual;
    2930    procedure Clear; virtual;
    30     procedure Contract;
    3131    procedure Delete(Index: TGListIndex); virtual;
    3232    procedure DeleteItems(Index, Count: TGListIndex);
    3333    function EqualTo(List: TGList): Boolean;
    34     procedure Expand;
    3534    function Extract(Item: TGListItem): TGListItem;
    3635    procedure Exchange(Index1, Index2: TGListIndex);
    … …  
    7877procedure TGList.SetCapacity(const AValue: TGListIndex);
    7978begin
     79  if (AValue < FCount) then
     80    raise EListError.CreateFmt(SListCapacityError, [AValue]);
    8081  SetLength(FItems, AValue);
    8182end;
    8283
     84procedure TGList.SetCapacityOptimized(const NewCapacity: TGListIndex);
     85var
     86  IncSize: TGListIndex;
     87begin
     88  if NewCapacity > Capacity then begin
     89    IncSize := NewCapacity - Capacity;
     90    // Expand
     91    if FCount = Capacity then begin
     92      IncSize := 4;
     93      if Capacity > 3 then IncSize := IncSize + 4;
     94      if Capacity > 8 then IncSize := IncSize + 8;
     95      if Capacity > 63 then IncSize := IncSize + Capacity shr 2; // Grow by one quarter
     96      Capacity := Capacity + IncSize;
     97    end;
     98  end else
     99  if NewCapacity < Capacity then begin
     100    // Contract
     101    if (Capacity > 256) and (FCount < Capacity shr 2) then
     102    begin
     103      Capacity := Capacity shr 1;
     104    end;
     105  end;
     106end;
     107
    83108function TGList.Get(Index: TGListIndex): TGListItem;
    84109begin
    … …  
    93118procedure TGList.SetCount(const AValue: TGListIndex);
    94119begin
    95   SetLength(FItems, AValue);
     120  if (AValue < 0) then
     121    raise EListError.CreateFmt(SListCountError, [AValue]);
     122  if AValue > Capacity then SetCapacityOptimized(AValue); // Before FCount change
    96123  FCount := AValue;
     124  if AValue < Capacity then SetCapacityOptimized(AValue); // After FCount change
    97125end;
    98126
    … …  
    105133   I := L;
    106134   J := R;
    107    P := FItems[ (L + R) div 2 ];
     135   P := FItems[(L + R) div 2];
    108136   repeat
    109137     while Compare(P, FItems[I]) > 0 do
    … …  
    111139     while Compare(P, FItems[J]) < 0 do
    112140       J := J - 1;
    113      If I <= J then
     141     if I <= J then
    114142     begin
    115143       Q := FItems[I];
    … …  
    128156procedure TGList.Assign(Source: TGList);
    129157var
    130   I: Integer;
     158  I: TGListIndex;
    131159begin
    132160  Count := Source.Count;
    … …  
    135163    Items[I] := Source[I];
    136164    I := I + 1;
    137   end;
    138 end;
    139 
    140 procedure TGList.Expand;
    141 var
    142   IncSize: TGListIndex;
    143 begin
    144   if FCount = Capacity then begin
    145     IncSize := 4;
    146     if Capacity > 3 then IncSize := IncSize + 4;
    147     if Capacity > 8 then IncSize := IncSize + 8;
    148     if Capacity > 63 then IncSize := IncSize + Capacity shr 2;
    149     Capacity := Capacity + IncSize;
    150   end;
    151 end;
    152 
    153 procedure TGList.Contract;
    154 begin
    155   if (Capacity > 256) and (FCount < Capacity shr 2) then
    156   begin
    157     Capacity := Capacity shr 1;
    158165  end;
    159166end;
    … …  
    184191  if (Index < 0) or (Index > FCount ) then
    185192    raise EListError.CreateFmt(SListIndexError, [Index]);
    186   if FCount = Capacity then Expand;
     193  if FCount = Capacity then SetCapacityOptimized(Capacity + 1);
    187194  if Index < FCount then
    188195    System.Move(FItems[Index], FItems[Index + 1], (FCount - Index) * SizeOf(TGListItem));
    … …  
    400407function TGList.Add(Item: TGListItem): TGListIndex;
    401408begin
    402   if FCount = Capacity then
    403     Self.Expand;
    404   FItems[FCount] := Item;
    405   Result := FCount;
    406   FCount := FCount + 1;
     409  Count := Count + 1;
     410  Result := FCount - 1;
     411  FItems[Result] := Item;
    407412end;
    408413
    … …  
    430435  FCount := FCount - 1;
    431436  System.Move(FItems[Index + 1], FItems[Index], (FCount - Index) * SizeOf(TGListItem));
    432   Contract;
     437  SetCapacityOptimized(Capacity - 1);
    433438end;
    434439
    … …  
    445450
    446451procedure TGList.Fill(Start, Count: TGListIndex; Value: TGListItem);
    447 begin
    448   while Count > 0 do begin
    449     Items[Start] := Value;
    450     Count := Count - 1;
    451     Start := Start + 1;
     452var
     453  I: TGListIndex;
     454begin
     455  I := Start;
     456  while I < Count do begin
     457    Items[I] := Value;
     458    I := I + 1;
    452459  end;
    453460end;
Note: See TracChangeset for help on using the changeset viewer.