#include "mfcpch.h"
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include "memry.h"
#include "tprintf.h"
#include "statistc.h"
Go to the source code of this file.
#define SEED1 0x1234 |
* (C) Copyright 1991, Hewlett-Packard Ltd. ** Licensed under the Apache License, Version 2.0 (the "License"); ** you may not use this file except in compliance with the License. ** You may obtain a copy of the License at ** http://www.apache.org/licenses/LICENSE-2.0 ** Unless required by applicable law or agreed to in writing, software ** distributed under the License is distributed on an "AS IS" BASIS, ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. ** See the License for the specific language governing permissions and ** limitations under the License.
Definition at line 29 of file statistc.cpp.
#define SEED2 0x5678 |
Definition at line 30 of file statistc.cpp.
#define SEED3 0x9abc |
Definition at line 31 of file statistc.cpp.
DLLSYM INT32 choose_nth_item | ( | INT32 | index, | |
void * | array, | |||
INT32 | count, | |||
size_t | size, | |||
int(*)(const void *, const void *) | compar | |||
) |
Returns the index of what would b the nth item in the array if the members were sorted, without actually sorting.
Definition at line 766 of file statistc.cpp.
References choose_nth_item(), nrand48(), SEED1, SEED2, SEED3, and swap_entries().
00773 { 00774 static UINT16 seeds[3] = { SEED1, SEED2, SEED3 }; 00775 //for nrand 00776 int result; //of compar 00777 INT32 next_sample; //next one to do 00778 INT32 next_lesser; //space for new 00779 INT32 prev_greater; //last one saved 00780 INT32 equal_count; //no of equal ones 00781 INT32 pivot; //proposed median 00782 00783 if (count <= 1) 00784 return 0; 00785 if (count == 2) { 00786 if (compar (array, (char *) array + size) < 0) { 00787 return index >= 1 ? 1 : 0; 00788 } 00789 else { 00790 return index >= 1 ? 0 : 1; 00791 } 00792 } 00793 if (index < 0) 00794 index = 0; //ensure lergal 00795 else if (index >= count) 00796 index = count - 1; 00797 #ifdef __UNIX__ 00798 pivot = (INT32) (nrand48 (seeds) % count); 00799 #else 00800 pivot = (INT32) (rand () % count); 00801 #endif 00802 swap_entries (array, size, pivot, 0); 00803 next_lesser = 0; 00804 prev_greater = count; 00805 equal_count = 1; 00806 for (next_sample = 1; next_sample < prev_greater;) { 00807 result = 00808 compar ((char *) array + size * next_sample, 00809 (char *) array + size * next_lesser); 00810 if (result < 0) { 00811 swap_entries (array, size, next_lesser++, next_sample++); 00812 //shuffle 00813 } 00814 else if (result > 0) { 00815 prev_greater--; 00816 swap_entries(array, size, prev_greater, next_sample); 00817 } 00818 else { 00819 equal_count++; 00820 next_sample++; 00821 } 00822 } 00823 if (index < next_lesser) 00824 return choose_nth_item (index, array, next_lesser, size, compar); 00825 else if (index < prev_greater) 00826 return next_lesser; //in equal bracket 00827 else 00828 return choose_nth_item (index - prev_greater, 00829 (char *) array + size * prev_greater, 00830 count - prev_greater, size, 00831 compar) + prev_greater; 00832 }
Fast median.
index | index to choose | |
array | array of items | |
count | number of items |
next one to do
space for new
last one saved
no of equal ones
proposed median
current sample
in equal bracket
Definition at line 692 of file statistc.cpp.
Referenced by choose_nth_item(), compute_page_skew(), LMS::compute_quadratic_errors(), compute_row_stats(), LMS::constrained_fit(), LMS::fit(), and median_block_xheight().
00696 { 00697 static UINT16 seeds[3] = { SEED1, SEED2, SEED3 }; 00698 //for nrand 00699 INT32 next_sample; 00700 INT32 next_lesser; 00701 INT32 prev_greater; 00702 INT32 equal_count; 00703 float pivot; 00704 float sample; 00705 00706 if (count <= 1) 00707 return 0; 00708 if (count == 2) { 00709 if (array[0] < array[1]) { 00710 return index >= 1 ? 1 : 0; 00711 } 00712 else { 00713 return index >= 1 ? 0 : 1; 00714 } 00715 } 00716 else { 00717 if (index < 0) 00718 index = 0; // ensure lergal 00719 else if (index >= count) 00720 index = count - 1; 00721 #ifdef __UNIX__ 00722 equal_count = (INT32) (nrand48 (seeds) % count); 00723 #else 00724 equal_count = (INT32) (rand () % count); 00725 #endif 00726 pivot = array[equal_count]; 00727 array[equal_count] = array[0]; // fill gap 00728 next_lesser = 0; 00729 prev_greater = count; 00730 equal_count = 1; 00731 for (next_sample = 1; next_sample < prev_greater;) { 00732 sample = array[next_sample]; 00733 if (sample < pivot) { 00734 array[next_lesser++] = sample; // shuffle 00735 next_sample++; 00736 } 00737 else if (sample > pivot) { 00738 prev_greater--; 00739 array[next_sample] = array[prev_greater]; // juggle 00740 array[prev_greater] = sample; 00741 } 00742 else { 00743 equal_count++; 00744 next_sample++; 00745 } 00746 } 00747 for (next_sample = next_lesser; next_sample < prev_greater;) 00748 array[next_sample++] = pivot; 00749 if (index < next_lesser) 00750 return choose_nth_item (index, array, next_lesser); 00751 else if (index < prev_greater) 00752 return next_lesser; 00753 else 00754 return choose_nth_item (index - prev_greater, 00755 array + prev_greater, 00756 count - prev_greater) + prev_greater; 00757 } 00758 }
Swap 2 entries of abitrary size in-place in a table.
Definition at line 838 of file statistc.cpp.
Referenced by choose_nth_item().
00842 { 00843 char tmp; 00844 char *ptr1; //to entries 00845 char *ptr2; 00846 size_t count; //of bytes 00847 00848 ptr1 = (char *) array + index1 * size; 00849 ptr2 = (char *) array + index2 * size; 00850 for (count = 0; count < size; count++) { 00851 tmp = *ptr1; 00852 *ptr1++ = *ptr2; 00853 *ptr2++ = tmp; //tedious! 00854 } 00855 }