alphanum.hpp
Go to the documentation of this file.
1 #ifndef ALPHANUM__HPP
2 #define ALPHANUM__HPP
3 
4 /*
5 The Alphanum Algorithm is an improved sorting algorithm for strings
6 containing numbers. Instead of sorting numbers in ASCII order like a
7 standard sort, this algorithm sorts numbers in numeric order.
8 
9 The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
10 
11 This implementation is Copyright (c) 2008 Dirk Jagdmann <doj@cubic.org>.
12 It is a cleanroom implementation of the algorithm and not derived by
13 other's works. In contrast to the versions written by Dave Koelle this
14 source code is distributed with the libpng/zlib license.
15 
16 This software is provided 'as-is', without any express or implied
17 warranty. In no event will the authors be held liable for any damages
18 arising from the use of this software.
19 
20 Permission is granted to anyone to use this software for any purpose,
21 including commercial applications, and to alter it and redistribute it
22 freely, subject to the following restrictions:
23 
24  1. The origin of this software must not be misrepresented; you
25  must not claim that you wrote the original software. If you use
26  this software in a product, an acknowledgment in the product
27  documentation would be appreciated but is not required.
28 
29  2. Altered source versions must be plainly marked as such, and
30  must not be misrepresented as being the original software.
31 
32  3. This notice may not be removed or altered from any source
33  distribution. */
34 
35 /* $Header: /code/doj/alphanum.hpp,v 1.3 2008/01/28 23:06:47 doj Exp $ */
36 
37 #include <cassert>
38 #include <functional>
39 #include <string>
40 #include <sstream>
41 
42 #ifdef ALPHANUM_LOCALE
43 #include <cctype>
44 #endif
45 
46 #ifdef DOJDEBUG
47 #include <iostream>
48 #include <typeinfo>
49 #endif
50 
51 // TODO: make comparison with hexadecimal numbers. Extend the alphanum_comp() function by traits to choose between decimal and hexadecimal.
52 
53 namespace doj
54 {
55 
56  // anonymous namespace for functions we use internally. But if you
57  // are coding in C, you can use alphanum_impl() directly, since it
58  // uses not C++ features.
59  namespace {
60 
61  // if you want to honour the locale settings for detecting digit
62  // characters, you should define ALPHANUM_LOCALE
63 #ifdef ALPHANUM_LOCALE
64 
65  bool alphanum_isdigit(int c)
66  {
67  return isdigit(c);
68  }
69 #else
70 
74  bool alphanum_isdigit(const char c)
75  {
76  return c>='0' && c<='9';
77  }
78 #endif
79 
95  int alphanum_impl(const char *l, const char *r)
96  {
97  enum mode_t { STRING, NUMBER } mode=STRING;
98 
99  while(*l && *r)
100  {
101  if(mode == STRING)
102  {
103  char l_char, r_char;
104  while((l_char=*l) && (r_char=*r))
105  {
106  // check if this are digit characters
107  const bool l_digit=alphanum_isdigit(l_char), r_digit=alphanum_isdigit(r_char);
108  // if both characters are digits, we continue in NUMBER mode
109  if(l_digit && r_digit)
110  {
111  mode=NUMBER;
112  break;
113  }
114  // if only the left character is a digit, we have a result
115  if(l_digit) return -1;
116  // if only the right character is a digit, we have a result
117  if(r_digit) return +1;
118  // compute the difference of both characters
119  const int diff=l_char - r_char;
120  // if they differ we have a result
121  if(diff != 0) return diff;
122  // otherwise process the next characters
123  ++l;
124  ++r;
125  }
126  }
127  else // mode==NUMBER
128  {
129 #ifdef ALPHANUM_LOCALE
130  // get the left number
131  char *end;
132  unsigned long l_int=strtoul(l, &end, 0);
133  l=end;
134 
135  // get the right number
136  unsigned long r_int=strtoul(r, &end, 0);
137  r=end;
138 #else
139  // get the left number
140  unsigned long l_int=0;
141  while(*l && alphanum_isdigit(*l))
142  {
143  // TODO: this can overflow
144  l_int=l_int*10 + *l-'0';
145  ++l;
146  }
147 
148  // get the right number
149  unsigned long r_int=0;
150  while(*r && alphanum_isdigit(*r))
151  {
152  // TODO: this can overflow
153  r_int=r_int*10 + *r-'0';
154  ++r;
155  }
156 #endif
157 
158  // if the difference is not equal to zero, we have a comparison result
159  const long diff=l_int-r_int;
160  if(diff != 0)
161  return diff;
162 
163  // otherwise we process the next substring in STRING mode
164  mode=STRING;
165  }
166  }
167 
168  if(*r) return -1;
169  if(*l) return +1;
170  return 0;
171  }
172 
173  }
174 
183  template <typename lT, typename rT>
184  int alphanum_comp(const lT& left, const rT& right)
185  {
186 #ifdef DOJDEBUG
187  std::clog << "alphanum_comp<" << typeid(left).name() << "," << typeid(right).name() << "> " << left << "," << right << std::endl;
188 #endif
189  std::ostringstream l; l << left;
190  std::ostringstream r; r << right;
191  return alphanum_impl(l.str().c_str(), r.str().c_str());
192  }
193 
201  template <>
202  int alphanum_comp<std::string>(const std::string& l, const std::string& r)
203  {
204 #ifdef DOJDEBUG
205  std::clog << "alphanum_comp<std::string,std::string> " << l << "," << r << std::endl;
206 #endif
207  return alphanum_impl(l.c_str(), r.c_str());
208  }
209 
211 
212  // now follow a lot of overloaded alphanum_comp() functions to get a
213  // direct call to alphanum_impl() upon the various combinations of c
214  // and c++ strings.
215 
223  int alphanum_comp(char* l, char* r)
224  {
225  assert(l);
226  assert(r);
227 #ifdef DOJDEBUG
228  std::clog << "alphanum_comp<char*,char*> " << l << "," << r << std::endl;
229 #endif
230  return alphanum_impl(l, r);
231  }
232 
233  int alphanum_comp(const char* l, const char* r)
234  {
235  assert(l);
236  assert(r);
237 #ifdef DOJDEBUG
238  std::clog << "alphanum_comp<const char*,const char*> " << l << "," << r << std::endl;
239 #endif
240  return alphanum_impl(l, r);
241  }
242 
243  int alphanum_comp(char* l, const char* r)
244  {
245  assert(l);
246  assert(r);
247 #ifdef DOJDEBUG
248  std::clog << "alphanum_comp<char*,const char*> " << l << "," << r << std::endl;
249 #endif
250  return alphanum_impl(l, r);
251  }
252 
253  int alphanum_comp(const char* l, char* r)
254  {
255  assert(l);
256  assert(r);
257 #ifdef DOJDEBUG
258  std::clog << "alphanum_comp<const char*,char*> " << l << "," << r << std::endl;
259 #endif
260  return alphanum_impl(l, r);
261  }
262 
263  int alphanum_comp(const std::string& l, char* r)
264  {
265  assert(r);
266 #ifdef DOJDEBUG
267  std::clog << "alphanum_comp<std::string,char*> " << l << "," << r << std::endl;
268 #endif
269  return alphanum_impl(l.c_str(), r);
270  }
271 
272  int alphanum_comp(char* l, const std::string& r)
273  {
274  assert(l);
275 #ifdef DOJDEBUG
276  std::clog << "alphanum_comp<char*,std::string> " << l << "," << r << std::endl;
277 #endif
278  return alphanum_impl(l, r.c_str());
279  }
280 
281  int alphanum_comp(const std::string& l, const char* r)
282  {
283  assert(r);
284 #ifdef DOJDEBUG
285  std::clog << "alphanum_comp<std::string,const char*> " << l << "," << r << std::endl;
286 #endif
287  return alphanum_impl(l.c_str(), r);
288  }
289 
290  int alphanum_comp(const char* l, const std::string& r)
291  {
292  assert(l);
293 #ifdef DOJDEBUG
294  std::clog << "alphanum_comp<const char*,std::string> " << l << "," << r << std::endl;
295 #endif
296  return alphanum_impl(l, r.c_str());
297  }
298 
300 
306  template<class Ty>
307  struct alphanum_less : public std::binary_function<Ty, Ty, bool>
308  {
309  bool operator()(const Ty& left, const Ty& right) const
310  {
311  return alphanum_comp(left, right) < 0;
312  }
313  };
314 
315 }
316 
317 
318 #endif
Definition: alphanum.hpp:53
char * end
STRING
char name[1]
int alphanum_comp(const lT &left, const rT &right)
Definition: alphanum.hpp:184
bool operator()(const Ty &left, const Ty &right) const
Definition: alphanum.hpp:309


plotjuggler
Author(s): Davide Faconti
autogenerated on Sat Jul 6 2019 03:44:16