Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
  • Search
  • Get Qt Extensions
  • Unsolved
Collapse
Brand Logo
  1. Home
  2. Qt Development
  3. General and Desktop
  4. Find the maximum sub-string that can fit inside a field of certain pixel-width
Forum Updated to NodeBB v4.3 + New Features

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

Scheduled Pinned Locked Moved Unsolved General and Desktop
12 Posts 2 Posters 3.2k Views 1 Watching
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • H Offline
    H Offline
    Harry123
    wrote on last edited by Harry123
    #1

    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 ?

    1 Reply Last reply
    0
    • VRoninV Offline
      VRoninV Offline
      VRonin
      wrote on last edited by
      #2

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

      "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
      ~Napoleon Bonaparte

      On a crusade to banish setIndexWidget() from the holy land of Qt

      1 Reply Last reply
      2
      • H Offline
        H Offline
        Harry123
        wrote on last edited by Harry123
        #3

        @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 ?

        1 Reply Last reply
        0
        • VRoninV Offline
          VRoninV Offline
          VRonin
          wrote on last edited by
          #4

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

          "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
          ~Napoleon Bonaparte

          On a crusade to banish setIndexWidget() from the holy land of Qt

          1 Reply Last reply
          1
          • H Offline
            H Offline
            Harry123
            wrote on last edited by
            #5

            @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.

            VRoninV 1 Reply Last reply
            0
            • H Offline
              H Offline
              Harry123
              wrote on last edited by
              #6

              @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.

              1 Reply Last reply
              0
              • H 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.

                VRoninV Offline
                VRoninV Offline
                VRonin
                wrote on last edited by
                #7

                @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?

                "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
                ~Napoleon Bonaparte

                On a crusade to banish setIndexWidget() from the holy land of Qt

                1 Reply Last reply
                0
                • H Offline
                  H Offline
                  Harry123
                  wrote on last edited by Harry123
                  #8

                  @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.

                  1 Reply Last reply
                  0
                  • VRoninV Offline
                    VRoninV Offline
                    VRonin
                    wrote on last edited by VRonin
                    #9

                    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;
                    };
                    

                    "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
                    ~Napoleon Bonaparte

                    On a crusade to banish setIndexWidget() from the holy land of Qt

                    1 Reply Last reply
                    3
                    • H Offline
                      H Offline
                      Harry123
                      wrote on last edited by Harry123
                      #10

                      @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.

                      1 Reply Last reply
                      0
                      • H Offline
                        H Offline
                        Harry123
                        wrote on last edited by
                        #11

                        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
                        
                        VRoninV 1 Reply Last reply
                        1
                        • H 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
                          
                          VRoninV Offline
                          VRoninV Offline
                          VRonin
                          wrote on last edited by
                          #12

                          @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

                          "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
                          ~Napoleon Bonaparte

                          On a crusade to banish setIndexWidget() from the holy land of Qt

                          1 Reply Last reply
                          1

                          • Login

                          • Login or register to search.
                          • First post
                            Last post
                          0
                          • Categories
                          • Recent
                          • Tags
                          • Popular
                          • Users
                          • Groups
                          • Search
                          • Get Qt Extensions
                          • Unsolved