1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2008, 2011 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18
19 #include "math/extrema.h"
20
21 #include <stdlib.h>
22
23 #include "data/case.h"
24 #include "data/val-type.h"
25 #include "libpspp/compiler.h"
26 #include "libpspp/ll.h"
27
28 #include "gl/xalloc.h"
29
30 struct extrema
31 {
32 size_t capacity;
33 size_t n;
34 struct ll_list list;
35
36 ll_compare_func *cmp_func;
37 };
38
39
40 static int
cmp_descending(const struct ll * a_,const struct ll * b_,void * aux UNUSED)41 cmp_descending (const struct ll *a_, const struct ll *b_, void *aux UNUSED)
42 {
43 const struct extremum *a = ll_data (a_, struct extremum, ll);
44 const struct extremum *b = ll_data (b_, struct extremum, ll);
45
46 if (a->value > b->value) return -1;
47
48 return (a->value < b->value);
49 }
50
51 static int
cmp_ascending(const struct ll * a_,const struct ll * b_,void * aux UNUSED)52 cmp_ascending (const struct ll *a_, const struct ll *b_, void *aux UNUSED)
53 {
54 const struct extremum *a = ll_data (a_, struct extremum, ll);
55 const struct extremum *b = ll_data (b_, struct extremum, ll);
56
57 if (a->value < b->value) return -1;
58
59 return (a->value > b->value);
60 }
61
62
63 struct extrema *
extrema_create(size_t n,enum extreme_end end)64 extrema_create (size_t n, enum extreme_end end)
65 {
66 struct extrema *extrema = xzalloc (sizeof *extrema);
67 extrema->capacity = n;
68
69 if (end == EXTREME_MAXIMA)
70 extrema->cmp_func = cmp_descending;
71 else
72 extrema->cmp_func = cmp_ascending;
73
74 ll_init (&extrema->list);
75
76 return extrema;
77 }
78
79 void
extrema_destroy(struct extrema * extrema)80 extrema_destroy (struct extrema *extrema)
81 {
82 struct ll *ll = ll_head (&extrema->list);
83
84 while (ll != ll_null (&extrema->list))
85 {
86 struct extremum *e = ll_data (ll, struct extremum, ll);
87
88 ll = ll_next (ll);
89 free (e);
90 }
91
92 free (extrema);
93 }
94
95
96 void
extrema_add(struct extrema * extrema,double val,double weight,casenumber location)97 extrema_add (struct extrema *extrema, double val,
98 double weight,
99 casenumber location)
100 {
101 struct extremum *e = xzalloc (sizeof *e) ;
102 e->value = val;
103 e->location = location;
104 e->weight = weight;
105
106 if (val == SYSMIS)
107 {
108 free (e);
109 return;
110 }
111
112 ll_insert_ordered (ll_head (&extrema->list), ll_null (&extrema->list),
113 &e->ll, extrema->cmp_func, NULL);
114
115 if (extrema->n++ > extrema->capacity)
116 {
117 struct ll *tail = ll_tail (&extrema->list);
118 struct extremum *et = ll_data (tail, struct extremum, ll);
119
120 ll_remove (tail);
121
122 free (et);
123 }
124 }
125
126
127 const struct ll_list *
extrema_list(const struct extrema * ex)128 extrema_list (const struct extrema *ex)
129 {
130 return &ex->list;
131 }
132
133
134 bool
extrema_top(const struct extrema * ex,double * v)135 extrema_top (const struct extrema *ex, double *v)
136 {
137 const struct extremum *top;
138
139 if (ll_is_empty (&ex->list))
140 return false;
141
142 top = (const struct extremum *)
143 ll_data (ll_head(&ex->list), struct extremum, ll);
144
145 *v = top->value;
146
147 return true;
148 }
149