fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef union {
  6.     int data;
  7.     int next[6]; //5 valori + separatore
  8. } node;
  9.  
  10. int size, capacity;
  11. node *trie;
  12.  
  13. int next;
  14.  
  15. void lookup_init()
  16. {
  17.     size = capacity = 1;
  18.     trie = (node *)calloc(sizeof(node), size);
  19. }
  20.  
  21. /**
  22.  * Verifica che una chiave esista.
  23.  *
  24.  * @return      -1 se non esiste, 0 se esiste (e poi dicono che non
  25.  *              rispetto gli standard)
  26.  */
  27. int lookup_exists(
  28.     const int kFirst,
  29.     const int kSecond,
  30.     const int kThird,
  31.     int* firstRow,
  32.     int* secondRow,
  33.     int* thirdRow
  34. ) {
  35.     next = 0;
  36.     for ( int i = 0; i < kFirst; i++ ) {
  37.         next = trie[next].next[firstRow[ i ]];
  38.         if(next == 0) return -1;
  39.     }
  40.     next = trie[next].next[5]; //separatore
  41.     for ( int i = 0; i < kSecond; i++ ) {
  42.         if(next == 0) return -1;
  43.         next = trie[next].next[secondRow[ i ]];
  44.     }
  45.     next = trie[next].next[5]; //separatore
  46.     for ( int i = 0; i < kThird; i++ ) {
  47.         if(next == 0) return -1;
  48.         next = trie[next].next[thirdRow[ i ]];
  49.     }
  50.     if(next == 0) return -1; 
  51.     return 0;
  52. }
  53.  
  54. int alloc() {
  55.     if(size == capacity) {
  56.         capacity *= 2;
  57.         trie = (node *)realloc(trie, sizeof(node)*capacity);
  58.     }
  59.     memset(&trie[size], 0, sizeof(node));
  60.     return size++;
  61. }
  62.  
  63. void lookup_update(
  64.     const int kFirst,
  65.     const int kSecond,
  66.     const int kThird,
  67.     int* firstRow,
  68.     int* secondRow,
  69.     int* thirdRow
  70. )
  71. {
  72.     int tmp;
  73.     next = 0;
  74.     for ( int i = 0; i < kFirst; i++ ) {
  75.         tmp = trie[next].next[firstRow[ i ]];
  76.         if(tmp == 0) {
  77.             tmp = alloc();
  78.             trie[next].next[firstRow[ i ]] = tmp;
  79.         }
  80.         next = tmp;
  81.     }
  82.     tmp = trie[next].next[5];
  83.     if(tmp == 0) {
  84.         tmp = alloc();
  85.         trie[next].next[5] = tmp;
  86.     }
  87.     next = tmp;
  88.     for ( int i = 0; i < kSecond; i++ ) {
  89.         tmp = trie[next].next[secondRow[ i ]];
  90.         if(tmp == 0) {
  91.             tmp = alloc();
  92.             trie[next].next[secondRow[ i ]] = tmp;
  93.         }
  94.         next = tmp;
  95.     }
  96.     tmp = trie[next].next[5];
  97.     if(tmp == 0) {
  98.         tmp = alloc();
  99.         trie[next].next[5] = tmp;
  100.     }
  101.     next = tmp;
  102.     for ( int i = 0; i < kThird; i++ ) {
  103.         tmp = trie[next].next[thirdRow[ i ]];
  104.         if(tmp == 0) {
  105.             tmp = alloc();
  106.             trie[next].next[thirdRow[ i ]] = tmp;
  107.         }
  108.         next = tmp;
  109.     }
  110.     ++(trie[next].data);  
  111. }
  112.  
  113. void lookup_free()
  114. {
  115.     free(trie);
  116. }
  117.  
  118. int main(void)
  119. {
  120.     /*
  121.         Ipotizzando di avere una tabella da 3 righe e 5 colonne:
  122.         +----+----+----+----+----+
  123.         |    |    |    |    |    |
  124.         +----+----+----+----+----+
  125.         |    |    |    |    |    |
  126.         +----+----+----+----+----+
  127.         |    |    |    |    |    |
  128.         +----+----+----+----+----+
  129.  
  130.         e di riempirla casualmente (popolandola da sinistra a destra con un
  131.         indice che corrisponde ad una lettera della array "ab")
  132.  
  133.         static char* ab[] = {
  134.             "az", "bd", "ce", "df", "ef", "fd", "gl"
  135.     */
  136.     int _1row[5];
  137.     int _2row[5];
  138.     int _3row[5];
  139.  
  140.     lookup_init();
  141.  
  142.     /*
  143.         Prima combinazione:
  144.         +----+----+----+----+----+
  145.         | az | bd | ce |    |    |
  146.         +----+----+----+----+----+
  147.         |    |    |    |    |    |
  148.         +----+----+----+----+----+
  149.         | df | ef |    |    |    |
  150.         +----+----+----+----+----+
  151.     */
  152.     _1row[0] = 0;
  153.     _1row[1] = 1;
  154.     _1row[2] = 2;
  155.     _3row[0] = 3;
  156.     _3row[1] = 4;
  157.     for ( int c = 0; c < 5; c++ ) {
  158.         /* Verifico che la combinazione esista già, se non esiste la creo
  159.            altrimenti aggiorno il campo "data".
  160.            In questo la prima combinazione avrà il campo "data" con il valore
  161.            4 (visto che incrementerà ad ogni "lookup_update") */
  162.         lookup_update( 3, 0, 2, _1row, _2row, _3row );
  163.     }
  164.  
  165.     /*
  166.         Seconda combinazione:
  167.         +----+----+----+----+----+
  168.         | az | bd |    |    |    |
  169.         +----+----+----+----+----+
  170.         | ce |    |    |    |    |
  171.         +----+----+----+----+----+
  172.         | df | ef |    |    |    |
  173.         +----+----+----+----+----+
  174.  
  175.         Campo "data" con valore 1.
  176.     */
  177.     _1row[0] = 0;
  178.     _1row[1] = 1;
  179.     _2row[0] = 2;
  180.     _3row[0] = 3;
  181.     _3row[1] = 4;
  182.     for ( int c = 0; c < 2; c++ ) {
  183.         lookup_update( 2, 1, 2, _1row, _2row, _3row );
  184.     }
  185.  
  186.     /*
  187.         Terza combinazione:
  188.         +----+----+----+----+----+
  189.         | az |    |    |    |    |
  190.         +----+----+----+----+----+
  191.         | bd | ce |    |    |    |
  192.         +----+----+----+----+----+
  193.         | df | ef |    |    |    |
  194.         +----+----+----+----+----+
  195.  
  196.         Campo "data" con valore 2.
  197.     */
  198.     _1row[0] = 0;
  199.     _2row[0] = 1;
  200.     _2row[1] = 2;
  201.     _3row[0] = 3;
  202.     _3row[1] = 4;
  203.     for ( int c = 0; c < 3; c++) {
  204.         lookup_update( 1, 2, 2, _1row, _2row, _3row );
  205.     }
  206.  
  207.     /*
  208.         Questa è sempre la seconda combinazione, perciò incrementa il campo
  209.         "data" di 15 valori.
  210.     */
  211.     _1row[0] = 0;
  212.     _1row[1] = 1;
  213.     _2row[0] = 2;
  214.     _3row[0] = 3;
  215.     _3row[1] = 4;
  216.     for ( int c = 0; c < 15; c++ ) {
  217.         lookup_update( 2, 1, 2, _1row, _2row, _3row );
  218.     }
  219.  
  220.     printf("%d", trie[next].data);
  221.  
  222.     lookup_free();
  223. }
Success #stdin #stdout 0s 9432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
17
https://ideone.com/oZ5sqU
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!