3v4l.org

run code in 300+ PHP versions simultaneously
<?php $rb = new RBTree; $inputs = array(); for ($i = 0; $i <= 100; ++$i) { $key = mt_rand(); $value = mt_rand(); $rb->put($key, $value); $inputs[] = $key; } for ($i = 0; $i <= 100; ++$i) { $key = mt_rand(0, 100); var_dump($key, $rb->get($key)); echo "\n"; } var_dump(101, $rb->get(101)); class Node { public $color; public $key; public $value; public $left; public $right; public function __construct($key, $value, $color) { $this->key = $key; $this->value = $value; $this->color = $color; } public function compare($key) { if ($this->key < $key) return -1; elseif ($this->key > $key) return 1; else return 0; } } class RBTree { const RED = true; const BLACK = false; private $root; public function isEmpty() { return $this->root == null; } public function put($key, $value) { $this->root = $this->insert($this->root, (int)$key, $value); $this->root->color = self::BLACK; } public function get($key) { $x = $this->search($this->root, (int)$key); return $x ? $x->value : null; } private function isRed($h) { return $h ? $h->color : false; } private function insert($x, $key, $value) { if (!$x) return new Node($key, $value, self::RED); $cmp = $x->compare($key); if ($cmp > 0) $x->right = $this->insert($x->right, $key, $value); elseif ($cmp < 0) $x->left = $this->insert($x->left, $key, $value); else $x->value = $value; if ($this->isRed($x->right) && !$this->isRed($x->left)) $x = $this->rotateLeft($x); if ($this->isRed($x->left) && $this->isRed($x->left->left)) $x = $this->rotateRight($x); if ($this->isRed($x->left) && $this->isRed($x->right)) $this->flipColors($x); return $x; } private function search($x, $key) { while ($x) { $cmp = $x->compare($key); if ($cmp > 0) $x = $x->right; elseif ($cmp < 0) $x = $x->left; else return $x; } return null; } private function flipColors($h) { $h->color = !$h->color; $h->left->color = !$h->left->color; $h->right->color = $h->right->color; } private function rotateLeft($h) { $x = $h->right; $h->right = $x->left; $x->left = $h; $x->color = $x->left->color; $x->left->color = self::RED; return $x; } private function rotateRight($h) { $x = $h->left; $h->left = $x->right; $x->right = $h; $x->color = $x->right->color; $x->right->color = self::RED; return $x; } }
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 42) Position 1 = 19
Branch analysis from position: 19
2 jumps found. (Code = 44) Position 1 = 21, Position 2 = 6
Branch analysis from position: 21
1 jumps found. (Code = 42) Position 1 = 37
Branch analysis from position: 37
2 jumps found. (Code = 44) Position 1 = 39, Position 2 = 23
Branch analysis from position: 39
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 23
2 jumps found. (Code = 44) Position 1 = 39, Position 2 = 23
Branch analysis from position: 39
Branch analysis from position: 23
Branch analysis from position: 6
2 jumps found. (Code = 44) Position 1 = 21, Position 2 = 6
Branch analysis from position: 21
Branch analysis from position: 6
filename:       /in/oQJ50
function name:  (null)
number of ops:  47
compiled vars:  !0 = $rb, !1 = $inputs, !2 = $i, !3 = $key, !4 = $value
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
    2     0  E >   NEW                                              $5      'RBTree'
          1        DO_FCALL                                      0          
          2        ASSIGN                                                   !0, $5
    3     3        ASSIGN                                                   !1, <array>
    5     4        ASSIGN                                                   !2, 0
          5      > JMP                                                      ->19
    6     6    >   INIT_FCALL                                               'mt_rand'
          7        DO_ICALL                                         $10     
          8        ASSIGN                                                   !3, $10
    7     9        INIT_FCALL                                               'mt_rand'
         10        DO_ICALL                                         $12     
         11        ASSIGN                                                   !4, $12
    8    12        INIT_METHOD_CALL                                         !0, 'put'
         13        SEND_VAR_EX                                              !3
         14        SEND_VAR_EX                                              !4
         15        DO_FCALL                                      0          
    9    16        ASSIGN_DIM                                               !1
         17        OP_DATA                                                  !3
    5    18        PRE_INC                                                  !2
         19    >   IS_SMALLER_OR_EQUAL                                      !2, 100
         20      > JMPNZ                                                    ~17, ->6
   12    21    >   ASSIGN                                                   !2, 0
         22      > JMP                                                      ->37
   13    23    >   INIT_FCALL                                               'mt_rand'
         24        SEND_VAL                                                 0
         25        SEND_VAL                                                 100
         26        DO_ICALL                                         $19     
         27        ASSIGN                                                   !3, $19
   14    28        INIT_FCALL                                               'var_dump'
         29        SEND_VAR                                                 !3
         30        INIT_METHOD_CALL                                         !0, 'get'
         31        SEND_VAR_EX                                              !3
         32        DO_FCALL                                      0  $21     
         33        SEND_VAR                                                 $21
         34        DO_ICALL                                                 
   15    35        ECHO                                                     '%0A'
   12    36        PRE_INC                                                  !2
         37    >   IS_SMALLER_OR_EQUAL                                      !2, 100
         38      > JMPNZ                                                    ~24, ->23
   17    39    >   INIT_FCALL                                               'var_dump'
         40        SEND_VAL                                                 101
         41        INIT_METHOD_CALL                                         !0, 'get'
         42        SEND_VAL_EX                                              101
         43        DO_FCALL                                      0  $25     
         44        SEND_VAR                                                 $25
         45        DO_ICALL                                                 
  124    46      > RETURN                                                   1

