aapl/compare.h

   1 /*
   2  *  Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   7  *  Aapl is free software; you can redistribute it and/or modify it under the
   8  *  terms of the GNU Lesser General Public License as published by the Free
   9  *  Software Foundation; either version 2.1 of the License, or (at your option)
  10  *  any later version.
  11  *
  12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
  13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  15  *  more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public License
  18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
  19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 #ifndef _AAPL_COMPARE_H
  23 #define _AAPL_COMPARE_H
  24
  25 #include <string.h>
  26 #include "table.h"
  27
  28 #ifdef AAPL_NAMESPACE
  29 namespace Aapl {
  30 #endif
  31
  32 /**
  33  * \defgroup compare Compare
  34  * \brief Basic compare clases.
  35  *
  36  * Compare classes are used by data structures that need to know the relative
  37  * ordering of elemets. To become a compare class, a class must imlement a
  38  * routine long compare(const T &key1, const T &key2) that behaves just like
  39  * strcmp.
  40  *
  41  * Compare classes are passed to the template data structure as a template
  42  * parameter and are inherited. In most cases the compare routine will base
  43  * the key comparision only on the two keys and the compare routine can
  44  * therefore be static. Though sometimes it is useful to include data in the
  45  * compare class and use this data in the comparison. For example the compare
  46  * class may contain a pointer to some other data structure to which the
  47  * comparison is delegated.
  48  *
  49  * @{
  50  */
  51
  52 /**
  53  * \brief Compare two null terminated character sequences.
  54  *
  55  * This comparision class is a wrapper for strcmp.
  56  */
  57 struct CmpStr
  58 {
  59         /**
  60          * \brief Compare two null terminated string types.
  61          */
  62         static inline long compare(const char *k1, const char *k2)
  63                 { return strcmp(k1, k2); }
  64 };
  65
  66 /**
  67  * \brief Compare a type for which < and > are implemented.
  68  *
  69  * CmpOrd is suitable for simple types such as integers and pointers that by
  70  * default have the less-than and greater-than operators defined.
  71  */
  72 template <class T> struct CmpOrd
  73 {
  74         /**
  75          * \brief Compare two ordinal types.
  76          *
  77          * This compare routine copies its arguements in by value.
  78          */
  79         static inline long compare(const T k1, const T k2)
  80         {
  81                 if (k1 < k2)
  82                         return -1;
  83                 else if (k1 > k2)
  84                         return 1;
  85                 else
  86                         return 0;
  87         }
  88 };
  89
  90 /**
  91  * \brief Compare two tables of type T
  92  *
  93  * Table comparison is useful for keying a data structure on a vector or
  94  * binary search table. T is the element type stored in the table.
  95  * CompareT is the comparison structure used to compare the individual values
  96  * in the table.
  97  */
  98 template < class T, class CompareT = CmpOrd<T> > struct CmpTable
  99                 : public CompareT
 100 {
 101         /**
 102          * \brief Compare two tables storing type T.
 103          */
 104         static inline long compare(const Table<T> &t1, const Table<T> &t2)
 105         {
 106                 if ( t1.tabLen < t2.tabLen )
 107                         return -1;
 108                 else if ( t1.tabLen > t2.tabLen )
 109                         return 1;
 110                 else
 111                 {
 112                         T *i1 = t1.data, *i2 = t2.data;
 113                         long len = t1.tabLen, cmpResult;
 114                         for ( long pos = 0; pos < len;
 115                                         pos += 1, i1 += 1, i2 += 1 )
 116                         {
 117                                 cmpResult = CompareT::compare(*i1, *i2);
 118                                 if ( cmpResult != 0 )
 119                                         return cmpResult;
 120                         }
 121                         return 0;
 122                 }
 123         }
 124 };
 125
 126 /**
 127  * \brief Compare two tables of type T -- non-static version.
 128  *
 129  * CmpTableNs is identical to CmpTable, however the compare routine is
 130  * non-static.  If the CompareT class contains a non-static compare, then this
 131  * version must be used because a static member cannot invoke a non-static
 132  * member.
 133  *
 134  * Table comparison is useful for keying a data structure on a vector or binary
 135  * search table. T is the element type stored in the table. CompareT
 136  * is the comparison structure used to compare the individual values in the
 137  * table.
 138  */
 139 template < class T, class CompareT = CmpOrd<T> > struct CmpTableNs
 140                 : public CompareT
 141 {
 142         /**
 143          * \brief Compare two tables storing type T.
 144          */
 145         inline long compare(const Table<T> &t1, const Table<T> &t2)
 146         {
 147                 if ( t1.tabLen < t2.tabLen )
 148                         return -1;
 149                 else if ( t1.tabLen > t2.tabLen )
 150                         return 1;
 151                 else
 152                 {
 153                         T *i1 = t1.data, *i2 = t2.data;
 154                         long len = t1.tabLen, cmpResult;
 155                         for ( long pos = 0; pos < len;
 156                                         pos += 1, i1 += 1, i2 += 1 )
 157                         {
 158                                 cmpResult = CompareT::compare(*i1, *i2);
 159                                 if ( cmpResult != 0 )
 160                                         return cmpResult;
 161                         }
 162                         return 0;
 163                 }
 164         }
 165 };
 166
 167 /**
 168  * \brief Compare two implicitly shared tables of type T
 169  *
 170  * This table comparison is for data structures based on implicitly
 171  * shared tables.
 172  *
 173  * Table comparison is useful for keying a data structure on a vector or
 174  * binary search table. T is the element type stored in the table.
 175  * CompareT is the comparison structure used to compare the individual values
 176  * in the table.
 177  */
 178 template < class T, class CompareT = CmpOrd<T> > struct CmpSTable : public CompareT
 179 {
 180         /**
 181          * \brief Compare two tables storing type T.
 182          */
 183         static inline long compare(const STable<T> &t1, const STable<T> &t2)
 184         {
 185                 long t1Length = t1.length();
 186                 long t2Length = t2.length();
 187
 188                 /* Compare lengths. */
 189                 if ( t1Length < t2Length )
 190                         return -1;
 191                 else if ( t1Length > t2Length )
 192                         return 1;
 193                 else {
 194                         /* Compare the table data. */
 195                         T *i1 = t1.data, *i2 = t2.data;
 196                         for ( long pos = 0; pos < t1Length;
 197                                         pos += 1, i1 += 1, i2 += 1 )
 198                         {
 199                                 long cmpResult = CompareT::compare(*i1, *i2);
 200                                 if ( cmpResult != 0 )
 201                                         return cmpResult;
 202                         }
 203                         return 0;
 204                 }
 205         }
 206 };
 207
 208 /**
 209  * \brief Compare two implicitly shared tables of type T -- non-static
 210  * version.
 211  *
 212  * This is a non-static table comparison for data structures based on
 213  * implicitly shared tables. If the CompareT class contains a non-static
 214  * compare, then this version must be used because a static member cannot
 215  * invoke a non-static member.
 216  *
 217  * Table comparison is useful for keying a data structure on a vector or
 218  * binary search table. T is the element type stored in the table.
 219  * CompareT is the comparison structure used to compare the individual values
 220  * in the table.
 221  */
 222 template < class T, class CompareT = CmpOrd<T> > struct CmpSTableNs
 223                 : public CompareT
 224 {
 225         /**
 226          * \brief Compare two tables storing type T.
 227          */
 228         inline long compare(const STable<T> &t1, const STable<T> &t2)
 229         {
 230                 long t1Length = t1.length();
 231                 long t2Length = t2.length();
 232
 233                 /* Compare lengths. */
 234                 if ( t1Length < t2Length )
 235                         return -1;
 236                 else if ( t1Length > t2Length )
 237                         return 1;
 238                 else {
 239                         /* Compare the table data. */
 240                         T *i1 = t1.data, *i2 = t2.data;
 241                         for ( long pos = 0; pos < t1Length;
 242                                         pos += 1, i1 += 1, i2 += 1 )
 243                         {
 244                                 long cmpResult = CompareT::compare(*i1, *i2);
 245                                 if ( cmpResult != 0 )
 246                                         return cmpResult;
 247                         }
 248                         return 0;
 249                 }
 250         }
 251 };
 252
 253
 254 /*@}*/
 255
 256 #ifdef AAPL_NAMESPACE
 257 }
 258 #endif
 259
 260 #endif /* _AAPL_COMPARE_H */