1 // Copyright (C) 2003  Davis E. King (davis@dlib.net)
2 // License: Boost Software License   See LICENSE.txt for the full license.
3 #ifndef DLIB_CONDITIONING_CLASS_KERNEl_1_
4 #define DLIB_CONDITIONING_CLASS_KERNEl_1_
5 
6 #include "conditioning_class_kernel_abstract.h"
7 #include "../assert.h"
8 #include "../algs.h"
9 
10 namespace dlib
11 {
12 
13     template <
14         unsigned long alphabet_size
15         >
16     class conditioning_class_kernel_1
17     {
18         /*!
19             INITIAL VALUE
20                 total == 1
21                 counts == pointer to an array of alphabet_size unsigned shorts
22                 for all i except i == alphabet_size-1: counts[i] == 0
23                 counts[alphabet_size-1] == 1
24 
25             CONVENTION
26                 counts == pointer to an array of alphabet_size unsigned shorts
27                 get_total() == total
28                 get_count(symbol) == counts[symbol]
29 
30                 LOW_COUNT(symbol) == sum of counts[0] though counts[symbol-1]
31                                      or 0 if symbol == 0
32 
33                 get_memory_usage() == global_state.memory_usage
34         !*/
35 
36     public:
37 
38         class global_state_type
39         {
40         public:
global_state_type()41             global_state_type () : memory_usage(0) {}
42         private:
43             unsigned long memory_usage;
44 
45             friend class conditioning_class_kernel_1<alphabet_size>;
46         };
47 
48         conditioning_class_kernel_1 (
49             global_state_type& global_state_
50         );
51 
52         ~conditioning_class_kernel_1 (
53         );
54 
55         void clear(
56         );
57 
58         bool increment_count (
59             unsigned long symbol,
60             unsigned short amount = 1
61         );
62 
63         unsigned long get_count (
64             unsigned long symbol
65         ) const;
66 
67         unsigned long get_total (
68         ) const;
69 
70         unsigned long get_range (
71             unsigned long symbol,
72             unsigned long& low_count,
73             unsigned long& high_count,
74             unsigned long& total_count
75         ) const;
76 
77         void get_symbol (
78             unsigned long target,
79             unsigned long& symbol,
80             unsigned long& low_count,
81             unsigned long& high_count
82         ) const;
83 
84         unsigned long get_memory_usage (
85         ) const;
86 
87         global_state_type& get_global_state (
88         );
89 
90         static unsigned long get_alphabet_size (
91         );
92 
93 
94     private:
95 
96         // restricted functions
97         conditioning_class_kernel_1(conditioning_class_kernel_1<alphabet_size>&);        // copy constructor
98         conditioning_class_kernel_1& operator=(conditioning_class_kernel_1<alphabet_size>&);    // assignment operator
99 
100         // data members
101         unsigned short total;
102         unsigned short* counts;
103         global_state_type& global_state;
104 
105     };
106 
107 // ----------------------------------------------------------------------------------------
108 // ----------------------------------------------------------------------------------------
109     // member function definitions
110 // ----------------------------------------------------------------------------------------
111 // ----------------------------------------------------------------------------------------
112 
113     template <
114         unsigned long alphabet_size
115         >
116     conditioning_class_kernel_1<alphabet_size>::
conditioning_class_kernel_1(global_state_type & global_state_)117     conditioning_class_kernel_1 (
118         global_state_type& global_state_
119     ) :
120         total(1),
121         counts(new unsigned short[alphabet_size]),
122         global_state(global_state_)
123     {
124         COMPILE_TIME_ASSERT( 1 < alphabet_size && alphabet_size < 65536 );
125 
126         unsigned short* start = counts;
127         unsigned short* end = counts+alphabet_size-1;
128         while (start != end)
129         {
130             *start = 0;
131             ++start;
132         }
133         *start = 1;
134 
135         // update memory usage
136         global_state.memory_usage += sizeof(unsigned short)*alphabet_size +
137                                      sizeof(conditioning_class_kernel_1);
138     }
139 
140 // ----------------------------------------------------------------------------------------
141 
142     template <
143         unsigned long alphabet_size
144         >
145     conditioning_class_kernel_1<alphabet_size>::
~conditioning_class_kernel_1()146     ~conditioning_class_kernel_1 (
147     )
148     {
149         delete [] counts;
150         // update memory usage
151         global_state.memory_usage -= sizeof(unsigned short)*alphabet_size +
152                                      sizeof(conditioning_class_kernel_1);
153     }
154 
155 // ----------------------------------------------------------------------------------------
156 
157     template <
158         unsigned long alphabet_size
159         >
160     void conditioning_class_kernel_1<alphabet_size>::
clear()161     clear(
162     )
163     {
164         total = 1;
165         unsigned short* start = counts;
166         unsigned short* end = counts+alphabet_size-1;
167         while (start != end)
168         {
169             *start = 0;
170             ++start;
171         }
172         *start = 1;
173     }
174 
175 // ----------------------------------------------------------------------------------------
176 
177     template <
178         unsigned long alphabet_size
179         >
180     unsigned long conditioning_class_kernel_1<alphabet_size>::
get_memory_usage()181     get_memory_usage(
182     ) const
183     {
184         return global_state.memory_usage;
185     }
186 
187 // ----------------------------------------------------------------------------------------
188 
189     template <
190         unsigned long alphabet_size
191         >
192     typename conditioning_class_kernel_1<alphabet_size>::global_state_type& conditioning_class_kernel_1<alphabet_size>::
get_global_state()193     get_global_state(
194     )
195     {
196         return global_state;
197     }
198 
199 // ----------------------------------------------------------------------------------------
200 
201     template <
202         unsigned long alphabet_size
203         >
204     bool conditioning_class_kernel_1<alphabet_size>::
increment_count(unsigned long symbol,unsigned short amount)205     increment_count (
206         unsigned long symbol,
207         unsigned short amount
208     )
209     {
210         // if we are going over a total of 65535 then scale down all counts by 2
211         if (static_cast<unsigned long>(total)+static_cast<unsigned long>(amount) >= 65536)
212         {
213             total = 0;
214             unsigned short* start = counts;
215             unsigned short* end = counts+alphabet_size;
216             while (start != end)
217             {
218                 *start >>= 1;
219                 total += *start;
220                 ++start;
221             }
222             // make sure it is at least one
223             if (counts[alphabet_size-1]==0)
224             {
225                 ++total;
226                 counts[alphabet_size-1] = 1;
227             }
228         }
229         counts[symbol] += amount;
230         total += amount;
231         return true;
232     }
233 
234 // ----------------------------------------------------------------------------------------
235 
236     template <
237         unsigned long alphabet_size
238         >
239     unsigned long conditioning_class_kernel_1<alphabet_size>::
get_count(unsigned long symbol)240     get_count (
241         unsigned long symbol
242     ) const
243     {
244         return counts[symbol];
245     }
246 
247 // ----------------------------------------------------------------------------------------
248 
249     template <
250         unsigned long alphabet_size
251         >
252     unsigned long conditioning_class_kernel_1<alphabet_size>::
get_alphabet_size()253     get_alphabet_size (
254     )
255     {
256         return alphabet_size;
257     }
258 
259 // ----------------------------------------------------------------------------------------
260 
261     template <
262         unsigned long alphabet_size
263         >
264     unsigned long conditioning_class_kernel_1<alphabet_size>::
get_total()265     get_total (
266     ) const
267     {
268         return total;
269     }
270 
271 // ----------------------------------------------------------------------------------------
272 
273     template <
274         unsigned long alphabet_size
275         >
276     unsigned long conditioning_class_kernel_1<alphabet_size>::
get_range(unsigned long symbol,unsigned long & low_count,unsigned long & high_count,unsigned long & total_count)277     get_range (
278         unsigned long symbol,
279         unsigned long& low_count,
280         unsigned long& high_count,
281         unsigned long& total_count
282     ) const
283     {
284         if (counts[symbol] == 0)
285             return 0;
286 
287         total_count = total;
288 
289         const unsigned short* start = counts;
290         const unsigned short* end = counts+symbol;
291         unsigned short high_count_temp = *start;
292         while (start != end)
293         {
294             ++start;
295             high_count_temp += *start;
296         }
297         low_count = high_count_temp - *start;
298         high_count = high_count_temp;
299         return *start;
300     }
301 
302 // ----------------------------------------------------------------------------------------
303 
304     template <
305         unsigned long alphabet_size
306         >
307     void conditioning_class_kernel_1<alphabet_size>::
get_symbol(unsigned long target,unsigned long & symbol,unsigned long & low_count,unsigned long & high_count)308     get_symbol (
309         unsigned long target,
310         unsigned long& symbol,
311         unsigned long& low_count,
312         unsigned long& high_count
313     ) const
314     {
315         unsigned long high_count_temp = *counts;
316         const unsigned short* start = counts;
317         while (target >= high_count_temp)
318         {
319             ++start;
320             high_count_temp += *start;
321         }
322 
323         low_count = high_count_temp - *start;
324         high_count = high_count_temp;
325         symbol = static_cast<unsigned long>(start-counts);
326     }
327 
328 // ----------------------------------------------------------------------------------------
329 
330 }
331 
332 #endif // DLIB_CONDITIONING_CLASS_KERNEl_1_
333 
334