PHP: una classe per il calcolo di matrici di distanze euclidee, cityblock e Minkowski

EuclideSono diversi gli ambiti nei quali può essere necessario raggruppare elementi di un certo insieme in base a differenze registrate attraverso misure sul campo. In questi casi per la determinazione dell’entità delle differenze, viene usata la distanza che può essere considerata al di là del suo significato metrico, una misura della diversità. I campi di applicazione possono essere i più disparati: dagli aspetti biologici come per esempio differenze genotipiche o fenotipiche di individui o popolazioni, agli aspetti socio-economici come redditi, produttività o consumo.
Non tutte le variabili, però, possono essere trattate allo stesso modo. Solo le variabili che vengono definite “ad intervallo”, possono essere utilizzate per calcolare distanze di tipo metrico come le distanze euclidee, city-block (o Manhattan) e di Minkowski. Parliamo quindi di variabili quantitative. Negli altri casi, a seconda del tipo di variabile utilizzato (dicotomiche, categoriali, ecc) le differenze possono essere comunque calcolate mediante l’utilizzo di distanze non metriche o ultra-metriche.
A questo punto è bene definire cosa sono le distanze metriche. Sono quelle che rispettano i seguenti enunciati:

  • la distanza tra due punti che non coincidono deve essere positiva;
  • la distanza tra due punti che coincidono è pari a 0;
  • la distanza tra due punti deve essere simmetrica (d AB = d BA),

e non contravvengono la proprietà della disuguaglianza triangolare, cioè dati tre punti A, B e C deve essere verificata la condizione che:
d AB < d AC + d BC
riassumendo, si può dire che sono quelle che seguono la metrica pitagorica.

Fatta questa doverosa premessa, passiamo ad analizzare le formule delle distanze metriche utilizzate
nella classe PHP.

Distanze Euclidee

E’ senza dubbio il tipo di distanza più diffuso. La formula per il calcolo deriva dalla formula della distanza fra 2 punti in un piano cartesiano e può essere espressa come:

Formula per il calcolo delle distanze euclidee

in cui xik e xjk sono le misure in posizione i e j rispettivamente della k-esima di n variabili.

Distanze city-block (Manhattan)

Viene anche detta distanza assoluta o della metrica del taxi. La sua formula è:

Formula per il calcolo delle distanze city-block

La particolarità di questa formula sta nel fatto che, considerando la distanza euclidea fra 2 punti A e C di un triangolo ABC, e che questa distanza può essere espressa come la radice quadrata della somma dei quadrati costruiti sui cateti del triangolo ABC, la distanza di city-block è la somma dei cateti di questo triangolo. Il concetto risulta forse più chiaro osservando la figura qui sotto.

Triangolo di esempio

Non a caso, il nome Manhattan deriva proprio dalla particolare disposizione delle strade del famoso quartiere di New York, che si incrociano ad angolo retto, formando una sorta di scacchiera. In effetti questo tipo di distanza, ben si presta a rappresentare il percorso reale fra due punti che si trovano in prossimità degli angoli opposti di un palazzo (…o grattacielo!)

Distanze di Minkowski

Rappresenta la forma più generalizzata di distanza metrica. La sua formula è:

Formula per il calcolo delle di minkowski

Si dice di ordine p, e in particolare quando p=1, coincide con la distanza city-block,
e quando p=2, coincide con la distanza euclidea, come si evince dalla formula. Per p -> infinito coincide con la distanza di Lagrange o di Chebychev.

La classe PHP che ho preparato permette di calcolare, scegliendo una delle distanze illustrate sopra, una matrice triangolare (nella quale la diagonale assume valori = 0) di confronto fra tutti i campioni passati in input. La matrice dati da passare come parametro al costruttore deve avere questo formato:

1
2
3
4
5
6
7
8
9
10
11
12
$dataTest = array (
                "sample01" => array(82.897,488,0.6381,8.576),
                "sample02" => array(37.04,512,0.7935,7.9293),
                "sample03" => array(86.571,617,0.1518,0.9705),
                "sample04" => array(76.038,876,0.0883,5.5867),
                "sample05" => array(67.726,687,0.9145,9.2478),
                "sample06" => array(34.407,979,0.8148,3.8348),
                "sample07" => array(52.258,462,0.7132,3.716),
                "sample08" => array(75.141,652,0.8453,8.3466),
                "sample09" => array(17.546,322,0.0483,1.5812),
                "sample10" => array(35.786,502,0.6899,3.1447)
                );

