Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
67.39% covered (warning)
67.39%
31 / 46
25.00% covered (danger)
25.00%
1 / 4
CRAP
0.00% covered (danger)
0.00%
0 / 1
TeamDraftInterleaver
67.39% covered (warning)
67.39%
31 / 46
25.00% covered (danger)
25.00%
1 / 4
20.80
0.00% covered (danger)
0.00%
0 / 1
 __construct
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 1
2
 interleave
0.00% covered (danger)
0.00%
0 / 10
0.00% covered (danger)
0.00%
0 / 1
2
 extractResults
0.00% covered (danger)
0.00%
0 / 4
0.00% covered (danger)
0.00%
0 / 1
6
 interleaveResults
100.00% covered (success)
100.00%
31 / 31
100.00% covered (success)
100.00%
1 / 1
10
1<?php
2
3namespace CirrusSearch\Search;
4
5use CirrusSearch\Util;
6
7/**
8 * Implementation of algorithm 2, Team-Draft Interleaving, from F. Radlinski, M.
9 * Kurup, and T. Joachims. How does clickthrough data reflect retrieval
10 * quality? In Proc 17th Intl. Conf. on Information and Knowledge Management.
11 * ACM New York, NY, USA, 2008.
12 */
13class TeamDraftInterleaver {
14    /** @var string The query provided by the user. */
15    private $searchTerm;
16
17    /**
18     * @param string $searchTerm The query provided by the user.
19     */
20    public function __construct( $searchTerm ) {
21        $this->searchTerm = $searchTerm;
22    }
23
24    /**
25     * @param CirrusSearchResultSet $a Results for team A
26     * @param CirrusSearchResultSet $b Results for team B
27     * @param int $limit Maximum number of results to return
28     * @return CirrusSearchResultSet
29     */
30    public function interleave( CirrusSearchResultSet $a, CirrusSearchResultSet $b, $limit ): CirrusSearchResultSet {
31        // Seed the randomness so an individual user the clicks a result and then
32        // comes back to the search page sees the same interleaving. This is not
33        // strictly necessary for the test, but provides the user a more consistent
34        // experience.
35        $seed = hexdec( substr( Util::generateIdentToken( $this->searchTerm ), 0, 8 ) );
36        mt_srand( $seed );
37
38        $aResults = $this->extractResults( $a );
39        $bResults = $this->extractResults( $b );
40        list( $interleaved, $teamA, $teamB, $aOffset ) = $this->interleaveResults(
41            $aResults,
42            $bResults,
43            $limit
44        );
45
46        return new InterleavedResultSet( $a, $interleaved, $teamA, $teamB, $aOffset );
47    }
48
49    private function extractResults( CirrusSearchResultSet $resultSet ) {
50        $extracted = [];
51        /** @var $result CirrusSearchResult */
52        foreach ( $resultSet as $result ) {
53            $extracted[$result->getDocId()] = $result;
54        }
55        return $extracted;
56    }
57
58    /**
59     * Interleave two arrays using team draft interleaving. Only public
60     * for unit tests. The id's used as keys in $a and $b must represent
61     * the same thing, to prevent duplicates in the returned results.
62     *
63     * @param mixed[] $a Map from id to anything in preferred order for team A
64     * @param mixed[] $b Map from id to anything in preferred order for team B
65     * @param int $limit Maximum number of results to interleave
66     * @return mixed[] Four item array. first item being the values from $a
67     *  and $b in the interleaved ordering, second the ids belonging to team
68     *  A, third the ids belonging to team B, and finally the offset for the
69     *  next page in $a.
70     */
71    public static function interleaveResults( $a, $b, $limit ) {
72        $interleaved = [];
73        $teamA = [];
74        $teamB = [];
75        $aIds = array_combine( array_keys( $a ), array_keys( $a ) );
76        $bIds = array_combine( array_keys( $b ), array_keys( $b ) );
77        while (
78            count( $interleaved ) < $limit
79            && ( $aIds || $bIds )
80        ) {
81            if ( !$aIds ) {
82                $id = reset( $bIds );
83                $teamB[] = $id;
84                $interleaved[] = $b[$id];
85            } elseif ( !$bIds ) {
86                $id = reset( $aIds );
87                $teamA[] = $id;
88                $interleaved[] = $a[$id];
89            // If team b has already chosen, then a needs to go
90            } elseif ( count( $teamA ) < count( $teamB )
91                || (
92                // If the counts are equal choose randomly which team goes next
93                    count( $teamA ) == count( $teamB )
94                    && mt_rand( 0, 1 ) === 1
95            ) ) {
96                $id = reset( $aIds );
97                $teamA[] = $id;
98                $interleaved[] = $a[$id];
99            } else {
100                $id = reset( $bIds );
101                $teamB[] = $id;
102                $interleaved[] = $b[$id];
103            }
104            unset( $aIds[$id], $bIds[$id] );
105        }
106
107        if ( $aIds ) {
108            // $offset needs to be set such that results starting at $offset +
109            // $limit are new. As such if we have 20 items and 10 of a are
110            // used, then offset should be -10. If 15 are used we want -5.
111            // This doesn't guarantee we don't show duplicates. Items from B
112            // could be in second page of A. The goal here is to ensure
113            // everything from A is seen when paginating even if there are
114            // dupes.
115            $nextA = reset( $aIds );
116            $nextAIdx = array_search( $nextA, array_keys( $a ) );
117            $offset = -( $limit - $nextAIdx );
118        } else {
119            $offset = 0;
120        }
121
122        return [ $interleaved, $teamA, $teamB, $offset ];
123    }
124}