alphanum.cpp

Go to the documentation of this file.
00001 /*
00002 The Alphanum Algorithm is an improved sorting algorithm for strings
00003 containing numbers.  Instead of sorting numbers in ASCII order like a
00004 standard sort, this algorithm sorts numbers in numeric order.
00005 
00006 The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
00007 
00008 This implementation is Copyright (c) 2008 Dirk Jagdmann <doj@cubic.org>.
00009 It is a cleanroom implementation of the algorithm and not derived by
00010 other's works. In contrast to the versions written by Dave Koelle this
00011 source code is distributed with the libpng/zlib license.
00012 
00013 This software is provided 'as-is', without any express or implied
00014 warranty. In no event will the authors be held liable for any damages
00015 arising from the use of this software.
00016 
00017 Permission is granted to anyone to use this software for any purpose,
00018 including commercial applications, and to alter it and redistribute it
00019 freely, subject to the following restrictions:
00020 
00021     1. The origin of this software must not be misrepresented; you
00022        must not claim that you wrote the original software. If you use
00023        this software in a product, an acknowledgment in the product
00024        documentation would be appreciated but is not required.
00025 
00026     2. Altered source versions must be plainly marked as such, and
00027        must not be misrepresented as being the original software.
00028 
00029     3. This notice may not be removed or altered from any source
00030        distribution. */
00031 
00032 /* $Header: /code/doj/alphanum.hpp,v 1.3 2008/01/28 23:06:47 doj Exp $ 
00033 
00034    slightly modified version, the main function is unaltered, but the
00035    interface definitions are changed to better suit hugins needs 
00036    */
00037 
00038 #include <hugin_utils/alphanum.h>
00039 #include <stdlib.h>
00040 
00041 namespace doj
00042 {
00043 
00044 int alphanum_impl(const char* l, const char* r)
00045 {
00046     enum mode_t { STRING, NUMBER } mode=STRING;
00047 
00048     while(*l && *r)
00049     {
00050         if(mode == STRING)
00051         {
00052             char l_char, r_char;
00053             while((l_char=*l) && (r_char=*r))
00054             {
00055                 // check if this are digit characters
00056                 const bool l_digit=isdigit(l_char)!=0, r_digit=isdigit(r_char)!=0;
00057                 // if both characters are digits, we continue in NUMBER mode
00058                 if(l_digit && r_digit)
00059                 {
00060                     mode=NUMBER;
00061                     break;
00062                 }
00063                 // if only the left character is a digit, we have a result
00064                 if(l_digit)
00065                 {
00066                     return -1;
00067                 }
00068                 // if only the right character is a digit, we have a result
00069                 if(r_digit)
00070                 {
00071                     return +1;
00072                 }
00073                 // compute the difference of both characters
00074                 const int diff=l_char - r_char;
00075                 // if they differ we have a result
00076                 if(diff != 0)
00077                 {
00078                     return diff;
00079                 }
00080                 // otherwise process the next characters
00081                 ++l;
00082                 ++r;
00083             }
00084         }
00085         else // mode==NUMBER
00086         {
00087             // get the left number
00088             char* end;
00089             unsigned long l_int=strtoul(l, &end, 10);
00090             l=end;
00091 
00092             // get the right number
00093             unsigned long r_int=strtoul(r, &end, 10);
00094             r=end;
00095 
00096             // if the difference is not equal to zero, we have a comparison result
00097             const long diff=l_int-r_int;
00098             if(diff != 0)
00099             {
00100                 return diff;
00101             }
00102 
00103             // otherwise we process the next substring in STRING mode
00104             mode=STRING;
00105         }
00106     }
00107 
00108     if(*r)
00109     {
00110         return -1;
00111     }
00112     if(*l)
00113     {
00114         return +1;
00115     }
00116     return 0;
00117 }
00118 
00119 int alphanum_comp(const std::string& l, const std::string& r)
00120 {
00121     return alphanum_impl(l.c_str(), r.c_str());
00122 }
00123 
00124 int alphanum_comp(const char* l, const char* r)
00125 {
00126     return alphanum_impl(l, r);
00127 }
00128 
00130 
00131 bool alphanum_less::operator()(const std::string& left, const std::string& right) const
00132 {
00133     return alphanum_comp(left, right) < 0;
00134 }
00135 
00136 } //namespace doj
00137 

Generated on Sun Sep 21 01:25:41 2014 for Hugintrunk by  doxygen 1.3.9.1