up

A priority search queue and LRU cache.
git clone git://git.jtobin.io/up.git
Log | Files | Refs

up_qor_rbal.c (4044B)

      1 #include "all.h"
      2 
      3 u3_noun
      4 _rrdub(u3_noun n_a, u3_noun l_a, u3_noun m_a, u3_noun r_a)
      5 {
      6   if ( c3n == u3du(l_a) ) {
      7     return u3m_bail(c3__exit);
      8   }
      9 
     10   u3_noun p_l_a = u3t(u3t(l_a));
     11   u3_noun hol = u3h(l_a);
     12 
     13   if ( c3n == u3ud(hol) ) {
     14     return u3m_bail(c3__exit);
     15   }
     16   else switch ( hol ) {
     17     default:
     18       return u3m_bail(c3__exit);
     19 
     20     case c3__llos: {
     21       u3_noun n_p_l_a, l_p_l_a, m_p_l_a, r_p_l_a;
     22       u3x_qual(p_l_a, &n_p_l_a, &l_p_l_a, &m_p_l_a, &r_p_l_a);
     23 
     24       u3_noun pre = u3qdu_qor_llsin(n_p_l_a, l_p_l_a, m_p_l_a, r_p_l_a);
     25       u3_noun pro = u3qdu_qor_rrsin(n_a, pre, m_a, r_a);
     26 
     27       u3z(pre);
     28 
     29       return pro;
     30     }
     31 
     32     case c3__rlos: {
     33       u3_noun n_p_l_a, l_p_l_a, m_p_l_a, r_p_l_a;
     34       u3x_qual(p_l_a, &n_p_l_a, &l_p_l_a, &m_p_l_a, &r_p_l_a);
     35 
     36       u3_noun pre = u3qdu_qor_rlsin(n_p_l_a, l_p_l_a, m_p_l_a, r_p_l_a);
     37       u3_noun pro = u3qdu_qor_rrsin(n_a, pre, m_a, r_a);
     38 
     39       u3z(pre);
     40 
     41       return pro;
     42     }
     43   }
     44 }
     45 
     46 u3_noun
     47 _rldub(u3_noun n_a, u3_noun l_a, u3_noun m_a, u3_noun r_a)
     48 {
     49   if ( c3n == u3du(r_a) ) {
     50     return u3m_bail(c3__exit);
     51   }
     52 
     53   u3_noun p_r_a = u3t(u3t(r_a));
     54   u3_noun hor = u3h(r_a);
     55 
     56   if ( c3n == u3ud(hor) ) {
     57     return u3m_bail(c3__exit);
     58   }
     59   else switch ( hor ) {
     60     default:
     61       return u3m_bail(c3__exit);
     62 
     63     case c3__llos: {
     64       u3_noun n_p_r_a, l_p_r_a, m_p_r_a, r_p_r_a;
     65       u3x_qual(p_r_a, &n_p_r_a, &l_p_r_a, &m_p_r_a, &r_p_r_a);
     66 
     67       u3_noun pre = u3qdu_qor_lrsin(n_p_r_a, l_p_r_a, m_p_r_a, r_p_r_a);
     68       u3_noun pro = u3qdu_qor_rlsin(n_a, l_a, m_a, pre);
     69 
     70       u3z(pre);
     71 
     72       return pro;
     73     }
     74 
     75     case c3__rlos: {
     76       u3_noun n_p_r_a, l_p_r_a, m_p_r_a, r_p_r_a;
     77       u3x_qual(p_r_a, &n_p_r_a, &l_p_r_a, &m_p_r_a, &r_p_r_a);
     78 
     79       u3_noun pre = u3qdu_qor_rrsin(n_p_r_a, l_p_r_a, m_p_r_a, r_p_r_a);
     80       u3_noun pro = u3qdu_qor_rlsin(n_a, l_a, m_a, pre);
     81 
     82       u3z(pre);
     83 
     84       return pro;
     85     }
     86   }
     87 }
     88 
     89 u3_noun
     90 _rrbal(u3_noun n, u3_noun l, u3_noun m, u3_noun r)
     91 {
     92   if ( c3n == u3du(l) ) {
     93     return u3m_bail(c3__exit);
     94   }
     95 
     96   u3_noun p_l = u3t(u3t(l));
     97 
     98   u3_noun n_p_l, l_p_l, m_p_l, r_p_l;
     99   u3x_qual(p_l, &n_p_l, &l_p_l, &m_p_l, &r_p_l);
    100 
    101   u3_atom sl = u3qdu_qor_size(l_p_l);
    102   u3_atom sr = u3qdu_qor_size(r_p_l);
    103 
    104   c3_o comp = u3qa_gth(sl, sr);
    105 
    106   u3z(sl);
    107   u3z(sr);
    108 
    109   return ( c3y == comp ) ? u3qdu_qor_rrsin(n, l, m, r) : _rrdub(n, l, m, r);
    110 }
    111 
    112 u3_noun
    113 _rlbal(u3_noun n, u3_noun l, u3_noun m, u3_noun r)
    114 {
    115   if ( c3n == u3du(r) ) {
    116     return u3m_bail(c3__exit);
    117   }
    118 
    119   u3_noun p_r = u3t(u3t(r));
    120 
    121   u3_noun n_p_r, l_p_r, m_p_r, r_p_r;
    122   u3x_qual(p_r, &n_p_r, &l_p_r, &m_p_r, &r_p_r);
    123 
    124   u3_atom sl = u3qdu_qor_size(l_p_r);
    125   u3_atom sr = u3qdu_qor_size(r_p_r);
    126 
    127   c3_o comp = u3qa_lth(sl, sr);
    128 
    129   u3z(sl);
    130   u3z(sr);
    131 
    132   return ( c3y == comp ) ? u3qdu_qor_rlsin(n, l, m, r) : _rldub(n, l, m, r);
    133 }
    134 
    135 u3_noun
    136 u3qdu_qor_rbal(u3_noun n_a, u3_noun l_a, u3_noun m_a, u3_noun r_a)
    137 {
    138   u3_atom sl = u3qdu_qor_size(l_a);
    139   u3_atom sr = u3qdu_qor_size(r_a);
    140   u3_atom s  = u3qa_add(sl, sr);
    141 
    142   if ( c3y == u3qa_lth(s, 2) ) {
    143     u3z(sl);
    144     u3z(sr);
    145     u3z(s);
    146 
    147     return u3qdu_qor_rlos(n_a, l_a, m_a, r_a);
    148   }
    149   else {
    150     u3z(s);
    151 
    152     u3_atom sm_l = u3qa_mul(4, sl);
    153 
    154     if ( c3y == u3qa_gth(sr, sm_l) ) {
    155       u3z(sl);
    156       u3z(sr);
    157       u3z(sm_l);
    158 
    159       return _rlbal(n_a, l_a, m_a, r_a);
    160     }
    161     else {
    162       u3z(sr);
    163       u3z(sm_l);
    164 
    165       u3_atom sm_r = u3qa_mul(4, sr);
    166 
    167       if ( c3y == u3qa_gth(sl, sm_r) ) {
    168         u3z(sl);
    169         u3z(sm_r);
    170 
    171         return _rrbal(n_a, l_a, m_a, r_a);
    172       }
    173       else {
    174         u3z(sl);
    175         u3z(sm_r);
    176 
    177         return u3qdu_qor_rlos(n_a, l_a, m_a, r_a);
    178       }
    179     }
    180   }
    181 }
    182 
    183 u3_noun
    184 u3wdu_qor_rbal(u3_noun cor)
    185 {
    186   u3_noun a;
    187 
    188   if ( (c3n == u3r_mean(cor, u3x_sam, &a, 0 )) ||
    189        (c3n == u3du(a)) )
    190   {
    191     return u3m_bail(c3__exit);
    192   } else {
    193     u3_noun n, l, m, r;
    194     u3x_qual(a, &n, &l, &m, &r);
    195 
    196     if ( (c3n == u3du(n)) || (c3n == u3ud(m)) ) {
    197       return u3m_bail(c3__exit);
    198     }
    199     else {
    200       return u3qdu_qor_rbal(n, l, m, r);
    201     }
    202   }
    203 }
    204 
    205