Splitting a long string based on its graphical presentation

Question

I got a long string, let's call it Story. I fetch this story from a database so I don't know how long it is.

I want to display this story in a view, but what if the story is too long so it doesn't fit in one view?

I don't want to adjust the font size because it may be a very long story and making the font size smaller is not a good solution.

Therefore I want to split the Story into more than one view. By passing the story and getting a separated story as an array of String every item in the array can fit in one view.

This is the code, it hopefully gives you a hint what I'm trying to achieve exactly:

extension String {

    /// - returns: The height that will fit Self
    func height(withConstrainedWidth width: CGFloat, font: UIFont) -> CGFloat {
        let constraintRect = CGSize(width: width, height: .greatestFiniteMagnitude)
        let boundingBox = self.boundingRect(with: constraintRect, options: .usesLineFragmentOrigin, attributes: [.font: font], context: nil)
        return ceil(boundingBox.height)
    }

    #warning("it's so slow that i can't handle it in main thread , ( 21 second for 15 items in array )")
    /// complition contains the separated string as array of string
    func splitToFitSize(_ size : CGSize = UIScreen.main.bounds.size ,font : UIFont = UIFont.systemFont(ofSize: 17) , complition : @escaping (([String]) -> Void) )  {
        DispatchQueue.global(qos: .background).async {

            // contents contains all the words as Array of String
            var contents = self.components(separatedBy: .whitespaces)

            var values : [String] = []
            for content in contents {
                // if one word can't fit the size -> remove it , which it's not good, but i don't know what to do with it
                guard content.isContentFit(size: size , font : font) else {contents.removeFirst(); continue;}
                if values.count > 0 {
                    for (i , value) in values.enumerated() {
                        var newValue = value
                        newValue += " \(content)"
                        if newValue.isContentFit(size: size, font: font) {
                            values[i] = newValue
                            contents.removeFirst()
                            break;
                        }else if i == values.count - 1 {
                            values.append(content)
                            contents.removeFirst()
                            break;
                        }
                    }
                }else {
                    values.append(content)
                    contents.removeFirst()
                }
            }
            complition(values)
        }
    }

    /// - returns: if Self can fit the passing size
    private func isContentFit(size : CGSize, font : UIFont) -> Bool{
        return self.height(withConstrainedWidth: size.width, font: font) < size.height
    }
}

This code is working, but it takes very long. If I want to split a story to 15 views it takes 20 seconds or even longer.

How can I optimize this so it runs faster?

Answer 1

General remarks

Here are some general remarks that could make your code look a little cleaner :

• Avoid using ; at the end of an instruction unless you have to put multiple instructions in the same line.
• Document the functions properly: The description of the complition parameter of splitToFitSize isn't well formatted.
• The correct spelling of complition is completion.
• This is subjective and probably nitpicky: Put a space only where needed, one after the closing curly brace of a scope: } else, and none before a punctuation sign: (size: size, font: font).

Catching the culprits

Sources of slow code:

• " \(content)": String interpolation is slow as previously stated here.
• self.components(separatedBy: .whitespaces): This has both a time and space complexity of O(n). Better iterate over the story with a String.Index.
• DispatchQueue.global(qos: .background) : This is the lowest priority you could give to code and it wastes time by switching from the main thread to a background one, and back.

• contents.removeFirst(): This is called in multiple places and repeatedly. Each call is O(n) since all the elements of the contents array shifted (Have a look here). This means that this algotithm shifts the elements of the contents array n + (n-1) + (n-2) + ... + 1 times. Knowing that : $$n + (n-1) + (n-2) + ... + 1 = \frac{n(n+1)}{2}$$

  it makes this algorithm O(n²), with n being the number of elements in contents. To circumvent this use an index that traverses the array.

---

Alternative implementation

Here is an alternative solution to split a string into a given size using a certain font :

extension String {

    static let blanks: [Character] = [" ", "\n", "\t"]

