It’s time to get “algorithmical” and solve a problem that could easily be implemented using a poorly performing algorithm the performant way.
The challenge is quite straightforward. For each of the entries in a structure, output the the title of the entry and its ancestors in a breadcrumb manner. So for example given the following structure:
Entry 1
Entry 2
Entry 3
Entry 4
Entry 5
Entry 6
Entry 7
The output should be:
Entry 1
Entry 1 > Entry 2
Entry 1 > Entry 2 > Entry 3
Entry 1 > Entry 2 > Entry 4
Entry 1 > Entry 5
Entry 6
Entry 6 > Entry 7
The catch is that the algorithm should have a complexity of O(1), meaning that the runtime, and in our case the number of database queries, should remain constant regardless of how many entries exist in the structure. If, on the other hand, the number of database queries grows linearly and is proportional to the number of entries then your algorithm has a complexity of O(n).
This is called “Big O notation” and can be visualised as follows:
For a more in-depth explanation check out A Simplified Explanation of the Big O Notation by Karuna Sehgal.
If you learn better from stories about carrier pigeons and lawn mowing then you can watch the first few minutes of this fun video.
The algorithm should be written in twig using Craft tags, so using the {% nav %} tag is allowed. It must output a structure’s entries as described above with a complexity of O(1). It should not rely on any plugins and the code will be evaluated based on the following criteria in order of priority:
Therefore the code should be readable and easy to understand. It should be concise and non-repetitive, but not at the expense of readability. It should be performant, but not at the expense of readability or brevity.
You can keep track of how performant your algorithm is by turning on the debug toolbar on the front-end of your site and keeping an eye on the number of database queries required to output the structure. Get a baseline by outputting the structure entries without their ancestors, then see how many extra queries are necessary to output the titles of their ancestors. If the number of database queries increases as you add more entries to the structure then you’re likely working with a O(n) algorithm. If it remains constant then congratulations, you have achieved O(1)!
Solution submitted by Alex Roper on 6 November 2019.
{% set entries = craft.entries.section('nav').all() %}
{% for entry in entries %}
{% set crumb = [] %}
{# Loop thru all entries again, matching items in the nested set model.
Match items where the current entry's left and right domain falls between
the item's left and right domain, including the current entry.
-#}
{% for item in entries if (entry.lft >= item.lft) and (entry.rgt <= item.rgt) %}
{% set crumb = crumb|merge([item.title]) %}
{% endfor %}
{# Output the full breadcrumb with > separators #}
{{ crumb|join(' > ') }}<br>
{% endfor %}
Solution submitted by Prateek Rungta on 6 November 2019.
{% set entries = craft.entries.section('pages').all() %}
{% nav entry in entries %}
{# Build ancestor lists for nested elements
by using previous breadcrumbs #}
{% set ancestors = entry.level > 1
? breadcrumbs[0 : entry.level - 1]
: [] %}
{# Add current entry to ancestors and render titles #}
{% set breadcrumbs = ancestors|merge([entry]) %}
{{ breadcrumbs|column('title')|join(' > ') }}
{# Repeat for all children #}
<br>
{% children %}
{% endnav %}
Solution submitted by Sarah Schütz on 8 November 2019.
{% set entries = craft.entries().section('entry').all() %}
{% macro render(entries) %}
{% nav entry in entries %}
{{ entry.title }}
{% ifchildren %}
> {% children %}
{% endifchildren %}
{% endnav %}
{% endmacro %}
{% set entryStack = [] %}
{% for entry in entries %}
{% set level = entry.level %}
{# remove all entries with a level higher or equal to the current entry #}
{% set entryStack = entryStack | slice(0, level - 1) %}
{# add current entry to stack #}
{% set entryStack = entryStack | merge([entry]) %}
{# render the current entry stack #}
<p>{{ _self.render(entryStack) }}</p>
{% endfor %}
Solution submitted by David Hellmann on 9 November 2019.
{% set entries = craft.entries.section('challange').all() %}
{% set storage = '' %}
{% for entry in entries %}
{% if entry.level == 1 %}
{% set storage = entry.title %}
{{ entry.title }}<br>
{% endif %}
{% if entry.level == 2 %}
{{ storage }} > {{ entry.title }}<br>
{% set storage = storage ~ ' > ' ~ entry.title %}
{% endif %}
{% if entry.level == 3 %}
{{ storage }} > {{ entry.title }}<br>
{% endif %}
{% endfor %}