← Back to branch summary

~ubuntu-branches/ubuntu/quantal/genometools/quantal-backports

« back to all changes in this revision

Viewing changes to src/core/disc_distri.c

  • Committer: Package Import Robot
  • Author(s): Sascha Steinbiss
  • Date: 2012-07-09 14:10:23 UTC
  • Revision ID: package-import@ubuntu.com-20120709141023-juuu4spm6chqsf9o
Tags: upstream-1.4.1
Import upstream version 1.4.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/disc_distri.c
 
1
/*
 
2
  Copyright (c) 2006-2010 Gordon Gremme <gremme@zbh.uni-hamburg.de>
 
3
  Copyright (c)      2007 Stefan Kurtz <kurtz@zbh.uni-hamburg.de>
 
4
  Copyright (c)      2008 Thomas Jahns <Thomas.Jahns@gmx.net>
 
5
  Copyright (c) 2006-2008 Center for Bioinformatics, University of Hamburg
 
6
 
 
7
  Permission to use, copy, modify, and distribute this software for any
 
8
  purpose with or without fee is hereby granted, provided that the above
 
9
  copyright notice and this permission notice appear in all copies.
 
10
 
 
11
  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 
12
  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 
13
  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 
14
  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 
15
  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 
16
  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 
17
  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 
18
*/
 
19
 
 
20
#include <stdio.h>
 
21
#include "core/assert_api.h"
 
22
#include "core/disc_distri.h"
 
23
#include "core/ensure.h"
 
24
#include "core/hashmap-generic.h"
 
25
#include "core/ma.h"
 
26
#include "core/unused_api.h"
 
27
 
 
28
struct GtDiscDistri {
 
29
  GtHashtable *hashdist;
 
30
  unsigned long long num_of_occurrences;
 
31
};
 
32
 
 
33
GtDiscDistri* gt_disc_distri_new(void)
 
34
{
 
35
  return gt_calloc((size_t) 1, sizeof (GtDiscDistri));
 
36
}
 
37
 
 
38
void gt_disc_distri_add(GtDiscDistri *d, unsigned long key)
 
39
{
 
40
  gt_disc_distri_add_multi(d, key, (unsigned long long) 1);
 
41
}
 
42
 
 
43
DECLARE_HASHMAP(unsigned long, ul, unsigned long long, ull, static, inline)
 
44
DEFINE_HASHMAP(unsigned long, ul, unsigned long long, ull, gt_ht_ul_elem_hash,
 
45
               gt_ht_ul_elem_cmp, NULL_DESTRUCTOR, NULL_DESTRUCTOR, static,
 
46
               inline)
 
47
 
 
48
void gt_disc_distri_add_multi(GtDiscDistri *d, unsigned long key,
 
49
                              unsigned long long occurrences)
 
50
{
 
51
  unsigned long long *valueptr;
 
52
  gt_assert(d);
 
53
 
 
54
  if (!d->hashdist)
 
55
    d->hashdist = ul_ull_gt_hashmap_new();
 
56
 
 
57
  valueptr = ul_ull_gt_hashmap_get(d->hashdist, key);
 
58
  if (!valueptr) {
 
59
    ul_ull_gt_hashmap_add(d->hashdist, key, occurrences);
 
60
  }
 
61
  else
 
62
    (*valueptr) += occurrences;
 
63
 
 
64
  d->num_of_occurrences += occurrences;
 
65
}
 
66
 
 
67
unsigned long long gt_disc_distri_get(const GtDiscDistri *d, unsigned long key)
 
68
{
 
69
  unsigned long long *valueptr;
 
70
  gt_assert(d);
 
71
  if (!d->hashdist || !(valueptr = ul_ull_gt_hashmap_get(d->hashdist, key)))
 
72
    return 0;
 
73
  return *valueptr;
 
74
}
 
75
 
 
76
typedef struct {
 
77
  double cumulative_probability;
 
78
  unsigned long long num_of_occurrences;
 
79
  GtFile *outfp;
 
80
} GtShowValueInfo;
 
81
 
 
82
static enum iterator_op
 
83
showvalue(unsigned long key, unsigned long long occurrences,
 
84
          void *data, GT_UNUSED GtError *err)
 
85
{
 
86
  double probability;
 
87
  GtShowValueInfo *info;
 
88
 
 
89
  gt_error_check(err);
 
90
  gt_assert(data && occurrences);
 
91
  info = (GtShowValueInfo*) data;
 
92
 
 
93
  probability = (double) ((double) occurrences / info->num_of_occurrences);
 
94
  info->cumulative_probability += probability;
 
95
  gt_file_xprintf(info->outfp, "%lu: %llu (prob=%.4f,cumulative=%.4f)\n",
 
96
                  key, occurrences, probability, info->cumulative_probability);
 
97
  return CONTINUE_ITERATION;
 
98
}
 
99
 
 
100
void gt_disc_distri_show(const GtDiscDistri *d, GtFile *outfp)
 
101
{
 
102
  GtShowValueInfo showvalueinfo;
 
103
  GT_UNUSED int rval;
 
104
 
 
105
  gt_assert(d);
 
106
 
 
107
  if (d->hashdist != NULL) {
 
108
    showvalueinfo.cumulative_probability = 0.0;
 
109
    showvalueinfo.num_of_occurrences = d->num_of_occurrences;
 
110
    showvalueinfo.outfp = outfp;
 
111
    rval = ul_ull_gt_hashmap_foreach_in_default_order(d->hashdist, showvalue,
 
112
                                                      &showvalueinfo, NULL);
 
113
    gt_assert(!rval); /* showvalue() is sane */
 
114
  }
 
115
}
 
116
 
 
117
typedef struct {
 
118
  GtDiscDistriIterFunc func;
 
119
  void *data;
 
120
} DiscDistriForeachInfo;
 
121
 
 
122
static enum iterator_op
 
123
disc_distri_foreach_iterfunc(unsigned long key, unsigned long long occurrences,
 
124
                             void *data, GT_UNUSED GtError *err)
 
125
{
 
126
  DiscDistriForeachInfo *info;
 
127
  gt_error_check(err);
 
128
  gt_assert(data);
 
129
  info = (DiscDistriForeachInfo*) data;
 
130
  info->func(key, occurrences, info->data);
 
131
  return CONTINUE_ITERATION;
 
132
}
 
133
 
 
134
static
 
135
void gt_disc_distri_foreach_generic(const GtDiscDistri *d,
 
136
                                    GtDiscDistriIterFunc func,
 
137
                                    void *data,
 
138
                                    ul_ull_gt_hashmap_KeyCmp cmp)
 
139
{
 
140
  DiscDistriForeachInfo info;
 
141
  GT_UNUSED int rval;
 
142
  gt_assert(d);
 
143
  if (d->hashdist != NULL) {
 
144
    info.func = func;
 
145
    info.data = data;
 
146
    if (cmp != NULL)
 
147
      rval = ul_ull_gt_hashmap_foreach_ordered(d->hashdist,
 
148
                                               disc_distri_foreach_iterfunc,
 
149
                                               &info, cmp, NULL);
 
150
    else
 
151
      rval = ul_ull_gt_hashmap_foreach_in_default_order(d->hashdist,
 
152
                                               disc_distri_foreach_iterfunc,
 
153
                                               &info, NULL);
 
154
    gt_assert(!rval); /* disc_distri_foreach_iterfunc() is sane */
 
155
  }
 
156
}
 
157
 
 
158
void gt_disc_distri_foreach(const GtDiscDistri *d, GtDiscDistriIterFunc func,
 
159
                            void *data)
 
160
{
 
161
  gt_disc_distri_foreach_generic(d,func,data,NULL);
 
162
}
 
163
 
 
164
static int
 
165
rev_key_cmp(const unsigned long a, const unsigned long b)
 
166
{
 
167
  return -gt_ht_ul_elem_cmp(&a,&b);
 
168
}
 
169
 
 
170
void gt_disc_distri_foreach_in_reverse_order(const GtDiscDistri *d,
 
171
                                             GtDiscDistriIterFunc func,
 
172
                                             void *data)
 
173
{
 
174
  gt_disc_distri_foreach_generic(d,func,data, rev_key_cmp);
 
175
}
 
176
 
 
177
#define DISC_DISTRI_FOREACHTESTSIZE 3
 
178
 
 
179
/* data for foreach unit test */
 
180
struct ForeachTesterData
 
181
{
 
182
  int counter;
 
183
  int expkeys[DISC_DISTRI_FOREACHTESTSIZE];
 
184
  int expvalues[DISC_DISTRI_FOREACHTESTSIZE];
 
185
  int *had_err;
 
186
  GtError *err;
 
187
};
 
188
 
 
189
/* helper function for unit test of foreach */
 
190
static void foreachtester(unsigned long key,
 
191
                          unsigned long long value, void *data)
 
192
{
 
193
  struct ForeachTesterData *tdata = data;
 
194
  GtError *err = tdata->err;
 
195
  tdata->counter++;
 
196
  gt_ensure(*(tdata->had_err), tdata->counter < DISC_DISTRI_FOREACHTESTSIZE);
 
197
  gt_ensure(*(tdata->had_err),
 
198
         (unsigned long) tdata->expkeys[tdata->counter] == key);
 
199
  gt_ensure(*(tdata->had_err),
 
200
         (unsigned long long) tdata->expvalues[tdata->counter] == value);
 
201
}
 
202
 
 
203
int gt_disc_distri_unit_test(GtError *err)
 
204
{
 
205
  GtDiscDistri *d;
 
206
  int had_err = 0;
 
207
  struct ForeachTesterData tdata;
 
208
 
 
209
  gt_error_check(err);
 
210
 
 
211
  d = gt_disc_distri_new();
 
212
 
 
213
  gt_ensure(had_err, gt_disc_distri_get(d, 0UL) == 0);
 
214
  gt_ensure(had_err, gt_disc_distri_get(d, 100UL) == 0);
 
215
  if (!had_err) {
 
216
    gt_disc_distri_add(d, 0);
 
217
    gt_disc_distri_add_multi(d, 100UL, 256ULL);
 
218
  }
 
219
  gt_ensure(had_err, gt_disc_distri_get(d, 0UL) == 1ULL);
 
220
  gt_ensure(had_err, gt_disc_distri_get(d, 100UL) == 256ULL);
 
221
 
 
222
  /* test foreach and foreach_in_reverse_order: */
 
223
  gt_disc_distri_add(d, 2UL);
 
224
  if (!had_err) {
 
225
    tdata.counter = -1;
 
226
    tdata.expkeys[0] = 0;
 
227
    tdata.expvalues[0] = 1;
 
228
    tdata.expkeys[1] = 2;
 
229
    tdata.expvalues[1] = 1;
 
230
    tdata.expkeys[2] = 100;
 
231
    tdata.expvalues[2] = 256;
 
232
    tdata.had_err = &had_err;
 
233
    tdata.err = err;
 
234
    gt_disc_distri_foreach(d, foreachtester, &tdata);
 
235
  }
 
236
  if (!had_err) {
 
237
    tdata.counter = -1;
 
238
    tdata.expkeys[0] = 100;
 
239
    tdata.expvalues[0] = 256;
 
240
    tdata.expkeys[1] = 2;
 
241
    tdata.expvalues[1] = 1;
 
242
    tdata.expkeys[2] = 0;
 
243
    tdata.expvalues[2] = 1;
 
244
    tdata.had_err = &had_err;
 
245
    tdata.err = err;
 
246
    gt_disc_distri_foreach_in_reverse_order(d, foreachtester, &tdata);
 
247
  }
 
248
 
 
249
  gt_disc_distri_delete(d);
 
250
 
 
251
  return had_err;
 
252
}
 
253
 
 
254
void gt_disc_distri_delete(GtDiscDistri *d)
 
255
{
 
256
  if (!d) return;
 
257
  gt_hashtable_delete(d->hashdist);
 
258
  gt_free(d);
 
259
}