Ed ecco dunque il codice PHP della classe:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class DistanceMatrix
{
 var $dataArray = null;
 var $dataSize = 0;
 var $dataVectSize = 0;
 
 function DistanceMatrix($data)
 {
  $this->dataArray = array();
  $this->dataArray = $data;
  $this->checkData();
 }
 
 function checkData()
 {
  $this->dataSize = count($this->dataArray);
  if($this->dataSize < 2){
   die("Cannot proceed: only one sample, or missing data");
  }
  reset ($this->dataArray);
  $this->dataVectSize = count(current($this->dataArray));
  foreach ($this->dataArray as $key => $vectData){
   $vectSize = count($vectData);
   if ($vectSize != $this->dataVectSize){
    die("Cannot proceed: different size vectors!");
   }
  }
 }
 
 function euclidean ($vect1,$vect2)
 {
  $qdist = 0.0;
  for($i=0;$i< $this->dataVectSize;$i++){
   $qdist += pow($vect1[$i]-$vect2[$i],2);
  }
  return sqrt($qdist);
 }
 
 function manhattan ($vect1,$vect2)
 {
  $dist = 0.0;
  for($i=0;$i< $this->dataVectSize;$i++){
   $dist += abs($vect1[$i]-$vect2[$i]);
  }
  return $dist;
 }
 
 function minkowski($vect1,$vect2,$exp) {
  $edist = 0.0;
  for($i=0; $i< $this->dataVectSize; $i++){
   $edist += pow(abs($vect1[$i]-$vect2[$i]), $exp);
  }
  return pow($edist, 1/$exp);
 }
 
 function printData($distType,$exp=1)
 {
  if (!method_exists($this,$distType)) {
   die ("Sorry, can't find $distType method!");
  }
  echo ("<h1>Matrix of $distType distances </h1>\n");
  echo ("<table class='datatable' summary='Results'>\n");
  echo ("<thead><tr>");
  echo ("<th>&nbsp;</th>");
  foreach ($this->dataArray as $key=>$data){
   echo ("<th>".$key."</th>");
  }
  echo ("</tr></thead><tbody>\n");
  foreach ($this->dataArray as $keyA=>$dataA){
   echo ("<tr>");
   echo ("<td><strong>".$keyA."</strong></td>");
   foreach ($this->dataArray as $keyB=>$dataB){
    if ($distType=="minkowski"){
     printf("<td>%.4f</td>",$this->minkowski($dataA,$dataB,$exp));
    }
    else{
     printf("<td>%.4f</td>",$this->$distType($dataA,$dataB));
    }
   }
   echo ("</tr>\n");
  }
  echo ("</tbody></table>\n");
 }
}

Demo:

In questa pagina è visibile una demo della classe con dei campioni ipotetici e delle variabili di test.

Download

Il download della classe completa del file di esempio è disponibile qui.

Conclusioni:

La naturale conclusione della produzione di una matrice di distanze è l’elaborazione di una cluster analisys. Questo metodo permette di leggere visivamente i raggruppamenti dovuti alle similarità o diseguaglianze indicate dalle distanze calcolate. Tali raggruppamenti potranno essere espressi in forma gerarchica. Un software distribuito con licenza GNU che permette queste elaborazioni, e che suggerisco
è Cluster 3.0, disponibile per Linux, Windows e MacOSX.

Riferimenti ed approfondimenti:

P4A3 framework: il widget Countdown rinnovato e con funzione timer

Widget p4a CountdownQuesto widget per il framework P4A è l’aggiornamento di quello descritto in questo post.
L’aggiornamento deriva dal fatto che la nuova versione del codice originale per jQuery, presenta cambiamenti importanti e ha richiesto la riscrittura di una buona parte del widget. La versione del Countdown for jQuery attualmente installata è la 1.4.3.

Ho pensato di cogliere l’occasione per rendere un poco più interattivo il widget, facendo scattare un evento gestibile dall’utente attraverso un metodo personalizzato, allo scadere del contatempo. Inoltre, ho utilizzato l’integrazione di P4A con i18n, per impostare automaticamente la lingua per gli output delle etichette e il formato della data e dell’ora.

Questo è l’elenco dei metodi fino ad esso implementati:

Elenco dei metodi:
NomeTipoDefaultNote
setSince()integer"null"Imposta la data e l’ora di avvio in formato UNIX timestamp
setUntil()integer"null"Imposta la data e l’ora di stop in formato UNIX timestamp.
setDisplayFormat()string"dHMS"‘Y’ anni, ‘O’ mesi, ‘W’ settimane, ‘D’ giorni, ‘H’ ore, ‘M’ minuti, ‘S’ secondi. I caratteri minuscoli impostano la visualizzazione opzionale
setCompactFormat()string"false"Imposta il formato ridotto.
setDescription()string""Imposta la descrizione del contatempo.
setServerTime()stringnullImposta l’offset per il fuso orario. Valori di esempio: ‘+1’, ‘+2’, ‘+3’, ‘-1’, ‘-2’, ‘-3’. etc.
setLayout()string''Imposta un layout personalizzabile attraverso tag HTML e parametri per esprimere la data e l’ora.
Le singole sezioni sono delimitate da %x…%x, dove x è ‘Y’ per definire gli anni, ‘O’ per i mesi,
‘W’ per le settimane, e ‘D’ per i giorni, ‘H’ per le ore, ‘M’ per i minuti, e ‘S’ per i secondi.
All’interno di queste sezioni, è possibile utilizzare ‘%n’ per determinare il valore del periodo,
‘%nn’ per il valore con un minimo di due caratteri, e ‘%l’ per l’etichetta del periodo (in accordo
con quanto impostato in setCompactFormat()).
setlocale()string'auto'Imposta un valore per la regionalizzazione. Per default viene presa l’impostazione di P4A_LOCALE.
In alternativa è possibile impostarla manualmente. Le traduzioni disponibili sono:
Chinese – Simplified “zh-CN”, Chinese – Traditional “zh-TW”, Czech “cs”, Danish “da”, Dutch “nl”, French “fr”, German “de”, Hebrew “he”, Hungarian “hu”, Indonesian “id”, Italian “it”, Norwegian “nb”, Persian/Farsi “fa”, Polish “pl”, Portuguese/Brazilian “pt-BR”, Romanian “ro”, Russian “ru”, Slovak “sk”, Spanish “es”, Swedish “sv”, Turkish “tr”, Ukranian “uk”
setPauseResumeType()stringnullSe impostato con i valori: “lap” o “pause” mostra un pulsante che ferma o riavvia il contatempo.
“lap” ferma solo la visualizzazione, “pause” ferma anche il conteggio. Se null il pulsante non viene mostrato.
setPauseResumeLabels()string'pause,resume'Imposta le etichette per il pulsante “Pause/resume”. I valori per l’azione toggle devono essere separati da una virgola.
onExpiry()booleanfalseImposta se deve scattare un evento allo scadere del countdown (funziona solo quando è impostato setUntil()).
setMessageOnExpire()string""Imposta il testo del messaggio che viene visualizzato allo scadere del countdown.
messageOnExpire()voidvoidSe è impostato un messaggio, lo mostra e restituisce un handle per l’evento actionOnExpire.
Questo metodo viene attivato quando onExpiry(true)

Ecco un po’ di codice di esempio per inserire il contatempo in una maschera e utilizzare l’evento actionOnExpire:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class test_countdown extends p4a_base_mask
{
 public function __construct()
 {
   parent::__construct();
   $this->setTitle("test Countdown");
   $this->build("P4A_jCountdown", "countdown")
    ->setStyleProperty("width","400px")
    ->setStyleProperty("float","none")
    ->setStyleProperty("margin","auto")    
    ->setDescription("test countdown")
    ->countdown->setUntil(time()+11)
    ->countdown->onExpiry(true)
    ->countdown->setMessageOnExpire("Il tempo e' scaduto!");
 
    $this->countdown->implement('actionOnExpire',$this,'show');
 
    $this->frame->anchorCenter($this->countdown);
  }
 
	public function show ()
	{
		$this->info("Questa e' una prova!");
		//Enable code below for looping
		//$this->countdown->setUntil(time()+11);
	}
 
}

Il pacchetto completo della maschera di esempio è scaricabile qui

Note:

L’impostazione di setLocale() non è in genere necessaria per il fatto che quando viene “costruito” il contatempo la regionalizzazione viene individuata automaticamente. Nel caso si volesse impostare questo parametro manualmente, si consiglia di non cambiarlo successivamente a run-time. Questo perché è stato scelto di caricare l’intero set di impostazioni per la regionalizzazione tramite codice javascript esterno, mediante files di libreria. Per questo metodo quindi, i cambiamenti a run-time generano codice non pulito, che sconsiglio, almeno fino a che non trovo il tempo di migliorare questa soluzione.
Come nella precedente versione, è consigliabile aggiungere un secondo quando si utilizza:->setUntil() e decrementare di un secondo quando si utilizza ->setSince(time())per evitare una non perfetta sincronizzazione fra il tempo in cui viene mostrato il widget e lo scattare del conteggio.
Infine è possibile rendere invisibile il widget, semplicemente con ->setVisible(false) e mantenere attivo il contatempo. Questo permette di utilizzare comunque l’handle per l’evento actionOnExpire anche senza visualizzare il widget.

Conclusioni:

