plasticarrays.pas

{$MODE OBJFPC} { -*- delphi -*- }
{$INCLUDE settings.inc}
unit plasticarrays;

interface

// migration notes:
//  "Init" can be removed or replaced by a call to Prepare
//  "Clone" and "CloneFrom" should be replaced by just assigning the plastic array

const
   kGrowthFactor: Double = 1.25;

type
   // Utils below is a type with the following static functions:
   //   function Equals(const A, B: T): Boolean;
   //   function LessThan(const A, B: T): Boolean;
   //   function GreaterThan(const A, B: T): Boolean;
   //   function Compare(const A, B: T): Int64; // negative means A is first, positive means B is first, 0 means they're equal

   generic PlasticArray <T, Utils> = record // for Utils see genericutils.pas
      // unlike regular dynamic arrays, this structure is entirely copy-on-write
      // reference counting is _not_ currently thread-safe
      // enumerating over the array operates on the live array, so do not remove entries at or before the current entry while doing so
    private
     type
      // Resist the temptation to add a variant of this that returns
      // pointers to values, because those pointers won't be stable.
      PPlasticArray = ^PlasticArray;
      TArray = array of T;
      PStructure = ^TStructure;
      TStructure = record
         FReferenceCount: Cardinal;
         FAllocatedSize: Cardinal;
         FUsedSize: Cardinal; // when changing this, newly valid FArray values must be Initialize()d and newly invalid FArray values must be Finalize()d
         FArray: array[Cardinal] of T;
      end;
     var
      FData: PStructure;
      class operator Initialize(var Rec: PlasticArray);
      class operator AddRef(var Rec: PlasticArray); 
      class operator Finalize(var Rec: PlasticArray);
      class operator Copy(constref Src: PlasticArray; var Dst: PlasticArray);
      function Allocate(const Count: Cardinal): PStructure; inline; // caller must set FUsedSize on the returned value (even if it is to zero)
      procedure DecRefCount(); inline; // caller must set FData to a valid value after this call
      procedure EnsureUnique(); inline;
      function GetItem(const Index: Cardinal): T; inline;
      procedure SetItem(const Index: Cardinal; const Item: T); inline;
      function GetLast(): T; inline;
      procedure SetLast(const Item: T); inline;
      procedure Grow(const MinCapacity: Cardinal); inline;
      function GetFilledLength(): Cardinal; inline;
      procedure SetFilledLength(const NewFilledLength: Cardinal); inline;
      function GetIsEmpty(): Boolean; inline;
      function GetIsNotEmpty(): Boolean; inline;
   public
      procedure Push(const Item: T); inline; // expensive if it requires the length to be increased
      function Pop(): T; inline; // trivial, does not free memory for slot that is popped
      procedure Empty(); inline; // trivial, does not free memory
      property Length: Cardinal read GetFilledLength write SetFilledLength; // expensive if it requires the length to be increased
      property Items[Index: Cardinal]: T read GetItem write SetItem; default;
      property Last: T read GetLast write SetLast;
      property IsEmpty: Boolean read GetIsEmpty;
      property IsNotEmpty: Boolean read GetIsNotEmpty;
    public
      // The following calls are relatively expensive for various reasons
      procedure Prepare(LikelyLength: Cardinal); inline; // increases the length to LikelyLength
      procedure GrowFor(NewItems: Cardinal); inline; // increases the length to fit at least Length + NewItems, maybe more
      procedure Squeeze(); inline; // reduces memory usage to minimum required
      procedure InsertAt(const InsertIndex: Cardinal; const Value: T); // does a memory move (if Index < FFilledLength)
      procedure RemoveAt(const RemoveIndex: Cardinal); // does a memory move
      procedure Remove(const Value: T); // does a linear search (from end), then memory move
      procedure RemoveAll(const Value: T); // walks the entire array
      procedure RemoveAllTrailing(const Value: T); // walks the entire array, backwards, stops at first non-matching (O(N), but relative cheap)
      procedure Replace(const Value: T; const NewValue: T); // does a linear search (from end), replaces at most one value
      function Contains(const Value: T): Boolean; // linear search
      function Contains(const Value: T; out IndexResult: Cardinal): Boolean; // linear search; IndexResult is only valid if result is True
      procedure RemoveShiftLeftInsert(const RemoveIndex, InsertIndex: Cardinal; NewValue: T);
      function Distill(): TArray; inline; // calls Squeeze(), extracts the array, then resets the PlasticArray
      function Copy(): TArray; inline; // copies the entire array to a new array
    public
     type
      TCompareFunc = function (const A, B: T): Integer is nested;
      procedure Sort(const CompareFunc: TCompareFunc);
      procedure Sort();
      procedure SortSubrange(L, R: Integer; const CompareFunc: TCompareFunc);
      procedure SortSubrange(L, R: Integer);
      procedure Shuffle();
      function Find(Target: T): Cardinal; // binary search; assumes sorted input and Utils with functioning comparators; only works for arrays with FFilledLength <= High(Integer)
    public
     type
       TEnumerator = record
        strict private
          FTarget: PPlasticArray;
          FIndex: Cardinal;
          function GetCurrent(): T;
        public
          constructor Create(const Target: PPlasticArray);
          function MoveNext(): Boolean;
          property Current: T read GetCurrent;
       end;
      function GetEnumerator(): TEnumerator; inline;
    public
     type
       TFilteredEnumerator = record
        strict private
          FTarget: PPlasticArray;
          FIndex: Cardinal;
          FFilter: T;
          function GetCurrent(): T;
        public
          constructor Create(const Target: PPlasticArray; const Filter: T);
          function MoveNext(): Boolean;
          property Current: T read GetCurrent;
          function GetEnumerator(): TFilteredEnumerator; inline;
       end;
      function Without(const Value: T): TFilteredEnumerator; inline;
    public
     type
      TReadOnlyView = record
       strict private
        var
          FArray: PPlasticArray;
         function GetFilledLength(): Cardinal; inline;
         function GetItem(Index: Cardinal): T; inline;
         function GetLast(): T; inline;
       private
         procedure Init(AArray: PPlasticArray);
       public
         // these calls are all O(1)
         property Length: Cardinal read GetFilledLength;
         property Items[Index: Cardinal]: T read GetItem; default;
         property Last: T read GetLast;
         function GetEnumerator(): TEnumerator; inline;
      end;
      function GetReadOnlyView(): TReadOnlyView;
   end;

implementation

uses
   arrayutils, sysutils,

   exceptions, typedump;

class operator PlasticArray.Initialize(var Rec: PlasticArray);
begin
   Rec.FData := nil;
end;

class operator PlasticArray.AddRef(var Rec: PlasticArray);
begin
   if (Assigned(Rec.FData)) then
      Inc(Rec.FData^.FReferenceCount);
end;

class operator PlasticArray.Finalize(var Rec: PlasticArray);
begin
   if (Assigned(Rec.FData)) then
      Rec.DecRefCount();
end;

class operator PlasticArray.Copy(constref Src: PlasticArray; var Dst: PlasticArray);
begin
   if (Assigned(Dst.FData)) then
      Dst.DecRefCount();
   Dst.FData := Src.FData;
   if (Assigned(Dst.FData)) then
      Inc(Dst.FData^.FReferenceCount);
end;

function PlasticArray.Allocate(const Count: Cardinal): PStructure; inline;
begin
   Result := GetMem(PtrUInt(@PStructure(nil)^.FArray) + SizeOf(T) * Count); // $R-
   Result^.FReferenceCount := 1;
   Result^.FAllocatedSize := Count;
   {$IFOPT C+}
   Result^.FUsedSize := High(Result^.FUsedSize);
   {$ENDIF}
end;
      
procedure PlasticArray.DecRefCount(); inline;
var
   Index: Cardinal;
begin
   Assert(Assigned(FData));
   Assert(FData^.FReferenceCount > 0);
   Dec(FData^.FReferenceCount);
   if (FData^.FReferenceCount = 0) then
   begin
      if (FData^.FUsedSize > 0) then
         for Index := 0 to FData^.FUsedSize - 1 do // $R-
            Finalize(FData^.FArray[Index]);
      FreeMem(FData);
      {$IFOPT C+} FData := PStructure(High(PtrUInt)); {$ENDIF}
   end;
end;

procedure PlasticArray.EnsureUnique();
var
   NewData: PStructure;
   Index: Cardinal;
