Change the positions to be 0-based, instead of 1-based.

15 files changed, 100 insertions, 72 deletions

diff --git a/ChangeLog b/ChangeLog
index 52e34d0..e4f2495 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,31 @@
+2002-12-11  Bruno Haible  <bruno@clisp.org>
+
+	Change the positions to be 0-based, instead of 1-based.
+	* src/positions.h (Positions::LASTCHAR): Set to -1.
+	(Positions::MAX_SIZE): New constant.
+	(Positions::pointer): Change return type.
+	(Positions::_positions): Change element type.
+	(PositionIterator::EOS, PositionReverseIterator::EOS): Set to -2.
+	* src/positions.icc (Positions::pointer): Change return type.
+	(Positions::sort): Update.
+	* src/positions.cc (Positions::contains, Positions::add,
+	Positions::remove): Update.
+	(Positions::print): Update. Fix off-by-one bug.
+	* src/options.cc (Options::~Options): Update.
+	(Options::parse_options): Set BAD_VALUE to -3. Update.
+	* src/keyword.cc (KeywordExt::init_selchars_low): Update.
+	* src/search.cc (Search::find_positions, Search::compute_alpha_unify,
+	Search::find_alpha_inc): Update.
+	* src/output.cc (Output::output_hash_function): Update. Don't emit
+	a 'case' statement right after 'default:'.
+	* tests/c-parse.exp: Regenerated.
+	* tests/charsets.exp: Regenerated.
+	* tests/cplusplus.exp: Regenerated.
+	* tests/java.exp: Regenerated.
+	* tests/languages.exp: Regenerated.
+	* tests/modula2.exp: Regenerated.
+	* tests/objc.exp: Regenerated.
+
 2002-12-10  Bruno Haible  <bruno@clisp.org>
 
 	* src/options.h: Reorder enum values.
diff --git a/src/keyword.cc b/src/keyword.cc
index 2d7904e..fc819b6 100644
--- a/src/keyword.cc
+++ b/src/keyword.cc
@@ -91,12 +91,12 @@ KeywordExt::init_selchars_low (bool use_all_chars, const Positions& positions, c
           if (i == Positions::LASTCHAR)
             /* Special notation for last KEY position, i.e. '$'.  */
             c = static_cast<unsigned char>(_allchars[_allchars_length - 1]);
-          else if (i <= _allchars_length)
+          else if (i < _allchars_length)
             {
               /* Within range of KEY length, so we'll keep it.  */
-              c = static_cast<unsigned char>(_allchars[i - 1]);
+              c = static_cast<unsigned char>(_allchars[i]);
               if (alpha_inc)
-                c += alpha_inc[i - 1];
+                c += alpha_inc[i];
             }
           else
             /* Out of range of KEY length, so we'll just skip it.  */
diff --git a/src/options.cc b/src/options.cc
index 2439ae6..6e8793e 100644
--- a/src/options.cc
+++ b/src/options.cc
@@ -526,7 +526,7 @@ Options::~Options ()
             if (pos == Positions::LASTCHAR)
               fprintf (stderr, "$\n");
             else
-              fprintf (stderr, "%d\n", pos);
+              fprintf (stderr, "%d\n", pos + 1);
         }
 
       fprintf (stderr, "finished dumping Options\n");