Class Node:
Function __construct:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  __construct
number of ops:  10
compiled vars:  !0 = $key, !1 = $value, !2 = $color
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   27     0  E >   RECV                                             !0      
          1        RECV                                             !1      
          2        RECV                                             !2      
   29     3        ASSIGN_OBJ                                               'key'
          4        OP_DATA                                                  !0
   30     5        ASSIGN_OBJ                                               'value'
          6        OP_DATA                                                  !1
   31     7        ASSIGN_OBJ                                               'color'
          8        OP_DATA                                                  !2
   32     9      > RETURN                                                   null

End of function __construct

Function compare:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 4, Position 2 = 6
Branch analysis from position: 4
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 6
2 jumps found. (Code = 43) Position 1 = 9, Position 2 = 11
Branch analysis from position: 9
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 11
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  compare
number of ops:  13
compiled vars:  !0 = $key
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   34     0  E >   RECV                                             !0      
   36     1        FETCH_OBJ_R                                      ~1      'key'
          2        IS_SMALLER                                               ~1, !0
          3      > JMPZ                                                     ~2, ->6
          4    > > RETURN                                                   -1
          5*       JMP                                                      ->12
   37     6    >   FETCH_OBJ_R                                      ~3      'key'
          7        IS_SMALLER                                               !0, ~3
          8      > JMPZ                                                     ~4, ->11
          9    > > RETURN                                                   1
         10*       JMP                                                      ->12
   38    11    > > RETURN                                                   0
   39    12*     > RETURN                                                   null

End of function compare

End of class Node.

Class RBTree:
Function isempty:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  isEmpty
number of ops:  4
compiled vars:  none
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   51     0  E >   FETCH_OBJ_R                                      ~0      'root'
          1        IS_EQUAL                                         ~1      ~0, null
          2      > RETURN                                                   ~1
   52     3*     > RETURN                                                   null

End of function isempty

Function put:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  put
number of ops:  16
compiled vars:  !0 = $key, !1 = $value
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   54     0  E >   RECV                                             !0      
          1        RECV                                             !1      
   56     2        INIT_METHOD_CALL                                         'insert'
          3        CHECK_FUNC_ARG                                           
          4        FETCH_OBJ_FUNC_ARG                               $3      'root'
          5        SEND_FUNC_ARG                                            $3
          6        CAST                                          4  ~4      !0
          7        SEND_VAL_EX                                              ~4
          8        SEND_VAR_EX                                              !1
          9        DO_FCALL                                      0  $5      
         10        ASSIGN_OBJ                                               'root'
         11        OP_DATA                                                  $5
   57    12        FETCH_OBJ_W                                      $6      'root'
         13        ASSIGN_OBJ                                               $6, 'color'
         14        OP_DATA                                                  <false>
   58    15      > RETURN                                                   null

End of function put