begin
   Assert(Assigned(FData));
   if (FData^.FReferenceCount > 1) then
   begin
      Dec(FData^.FReferenceCount);
      NewData := Allocate(FData^.FAllocatedSize);
      NewData^.FUsedSize := FData^.FUsedSize;
      if (FData^.FUsedSize > 0) then
         for Index := 0 to FData^.FUsedSize - 1 do // $R-
         begin
            Initialize(NewData^.FArray[Index]);
            NewData^.FArray[Index] := FData^.FArray[Index]; // we don't just blindly copy bytes because the data might itself be of a managed type
         end;
      FData := NewData;
   end;
end;

function PlasticArray.GetItem(const Index: Cardinal): T;
begin
   Assert(Index < Length);
   Result := FData^.FArray[Index];
end;

procedure PlasticArray.SetItem(const Index: Cardinal; const Item: T);
begin
   Assert(Index < Length);
   EnsureUnique();
   FData^.FArray[Index] := Item;
end;

function PlasticArray.GetLast(): T;
begin
   Assert(Length > 0);
   Result := FData^.FArray[FData^.FUsedSize - 1]; // $R-
end;

procedure PlasticArray.SetLast(const Item: T);
begin
   Assert(Length > 0);
   FData^.FArray[FData^.FUsedSize - 1] := Item;
end;

function PlasticArray.GetIsEmpty(): Boolean;
begin
   Result := (not Assigned(FData)) or (FData^.FUsedSize = 0);
end;

function PlasticArray.GetIsNotEmpty(): Boolean;
begin
   Result := Assigned(FData) and (FData^.FUsedSize > 0);
end;

procedure PlasticArray.Grow(const MinCapacity: Cardinal);
var
   OldLength, Index: Cardinal;
   NewLength: Int64;
   NewData: PStructure;
begin
   if (Assigned(FData)) then
      OldLength := FData^.FAllocatedSize
   else
      OldLength := 0;
   Assert(MinCapacity > OldLength);
   Assert(kGrowthFactor >= 1.0);
   NewLength := Trunc(OldLength * kGrowthFactor) + 1;
   if (NewLength > High(Cardinal)) then
      NewLength := High(Cardinal);
   if (NewLength < MinCapacity) then
      NewLength := MinCapacity;
   NewData := Allocate(NewLength); // $R-
   if (Assigned(FData)) then
   begin
      NewData^.FUsedSize := FData^.FUsedSize;
      if (FData^.FUsedSize > 0) then
         for Index := 0 to FData^.FUsedSize - 1 do // $R-
         begin
            Initialize(NewData^.FArray[Index]);
            NewData^.FArray[Index] := FData^.FArray[Index]; // we don't just blindly copy bytes because the data might itself be of a managed type
         end;
      DecRefCount();
   end
   else
   begin
      NewData^.FUsedSize := 0;
   end;
   FData := NewData;
end;

function PlasticArray.GetFilledLength(): Cardinal;
begin
   if (Assigned(FData)) then
      Result := FData^.FUsedSize
   else
      Result := 0;
end;

procedure PlasticArray.SetFilledLength(const NewFilledLength: Cardinal);
var
   Index: Cardinal;
begin
   if (NewFilledLength > 0) then
   begin
      if (not Assigned(FData)) then
      begin
         FData := Allocate(NewFilledLength);
         for Index := 0 to NewFilledLength - 1 do // $R-
            Initialize(FData^.FArray[Index]);
         FData^.FUsedSize := NewFilledLength;
      end
      else
      if (NewFilledLength > FData^.FUsedSize) then
      begin
         if (NewFilledLength > FData^.FAllocatedSize) then
            Grow(NewFilledLength);
         EnsureUnique();
         for Index := FData^.FUsedSize to NewFilledLength - 1 do // $R-
            Initialize(FData^.FArray[Index]);
         FData^.FUsedSize := NewFilledLength;
      end
      else
      if (NewFilledLength < FData^.FUsedSize) then
      begin
         EnsureUnique();
         for Index := FData^.FUsedSize - 1 downto NewFilledLength do // $R-
            Finalize(FData^.FArray[Index]);
         FData^.FUsedSize := NewFilledLength;
      end;
   end
   else
   if (Assigned(FData)) then
   begin
      if (FData^.FUsedSize > 0) then
      begin
         EnsureUnique();
         for Index := FData^.FUsedSize - 1 downto 0 do // $R-
            Finalize(FData^.FArray[Index]);
         FData^.FUsedSize := 0;
      end;
   end;
