index file & processor
<?php header ("Content-Type: text/html; charset=utf-8");?>
<html>
<head>
<title>Здирук, ДЗ2</title>
</head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<body>
<h1>Anti-Zdiruk v.FINAL, а <a href="http://www.chto.su">также мой
уютненький бложег</a></h1>
<pre>
<a href="#result">Scroll down to results</a> | <a href="source.php">Source code!</a>
---
<b><i>Внимание, этот скрипт строит KD-дерево полных или всех индексов, следуя логике размещения записей на блоках и тому, что индекс однозначно определяет запись.
Товарищу Здируку <u>ЭТО НЕ НУЖНО</u> (его индексы определяют блок из трех записей), не показывайте ему это, этого он у вас НЕ ПРИМЕТ.
Данный скрипт разработан в исключительно ознакомительных целях. Если вам действительно нужно строить полное KD-дерево, то пожалуйста - проект к вашим услугам.</i></b>
---
Changelog:
    v.FINAL Добавлено уведомление об окончании разработки.
    v.0.8 Возможность построения ВСЕХ типов индекса для таблицы.
    v.0.7 Возможность выводить только полные индексы [уровень1,уровень2,уровень3], а не последовательно [[[уровень1],уровень2],уровень3]
    v.0.6.1 Небольшой дебаг
    v.0.6 Изменен порядок построения индекса в порядке вставки записей.
    v.0.5 Изменена логика построения индекса на правильную, добавлен вывод данных на блоках
    v.0.4 Изменены цвета на цвета, удобные для печати на монохромных принтерах
    v.0.3 Изменена индексация пола, один пол не может быть подуровнем другого
    v.0.2 Добавлен GUI
    v.0.1 Стартовая версия без GUI
---
ДЗ СУБД 2, построение KD-индекса записей.
Копипастните данные из таблицы, исключая заголовки полей, в поле data.
---
Вот они, для лучшего усвоения:
01    20    300    М
02    16    100    M
03    34    1500    Ж
04    47    2000    M
05    -    500    Ж
06    70    1000    M
07    25    300    Ж
08    56    1000    Ж
09    24    15000    Ж
10    14    200000    M
11    33    -    M
12    60    2000    Ж
13    70    1000    M
14    25    300    Ж
15    56    1000    Ж
16    24    15000    Ж
17    44    100    M
18    34    -    Ж
19    50    2000    Ж
20    -    -    M
21    70    1000    Ж
22    25    300    Ж
23    56    1000    М
24    24    15000    М
25    64    100000    M
26    33    -    Ж
27    60    2000    Ж
28    -    -    Ж
29    45    3000    Ж
30    50    10000    M
----
Копипастните данные из вариантов в поле query.
---
Вот мой, второй:
11 02 13 04 25 06 07 08 29 10 01 12 03 14 15 
16 17 18 19 20 21 22 23 24 05 26 27 28 09 30
---
Выберите желаемый тип индекса.
Структура ответа (таблично-древовидная форма)
<table border="1">
<tr>
        <td>Первый уровень индекса</td>
        <td></td>
        <td></td>
        <td></td>
        <td></td>
    </tr>
<tr>
        <td></td>
        <td>Значение индекса</td>
        <td></td>
        <td></td>
        <td></td>
    </tr>
<tr>
        <td></td>
        <td></td>
        <td>Данные индекса</td>
        <td></td>
        <td></td>
    </tr>
<tr>
        <td></td>
        <td></td>
        <td></td>
        <td>Запись номера N</td>
        <td>Позиция записи на диске</td>
    </tr>
<tr>
        <td></td>
        <td></td>
        <td>Правая ветка</td>
        <td></td>
        <td></td>
    </tr>
<tr>
        <td></td>
        <td></td>
        <td>..</td>
        <td>..</td>
        <td>..</td>
    </tr>
<tr>
        <td></td>
        <td></td>
        <td>Левая ветка</td>
        <td></td>
        <td></td>
    </tr>
<tr>
        <td></td>
        <td></td>
        <td>..</td>
        <td>..</td>
        <td>..</td>
    </tr>
<tr>
        <td></td>
        <td></td>
        <td>Следующий уровень индекса</td>
        <td></td>
        <td></td>
    </tr>
<tr>
        <td></td>
        <td></td>
        <td>..</td>
        <td>..</td>
        <td>..</td>
    </tr>
</table>
<?php
if ($_POST['data']) {
    
$data explode("\n",(string)$_POST['data']);
    
$query = (string)$_POST['query'];
    
$IT = (int)$_POST['it'];
    
$fullindex = isset($_POST['fullindex']);
}

print 
'<form method="POST">
Data:<textarea name="data">'
.((string)$_POST['data']).'</textarea>
Query:<textarea name="query">'
.htmlentities($query).'</textarea>
Index type: <input type="radio" name="it" value="0"'
.($IT==0?' checked':'').'>Age-Salary-Gender<br/>
<input type="radio" name="it" value="1"'
.($IT==1?' checked':'').'>Salary-Age-Gender<br/>
<input type="radio" name="it" value="2"'
.($IT==2?' checked':'').'>Gender-Age-Salary<br/>
<input type="radio" name="it" value="3"'
.($IT==3?' checked':'').'>Gender-Salary-Age<br/>
<input type="radio" name="it" value="4"'
.($IT==4?' checked':'').'>Salary-Gender-Age<br/>
<input type="radio" name="it" value="5"'
.($IT==5?' checked':'').'>Age-Gender-Salary<br/>
<input type="radio" name="it" value="6"'
.($IT==6?' checked':'').'>ALL<br/>
Only full index: <input type="checkbox" name="fullindex" value="1"'
.($fullindex?' checked':'').'>
<input type="submit"></form>'
;

if (
$data) {

    
$indexes[] = array('age','salary','gender');
    
$indexes[] = array('salary','age','gender');
    
$indexes[] = array('gender','age','salary');
    
$indexes[] = array('gender','salary','age');
    
$indexes[] = array('salary','gender','age');
    
$indexes[] = array('age','gender','salary');

    foreach (
$data as $line) {
        
preg_match("/([0-9]+)(.*?)([0-9-]+)(.*?)([0-9-]+)(.*?)(М|Ж|M)/",$line,$matches);
        
$matches array_map("trim",$matches);
        
$gender = ($matches[7]=='Ж'?'f':'m');
        
$records[(int)$matches[1]] = array('id'=>(int)$matches[1],'age'=>$matches[3],'salary'=>$matches[5],'gender'=>$gender);
        
//$records[(int)$matches[1]] = array((int)$matches[5],(int)$matches[3],$gender);
    
}

    if (
$query) {
        
preg_match_all("/([0-9]+)/",$query,$matches);
        
$selects $matches[0];
    }

    if (
$selects) {
        foreach (
$selects as $sel) {
            
$records2[] = $records[(int)$sel];
        }
        
$records $records2;
    }

    
$blocksdata array_chunk($records3);
    print 
'<table><tr><td style="vertical-align: top;">Blocks data:<br/>';
    
printArray($blocksdata);

    
$idonblocks assign_blocks_to_ids($blocksdata);

    print 
'Records locations:<br/>';
    
printArray($idonblocks);


    
//TOTAL KEY STRUCTURE CREATION - UNNEDED
    
foreach ($records as $rec) {
        
$sals[$rec['salary']][] = $rec['id']; //key - salary
        
$ages[$rec['age']][] = $rec['id']; //key - age
        
$genders[$rec['gender']][] = $rec['id']; // key- gender
    
}

    
/*ksort($sals);
     ksort($ages);
     ksort($genders);*/

    
$treedata['salary'] = $sals;
    
$treedata['age'] = $ages;
    
$treedata['gender'] = $genders;

    
    function 
bulid_full_tree($treedata,$IT,$indexes,$idonblocks,$fullindex) {

    
$i1 make_tree($treedata[$indexes[$IT][0]],$indexes[$IT][0],$idonblocks);

    while(
$i2key get_way('data-'.$indexes[$IT][0], $i1)) {

        eval(
'$i2data = $i1'.$i2key.';');
        
$i2 make_level_tree($i2data$indexes[$IT][1],$idonblocks);
        eval(
'unset($i1'.$i2key.');');
        
$i2key str_replace('data-'.$indexes[$IT][0],$indexes[$IT][1],$i2key);
        eval(
'$i1'.$i2key.'=$i2;');

    }
    
$i3key get_way('data-'.$indexes[$IT][1], $i1);
    while(
$i3key get_way('data-'.$indexes[$IT][1], $i1)) {
        eval(
'$i3data = $i1'.$i3key.';');

        
$i3 make_level_tree($i3data$indexes[$IT][2],$idonblocks);
        eval(
'unset($i1'.$i3key.');');
        
$i3key str_replace('data-'.$indexes[$IT][1],$indexes[$IT][2],$i3key);
        
$fullindexreturns[] = $i3key;
        eval(
'$i1'.$i3key.'=$i3;');

    }
    
//var_dump($i1);
    // cleanup from undeeded index data
    
while($cleankey get_way('data-'.$indexes[$IT][2], $i1)) {
        eval(
'unset($i1'.$cleankey.');');
    }

    
// cleanup from null branches
    
while($cleankey get_null_way($i1)) {
        eval(
'unset($i1'.$cleankey.');');
    }
    
        if (
$fullindex) {
        foreach (
$fullindexreturns as $ireturn) {
            eval(
'$result'.$ireturn.'=$i1'.$ireturn.';');
        }
    } else 
$result $i1;
    
    
//$result = array($indexes[$IT][0]=>$result);
    
    
return $result;
    }
    
    if (
$IT<>6)
    
$result = array($indexes[$IT][0]=>bulid_full_tree($treedata,$IT,$indexes,$idonblocks,$fullindex));
    else {
        
$result = array();
        foreach (
array_keys($indexes) as $IT) {
            
$result[$indexes[$IT][0]] = bulid_full_tree($treedata,$IT,$indexes,$idonblocks,$fullindex);
        }
    }
    
// sort result array
    //ksortTree($i1);
    // print NONGUI
    //print_r($i1);

    
print '</td><td style="vertical-align: top;">Index structure:<br/>';
    
    
// GUI GUI GUI
    
printArray($result);
    print 
'</td></tr></table>';
}

