WordPress Walker Paged Threaded

/**
 * Implements threaded awareness for {@see paged_walk()}.
 *
 * @link http://wordpress.stackexchange.com/questions/20506
 * @uses Walker
 */
class Walker_Paged_Threaded extends Walker
{
    /**
     * Get total number of children for an element, recursively working down
     * the tree if neccessary.
     *
     * @param int $ID The element ID
     * @param array $child_elements All children, indexed by parent ID
     * @return int
     */
    function get_total_children( $ID, $child_elements = array() )
    {
        if ( empty( $ID ) || empty( $child_elements[ $ID ] ) )
            return 0;

        $count = count( $child_elements[ $ID ] );
        $id_field = $this->db_fields['id'];

        // iterate over children and recursively call if they themselves have children
        foreach ( $child_elements[ $ID ] as $child ) {
            if ( ! empty( $child_elements[ $child->$id_field ] ) )
                $count = $count + $this->get_total_children( $child->$id_field, $child_elements );
        }

        return $count;
    }

    /**
     * Separate elements into two buckets: top level and children elements.
     *
     * Children elements is a two dimensional array, indexed by parent ID.
     *
     * @param array $elements
     * @return array $top_elements, $child_elements
     */
    function get_top_and_child_elements( $elements )
    {
        $parent_field = $this->db_fields['parent'];

        $top_elements =
        $child_elements = array();

        foreach ( $elements as $e ) {
            if ( 0 == $e->$parent_field )
                $top_elements[] = $e;
            else
                $child_elements[ $e->$parent_field ][] = $e;
        }

        return array( $top_elements, $child_elements );
    }

    /**
     * This does not actually return the total number of root elements!
     *
     * It's a trick so that {@see get_comment_pages_count()} calculates the
     * correct number of pages.
     *
     * Will break if you start passing custom 'per_page' arguments about.
     */
    function get_number_of_root_elements( $elements )
    {
        $per_page = ( int ) get_query_var( 'comments_per_page' );

        if ( 0 === $per_page )
            $per_page = ( int ) get_option( 'comments_per_page' );

        if ( 0 === $per_page )
            $per_page = 1;

        list( $top_elements, $child_elements ) = $this->get_top_and_child_elements( $elements );
        $page_starts = $this->get_element_page_starts( $per_page, $top_elements, $child_elements );

        return count( $page_starts ) * $per_page;
    }

    /**
     * Get the page start indexes for $top_elements.
     *
     * @param array $top_elements
     * @param array $top_elements
     * @return array Page numbers and their starting $top_elements key
     */
    function get_element_page_starts( $per_page, $top_elements, $child_elements )
    {
        $id_field = $this->db_fields['id'];
        $page_starts = array( 1 => 0 );
        $stack_count = 0;

        foreach ( $top_elements as $k => $e ) {

            // add *this* and ALL children to the count stack
            $stack_count = ++$stack_count + $this->get_total_children( $e->$id_field, $child_elements );

            if ( $stack_count < $per_page )
                continue; // keep-a-counting

            // hit maximum for the page, start a new one with next element
            if ( isset( $top_elements[$k + 1] ) )
                $page_starts[] = $k + 1;

            $stack_count = 0; // reset stack
        }

        return $page_starts;
    }

    /**
     * paged_walk() - as {@see Walker_Comment::paged_walk()}, but accounting for
     * threading in pagination.
     *
     * @see Walker_Comment::paged_walk()
     *
     * @param int $max_depth = 0 means display all levels; $max_depth > 0 specifies the number of display levels.
     * @param int $page_num the specific page number, beginning with 1.
     * @return XHTML of the specified page of elements
     */
    function paged_walk( $elements, $max_depth, $page_num, $per_page )
    {
        /* sanity check */
        if ( empty( $elements ) || $max_depth < -1 )
            return '';

        $args = array_slice( func_get_args(), 4 );
        $output = '';

        $id_field = $this->db_fields['id'];
        $parent_field = $this->db_fields['parent'];

        $count = -1;
        if ( -1 == $max_depth )
            $total_top = count( $elements );
        if ( $page_num < 1 || $per_page < 0 ) {
            // No paging
            $paging = false;
            $start = 0;
            if ( -1 == $max_depth )
                $end = $total_top;
            $this->max_pages = 1;
        } else {
            $paging = true;
            $start = ( ( int )$page_num - 1 ) * ( int )$per_page;
            $end = $start + $per_page;
            if ( -1 == $max_depth )
                $this->max_pages = ceil( $total_top / $per_page );
        }

        // flat display
        if ( -1 == $max_depth ) {
            if ( ! empty( $args[0]['reverse_top_level'] ) ) {
                $elements = array_reverse( $elements );
                $oldstart = $start;
                $start = $total_top - $end;
                $end = $total_top - $oldstart;
            }

            $empty_array = array();
            foreach ( $elements as $e ) {
                $count++;
                if ( $count < $start )
                    continue;
                if ( $count >= $end )
                    break;
                $this->display_element( $e, $empty_array, 1, 0, $args, $output );
            }
            return $output;
        }

        list( $top_elements, $child_elements ) = $this->get_top_and_child_elements( $elements );
        $total_top = count( $top_elements );

        // check we actually need paging
        if ( $paging && count( $elements ) > $per_page ) {
            $page_starts = $this->get_element_page_starts( $per_page, $top_elements, $child_elements );
            $this->max_pages = count( $page_starts );

            if ( isset( $page_starts[$page_num] ) ) { // valid page
                $start = $page_starts[$page_num];

                // set end to start key for next page
                if ( isset( $page_starts[$page_num + 1] ) )
                    $end = $page_starts[$page_num + 1];

                // no next page, end is last key + 1
                else
                    $end = $total_top;

            } else { // invalid page number - void indexes
                $start = $total_top;
                $end = $start + $per_page;
            }

        // no paging
        } else {
            $start = 0;
            $end = $total_top;
        }

        if ( ! empty( $args[0]['reverse_top_level'] ) )
            $top_elements = array_reverse( $top_elements );

        if ( ! empty( $args[0]['reverse_children'] ) ) {
            foreach ( $child_elements as $parent => $children )
                $child_elements[$parent] = array_reverse( $children );
        }

        foreach ( $top_elements as $k => $e ) {
            //for the last page, need to unset earlier children in order to keep track of orphans
            if ( $end >= $total_top && $k < $start )
                $this->unset_children( $e, $child_elements );

            if ( $k < $start )
                continue;

            if ( $k >= $end )
                break;

            $this->display_element( $e, $child_elements, $max_depth, 0, $args, $output );
        }

        if ( $end >= $total_top && count( $child_elements ) > 0 ) {
            $empty_array = array();
            foreach ( $child_elements as $orphans )
                foreach ( $orphans as $op )
                    $this->display_element( $op, $empty_array, 1, 0, $args, $output );
        }

        return $output;
    }
}