end;

procedure PlasticArray.Prepare(LikelyLength: Cardinal);
var
   Index: Cardinal;
   NewData: PStructure;
begin
   Assert(LikelyLength > 0);
   Assert(LikelyLength >= Length);
   if (not Assigned(FData)) then
   begin
      FData := Allocate(LikelyLength);
      FData^.FUsedSize := 0;
   end
   else
   if (LikelyLength > FData^.FAllocatedSize) then
   begin
      NewData := Allocate(LikelyLength);
      NewData^.FUsedSize := FData^.FUsedSize;
      if (FData^.FUsedSize > 0) then
         for Index := 0 to FData^.FUsedSize - 1 do // $R-
         begin
            Initialize(NewData^.FArray[Index]);
            NewData^.FArray[Index] := FData^.FArray[Index]; // we don't just blindly copy bytes because the data might itself be of a managed type
         end;
      DecRefCount();
      FData := NewData;
   end;
end;

procedure PlasticArray.GrowFor(NewItems: Cardinal);
begin
   Assert(NewItems > 0);
   Assert(Length + NewItems <= High(Cardinal)); // $R-
   if (Assigned(FData)) then
   begin
      if (FData^.FUsedSize + NewItems <= FData^.FAllocatedSize) then
         exit;
      Inc(NewItems, FData^.FUsedSize);
   end;
   Grow(NewItems);
end;

procedure PlasticArray.Squeeze();
var
   NewData: PStructure;
   Index: Cardinal;
begin
   if (Assigned(FData) and (FData^.FUsedSize <> FData^.FAllocatedSize)) then
   begin
      NewData := Allocate(FData^.FUsedSize);
      if (FData^.FUsedSize > 0) then
         for Index := 0 to FData^.FUsedSize - 1 do // $R-
         begin
            Initialize(NewData^.FArray[Index]);
            NewData^.FArray[Index] := FData^.FArray[Index]; // we don't just blindly copy bytes because the data might itself be of a managed type
         end;
      NewData^.FUsedSize := FData^.FUsedSize;
      DecRefCount();
      FData := NewData;
   end;
end;

procedure PlasticArray.Empty();
var
   Index: Cardinal;
begin
   if (Assigned(FData) and (FData^.FUsedSize > 0)) then
   begin
      EnsureUnique();
      for Index := FData^.FUsedSize - 1 downto 0 do // $R-
         Finalize(FData^.FArray[Index]);
      FData^.FUsedSize := 0;
   end;
end;

procedure PlasticArray.Push(const Item: T);
begin
   if (not Assigned(FData)) then
   begin
      FData := Allocate(1);
      Initialize(FData^.FArray[0]);
      FData^.FUsedSize := 1;
   end
   else
   if (FData^.FUsedSize < FData^.FAllocatedSize) then
   begin
      EnsureUnique();
      Initialize(FData^.FArray[FData^.FUsedSize]);
      Inc(FData^.FUsedSize);
   end
   else
   begin
      Assert(FData^.FUsedSize < High(FData^.FUsedSize));
      Grow(FData^.FUsedSize + 1); // $R-
      Assert(Assigned(FData) and (FData^.FUsedSize < FData^.FAllocatedSize) and (FData^.FReferenceCount = 1));
      Initialize(FData^.FArray[FData^.FUsedSize]);
      Inc(FData^.FUsedSize);
   end;
   FData^.FArray[FData^.FUsedSize - 1] := Item;
end;

function PlasticArray.Pop(): T;
begin
   Assert(Assigned(FData));
   EnsureUnique();
   Dec(FData^.FUsedSize);
   Result := FData^.FArray[FData^.FUsedSize];
   Finalize(FData^.FArray[FData^.FUsedSize]);
end;

procedure PlasticArray.InsertAt(const InsertIndex: Cardinal; const Value: T);
var
   Index: Cardinal;
