Archivi delle etichette: delphi

Puntatori alberi e ricorsività parte ][

Rieccomi 🙂 con la seconda parte dei miei mini articoli su Delphi. I simpatizzanti della mela morsicata mi perdoneranno per aver usato ][ al posto del numero 2, ma il mio primo computer è stato un Apple ][ e la tentazione è stata troppo grande 🙂
La prima puntata della saga è qui. Partendo dal primo articolo ho pensato di aggiungere l’implementazione di un design pattern, il singleton.
Lo scopo del singleton, che è un design pattern creazionale, è quello di garantire la creazione di una sola istanza di una particolare classe. Il link a wikipedia è qui. Nell’esempio precedente il singleton potrebbe esserci utile perché pensando alla nostra classe StandardTreeGest in un contesto più ampio, quindi come parte di un progetto più complesso scritto da molti programmatori, ci troveremmo a doverla istanziare in più punti. Certo potremmo dichiarare una bella variabile globale 🙂 (male… molto male chi lo ha pensato?) ma questa non ci garantirebbe dall’instanziarla più volte e quindi poi trovarci con una struttura dati inconsistente e con anomalie molto molto “stravaganti”.

Cercando in giro non ho trovato molti esempi di singleton in Delphi. I primi risultati della mia ricerca sono stati:

questo che però è stato risolto usando un’interfaccia e dove si elogiava una soluzione C# definendola elegante… Delphi si basa sul Pascal, ma non è un linguaggio vecchio 🙂 abbiamo anche i tipi generici da Delphi 2009
– Altra soluzione è questa (per Delphi 5) ma utilizza un singleton “strano”… con una tecnica di reference count.

Avendo comprato un bel libro sui design pattern (da non leggere la sera 🙂 specialmente dopo una pizza ai 4 formaggi) ho voluto fare (o almeno ci ho provato) il “preciso” copiando il codice C++

#include <iostream>
 
#define null 0
 
class singleton {
  private:
    static singleton* instance_ptr;

  protected:
    singleton() { };

  public:
    ~singleton() {};
    static singleton* get_instance() {
      if (instance_ptr == null) {
        instance_ptr = new singleton;
      }
      return instance_ptr;
    }
};
 
// initialize pointer
singleton* singleton::instance_ptr = null;

Che in Delphi verrà scritto invece così:

  Singleton = class
    strict private
      // Singleton
      class var
        pInstance: Singleton;

    strict protected
      constructor Create; virtual;

    public
      destructor Destroy; override;
      class function getInstance: StandardTreeGest;
  end;

Ok descriviamo il codice Delphi. Per prima la bellissima parola chiave strict che serve a rendere veramente privati e protetti i dati membro… perché le parole private e protected non valgono per classi all’interno della stessa unit. Tanto per intenderci potete vedere questo codice sorgente che ho copiato da Stack Overflow:

type
  TFather = class
  private
    FPriv : integer;
  strict private
    FStrPriv : integer;
  protected
    FProt : integer;
  strict protected
    FStrProt : integer;
  public
    FPublic : integer;
  end;

  TSon = class(TFather)
  public
    procedure DoStuff;
  end;

  TUnrelated = class
  public
    procedure DoStuff;
  end;

procedure TSon.DoStuff;
begin
  FProt := 10;       // Legal, as it should be. Accessible to descendants.
  FPriv := 100;      // Legal, even though private. This won't work from another unit!
  FStrictPriv := 10; // <- Compiler Error, FStrictPrivFather is private to TFather
  FPublic := 100;    // Legal, naturally. Public members are accessible from everywhere.
end;

procedure TUnrelated.DoStuff;
var
  F : TFather;
begin
  F := TFather.Create;
  try
    F.FProt := 10;     // Legal, but it shouldn't be!
    F.FStrProt := 100; // <- Compiler error, the strict keyword has "made the protection work"
    F.FPublic := 100;  // Legal, naturally.
  finally
    F.Free;
  end;
end;

Qui si parla di un bug del compilatore… ma nell’help ufficiale è una features 🙂 ovviamente!!!
Poi incontriamo un’altra parolina magica class var questa ci permette di definire dei dati membro statici, infatti per il singleton sia il dato membro che la funzione di istanziazione della classe devono essere statici (per poter essere richiamati senza istanziare una classe, ma dico una cosa ovvia vero…?).

La Unit TreeGest del nostro esempio risulterà quindi essere questa:

unit TreeGest;

interface

type
  pElement = ^Element;

  Element = record
    iValue: integer;
    pLeftElement, pRightElement: pElement;
  end;

  StandardTreeGest = class
    strict private
      // Singleton
      class var
        pInstance: StandardTreeGest;

    strict protected
      constructor Create; virtual;

    private
      // Tree managment
      pRoot: pElement;

      function CreateNewElem(ext_iValue: integer): pElement;
      function InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
      function ReadFromMinimum(pCurrElem: pElement): string;

      procedure DeleteAll_From(pCurrElem: pElement);

    public
      function AddElement(ext_iValue: integer): pElement;
      function SortAscending: string;

      procedure DeleteAll;

      destructor Destroy; override;

      // Singleton
      class function getInstance: StandardTreeGest;
  end;

implementation

{ StandardTreeGest }

uses
  System.SysUtils;

constructor StandardTreeGest.Create;
begin
  pRoot := nil;
end;

destructor StandardTreeGest.Destroy;
begin
  if assigned(pRoot) then
    DeleteAll;
end;

class function StandardTreeGest.getInstance: StandardTreeGest;
begin
  if (pInstance = nil) then
    pInstance := StandardTreeGest.Create;

  result := pInstance;
end;

procedure StandardTreeGest.DeleteAll;
begin
  DeleteAll_From(pRoot);
  pRoot := nil;
end;

procedure StandardTreeGest.DeleteAll_From(pCurrElem: pElement);
begin
  if pCurrElem <> nil then
  begin
    DeleteAll_From(pCurrElem.pLeftElement);
    DeleteAll_From(pCurrElem.pRightElement);
    Dispose(pCurrElem);
  end
end;

function StandardTreeGest.AddElement(ext_iValue: integer): pElement;
var
  pAddedElement: pElement;

begin
  if pRoot = nil then
  begin
    pRoot := CreateNewElem(ext_iValue);
    pAddedElement := pRoot;
  end
  else
    pAddedElement := InsertSorted(ext_iValue, pRoot);

  result := pAddedElement;
end;

function StandardTreeGest.CreateNewElem(ext_iValue: integer): pElement;
var
  pNewElement: pElement;
begin
  try
    new(pNewElement);
    pNewElement.iValue := ext_iValue;
    pNewElement.pLeftElement := nil;
    pNewElement.pRightElement := nil;
  except
    pNewElement := nil;
  end;

  result := pNewElement;
end;

function StandardTreeGest.InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
var
  pResultElem: pElement;

begin
  if (pCurrElem = nil) then
  begin
    pResultElem := CreateNewElem(ext_iValue);
    pCurrElem := pResultElem;
  end
  else
    if (ext_iValue < pCurrElem.iValue) then
      pResultElem := InsertSorted(ext_iValue, pCurrElem.pLeftElement)
    else
      pResultElem := InsertSorted(ext_iValue, pCurrElem.pRightElement);

  result := pResultElem;
end;

function StandardTreeGest.SortAscending: string;
var
  sNode: string;

begin
  sNode := ReadFromMinimum(pRoot);
  if (sNode <> '') then
    result := Copy(sNode, 3, length(sNode) - 2)
  else
    result := '';
end;

function StandardTreeGest.ReadFromMinimum(pCurrElem: pElement): string;
var
  sOrderedTree: string;

begin
  if pCurrElem <> nil then
  begin
    sOrderedTree := ReadFromMinimum(pCurrElem.pLeftElement) + ' - ' + IntToStr(pCurrElem.iValue);
    sOrderedTree := sOrderedTree + ReadFromMinimum(pCurrElem.pRightElement);
  end
  else
    sOrderedTree := '';

  result := sOrderedTree;
end;

end.

Oltre ad aver implementato il singleton rispetto a quella dello scorso post ho aggiunto un blocco try…except al momento dell’allocazione della memoria del nuovo nodo dell’albero. Nel mondo ideale la memoria è illimitata, ma in quello reale finisce sempre sul più bello e la scorsa volta mi sono dimenticato di gestire l’eccezione.
Il programma avrà l’aspetto seguente:

pgm_singleton

Che a parte un bottone in più… è uguale al precedente… che farà il nuovo bottone?

procedure TfrmMain.btnAddElem2Click(Sender: TObject);
var
  pTreeGestLocal: StandardTreeGest;
  iValue, iCode: integer;

begin
  pTreeGestLocal := StandardTreeGest.getInstance;

  Val(txtValue.Text, iValue, iCode);

  if ((trim(txtValue.Text) <> '') and (iCode = 0)) then
  begin
    pTreeGestLocal.AddElement(StrToInt(txtValue.Text));
    txtValue.Clear;
    txtValue.SetFocus;
  end
end;

Semplicemente permette di verificare il singleton, aggiungendo direttamente un elemento all’albero. Notate che uso solo varibili locali e che la getInstance mi restituisce sempre il riferimento all’unica classe StandardTreeGest creata.

Il codice sorgente lo potete scaricare qui.

Alla prossima 🙂

Puntatori, alberi e ricorsività

Rieccomi dopo tanto. Questo è il primo articolo di una piccola serie… facciamo miniserie di 3 o forse 4 puntate veloci.
Qualche tempo fa ho fatto un colloquio per una ditta all’estero, il colloquio prevedeva anche un test pratico. 40 minuti di tempo per creare in Delphi un albero, popolarlo e stamparne gli elementi.
L’albero conteneva numeri, a partire dalla radice i numeri minori del nodo corrente venivano memorizzati nel ramo a sinistra, quelli maggiori del nodo corrente invece nel ramo di destra. La lettura ovviamente doveva restituire gli elementi in maniera ordinata.
Facendo un esempio pratico, dovendo inserire i numeri 10 – 6 – 4 – 3 – 8 -12 avremo avuto un albero come questo:

Tree

Insomma 🙂 il calssico esercizio di teoria sugli alberi, dov’era l’inghippo? Si avevano a disposizione solo 40 minuti! E il tempo vola.

Devo ammettere che il test era proprio ben fatto. Dopo averlo superato ho pensato che in realtà fosse troppo facile, ma non lo era affatto. Per poterlo passare o si conosceva la teoria o non si sarebbe potuto trovare nulla su google da copiare ed incollare. Gli elementi da inserire erano:

– Puntatori
– Gli alberi
– La ricorsione

I puntatori non sono così usati in Delphi e non ho mai capito bene perché sono indicanti da molti sviluppatori come il male di ogni software. Agli albori di Java una delle frasi che mi aveva divertito di più era:
“La gestione della memoria è troppo importante per lasciarla agli sviluppatori. La gestione della memoria è troppo importante per lasciarla al software”.
Chissà chi aveva ragione…

Sugli alberi dipende molto da che software sviluppate, io non li ho più usati dai tempi della scuola… troppo software gestionale 🙂 con le sue query SQL.
Riguardo la ricorsione… siamo quasi come i puntatori; un altro di quegli argomenti amati e odiati, la ricorsione (qui il link a wikipedia) risolve semplicemente alcune tipologie di problemi ma al tempo stesso non è performante.

Tornando a noi, il programmino finale è quello nella figura di seguito:

Il programma

Ok è esteticamente bruttino, ma abbiate pietà, comprensione, umanità un principio di cataratta 🙂 … fare le cornicette di notte non mi entusiasma 🙂 Il suo funzionamento è semplice. Si aggiungono gli elementi alla TListBox premendo il bottone “Add Element” che sposta l’elemento dalla TEdit “value” alla lista, una volta che abbiamo popolato a dovere quest’ultima il bottone “Create tree” genererà l’albero.
Il bottone “Sorted elements” scriverà gli elementi dal più piccolo al più grande 🙂 nel componente TEdit a fianco del bottone.

L’implementazione della classe StandardTreeGest prevederà le funzioni pubbliche:

public
  function AddElement(ext_iValue: integer): pElement;
  function SortAscending: string;

Per aggiungere un elemento e per estrarre la lista degli elementi inseriti in maniera ordinata. Queste 2 funzioni saranno le “interfacce” pubbliche delle seguenti funzioni private:

function InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
function ReadFromMinimum(pCurrElem: pElement): string;

Che opereranno realmente sull’albero. Andando ad evidenziare i punti problematici elencati prima (puntatori, alberi e ricorsione) vediamo che ogni nodo di un albero è formato da 2 puntatori ad altri nodi (uno al ramo sinistro e uno al destro) e dal valore del nodo stesso. Questo in Delphi si dichiara così:

type
  pElement = ^Element;

  Element = record
    iValue: integer;
    pLeftElement, pRightElement: pElement;
  end;

Abbiamo quindi le funzioni pubbliche per l’accesso all’albero che richiameranno quelle private che saranno anche quelle ricorsive.

function StandardTreeGest.AddElement(ext_iValue: integer): pElement;
var
  pAddedElement: pElement;

begin
  if pRoot = nil then
  begin
    pRoot := CreateNewElem(ext_iValue);
    pAddedElement := pRoot;
  end
  else
    pAddedElement := InsertOrdered(ext_iValue, pRoot);

  result := pAddedElement;
end;

function StandardTreeGest.SortAscending: string;
var
  sNode: string;

begin
  sNode := ReadFromMinimum(pRoot);
  if (sNode <> '') then
    result := Copy(sNode, 3, length(sNode) - 2)
  else
    result := '';
end;

Come vedete fanno ben poche cose principalmente legate al controllo del nodo radice dell’albero. Il lavoro vero lo fanno le funzioni private:

function CreateNewElem(ext_iValue: integer): pElement;
function InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
function ReadFromMinimum(pCurrElem: pElement): string;

Con il loro codice sorgente:

function StandardTreeGest.CreateNewElem(ext_iValue: integer): pElement;
var
  pNewElement: pElement;
begin
  new(pNewElement);
  pNewElement.iValue := ext_iValue;
  pNewElement.pLeftElement := nil;
  pNewElement.pRightElement := nil;

  result := pNewElement;
end;

function StandardTreeGest.InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
var
  pResultElem: pElement;

begin
  if (pCurrElem = nil) then
  begin
    pResultElem := CreateNewElem(ext_iValue);
    pCurrElem := pResultElem;
  end
  else
    if (ext_iValue < pCurrElem.iValue) then
      pResultElem := InsertOrdered(ext_iValue, pCurrElem.pLeftElement)
    else
      pResultElem := InsertOrdered(ext_iValue, pCurrElem.pRightElement);

  result := pResultElem;
end;

function StandardTreeGest.ReadFromMinimum(pCurrElem: pElement): string;
var
  sOrderedTree: string;

begin
  if pCurrElem <> nil then
  begin
    sOrderedTree := ReadFromMinimum(pCurrElem.pLeftElement) + ' - ' + IntToStr(pCurrElem.iValue);
    sOrderedTree := sOrderedTree + ReadFromMinimum(pCurrElem.pRightElement);
  end
  else
    sOrderedTree := '';

  result := sOrderedTree;
end;

A parte la CreateNewElem le altre funzioni sono ricorsive cioè richiamano se stesse dal loro interno, questo permette ad esempio alla ReadFromMinimum di leggere tutti i nodi a sinistra e una volta arrivato all’ultimo elemento di “riavvolgersi” su se stessa e passare alla lettura del ramo destro del nodo corrente. Tutto questo perché le chiamate a funzione e le variabili locali in esse contenute vengono memorizzate sullo stack. Da qui la lentezza e la grande occupazione di memoria delle funzioni ricorsive a cui si contrappone la drammatica semplicità del codice scritto.

Volevo richiamare la vostra attenzione sulla creazione di un nuovo record nella funzione CreateNewElem

  new(pNewElement);

avete visto l’istruzione new… mica vorrete lasciarla senza la sua dispose!!! 🙂 I puntatori fanno casini quando ci dimentichiamo di deallocarli o magari li usiamo senza allocarli, ma non sono così cattivi in fondo.
La funzione di “ripulitura” è la DeleteAll richiamata anche da dentro il distruttore della classe StandardTreeGest. Il codice completo di quest’ultima è il seguente:

unit TreeGest;

interface

type
  pElement = ^Element;

  Element = record
    iValue: integer;
    pLeftElement, pRightElement: pElement;
  end;

  StandardTreeGest = class
    private
      pRoot: pElement;

      function CreateNewElem(ext_iValue: integer): pElement;
      function InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
      function ReadFromMinimum(pCurrElem: pElement): string;

      procedure DeleteAll_From(pCurrElem: pElement);

    public
      function AddElement(ext_iValue: integer): pElement;
      function SortAscending: string;

      procedure DeleteAll;

      constructor Create; virtual;
      destructor Destroy; override;

  end;

implementation

{ StandardTreeGest }

uses
  System.SysUtils;

constructor StandardTreeGest.Create;
begin
  pRoot := nil;
end;

destructor StandardTreeGest.Destroy;
begin
  if assigned(pRoot) then
    DeleteAll;
end;

procedure StandardTreeGest.DeleteAll;
begin
  DeleteAll_From(pRoot);
  pRoot := nil;
end;

procedure StandardTreeGest.DeleteAll_From(pCurrElem: pElement);
begin
  if pCurrElem <> nil then
  begin
    DeleteAll_From(pCurrElem.pLeftElement);
    DeleteAll_From(pCurrElem.pRightElement);
    Dispose(pCurrElem);
  end
end;

function StandardTreeGest.AddElement(ext_iValue: integer): pElement;
var
  pAddedElement: pElement;

begin
  if pRoot = nil then
  begin
    pRoot := CreateNewElem(ext_iValue);
    pAddedElement := pRoot;
  end
  else
    pAddedElement := InsertSorted(ext_iValue, pRoot);

  result := pAddedElement;
end;

function StandardTreeGest.CreateNewElem(ext_iValue: integer): pElement;
var
  pNewElement: pElement;
begin
  new(pNewElement);
  pNewElement.iValue := ext_iValue;
  pNewElement.pLeftElement := nil;
  pNewElement.pRightElement := nil;

  result := pNewElement;
end;

function StandardTreeGest.InsertSorted(ext_iValue: integer; var pCurrElem: pElement): pElement;
var
  pResultElem: pElement;

begin
  if (pCurrElem = nil) then
  begin
    pResultElem := CreateNewElem(ext_iValue);
    pCurrElem := pResultElem;
  end
  else
    if (ext_iValue < pCurrElem.iValue) then
      pResultElem := InsertSorted(ext_iValue, pCurrElem.pLeftElement)
    else
      pResultElem := InsertSorted(ext_iValue, pCurrElem.pRightElement);

  result := pResultElem;
end;

function StandardTreeGest.SortAscending: string;
var
  sNode: string;

begin
  sNode := ReadFromMinimum(pRoot);
  if (sNode <> '') then
    result := Copy(sNode, 3, length(sNode) - 2)
  else
    result := '';
end;

function StandardTreeGest.ReadFromMinimum(pCurrElem: pElement): string;
var
  sOrderedTree: string;

begin
  if pCurrElem <> nil then
  begin
    sOrderedTree := ReadFromMinimum(pCurrElem.pLeftElement) + ' - ' + IntToStr(pCurrElem.iValue);
    sOrderedTree := sOrderedTree + ReadFromMinimum(pCurrElem.pRightElement);
  end
  else
    sOrderedTree := '';

  result := sOrderedTree;
end;

end.

Il sorgente di tutto il programma lo trovate qui

Come potete vedere ho creato il costruttore e il distruttore… ho fatto lo stesso anche con la form del main, so che con le form avrei potuto usare l’evento oncreate per fare le mie inizializzazioni ma sono un po “stagionato” 🙂

Concludo questo primo articolo dicendo che le poche righe scritte non sono certo esaustive, gli alberi sono materia complessa se non di più, ma la mia idea è di buttare una pietra nell’acqua e far muovere un po’ le cose. Spiegare quello che so e anche imparare per cui se avete commenti, suggerimenti o correzioni non esitate a scrivere 🙂