Skip to content

TSortedArray

Jump to bottom
Ivan Semenkov edited this page Feb 8, 2021 · 4 revisions

Table of contents

About

The TSortedArray is an automatically resizing array which stores its elements in sorted order. It is based on pascal's dynamic array structure. All operations on a TSortedArray maintain the sorted property. Most operations are done in O(n) time, but searching can be done in O(log n) worst case.

TSortedArray internally stores all data in a safe manner for strings and user-defined data structures.

uses
  container.sortedarray, utils.functor;

type
  generic TSortedArray<T, BinaryCompareFunctor> = class

BinaryCompareFunctor is based on utils.functor.TBinaryFunctor interface and used to compare two array items in sort and search functions.

TOptionalValue

If macro {$USE_OPTIONAL} is defined, then all methods return a TOptionalValue wrapper, otherwise T.

uses
  utils.optional;

type
  TOptionalValue = {$IFDEF FPC}specialize{$ENDIF} TOptional<T>;

For non-existent values, returns a empty TOptionalValue if defined or an EIndexOutOfRangeException is thrown.

type
  {$IFNDEF USE_OPTIONAL}
  EIndexOutOfRangeException = class(Exception);
  {$ENDIF}

Create

A new array can be created by call its constructor. It is also possible to reserve memory for items by the first argument.

constructor Create (ALength : Cardinal = 0);
Example
uses
  container.sortedarray, utils.functor;

type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;

var
  arr : TIntegerArray;

begin
  arr := TIntegerArray.Create;

  FreeAndNil(arr);
end;

Append

Insert a value into a sorted array while maintaining the sorted property.

function Append (AValue : T) : Boolean;
Example
uses
  container.sortedarray, utils.functor;
 
type
  IntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger
 
var
  arr : TIntegerArray;
  
begin
  arr := TIntegerArray.Create;
  
  arr.Append(15);
  arr.Append(-598565101);
  
  FreeAndNil(arr);
end;

Remove

The methods to remove data from the array.

Remove

Remove the entry at the specified location in a TSortedArray. If the item at index doesn't exists, nothing happens.

procedure Remove (AIndex: Cardinal);
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  
begin
  arr := TIntegerArray.Create;
  
  arr.Remove(0);
  arr.Remove(8);
  
  FreeAndNil(arr);
end;

Remove range

Remove a range of entries at the specified location in a TSortedArray. If the items at indexes don't exists, nothing happens.

procedure RemoveRange (AIndex : LongInt; ALength : LongInt);
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  
begin
  arr := TIntegerArray.Create;
  
  arr.RemoveRange(0, 5);
  
  FreeAndNil(arr);
end;

Clear

Remove all entries from a TSortedArray.

procedure Clear;
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  
begin
  arr := TIntegerArray.Create;
  
  arr.Clear;
  
  FreeAndNil(arr);
end;

Search

Find the index of a particular value in a TSortedArray. Return the index of the value if found, or -1 if not found.

function IndexOf (AData : T) : Integer;
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  
begin
  arr := TIntegerArray.Create;
  
  writeln(arr.IndexOf(5));
  
  FreeAndNil(arr);
end;

Values

To get value from a TSortedArray use Value property.

property Value [AIndex : LongInt] : {$IFNDEF USE_OPTIONAL}T{$ELSE}TOptionalValue{$ENDIF};

If index not exists returns empty TOptionalValue or raise EIndexOutOfRangeException.

Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  
begin
  arr := TIntegerArray.Create;
  
  writeln(arr.Value[0]);
  
  FreeAndNil(arr);
end;

Length

Get TSortedArray size.

property Length : LongInt;
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  
begin
  arr := TIntegerArray.Create;
  writeln(arr.Length);
  
  FreeAndNil(arr);
end;

IsEmpty

Return true if container is empty.

function IsEmpty : Boolean;
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  
begin
  arr := TIntegerArray.Create;
 if arr.IsEmpty then
   ;
  
  FreeAndNil(arr);
end;

Iterate

It is possible to iterate for TSortedArray values using in operator. Each value would present as TSortedArray.TIterator object.

uses
  container.sortedarray, utils.functor;
  
type
  generic TSortedArrayList<T, BinaryCompareFunctor> = class
  type
    TIterator = class({$IFDEF FPC}specialize{$ENDIF} TBidirectionalIterator<T, TIterator>)
  end;

TBidirectionalIterator is a abstract class which provide interface for iterable object that can moves to both sides.

Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  iterator : TIntegerArray.TIterator;
  
begin
  arr := TIntegerArray.Create;
  
  for iterator in arr do
    ;
  
  FreeAndNil(arr);
end;

FirstEntry

Retrive the iterator for first entry in an array.

function FirstEntry : TIterator;
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  iterator : TIntegerArray.TIterator;
  
begin
  arr := TIntegerArray.Create;
  
  iterator := arr.FirstEntry;
  
  FreeAndNil(arr);
end;

LastEntry

Retrive the iterator for last entry in an array.

function LastEntry : TIterator;
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  iterator : TIntegerArray.TIterator;
  
begin
  arr := TIntegerArray.Create;
  
  iterator := arr.LastEntry;
  
  FreeAndNil(arr);
end;

TIterator

HasValue

Return true if iterator has correct value.

function HasValue : Boolean;
Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  iterator : TIntegerArray.TIterator;
  
begin
  arr := TIntegerArray.Create;
  
  iterator := arr.FirstEntry;
  while iterator.HasValue do
  begin
  
    iterator := iterator.Next;
  end;
  
  FreeAndNil(arr);
end;
Prev

Retrieve the iterator for previous entry in an array.

Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  iterator : TIntegerArray.TIterator;
  
begin
  arr := TIntegerArray.Create;
  
  iterator := arr.LastEntry;
  while iterator.HasValue do
  begin
  
    iterator := iterator.Prev;
  end;
  
  FreeAndNil(arr);
end;
Next

Retrieve the iterator for next entry in an array.

Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  iterator : TIntegerArray.TIterator;
  
begin
  arr := TIntegerArray.Create;
  
  iterator := arr.FirstEntry;
  while iterator.HasValue do
  begin
  
    iterator := iterator.Next;
  end;
  
  FreeAndNil(arr);
end;
Value

To get value use Value property.

property Value : {$IFNDEF USE_OPTIONAL}T{$ELSE}TOptionalValue{$ENDIF};

If iterator not have correct value returns empty TOptionalValue or raise EIndexOutOfRangeException.

Example
uses
  container.sortedarray, utils.functor;
 
type
  TIntegerArray = {$IFDEF FPC}type specialize{$ENDIF} TSortedArray<Integer, TCompareFunctorInteger>;
 
var
  arr : TIntegerArray;
  iterator : TIntegerArray.TIterator;
  
begin
  arr := TIntegerArray.Create;
  
  iterator := arr.FirstEntry;
  while iterator.HasValue do
  begin
  	writeln(iterator.Value);
    iterator := iterator.Next;
  end;
  
  FreeAndNil(arr);
end;
Clone this wiki locally