Questi ultimi giorni sono stati davvero impietosi con il mio (già scarso) tempo libero, e non ho potuto sviluppare il codice come avrei voluto… spero di poterci dedicare ancora del tempo, perché mi sembra un progetto interessante e, spero utile a molti. Ci sono ancora alcune caratteristiche da integrare e miglioramenti da fare nel codice, spero nell’aiuto degli utenti! Nel frattempo cercherò anche di ampliare e migliorare la documentazione (già presente nel pacchetto).

Riferimenti ed approfondimenti:

P4A 3 framework: personalizzare il tema grafico con icone e colori

Le icone di P4ASulla personalizzazione dell’aspetto grafico delle maschere di P4A, esiste già questo interessante screencast di Fabrizio Balliano. Trovo interessante poter cambiare la grafica perché l’aspetto di default, sebbene gradevole e riposante, in alcuni casi, per esempio sugli schermi dei netbook appare un po’ troppo poco contrastato. Il tema alternativo proposto nello screencast è “Human” per Gnome, davvero molto bello!
Il set di impostazioni per i colori e il set di icone vengono generati a partire da script PHP. Entrambi gli script sono disponibili in P4A Wiki nella sezione: “Theme customizations”, il requisito è di farli girare su una macchina Linux, che sia dotata del necessario software di conversione da SVG a PNG. Ho pensato di scrivere questo post, anche se in gran parte è una ripetizione dello screencast di Fabrizio, perché qualcuno si potrebbe trovare in difficoltà scoprendo al primo approccio che lo script che genera il set di icone, per funzionare correttamente, necessita di una particolare libreria.

Dunque, la situazione migliore è che possediamo una distro “Ubuntu“, quindi con installato il Desktop Gnome. Per prima cosa, ci dobbiamo accertare che sia installato il programma rsvg che fa parte della libreria librsvg. Se non è presente (in genere non lo è…), l’installazione è davvero molto semplice utilizzando apt-get:

sudo apt-get install librsvg2-2

invece, se volete perdere tempo e avete già installate tutte le librerie per il supporto alle manipolazioni dei formati SVG, potete installare il pacchetto manualmente. Queste librerie sono comunque necessarie: libxml2 e libxml2-dev

Questo è il link per l’installazione del software rsvg:
http://ftp.gnome.org/pub/GNOME/sources/librsvg/2.22/librsvg-2.22.3.tar.bz2

scompattate il pacchetto con:

tar -xjvf librsvg-2.22.3.tar.gz.bz2

ed infine compilate:

  • sudo ./configure
  • sudo make
  • sudo make install

Ci siamo, ora possiamo lanciare lo script di Fabrizio che genera il set di icone, in questo caso il set Human per Gnome:

php build_icon_theme.php /home/directory/che/volete /usr/share/icons/Human /usr/share/icons/gnome

Adesso copiate le icone generate che saranno raggruppate nelle cartelle con il nome 16 e 32 nella directory human che si deve trovare all’interno di p4a/icons e aggiungete il seguente codice all’interno del file index.php della vostra applicazione P4A, prima della riga di codice: require_once dirname(__FILE__) . '/../../p4a.php'; e con le icone abbiamo finito.

define('P4A_ICONS_NAME', 'human');

In pratica lo script recupera le icone che servono a p4a e le copia, creando la struttura di directory necessaria, nella cartella /directory/che/volete. Se non sono disponibili nel formato richiesto, le genera dai modelli scalabili in SVG, oppure le cerca fra quelle del tema Gnome. Naturalmente, è sempre possibile aggiustare alcuni set a mano. Per esempio, ho notato che nella generazione del tema “Human”, l’icona “folder open”, risulta di colore grigio ed è piuttosto differente da “folder”, così l’ho sostituita con quella generata per il tema “Tangerine”.

Per quanto riguarda lo schema dei colori, dovete procurarvi lo script PHP: gtkrc2p4a.php per importare gli schemi Gnome gtkrc. Per generare il set di colori che armonizza le icone “Human”, digitate da linea di comando:

php gtkrc2p4a.php /usr/share/themes/Human/gtk-2.0/gtkrc

L’esecuzione genera il seguente set di impostazioni da copiare e incollare dentro index.php (sempre prima di: require_once dirname(__FILE__) . '/../../p4a.php';):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
define('P4A_THEME_FG', '#101010');
define('P4A_THEME_BG', '#EFEBE7');
define('P4A_THEME_BORDER', '#d7d3cf');
define('P4A_THEME_INPUT_FG', '#1A1A1A');
define('P4A_THEME_INPUT_BG', '#FFF');
define('P4A_THEME_INPUT_BORDER', '#e5e5e5');
define('P4A_THEME_SELECTED_FG', '#1A1A1A');
define('P4A_THEME_SELECTED_BG', '#FFA443');
define('P4A_THEME_SELECTED_BORDER', '#e5933c');
define('P4A_THEME_TOOLTIP_FG', '#000');
define('P4A_THEME_TOOLTIP_BG', '#F5F5B5');
define('P4A_THEME_TOOLTIP_BORDER', '#dcdca2');
define('P4A_THEME_EVEN_ROW', '#eee');
define('P4A_THEME_ODD_ROW', '#fff');

Sembra fatta, ma c’è ancora qualcosa di imperfetto. Se nella vostra applicazione è presente un “tab-panel” i bordi rimangono colorati dell’azzurro di default, e lo sfondo del bottoncino per il passaggio da un pannello all’altro, rimane azzurro chiaro. Così per essere pignoli rimane da modificare un poco il CSS in questo modo:

Create un file provacss.php con le seguenti istruzioni per il CSS (io l’ho messo nella directory libraries della mia applicazione):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?php
header('Content-type: text/css');
?>
.p4a_tab_pane ul.tabs {
	border-bottom: 1px solid <?php echo $_GET['input_border'] ?>;
}
.p4a_tab_pane ul.tabs li a {
	border: 1px solid <?php echo $_GET['input_border'] ?>;
}
.p4a_tab_pane ul.tabs a:hover {
	background: <?php echo $_GET['selected_bg'] ?>;
}
.p4a_tab_pane div.p4a_tab_pane_page {
	border: 1px solid <?php echo $_GET['input_border'] ?>;
}

Nel file principale della vostra applicazione, quello che estende la classe base p4a, inserite questo codice:

$this->addCss(P4A_APPLICATION_LIBRARIES_PATH."provacss.php?". $this->getCssConstants());

E il gioco è fatto! In pratica, è possibile aggiungere un CSS dinamico che carica, mediante querystring, le costanti determinate dal tema adottato.

Ecco uno screeshot della mia applicazione per la gestione delle fatture “vestita” con Human-gnome:

Screenshot di gestione fatture con tema Human
Screenshot di gestione fatture con tema Human

Download

Per chi non avesse a disposizione un ambiente Linux (ma cosa aspetta a farlo?) metto a disposizione il set di icone Human che ho generato qui

Conclusioni

Una volta compreso il meccanismo, personalizzare p4a è piuttosto semplice. Mi sono divertito anche a creare un tema “Vista like”, tanto per non spiazzare troppo i clienti “allineati” a M$…

Riferimenti ed approfondimenti:

  • Screencast di Fabrizio Balliano: “Theme customizations in RC5”
  • P4A Wiki

Fabrizio Balliano ha scritto:

ottimo articolo come sempre, vedo però di risolvere il problema del tab pane perché va fixato :)
23.02.09 09:41
Fabrizio Balliano ha scritto:

risolto e committato :)

P4A 3 framework: db_navigator helper per estrarre un ramo da un dbtree

Esempio di db_navigatorQuesto helper deriva naturalmente dalla funzione descritta nel precedente post.P4A mette a disposizione un widget chiamato P4A_DB_Navigator che si basa su archivi di tipo albero a liste di adiacenza e fornisce un output grafico della lista dei nodi, con un buon grado di interattività. Esiste, per esempio, un metodo che si chiama getPath() che restituisce in un array, il percorso dalla root al nodo fornito in input attraverso la chiave primaria. Purtroppo però, non esiste nessun metodo per estrarre l’insieme di nodi figli da un certo nodo parentale, così ho pensato di adottare la funzione presentata nel precedente post.

I parametri di input sono:

  • $navigator – l’oggetto da cui discende (implicito)
  • $id – l’identificativo del nodo da cui partire
  • $table – il nome della tabella che rappresenta l’albero
  • $pk – il nome della chiave primaria
  • $recursor – il nome del campo che identifica il nodo parentale

Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// File: P4A_db_navigator_getBranch.php
<?php
function P4A_db_navigator_getBranch ($navigator, $params)
{
  list($id, $table, $pk, $recursor) = $params;
  $arr = p4a_db::singleton()->getAll("SELECT * FROM $table");
  $pksArr = array();
  foreach ($arr as $rec) {
    $pksArr[$rec[$pk]]=$rec[$recursor];
  }
  $branchIds = array($id);
  $i=0;
  while ($i<count($branchIds)) {
    $newKeys = array_keys($pksArr,$branchIds[$i]);
    if (!empty($newKeys)) {
      foreach ($newKeys as $newKey){
        array_push($branchIds, $newKey);
      }
    }
    ++$i;
  }
  $res = array();
  foreach ($arr as $child) {
    if (in_array($child[$pk], $branchIds)) {
      $res[] = $child;
    }
  }
  return $res;
}
?>

Come esempio ho costruito una semplicissima maschera nella quale, ogni volta che viene selezionato un nodo, viene mostrato un messaggio con l’array dei nodi figli.

Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class dbtree extends P4A_Base_Mask
{
  public function __construct()
  {
    parent::__construct();
    $this->setTitle('Test dbTree');
    //Source
    $this->build("p4a_db_source","dbtree")
      ->setTable("tree")
      ->setPk("id")
      ->load()
      ->firstRow();
    $this->setSource($this->dbtree);
    // db_navigator
    $this->build("p4a_db_navigator","navigator")
      ->setSource($this->dbtree)
      ->setRecursor("parent_id")
      ->setDescription("nome")
      ->setStyleProperty("height","85%")
      ->setStyleProperty("overflow","auto")
      ->collapse(true);
    // Display
    $this->display("sidebar_left",$this->navigator);
    // Intercept action afterMoveRow
    $this->intercept($this->dbtree,"afterMoveRow","showBranch");
  }
	public function showBranch()
  {
    $idCommessa = $this->dbtree->fields->id->getNewValue();
    $arr = $this->navigator->getBranch ($idCommessa, "tree", "id", "parent_id");
    $this->info(print_r($arr,true));
  }
}

L’esempio completo è scaricabile qui

Conclusioni

Lancio l’idea di mettere questa funzione fra i metodi del P4A_db_navigator, sempre che non esca fuori qualche dannato baco :-).

Riferimenti ed approfondimenti:

PHP: estrarre un ramo da un albero a liste di adiacenza senza ricorsione

Esempio di struttura ad albero
Esempio di struttura ad albero
Supponiamo di avere un archivio con una struttura ad albero di tipo a liste di adiacenza. Ogni record sarà necessariamente caratterizzato da un identificativo univoco e da un attributo che serve a riconoscere il proprio genitore. Per esempio, nella figura accanto, l’elemento 4 avrà id = 4, e parentId = 1, l’elemento 9 avrà id = 9, e parentId = 4, e così via. Questo modello offre alcuni vantaggi, che sono principalmente la semplicità della struttura e la velocità negli inserimenti. D’altro canto, risultano piuttosto onerosi processi come l’estrazione o la cancellazione di interi rami. Le query risultano quindi, complesse e spesso ricorsive.

Sebbene l’utilizzo di una struttura di tipo nested tree model ideata da Joe Celko sia quasi sempre preferibile, alle volte è necessario cimentarsi con gli algoritmi per la manipolazione delle liste di adiacenza.

Se si deve salire da una foglia fino alla root, non è troppo difficile, basta risalire, attraverso il parentId, il genitore finché parentId = NULL. Il procedimento naturalmente ricorsivo, per questo motivo spesso si indica l’attributo parentId anche con il nome di ricorsore.

Il gioco si fa duro quando si deve estrarre un ramo a partire da un certo genitore… ma come disse John Belushi: “When the going gets tough, the toughs get going!”. Vediamo come fare evitando di farci del male con stored procedure, query ricorsive o tabelle temporanee.
La soluzione che ho adottato prende spunto dagli algoritmi di attraversamento dei grafi: Breadth-first search e Depth-first search. Questi sono procedimenti non ricorsivi che utilizzano stack di tipo FIFO e LIFO per l’esplorazione dei nodi.

L’operazione di fetching da un archivio che rappresenta l’albero della figura in alto produrrà un’array di questo tipo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$arrTest = array (
                    0 => array ("id"=>1, "parent_id"=>NULL),
                    1 => array ("id"=>2, "parent_id"=>1),
                    2 => array ("id"=>3, "parent_id"=>1),
                    3 => array ("id"=>4, "parent_id"=>1),
                    4 => array ("id"=>5, "parent_id"=>2),
                    5 => array ("id"=>6, "parent_id"=>2),
                    6 => array ("id"=>7, "parent_id"=>3),
                    7 => array ("id"=>8, "parent_id"=>3),
                    8 => array ("id"=>9, "parent_id"=>4),
                    9 => array ("id"=>10, "parent_id"=>4),
                    10 => array ("id"=>11, "parent_id"=>4),
                    11 => array ("id"=>12, "parent_id"=>5),
                    12 => array ("id"=>13, "parent_id"=>5),
                    13 => array ("id"=>14, "parent_id"=>6),
                    14 => array ("id"=>15, "parent_id"=>7),
                    15 => array ("id"=>16, "parent_id"=>7),
                    16 => array ("id"=>17, "parent_id"=>9),
                    17 => array ("id"=>18, "parent_id"=>9),
                    18 => array ("id"=>19, "parent_id"=>10),
                    19 => array ("id"=>20, "parent_id"=>11),
                    20 => array ("id"=>21, "parent_id"=>11)
                  );

Ammettiamo ora di voler estrarre l’intero ramo che ha come radice l’elemento 4. La funzione seguente utilizza un nuovo array che viene costruito utilizzando come chiave gli id e come valori i parent_id. Questo ci permette di utilizzare la funzione PHP: array_keys() per le ricerche dei figli, che è piuttosto efficiente.

Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function getBranch ($arr,$pk,$recursor,$idBranch)
{
  $pksArr = array();
  foreach ($arr as $rec) {
    $pksArr[$rec[$pk]]=$rec[$recursor];
  }
  $branchIds = array($idBranch);
  $i=0;
  while ($i<count($branchIds)) {
    $newKeys = array_keys($pksArr,$branchIds[$i]);
    if (!empty($newKeys)) {
      foreach ($newKeys as $newKey){
        array_push($branchIds, $newKey);
      }
    }
    ++$i;
  }
  $res = array();
  foreach ($arr as $child) {
    if (in_array($child[$pk], $branchIds)) {
      $res[] = $child;
    }
  }
  return $res;
}

Certo, il codice di questa funzione non è troppo ottimizzato: utilizza tre array (anche se $pksArr e $branchIds sono monodimensionali e quindi “leggeri”) ed esegue tre cicli. In particolare il ciclo (righe 19-23) è piuttosto lento, ma è necessario se si vuole recuperare tutti gli attributi degli elementi estratti oltre agli indispensabili id già presenti in $branchIds. Dalle prove che ho fatto, per archivi fino a 10-15000 records risulta comunque abbastanza efficiente.

Questo è il risultato dell’estrazione del ramo con radice 4 (si nota che l’andamento è di tipo “breadth-first-search” ricerca in ampiezza, seguendo i colori: rosso-verde-blu-giallo):

Array
(
    [0] => Array
        (
            [id] => 4
            [parent_id] => 1
        )

    [1] => Array
        (
            [id] => 9
            [parent_id] => 4
        )

    [2] => Array
        (
            [id] => 10
            [parent_id] => 4
        )

    [3] => Array
        (
            [id] => 11
            [parent_id] => 4
        )

    [4] => Array
        (
            [id] => 17
            [parent_id] => 9
        )

    [5] => Array
        (
            [id] => 18
            [parent_id] => 9
        )

    [6] => Array
        (
            [id] => 19
            [parent_id] => 10
        )

    [7] => Array
        (
            [id] => 20
            [parent_id] => 11
        )

    [8] => Array
        (
            [id] => 21
            [parent_id] => 11
        )

)
// Tempo di esecuzione: 0.2388 msecs

Conclusioni

Personalmente, ho una certa ritrosia nell’uso di funzioni ricorsive, per questo ho perso del tempo a cercare soluzioni alternative e cicliche, ciò non toglie che, ad esempio per recuperare il percorso di una foglia (risalendo quindi verso la root), la ricorsione sia la soluzione più adatta.

Riferimenti ed approfondimenti:

P4A 3 Framework: helper per la gestione degli errori in saveRow() e deleteRow()

Errore di chiave duplicataHo scritto questi due helper per facilitare la gestione degli errori dovuti a query di aggiornamento e di cancellazione record. Gli helper sono una comodissima feature del framework P4A, si tratta dell’opportunità di scrivere funzioni personalizzate che possono essere raggiunte da qualsiasi maschera dell’applicazione. Questa caratteristica consente quindi un efficiente riutilizzo del codice, con grande vantaggio per la leggibilità dello stesso. Per costruire un helper, richiamabile da qualsiasi maschera, è necessario scrivere un file nella directory libraries, all’interno della propria applicazione salvandolo con un nome a piacere preceduto dal suffisso p4a_mask_. All’interno del file deve essere presente una funzione nominata nello stesso modo. Vediamo un esempio di albero di directory:

P4A
 |
 -- applications
      |
      -- gestione_fatture
          |
          -- objects
          |
          -- uploads
          |
          -- libraries  <-- qui! 

All’interno di questa directory posizioniamo i due file:

  • p4a_mask_savewithoutpain.php
  • p4a_mask_deletebreezily.php

Le due funzioni richiamano i metodi saveRow() e deleteRow() all’interno del costrutto PHP: try ... catch, intercettando gli eventuali errori e fornendo un messaggio di avviso senza interrompere il flusso del programma. Quando si utilizzano query di aggiornamento e cancellazione, è sempre bene fare dei controlli perché se si utilizzano tabelle InnoDB si rischia di rompere l’integrità referenziale, se si utilizzano indici di tipo UNIQUE si rischia la duplicazione, e così via. D’altra parte la ricerca tramite SELECT dei vincoli e/o delle chiavi duplicate è spesso troppo laboriosa, anche se in certi casi necessaria.
NOTA: try ... catch funziona solo con P4A 3.x, in quanto è disponibile a partire da PHP5.

Vediamo il codice di p4a_mask_savewithoutpain.php:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Funzione: Salva senza soffrire :-)
function P4A_Mask_saveWithoutPain($mask, $params)
{    
    list($source) = $params;
    $mask->source = $source; 
	  try{ 
      $mask->source->saveRow();       
    } catch (Exception $e) {  
 
      $res = $e->getMessage();
      preg_match("/\SQLSTATE\[(.+)\]/",$res, $results);
 
      if ($results[1] == '23000') {
        $msg = "Errore: chiave duplicata!";
      }
      else {
        $msg = "Si e' verificato un errore nel salvataggio dei dati";
      }    
      $mask->warning($msg);  
    }
}

Le prime due righe di codice che ho spudoratamente copiato dagli helper di sistema, servono a ricevere gli oggetti: maschera chiamante e data source. Con try si tenta una saveRow(), se fallisce viene valutato il messaggio di errore per lo sbaglio più frequente: chiave duplicata. Negli altri casi viene segnalato un errore generico.

Questo, invece è il codice di p4a_mask_deletebreezily.php:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Funzione: cancella allegramente... :-)
function P4A_Mask_deleteBreezily($mask, $params)
{
    list($source) = $params;
    $mask->source = $source;
	  try{ 
      $mask->source->deleteRow();       
      } 
    catch (Exception $e) {  
      $res = $e->getMessage();
      $pos = strpos($res, "General error: 1451"); // Errore di rottura integrita'
                                                  // referenziale
      if ($pos==false) {
        $msg = "Si e' verificato un errore nella cancellazione";
      }
      else {
        $msg = "Errore: impossibile cancellare un record correlato";
      }
      $mask->warning($msg);  
    }
}

In questo caso ho valutato solo errori di cancellazione di record che abbiano un vincolo di relazione. Non ho ricercato nella descrizione il codice SQLSTATE perché in SQL lo stesso codice accomuna diversi casi. E’ quindi necessario utilizzare il numero di errore MySQL, che nel caso di rottura dell’integrità referenziale è 1451.

Ecco infine il codice da aggiungere alla nostra ipotetica maschera: (gli helper vengono richiamati omettendo il suffisso p4a_mask_ )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class test_fatture extends p4a_base_mask
{
 public function __construct()
  {
    parent::__construct();
    // DB Source
    $this->build("p4a_db_source", "source")
    // .....
    // codice della maschera...
    // .....
  }
  public function saveRow ()
  {
    $this->saveWithoutPain($this->source);
  }
  public function deleteRow()
  {
    $this->deleteBreezily($this->source);
  }
}

Infine vorrei ricordare gli helper di sistema che, grazie agli autori, ci fanno risparmiare parecchio lavoro!

  • P4A_Field_loadSelectByArray – Imposta un campo di tipo select da un array.
  • P4A_Field_loadSelectByTable – Imposta un campo di tipo select da una tabella.
  • P4A_Frame_anchorTabPane – Ancora un tab pane ad una maschera.
  • P4A_Mask_useToolbar – Imposta una toolbar e la ancora alla topbar.
  • P4A_Mask_setTableAsSource – Imposta un DB_source da una tabella.
  • P4A_Mask_constructSimpleEdit – Costruisce un’intera maschera! (disponibile in P4A 3.2.0)

Conclusioni

Credo che, grazie a strumenti di questo tipo, si può contribuire nello sviluppo Open Source, con poco sforzo e molto vantaggio per tutta la comunità!

Riferimenti ed approfondimenti:


Andrea ha scritto:

Ciao Mario,
complimenti per i gli helper, molto utili :)

Solo un appunto, io eviterei questa linea di codice
$mask->source = $source;
In pratica cosi’ facendo rifai un’assegnazione della variabile source della maschera che non serve: nel tuo esempio quando chiami $this->build(“p4a_db_source”, “source”) hai gia’ popolato la variabile source con un db_source.
Tra l’altro nel tuo esempio non da’ alcun fastidio ma in un caso teorico potrebbe essere un problema perche’ se l’utente inizializzasse la variabile source con un oggetto diverso chiamando quella riga di codice lo andresti a sovrascrivere con risultati del tutto inaspettati (immagina un utente che nella maschera abbia scritto $this->build(‘p4a_table’,’source’)).

Per risolvere il tutto basterebbe cambiare il codice in questa maniera:

try{
$source->saveRow();

Spero di esserti stato utile, a presto
Andrea

ps spero di non aver postato questo commento due volte, la prima volta il server mi ha dato errore… nel caso ignorami ;)
30.12.08 12:04
Mario Spada Author Profile Page ha scritto:

Grazie Andrea per la correzione, hai perfettamente ragione!
30.12.08 19:55