Building tags in iOS that take up minimal rows (0–1 Knapsack Problem in action)

In iOS development, collection views are widely used, and this article aims to demonstrate a solution for having tags in minimal rows. In other words, we want to have the following.

iPhone on the left presents tags in collection view in random order, iPhone on the right sorts the elements in a way to have minimal rows

It turns out, we have solutions to this. I will be explaining one of those. Let’s dive deep into world of algorithms (my dearest love ❤️). Have you ever heard of 0–1 Knapsack problem?

Imagine you are a robber, and you have a knapsack with you to rob a supermarket. In supermarket, there are items of various costs and weights. Your knapsack can hold up to X weight and you need to reason which items to take to maximize the cost of items you robbed. Well, it turns out that in the most of the cases, you need to take the items with minimal weight.

This problem belongs to the set of problems of Greedy algorithms. It doesn’t sure that you will always succeed by taking the minimal weighted item, but in most cases, you will be close to optimal solution.

Want to read this story later? Save it in Journal.

Now, in the case of ours we have tags and rows which have a fixed width. If in the end we’ll have 5 rows, think that we had 5 robbers. Each row presents a robber having a knapsack with the weight of row’s width. Our robber will take the items with maximal width as soon as it has no space to add a newer item.

Let’s code 👩‍💻

For this task, let’s create a UICollectionViewCell subclass and call it TagCollectionViewCell. See the implementation below.

class TagCollectionViewCell: UICollectionViewCell {
    @IBOutlet weak var backgroundVieww: UIView!
    @IBOutlet weak var titleLabel: UILabel!
    
    override var intrinsicContentSize: CGSize {
        return CGSize(width: self.titleLabel.intrinsicContentSize.width + 40.0, height: 45.0)
    }
    
    override func awakeFromNib() {
        super.awakeFromNib()
        self.backgroundVieww.layer.cornerRadius = 45/2
    }
    
    func config(info: String) {
        self.titleLabel.text = info
    }
}

We have a titleLabel (for tag text), backgroundVieww (UI purposes), and the most important part in here is to override cell’s intrinsicContentSize. We provide that cell’s intrinsic content size width should be label’s intrinsic content size’s width + 40.0, and height is fixed as 45.0. In my example, my label’s trailing and leading constraints are 20s, that’s why I have + 40.0 for my cell’s intrinsic content size width.

Since we are done with cell implementation, let’s see how’s the item sorting will be. I created an extension of collection view which will add the method of getting optimal cells. The method takes as parameters the cells in random order and the width of the row. I also created a class named RowInformation, which will store the selected cells for the row, spacing and width of the row that cells occupied. Let’s see the code and dive into it.

import Foundation
import UIKit

fileprivate class RowInformation {
    var spacing: CGFloat
    var cells: [UICollectionViewCell] = [] {
        didSet {
            width = cells.reduce(0.0, { $0 + $1.intrinsicContentSize.width })
            if !cells.isEmpty {
                width += CGFloat(cells.count - 1) * spacing
            }
        }
    }
    var width: CGFloat = 0.0
    
    init(spacing: CGFloat) {
        self.spacing = spacing
    }
}

extension UICollectionView {
    func getOptimalCells(_ cells: [UICollectionViewCell], maxWidth: CGFloat) -> [UICollectionViewCell] {
        var rows: [RowInformation] = []
        let spacing = (self.collectionViewLayout
            as? UICollectionViewFlowLayout)?.minimumInteritemSpacing ?? 0.0
        
        var cellsCopy = cells
        cellsCopy.sort(by: { $0.intrinsicContentSize.width > $1.intrinsicContentSize.width })
        
        cellsCopy.forEach { (cell) in
            var isAdded: Bool = false
            for row in rows {
                if row.width + cell.intrinsicContentSize.width + spacing < maxWidth {
                    row.cells.append(cell)
                    isAdded = true
                    break
                }
            }
            if !isAdded {
                let newRow = RowInformation(spacing: spacing)
                newRow.cells.append(cell)
                rows.append(newRow)
            }
        }
        
        cellsCopy = rows.reduce(into: [UICollectionViewCell](), { (cells, row) in
            cells.append(contentsOf: row.cells)
        })
        
        return cellsCopy
    }
}

Class RowInformation takes a spacing as init parameter which is the spacing between cells, it has cells which is an array of UICollectionViewCells and width — the width occupied by cells that were chosen to be in that row for optimality. While we add the cells in the group, we change the width based on cells’ intrinsic content size (that we had already overridden in cell’s implementation 😎) and the spacing.

Then, as I mentioned, I created a UICollectionView extension and added a method called getOptimalCells which takes as parameters the cells in random order and the width of the row. Implementation is as follows` firstly, it creates an empty array of rows (which are of type RowInformation), gets the spacing from collection view’s flow layout. Then, creates a copy of cells, sorts based on intrinsic content size width, for each sees if can fit into one of the rows, adds it, if it can’t, adds a new row with that cell. Lastly, it reduces rows into cells array and returns the sorted array. And boooom we have minimal rows for the problem ✨.

If you want to see this all in an action, I have a github repo of the whole code in a working example. Check it out — https://github.com/tateviktome/Tags

Thank u veryyy much! This was my first article !!! Clap if you liked it 😍. I will be sharing more in the future 😇.

📝 Save this story in Journal.

👩‍💻 Wake up every Sunday morning to the week’s most noteworthy stories in Tech waiting in your inbox. Read the Noteworthy in Tech newsletter.