@@ -767,7 +767,7 @@ Options::parse_options (int argc, char *argv[])
         case 'k':               /* Sets key positions used for hash function.  */
           {
             _option_word |= POSITIONS;
-            const int BAD_VALUE = -2;
+            const int BAD_VALUE = -3;
             const int EOS = PositionIterator::EOS;
             int       value;
             PositionStringParser sparser (/*getopt*/optarg, 1, Positions::MAX_KEY_POS, Positions::LASTCHAR, BAD_VALUE, EOS);
@@ -776,8 +776,8 @@ Options::parse_options (int argc, char *argv[])
               _option_word |= ALLCHARS;
             else
               {
-                unsigned char *key_positions = _key_positions.pointer();
-                unsigned char *key_pos;
+                int *key_positions = _key_positions.pointer();
+                int *key_pos;
 
                 for (key_pos = key_positions; (value = sparser.nextPosition()) != EOS; key_pos++)
                   {
@@ -788,16 +788,19 @@ Options::parse_options (int argc, char *argv[])
                         short_usage (stderr);
                         exit (1);
                       }
-                    if (key_pos - key_positions == Positions::MAX_KEY_POS + 1)
+                    if (key_pos - key_positions == Positions::MAX_SIZE)
                       {
-                        /* More than Positions::MAX_KEY_POS + 1 key positions.
+                        /* More than Positions::MAX_SIZE key positions.
                            Since all key positions are in the range
-                           1..Positions::MAX_KEY_POS or == Positions::LASTCHAR,
+                           0..Positions::MAX_KEY_POS-1 or == Positions::LASTCHAR,
                            there must be duplicates.  */
                         fprintf (stderr, "Duplicate key positions selected\n");
                         short_usage (stderr);
                         exit (1);
                       }
+                    if (value != Positions::LASTCHAR)
+                      /* We use 0-based indices in the class Positions.  */
+                      value = value - 1;
                     *key_pos = value;
                   }
 
diff --git a/src/output.cc b/src/output.cc
index 6e0d688..05ac35a 100644
--- a/src/output.cc
+++ b/src/output.cc
@@ -674,7 +674,7 @@ Output::output_hash_function () const
       /* Get the highest key position.  */
       key_pos = iter.next ();
 
-      if (key_pos == Positions::LASTCHAR || key_pos <= _min_key_len)
+      if (key_pos == Positions::LASTCHAR || key_pos < _min_key_len)
         {
           /* We can perform additional optimizations here:
              Write it out as a single expression. Note that the values
@@ -685,7 +685,7 @@ Output::output_hash_function () const
                   option[NOLENGTH] ? "" : "len + ");
 
           if (_key_positions.get_size() == 2
-              && _key_positions[0] == 1
+              && _key_positions[0] == 0
               && _key_positions[1] == Positions::LASTCHAR)
             /* Optimize special case of "-k 1,$".  */
             {
@@ -699,9 +699,9 @@ Output::output_hash_function () const
             {
               for (; key_pos != Positions::LASTCHAR; )
                 {
-                  printf ("asso_values[%sstr[%d]", char_to_index, key_pos - 1);
-                  if (_alpha_inc[key_pos - 1])
-                    printf ("+%u", _alpha_inc[key_pos - 1]);
+                  printf ("asso_values[%sstr[%d]", char_to_index, key_pos);
+                  if (_alpha_inc[key_pos])
+                    printf ("+%u", _alpha_inc[key_pos]);
                   printf ("]");
                   if ((key_pos = iter.next ()) != PositionIterator::EOS)
                     printf (" + ");
@@ -725,7 +725,7 @@ Output::output_hash_function () const
                   option[NOLENGTH] ? "0" : "len",
                   option[NOLENGTH] ? "len" : "hval");
 
-          while (key_pos != Positions::LASTCHAR && key_pos > _max_key_len)
+          while (key_pos != Positions::LASTCHAR && key_pos >= _max_key_len)
             if ((key_pos = iter.next ()) == PositionIterator::EOS)
               break;
 
@@ -734,13 +734,13 @@ Output::output_hash_function () const
               int i = key_pos;
               do
                 {
-                  for ( ; i >= key_pos; i--)
+                  for ( ; i > key_pos; i--)
                     printf ("      case %d:\n", i);
 
                   printf ("        hval += asso_values[%sstr[%d]",
-                          char_to_index, key_pos - 1);
-                  if (_alpha_inc[key_pos - 1])
-                    printf ("+%u", _alpha_inc[key_pos - 1]);
+                          char_to_index, key_pos);
+                  if (_alpha_inc[key_pos])
+                    printf ("+%u", _alpha_inc[key_pos]);
                   printf ("];\n");
 
                   key_pos = iter.next ();
diff --git a/src/positions.cc b/src/positions.cc
index f02ff67..2a096c1 100644
--- a/src/positions.cc
+++ b/src/positions.cc
@@ -35,7 +35,7 @@ bool
 Positions::contains (int pos) const
 {
   unsigned int count = _size;
-  const unsigned char *p = _positions + _size - 1;
+  const int *p = _positions + _size - 1;
 
   for (; count > 0; p--, count--)
     {
@@ -52,13 +52,13 @@ Positions::add (int pos)
 {
   unsigned int count = _size;
 
-  if (count == MAX_KEY_POS + 1)
+  if (count == MAX_SIZE)
     {
       fprintf (stderr, "Positions::add internal error: overflow\n");
       exit (1);
     }
 
-  unsigned char *p = _positions + _size - 1;
+  int *p = _positions + _size - 1;
 
   for (; count > 0; p--, count--)
     {
@@ -81,7 +81,7 @@ Positions::remove (int pos)
   unsigned int count = _size;
   if (count > 0)
     {
-      unsigned char *p = _positions + _size - 1;
+      int *p = _positions + _size - 1;
 
       if (*p == pos)
         {
@@ -90,7 +90,7 @@ Positions::remove (int pos)
         }
       if (*p < pos)
         {
-          unsigned char prev = *p;
+          int prev = *p;
 
           for (;;)
             {
@@ -106,7 +106,7 @@ Positions::remove (int pos)
                 }
               if (*p > pos)
                 break;
-              unsigned char curr = *p;
+              int curr = *p;
               *p = prev;
               prev = curr;
             }
@@ -123,17 +123,18 @@ Positions::print () const
   bool first = true;
   bool seen_LASTCHAR = false;
   unsigned int count = _size;
-  const unsigned char *p = _positions + _size - 1;
+  const int *p = _positions + _size - 1;
 
-  for (; count > 0; p--, count--)
+  for (; count > 0; p--)
     {
+      count--;
       if (*p == LASTCHAR)
         seen_LASTCHAR = true;
       else
         {
           if (!first)
             printf (",");
-          printf ("%d", *p);
+          printf ("%d", *p + 1);
           if (count > 0 && p[-1] == *p + 1)
             {
               printf ("-");
@@ -143,7 +144,7 @@ Positions::print () const
                   count--;
                 }
               while (count > 0 && p[-1] == *p + 1);
-              printf ("%d", *p);
+              printf ("%d", *p + 1);
             }
           first = false;
         }
diff --git a/src/positions.h b/src/positions.h
index 1c883a4..984195a 100644
--- a/src/positions.h
+++ b/src/positions.h
@@ -34,12 +34,17 @@ class Positions
   friend class PositionReverseIterator;
 public:
   /* Denotes the last char of a keyword, depending on the keyword's length.  */
-  enum {                LASTCHAR = 0 };
+  enum {                LASTCHAR = -1 };
 
-  /* Maximum key position specifiable by the user.
-     Note that this must fit into the element type of _positions[], below.  */
+  /* Maximum key position specifiable by the user, 1-based.
+     Note that MAX_KEY_POS-1 must fit into the element type of _positions[],
+     below.  */
   enum {                MAX_KEY_POS = 255 };
 
+  /* Maximum possible size.  Since duplicates are eliminated and the possible
+     0-based positions are -1 .. MAX_KEY_POS-1, this is:  */
+  enum {                MAX_SIZE = MAX_KEY_POS + 1 };
+
   /* Constructors.  */
                         Positions ();
                         Positions (int pos1);
@@ -56,7 +61,7 @@ public:
   unsigned int          get_size () const;
 
   /* Write access.  */
-  unsigned char *       pointer ();
+  int *                 pointer ();
   void                  set_size (unsigned int size);
 
   /* Sorts the array in reverse order.
@@ -74,11 +79,9 @@ public:
 private:
   /* Number of positions.  */
   unsigned int          _size;
-  /* Array of positions.  1 for the first char, 2 for the second char etc.,
-     LASTCHAR for the last char.
-     Note that since duplicates are eliminated, the maximum possible size
-     is MAX_KEY_POS + 1.  */
-  unsigned char         _positions[MAX_KEY_POS + 1];
+  /* Array of positions.  0 for the first char, 1 for the second char etc.,
+     LASTCHAR for the last char.  */
+  int                   _positions[MAX_SIZE];
 };
 
 /* This class denotes an iterator through a set of byte positions.  */
@@ -90,7 +93,7 @@ public:
                         PositionIterator (Positions const& positions);
 
   /* End of iteration marker.  */
-  enum {                EOS = -1 };
+  enum {                EOS = -2 };
 
   /* Retrieves the next position, or EOS past the end.  */
   int                   next ();
@@ -110,7 +113,7 @@ public:
                         PositionReverseIterator (Positions const& positions);
 
   /* End of iteration marker.  */
-  enum {                EOS = -1 };
+  enum {                EOS = -2 };
 
   /* Retrieves the next position, or EOS past the end.  */
   int                   next ();
diff --git a/src/positions.icc b/src/positions.icc
index 9475f69..32af6b1 100644
--- a/src/positions.icc
+++ b/src/positions.icc
@@ -84,7 +84,7 @@ Positions::get_size () const
 
 /* Write access.  */
 
-INLINE unsigned char *
+INLINE int *
 Positions::pointer ()
 {
   return _positions;
@@ -103,7 +103,7 @@ Positions::sort ()
 {
   /* Bubble sort.  */
   bool duplicate_free = true;
-  unsigned char *base = _positions;
+  int *base = _positions;
   unsigned int len = _size;
 
   for (unsigned int i = 1; i < len; i++)
diff --git a/src/search.cc b/src/search.cc
index 7ceb26c..a1b71a8 100644
--- a/src/search.cc
+++ b/src/search.cc
@@ -251,10 +251,10 @@ Search::find_positions ()
                 {
                   int n = keyword1->_allchars_length;
                   int i;
-                  for (i = 1; i < n; i++)
+                  for (i = 0; i < n - 1; i++)
                     {
-                      unsigned char c1 = keyword1->_allchars[i-1];
-                      unsigned char c2 = keyword2->_allchars[i-1];
+                      unsigned char c1 = keyword1->_allchars[i];
+                      unsigned char c2 = keyword2->_allchars[i];
                       if (option[UPPERLOWER])
                         {
                           if (c1 >= 'A' && c1 <= 'Z')
@@ -265,13 +265,13 @@ Search::find_positions ()
                       if (c1 != c2)
                         break;
                     }
-                  if (i < n)
+                  if (i < n - 1)
                     {
                       int j;
-                      for (j = i + 1; j <= n; j++)
+                      for (j = i + 1; j < n; j++)
                         {
-                          unsigned char c1 = keyword1->_allchars[j-1];
-                          unsigned char c2 = keyword2->_allchars[j-1];
+                          unsigned char c1 = keyword1->_allchars[j];
+                          unsigned char c2 = keyword2->_allchars[j];
                           if (option[UPPERLOWER])
                             {
                               if (c1 >= 'A' && c1 <= 'Z')
@@ -282,7 +282,7 @@ Search::find_positions ()
                           if (c1 != c2)
                             break;
                         }
-                      if (j > n)
+                      if (j >= n)
                         {
                           /* Position i is mandatory.  */
                           if (!mandatory.contains (i))
@@ -295,8 +295,8 @@ Search::find_positions ()
     }
 
   /* 2. Add positions, as long as this decreases the duplicates count.  */
-  int imax = (_max_key_len < Positions::MAX_KEY_POS
-              ? _max_key_len : Positions::MAX_KEY_POS);
+  int imax = (_max_key_len - 1 < Positions::MAX_KEY_POS - 1
+              ? _max_key_len - 1 : Positions::MAX_KEY_POS - 1);
   Positions current = mandatory;
   unsigned int current_duplicates_count = count_duplicates_tuple (current);
   for (;;)
@@ -304,7 +304,7 @@ Search::find_positions ()
       Positions best;
       unsigned int best_duplicates_count = UINT_MAX;
 
-      for (int i = imax; i >= 0; i--)
+      for (int i = imax; i >= -1; i--)
         if (!current.contains (i))
           {
             Positions tryal = current;
@@ -315,7 +315,7 @@ Search::find_positions ()
                or if it produces the same number of duplicates but with
                a more efficient hash function.  */
             if (try_duplicates_count < best_duplicates_count
-                || (try_duplicates_count == best_duplicates_count && i > 0))
+                || (try_duplicates_count == best_duplicates_count && i >= 0))
               {
                 best = tryal;
                 best_duplicates_count = try_duplicates_count;
@@ -337,7 +337,7 @@ Search::find_positions ()
       Positions best;
       unsigned int best_duplicates_count = UINT_MAX;
 
-      for (int i = imax; i >= 0; i--)
+      for (int i = imax; i >= -1; i--)
         if (current.contains (i) && !mandatory.contains (i))
           {
             Positions tryal = current;
@@ -348,7 +348,7 @@ Search::find_positions ()
                or if it produces the same number of duplicates but with
                a more efficient hash function.  */
             if (try_duplicates_count < best_duplicates_count
-                || (try_duplicates_count == best_duplicates_count && i == 0))
+                || (try_duplicates_count == best_duplicates_count && i == -1))
               {
                 best = tryal;
                 best_duplicates_count = try_duplicates_count;
@@ -370,9 +370,9 @@ Search::find_positions ()
       Positions best;
       unsigned int best_duplicates_count = UINT_MAX;
 
-      for (int i1 = imax; i1 >= 0; i1--)
+      for (int i1 = imax; i1 >= -1; i1--)
         if (current.contains (i1) && !mandatory.contains (i1))
-          for (int i2 = imax; i2 >= 0; i2--)
+          for (int i2 = imax; i2 >= -1; i2--)
             if (current.contains (i2) && !mandatory.contains (i2) && i2 != i1)
               for (int i3 = imax; i3 >= 0; i3--)
                 if (!current.contains (i3))
@@ -389,7 +389,7 @@ Search::find_positions ()
                        a more efficient hash function.  */
                     if (try_duplicates_count < best_duplicates_count
                         || (try_duplicates_count == best_duplicates_count
-                            && (i1 == 0 || i2 == 0 || i3 > 0)))
+                            && (i1 == -1 || i2 == -1 || i3 >= 0)))
                       {
                         best = tryal;
                         best_duplicates_count = try_duplicates_count;
@@ -422,7 +422,7 @@ Search::find_positions ()
             seen_lastchar = true;
           else
             {
-              fprintf (stderr, "%d", i);
+              fprintf (stderr, "%d", i + 1);
               first = false;
             }
         }
@@ -509,8 +509,8 @@ Search::compute_alpha_unify (const Positions& positions, const unsigned int *alp
                   unsigned int c;
                   if (i == Positions::LASTCHAR)
                     c = static_cast<unsigned char>(keyword->_allchars[keyword->_allchars_length - 1]);
-                  else if (i <= keyword->_allchars_length)
-                    c = static_cast<unsigned char>(keyword->_allchars[i - 1]);
+                  else if (i < keyword->_allchars_length)
+                    c = static_cast<unsigned char>(keyword->_allchars[i]);
                   else
                     continue;
                   if (c >= 'A' && c <= 'Z')
@@ -518,7 +518,7 @@ Search::compute_alpha_unify (const Positions& positions, const unsigned int *alp
                   if (c >= 'a' && c <= 'z')
                     {
                       if (i != Positions::LASTCHAR)
-                        c += alpha_inc[i - 1];
+                        c += alpha_inc[i];
                       /* Unify c with c - ('a'-'A').  */
                       unsigned int d = alpha_unify[c];
                       unsigned int b = c - ('a'-'A');
@@ -622,7 +622,7 @@ Search::find_alpha_inc ()
               if (key_pos == PositionIterator::EOS
                   || key_pos == Positions::LASTCHAR)
                 abort ();
-              indices[j] = key_pos - 1;
+              indices[j] = key_pos;
             }
         }
 
diff --git a/tests/c-parse.exp b/tests/c-parse.exp
index 405be7b..65033c6 100644
--- a/tests/c-parse.exp
+++ b/tests/c-parse.exp
@@ -57,7 +57,6 @@ hash (str, len)
   switch (hval)
     {
       default:
-      case 3:
         hval += asso_values[(unsigned char)str[2]];
       case 2:
       case 1:
diff --git a/tests/charsets.exp b/tests/charsets.exp
index 8b844ca..92f5a33 100644
--- a/tests/charsets.exp
+++ b/tests/charsets.exp
@@ -66,7 +66,6 @@ hash (str, len)
   switch (hval)
     {
       default:
-      case 22:
         hval += asso_values[(unsigned char)str[21]];
       case 21:
       case 20:
diff --git a/tests/cplusplus.exp b/tests/cplusplus.exp
index 598e95f..f8a4765 100644
--- a/tests/cplusplus.exp
+++ b/tests/cplusplus.exp
@@ -57,7 +57,6 @@ hash (str, len)
   switch (hval)
     {
       default:
-      case 7:
         hval += asso_values[(unsigned char)str[6]];
       case 6:
       case 5:
diff --git a/tests/java.exp b/tests/java.exp
index e2ca0c6..6965094 100644
--- a/tests/java.exp
+++ b/tests/java.exp
@@ -81,7 +81,6 @@ hash (str, len)
   switch (hval)
     {
       default:
-      case 3:
         hval += asso_values[(unsigned char)str[2]];
       case 2:
       case 1:
diff --git a/tests/languages.exp b/tests/languages.exp
index 9edb795..f30a856 100644
--- a/tests/languages.exp
+++ b/tests/languages.exp
@@ -70,7 +70,6 @@ hash (str, len)
   switch (hval)
     {
       default:
-      case 5:
         hval += asso_values[(unsigned char)str[4]+1];
       case 4:
       case 3:
diff --git a/tests/modula2.exp b/tests/modula2.exp
index f0f033d..a38ba5e 100644
--- a/tests/modula2.exp
+++ b/tests/modula2.exp
@@ -54,7 +54,6 @@ hash (str, len)
   switch (len)
     {
       default:
-      case 8:
         hval += asso_values[(unsigned char)str[7]];
       case 7:
         hval += asso_values[(unsigned char)str[6]];
diff --git a/tests/objc.exp b/tests/objc.exp
index 6d604da..316f63d 100644
--- a/tests/objc.exp
+++ b/tests/objc.exp
@@ -57,7 +57,6 @@ hash (str, len)
   switch (hval)
     {
       default:
-      case 3:
         hval += asso_values[(unsigned char)str[2]];
       case 2:
       case 1: