Crossings Minimization  1.0
Statistics.c
Go to the documentation of this file.
1 /**
2  * @file Statistics.c
3  * @brief
4  * Implements a Statistics class with methods for computing min, median,
5  * mean, max, and standard deviation.
6  *
7  * @author Matt Stallmann
8  * @date 2009/05/18
9  *
10  * Migrate changes back to C-Utilities
11  */
12 
13 #include "Statistics.h"
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <math.h>
17 #include <assert.h>
18 
19 /**
20  * Data invariant: the data array remains sorted in increasing order; this is
21  * obviously inefficient but this class is not intended for large data sets.
22  * The sorting is done via insertion sort, so it will be efficient if the
23  * data comes in increasing order.
24  */
25 
27 {
28 #ifdef TEST
29  printf( "-> init_statistics, size = %d\n", size );
30 #endif
31  Statistics s = (Statistics) calloc( 1, sizeof( struct statistics_struct ) );
32  s->array_size = size;
33  s->number_of_data_points = 0;
34  s->sum = 0.0;
35  s->data = (double *) calloc( size, sizeof( double ) );
36 #ifdef TEST
37  printf( "<- init_statistics, size = %d\n", size );
38 #endif
39  return s;
40 }
41 
42 double get_min( Statistics s ) { return s->data[0]; }
43 
45 {
46  if ( s->number_of_data_points % 2 == 0 )
47  // even
48  {
49  int end_of_first_half = (s->number_of_data_points - 1) / 2;
50  int start_of_second_half = s->number_of_data_points / 2;
51  return (s->data[ end_of_first_half ]
52  + s->data[ start_of_second_half ]) / 2;
53  }
54  else
55  // odd
56  {
57  return s->data[ s->number_of_data_points / 2 ];
58  }
59 }
60 
61 double get_mean( Statistics s ) { return s->sum / s->number_of_data_points; }
62 
63 double get_max( Statistics s ) { return s->data[ s->number_of_data_points - 1 ]; }
64 
66 {
67  double sum_of_squares = 0;
68  for ( int i = 0; i < s->number_of_data_points; i++ )
69  sum_of_squares += s->data[i] * s->data[i];
70  double mean = get_mean( s );
71  return sqrt( sum_of_squares / s->number_of_data_points
72  - mean * mean );
73 }
74 
76 { return s->number_of_data_points; }
77 
78 /**
79  * Initially
80  * - A[0] <= A[1] <= ... <= A[n] and there is room for one more item
81  * When insert is done
82  * - A[0] <= ... <= A[i] <= x == A[i+1] <= A[i+2] <= ... <= A[n+1]
83  * where the A[0] ... A[i] are as before and A[i+2] ... A[n+1] have the
84  * values of A[i+1] ... A[n]
85  */
86 static void insert( double x, double * A, int n )
87 {
88  int i = n;
89  while ( i >= 0 && x < A[i] )
90  {
91  A[i+1] = A[i];
92  i--;
93  }
94  A[i+1] = x;
95 }
96 
97 #ifdef TEST
98 static void print_data( Statistics s )
99 {
100  fprintf( stderr, "-----\n" );
101  fprintf( stderr, "%d |", s->number_of_data_points );
102  for ( int i = 0; i < s->number_of_data_points; i++ )
103  fprintf( stderr, " %5.2lf", s->data[i] );
104  fprintf( stderr, "\n" );
105  fprintf( stderr, "array_size = %d\n", s->array_size );
106  fprintf( stderr, "sum = %5.2lf\n", s->sum );
107  fprintf( stderr, "-----\n" );
108 }
109 #endif
110 
111 void add_data( Statistics s, double data_point )
112 {
113 #ifdef TEST
114  fprintf( stderr, "-> add_data, data_point = %5.2lf\n", data_point );
115  print_data( s );
116 #endif
117  assert( s->number_of_data_points < s->array_size );
118  s->sum += data_point;
119  insert( data_point, s->data, s->number_of_data_points - 1 );
121 #ifdef TEST
122  fprintf( stderr, "<- add_data, data_point = %5.2lf\n", data_point );
123  print_data( s );
124 #endif
125 }
126 
127 void print_statistics( Statistics s, FILE * output_stream, const char * format )
128 {
129  fprintf( output_stream, format, get_min(s) );
130  fprintf( output_stream, "\t" );
131  fprintf( output_stream, format, get_median(s) );
132  fprintf( output_stream, "\t" );
133  fprintf( output_stream, format, get_mean(s) );
134  fprintf( output_stream, "\t" );
135  fprintf( output_stream, format, get_max(s) );
136  fprintf( output_stream, "\t" );
137  fprintf( output_stream, format, get_standard_deviation(s) );
138  fprintf( output_stream, "\t" );
139  fprintf( output_stream, "%d", get_number_of_data_points(s) );
140 }
141 
143 {
144  assert( s != NULL );
145  if ( s->data != NULL ) free( s->data );
146  free( s );
147 }
148 
149 #ifdef TEST
150 
151 /**
152  * Simple test program. Reads the number of data points, followed by a list of
153  * the data items.
154  */
155 int main()
156 {
157  int n = 0;
158  scanf( "%d", &n );
159  Statistics s = init_statistics( n );
160  int i = 0;
161  for ( ; i < n ; i++ )
162  {
163  double data;
164  if ( scanf( "%lf", &data ) == EOF ) break;
165  add_data( s, data );
166  }
167 /* printf( "min = \t%5.2f\n", get_min( s ) ); */
168 /* printf( "med = \t%5.2f\n", get_median( s ) ); */
169 /* printf( "mean = \t%5.2f\n", get_mean( s ) ); */
170 /* printf( "max = \t%5.2f\n", get_max( s ) ); */
171 /* printf( "stdev = \t%5.2f\n", get_standard_deviation( s ) ); */
172 
173  printf( "Stats = \t" );
174  print_statistics( s, stdout, "%5.2lf" );
175  printf( "\n" );
176  free_statistics( s );
177 }
178 
179 #endif
180 
181 // [Last modified: 2009 05 19 at 13:05:11 GMT]
double get_median(Statistics s)
Definition: Statistics.c:44
void add_data(Statistics s, double data_point)
Definition: Statistics.c:111
Statistics init_statistics(int size)
Definition: Statistics.c:26
double get_max(Statistics s)
Definition: Statistics.c:63
Interface for a Statistics class with methods for computing min, median, mean, max, and standard deviation.
void print_statistics(Statistics s, FILE *output_stream, const char *format)
Definition: Statistics.c:127
struct statistics_struct * Statistics
double get_mean(Statistics s)
Definition: Statistics.c:61
double get_standard_deviation(Statistics s)
Definition: Statistics.c:65
int number_of_data_points
Definition: Statistics.h:20
double get_min(Statistics s)
Definition: Statistics.c:42
static void insert(double x, double *A, int n)
Definition: Statistics.c:86
void free_statistics(Statistics s)
Definition: Statistics.c:142
int get_number_of_data_points(Statistics s)
Definition: Statistics.c:75
int main(int argc, char *argv[])
Definition: add_edges.c:185