    func splitToFit (size: CGSize, using font: UIFont) -> [String] {
        var output: [String] = []
        var (fitted, remaining) = fit(self, in: size, using: font)
        var lastCount = fitted.count
        output.append(fitted)

        while remaining != "" {
            (fitted, remaining) = fit(remaining,
                                      in: size,
                                      using: font,
                                      lastCount: lastCount)
            lastCount = fitted.count
            output.append(fitted)
        }

        //Trim white spaces if needed
        //return output.map { $0.trimmingCharacters(in: .whitespacesAndNewlines)}
        return output
    }

    private func fit(
        _ str: String,
        in size: CGSize,
        using font: UIFont,
        lastCount: Int = 0) -> (String, String) {

        if !str.isTruncated(in: size, using: font) {
            return (str, "")
        }

        var low = 0
        var high = str.count - 1
        let lastValidIndex = high
        var substr = ""
        let step = lastCount/10  //Could be adjusted


        if lastCount != 0 {
            high = min(lastCount, lastValidIndex)
            while !str[0..<high].isTruncated(in: size, using: font) {
                low = high
                high = min(high + step, lastValidIndex)
            }
        }

        while low < high - 1 {
            let mid = low + (high - low)/2 
            //Or more efficiently 
            //let mid = Int((UInt(low) + UInt(high)) >> 1)
            //Have a look here https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

            substr = str[0..<mid]

            let substrTruncated = substr.isTruncated(in: size, using: font)

            if substrTruncated {
                high = mid
            } else  {
                low = mid
            }
        }

        substr = str[0..<low]

        while !String.blanks.contains(substr.last!) {
            substr.removeLast()
            low -= 1
        }

        let remains = str[low..<str.count]
        return (substr, remains)
    }
}

It calls these other extensions :

extension String {
    func isTruncated(in size: CGSize, using font: UIFont) -> Bool {
        let textSize = (self as NSString)
            .boundingRect(with: CGSize(width: size.width,
                                       height: .greatestFiniteMagnitude),
                          options: .usesLineFragmentOrigin,
                          attributes: [.font: font],
                          context: nil).size

        return ceil(textSize.height) > size.height
    }

    subscript (range: Range<Int>) -> String {
        let startIndex = self.index(self.startIndex, offsetBy: range.lowerBound)
        let endIndex = self.index(self.startIndex, offsetBy: range.upperBound)
        let range = startIndex..<endIndex

        return String(self[range])
    }
}

This code is inspired by this library but twice as fast 🚀. Further improvements are possible.

It was tested using the following code:

class ViewController: UIViewController, UIScrollViewDelegate {

    var scrollView: UIScrollView! {
        didSet{
            scrollView.delegate = self
        }
    }

    private let font = UIFont.systemFont(ofSize: 17)

    override func viewDidLoad() {
        super.viewDidLoad()

        let width = view.frame.width
        let height = view.frame.height
        let labelSize = CGSize(width: width - 40.0, height: height - 60.0)
        //Split the story here
        //let start = Date()
        let strings = story.splitToFit(size: labelSize, using: font)
        //let end = Date()
        //print("time =", end.timeIntervalSince(start))

        let scrollViewFrame = CGRect(x: 0,
                                     y: 0,
                                     width: width,
                                     height: height)

        scrollView = UIScrollView(frame: scrollViewFrame)
        scrollView.contentSize = CGSize(width: width * CGFloat(strings.count), height: height)
        scrollView.isPagingEnabled = true

        let colors: [UIColor] = [.red, .green, .blue]

        for i in 0 ..< strings.count {
            let label = UILabel()
            label.numberOfLines = 0
            label.frame = CGRect(origin: CGPoint(x: width * CGFloat(i) + 20.0,
                                                 y: 40.0),
                                 size: labelSize)
            label.backgroundColor = colors[i % 3]
            label.font = font
            label.text = strings[i]
            label.translatesAutoresizingMaskIntoConstraints = false
            scrollView.addSubview(label)
        }

        view.addSubview(scrollView)
    }
}

with story being a 10-paragraph string, 1104 total words, 7402 total characters, generated on this website, it takes 54ms on my local machine to split the story.

If the story is too long, and to avoid blocking the main thread I would recommend adding subviews asynchronously to the UIScrollView as the fitted strings are calculated one by one.