Creating Column numbering like in Excecl i.e. A...Z then AA ... ZZ and so forth

Hi,
I wanted to have a numbering scheme for columns like the one provided by Office calculation programs.

My approach so far is this:

Code:

---

#include <QList>
#include <QStringList>
#include <QDebug>
 
QString getLabelFromInt(uint digit)
{
    uint base = 26;
 
    uint remainder;
    uint quotient = digit;
 
    QList<int> l;
    do {
        remainder = quotient % base;
        quotient = quotient / base;
        l.prepend(remainder);
    } while (quotient != 0);
 
    QStringList strList;
    for (int i = 0; i < l.size(); ++i)
        strList << QString(char(l[i] + 'a'));
 
    return strList.join("");
}
 
int main(int argc, char** arg) {
    for (int i = 0; i < 200; ++i)
        qDebug() << getLabelFromInt(i);
}

---

but it generates a-z but then continues with ba - zz and then baa - zzz. Considering an alphabet with two symbols (0 and 1) it would have to go like this:

0
1
00
01
10
11
000
001
010
011
100
101
110
111

instead of
0
1
10
11
100
101
110
111

Of course I see the pattern: the first one has 2^3+2^2+2^1 elements (since it includes the preceding combinations) while the second (normal) one has 2^3 elements but I can't put the pieces together.
Is there a simple way to implement this?

Thanx in advance
momesana

Ok, solved it myself in an ugly and hackish way. If someone knows a better way to do it, let me know!

Code:

---

#include <QList>
#include <QStringList>
#include <QDebug>
#include <QList>
#include <iostream>
#include <cmath>
 
QString getLabelFromInt(int digit)
{
    // TODO base should be based on the actual number
    // of letters in the locale of the user
    int base = 26;
    int n = 1;
    int tmp = base;
    int prevTmp = 0;
 
    while ((tmp - 1) < digit) {
      ++n;
      prevTmp = tmp;
      tmp += std::pow(base, n);
    };
 
    digit -= prevTmp;
 
    uint remainder;
    uint quotient = digit;
    QList<int> l;
    do {
        remainder = quotient % base;
        quotient = quotient / base;
        l.prepend(remainder);
    } while (quotient != 0);
 
    QStringList strList;
    for (int i = 0; i < l.size(); ++i)
        strList << QString(char(l[i] + 'a')); // TODO make this work for other locales as well
 
    for (int i = 0; i < n - l.size(); ++i)
      strList.prepend(QString('a')); // TODO make this work for other locales as well
 
    return strList.join("");
}
 
 
int main(int argc, char** arg) {
  for (int i = 0; i < 10000; ++i)
    qDebug() << getLabelFromInt(i);
 
}

---

Here is an improved version if anyone ever happens to need that code. If it shouldn't work for whatever reason use the code I posted first:

Code:

---

QString getLabelFromInt(int index) const
 {
   int base = 26;
   int n  = ((log10((index + 1) * (base - 1) + 1)) / log10(base));
   qMin(n, 1);
   index -= ((pow(base, n) - 1) / (base - 1)) - 1;
 
   int quotient = index;
   QList<int> intList;
   do {
     intList.prepend(quotient % base);
     quotient = quotient / base;
   } while (quotient != 0);
 
   QString str;
   for (unsigned i = 0; i < n - intList.size(); ++i)
     str += 'a';
 
   QList<int>::const_iterator iter;
   for (iter = intList.begin(); iter != intList.end(); ++iter)
     str += *iter + 'a';
 
   return str;
 }

---

and here is the C++ version without Qt

Code:

---

string getLabelFromInt(int index)
{
    int base = 26;
    int n  = ((log10((index + 1) * (base - 1) + 1)) / log10(base));
    n = (n < 1) ? 1 : n;
    index -= ((pow(base, n) - 1) / (base - 1)) - 1;
 
    int quotient = index;
    list<int> intList;
    do {
        intList.push_front(quotient % base);
        quotient = quotient / base;
    } while (quotient != 0);
 
    string str;
    for (unsigned i = 0; i < n - intList.size(); ++i)
      str += 'a';
 
    list<int>::const_iterator iter;
    for (iter = intList.begin(); iter != intList.end(); ++iter)
      str += *iter + 'a';
 
    return str;
}

