up

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

up_qor_lbal.c (4044B)

      1 #include "all.h"
      2 
      3 u3_noun
      4 _lrdub(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_lrsin(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_lrsin(n_a, pre, m_a, r_a);
     38 
     39       u3z(pre);
     40 
     41       return pro;
     42     }
     43   }
     44 }
     45 
     46 u3_noun
     47 _lldub(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_llsin(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_llsin(n_a, l_a, m_a, pre);
     81 
     82       u3z(pre);
     83 
     84       return pro;
     85     }
     86   }
     87 }
     88 
     89 u3_noun
     90 _lrbal(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_lrsin(n, l, m, r) : _lrdub(n, l, m, r);
    110 }
    111 
    112 u3_noun
    113 _llbal(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_llsin(n, l, m, r) : _lldub(n, l, m, r);
    133 }
    134 
    135 u3_noun
    136 u3qdu_qor_lbal(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 
    144     u3z(sl);
    145     u3z(sr);
    146     u3z(s);
    147 
    148     return u3qdu_qor_llos(n_a, l_a, m_a, r_a);
    149   }
    150   else {
    151     u3z(s);
    152 
    153     u3_atom sm_l = u3qa_mul(4, sl);
    154 
    155     if ( c3y == u3qa_gth(sr, sm_l) ) {
    156       u3z(sl);
    157       u3z(sr);
    158       u3z(sm_l);
    159 
    160       return _llbal(n_a, l_a, m_a, r_a);
    161     }
    162     else {
    163       u3z(sr);
    164       u3z(sm_l);
    165 
    166       u3_atom sm_r = u3qa_mul(4, sr);
    167 
    168       if ( c3y == u3qa_gth(sl, sm_r) ) {
    169         u3z(sl);
    170         u3z(sm_r);
    171 
    172         return _lrbal(n_a, l_a, m_a, r_a);
    173       }
    174       else {
    175         u3z(sl);
    176         u3z(sm_r);
    177 
    178         return u3qdu_qor_llos(n_a, l_a, m_a, r_a);
    179       }
    180     }
    181   }
    182 }
    183 
    184 u3_noun
    185 u3wdu_qor_lbal(u3_noun cor)
    186 {
    187   u3_noun a;
    188 
    189   if ( (c3n == u3r_mean(cor, u3x_sam, &a, 0 )) ||
    190        (c3n == u3du(a)) )
    191   {
    192     return u3m_bail(c3__exit);
    193   } else {
    194     u3_noun n, l, m, r;
    195     u3x_qual(a, &n, &l, &m, &r);
    196 
    197     if ( (c3n == u3du(n)) || (c3n == u3ud(m)) ) {
    198       return u3m_bail(c3__exit);
    199     }
    200     else {
    201       return u3qdu_qor_lbal(n, l, m, r);
    202     }
    203   }
    204 }
    205