1 #if !defined HAVE_USEARCH_H__
2 #define HAVE_USEARCH_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2010, 2012 Joerg Arndt
5 // License: GNU General Public License version 3 or later,
6 // see the file COPYING.txt in the main directory.
7
8 #include "fxttypes.h"
9
10
11 template <typename Type>
first_eq_idx(const Type * f,ulong n,Type v)12 inline ulong first_eq_idx(const Type *f, ulong n, Type v)
13 // Return index of first element == v
14 // Return n if all !=v
15 {
16 ulong k = 0;
17 while ( (k<n) && (f[k]!=v) ) k++;
18 return k;
19 }
20 // -------------------------
21
22 template <typename Type>
first_eq_idx_large(const Type * f,ulong n,Type v)23 inline ulong first_eq_idx_large(const Type *f, ulong n, Type v)
24 // Return index of first element == v
25 // Return n if all !=v
26 // Unrolled version for large arrays.
27 {
28 ulong k;
29 for (k=0; k<(n&3); ++k) if ( f[k]==v ) return k;
30
31 while ( k!=n ) // 4-fold unrolled
32 {
33 Type t0 = f[k], t1 = f[k+1], t2 = f[k+2], t3 = f[k+3];
34 bool qa = ( (t0==v) | (t1==v) ); // note bit-wise OR to avoid branch
35 bool qb = ( (t2==v) | (t3==v) );
36 if ( qa | qb ) // element v found
37 {
38 while ( 1 ) { if ( f[k]==v ) return k; else ++k; }
39 }
40 k += 4;
41 }
42
43 return n;
44 }
45 // -------------------------
46
47
48 template <typename Type>
first_neq_idx(const Type * f,ulong n,Type v)49 inline ulong first_neq_idx(const Type *f, ulong n, Type v)
50 // Return index of first element != v
51 // Return n if all ==v
52 {
53 ulong k = 0;
54 while ( (k<n) && (f[k]==v) ) k++;
55 return k;
56 }
57 // -------------------------
58
59
60 template <typename Type>
first_geq_idx(const Type * f,ulong n,Type v)61 inline ulong first_geq_idx(const Type *f, ulong n, Type v)
62 // Return index of first element >=v
63 // Return n if no such element is found
64 {
65 for (ulong i=0; i<n; ++i) if ( f[i]>=v ) return i;
66 return n;
67 }
68 // -------------------------
69
70
71 template <typename Type>
first_leq_idx(const Type * f,ulong n,Type v)72 inline ulong first_leq_idx(const Type *f, ulong n, Type v)
73 // Return index of first element <=v
74 // Return n if no such element is found
75 {
76 for (ulong i=0; i<n; ++i) if ( f[i]<=v ) return i;
77 return n;
78 }
79 // -------------------------
80
81
82
83 template <typename Type>
last_eq_idx(const Type * f,ulong n,Type v)84 inline ulong last_eq_idx(const Type *f, ulong n, Type v)
85 // Return index of last element == v
86 // Return n if all !=v
87 {
88 ulong k = n-1;
89 while ( f[k]!=v )
90 {
91 k--;
92 if ( 0==k ) return n;
93 }
94 return k;
95 }
96 // -------------------------
97
98
99 template <typename Type>
last_neq_idx(const Type * f,ulong n,Type v)100 inline ulong last_neq_idx(const Type *f, ulong n, Type v)
101 // Return index of last element != v
102 // Return n if all ==v
103 {
104 ulong k = n-1;
105 while ( f[k]==v )
106 {
107 k--;
108 if ( 0==k ) return n;
109 }
110 return k;
111 }
112 // -------------------------
113
114
115 template <typename Type>
last_geq_idx(const Type * f,ulong n,Type v)116 inline ulong last_geq_idx(const Type *f, ulong n, Type v)
117 // Return index of last element >= v
118 // Return n if all <v
119 {
120 ulong k = n-1;
121 while ( f[k]<v )
122 {
123 k--;
124 if ( 0==k ) return n;
125 }
126 return k;
127 }
128 // -------------------------
129
130
131 template <typename Type>
last_leq_idx(const Type * f,ulong n,Type v)132 inline ulong last_leq_idx(const Type *f, ulong n, Type v)
133 // Return index of last element <= v
134 // Return n if all >v
135 {
136 ulong k = n-1;
137 while ( f[k]>v ) { k--; if ( 0==k ) return n; }
138 return k;
139 }
140 // -------------------------
141
142
143 template <typename Type>
u_unique(const Type * f,ulong n)144 bool u_unique(const Type *f, ulong n)
145 // Return whether elements in unordered array f[] are unique.
146 // Algorithm is O(n^2), so use for small n only.
147 {
148 for (ulong j=0; j<n; ++j)
149 {
150 const Type fj = f[j];
151 for (ulong k=j+1; k<n; ++k)
152 if ( fj == f[k] ) return false;
153 }
154 return true;
155 }
156 // -------------------------
157
158
159 #endif // !defined HAVE_USEARCH_H__
160