1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
/*
* Copyright (C) 2011 The Android Open Source Project
*
* 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.
*/
/* $Id: db_utilities_indexing.cpp,v 1.3 2011/06/17 14:03:31 mbansal Exp $ */
#include "db_utilities_indexing.h"
#include "db_utilities.h"
/*****************************************************************
* Lean and mean begins here *
*****************************************************************/
void db_Zero(double *d,long nr)
{
long i;
for(i=0;i<nr;i++) d[i]=0.0;
}
/*This routine breaks number in source into values smaller and larger than
a pivot element. Values equal to the pivot are ignored*/
void db_LeanPartitionOnPivot(double pivot,double *dest,const double *source,long first,long last,long *first_equal,long *last_equal)
{
double temp;
const double *s_point;
const double *s_top;
double *d_bottom;
double *d_top;
s_point=source+first;
s_top=source+last;
d_bottom=dest+first;
d_top=dest+last;
for(;s_point<=s_top;)
{
temp= *(s_point++);
if(temp<pivot) *(d_bottom++)=temp;
else if(temp>pivot) *(d_top--)=temp;
}
*first_equal=d_bottom-dest;
*last_equal=d_top-dest;
}
double db_LeanQuickSelect(const double *s,long nr_elements,long pos,double *temp)
{
long first=0;
long last=nr_elements-1;
double pivot;
long first_equal,last_equal;
double *tempA;
double *tempB;
double *tempC;
const double *source;
double *dest;
tempA=temp;
tempB=temp+nr_elements;
source=s;
dest=tempA;
for(;last-first>2;)
{
pivot=db_TripleMedian(source[first],source[last],source[(first+last)/2]);
db_LeanPartitionOnPivot(pivot,dest,source,first,last,&first_equal,&last_equal);
if(first_equal>pos) last=first_equal-1;
else if(last_equal<pos) first=last_equal+1;
else
{
return(pivot);
}
/*Swap pointers*/
tempC=tempA;
tempA=tempB;
tempB=tempC;
source=tempB;
dest=tempA;
}
pivot=db_TripleMedian(source[first],source[last],source[(first+last)/2]);
return(pivot);
}
float* db_AlignPointer_f(float *p,unsigned long nr_bytes)
{
float *ap;
unsigned long m;
m=((unsigned long)p)%nr_bytes;
if(m) ap=(float*) (((unsigned long)p)-m+nr_bytes);
else ap=p;
return(ap);
}
short* db_AlignPointer_s(short *p,unsigned long nr_bytes)
{
short *ap;
unsigned long m;
m=((unsigned long)p)%nr_bytes;
if(m) ap=(short*) (((unsigned long)p)-m+nr_bytes);
else ap=p;
return(ap);
}
|
