Find the maximum sub-string that can fit inside a field of certain pixel-width

Harry123

Given a string and a field of certain pixel-width, I need to find the maximum sub-string that can fit inside the field. The idea is to cut-up a long string into sub-strings that will be displayed as lines. For technical reasons, I cannot use QTextEdit or other widgets for the display.

My current solution is to divide the total pixel-width of the string by the width of an "average" character, giving an initial guess. Let's call this number N. I then loop calculating the width of a sub-string of N characters, adding or subtracting 1 to N, until I find the maximum sub-string that will fit.

As this procedure is very slow when executed many times, does someone have a better/faster idea ?

VRonin

I think what you are after is http://doc.qt.io/qt-5/qfontmetrics.html#elidedText

Harry123

@VRonin

Thanks for the answer.

QFontMetrics::elidedText() will give a better first guess (N above) than dividing by the "average" character. But as it is not exact, taking space for the "...", my algorithm is still required for an exact fit.

This is a good improvement, but is there a way that does not require the loop of +-1 ?

VRonin

You can still use the loop but use QFontMetrics::size::width instead to get the precise size

Harry123

@VRonin : This is about what I do now.

Strange that the developer who wrote QFontMetrics::elidedText did not think of it, since a best-fit function should be very similar in code.

Harry123

@VRonin :

I tried it, and the performance of QFontMetrics::elidedText was MUCH worst than my own loop.
People who try to use it in the future should be aware that its performance is atrocious.

So still no better solution except my own ugly slow loop.

VRonin

@Harry123 said in Find the maximum sub-string that can fit inside a field of certain pixel-width:

trange that the developer who wrote QFontMetrics::elidedText did not think of it,

They actually did, I was just too lazy to open the doc page. Just use elidedText with Qt::ElideNone as second argument to have no ellipsis

@Harry123 said in Find the maximum sub-string that can fit inside a field of certain pixel-width:

the performance of QFontMetrics::elidedText was MUCH worst

Strange, could you show us your code?

Harry123

@VRonin :
This is not rocket science, you know.
The only difference is that according to your last remark, a loop using QFontMetrics::width calls was replaced by the call QString elided = fontmetrics.elidedText(text, Qt::ElideNone, npixels); and then return elided.length().

I timed it, and to parse 40+ KB of text into chunks of 800 pixels :

QFontMetrics::width loop starting with division by "average" character width : about 1 minute
QFontMetrics::elidedText : after 10 minutes I ran out of patience and stopped it
Using Windows API : very fast

Probably elidedText does not use my small optimization of division by "average" character width.

I also wonder why QFontMetrics::width is slower than using native API. Some of it may be because with the API no time is wasted on creating and destroying objects such as QString.

VRonin

After testing I have 2 things to say:

Qt::ElideNone does not do what the docs imply, it just does not elide at all
As you correctly suggested elidedText is slower than a manual loop

On the other hand I get your processing times to be quite off... with the code below I split the entire Shakespeare's Hamlet (177kB) in 800 pixels in 9 seconds in debug mode and 1.7 seconds in release mode

#include <QWidget>
#include <QPushButton>
#include <QPlainTextEdit>
#include <QVBoxLayout>
#include <QDebug>
class Elider : public QWidget{
    Q_OBJECT
    Q_DISABLE_COPY(Elider)
public:
    explicit Elider(QWidget* parent=nullptr)
        :QWidget(parent)
        ,m_elidePixels(800)
    {
        m_original=new QPlainTextEdit(this);
        m_elided=new QPlainTextEdit(this);
        m_elided->setReadOnly(true);
        m_processBtn=new QPushButton("Process",this);
        connect(m_processBtn,&QPushButton::clicked,this,&Elider::elideText);
        QVBoxLayout* mainLay=new QVBoxLayout(this);
        mainLay->addWidget(m_original);
        mainLay->addWidget(m_elided);
        mainLay->addWidget(m_processBtn);
    }
    int elidePixels() const
    {
        return m_elidePixels;
    }

    void setElidePixels(int elidePixels)
    {
        m_elidePixels = elidePixels;
    }

private slots:
   void elideText(){
        m_elided->clear();
        QString BaseString = m_original->toPlainText();
        const QFontMetrics fontmetrics(m_elided->font());
        while(BaseString.size()>0){
            int fragmentLeng=m_elidePixels/fontmetrics.width("a");//fontmetrics.elidedText(BaseString,Qt::ElideRight, m_elidePixels).size()-1;
            for(;fontmetrics.width(BaseString.left(fragmentLeng))<=m_elidePixels && fragmentLeng<=BaseString.size();++fragmentLeng)
            {}
            for(;fontmetrics.width(BaseString.left(fragmentLeng))>m_elidePixels && fragmentLeng>0;--fragmentLeng)
            {}
            m_elided->appendPlainText(BaseString.left(fragmentLeng)+'\n');
            BaseString.remove(0,fragmentLeng);
        }
    }

private:
    int m_elidePixels;
    QPushButton* m_processBtn;
    QPlainTextEdit* m_original;
    QPlainTextEdit* m_elided;
};

Harry123

@VRonin :
My code does much more than just calculate offsets, but it also unfortunately does creation/deletion of objects inside the loop.
I'm already in the process of optimizing it to avoid that, the end result leaning more in the direction of your code.

Thank you for your help and interest.

I do not mark this post as solved, since no other solution was found except for loops starting from an initial guess.
As a remark, elidedText could do with some serious optimization.

Harry123

An important optimization of the code contributed by @VRonin is by setting the initial guess in a proportional manner by using the formula of:

guess = (pixel-width / pixel-width-of-string) * number-of-characters-in-string

VRonin

@Harry123 Further improvements:

use leftRef instead of left() (everywhere apart from appendPlainText)
since this is basically find the maximum fragmentLeng that satisfies the constrains: fontmetrics.width(BaseString.left(fragmentLeng))<=m_elidePixels and fragmentLeng<=BaseString.size():
- you can use a bracket and solve algorithm for fontmetrics.width(BaseString.left(fragmentLeng))-m_elidePixels and then return the lower bound of the bracket
- probably overkill but you can use a specialised library for function optimisation rather than just trying every single fragmentLeng value as I'm doing