---

Succumbed to the optimization devil inside me :-D. No one will ever use this code or probably even read this post but anyway, here is the (so far) final version:

Code:

---

QString getLabelFromInt(int index, char startingChar, int base)
 {
     double n  = log10((index + 1) * (base - 1) + 1) / log10(base);
     index -= ((pow(base, (int) n) - 1) / (base - 1)) - 1;
 
     QString result((int) n, QChar(startingChar));
     int quotient = index;
     int strIndex = result.length();
     do {
         result[--strIndex]= QChar(startingChar + quotient % base);
         quotient = quotient / base;
     } while (quotient != 0);
 
     return result;
 }

---

I read all the posts in this thread :)

The only thing that bothers me is that you are assuming that all characters for the symbols form a sequence. That's never the case for non-ascii alphabets, I'm afraid. Maybe it'd be better to pass an array of symbols?

Quote:

---

Originally Posted by wysota

I read all the posts in this thread :)

The only thing that bothers me is that you are assuming that all characters for the symbols form a sequence. That's never the case for non-ascii alphabets, I'm afraid. Maybe it'd be better to pass an array of symbols?

---

Yes, already realized that yesterday when I thought about making this work with arabic-like alphabets (I am persian and we use an alphabet based on arabic) and realized that you can't iterate over QChar and that the only viable solution is to provide a list, vector or something with the unicode characters in the correct order.

Thanks for the feedback :-)

You could change your code in a way similar to this:

Code:

---

class IndexIterator {
public:
  IndexIterator(...) {}
  QString nextIndex() {
    //... main part of your code goes here
  }
  virtual QChar nextCharacter() = 0;
  virtual void resetIterator() = 0;
};
 
class AsciiIndexIterator : public IndexIterator {
public:
  AsciiIndexIterator(...) : IndexIterator(...), m_current('A'){}
  QChar nextCharacter() {
    if(m_current=='Z') return QChar();
    return m_current++;
  }
  void resetIterator() { m_current = 'A'; }
private:
  char m_current;
};

---

You can then tell your code to use nextCharacter() to get the next character in sequence until you receive a null character. Then you know you've run out of characters and should call resetIterator() to go back to the first element of the sequence.

Interesting approach wysota. Will try that in the coming days. Meanwhile I found some bugs in the above code I had posted which is mainly due to floating point precision issues that causes a variable of type double with a value of (approximately) three to be turned into two when being casted to an int. Well, you guys probably all have read http://docs.sun.com/source/806-3568/ncg_goldberg.html but I hadn't so I wasted hours debugging this mysterious problem that turned up about 30 times for 500000 inputs.

Here is the updated version which takes an alphabet as a parameter in form of a QList<QChar>. It's still an unsatisfying solution for something like persian where letters are being joined and change their shape when put into a string. Thus, how to handle the resulting string (accessing the individual chars and render them separately or inserting whitespaces between the chars) is the job of the user of this function. Anyway, maybe it turns out to be useful to someone :-).

Code:

---

QString getLabelFromInt(int index, QList<QChar>& alphabet, int base)
{
    // Alphabet should have at least two elements
    if (alphabet.size() < 2)
      return QString();
 
    if (base < 2 || base > alphabet.size())
      base = alphabet.size();
 
    double tmp  = log10((index + 1) * (base - 1) + 1) / log10(base);
    int n = (int)floor(tmp + sqrt(numeric_limits<double>::epsilon()));
    index -= ((pow(base, n) - 1) / (base - 1)) - 1;
 
    QString result(n, alphabet[0]);
    int quotient = index;
    int strIndex = result.length();
    do {
        result[--strIndex] = alphabet[quotient % base];
        quotient = quotient / base;
    } while (quotient != 0);
 
    return result;
}

---

a better way using Qt using ASCII caracters.


QString getLabelFromInt(int number)
{
return QString::number(number,36);
}
using base 36 to convert a number to string, include the number 0-9 and a-z caracters



y try to find a more compact, but i think is not possible :)

I don't see how that would solve the problem at hand. The code is not about mere base conversion in conjunction with turning the result into a string. Just compare your results with the ones provided by my function.