home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 mARCH / PCWK3A99.iso / Linux / DDD331 / DDD-3_1_.000 / DDD-3_1_ / ddd-3.1.1 / ddd / SmartC.C < prev    next >
C/C++ Source or Header  |  1998-09-22  |  3KB  |  130 lines
  1. // $Id: SmartC.C,v 1.2 1998/09/22 11:31:31 zeller Exp $ -*- C++ -*-
  2. // `smart' string comparison
  3.  
  4. // Copyright (C) 1998 Technische Universitaet Braunschweig, Germany.
  5. // Written by Andreas Zeller <zeller@ips.cs.tu-bs.de>.
  6. // 
  7. // This file is part of DDD.
  8. // 
  9. // DDD is free software; you can redistribute it and/or
  10. // modify it under the terms of the GNU General Public
  11. // License as published by the Free Software Foundation; either
  12. // version 2 of the License, or (at your option) any later version.
  13. // 
  14. // DDD is distributed in the hope that it will be useful,
  15. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. // See the GNU General Public License for more details.
  18. // 
  19. // You should have received a copy of the GNU General Public
  20. // License along with DDD -- see the file COPYING.
  21. // If not, write to the Free Software Foundation, Inc.,
  22. // 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23. // 
  24. // DDD is the data display debugger.
  25. // For details, see the DDD World-Wide-Web page, 
  26. // `http://www.cs.tu-bs.de/softech/ddd/',
  27. // or send a mail to the DDD developers <ddd@ips.cs.tu-bs.de>.
  28.  
  29. char SmartCompare_rcsid[] = 
  30.     "$Id: SmartC.C,v 1.2 1998/09/22 11:31:31 zeller Exp $";
  31.  
  32. #ifdef __GNUG__
  33. #pragma implementation
  34. #endif
  35.  
  36. #include "SmartC.h"
  37. #include "assert.h"
  38.  
  39. #include <ctype.h>
  40. #include <stdlib.h>
  41.  
  42. // Compare S1 and S2, taking numerals into account
  43. // returns < 0, > 0, or 0 iff S1 < S2, S1 > S2, or S1 == S2.
  44. int smart_compare(const char *s1, const char *s2)
  45. {
  46.     for (;;)
  47.     {
  48.     while (*s1 != '\0' && *s2 != '\0' && *s1 == *s2)
  49.         s1++, s2++;
  50.  
  51.     if (*s1 != '\0' && isdigit(*s1) && 
  52.         *s2 != '\0' && isdigit(*s2))
  53.     {
  54.         // Compare numerals numerically
  55.         const char *e1 = s1;
  56.         const char *e2 = s2;
  57.  
  58.         long i1 = strtol((char *)s1, (char **)&e1, 0);
  59.         long i2 = strtol((char *)s2, (char **)&e2, 0);
  60.  
  61.         assert(e1 != s1 && e2 != s2);
  62.  
  63.         int ret = i1 - i2;
  64.         if (ret != 0)
  65.         return ret;
  66.  
  67.         // Continue after numerals
  68.         s1 = e1;
  69.         s2 = e2;
  70.     }
  71.     else
  72.     {
  73.         // Simple string comparison
  74.         return *s1 - *s2;
  75.     }
  76.     }
  77. }
  78.  
  79. // Shell sort -- simple and fast
  80. #define SMART_SHELL_SORT(type, a, size) \
  81.     int h = 1; \
  82.     do { \
  83.     h = h * 3 + 1; \
  84.     } while (h <= size); \
  85.     do { \
  86.     h /= 3; \
  87.     for (int i = h; i < size; i++) \
  88.     { \
  89.         type v = a[i]; \
  90.         int j; \
  91.         for (j = i; j >= h && smart_compare(a[j - h], v) > 0; j -= h) \
  92.         a[j] = a[j - h]; \
  93.         if (i != j) \
  94.         a[j] = v; \
  95.     } \
  96.     } while (h != 1)
  97.  
  98.  
  99. // Sort array A, using smart_compare
  100. void smart_sort(StringArray& a)
  101. {
  102.     SMART_SHELL_SORT(string, a, a.size());
  103. }
  104.  
  105. // Sort array A, using smart_compare
  106. void smart_sort(char *a[], int size)
  107. {
  108.     SMART_SHELL_SORT(char *, a, size);
  109. }
  110.  
  111. // Sort array A, using smart_compare
  112. void smart_sort(string *a, int size)
  113. {
  114.     SMART_SHELL_SORT(string, a, size);
  115. }
  116.  
  117. // Remove adjacent duplicates in A
  118. void uniq(StringArray& a)
  119. {
  120.     StringArray b;
  121.  
  122.     for (int i = 0; i < a.size(); i++)
  123.     {
  124.     if (i == 0 || a[i - 1] != a[i])
  125.         b += a[i];
  126.     }
  127.     
  128.     a = b;
  129. }
  130.