← Back to branch summary

~ubuntu-branches/ubuntu/precise/dicelab/precise

« back to all changes in this revision

Viewing changes to util.c

  • Committer: Bazaar Package Importer
  • Author(s): Robert Lemmen
  • Date: 2007-12-10 17:06:15 UTC
  • Revision ID: james.westby@ubuntu.com-20071210170615-q1av8grz0vjiv397
Tags: upstream-0.5
Import upstream version 0.5

Show diffs side-by-side

added added

removed removed

Lines of Context:
util.c
 
1
#include <stdlib.h>
 
2
 
 
3
#include "util.h"
 
4
 
 
5
void quicksort(int *data, int start, int end) {
 
6
        if (end > start) {
 
7
                int i=start-1;
 
8
                int j = end;
 
9
                int t;
 
10
                for(;;) {
 
11
                        while(data[++i] < data[end]);
 
12
                        while(data[--j >= 0 ? j : end] > data[end]);
 
13
                        if (i>=j)
 
14
                                break;
 
15
                        t = data[i];
 
16
                        data[i] = data[j];
 
17
                        data[j] = t;
 
18
                }
 
19
                t = data[i];
 
20
                data[i] = data[end];
 
21
                data[end] = t;
 
22
 
 
23
                quicksort(data, start, i-1);
 
24
                quicksort(data, i+1, end);
 
25
        }
 
26
}
 
27
 
 
28
void permute(int *data, int count) {
 
29
        int i, p, t;
 
30
        for (i = count-1; i >= 0; i--) {
 
31
                p = (int) ((i+1) * (rand() / (RAND_MAX + 1.0)));
 
32
                t = data[i];
 
33
                data[i] = data[p];
 
34
                data[p] = t;
 
35
        }
 
36
}
 
37
 
 
38
void result_add(struct result_node **list, int value) {
 
39
        // make sure we have a list
 
40
        if (*list == NULL) {
 
41
                *list = (struct result_node *)malloc(sizeof(struct result_node));
 
42
                (*list)->value = value;
 
43
                (*list)->prob = 1;
 
44
                (*list)->next = NULL;
 
45
                return;
 
46
        }
 
47
        // walk the list
 
48
        struct result_node *cur = *list, *last = NULL;
 
49
        while ((cur != NULL) && (cur->value < value)) {
 
50
                last = cur;
 
51
                cur = cur->next;
 
52
        }
 
53
        // see what we have to do
 
54
        if (cur == NULL) {
 
55
                cur = (struct result_node *)malloc(sizeof(struct result_node));
 
56
                cur->value = value;
 
57
                cur->prob = 1;
 
58
                cur->next = NULL;
 
59
                last->next = cur;
 
60
                return;
 
61
        }
 
62
        else if (cur->value == value) {
 
63
                cur->prob++;
 
64
                return;
 
65
        }
 
66
        else if (last != NULL) {
 
67
                last->next = (struct result_node *)malloc(sizeof(struct result_node));
 
68
                last->next->value = value;
 
69
                last->next->prob = 1;
 
70
                last->next->next = cur;
 
71
        }
 
72
        else {
 
73
                *list = (struct result_node *)malloc(sizeof(struct result_node));
 
74
                (*list)->value = value;
 
75
                (*list)->prob = 1;
 
76
                (*list)->next = cur;
 
77
        }
 
78
}
 
79
 
 
80
inline void swapperm(int *data, int i, int j) {
 
81
        if (i == j)
 
82
                return;
 
83
        data[i] ^= data[j];
 
84
        data[j] ^= data[i];
 
85
        data[i] ^= data[j];
 
86
};
 
87
 
 
88
void _rec_all_permutations(int *data, int count, 
 
89
                void (*callback)(int *data, int count, void *arg, float farg), 
 
90
                void *arg, float farg, int n) {
 
91
        if (1 == n) {
 
92
                callback(data, count, arg, farg);
 
93
        }
 
94
        else {
 
95
                int c;
 
96
                for (c = 0; c < n; c++) {
 
97
                        _rec_all_permutations(data, count, callback, arg, farg, n-1);
 
98
                        swapperm(data,  n%2 == 1 ? 0 : c, n-1); 
 
99
                }
 
100
        }
 
101
}
 
102
 
 
103
void all_permutations(int *data, int count, 
 
104
                void (*callback)(int *data, int count, void *arg, float farg), 
 
105
                void *arg, float farg) {
 
106
        _rec_all_permutations(data, count, callback, arg, farg, count);
 
107
}
 
108
 
 
109
long factorial(int n) {
 
110
        long fact = 1;
 
111
        while (n > 0) {
 
112
                fact *= n--;
 
113
        }
 
114
        return fact;
 
115
}