Configuring Kannel with GSM modem

These is sample config for Alcatel X200L(1bbb:0017) We assume that you have setup you modem(for example you have your modem at /dev/ttyUSB0-4)

1. Add kannel to dialout group (/etc/groups)
2. Config some stuff:
/etc/kannel/kannel.conf:

	group = core
	admin-port = 13000
	admin-password =
	admin-deny-ip = "*.*.*.*"
	admin-allow-ip = "127.0.0.1"
	smsbox-port = 13001
	log-file = "/var/log/kannel/bearerbox.log"
	#log-level = 3
	box-deny-ip = "*.*.*.*"
	box-allow-ip = "127.0.0.1"
	dlr-storage = mysql
	#--- mysql connection
	group = mysql-connection
	id = mydlr
	host = localhost
	username = kannel
	password = jMYnv29rcScJEZsM
	database = kannel
	max-connections = 1
	# ---- DLR table structure ----
	group = dlr-db
	id = mydlr
	table = dlr
	field-smsc = smsc
	field-timestamp = timestamp
	field-destination = destination
	field-source = source
	field-service = service
	field-url = url
	field-mask = mask
	field-status = status
	field-boxc-id = boxc_id
	# device conf
	group = smsc
	smsc = at
	smsc-id = usbmodem
	modemtype = auto
	device=/dev/ttyUSB3
	my-number = +359888123456
	log-level = 0
	group = sms-service
	keyword-regex = .*
	catch-all = yes
	max-messages = 0
	get-url = "http://localhost/api/receive.php?sender_gsm=%p&receiever_gsm=%P&text=%a&dlr=%d&s=%n"
	group = smsbox
	bearerbox-host = 127.0.0.1
	sendsms-port = 7048
	global-sender = "sms"
	#log-level = 3
	log-file = "/var/log/kannel/smsbox.log"
	group = sendsms-user
	username = senduser
	password = sendpass
	max-messages = 3
	concatenation = true
	include = "/etc/kannel/modems.conf"

view raw kannel.conf hosted with ❤ by GitHub

/etc/kannel/modems.conf:

	group = modems
	id = generic
	name = "Generic Modem"
	speed = 9600
	init-string = "AT+CNMI=1,2,2,2,1"

view raw modems.conf hosted with ❤ by GitHub

Important params:

* device - You should find out on what device you can access the modem with AT commands. So we try all of them from 0 to 4. This device works with 3 and 4.

* init-string - this one is extremely important. If it is not correct you even may not connect to the modem, can't send a message or can't receive DLRs. If you get "got +CMT but pdu_extract failed" message when receive a DLR it is highly possible that the init-string is not the correct one for your device.

PHP B-tree - Add element/node

Here follows an example of creating "Multiway B-Tree".
< br />The implementation is in PHP:

// B-tree
function btree_search( $value, $a, &$higher, $v)
{
 global $tree, $q, $u, $n, $nn;
 
 static $v;
 
 // create new elelemt
 if( $tree[$a]['m'] == 0 )
 {
  $higher = true;
  $v['value'] = $value;
  $v['count'] = 1;
  $v['p'] = null;
  
  $u = $v;
 }
 else
 {
   $cur = $tree[$a];
   $l = 1;
   $r = $cur['m'];

   do// binary search
   {
    $k = (int)( ($l + $r)/2);
    if( $value <= $cur['el'][$k]['value'] )
    {
     $r = $k - 1;
    }
    if( $value >= $cur['el'][$k]['value'] )
    {
     $l = $k + 1;
    }
   }while( $r >= $l);

   // found
   if( $l - $r > 1)
   {
    $cur['el'][$k]['count']++;
    $higher = false;
   }
   else
   {
    if( $r == 0 )
     $q = $cur['p0'];
    else
     $q = $cur['el'][$r]['p'];
    
    btree_search($value, $q, $higher, $u);
    if( $higher )
    {
     /* $a !== null. Search key $value in B-tree with root $a;
       insert new item with key $value. If an entry is to be passed up,
       assign it to $v. $higher = "tree has become higher"
    */
     
     $cur = &$tree[$a];
    
     // !$higher
    if( $cur['m'] < $n*2 )
    {
     $cur['m']++;
     $higher = false;

     
     for( $i=$cur['m']; $i >= $r+2; $i-- )
     {
      $cur['el'][$i] = $cur['el'][$i-1];
      
     }
     
     $cur['el'][$r+1] = $u;
     
    }
    // page $tree[$a]/$cur is full.
    // It's partioned and the odd element is moved to v 
    else
    {
     // add new element to $tree and assign
     // the last element's num to $b;
     $b = array_push($tree, array());
     if( $r <= $n ) // insert in left page $a
     {
      if( $r == $n )
       $v = $u;
      else
      {
       $v = $cur['el'][$n];
       for( $i=$n; $i >= $r+2; $i-- )
        $cur['el'][$i] = $cur['el'][$i-1];
       
       $cur['el'][$r+1] = $u;
      }
      for( $i=1; $i <= $n; $i++ ){
       $tree[$b]['el'][$i] = $cur['el'][$i+$n];
       unset( $cur['el'][$i+$n] );
      }
     }
     else // insert into right page $b
     {
      $r = $r-$n;
      $v = $cur['el'][$n+1];
      for( $i=1; $i <= $r-1; $i++ )
       $tree[$b]['el'][$i] = $cur['el'][$i+$n+1];
      $tree[$b]['el'][$r] = $u;
       
      for( $i=$r+1; $i <= $n; $i++ )
       $tree[$b]['el'][$i] = $cur['el'][$i+$n];
      
     }
     $cur['m'] = $n;
     $tree[$b]['m'] = $n;
     $tree[$b]['p0'] = $v['p'];
     $v['p'] = $b;
     
     $u = $v;
    }
    }
   }
 }
 return 1;
}

$b_tree = array();
// you could create as many trees as you want
// but when you want to work with them use $tree = &$my_tree;
$tree = &$b_tree;
// array for B-tree insert test
// test steps bellow to see how the tree behaves 
$values = array(20);
//$values = array(20, 40, 10, 30,15);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25 );

$higher = false;
$root = null;
$n = 2;
foreach( $values as $val )
{

 btree_search( $val, $root, $higher, $u);
 if( $higher )
 {
  $q = $root;
  if( count($tree) == 0 )
  {
   $tree = array(1=>array());
   $root = 1;
  }
  else
   $root = array_push($tree, array());

  $tree[$root]['m'] = 1;
  $tree[$root]['p0'] = $q;
  
  $tree[$root]['el'][1] = $u;
 }
}

PHP B-tree - Remove element/node

Here follows an example of deleting from "Multiway B-Tree".

PHP code:

function btree_delete($value, $a, &$higher)
{
 /*  search and delete key $value in B-tree a; if a page underflow arises,
  balance with adjacent page or merge; $higher := "page $a is undersize" */
 
 global $tree, $n;
 
 if( $a === null )
 {
  $higher = false;
 }
 else
 {
  $l = 1;
  $r = $tree[$a]['m'];
  
  // binary search
  do
  {
   $k = (int)( ($l + $r)/2 );
   if( $value <= $tree[$a]['el'][$k]['value'] )
    $r = $k -1;
   if( $value >= $tree[$a]['el'][$k]['value'] )
    $l = $k +1;
  }while( $r >= $l );
  
  
  if( $r === 0 )
  {
   $q = $tree[$a]['p0']; // go to the left
  }
  else
   $q = $tree[$a]['el'][$r]['p']; // go to the right
   
  if( $l - $r > 1)
  {
   // $a is leaf page
   if( $q === null )
   {
    $tree[$a]['m']--;
    $higher = ($tree[$a]['m'] < $n )? true: false;
    
    for( $i=$k; $i <= $tree[$a]['m']; $i++ )
    {
     $tree[$a]['el'][$i] = $tree[$a]['el'][$i+1];
    }
   }
   else
   {
    btree_del($q,$a, $higher, $k);
    if( $higher )
    {
     underflow( $a , $q, $r, $higher, $k); 
    }
   }
  }
  else
  {
   btree_delete( $value, $q, $higher );
   if( $higher )
   {
    underflow( $a, $q, $r, $higher, $k );
   }
  }
 }
 
}

function underflow( $c, $a, $s, &$higher, &$k )
{
 /* $a = underflowing page, $c = ancestor page,
  $s = index of deleted entry in c */
 
 global $tree, $n;
 
 $mc = $tree[$c]['m'];
 
 if( $s < $mc ) 
 {
  $s++;
  
  // $b = page to the right of a
  $b = $tree[$c]['el'][$s]['p'];
  $mb = $tree[$b]['m'];
  
  // $k = nof items available on page b
  $k = (int)( ($mb - $n+1)/2 );
  
  $tree[$a]['el'][$n] = $tree[$c]['el'][$s];
  
  $tree[$a]['el'][$n]['p'] = $tree[$b]['p0'];

  if( $k > 0 )// balance by moving k-1 items from $b to $a
  {
   for( $i=1; $i <= $k-1; $i++ )
   {
    $tree[$a]['el'][$i+$n] = $tree[$b]['el'][$i];
   }
   $tree[$c]['el'][$s] = $tree[$b]['el'][$k];
   $tree[$c]['el'][$s]['p'] = $b;
   
   $tree[$b]['p0'] = $tree[$b]['el'][$k]['p'];
   $mb -= $k;/////// +1
   
   for( $i=1; $i <= $mb; $i++  )
   {
    $tree[$b]['el'][$i] = $tree[$b]['el'][$i+$k];
   }
   $tree[$b]['m'] = $mb;
   $tree[$a]['m'] = $n-1 +$k;
   $higher = false;

  }
  else// merging a and b, discard b
  {
   for( $i=1; $i <= $n; $i++ )
   {
    $tree[$a]['el'][$i+$n] = $tree[$b]['el'][$i];
   }
   for( $i=$s; $i <= $mc-1; $i++)
   {
    $tree[$c]['el'][$i] = $tree[$c]['el'][$i+1];
   }
   $tree[$a]['m'] = 2*$n;
   $tree[$c]['m'] = $mc - 1;
  }
 }
 else
 {
  // $b = page to the left of $a
  if( $s == 1 )
  {
   $b = $tree[$c]['p0'];
  }
  else
  {
   $b = $tree[$c]['el'][$s-1]['p'];
  }
  $mb = $tree[$b]['m']+1;
  $k = (int)( ($mb - $n)/2 );
  
  if( $k > 0 )
  {
   for( $i=$n-1; $i >= 1; $i-- )
   {
    $tree[$a]['el'][$i+$k] = $tree[$a]['el'][$i]; 
   }
   $tree[$a]['el'][$k] = $tree[$c]['el'][$s];
   $tree[$a]['el'][$k]['p'] = $tree[$a]['p0'];

   // move k-1 items from $b to $a, one to $c

   $mb -= $k;//////// +1
   
   for( $i=$k-1; $i >= 1; $i-- )
   {
    $tree[$a]['el'][$i] = $tree[$b]['el'][$i+$mb]; 
   }
   $tree[$a]['p0'] = $tree[$b]['el'][$mb]['p'];
   
   $tree[$c]['el'][$s] = $tree[$b]['el'][$mb];
   $tree[$c]['el'][$s]['p'] = $a;
   
   $tree[$b]['m'] = $mb -1;
   $tree[$a]['m'] = $n-1 +$k;

   $higher = false;
   
  }
  else //merge pages $a and $b, discard $a
  {
   $tree[$b]['el'][$mb] = $tree[$c]['el'][$s];
   $tree[$b]['el'][$mb]['p'] = $tree[$a]['p0'];
   
   for( $i=1; $i <= $n-1; $i++ )
   {
    $tree[$b]['el'][$i+$mb] = $tree[$a]['el'][$i];
   }
   $tree[$b]['m'] = 2*$n;
   $tree[$c]['m'] = $mc - 1;
  }
 }
}

function btree_del($p, $a, &$higher, &$k)
{
 global $tree, $n;
 
 $m = &$tree[$p]['m'];
 
 $q = $tree[$p]['el'][$m]['p'];
 if( $q !== null )
 {
  btree_del($q, $a, $higher, $k);
  if( $higher )
   underflow($p, $q, $m, $higher, $k);
 }
 else
 {
  $tree[$p]['el'][$m]['p'] = $tree[$a]['el'][$k]['p'];
  $tree[$a]['el'][$k] = $tree[$p]['el'][$m];
  
  $m--;

  $higher = ($m < $n )? true: false;
 }
}

Full example of creating and delete from B-Tree here

PHP Balanced tree - Add element/node

This script add element to the tree if it doesn't exist, if exists just increment it counter.

function search_btree( $value, $ptr, $higher, $ptr0 = 0,$node = 'left' )
{
 global $tree;
 static 
  $first_run = 1,
  $higher,
  $beginning;  
 
 if( !$tree[$ptr]['value'] )// insertion
 {
  if( !$first_run )// create new element in the tree array - $tree
  {
   $tree[] = array();
   $ptr = count($tree)-1;
    
   $tree[$ptr0][$node] = $ptr;// put current node in parent's left or right node

  }else{// $tree[0] is already create so we just use is
   $first_run--;
   $beginning = $ptr;
  }
  $higher = true;
  
  $tree[$ptr]['value'] = $value;
  $tree[$ptr]['left'] = null;
  $tree[$ptr]['right'] = null;
  $tree[$ptr]['bal'] = 0;
  $tree[$ptr]['count'] = 1;
  
 }
 else
 {
  if( $value < $tree[$ptr]['value'] )
  {
   search_btree( $value, $tree[$ptr]['left'], $higher, $ptr );
   if( $higher )
   {
    switch( $tree[$ptr]['bal'] )
    {
     case 1:
      $tree[$ptr]['bal'] = 0;
      $higher = false;
     break;
     case 0:
      $tree[$ptr]['bal'] = -1;
     break;
     case -1:
      $ptr1 = $tree[$ptr]['left'];
      if( $tree[$ptr1]['bal'] == -1) // individualli flip LL
      {
       
       $tree[$ptr]['left'] = $tree[$ptr1]['right'];
       $tree[$ptr1]['right'] = $ptr;
       $tree[$ptr]['bal'] = 0;


       if( $ptr == $beginning )
        $beginning = $ptr1;
       // replaces $ptr with $ptr1 in parent left or right node
       replace_pointer_link( $ptr, $ptr1 );
       $ptr = $ptr1;
      }
      else
      {
       $ptr2 = $tree[$ptr1]['right'];

       $tree[$ptr1]['right'] = $tree[$ptr2]['left'];
       $tree[$ptr2]['left'] = $ptr1;
       
       $tree[$ptr]['left'] = $tree[$ptr2]['right'];
       $tree[$ptr2]['right'] = $ptr;
       
       if( $tree[$ptr2]['bal'] == -1 )
        $tree[$ptr]['bal'] = 1;
       else
        $tree[$ptr]['bal'] = 0;
        
       if( $tree[$ptr2]['bal'] == 1 )
        $tree[$ptr1]['bal'] = -1;
       else
        $tree[$ptr1]['bal'] = 0;
       
       if( $ptr == $beginning )
        $beginning = $ptr2;
       replace_pointer_link( $ptr, $ptr2 );
       $ptr = $ptr2;
       
      }
      $tree[$ptr]['bal'] = 0;
      $higher = false;
     break;
    }
   }
  }
  else if( $value > $tree[$ptr]['value'] )
  {
   search_btree( $value, $tree[$ptr]['right'], $higher, $ptr, 'right' );
   if( $higher )
   {
    switch( $tree[$ptr]['bal'] )
    {
     case -1:
      $tree[$ptr]['bal'] = 0;
      $higher = false;
     break;
     case 0:
      $tree[$ptr]['bal'] = 1;
     break;
     case 1:
      $ptr1 = $tree[$ptr]['right'];
      if( $tree[$ptr1]['bal'] == 1 )// individualli flip RR
      {

       $tree[$ptr]['right'] = $tree[$ptr1]['left'];
       $tree[$ptr1]['left'] = $ptr;
       
       $tree[$ptr]['bal'] = 0;
       
       if( $ptr == $beginning )
        $beginning = $ptr1;
       replace_pointer_link( $ptr, $ptr1 );
       $ptr = $ptr1;
      }
      else//RL
      {
       
       $ptr2 = $tree[$ptr1]['left'];
       
       $tree[$ptr1]['left'] = $tree[$ptr2]['right'];
       $tree[$ptr2]['right'] = $ptr1;
       
       $tree[$ptr]['right'] = $tree[$ptr2]['left'];
       $tree[$ptr2]['left'] = $ptr;
       
       if( $tree[$ptr2]['bal'] == 1 )
        $tree[$ptr]['bal'] = -1;
       else
        $tree[$ptr]['bal'] = 0;
       
       if( $tree[$ptr2]['bal'] == -1 )
        $tree[$ptr1]['bal'] = 1;
       else
        $tree[$ptr1]['bal'] = 0;
       
       if( $ptr == $beginning )
        $beginning = $ptr2;

       replace_pointer_link( $ptr, $ptr2 );
       $ptr = $ptr2;
      }
      $tree[$ptr]['bal'] = 0;
      $higher = false;
     break;
    }
   }
  }
  else
  {
   $tree[$ptr]['count']++;
   $higher = false;
  }
 }
 return $beginning;
}
//replaces $old_ptr with $new_ptr in the parent node's left or right node
function replace_pointer_link( $old_ptr, $new_ptr )
{
 global $tree;

 for( $i=0; $i < count($tree); $i++)
 {
  if( $i === $new_ptr )
   continue;//prevents replacing $old_ptr with $new_ptr in $tree[$new_ptr] 
 
  // if $tree[$i]['left'] is empty and we are checking for link to node 0($old_ptr=0),
  // ('' == 0)==true, but ('' === 0)==false
  // we don't need to put link to node 0 on empty nodes
  if( $tree[$i]['left'] === $old_ptr ){
   $tree[$i]['left'] = $new_ptr;
   return;
   }
   elseif( $tree[$i]['right'] === $old_ptr)
  {
   $tree[$i]['right'] = $new_ptr;
   return;
  }
 }

}
//
// Example:
//

$my_tree = array();
// you could create as many trees as you want
// but when you want to work with them use $tree = &$my_tree;
$tree = &$my_tree;
$start = 0;

// test all 4 cases of rebalancing when
// adding element in balanced tree
$values = array( 4, 5, 7, 2, 1, 3, 6);
foreach( $values as $val )
{
 $start = search_btree( $val, $start, false);
}
echo "<html><body>";
echo "start=$start;";
echo "<pre>";
print_r( $my_tree );
echo "</pre>";
echo "<br><br>";
echo "</body></html>";

?>

Source

PHP Balanced tree - Remove element/node

Delete element from balanced tree:

//replaces $old_ptr with $new_ptr in the parent node's left or right node
function replace_pointer_link( $old_ptr, $new_ptr )
{
 global $tree;

 for( $i=0; $i < count($tree); $i++)
 {
  if( $i === $new_ptr )
   continue;//prevents replacing $old_ptr with $new_ptr in $tree[$new_ptr] 
 
  // if $tree[$i]['left'] is empty and we are checking for link to node 0($old_ptr=0),
  // ('' == 0)==true, but ('' === 0)==false
  // we don't need to put link to node 0 on empty nodes
  if( $tree[$i]['left'] === $old_ptr ){
   $tree[$i]['left'] = $new_ptr;
   return;
   }
   elseif( $tree[$i]['right'] === $old_ptr)
  {
   $tree[$i]['right'] = $new_ptr;
   return;
  }
 }

}
function delete( $value, $ptr, $higher)
{
 global $tree, $q, $start;
 static $higher;
 
 if( !$tree[$ptr]['value'] )
 {
  echo "KEY IS NOT IN TREE";
  $higher = false;
 }
 elseif( $value < $tree[$ptr]['value'] )
 {
  delete( $value, $tree[$ptr]['left'], $higher );
  if( $higher )
   balance1( $ptr, $higher);
 }
 elseif ( $value > $tree[$ptr]['value'] )
 {
 delete( $value, $tree[$ptr]['right'], $higher );
  if( $higher )
   balance2( $ptr, $higher);
 }
 else
 {
  $q = $ptr;
  if( $tree[$q]['right'] === null )
  {
   replace_pointer_link( $ptr, $tree[$q]['left'] );
   unset($tree[$q]);
   $higher = true; 
  }
  elseif( $tree[$q]['left'] === null )
  {
   replace_pointer_link( $ptr, $tree[$q]['right']);
   unset($tree[$q]);
   $higher = true;
  }
  else
  {
   del( $tree[$q]['left'], $higher );
   if( $higher )
    balance1( $ptr, $higher);
  
  }
 }
 
}
function balance1( $ptr, &$higher)
{
 global $tree, $start;
 switch( $tree[$ptr]['bal'] ){
  case -1: 
   $tree[$ptr]['bal'] = 0;// after del tree is balanced
  break;
  case 0://after deletion tree is higher in the right side
   $tree[$ptr]['bal'] = 1;
   $higher = false;
  break;
  case 1: // tree must be rebalanced
   $ptr1 = $tree[$ptr]['right'];
   $bal1 = $tree[$ptr1]['bal'];
   
   if( $bal1 >= 0 )// single flip RR
   {
    $tree[$ptr]['right'] = $tree[$ptr1]['left'];
    $tree[$ptr1]['left'] = $ptr;
    
    if( $bal1 == 0 )
    {
     $tree[$ptr]['bal'] = 1;
     $tree[$ptr1]['bal'] = -1;
     $higher = false;
    }else{
     $tree[$ptr]['bal'] = 0;
     $tree[$ptr1]['bal'] = 0;
    }
    
    // start pointer is replaced we need to change $start
    if( $ptr == $start )
     $start = $ptr1;
    replace_pointer_link($ptr, $ptr1);
   }
   else // double flip RL
   {
    $ptr2 = $tree[$ptr1]['left'];
    $bal2 = $tree[$ptr2]['bal'];
    
    $tree[$ptr1]['left'] = $tree[$ptr2]['right'];
    $tree[$ptr2]['right'] = $ptr1;
    
    $tree[$ptr]['right'] = $tree[$ptr2]['left'];
    $tree[$ptr2]['left'] = $ptr;
    
    if( $bal2 == 1 )
    {
     $tree[$ptr]['bal'] = -1;
    }else{
     $tree[$ptr]['bal'] = 0;
    }
    if( $bal2 == -1 )
    {
     $tree[$ptr1]['bal'] = 1;
    }else{
     $tree[$ptr1]['bal'] = 0;
    }

    if( $ptr == $start )
     $start = $ptr2;
    replace_pointer_link( $ptr, $ptr2);
    $tree[$ptr2]['bal'] = 0;
   }
   
  break;
 }
}

function balance2( $ptr, &$higher )
{
 global $tree, $start;
 switch( $tree[$ptr]['bal'] )
 {
  case 1:
   $tree[$ptr]['bal'] = 0;
  break;
  case 0:
   $tree[$ptr]['bal'] =-1;
   $higher = false;
  break;
  case -1:
   $ptr1 = $tree[$ptr]['left'];
   $bal1 = $tree[$ptr1]['bal'];
   
   if( $bal1 <= 0 )// single flip LL
   {
    $tree[$ptr]['left'] = $tree[$ptr1]['right'];
    $tree[$ptr1]['right'] = $ptr;
    
    if( $bal1 == 0 )
    {
     $tree[$ptr]['bal'] = -1;
     $tree[$ptr1]['bal'] = 1;
     $higher = false;
    }
    else
    {
     $tree[$ptr]['bal'] = 0;
     $tree[$ptr1]['bal'] = 0;
    }
    if( $ptr == $start )
     $start = $ptr1;
    replace_pointer_link( $ptr, $ptr1);
   }
   else// double flip LR 
   {
    $ptr2 = $tree[$ptr1]['right'];
    $bal2 = $tree[$ptr2]['bal'];
    
    $tree[$ptr1]['right'] = $tree[$ptr2]['left'];
    $tree[$ptr2]['left'] = $ptr1;
    
    $tree[$ptr]['left'] = $tree[$ptr2]['right'];
    $tree[$ptr2]['right'] = $ptr;
    
    if( $bal2 == -1 )
     $tree[$ptr]['bal'] = 1;
    else
     $tree[$ptr]['bal'] = 0;
    if( $bal2 == 1 )
     $tree[$ptr1]['bal'] = -1;
    else
     $tree[$ptr1]['bal'] = 0;
    
    if( $ptr == $start )
     $start = $ptr2;
    replace_pointer_link($ptr, $ptr2);
    $tree[$ptr2]['bal'] = 0;
   }
  
 }
}
function del( $ptr, &$higher )
{
 global $tree, $q;
 if( $tree[$ptr]['right'] )
 {
  del( $tree[$ptr]['right'], $higher);
  if( $higher )
   balance2( $ptr, $higher);
 }
 else
 {
  $tree[$q]['value'] = $tree[$ptr]['value'];
  $tree[$q]['count'] = $tree[$ptr]['count'];
  
  replace_pointer_link($ptr, $tree[$ptr]['left']);
  if( $ptr == $start )
   $start = $tree[$ptr]['left'];

  unset($tree[$ptr]);
  $higher = true;
 }
}
$my_tree = array();
// you could create as many trees as you want
// but when you want to work with them use $tree = &$my_tree;
$tree = &$my_tree;
$start = 0;

// array for testing deletion in balanced tree 
$values = array(5, 3, 8, 2, 4, 7, 10, 1, 6, 9, 11);

foreach( $values as $val )
{
 $start = search_btree( $val, $start, false);
}
echo "<html><body>";
echo "start=$start;";
echo "<pre>";
print_r( $my_tree );

delete( 4, $start, false);
delete( 8, $start, false);
delete( 6, $start, false);
delete( 5, $start, false);
delete( 2, $start, false);
delete( 1, $start, false);
delete( 7, $start, false);


echo "start=$start<br>";
print_r($tree);

echo "</pre>";
echo "<br><br>";
echo "</body></html>";

Source

PHP Generate perfectly balanced tree

The script that follows generates perfectly balanced tree with "n" nodes:

	function tree(&$tree, $num_nodes)
	{
	if($num_nodes == 0)
	return null;
	$left = (int)($num_nodes / 2);
	$right = $num_nodes - $left -1;
	$tree[]['value'] = (int)(mt_rand( 1, 50) / $num_nodes+1);
	$last = count($tree)-1;
	$tree[$last]['left'] = tree($tree, $left);
	$tree[$last]['right'] = tree($tree, $right);
	return $last;
	}

view raw gistfile1.php hosted with ❤ by GitHub

PHP Eight queens

Here is recursive algorithm solving the problem with eight queens which don't threaten each other:

function check( $i )
{
 global $column, $rows, $left_d, $right_d;
 for( $j = 1; $j <= 8; $j++ )
 {
  // check is the row and both diagonals are free
  if( $rows[$j] && $left_d[$i+$j] && $right_d[$i-$j] )
  {
   $column[$i] = $j;//put the qeen on the $i column in the $j position
   
   //set row and diagonals to occupied 
   $rows[$j] = false;
   $left_d[$i+$j] = false;
   $right_d[$i-$j] = false;
   
   // if $i == last column(8) we print the results
   if( $i < 8 )
    check( $i + 1 );
   else
    print_results();
   
   //unset row and diagonals
   $rows[$j] = true;
   $left_d[$i+$j] = true;
   $right_d[$i-$j] = true;
  }
 }
}

function print_results()
{
 global $column;
 foreach( $column as $value )
  echo $value ."&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
 
 echo "<br />\n";
}

for( $i = 1; $i <= 8; $i++ )
 $rows[$i] = true;

for( $i = 2; $i <= 16; $i++ )
 $left_d[$i] = true;
  

for( $i = -7; $i <= 7; $i++ )
 $right_d[$i] = true;

check(1);