function 
make_tree($array,$index,$idonblocks) {

    if (!
$array) return NULL;

    
$keys array_keys($array);

    
$key $keys[0];

    
$branch[$key]['data-'.$index] = $array[$key];
    
$branch[$key]['index'] = make_index_record($idonblocks,$array[$key]);

    
$count 0;
    foreach (
$array as $arkey=>$val) {
        
$count++;
        if (
$count==1) { $sravn $arkey; continue; }
        if (
$arkey>=$sravn)
        
$to_right[$arkey] = $val;
        else 
$to_left[$arkey] = $val;
    }

    if (
$index=='gender') {
        
$to_merge make_tree($to_right,$index,$idonblocks);
        if (
$to_merge)
        
$branch array_merge($branch,$to_merge);
        
$to_merge make_tree($to_left,$index,$idonblocks);
        if (
$to_merge)
        
$branch array_merge($branch,$to_merge);
    } else {

        
$branch[$key]['right'] = make_tree($to_right,$index,$idonblocks);
        
$branch[$key]['left'] = make_tree($to_left,$index,$idonblocks);
    }
    return 
$branch;
}

function 
make_level_tree($selects,$index,$idonblocks) {
    global 
$records;
    if (!
is_array($selects)) die('no data for tree level');


    foreach (
$records as $record) {
        
$recs[$record['id']] = $record;
    }

    
$diff array_diff(array_keys($recs),$selects);

    foreach (
$diff as $t) { unset($recs[$t]); }


    foreach (
$recs as $id=>$rec) {
        
$return[$rec[$index]][] = $id;
    }

    
//ksort($return);

    
$return make_tree($return,$index,$idonblocks);
    return 
$return;
}

function 
get_null_way($array ,$curway=array(),$level=0,$levelsfalse = array()) {

    foreach(
$array AS $key=>$value){

        
$curway[$level] = "[".(!is_int($key)?"'$key'":$key)."]";
        if(
$value==NULL) {
            if (
$levelsfalse) {
                foreach (
$levelsfalse as $level) unset($curway[$level]);
            }
            return 
implode('',$curway);
        }
        if(
is_array($value)){
            if( (
$result get_null_way($value$curway$level+1,$levelsfalse)) !== false)
            return 
$result;
        }
    }
    
$levelsfalse[] = $level;
    return 
false;
}

function 
get_way$needle_key$array ,$curway=array(),$level=0,$levelsfalse = array()) {

    foreach(
$array AS $key=>$value){

        
$curway[$level] = "[".(!is_int($key)?"'$key'":$key)."]";
        if(
$key === $needle_key) {
            if (
$levelsfalse) {
                foreach (
$levelsfalse as $level) unset($curway[$level]);
            }
            return 
implode('',$curway);
        }
        if(
is_array($value)){
            if( (
$result get_way($needle_key,$value$curway$level+1,$levelsfalse)) !== false)
            return 
$result;
        }
    }
    
$levelsfalse[] = $level;
    return 
false;
}

function 
printArray$a ,$count=NULL){


    
$count = (isset($count)) ? ++$count 0;
    
$colors = array('#555555','#888888','#BBBBBB','#EEEEEE','#FFFFFF');
    if (
$count count($colors)) {
        
$ccount $count%count($colors);
    } else 
$ccount $count;

    if (!
is_array($a)) {
        echo 
"Passed argument is not an array!<p>";
        return;
    }

    echo 
"<table id=\"result\" border=1 cellpadding=0 cellspacing=0 bgcolor=$colors[$ccount]>";

    while(list(
$k$v) = each($a)) {
        echo 
"<tr><td style='padding:1em'>$k</td><td style='padding:1em'>$v</td></tr>\n";
        if (
is_array($v)) {
            echo 
"<tr><td> </td><td>";
            
printArray($v,$count);
            echo 
"</td></tr>\n";
        }
    }
    echo 
"</table>";
    
$count--;
}

function 
assign_blocks_to_ids($ar) {
    foreach (
$ar as $bid=>$bdata) {
        foreach (
$bdata as $bpos=>$rec) {
            
$return[$rec['id']] = "block:$bid,record:$bpos";
        }
    }
    return 
$return;
}

function 
make_index_record($records,$selects) {
        
$diff array_diff(array_keys($records),$selects);
        foreach (
$diff as $t) { unset($records[$t]); }
        return 
$records;
}
?>
</pre>
</body>
</html>