begin
   if (not Assigned(FData) or (InsertIndex = FData^.FUsedSize)) then
   begin
      Push(Value);
      exit;
   end;
   Assert(InsertIndex < FData^.FUsedSize);
   EnsureUnique(); // TODO: we could avoid one set of copies here by doing this manually
   GrowFor(1);
   Initialize(FData^.FArray[FData^.FUsedSize]);
   Inc(FData^.FUsedSize);
   Assert(FData^.FUsedSize >= 2); // if it was zero before, then we would have taken the Push branch, anything else and it'll be >= 2 now
   for Index := FData^.FUsedSize - 2 downto InsertIndex do // $R-
      FData^.FArray[Index + 1] := FData^.FArray[Index];
   FData^.FArray[InsertIndex] := Value;
end;

procedure PlasticArray.RemoveAt(const RemoveIndex: Cardinal);
var
   Index: Cardinal;
begin
   Assert(Assigned(FData));
   Assert(FData^.FUsedSize > 0); // otherwise nothing to remove
   Assert(RemoveIndex < FData^.FUsedSize);
   EnsureUnique(); // TODO: we could avoid one set of copies here by doing this manually
   if (RemoveIndex < FData^.FUsedSize - 1) then
   begin
      Assert(FData^.FUsedSize >= 2);
      for Index := RemoveIndex to FData^.FUsedSize - 2 do // $R-
         FData^.FArray[Index] := FData^.FArray[Index + 1];
   end;
   Dec(FData^.FUsedSize);
   Finalize(FData^.FArray[FData^.FUsedSize]);
end;

procedure PlasticArray.Remove(const Value: T);
var
   Index: Cardinal;
begin
   if (Assigned(FData) and (FData^.FUsedSize > 0)) then
   begin
      Index := FData^.FUsedSize;
      repeat
         Dec(Index);
         if (Utils.Equals(FData^.FArray[Index], Value)) then
         begin
            RemoveAt(Index);
            exit;
         end;
      until Index = 0;
   end;
end;

procedure PlasticArray.RemoveAll(const Value: T);
var
   ReadIndex, WriteIndex: Cardinal;
begin
   if (Assigned(FData) and (FData^.FUsedSize > 0)) then
   begin
      ReadIndex := 0;
      WriteIndex := 0;
      while (ReadIndex < FData^.FUsedSize) do
      begin
         if (not Utils.Equals(FData^.FArray[ReadIndex], Value)) then
         begin
            // we're keeping this one, shift it down if we've removed something else
            if (WriteIndex <> ReadIndex) then
               FData^.FArray[WriteIndex] := FData^.FArray[ReadIndex];
            Inc(WriteIndex);
         end
         else
         begin
            // we're ditching this one
            EnsureUnique(); // we're going to be changing something eventually, so apply copy-on-write semantics
         end;
         Inc(ReadIndex);
      end;
      Assert((WriteIndex = FData^.FUsedSize) or (FData^.FReferenceCount = 1));
      if (WriteIndex < FData^.FUsedSize) then
      begin
         Assert(ReadIndex = FData^.FUsedSize);
         FData^.FUsedSize := WriteIndex;
         while (WriteIndex < ReadIndex) do
         begin
            Finalize(FData^.FArray[WriteIndex]);
            Inc(WriteIndex);
         end;
      end;
   end;
end;

procedure PlasticArray.RemoveAllTrailing(const Value: T);
begin
   if (Assigned(FData)) then
   begin
      while (FData^.FUsedSize > 0) do
      begin
         if (not Utils.Equals(FData^.FArray[FData^.FUsedSize - 1], Value)) then // $R-
            exit;
         EnsureUnique();
         Dec(FData^.FUsedSize);
         Finalize(FData^.FArray[FData^.FUsedSize]);
      end;
   end;
end;

procedure PlasticArray.Replace(const Value: T; const NewValue: T);
var
   Index: Cardinal;
begin
   if (Assigned(FData)) then
   begin
      Index := FData^.FUsedSize;
      while (Index > 0) do
      begin
         Dec(Index);
         if (Utils.Equals(FData^.FArray[Index], Value)) then
         begin
            EnsureUnique();
            FData^.FArray[Index] := NewValue;
            exit;
         end;
      end;
   end;
end;

function PlasticArray.Contains(const Value: T): Boolean;
var
   Index: Cardinal;
begin
   if (Assigned(FData) and (FData^.FUsedSize > 0)) then
   begin
      for Index := FData^.FUsedSize - 1 downto 0 do // $R-
         if (Utils.Equals(FData^.FArray[Index], Value)) then
         begin
            Result := True;
            exit;
         end;
   end;
   Result := False;
