module Jekyll
  module MenuFilter
    def menu(input, displayurl)
      def create_menu(pages, base, displayurl)
        # URLs in `base`, `displayurl`, `cururl` are normalized to remove trailing slashes. This is to be able to distinguish the root of a folder from its children by the number of slashes in the URL.
        # We need this to treat the root of a folder as a direct child of the parent folder, whereas pages within a subfolder are of course grandchildren.
        result = Array.new
        for page in pages
          cururl = page['url'].chomp('/')
          # Test if this page is a non-hidden *direct* child of `base`
          if cururl.start_with?(base) and cururl.count('/') == base.count('/') and (not page['hide'])
            # figure out CSS class
            if cururl == displayurl
              css_class = 'current'
            elsif cururl.start_with?(displayurl)
              css_class = 'child'
            elsif displayurl.start_with?(cururl)
              css_class = 'parent'
            else
              css_class = 'sibling'
            end
            # create menu node
            menu_node = { 'url' => page['url'], 'title' => page['slug'] ? page['slug'] : (page['title'] ? page['title'] : page['url']), 'class' => css_class, 'sort' => page['sort'] ? page['sort'] : 0 }
            # potentially recurse
            if (css_class == 'parent' or css_class == 'current')
              sub_nodes = create_menu(pages, cururl + "/", displayurl)
              if sub_nodes.size > 0
                menu_node['sub'] = sub_nodes
              end
              if css_class == 'parent' and sub_nodes.all? { |page| page['class'] == 'sibling' }
                # we won't get closer to this URL, it doesn't exist in our page list
                menu_node['class'] = 'current'
                sub_nodes.each { |page| page['class'] = 'child' }
              end
            end
            # remember the root
            if base == ""
              menu_node['class'] += ' root'
            end
            # store menu node
            result.push(menu_node)
          else
            #print "Not adding: cur=", cururl, ", base=", base, ", hide=", page['hide'], "\n"
          end
        end
        # sort the result before returning it
        result.sort_by { |page| [page['sort'], page['url']] }
      end
      
      create_menu(input, "", displayurl.chomp('/'))
    end
  end
end

Liquid::Template.register_filter(Jekyll::MenuFilter)