fork(1) download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. typedef struct lazy_segment_node{
  5.   int lower_value;
  6.   int upper_value;
  7.  
  8.   unsigned char propagated;
  9.  
  10.   struct lazy_segment_node * left_child;
  11.   struct lazy_segment_node * right_child;
  12. } lazy_segment_node;
  13.  
  14. lazy_segment_node * initialize(lazy_segment_node ** mem, int lower_value, int upper_value){
  15.   lazy_segment_node * tmp = NULL;
  16.   if(mem != NULL)
  17.     tmp = *mem;
  18.   if(tmp == NULL)
  19.     tmp = malloc(sizeof(lazy_segment_node));
  20.   if(tmp == NULL)
  21.     return NULL;
  22.   tmp->lower_value = lower_value;
  23.   tmp->upper_value = upper_value;
  24.   tmp->propagated = 0;
  25.   tmp->left_child = NULL;
  26.   tmp->right_child = NULL;
  27.  
  28.   if(mem != NULL)
  29.     *mem = tmp;
  30.   return tmp;
  31. }
  32.  
  33. lazy_segment_node * accessErr(lazy_segment_node* node, int * error){
  34.   if(node == NULL){
  35.     if(error != NULL)
  36.       *error = 1;
  37.     return NULL;
  38.   }
  39.   if(node->propagated)
  40.     return node;
  41.  
  42.   if(node->upper_value == node->lower_value){
  43.     node->propagated = 1;
  44.     return node;
  45.   }
  46.   node->left_child = initialize(NULL,node->lower_value,(node->lower_value + node->upper_value)/2);
  47.   if(node->left_child == NULL){
  48.     if(error != NULL)
  49.       *error = 2;
  50.     return NULL;
  51.   }
  52.  
  53.   node->right_child = initialize(NULL,(node->lower_value + node->upper_value)/2 + 1,node->upper_value);
  54.   if(node->right_child == NULL){
  55.     free(node->left_child);
  56.     if(error != NULL)
  57.       *error = 3;
  58.     return NULL;
  59.   }  
  60.   node->propagated = 1;
  61.   return node;
  62. }
  63.  
  64. lazy_segment_node * access(lazy_segment_node* node){
  65.   return accessErr(node,NULL);
  66. }
  67.  
  68. void free_lazy_segment_tree(lazy_segment_node * root){
  69.   if(root == NULL)
  70.     return;
  71.   free_lazy_segment_tree(root->left_child);
  72.   free_lazy_segment_tree(root->right_child);
  73.   free(root);
  74. }
  75.  
  76. int main(){
  77.   lazy_segment_node * test = NULL;
  78.   initialize(&test,1,10);
  79.   printf("Lazy evaluation test\n");
  80.   printf("test->lower_value: %i\n",test->lower_value);
  81.   printf("test->upper_value: %i\n",test->upper_value);
  82.  
  83.   printf("\nNode not propagated\n");
  84.   printf("test->left_child: %p\n",test->left_child);
  85.   printf("test->right_child: %p\n",test->right_child);
  86.  
  87.   printf("\nNode propagated with access:\n");
  88.   printf("access(test)->left_child: %p\n",access(test)->left_child);
  89.   printf("access(test)->right_child: %p\n",access(test)->right_child);
  90.  
  91.   printf("\nNode propagated with access, but subchilds are not:\n");
  92.   printf("access(test)->left_child->left_child: %p\n",access(test)->left_child->left_child);
  93.   printf("access(test)->left_child->right_child: %p\n",access(test)->left_child->right_child);
  94.  
  95.   printf("\nCan use access on subchilds:\n");
  96.   printf("access(test->left_child)->left_child: %p\n",access(test->left_child)->left_child);
  97.   printf("access(test->left_child)->right_child: %p\n",access(test->left_child)->right_child);
  98.  
  99.   printf("\nIt's possible to chain:\n");
  100.   printf("access(access(access(test)->right_child)->right_child)->lower_value: %i\n",access(access(access(test)->right_child)->right_child)->lower_value);
  101.   printf("access(access(access(test)->right_child)->right_child)->upper_value: %i\n",access(access(access(test)->right_child)->right_child)->upper_value);
  102.  
  103.   free_lazy_segment_tree(test);
  104.  
  105.   return 0;
  106. }
Success #stdin #stdout 0.01s 1852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Lazy evaluation test
test->lower_value: 1
test->upper_value: 10

Node not propagated
test->left_child: (nil)
test->right_child: (nil)

Node propagated with access:
access(test)->left_child: 0x948e020
access(test)->right_child: 0x948e038

Node propagated with access, but subchilds are not:
access(test)->left_child->left_child: (nil)
access(test)->left_child->right_child: (nil)

Can use access on subchilds:
access(test->left_child)->left_child: 0x948e050
access(test->left_child)->right_child: 0x948e068

It's possible to chain:
access(access(access(test)->right_child)->right_child)->lower_value: 9
access(access(access(test)->right_child)->right_child)->upper_value: 10
https://ideone.com/bNVDx
language:
C (gcc 8.3)
created:
12 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!