gistfile1.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

//#define DEBUG 
#ifndef DEBUG 
#define DEBUG 0
#endif

typedef struct partialSum {
      int index; // for convient
      int sum;  // partial sum for i and nodes in left tree
      // struct partialSum * left, *right;
}PartialSum; 

#define PartialParent(i) (((i)-1)/2)
#define PartialLeft(p)   (p*2+1)
#define PartialRight(p)  (p*2+2)


int* test_data =NULL;

PartialSum inorderVisit ( PartialSum* tree, int index, int length,int* data ,int current) {
// notes on return value:
// use ret.index as the number of nodes in this sub-tree
// use ret.sum as the sum of the whole sub-tree
      PartialSum ret = {0,0} ; 
      PartialSum viewedLeft  = {.index=0, .sum=0} ; 
      PartialSum viewedRight = {.index=0, .sum=0} ;
      
      if (PartialLeft(index) < length) {
            viewedLeft = inorderVisit ( tree, PartialLeft(index), length, data,current);            
            current += viewedLeft.index;
      }
      
      tree[index].index = current;
      tree[index].sum   = data[current] + viewedLeft.sum;
      
      if (DEBUG) {
            int  d= tree[index].sum;
            printf ("%d, ",d);
      }

      current +=1;

      if (PartialRight(index) < length) {
            viewedRight = inorderVisit( tree, PartialRight(index), length, data,current);
            current += viewedRight.index;
      }
      ret.index = (1+ viewedLeft.index + viewedRight.index);
      ret.sum   = tree[index].sum + viewedRight.sum;
      return ret;
}

PartialSum* initTree (int* data, int length){
      PartialSum* tree = malloc(length * sizeof(PartialSum));
      inorderVisit (tree,0,length,data,0);
      return tree;
}


int findPartialSum (PartialSum* tree, int k ) {
      int sum=0;
      int point=0;
      while (tree[point].index != k ) {
            if (tree[point].index > k) {
                  point = PartialLeft (point);
            }
            else {
                  sum += tree[point].sum;
                  point = PartialRight (point);
            }
      }
      sum += tree[point].sum;
      return sum;

}

void addPartialSum (PartialSum* tree, int k, int value) {
      int point =0;
      while (tree[point].index != k) {
            if (tree[point].index > k) {
                  tree[point].sum += value;
                  point = PartialLeft (point);
            }
            else {
                  point = PartialRight (point);
            }
      }
      tree[point].sum +=value;
}

int checkAll (PartialSum * tree, int* data, int len,const char* test) {
      int i=0;
      int sum;
      int pass=1;

      for (i=0,sum=0; i<len; i++) {
            sum += test_data[i];
            if ( sum != findPartialSum(tree,i)) {
                  pass=0; break ;
            }
      }
      if (pass) printf ("%s : PASS\n",test);
      else printf ("%s : FAILED\n",test);
      return pass;
}

void randomTest(PartialSum* tree, int* data, int len, int times) {
      int i=0;
      char testName[100];

      srand(time(NULL));

      if (!checkAll (tree, data, len,"init"))  return;

      for (i=0; i< times; i++){
            int k = rand()%len;
            int v = rand()%20;
            test_data[k] +=v;
            addPartialSum(tree,k,v);
            sprintf(testName, "No %d (%d,%d)",i+1,k,v);
            if (!checkAll (tree, data,len, testName)) break;
      }
      if (i==times) printf ("\n %d tests all pass!\n",times);
      return ;
}


int main (int argc, char** argv) {
      int len ;
      int i;
      PartialSum * tree;

      sscanf(argv[1],"%d",&len);
      
      test_data = malloc ( len* sizeof(int));
      for (i=0; i<len; i++) {
            test_data[i]=1;

      }

      tree= initTree(test_data, len);
      
      randomTest(tree,test_data,len,30);

      return 0;
}