Skip to content

TTrie

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

Table of contents

About

A trie is a data structure which provides fast mappings from strings to values.

uses
  container.trie;
  
type
  generic TTrie<V> = class

TOptionalValue

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

uses
  utils.optional;

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

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

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

Create

A new trie can be created by call its constructor.

constructor Create;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  
begin
  trie := TIntegerTrie.Create;
  
  FreeAndNil(trie);
end;

Insert

There are several methods to insert data to the trie.

Insert

Insert a new key-value pair into a trie. The key is a NUL-terminated string. Return true if the value was inserted successfully, or false if it was not possible to append new entry.

function Insert (Key : AnsiString; Value : V) : Boolean;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  
begin
  trie := TIntegerTrie.Create;
  trie.Insert('test', 123);
  
  FreeAndNil(trie);
end;

InsertBinary

Insert a new key-value pair into a trie. The key is a sequence of bytes. Return true if the value was inserted successfully, or false if it was not possible to append new entry.

function InsertBinary (Key : PByte; KeyLength : Integer; Value : V) : Boolean;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  data : array [0 .. 10] of byte;
  
begin
  trie := TIntegerTrie.Create;
  trie.Insert(PByte(@data), 10, 123);
  
  FreeAndNil(trie);
end;

Remove

The methods to remove data from the trie.

Remove

Remove an entry from a trie. Return true if the request was successful, false if it was not possible to find the value.

function Remove (Key : AnsiString) : Boolean;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  
begin
  trie := TIntegerTrie.Create;
  trie.Remove('test');
  
  FreeAndNil(trie);
end;

RemoveBinary

Remove an entry from a trie. The key is a sequence of bytes.

function RemoveBinary (Key : PByte; KeyLength : Integer) : Boolean;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  data : array [0 .. 10] of byte;
  
begin
  trie := TIntegerTrie.Create;
  trie.Remove(PByte(@data), 10);
  
  FreeAndNil(trie);
end;

Search

Search

Look up a value from its key in a trie.

function Search (Key : AnsiString) : {$IFNDEF USE_OPTIONAL}V
  	{$ELSE}TOptionalValue{$ENDIF};

If value not exists returns empty TOptionalValue or raise EKeyNotExistsException.

Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  
begin
  trie := TIntegerTrie.Create;
  writeln(trie.Search('test'));
  
  FreeAndNil(trie);
end;

SearchDefault

Look up a value from its key in a trie. Return default value if Key not exists.

function SearchDefault (Key : AnsiString; ADefault : V) : V;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  
begin
  trie := TIntegerTrie.Create;
  writeln(trie.SearchDefault('test', -1));
  
  FreeAndNil(trie);
end;

SearchBinary

Look up a value from its key in a trie. The key is a sequence of bytes.

function SearchBinary (Key : PByte; KeyLength : Integer) : 
	{$IFNDEF USE_OPTIONAL}V{$ELSE}TOptionalValue{$ENDIF};
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  data : array [0 .. 10] of byte;
  
begin
  trie := TIntegerTrie.Create;
  writeln(trie.SearchBinary(PByte(@data), 10));
  
  FreeAndNil(trie);
end;

SearchBinaryDefault

Look up a value from its key in a trie. The key is a sequence of bytes. Return default value if Key not exists.

function SearchBinaryDefault (Key : PByte; KeyLength : Integer; ADefault :
  V) : V;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  data : array [0 .. 10] of byte;
  
begin
  trie := TIntegerTrie.Create;
  writeln(trie.SearchBinaryDefault(PByte(@data), 10, -1));
  
  FreeAndNil(trie);
end;

NumEntries

Return the number of entries in a trie.

function NumEntries : Cardinal;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  
begin
  trie := TIntegerTrie.Create;
  writeln(trie.NumEntries);
  
  FreeAndNil(trie);
end;

IsEmpty

Return true if container is empty.

function IsEmpty : Boolean;
Example
uses
  container.trie;
  
type
  TIntegerTrie = {$IFDEF FPC}type specialize{$ENDIF} TTrie<Integer>;

var
  trie : TIntegerTrie;
  
begin
  trie := TIntegerTrie.Create;
  if trie.IsEmpty then
    ;
  
  FreeAndNil(trie);
end;
Clone this wiki locally