Function get:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 10, Position 2 = 13
Branch analysis from position: 10
1 jumps found. (Code = 42) Position 1 = 14
Branch analysis from position: 14
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 13
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  get
number of ops:  16
compiled vars:  !0 = $key, !1 = $x
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   60     0  E >   RECV                                             !0      
   62     1        INIT_METHOD_CALL                                         'search'
          2        CHECK_FUNC_ARG                                           
          3        FETCH_OBJ_FUNC_ARG                               $2      'root'
          4        SEND_FUNC_ARG                                            $2
          5        CAST                                          4  ~3      !0
          6        SEND_VAL_EX                                              ~3
          7        DO_FCALL                                      0  $4      
          8        ASSIGN                                                   !1, $4
   63     9      > JMPZ                                                     !1, ->13
         10    >   FETCH_OBJ_R                                      ~6      !1, 'value'
         11        QM_ASSIGN                                        ~7      ~6
         12      > JMP                                                      ->14
         13    >   QM_ASSIGN                                        ~7      null
         14    > > RETURN                                                   ~7
   64    15*     > RETURN                                                   null

End of function get

Function isred:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 2, Position 2 = 5
Branch analysis from position: 2
1 jumps found. (Code = 42) Position 1 = 6
Branch analysis from position: 6
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 5
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  isRed
number of ops:  8
compiled vars:  !0 = $h
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   66     0  E >   RECV                                             !0      
   68     1      > JMPZ                                                     !0, ->5
          2    >   FETCH_OBJ_R                                      ~1      !0, 'color'
          3        QM_ASSIGN                                        ~2      ~1
          4      > JMP                                                      ->6
          5    >   QM_ASSIGN                                        ~2      <false>
          6    > > RETURN                                                   ~2
   69     7*     > RETURN                                                   null

End of function isred

Function insert:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 5, Position 2 = 11
Branch analysis from position: 5
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 11
2 jumps found. (Code = 43) Position 1 = 17, Position 2 = 26
Branch analysis from position: 17
1 jumps found. (Code = 42) Position 1 = 39
Branch analysis from position: 39
2 jumps found. (Code = 46) Position 1 = 44, Position 2 = 50
Branch analysis from position: 44
2 jumps found. (Code = 43) Position 1 = 51, Position 2 = 55
Branch analysis from position: 51
2 jumps found. (Code = 46) Position 1 = 60, Position 2 = 66
Branch analysis from position: 60
2 jumps found. (Code = 43) Position 1 = 67, Position 2 = 71
Branch analysis from position: 67
2 jumps found. (Code = 46) Position 1 = 76, Position 2 = 81
Branch analysis from position: 76
2 jumps found. (Code = 43) Position 1 = 82, Position 2 = 85
Branch analysis from position: 82
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 85
Branch analysis from position: 81
Branch analysis from position: 71
Branch analysis from position: 66
Branch analysis from position: 55
Branch analysis from position: 50
Branch analysis from position: 26
2 jumps found. (Code = 43) Position 1 = 28, Position 2 = 37
Branch analysis from position: 28
1 jumps found. (Code = 42) Position 1 = 39
Branch analysis from position: 39
Branch analysis from position: 37
2 jumps found. (Code = 46) Position 1 = 44, Position 2 = 50
Branch analysis from position: 44
Branch analysis from position: 50
filename:       /in/oQJ50
function name:  insert
number of ops:  87
compiled vars:  !0 = $x, !1 = $key, !2 = $value, !3 = $cmp
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   71     0  E >   RECV                                             !0      
          1        RECV                                             !1      
          2        RECV                                             !2      
   73     3        BOOL_NOT                                         ~4      !0
          4      > JMPZ                                                     ~4, ->11
          5    >   NEW                                              $5      'Node'
          6        SEND_VAR_EX                                              !1
          7        SEND_VAR_EX                                              !2
          8        SEND_VAL_EX                                              <true>
          9        DO_FCALL                                      0          
         10      > RETURN                                                   $5
   75    11    >   INIT_METHOD_CALL                                         !0, 'compare'
         12        SEND_VAR_EX                                              !1
         13        DO_FCALL                                      0  $7      
         14        ASSIGN                                                   !3, $7
   76    15        IS_SMALLER                                               0, !3
         16      > JMPZ                                                     ~9, ->26
         17    >   INIT_METHOD_CALL                                         'insert'
         18        FETCH_OBJ_R                                      ~11     !0, 'right'
         19        SEND_VAL                                                 ~11
         20        SEND_VAR                                                 !1
         21        SEND_VAR                                                 !2
         22        DO_FCALL                                      0  $12     
         23        ASSIGN_OBJ                                               !0, 'right'
         24        OP_DATA                                                  $12
         25      > JMP                                                      ->39
   77    26    >   IS_SMALLER                                               !3, 0
         27      > JMPZ                                                     ~13, ->37
         28    >   INIT_METHOD_CALL                                         'insert'
         29        FETCH_OBJ_R                                      ~15     !0, 'left'
         30        SEND_VAL                                                 ~15
         31        SEND_VAR                                                 !1
         32        SEND_VAR                                                 !2
         33        DO_FCALL                                      0  $16     
         34        ASSIGN_OBJ                                               !0, 'left'
         35        OP_DATA                                                  $16
         36      > JMP                                                      ->39
   78    37    >   ASSIGN_OBJ                                               !0, 'value'
         38        OP_DATA                                                  !2
   80    39    >   INIT_METHOD_CALL                                         'isRed'
         40        FETCH_OBJ_R                                      ~18     !0, 'right'
         41        SEND_VAL                                                 ~18
         42        DO_FCALL                                      0  $19     
         43      > JMPZ_EX                                          ~20     $19, ->50
         44    >   INIT_METHOD_CALL                                         'isRed'
         45        FETCH_OBJ_R                                      ~21     !0, 'left'
         46        SEND_VAL                                                 ~21
         47        DO_FCALL                                      0  $22     
         48        BOOL_NOT                                         ~23     $22
         49        BOOL                                             ~20     ~23
         50    > > JMPZ                                                     ~20, ->55
         51    >   INIT_METHOD_CALL                                         'rotateLeft'
         52        SEND_VAR_EX                                              !0
         53        DO_FCALL                                      0  $24     
         54        ASSIGN                                                   !0, $24
   81    55    >   INIT_METHOD_CALL                                         'isRed'
         56        FETCH_OBJ_R                                      ~26     !0, 'left'
         57        SEND_VAL                                                 ~26
         58        DO_FCALL                                      0  $27     
         59      > JMPZ_EX                                          ~28     $27, ->66
         60    >   INIT_METHOD_CALL                                         'isRed'
         61        FETCH_OBJ_R                                      ~29     !0, 'left'
         62        FETCH_OBJ_R                                      ~30     ~29, 'left'
         63        SEND_VAL                                                 ~30
         64        DO_FCALL                                      0  $31     
         65        BOOL                                             ~28     $31
         66    > > JMPZ                                                     ~28, ->71
         67    >   INIT_METHOD_CALL                                         'rotateRight'
         68        SEND_VAR_EX                                              !0
         69        DO_FCALL                                      0  $32     
         70        ASSIGN                                                   !0, $32
   82    71    >   INIT_METHOD_CALL                                         'isRed'
         72        FETCH_OBJ_R                                      ~34     !0, 'left'
         73        SEND_VAL                                                 ~34
         74        DO_FCALL                                      0  $35     
         75      > JMPZ_EX                                          ~36     $35, ->81
         76    >   INIT_METHOD_CALL                                         'isRed'
         77        FETCH_OBJ_R                                      ~37     !0, 'right'
         78        SEND_VAL                                                 ~37
         79        DO_FCALL                                      0  $38     
         80        BOOL                                             ~36     $38
         81    > > JMPZ                                                     ~36, ->85
         82    >   INIT_METHOD_CALL                                         'flipColors'
         83        SEND_VAR_EX                                              !0
         84        DO_FCALL                                      0          
   84    85    > > RETURN                                                   !0
   85    86*     > RETURN                                                   null

End of function insert

Function search:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 42) Position 1 = 18
Branch analysis from position: 18
2 jumps found. (Code = 44) Position 1 = 19, Position 2 = 3
Branch analysis from position: 19
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 3
2 jumps found. (Code = 43) Position 1 = 9, Position 2 = 12
Branch analysis from position: 9
1 jumps found. (Code = 42) Position 1 = 18
Branch analysis from position: 18
Branch analysis from position: 12
2 jumps found. (Code = 43) Position 1 = 14, Position 2 = 17
Branch analysis from position: 14
1 jumps found. (Code = 42) Position 1 = 18
Branch analysis from position: 18
Branch analysis from position: 17
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  search
number of ops:  21
compiled vars:  !0 = $x, !1 = $key, !2 = $cmp
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   87     0  E >   RECV                                             !0      
          1        RECV                                             !1      
   89     2      > JMP                                                      ->18
   90     3    >   INIT_METHOD_CALL                                         !0, 'compare'
          4        SEND_VAR_EX                                              !1
          5        DO_FCALL                                      0  $3      
          6        ASSIGN                                                   !2, $3
   91     7        IS_SMALLER                                               0, !2
          8      > JMPZ                                                     ~5, ->12
          9    >   FETCH_OBJ_R                                      ~6      !0, 'right'
         10        ASSIGN                                                   !0, ~6
         11      > JMP                                                      ->18
   92    12    >   IS_SMALLER                                               !2, 0
         13      > JMPZ                                                     ~8, ->17
         14    >   FETCH_OBJ_R                                      ~9      !0, 'left'
         15        ASSIGN                                                   !0, ~9
         16      > JMP                                                      ->18
   93    17    > > RETURN                                                   !0
   89    18    > > JMPNZ                                                    !0, ->3
   95    19    > > RETURN                                                   null
   96    20*     > RETURN                                                   null