end;

function PlasticArray.Contains(const Value: T; out IndexResult: Cardinal): Boolean;
var
   Index: Cardinal;
begin
   if (Assigned(FData) and (FData^.FUsedSize > 0)) then
   begin
      for Index := FData^.FUsedSize - 1 downto 0 do // $R-
         if (Utils.Equals(FData^.FArray[Index], Value)) then
         begin
            Result := True;
            IndexResult := Index;
            exit;
         end;
   end;
   Result := False;
   {$IFOPT C+} IndexResult := High(IndexResult); {$ENDIF}
end;

procedure PlasticArray.RemoveShiftLeftInsert(const RemoveIndex, InsertIndex: Cardinal; NewValue: T);
var
   Index: Cardinal;
begin
   Assert(Assigned(FData));
   Assert(RemoveIndex <= InsertIndex);
   Assert(InsertIndex < FData^.FUsedSize);
   Assert(FData^.FAllocatedSize >= FData^.FUsedSize);
   if (InsertIndex > RemoveIndex) then
      for Index := RemoveIndex to InsertIndex - 1 do // $R-
         FData^.FArray[Index] := FData^.FArray[Index + 1];
   FData^.FArray[InsertIndex] := NewValue;
end;

function PlasticArray.Distill(): TArray;
var
   Index: Cardinal;
begin
   if (Assigned(FData) and (FData^.FUsedSize > 0)) then
   begin
      SetLength(Result, FData^.FUsedSize); // {BOGUS Warning: Function result variable of a managed type does not seem to be initialized}
      for Index := 0 to FData^.FUsedSize - 1 do // $R-
         Result[Index] := FData^.FArray[Index]; // we don't just blindly copy bytes because the data might itself be of a managed type
      DecRefCount();
      FData := nil;
   end
   else
      Result := nil;
end;

function PlasticArray.Copy(): TArray;
var
   Index: Cardinal;
begin
   if (Assigned(FData) and (FData^.FUsedSize > 0)) then
   begin
      SetLength(Result, FData^.FUsedSize); // {BOGUS Warning: Function result variable of a managed type does not seem to be initialized}
      for Index := 0 to FData^.FUsedSize - 1 do // $R-
         Result[Index] := FData^.FArray[Index]; // we don't just blindly copy bytes because the data might itself be of a managed type
   end
   else
      Result := nil;
end;

procedure PlasticArray.SortSubrange(L, R: Integer; const CompareFunc: TCompareFunc);
var
   I, J : Integer;
   P, Q : T;
begin
   Assert(Assigned(FData));
   Assert(L >= 0);
   Assert(L < FData^.FUsedSize);
   Assert(R >= 0);
   Assert(R < FData^.FUsedSize);
   Assert(L < R);
   // based on QuickSort in rtl/objpas/classes/lists.inc
   repeat
      I := L;
      J := R;
      P := FData^.FArray[(L + R) div 2];
      repeat
         while (CompareFunc(P, FData^.FArray[I]) > 0) do
            I := I + 1; // $R-
         while (CompareFunc(P, FData^.FArray[J]) < 0) do
            J := J - 1; // $R-
         if (I <= J) then
         begin
            Q := FData^.FArray[I];
            FData^.FArray[I] := FData^.FArray[J];
            FData^.FArray[J] := Q;
            I := I + 1; // $R-
            J := J - 1; // $R-
         end;
      until I > J;
      if (L < J) then
         SortSubrange(L, J, CompareFunc);
      L := I;
   until I >= R;
end;

procedure PlasticArray.Sort(const CompareFunc: TCompareFunc);
begin
   if (Assigned(FData) and (FData^.FUsedSize > 1)) then
   begin
      Assert(FData^.FUsedSize < High(Integer));
      SortSubrange(0, FData^.FUsedSize-1, CompareFunc); // $R-
   end;
end;

procedure PlasticArray.SortSubrange(L, R: Integer);
var
   I, J : Integer;
   P, Q : T;
begin
   Assert(Assigned(FData));
   Assert(L >= 0);
   Assert(L < FData^.FUsedSize);
   Assert(R >= 0);
   Assert(R < FData^.FUsedSize);
   Assert(L < R);
   // based on QuickSort in rtl/objpas/classes/lists.inc
   repeat
      I := L;
      J := R;
      P := FData^.FArray[(L + R) div 2];
      repeat
         while (Utils.GreaterThan(P, FData^.FArray[I])) do
            I := I + 1; // $R-
         while (Utils.LessThan(P, FData^.FArray[J])) do
            J := J - 1; // $R-
         if (I <= J) then
         begin
            Q := FData^.FArray[I];
            FData^.FArray[I] := FData^.FArray[J];
            FData^.FArray[J] := Q;
            I := I + 1; // $R-
            J := J - 1; // $R-
         end;
      until I > J;
      if (L < J) then
         SortSubrange(L, J);
      L := I;
   until I >= R;
end;

procedure PlasticArray.Sort();
begin
   if (Assigned(FData) and (FData^.FUsedSize > 1)) then
   begin
      Assert(FData^.FUsedSize < High(Integer));
      SortSubrange(0, FData^.FUsedSize-1); // $R-
   end;
end;

procedure PlasticArray.Shuffle();
begin
   if (Assigned(FData) and (FData^.FUsedSize > 0)) then
   begin
      FisherYatesShuffle(FData^.FArray[0], FData^.FUsedSize, SizeOf(T)); // $R-
   end;
end;

function PlasticArray.Find(Target: T): Cardinal;

   function Search(const I: Integer): Int64;
   begin
      Result := Utils.Compare(FData^.FArray[I], Target);
   end;
   
begin
   if (not Assigned(FData) or (FData^.FUsedSize = 0)) then
   begin
      Result := 0;
      exit;
   end;
   Result := BinarySearch(0, FData^.FUsedSize, @Search); // $R-
end;


constructor PlasticArray.TEnumerator.Create(const Target: PPlasticArray);
begin
   Assert(Assigned(Target));
   FTarget := Target;
   FIndex := 0;
end;

function PlasticArray.TEnumerator.GetCurrent(): T;
begin
   Assert(FIndex > 0);
   Result := FTarget^[FIndex-1]; // $R-
end;

function PlasticArray.TEnumerator.MoveNext(): Boolean;
begin
   Result := FIndex < FTarget^.Length;
   Inc(FIndex);
end;

function PlasticArray.GetEnumerator(): TEnumerator;
begin
   Result := TEnumerator.Create(@Self);
end;


constructor PlasticArray.TFilteredEnumerator.Create(const Target: PPlasticArray; const Filter: T);
begin
   Assert(Assigned(Target));
   FTarget := Target;
   FIndex := 0;
   FFilter := Filter;
end;

function PlasticArray.TFilteredEnumerator.GetCurrent(): T;
begin
   Assert(FIndex > 0);
   Result := FTarget^[FIndex-1]; // $R-
end;

function PlasticArray.TFilteredEnumerator.MoveNext(): Boolean;
begin
   repeat
      Inc(FIndex);
   until (FIndex > FTarget^.Length) or (not Utils.Equals(FTarget^[FIndex - 1], FFilter)); // $R-
   Result := FIndex <= FTarget^.Length;
end;

function PlasticArray.TFilteredEnumerator.GetEnumerator(): TFilteredEnumerator;
begin
   Result := Self;
end;

function PlasticArray.Without(const Value: T): TFilteredEnumerator;
begin
   Result := TFilteredEnumerator.Create(@Self, Value);
end;


procedure PlasticArray.TReadOnlyView.Init(AArray: PPlasticArray);
begin
   Assert(Assigned(AArray));
   FArray := AArray;
end;

function PlasticArray.TReadOnlyView.GetFilledLength(): Cardinal;
begin
   Result := FArray^.Length;
end;

function PlasticArray.TReadOnlyView.GetItem(Index: Cardinal): T;
begin
   Result := FArray^[Index];
end;

function PlasticArray.TReadOnlyView.GetLast(): T;
begin
   Result := FArray^.GetLast();
end;

function PlasticArray.TReadOnlyView.GetEnumerator(): TEnumerator;
begin
   Result := FArray^.GetEnumerator();
end;

function PlasticArray.GetReadOnlyView(): PlasticArray.TReadOnlyView;
begin
   Result.Init(@Self);
end;

{$IFDEF TESTS}
{$PUSH}
{$INCLUDE plasticarrays.tests.inc}
{$POP}
initialization
   RunTests();
{$ENDIF}
end.