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 = insert($x->right, $key, $value); elseif ($cmp < 0) $x->left = 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/7TjAY
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/7TjAY
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/7TjAY
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/7TjAY
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/7TjAY
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/7TjAY
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/7TjAY
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 = 27
Branch analysis from position: 17
1 jumps found. (Code = 42) Position 1 = 41
Branch analysis from position: 41
2 jumps found. (Code = 46) Position 1 = 46, Position 2 = 52
Branch analysis from position: 46
2 jumps found. (Code = 43) Position 1 = 53, Position 2 = 57
Branch analysis from position: 53
2 jumps found. (Code = 46) Position 1 = 62, Position 2 = 68
Branch analysis from position: 62
2 jumps found. (Code = 43) Position 1 = 69, Position 2 = 73
Branch analysis from position: 69
2 jumps found. (Code = 46) Position 1 = 78, Position 2 = 83
Branch analysis from position: 78
2 jumps found. (Code = 43) Position 1 = 84, Position 2 = 87
Branch analysis from position: 84
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 87
Branch analysis from position: 83
Branch analysis from position: 73
Branch analysis from position: 68
Branch analysis from position: 57
Branch analysis from position: 52
Branch analysis from position: 27
2 jumps found. (Code = 43) Position 1 = 29, Position 2 = 39
Branch analysis from position: 29
1 jumps found. (Code = 42) Position 1 = 41
Branch analysis from position: 41
Branch analysis from position: 39
2 jumps found. (Code = 46) Position 1 = 46, Position 2 = 52
Branch analysis from position: 46
Branch analysis from position: 52
filename:       /in/7TjAY
function name:  insert
number of ops:  89
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, ->27
         17    >   INIT_FCALL_BY_NAME                                       'insert'
         18        CHECK_FUNC_ARG                                           
         19        FETCH_OBJ_FUNC_ARG                               $11     !0, 'right'
         20        SEND_FUNC_ARG                                            $11
         21        SEND_VAR_EX                                              !1
         22        SEND_VAR_EX                                              !2
         23        DO_FCALL                                      0  $12     
         24        ASSIGN_OBJ                                               !0, 'right'
         25        OP_DATA                                                  $12
         26      > JMP                                                      ->41
   77    27    >   IS_SMALLER                                               !3, 0
         28      > JMPZ                                                     ~13, ->39
         29    >   INIT_FCALL_BY_NAME                                       'insert'
         30        CHECK_FUNC_ARG                                           
         31        FETCH_OBJ_FUNC_ARG                               $15     !0, 'left'
         32        SEND_FUNC_ARG                                            $15
         33        SEND_VAR_EX                                              !1
         34        SEND_VAR_EX                                              !2
         35        DO_FCALL                                      0  $16     
         36        ASSIGN_OBJ                                               !0, 'left'
         37        OP_DATA                                                  $16
         38      > JMP                                                      ->41
   78    39    >   ASSIGN_OBJ                                               !0, 'value'
         40        OP_DATA                                                  !2
   80    41    >   INIT_METHOD_CALL                                         'isRed'
         42        FETCH_OBJ_R                                      ~18     !0, 'right'
         43        SEND_VAL                                                 ~18
         44        DO_FCALL                                      0  $19     
         45      > JMPZ_EX                                          ~20     $19, ->52
         46    >   INIT_METHOD_CALL                                         'isRed'
         47        FETCH_OBJ_R                                      ~21     !0, 'left'
         48        SEND_VAL                                                 ~21
         49        DO_FCALL                                      0  $22     
         50        BOOL_NOT                                         ~23     $22
         51        BOOL                                             ~20     ~23
         52    > > JMPZ                                                     ~20, ->57
         53    >   INIT_METHOD_CALL                                         'rotateLeft'
         54        SEND_VAR_EX                                              !0
         55        DO_FCALL                                      0  $24     
         56        ASSIGN                                                   !0, $24
   81    57    >   INIT_METHOD_CALL                                         'isRed'
         58        FETCH_OBJ_R                                      ~26     !0, 'left'
         59        SEND_VAL                                                 ~26
         60        DO_FCALL                                      0  $27     
         61      > JMPZ_EX                                          ~28     $27, ->68
         62    >   INIT_METHOD_CALL                                         'isRed'
         63        FETCH_OBJ_R                                      ~29     !0, 'left'
         64        FETCH_OBJ_R                                      ~30     ~29, 'left'
         65        SEND_VAL                                                 ~30
         66        DO_FCALL                                      0  $31     
         67        BOOL                                             ~28     $31
         68    > > JMPZ                                                     ~28, ->73
         69    >   INIT_METHOD_CALL                                         'rotateRight'
         70        SEND_VAR_EX                                              !0
         71        DO_FCALL                                      0  $32     
         72        ASSIGN                                                   !0, $32
   82    73    >   INIT_METHOD_CALL                                         'isRed'
         74        FETCH_OBJ_R                                      ~34     !0, 'left'
         75        SEND_VAL                                                 ~34
         76        DO_FCALL                                      0  $35     
         77      > JMPZ_EX                                          ~36     $35, ->83
         78    >   INIT_METHOD_CALL                                         'isRed'
         79        FETCH_OBJ_R                                      ~37     !0, 'right'
         80        SEND_VAL                                                 ~37
         81        DO_FCALL                                      0  $38     
         82        BOOL                                             ~36     $38
         83    > > JMPZ                                                     ~36, ->87
         84    >   INIT_METHOD_CALL                                         'flipColors'
         85        SEND_VAR_EX                                              !0
         86        DO_FCALL                                      0          
   84    87    > > RETURN                                                   !0
   85    88*     > 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/7TjAY
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/7TjAY
function name:  flipColors
number of ops:  18
compiled vars:  !0 = $h
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   98     0  E >   RECV                                             !0      
  100     1        BOOL_NOT                                         ~2      !0
          2        FETCH_CONSTANT                                   ~3      'color'
          3        CONCAT                                           ~4      ~2, ~3
          4        ASSIGN_OBJ                                               !0, 'color'
          5        OP_DATA                                                  ~4
  101     6        FETCH_OBJ_R                                      ~7      !0, 'left'
          7        FETCH_OBJ_R                                      ~8      ~7, 'color'
          8        BOOL_NOT                                         ~9      ~8
          9        FETCH_OBJ_W                                      $5      !0, 'left'
         10        ASSIGN_OBJ                                               $5, 'color'
         11        OP_DATA                                                  ~9
  102    12        FETCH_OBJ_R                                      ~12     !0, 'right'
         13        FETCH_OBJ_R                                      ~13     ~12, 'color'
         14        FETCH_OBJ_W                                      $10     !0, 'right'
         15        ASSIGN_OBJ                                               $10, 'color'
         16        OP_DATA                                                  ~13
  103    17      > 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/7TjAY
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/7TjAY
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:
146.65 ms | 1424 KiB | 17 Q