End of function search

Function flipcolors:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  flipColors
number of ops:  17
compiled vars:  !0 = $h
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   98     0  E >   RECV                                             !0      
  100     1        FETCH_OBJ_R                                      ~2      !0, 'color'
          2        BOOL_NOT                                         ~3      ~2
          3        ASSIGN_OBJ                                               !0, 'color'
          4        OP_DATA                                                  ~3
  101     5        FETCH_OBJ_R                                      ~6      !0, 'left'
          6        FETCH_OBJ_R                                      ~7      ~6, 'color'
          7        BOOL_NOT                                         ~8      ~7
          8        FETCH_OBJ_W                                      $4      !0, 'left'
          9        ASSIGN_OBJ                                               $4, 'color'
         10        OP_DATA                                                  ~8
  102    11        FETCH_OBJ_R                                      ~11     !0, 'right'
         12        FETCH_OBJ_R                                      ~12     ~11, 'color'
         13        FETCH_OBJ_W                                      $9      !0, 'right'
         14        ASSIGN_OBJ                                               $9, 'color'
         15        OP_DATA                                                  ~12
  103    16      > RETURN                                                   null

End of function flipcolors

Function rotateleft:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  rotateLeft
number of ops:  17
compiled vars:  !0 = $h, !1 = $x
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  105     0  E >   RECV                                             !0      
  107     1        FETCH_OBJ_R                                      ~2      !0, 'right'
          2        ASSIGN                                                   !1, ~2
  108     3        FETCH_OBJ_R                                      ~5      !1, 'left'
          4        ASSIGN_OBJ                                               !0, 'right'
          5        OP_DATA                                                  ~5
  109     6        ASSIGN_OBJ                                               !1, 'left'
          7        OP_DATA                                                  !0
  110     8        FETCH_OBJ_R                                      ~8      !1, 'left'
          9        FETCH_OBJ_R                                      ~9      ~8, 'color'
         10        ASSIGN_OBJ                                               !1, 'color'
         11        OP_DATA                                                  ~9
  111    12        FETCH_OBJ_W                                      $10     !1, 'left'
         13        ASSIGN_OBJ                                               $10, 'color'
         14        OP_DATA                                                  <true>
  112    15      > RETURN                                                   !1
  113    16*     > RETURN                                                   null

End of function rotateleft

Function rotateright:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/oQJ50
function name:  rotateRight
number of ops:  17
compiled vars:  !0 = $h, !1 = $x
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  115     0  E >   RECV                                             !0      
  117     1        FETCH_OBJ_R                                      ~2      !0, 'left'
          2        ASSIGN                                                   !1, ~2
  118     3        FETCH_OBJ_R                                      ~5      !1, 'right'
          4        ASSIGN_OBJ                                               !0, 'left'
          5        OP_DATA                                                  ~5
  119     6        ASSIGN_OBJ                                               !1, 'right'
          7        OP_DATA                                                  !0
  120     8        FETCH_OBJ_R                                      ~8      !1, 'right'
          9        FETCH_OBJ_R                                      ~9      ~8, 'color'
         10        ASSIGN_OBJ                                               !1, 'color'
         11        OP_DATA                                                  ~9
  121    12        FETCH_OBJ_W                                      $10     !1, 'right'
         13        ASSIGN_OBJ                                               $10, 'color'
         14        OP_DATA                                                  <true>
  122    15      > RETURN                                                   !1
  123    16*     > RETURN                                                   null

End of function rotateright

End of class RBTree.

Generated using Vulcan Logic Dumper, using php 8.0.0


preferences:
149.3 ms | 1424 KiB | 17 Q