[Summary view]

   1  <?php
   2  // This file is part of Moodle - http://moodle.org/
   3  //
   4  // Moodle is free software: you can redistribute it and/or modify
   5  // it under the terms of the GNU General Public License as published by
   6  // the Free Software Foundation, either version 3 of the License, or
   7  // (at your option) any later version.
   8  //
   9  // Moodle is distributed in the hope that it will be useful,
  10  // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  // GNU General Public License for more details.
  13  //
  14  // You should have received a copy of the GNU General Public License
  15  // along with Moodle.  If not, see <http://www.gnu.org/licenses/>.
  16  
  17  /**
  18   * Class to sort items.
  19   *
  20   * @package    mod_forum
  21   * @copyright  2019 Ryan Wyllie <ryan@moodle.com>
  22   * @license    http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
  23   */
  24  
  25  namespace mod_forum\local\entities;
  26  
  27  defined('MOODLE_INTERNAL') || die();
  28  
  29  /**
  30   * Class to sort lists of items.
  31   *
  32   * @copyright  2019 Ryan Wyllie <ryan@moodle.com>
  33   * @license    http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
  34   */
  35  class sorter {
  36      /** @var callable $getid Function used to get the id from an item */
  37      private $getid;
  38      /** @var callable $getparentid Function used to get the parent id from an item */
  39      private $getparentid;
  40  
  41      /**
  42       * Constructor.
  43       *
  44       * Allows the calling code to provide 2 functions to get the id and parent id from
  45       * the list of items it is intended to process.
  46       *
  47       * This allows this class to be composed in numerous different ways to support various
  48       * types of items while keeping the underlying sorting algorithm consistent.
  49       *
  50       * @param callable $getid Function used to get the id from an item
  51       * @param callable $getparentid Function used to get the parent id from an item
  52       */
  53      public function __construct(callable $getid, callable $getparentid) {
  54          $this->getid = $getid;
  55          $this->getparentid = $getparentid;
  56      }
  57  
  58      /**
  59       * Sort a list of items into a parent/child data structure. The resulting data structure
  60       * is a recursive array of arrays where the first element is the parent and the second is
  61       * an array of it's children.
  62       *
  63       * For example
  64       * If we have an array of items A, B, C, and D where D is a child of C, B and C are children
  65       * of A.
  66       *
  67       * This function would sort them into the following:
  68       * [
  69       *      [
  70       *          A,
  71       *          [
  72       *              [
  73       *                  B,
  74       *                  []
  75       *              ],
  76       *              [
  77       *                  C,
  78       *                  [
  79       *                      [
  80       *                          D,
  81       *                          []
  82       *                      ]
  83       *                  ]
  84       *              ]
  85       *          ]
  86       *      ]
  87       * ]
  88       *
  89       * @param array $items The list of items to sort.
  90       * @return array
  91       */
  92      public function sort_into_children(array $items) : array {
  93          $ids = array_reduce($items, function($carry, $item) {
  94              $carry[($this->getid)($item)] = true;
  95              return $carry;
  96          }, []);
  97  
  98          // Split out the items into "parents" and "replies" (children). These are unsorted
  99          // at this point.
 100          [$parents, $replies] = array_reduce($items, function($carry, $item) use ($ids) {
 101              $parentid = ($this->getparentid)($item);
 102  
 103              if (!empty($ids[$parentid])) {
 104                  // This is a child to another item in the list so add it to the children list.
 105                  $carry[1][] = $item;
 106              } else {
 107                  // This isn't a child to anything in our list so it's a parent.
 108                  $carry[0][] = $item;
 109              }
 110  
 111              return $carry;
 112          }, [[], []]);
 113  
 114          if (empty($replies)) {
 115              return array_map(function($parent) {
 116                  return [$parent, []];
 117              }, $parents);
 118          }
 119  
 120          // Recurse to sort the replies into the correct nesting.
 121          $sortedreplies = $this->sort_into_children($replies);
 122  
 123          // Sort the parents and sorted replies into their matching pairs.
 124          return array_map(function($parent) use ($sortedreplies) {
 125              $parentid = ($this->getid)($parent);
 126              return [
 127                  $parent,
 128                  array_values(array_filter($sortedreplies, function($replydata) use ($parentid) {
 129                      return ($this->getparentid)($replydata[0]) == $parentid;
 130                  }))
 131              ];
 132          }, $parents);
 133      }
 134  
 135      /**
 136       * Take the data structure returned from "sort_into_children" and flatten it back
 137       * into an array. It does a depth first flatten which maintains the reply ordering.
 138       *
 139       * @param array $items Items in the data structure returned by "sort_into_children"
 140       * @return array A flat array.
 141       */
 142      public function flatten_children(array $items) : array {
 143          $result = [];
 144  
 145          foreach ($items as [$item, $children]) {
 146              $result[] = $item;
 147              $result = array_merge($result, $this->flatten_children($children));
 148          }
 149  
 150          return $result;
 151      }
 152  }