Recently I faced an interesting task to display hierarchical data as a list for the iOS platform. For example, displaying folders and related files is convenient in this mode. Here is the package to visualize hierarchical data as a list with the search feature: . SwiftListTreeDataSource Popular solutions for Apple platforms: . Apple adds this feature starting iOS 14. The downside: no support for old iOS versions, no search support. NSDiffableDataSourceSectionSnapshot . Looks really great, supports old OS versions, MIT license. The downside: created many issues and no support starting 2016. Implementation depends on UITableView a lot, adding search support will require quite some rework and most likely will create stability concerns for the component. RATreeView So it was decided to create a package that will allow addressing all the functional requirements. Note: example source code includes only key points of the algorithm. For the final version, please check the link above. Display hierarchy, simple case Despite the hierarchical nature of data from the example, we can see that this is the same flat list to display. The indentation is the decoration of the list item, which can be calculated based on its nesting level. To handle this scenario, we need to create a simple list from a hierarchical structure: add children after each parent element. Let’s create models and a method to build a data source for the list. Now we can use a created data source, for example, in : UITableView Handle unlimited nesting Let’s consider a more complex example, in which nesting has no restrictions: From the data structure, we can see its recursive nature: an element can contain several elements of the same type, which themselves can also contain elements, and so on. For this task, we need to update the model: makes sense for nesting 1, but here we need to know the depth level of the element. Let’s name the new model for displaying : isChild TreeItem Let’s add two properties, and : parent level is needed to determine the relationship between elements and will also help to determine the depth of nesting. parent is a property that stores nesting, calculated once through to avoid wasting resources when constantly accessing it. level level (of:) The implementation of loops through the chain of available parents each time incrementing the counter: finally, the number of available parents makes it possible to calculate the depth of the current element. level (of :) Data processing First, we need to convert the original data model to a so that it can be used for displaying items. Let’s put the logic in a separate class named . TreeItem ListTreeDataSource The method checks where items need to be added: to an existing parent or as root. If a parent is specified, then the lookup table is checked and added to otherwise, to . The target are created, cached, and added to the target array. append (_: to :) parentBackingItem.subitems backingStore TreeItems The lookup table allows us to quickly find the target for a given item. Otherwise, we have to traverse the entire tree every time, which is not really efficient. TreeItem To add the entire hierarchy of objects, we can write a small utility that recursively traverses and adds all the elements: is a data store in a format convenient for us, but it is not enough to display the data. To do this, we need to build a flat list from this hierarchical store. Let’s write a generic version to create a list data source and name it : TreeDataSource.backingStore depthFirstFlattened The recursive implementation looks pretty straightforward: after each parent, add all of its nested elements before moving on to the next one. In fact, this is a depth-first traversal of the graph with the accumulation of the traversed elements to the “flat” list. The output is a one-dimensional perspective on a tree (an array of nodes), which can be used as a data source for a UI framework. Data for the list Now we can fix the TODO for items needed by the UI component: There’s an option to call method automatically when data changes (after calling for example). The downside is that if we have thousands of nodes, it will create serious performance problems as it will be constantly called. Therefore, we’ll keep it up to the user of the component, providing more control. reload append Display only expanded nested elements This requires a little tweak: create property and filter which child items will be shown: TreeItem.isExpanded Example usage with UITableView: The structure of the component also provides the ability to add new data to the existing state, e.g., in case of deferred loading/loading on demand. Methods for inserting/deleting elements are also available but not described to make the material more compact. Decrease indentation for deep nesting The formula for determining the indentation can be improved. For example, on the iPhone 5, it is difficult to fit even a small hierarchy. Below are attached screenshots of the current vs. desired visual state of deep nesting. My good friend from the data analysis department helped with the to try to fit the indentation into space available: exponential decay formula Optimizing performance A recursive implementation looks elegant, but it can be problematic for a large dataset. To achieve optimal performance on older devices, let’s rewrite the and traversal algorithms using an iterative style through the queue and stack: breadth-first depth-first Performance testing Testing machine specification: MacBook Pro 2019, 2,6 GHz 6-Core Intel Core i7, 16 GB 2667 MHz DDR4 It was also interesting to compare the performance with the Apple component, but I guess this will not be very correct since it also combines the functionality of and probably does more work providing less control. For the sake of interest, two performance tests: NSDiffableDataSourceSectionSnapshot Search feature The task is also to provide the ability to search for all elements, with the following criteria: Capability to find target elements by search criteria, both parents and children. Show full path to target elements (keep the same visual structure). If a parent element is found with children that do not match the search criteria, do not apply the filter to them (search for a folder when we do not know the content). Keep the option to hide / open parent elements. Let’s visually represent our task: In this case, there’re couple of key points: The entire data set is used for search, including the children of the leaf levels. The parent elements may or may not match the search criteria, but we need them to display the entire path. If a parent is found with children that do not match the search criteria, do not apply the filter to them. But if there are children that meet the criterion, then the filter will be applied. Note: this is an arguable point and may depend on business requirements, I took inspiration based on how the filter works in Xcode by project files, although there are slight differences. To do this, we will create a new class that extends the capabilities of the previous one. Here we can also apply the depth-first traversal method,  with an additional filter: Preparing state for filter: is a flat list of all “ ” items for search, cached to optimize resource consumption. The data source for the filter. allFlattenedItemStore expanded Reset the state of all elements by isExpanded = false . Retrieving — the search targets obtained by applying the filter to filteredTargetItems allFlattenedItemStore . Get — the set of parents of the target items. targetItemsTraversedParentSet Mark items in as to expose the path to target items. targetItemsTraversedParentSet isExpanded=true Preparation of the state is complete, invoke depth-first traversal with a filter that is determined by the current state in isIncludedInExpand . Filter logic: If the element is the root, then it needs to match the search criteria or be included in the set targetItemsTraversedParentSet . If the element itself is included in the set of , then it fits criteria (such as ). targetItemsTraversedParentSet RootChild_2 The filter is then applied to all items whose parents are in the set. Additionally, the user can expand the target element of the search, and therefore ` ` is needed to include the rest of the child elements. targetItemsTraversedParentSet else true Summary The final component does not depend on the UI frameworks and can be used with UITableView, UICollectionView, NSTableView, SwiftUI, or in a console application. All source code and demo with examples can be checked on . The component includes unit tests and performance tests. GitHub Thank you for the reading! I hope the material was useful. Any feedback is welcome.

The Graph

Chain

Apple

Intel

Target

Read My Stories

Too Long; Didn't Read

In your car, at home, or at work — Bosch technology shapes many areas of life.

Display Hierarchical Data as List with Search Feature

Too Long; Didn't Read

Companies Mentioned

Coins Mentioned

Dzmitry Antonenka

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Display Hierarchical Data as List with Search Feature

Too Long; Didn't Read

Companies Mentioned

Coins Mentioned

Dzmitry Antonenka

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES