← Back to branch summary

~ubuntu-branches/ubuntu/lucid/igraph/lucid

« back to all changes in this revision

Viewing changes to src/igraph_psumtree.c

  • Committer: Bazaar Package Importer
  • Author(s): Mathieu Malaterre
  • Date: 2009-11-16 18:12:42 UTC
  • Revision ID: james.westby@ubuntu.com-20091116181242-mzv9p5fz9uj57xd1
Tags: upstream-0.5.3
Import upstream version 0.5.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/igraph_psumtree.c
 
1
/* -*- mode: C -*-  */
 
2
/* 
 
3
   IGraph library.
 
4
   Copyright (C) 2006 Elliot Paquette <Elliot.Paquette05@kzoo.edu>
 
5
   Kalamazoo College, 1200 Academy st, Kalamazoo, MI
 
6
 
 
7
   This program is free software; you can redistribute it and/or modify
 
8
   it under the terms of the GNU General Public License as published by
 
9
   the Free Software Foundation; either version 2 of the License, or
 
10
   (at your option) any later version.
 
11
   
 
12
   This program is distributed in the hope that it will be useful,
 
13
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
   GNU General Public License for more details.
 
16
   
 
17
   You should have received a copy of the GNU General Public License
 
18
   along with this program; if not, write to the Free Software
 
19
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
 
20
   02110-1301 USA
 
21
 
 
22
*/
 
23
 
 
24
#include "types.h"
 
25
#include "error.h"
 
26
#include "config.h"
 
27
 
 
28
#include <math.h>
 
29
#include <stdio.h>
 
30
 
 
31
double igraph_i_log2(double f) {
 
32
  return log(f) / log(2.0);
 
33
}
 
34
 
 
35
int igraph_psumtree_init(igraph_psumtree_t *t, long int size) {
 
36
  t->size=size;
 
37
  t->offset=pow(2, ceil(igraph_i_log2(size)))-1;
 
38
  IGRAPH_CHECK(igraph_vector_init((igraph_vector_t *)t, t->offset+t->size));
 
39
  return 0;
 
40
}
 
41
 
 
42
void igraph_psumtree_destroy(igraph_psumtree_t *t) {
 
43
  igraph_vector_destroy((igraph_vector_t *)t);
 
44
}
 
45
 
 
46
igraph_real_t igraph_psumtree_get(const igraph_psumtree_t *t, long int idx) {
 
47
  const igraph_vector_t *tree=&t->v;
 
48
  return VECTOR(*tree)[t->offset+idx];
 
49
}
 
50
 
 
51
int igraph_psumtree_search(const igraph_psumtree_t *t, long int *idx,
 
52
                           igraph_real_t search) {
 
53
  const igraph_vector_t *tree=&t->v;
 
54
  long int i = 1;
 
55
  long int size = igraph_vector_size(tree);
 
56
  
 
57
  while( 2*i+1 <= size) {
 
58
    if( search <= VECTOR(*tree)[i*2-1] ) {
 
59
      i <<= 1;  
 
60
    } else {
 
61
      search -= VECTOR(*tree)[i*2-1];
 
62
      i <<= 1;
 
63
      i += 1;
 
64
    }
 
65
  }
 
66
  if (2*i <= size) {
 
67
    i=2*i;
 
68
  }
 
69
 
 
70
  *idx = i-t->offset-1;
 
71
  return IGRAPH_SUCCESS;
 
72
}
 
73
 
 
74
int igraph_psumtree_update(igraph_psumtree_t *t, long int idx, 
 
75
                           igraph_real_t new_value) {
 
76
  const igraph_vector_t *tree=&t->v;
 
77
  igraph_real_t difference;
 
78
  
 
79
  idx = idx + t->offset+1;
 
80
  difference = new_value - VECTOR(*tree)[idx-1];
 
81
  
 
82
  while( idx >= 1 ) {
 
83
    VECTOR(*tree)[idx-1] += difference;
 
84
    idx >>= 1;
 
85
  }
 
86
  return IGRAPH_SUCCESS;        
 
87
}
 
88
 
 
89
long int igraph_psumtree_size(const igraph_psumtree_t *t) {
 
90
  return t->size;
 
91
}
 
92
 
 
93
igraph_real_t igraph_psumtree_sum(const igraph_psumtree_t *t) {
 
94
  return VECTOR(t->v)[0];
 
95
}