Skip to content

TOrderedSet

Jump to bottom
Ivan Semenkov edited this page Feb 7, 2021 · 2 revisions

Table of contents

About

TOrderedSet is a set stores a collection of values. Each value can only exist once in the set.

uses
  container.orderedset, utils.functor;
  
type
  generic TOrderedSet<T, BinaryCompareFunctor> = class

BinaryCompareFunctor is based on utils.functor.TBinaryFunctor interface and used to compare two items.

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 EValueNotExistsException is thrown.

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

Create

A new ordered set can be created by call its constructor.

constructor Create (HashFunc : THashOrderedSetFunc);

HashFunc is a function that generate a hash key for a TOrderedSet value.

Hash functions

Unit container.orderedset contains next hash functions:

function HashPointer(location : Pointer) : Cardinal;

Generate a hash key for a pointer. The value pointed at by the pointer is not used, only the pointer itself.

function HashInteger(location : Integer) : Cardinal;

Generate a hash key for an integer. The value is used to generate the key.

function HashString(location : String) : Cardinal;

Generate a hash key from a string. This is the djb2 string hash function.

function HashStringNoCase(location : String) : Cardinal;

Generate a hash key from a string, ignoring the case of letters. This is the djb2 string hash function.

Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  
  FreeAndNil(intSet);
end;

Insert

Add a value to a set.

function Insert (Value : T) : Boolean;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  intSet.Insert(24);
  
  FreeAndNil(intSet);
end;

Remove

Remove a value from a set.

function Remove (Value : T) : Boolean;

Return true if the request was successful, false if it was not possible to find the value.

Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  intSet.Remove(24);
  
  FreeAndNil(intSet);
end;

HasValue

Return true if a particular value is in a set.

function HasValue (Value : V) : Boolean;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  if intSet.HasValue(3) then
    ;
  
  FreeAndNil(intSet);
end;

NumEntries

Retrieve the number of entries in a set.

function NumEntries : Cardinal;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  writeln(intSet.NumEntries);
    
  FreeAndNil(intSet);
end;

IsEmpty

Return true if container is empty.

function IsEmpty : Boolean;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  if intSet.IsEmpty then
    ;
    
  FreeAndNil(intSet);
end;

Union

Perform a union of two sets. A new set containing all values which are in the first or second sets, or empty set if it was not possible to allocate memory for the new set.

function Union (OrderedSet : {$IFDEF FPC}specialize{$ENDIF} TOrderedSet<T, 
      BinaryCompareFunctor>) : {$IFDEF FPC}specialize{$ENDIF} TOrderedSet<T, 
      BinaryCompareFunctor>;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet1, intSet2, intSet : TIntegerOrderedSet;
  
begin
  intSet1 := TIntegerOrderedSet.Create(@HashInteger);
  intSet2 := TIntegerOrderedSet.Create(@HashInteger);
  
  intSet := intSet1.Union(intSet2);
  
  FreeAndNil(intSet);
end;

Intersection

Perform an intersection of two sets. A new set containing all values which are in both set, or empty set if it was not possible to allocate memory for the new set.

function Intersection (OrderedSet : {$IFDEF FPC}specialize{$ENDIF} 
      TOrderedSet<T, BinaryCompareFunctor>) : {$IFDEF FPC}specialize{$ENDIF} 
      TOrderedSet<T, BinaryCompareFunctor>;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet1, intSet2, intSet : TIntegerOrderedSet;
  
begin
  intSet1 := TIntegerOrderedSet.Create(@HashInteger);
  intSet2 := TIntegerOrderedSet.Create(@HashInteger);
  
  intSet := intSet1.Intersection(intSet2);
  
  FreeAndNil(intSet);
end;

Iterate

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

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

TForwardIterator is a abstract class which provide interface for iterable object that can moves to forward side.

Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  iterator : TIntegerOrderedSet.TIterator;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  for iterator in inSet do
    ;
  
  FreeAndNil(intSet);
end;

FirstEntry

Retrive the iterator for first entry in an ordered set.

function FirstEntry : TIterator;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  iterator : TIntegerOrderedSet.TIterator;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  iterator := intSet.FirstEntry;
  
  FreeAndNil(intSet);
end;

TIterator

HasValue

Return true if iterator has correct value.

function HasValue : Boolean;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  iterator : TIntegerOrderedSet.TIterator;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  iterator := intSet.FirstEntry;
  while iterator.HasValue do
  begin
  
  	iterator := iterator.Next;
  end;
  
  FreeAndNil(intSet);
end;

Next

Retrieve the iterator for next entry in an array list.

function Next : TIterator;
Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  iterator : TIntegerOrderedSet.TIterator;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  iterator := intSet.FirstEntry;
  while iterator.HasValue do
  begin
  
  	iterator := iterator.Next;
  end;
  
  FreeAndNil(intSet);
end;

Value

To get value use Value property.

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

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

Example
uses
  container.orderedset, utils.functor;
  
type
  TIntegerOrderedSet = {$IFDEF FPC}type specialize{$ENDIF} TOrderedSet<Integer, TCompareFunctorInteger>;

var
  intSet : TIntegerOrderedSet;
  iterator : TIntegerOrderedSet.TIterator;
  
begin
  intSet := TIntegerOrderedSet.Create(@HashInteger);
  iterator := intSet.FirstEntry;
  while iterator.HasValue do
  begin
  	writeln(iterator.Value);
  	iterator := iterator.Next;
  end;
  
  FreeAndNil(intSet);
end;
Clone this wiki locally