diff options
Diffstat (limited to 'rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq')
2 files changed, 4074 insertions, 0 deletions
diff --git a/rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq/index.rs.html b/rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq/index.rs.html new file mode 100644 index 0000000..9f59f7f --- /dev/null +++ b/rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq/index.rs.html @@ -0,0 +1,1359 @@ +<!DOCTYPE html><html lang="en"><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="generator" content="rustdoc"><meta name="description" content="Source of the Rust file `/home/pico/.local/share/cargo/registry/src/github.com-1ecc6299db9ec823/rand-0.8.5/src/seq/index.rs`."><meta name="keywords" content="rust, rustlang, rust-lang"><title>index.rs - source</title><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceSerif4-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../FiraSans-Regular.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../FiraSans-Medium.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceCodePro-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceSerif4-Bold.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceCodePro-Semibold.ttf.woff2"><link rel="stylesheet" href="../../../normalize.css"><link rel="stylesheet" href="../../../rustdoc.css" id="mainThemeStyle"><link rel="stylesheet" href="../../../ayu.css" disabled><link rel="stylesheet" href="../../../dark.css" disabled><link rel="stylesheet" href="../../../light.css" id="themeStyle"><script id="default-settings" ></script><script src="../../../storage.js"></script><script defer src="../../../source-script.js"></script><script defer src="../../../source-files.js"></script><script defer src="../../../main.js"></script><noscript><link rel="stylesheet" href="../../../noscript.css"></noscript><link rel="icon" href="https://www.rust-lang.org/favicon.ico"></head><body class="rustdoc source"><!--[if lte IE 11]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><nav class="sidebar"></nav><main><div class="width-limiter"><nav class="sub"><a class="sub-logo-container" href="../../../rand/index.html"> + <img src="https://www.rust-lang.org/logos/rust-logo-128x128-blk.png" alt="logo"></a><form class="search-form"><span></span><input class="search-input" name="search" autocomplete="off" spellcheck="false" placeholder="Click or press ‘S’ to search, ‘?’ for more options…" type="search"><div id="help-button" title="help" tabindex="-1"><a href="../../../help.html">?</a></div><div id="settings-menu" tabindex="-1"><a href="../../../settings.html" title="settings"><img width="22" height="22" alt="Change settings" src="../../../wheel.svg"></a></div></form></nav><section id="main-content" class="content"><div class="example-wrap"><pre class="src-line-numbers"><span id="1">1</span> +<span id="2">2</span> +<span id="3">3</span> +<span id="4">4</span> +<span id="5">5</span> +<span id="6">6</span> +<span id="7">7</span> +<span id="8">8</span> +<span id="9">9</span> +<span id="10">10</span> +<span id="11">11</span> +<span id="12">12</span> +<span id="13">13</span> +<span id="14">14</span> +<span id="15">15</span> +<span id="16">16</span> +<span id="17">17</span> +<span id="18">18</span> +<span id="19">19</span> +<span id="20">20</span> +<span id="21">21</span> +<span id="22">22</span> +<span id="23">23</span> +<span id="24">24</span> +<span id="25">25</span> +<span id="26">26</span> +<span id="27">27</span> +<span id="28">28</span> +<span id="29">29</span> +<span id="30">30</span> +<span id="31">31</span> +<span id="32">32</span> +<span id="33">33</span> +<span id="34">34</span> +<span id="35">35</span> +<span id="36">36</span> +<span id="37">37</span> +<span id="38">38</span> +<span id="39">39</span> +<span id="40">40</span> +<span id="41">41</span> +<span id="42">42</span> +<span id="43">43</span> +<span id="44">44</span> +<span id="45">45</span> +<span id="46">46</span> +<span id="47">47</span> +<span id="48">48</span> +<span id="49">49</span> +<span id="50">50</span> +<span id="51">51</span> +<span id="52">52</span> +<span id="53">53</span> +<span id="54">54</span> +<span id="55">55</span> +<span id="56">56</span> +<span id="57">57</span> +<span id="58">58</span> +<span id="59">59</span> +<span id="60">60</span> +<span id="61">61</span> +<span id="62">62</span> +<span id="63">63</span> +<span id="64">64</span> +<span id="65">65</span> +<span id="66">66</span> +<span id="67">67</span> +<span id="68">68</span> +<span id="69">69</span> +<span id="70">70</span> +<span id="71">71</span> +<span id="72">72</span> +<span id="73">73</span> +<span id="74">74</span> +<span id="75">75</span> +<span id="76">76</span> +<span id="77">77</span> +<span id="78">78</span> +<span id="79">79</span> +<span id="80">80</span> +<span id="81">81</span> +<span id="82">82</span> +<span id="83">83</span> +<span id="84">84</span> +<span id="85">85</span> +<span id="86">86</span> +<span id="87">87</span> +<span id="88">88</span> +<span id="89">89</span> +<span id="90">90</span> +<span id="91">91</span> +<span id="92">92</span> +<span id="93">93</span> +<span id="94">94</span> +<span id="95">95</span> +<span id="96">96</span> +<span id="97">97</span> +<span id="98">98</span> +<span id="99">99</span> +<span id="100">100</span> +<span id="101">101</span> +<span id="102">102</span> +<span id="103">103</span> +<span id="104">104</span> +<span id="105">105</span> +<span id="106">106</span> +<span id="107">107</span> +<span id="108">108</span> +<span id="109">109</span> +<span id="110">110</span> +<span id="111">111</span> +<span id="112">112</span> +<span id="113">113</span> +<span id="114">114</span> +<span id="115">115</span> +<span id="116">116</span> +<span id="117">117</span> +<span id="118">118</span> +<span id="119">119</span> +<span id="120">120</span> +<span id="121">121</span> +<span id="122">122</span> +<span id="123">123</span> +<span id="124">124</span> +<span id="125">125</span> +<span id="126">126</span> +<span id="127">127</span> +<span id="128">128</span> +<span id="129">129</span> +<span id="130">130</span> +<span id="131">131</span> +<span id="132">132</span> +<span id="133">133</span> +<span id="134">134</span> +<span id="135">135</span> +<span id="136">136</span> +<span id="137">137</span> +<span id="138">138</span> +<span id="139">139</span> +<span id="140">140</span> +<span id="141">141</span> +<span id="142">142</span> +<span id="143">143</span> +<span id="144">144</span> +<span id="145">145</span> +<span id="146">146</span> +<span id="147">147</span> +<span id="148">148</span> +<span id="149">149</span> +<span id="150">150</span> +<span id="151">151</span> +<span id="152">152</span> +<span id="153">153</span> +<span id="154">154</span> +<span id="155">155</span> +<span id="156">156</span> +<span id="157">157</span> +<span id="158">158</span> +<span id="159">159</span> +<span id="160">160</span> +<span id="161">161</span> +<span id="162">162</span> +<span id="163">163</span> +<span id="164">164</span> +<span id="165">165</span> +<span id="166">166</span> +<span id="167">167</span> +<span id="168">168</span> +<span id="169">169</span> +<span id="170">170</span> +<span id="171">171</span> +<span id="172">172</span> +<span id="173">173</span> +<span id="174">174</span> +<span id="175">175</span> +<span id="176">176</span> +<span id="177">177</span> +<span id="178">178</span> +<span id="179">179</span> +<span id="180">180</span> +<span id="181">181</span> +<span id="182">182</span> +<span id="183">183</span> +<span id="184">184</span> +<span id="185">185</span> +<span id="186">186</span> +<span id="187">187</span> +<span id="188">188</span> +<span id="189">189</span> +<span id="190">190</span> +<span id="191">191</span> +<span id="192">192</span> +<span id="193">193</span> +<span id="194">194</span> +<span id="195">195</span> +<span id="196">196</span> +<span id="197">197</span> +<span id="198">198</span> +<span id="199">199</span> +<span id="200">200</span> +<span id="201">201</span> +<span id="202">202</span> +<span id="203">203</span> +<span id="204">204</span> +<span id="205">205</span> +<span id="206">206</span> +<span id="207">207</span> +<span id="208">208</span> +<span id="209">209</span> +<span id="210">210</span> +<span id="211">211</span> +<span id="212">212</span> +<span id="213">213</span> +<span id="214">214</span> +<span id="215">215</span> +<span id="216">216</span> +<span id="217">217</span> +<span id="218">218</span> +<span id="219">219</span> +<span id="220">220</span> +<span id="221">221</span> +<span id="222">222</span> +<span id="223">223</span> +<span id="224">224</span> +<span id="225">225</span> +<span id="226">226</span> +<span id="227">227</span> +<span id="228">228</span> +<span id="229">229</span> +<span id="230">230</span> +<span id="231">231</span> +<span id="232">232</span> +<span id="233">233</span> +<span id="234">234</span> +<span id="235">235</span> +<span id="236">236</span> +<span id="237">237</span> +<span id="238">238</span> +<span id="239">239</span> +<span id="240">240</span> +<span id="241">241</span> +<span id="242">242</span> +<span id="243">243</span> +<span id="244">244</span> +<span id="245">245</span> +<span id="246">246</span> +<span id="247">247</span> +<span id="248">248</span> +<span id="249">249</span> +<span id="250">250</span> +<span id="251">251</span> +<span id="252">252</span> +<span id="253">253</span> +<span id="254">254</span> +<span id="255">255</span> +<span id="256">256</span> +<span id="257">257</span> +<span id="258">258</span> +<span id="259">259</span> +<span id="260">260</span> +<span id="261">261</span> +<span id="262">262</span> +<span id="263">263</span> +<span id="264">264</span> +<span id="265">265</span> +<span id="266">266</span> +<span id="267">267</span> +<span id="268">268</span> +<span id="269">269</span> +<span id="270">270</span> +<span id="271">271</span> +<span id="272">272</span> +<span id="273">273</span> +<span id="274">274</span> +<span id="275">275</span> +<span id="276">276</span> +<span id="277">277</span> +<span id="278">278</span> +<span id="279">279</span> +<span id="280">280</span> +<span id="281">281</span> +<span id="282">282</span> +<span id="283">283</span> +<span id="284">284</span> +<span id="285">285</span> +<span id="286">286</span> +<span id="287">287</span> +<span id="288">288</span> +<span id="289">289</span> +<span id="290">290</span> +<span id="291">291</span> +<span id="292">292</span> +<span id="293">293</span> +<span id="294">294</span> +<span id="295">295</span> +<span id="296">296</span> +<span id="297">297</span> +<span id="298">298</span> +<span id="299">299</span> +<span id="300">300</span> +<span id="301">301</span> +<span id="302">302</span> +<span id="303">303</span> +<span id="304">304</span> +<span id="305">305</span> +<span id="306">306</span> +<span id="307">307</span> +<span id="308">308</span> +<span id="309">309</span> +<span id="310">310</span> +<span id="311">311</span> +<span id="312">312</span> +<span id="313">313</span> +<span id="314">314</span> +<span id="315">315</span> +<span id="316">316</span> +<span id="317">317</span> +<span id="318">318</span> +<span id="319">319</span> +<span id="320">320</span> +<span id="321">321</span> +<span id="322">322</span> +<span id="323">323</span> +<span id="324">324</span> +<span id="325">325</span> +<span id="326">326</span> +<span id="327">327</span> +<span id="328">328</span> +<span id="329">329</span> +<span id="330">330</span> +<span id="331">331</span> +<span id="332">332</span> +<span id="333">333</span> +<span id="334">334</span> +<span id="335">335</span> +<span id="336">336</span> +<span id="337">337</span> +<span id="338">338</span> +<span id="339">339</span> +<span id="340">340</span> +<span id="341">341</span> +<span id="342">342</span> +<span id="343">343</span> +<span id="344">344</span> +<span id="345">345</span> +<span id="346">346</span> +<span id="347">347</span> +<span id="348">348</span> +<span id="349">349</span> +<span id="350">350</span> +<span id="351">351</span> +<span id="352">352</span> +<span id="353">353</span> +<span id="354">354</span> +<span id="355">355</span> +<span id="356">356</span> +<span id="357">357</span> +<span id="358">358</span> +<span id="359">359</span> +<span id="360">360</span> +<span id="361">361</span> +<span id="362">362</span> +<span id="363">363</span> +<span id="364">364</span> +<span id="365">365</span> +<span id="366">366</span> +<span id="367">367</span> +<span id="368">368</span> +<span id="369">369</span> +<span id="370">370</span> +<span id="371">371</span> +<span id="372">372</span> +<span id="373">373</span> +<span id="374">374</span> +<span id="375">375</span> +<span id="376">376</span> +<span id="377">377</span> +<span id="378">378</span> +<span id="379">379</span> +<span id="380">380</span> +<span id="381">381</span> +<span id="382">382</span> +<span id="383">383</span> +<span id="384">384</span> +<span id="385">385</span> +<span id="386">386</span> +<span id="387">387</span> +<span id="388">388</span> +<span id="389">389</span> +<span id="390">390</span> +<span id="391">391</span> +<span id="392">392</span> +<span id="393">393</span> +<span id="394">394</span> +<span id="395">395</span> +<span id="396">396</span> +<span id="397">397</span> +<span id="398">398</span> +<span id="399">399</span> +<span id="400">400</span> +<span id="401">401</span> +<span id="402">402</span> +<span id="403">403</span> +<span id="404">404</span> +<span id="405">405</span> +<span id="406">406</span> +<span id="407">407</span> +<span id="408">408</span> +<span id="409">409</span> +<span id="410">410</span> +<span id="411">411</span> +<span id="412">412</span> +<span id="413">413</span> +<span id="414">414</span> +<span id="415">415</span> +<span id="416">416</span> +<span id="417">417</span> +<span id="418">418</span> +<span id="419">419</span> +<span id="420">420</span> +<span id="421">421</span> +<span id="422">422</span> +<span id="423">423</span> +<span id="424">424</span> +<span id="425">425</span> +<span id="426">426</span> +<span id="427">427</span> +<span id="428">428</span> +<span id="429">429</span> +<span id="430">430</span> +<span id="431">431</span> +<span id="432">432</span> +<span id="433">433</span> +<span id="434">434</span> +<span id="435">435</span> +<span id="436">436</span> +<span id="437">437</span> +<span id="438">438</span> +<span id="439">439</span> +<span id="440">440</span> +<span id="441">441</span> +<span id="442">442</span> +<span id="443">443</span> +<span id="444">444</span> +<span id="445">445</span> +<span id="446">446</span> +<span id="447">447</span> +<span id="448">448</span> +<span id="449">449</span> +<span id="450">450</span> +<span id="451">451</span> +<span id="452">452</span> +<span id="453">453</span> +<span id="454">454</span> +<span id="455">455</span> +<span id="456">456</span> +<span id="457">457</span> +<span id="458">458</span> +<span id="459">459</span> +<span id="460">460</span> +<span id="461">461</span> +<span id="462">462</span> +<span id="463">463</span> +<span id="464">464</span> +<span id="465">465</span> +<span id="466">466</span> +<span id="467">467</span> +<span id="468">468</span> +<span id="469">469</span> +<span id="470">470</span> +<span id="471">471</span> +<span id="472">472</span> +<span id="473">473</span> +<span id="474">474</span> +<span id="475">475</span> +<span id="476">476</span> +<span id="477">477</span> +<span id="478">478</span> +<span id="479">479</span> +<span id="480">480</span> +<span id="481">481</span> +<span id="482">482</span> +<span id="483">483</span> +<span id="484">484</span> +<span id="485">485</span> +<span id="486">486</span> +<span id="487">487</span> +<span id="488">488</span> +<span id="489">489</span> +<span id="490">490</span> +<span id="491">491</span> +<span id="492">492</span> +<span id="493">493</span> +<span id="494">494</span> +<span id="495">495</span> +<span id="496">496</span> +<span id="497">497</span> +<span id="498">498</span> +<span id="499">499</span> +<span id="500">500</span> +<span id="501">501</span> +<span id="502">502</span> +<span id="503">503</span> +<span id="504">504</span> +<span id="505">505</span> +<span id="506">506</span> +<span id="507">507</span> +<span id="508">508</span> +<span id="509">509</span> +<span id="510">510</span> +<span id="511">511</span> +<span id="512">512</span> +<span id="513">513</span> +<span id="514">514</span> +<span id="515">515</span> +<span id="516">516</span> +<span id="517">517</span> +<span id="518">518</span> +<span id="519">519</span> +<span id="520">520</span> +<span id="521">521</span> +<span id="522">522</span> +<span id="523">523</span> +<span id="524">524</span> +<span id="525">525</span> +<span id="526">526</span> +<span id="527">527</span> +<span id="528">528</span> +<span id="529">529</span> +<span id="530">530</span> +<span id="531">531</span> +<span id="532">532</span> +<span id="533">533</span> +<span id="534">534</span> +<span id="535">535</span> +<span id="536">536</span> +<span id="537">537</span> +<span id="538">538</span> +<span id="539">539</span> +<span id="540">540</span> +<span id="541">541</span> +<span id="542">542</span> +<span id="543">543</span> +<span id="544">544</span> +<span id="545">545</span> +<span id="546">546</span> +<span id="547">547</span> +<span id="548">548</span> +<span id="549">549</span> +<span id="550">550</span> +<span id="551">551</span> +<span id="552">552</span> +<span id="553">553</span> +<span id="554">554</span> +<span id="555">555</span> +<span id="556">556</span> +<span id="557">557</span> +<span id="558">558</span> +<span id="559">559</span> +<span id="560">560</span> +<span id="561">561</span> +<span id="562">562</span> +<span id="563">563</span> +<span id="564">564</span> +<span id="565">565</span> +<span id="566">566</span> +<span id="567">567</span> +<span id="568">568</span> +<span id="569">569</span> +<span id="570">570</span> +<span id="571">571</span> +<span id="572">572</span> +<span id="573">573</span> +<span id="574">574</span> +<span id="575">575</span> +<span id="576">576</span> +<span id="577">577</span> +<span id="578">578</span> +<span id="579">579</span> +<span id="580">580</span> +<span id="581">581</span> +<span id="582">582</span> +<span id="583">583</span> +<span id="584">584</span> +<span id="585">585</span> +<span id="586">586</span> +<span id="587">587</span> +<span id="588">588</span> +<span id="589">589</span> +<span id="590">590</span> +<span id="591">591</span> +<span id="592">592</span> +<span id="593">593</span> +<span id="594">594</span> +<span id="595">595</span> +<span id="596">596</span> +<span id="597">597</span> +<span id="598">598</span> +<span id="599">599</span> +<span id="600">600</span> +<span id="601">601</span> +<span id="602">602</span> +<span id="603">603</span> +<span id="604">604</span> +<span id="605">605</span> +<span id="606">606</span> +<span id="607">607</span> +<span id="608">608</span> +<span id="609">609</span> +<span id="610">610</span> +<span id="611">611</span> +<span id="612">612</span> +<span id="613">613</span> +<span id="614">614</span> +<span id="615">615</span> +<span id="616">616</span> +<span id="617">617</span> +<span id="618">618</span> +<span id="619">619</span> +<span id="620">620</span> +<span id="621">621</span> +<span id="622">622</span> +<span id="623">623</span> +<span id="624">624</span> +<span id="625">625</span> +<span id="626">626</span> +<span id="627">627</span> +<span id="628">628</span> +<span id="629">629</span> +<span id="630">630</span> +<span id="631">631</span> +<span id="632">632</span> +<span id="633">633</span> +<span id="634">634</span> +<span id="635">635</span> +<span id="636">636</span> +<span id="637">637</span> +<span id="638">638</span> +<span id="639">639</span> +<span id="640">640</span> +<span id="641">641</span> +<span id="642">642</span> +<span id="643">643</span> +<span id="644">644</span> +<span id="645">645</span> +<span id="646">646</span> +<span id="647">647</span> +<span id="648">648</span> +<span id="649">649</span> +<span id="650">650</span> +<span id="651">651</span> +<span id="652">652</span> +<span id="653">653</span> +<span id="654">654</span> +<span id="655">655</span> +<span id="656">656</span> +<span id="657">657</span> +<span id="658">658</span> +<span id="659">659</span> +<span id="660">660</span> +<span id="661">661</span> +<span id="662">662</span> +<span id="663">663</span> +<span id="664">664</span> +<span id="665">665</span> +<span id="666">666</span> +<span id="667">667</span> +<span id="668">668</span> +<span id="669">669</span> +<span id="670">670</span> +<span id="671">671</span> +<span id="672">672</span> +<span id="673">673</span> +<span id="674">674</span> +<span id="675">675</span> +<span id="676">676</span> +<span id="677">677</span> +<span id="678">678</span> +</pre><pre class="rust"><code><span class="comment">// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +</span><span class="doccomment">//! Low-level API for sampling indices + +</span><span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] </span><span class="kw">use </span>core::slice; + +<span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] </span><span class="kw">use </span>alloc::vec::{<span class="self">self</span>, Vec}; +<span class="comment">// BTreeMap is not as fast in tests, but better than nothing. +</span><span class="attribute">#[cfg(all(feature = <span class="string">"alloc"</span>, not(feature = <span class="string">"std"</span>)))] +</span><span class="kw">use </span>alloc::collections::BTreeSet; +<span class="attribute">#[cfg(feature = <span class="string">"std"</span>)] </span><span class="kw">use </span>std::collections::HashSet; + +<span class="attribute">#[cfg(feature = <span class="string">"std"</span>)] +</span><span class="kw">use </span><span class="kw">crate</span>::distributions::WeightedError; + +<span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] +</span><span class="kw">use crate</span>::{Rng, distributions::{uniform::SampleUniform, Distribution, Uniform}}; + +<span class="attribute">#[cfg(feature = <span class="string">"serde1"</span>)] +</span><span class="kw">use </span>serde::{Serialize, Deserialize}; + +<span class="doccomment">/// A vector of indices. +/// +/// Multiple internal representations are possible. +</span><span class="attribute">#[derive(Clone, Debug)] +#[cfg_attr(feature = <span class="string">"serde1"</span>, derive(Serialize, Deserialize))] +</span><span class="kw">pub enum </span>IndexVec { + <span class="attribute">#[doc(hidden)] + </span>U32(Vec<u32>), + <span class="attribute">#[doc(hidden)] + </span>USize(Vec<usize>), +} + +<span class="kw">impl </span>IndexVec { + <span class="doccomment">/// Returns the number of indices + </span><span class="attribute">#[inline] + </span><span class="kw">pub fn </span>len(<span class="kw-2">&</span><span class="self">self</span>) -> usize { + <span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{ + IndexVec::U32(<span class="kw-2">ref </span>v) => v.len(), + IndexVec::USize(<span class="kw-2">ref </span>v) => v.len(), + } + } + + <span class="doccomment">/// Returns `true` if the length is 0. + </span><span class="attribute">#[inline] + </span><span class="kw">pub fn </span>is_empty(<span class="kw-2">&</span><span class="self">self</span>) -> bool { + <span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{ + IndexVec::U32(<span class="kw-2">ref </span>v) => v.is_empty(), + IndexVec::USize(<span class="kw-2">ref </span>v) => v.is_empty(), + } + } + + <span class="doccomment">/// Return the value at the given `index`. + /// + /// (Note: we cannot implement [`std::ops::Index`] because of lifetime + /// restrictions.) + </span><span class="attribute">#[inline] + </span><span class="kw">pub fn </span>index(<span class="kw-2">&</span><span class="self">self</span>, index: usize) -> usize { + <span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{ + IndexVec::U32(<span class="kw-2">ref </span>v) => v[index] <span class="kw">as </span>usize, + IndexVec::USize(<span class="kw-2">ref </span>v) => v[index], + } + } + + <span class="doccomment">/// Return result as a `Vec<usize>`. Conversion may or may not be trivial. + </span><span class="attribute">#[inline] + </span><span class="kw">pub fn </span>into_vec(<span class="self">self</span>) -> Vec<usize> { + <span class="kw">match </span><span class="self">self </span>{ + IndexVec::U32(v) => v.into_iter().map(|i| i <span class="kw">as </span>usize).collect(), + IndexVec::USize(v) => v, + } + } + + <span class="doccomment">/// Iterate over the indices as a sequence of `usize` values + </span><span class="attribute">#[inline] + </span><span class="kw">pub fn </span>iter(<span class="kw-2">&</span><span class="self">self</span>) -> IndexVecIter<<span class="lifetime">'_</span>> { + <span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{ + IndexVec::U32(<span class="kw-2">ref </span>v) => IndexVecIter::U32(v.iter()), + IndexVec::USize(<span class="kw-2">ref </span>v) => IndexVecIter::USize(v.iter()), + } + } +} + +<span class="kw">impl </span>IntoIterator <span class="kw">for </span>IndexVec { + <span class="kw">type </span>Item = usize; + <span class="kw">type </span>IntoIter = IndexVecIntoIter; + + <span class="doccomment">/// Convert into an iterator over the indices as a sequence of `usize` values + </span><span class="attribute">#[inline] + </span><span class="kw">fn </span>into_iter(<span class="self">self</span>) -> IndexVecIntoIter { + <span class="kw">match </span><span class="self">self </span>{ + IndexVec::U32(v) => IndexVecIntoIter::U32(v.into_iter()), + IndexVec::USize(v) => IndexVecIntoIter::USize(v.into_iter()), + } + } +} + +<span class="kw">impl </span>PartialEq <span class="kw">for </span>IndexVec { + <span class="kw">fn </span>eq(<span class="kw-2">&</span><span class="self">self</span>, other: <span class="kw-2">&</span>IndexVec) -> bool { + <span class="kw">use </span><span class="self">self</span>::IndexVec::<span class="kw-2">*</span>; + <span class="kw">match </span>(<span class="self">self</span>, other) { + (<span class="kw-2">&</span>U32(<span class="kw-2">ref </span>v1), <span class="kw-2">&</span>U32(<span class="kw-2">ref </span>v2)) => v1 == v2, + (<span class="kw-2">&</span>USize(<span class="kw-2">ref </span>v1), <span class="kw-2">&</span>USize(<span class="kw-2">ref </span>v2)) => v1 == v2, + (<span class="kw-2">&</span>U32(<span class="kw-2">ref </span>v1), <span class="kw-2">&</span>USize(<span class="kw-2">ref </span>v2)) => { + (v1.len() == v2.len()) && (v1.iter().zip(v2.iter()).all(|(x, y)| <span class="kw-2">*</span>x <span class="kw">as </span>usize == <span class="kw-2">*</span>y)) + } + (<span class="kw-2">&</span>USize(<span class="kw-2">ref </span>v1), <span class="kw-2">&</span>U32(<span class="kw-2">ref </span>v2)) => { + (v1.len() == v2.len()) && (v1.iter().zip(v2.iter()).all(|(x, y)| <span class="kw-2">*</span>x == <span class="kw-2">*</span>y <span class="kw">as </span>usize)) + } + } + } +} + +<span class="kw">impl </span>From<Vec<u32>> <span class="kw">for </span>IndexVec { + <span class="attribute">#[inline] + </span><span class="kw">fn </span>from(v: Vec<u32>) -> <span class="self">Self </span>{ + IndexVec::U32(v) + } +} + +<span class="kw">impl </span>From<Vec<usize>> <span class="kw">for </span>IndexVec { + <span class="attribute">#[inline] + </span><span class="kw">fn </span>from(v: Vec<usize>) -> <span class="self">Self </span>{ + IndexVec::USize(v) + } +} + +<span class="doccomment">/// Return type of `IndexVec::iter`. +</span><span class="attribute">#[derive(Debug)] +</span><span class="kw">pub enum </span>IndexVecIter<<span class="lifetime">'a</span>> { + <span class="attribute">#[doc(hidden)] + </span>U32(slice::Iter<<span class="lifetime">'a</span>, u32>), + <span class="attribute">#[doc(hidden)] + </span>USize(slice::Iter<<span class="lifetime">'a</span>, usize>), +} + +<span class="kw">impl</span><<span class="lifetime">'a</span>> Iterator <span class="kw">for </span>IndexVecIter<<span class="lifetime">'a</span>> { + <span class="kw">type </span>Item = usize; + + <span class="attribute">#[inline] + </span><span class="kw">fn </span>next(<span class="kw-2">&mut </span><span class="self">self</span>) -> <span class="prelude-ty">Option</span><usize> { + <span class="kw">use </span><span class="self">self</span>::IndexVecIter::<span class="kw-2">*</span>; + <span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{ + U32(<span class="kw-2">ref mut </span>iter) => iter.next().map(|i| <span class="kw-2">*</span>i <span class="kw">as </span>usize), + USize(<span class="kw-2">ref mut </span>iter) => iter.next().cloned(), + } + } + + <span class="attribute">#[inline] + </span><span class="kw">fn </span>size_hint(<span class="kw-2">&</span><span class="self">self</span>) -> (usize, <span class="prelude-ty">Option</span><usize>) { + <span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{ + IndexVecIter::U32(<span class="kw-2">ref </span>v) => v.size_hint(), + IndexVecIter::USize(<span class="kw-2">ref </span>v) => v.size_hint(), + } + } +} + +<span class="kw">impl</span><<span class="lifetime">'a</span>> ExactSizeIterator <span class="kw">for </span>IndexVecIter<<span class="lifetime">'a</span>> {} + +<span class="doccomment">/// Return type of `IndexVec::into_iter`. +</span><span class="attribute">#[derive(Clone, Debug)] +</span><span class="kw">pub enum </span>IndexVecIntoIter { + <span class="attribute">#[doc(hidden)] + </span>U32(vec::IntoIter<u32>), + <span class="attribute">#[doc(hidden)] + </span>USize(vec::IntoIter<usize>), +} + +<span class="kw">impl </span>Iterator <span class="kw">for </span>IndexVecIntoIter { + <span class="kw">type </span>Item = usize; + + <span class="attribute">#[inline] + </span><span class="kw">fn </span>next(<span class="kw-2">&mut </span><span class="self">self</span>) -> <span class="prelude-ty">Option</span><<span class="self">Self</span>::Item> { + <span class="kw">use </span><span class="self">self</span>::IndexVecIntoIter::<span class="kw-2">*</span>; + <span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{ + U32(<span class="kw-2">ref mut </span>v) => v.next().map(|i| i <span class="kw">as </span>usize), + USize(<span class="kw-2">ref mut </span>v) => v.next(), + } + } + + <span class="attribute">#[inline] + </span><span class="kw">fn </span>size_hint(<span class="kw-2">&</span><span class="self">self</span>) -> (usize, <span class="prelude-ty">Option</span><usize>) { + <span class="kw">use </span><span class="self">self</span>::IndexVecIntoIter::<span class="kw-2">*</span>; + <span class="kw">match </span><span class="kw-2">*</span><span class="self">self </span>{ + U32(<span class="kw-2">ref </span>v) => v.size_hint(), + USize(<span class="kw-2">ref </span>v) => v.size_hint(), + } + } +} + +<span class="kw">impl </span>ExactSizeIterator <span class="kw">for </span>IndexVecIntoIter {} + + +<span class="doccomment">/// Randomly sample exactly `amount` distinct indices from `0..length`, and +/// return them in random order (fully shuffled). +/// +/// This method is used internally by the slice sampling methods, but it can +/// sometimes be useful to have the indices themselves so this is provided as +/// an alternative. +/// +/// The implementation used is not specified; we automatically select the +/// fastest available algorithm for the `length` and `amount` parameters +/// (based on detailed profiling on an Intel Haswell CPU). Roughly speaking, +/// complexity is `O(amount)`, except that when `amount` is small, performance +/// is closer to `O(amount^2)`, and when `length` is close to `amount` then +/// `O(length)`. +/// +/// Note that performance is significantly better over `u32` indices than over +/// `u64` indices. Because of this we hide the underlying type behind an +/// abstraction, `IndexVec`. +/// +/// If an allocation-free `no_std` function is required, it is suggested +/// to adapt the internal `sample_floyd` implementation. +/// +/// Panics if `amount > length`. +</span><span class="kw">pub fn </span>sample<R>(rng: <span class="kw-2">&mut </span>R, length: usize, amount: usize) -> IndexVec +<span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">if </span>amount > length { + <span class="macro">panic!</span>(<span class="string">"`amount` of samples must be less than or equal to `length`"</span>); + } + <span class="kw">if </span>length > (::core::u32::MAX <span class="kw">as </span>usize) { + <span class="comment">// We never want to use inplace here, but could use floyd's alg + // Lazy version: always use the cache alg. + </span><span class="kw">return </span>sample_rejection(rng, length, amount); + } + <span class="kw">let </span>amount = amount <span class="kw">as </span>u32; + <span class="kw">let </span>length = length <span class="kw">as </span>u32; + + <span class="comment">// Choice of algorithm here depends on both length and amount. See: + // https://github.com/rust-random/rand/pull/479 + // We do some calculations with f32. Accuracy is not very important. + + </span><span class="kw">if </span>amount < <span class="number">163 </span>{ + <span class="kw">const </span>C: [[f32; <span class="number">2</span>]; <span class="number">2</span>] = [[<span class="number">1.6</span>, <span class="number">8.0 </span>/ <span class="number">45.0</span>], [<span class="number">10.0</span>, <span class="number">70.0 </span>/ <span class="number">9.0</span>]]; + <span class="kw">let </span>j = <span class="kw">if </span>length < <span class="number">500_000 </span>{ <span class="number">0 </span>} <span class="kw">else </span>{ <span class="number">1 </span>}; + <span class="kw">let </span>amount_fp = amount <span class="kw">as </span>f32; + <span class="kw">let </span>m4 = C[<span class="number">0</span>][j] * amount_fp; + <span class="comment">// Short-cut: when amount < 12, floyd's is always faster + </span><span class="kw">if </span>amount > <span class="number">11 </span>&& (length <span class="kw">as </span>f32) < (C[<span class="number">1</span>][j] + m4) * amount_fp { + sample_inplace(rng, length, amount) + } <span class="kw">else </span>{ + sample_floyd(rng, length, amount) + } + } <span class="kw">else </span>{ + <span class="kw">const </span>C: [f32; <span class="number">2</span>] = [<span class="number">270.0</span>, <span class="number">330.0 </span>/ <span class="number">9.0</span>]; + <span class="kw">let </span>j = <span class="kw">if </span>length < <span class="number">500_000 </span>{ <span class="number">0 </span>} <span class="kw">else </span>{ <span class="number">1 </span>}; + <span class="kw">if </span>(length <span class="kw">as </span>f32) < C[j] * (amount <span class="kw">as </span>f32) { + sample_inplace(rng, length, amount) + } <span class="kw">else </span>{ + sample_rejection(rng, length, amount) + } + } +} + +<span class="doccomment">/// Randomly sample exactly `amount` distinct indices from `0..length`, and +/// return them in an arbitrary order (there is no guarantee of shuffling or +/// ordering). The weights are to be provided by the input function `weights`, +/// which will be called once for each index. +/// +/// This method is used internally by the slice sampling methods, but it can +/// sometimes be useful to have the indices themselves so this is provided as +/// an alternative. +/// +/// This implementation uses `O(length + amount)` space and `O(length)` time +/// if the "nightly" feature is enabled, or `O(length)` space and +/// `O(length + amount * log length)` time otherwise. +/// +/// Panics if `amount > length`. +</span><span class="attribute">#[cfg(feature = <span class="string">"std"</span>)] +#[cfg_attr(doc_cfg, doc(cfg(feature = <span class="string">"std"</span>)))] +</span><span class="kw">pub fn </span>sample_weighted<R, F, X>( + rng: <span class="kw-2">&mut </span>R, length: usize, weight: F, amount: usize, +) -> <span class="prelude-ty">Result</span><IndexVec, WeightedError> +<span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + F: Fn(usize) -> X, + X: Into<f64>, +{ + <span class="kw">if </span>length > (core::u32::MAX <span class="kw">as </span>usize) { + sample_efraimidis_spirakis(rng, length, weight, amount) + } <span class="kw">else </span>{ + <span class="macro">assert!</span>(amount <= core::u32::MAX <span class="kw">as </span>usize); + <span class="kw">let </span>amount = amount <span class="kw">as </span>u32; + <span class="kw">let </span>length = length <span class="kw">as </span>u32; + sample_efraimidis_spirakis(rng, length, weight, amount) + } +} + + +<span class="doccomment">/// Randomly sample exactly `amount` distinct indices from `0..length`, and +/// return them in an arbitrary order (there is no guarantee of shuffling or +/// ordering). The weights are to be provided by the input function `weights`, +/// which will be called once for each index. +/// +/// This implementation uses the algorithm described by Efraimidis and Spirakis +/// in this paper: https://doi.org/10.1016/j.ipl.2005.11.003 +/// It uses `O(length + amount)` space and `O(length)` time if the +/// "nightly" feature is enabled, or `O(length)` space and `O(length +/// + amount * log length)` time otherwise. +/// +/// Panics if `amount > length`. +</span><span class="attribute">#[cfg(feature = <span class="string">"std"</span>)] +</span><span class="kw">fn </span>sample_efraimidis_spirakis<R, F, X, N>( + rng: <span class="kw-2">&mut </span>R, length: N, weight: F, amount: N, +) -> <span class="prelude-ty">Result</span><IndexVec, WeightedError> +<span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + F: Fn(usize) -> X, + X: Into<f64>, + N: UInt, + IndexVec: From<Vec<N>>, +{ + <span class="kw">if </span>amount == N::zero() { + <span class="kw">return </span><span class="prelude-val">Ok</span>(IndexVec::U32(Vec::new())); + } + + <span class="kw">if </span>amount > length { + <span class="macro">panic!</span>(<span class="string">"`amount` of samples must be less than or equal to `length`"</span>); + } + + <span class="kw">struct </span>Element<N> { + index: N, + key: f64, + } + <span class="kw">impl</span><N> PartialOrd <span class="kw">for </span>Element<N> { + <span class="kw">fn </span>partial_cmp(<span class="kw-2">&</span><span class="self">self</span>, other: <span class="kw-2">&</span><span class="self">Self</span>) -> <span class="prelude-ty">Option</span><core::cmp::Ordering> { + <span class="self">self</span>.key.partial_cmp(<span class="kw-2">&</span>other.key) + } + } + <span class="kw">impl</span><N> Ord <span class="kw">for </span>Element<N> { + <span class="kw">fn </span>cmp(<span class="kw-2">&</span><span class="self">self</span>, other: <span class="kw-2">&</span><span class="self">Self</span>) -> core::cmp::Ordering { + <span class="comment">// partial_cmp will always produce a value, + // because we check that the weights are not nan + </span><span class="self">self</span>.partial_cmp(other).unwrap() + } + } + <span class="kw">impl</span><N> PartialEq <span class="kw">for </span>Element<N> { + <span class="kw">fn </span>eq(<span class="kw-2">&</span><span class="self">self</span>, other: <span class="kw-2">&</span><span class="self">Self</span>) -> bool { + <span class="self">self</span>.key == other.key + } + } + <span class="kw">impl</span><N> Eq <span class="kw">for </span>Element<N> {} + + <span class="attribute">#[cfg(feature = <span class="string">"nightly"</span>)] + </span>{ + <span class="kw">let </span><span class="kw-2">mut </span>candidates = Vec::with_capacity(length.as_usize()); + <span class="kw">let </span><span class="kw-2">mut </span>index = N::zero(); + <span class="kw">while </span>index < length { + <span class="kw">let </span>weight = weight(index.as_usize()).into(); + <span class="kw">if </span>!(weight >= <span class="number">0.</span>) { + <span class="kw">return </span><span class="prelude-val">Err</span>(WeightedError::InvalidWeight); + } + + <span class="kw">let </span>key = rng.gen::<f64>().powf(<span class="number">1.0 </span>/ weight); + candidates.push(Element { index, key }); + + index += N::one(); + } + + <span class="comment">// Partially sort the array to find the `amount` elements with the greatest + // keys. Do this by using `select_nth_unstable` to put the elements with + // the *smallest* keys at the beginning of the list in `O(n)` time, which + // provides equivalent information about the elements with the *greatest* keys. + </span><span class="kw">let </span>(<span class="kw">_</span>, mid, greater) + = candidates.select_nth_unstable(length.as_usize() - amount.as_usize()); + + <span class="kw">let </span><span class="kw-2">mut </span>result: Vec<N> = Vec::with_capacity(amount.as_usize()); + result.push(mid.index); + <span class="kw">for </span>element <span class="kw">in </span>greater { + result.push(element.index); + } + <span class="prelude-val">Ok</span>(IndexVec::from(result)) + } + + <span class="attribute">#[cfg(not(feature = <span class="string">"nightly"</span>))] + </span>{ + <span class="kw">use </span>alloc::collections::BinaryHeap; + + <span class="comment">// Partially sort the array such that the `amount` elements with the largest + // keys are first using a binary max heap. + </span><span class="kw">let </span><span class="kw-2">mut </span>candidates = BinaryHeap::with_capacity(length.as_usize()); + <span class="kw">let </span><span class="kw-2">mut </span>index = N::zero(); + <span class="kw">while </span>index < length { + <span class="kw">let </span>weight = weight(index.as_usize()).into(); + <span class="kw">if </span>!(weight >= <span class="number">0.</span>) { + <span class="kw">return </span><span class="prelude-val">Err</span>(WeightedError::InvalidWeight); + } + + <span class="kw">let </span>key = rng.gen::<f64>().powf(<span class="number">1.0 </span>/ weight); + candidates.push(Element { index, key }); + + index += N::one(); + } + + <span class="kw">let </span><span class="kw-2">mut </span>result: Vec<N> = Vec::with_capacity(amount.as_usize()); + <span class="kw">while </span>result.len() < amount.as_usize() { + result.push(candidates.pop().unwrap().index); + } + <span class="prelude-val">Ok</span>(IndexVec::from(result)) + } +} + +<span class="doccomment">/// Randomly sample exactly `amount` indices from `0..length`, using Floyd's +/// combination algorithm. +/// +/// The output values are fully shuffled. (Overhead is under 50%.) +/// +/// This implementation uses `O(amount)` memory and `O(amount^2)` time. +</span><span class="kw">fn </span>sample_floyd<R>(rng: <span class="kw-2">&mut </span>R, length: u32, amount: u32) -> IndexVec +<span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="comment">// For small amount we use Floyd's fully-shuffled variant. For larger + // amounts this is slow due to Vec::insert performance, so we shuffle + // afterwards. Benchmarks show little overhead from extra logic. + </span><span class="kw">let </span>floyd_shuffle = amount < <span class="number">50</span>; + + <span class="macro">debug_assert!</span>(amount <= length); + <span class="kw">let </span><span class="kw-2">mut </span>indices = Vec::with_capacity(amount <span class="kw">as </span>usize); + <span class="kw">for </span>j <span class="kw">in </span>length - amount..length { + <span class="kw">let </span>t = rng.gen_range(<span class="number">0</span>..=j); + <span class="kw">if </span>floyd_shuffle { + <span class="kw">if let </span><span class="prelude-val">Some</span>(pos) = indices.iter().position(|<span class="kw-2">&</span>x| x == t) { + indices.insert(pos, j); + <span class="kw">continue</span>; + } + } <span class="kw">else if </span>indices.contains(<span class="kw-2">&</span>t) { + indices.push(j); + <span class="kw">continue</span>; + } + indices.push(t); + } + <span class="kw">if </span>!floyd_shuffle { + <span class="comment">// Reimplement SliceRandom::shuffle with smaller indices + </span><span class="kw">for </span>i <span class="kw">in </span>(<span class="number">1</span>..amount).rev() { + <span class="comment">// invariant: elements with index > i have been locked in place. + </span>indices.swap(i <span class="kw">as </span>usize, rng.gen_range(<span class="number">0</span>..=i) <span class="kw">as </span>usize); + } + } + IndexVec::from(indices) +} + +<span class="doccomment">/// Randomly sample exactly `amount` indices from `0..length`, using an inplace +/// partial Fisher-Yates method. +/// Sample an amount of indices using an inplace partial fisher yates method. +/// +/// This allocates the entire `length` of indices and randomizes only the first `amount`. +/// It then truncates to `amount` and returns. +/// +/// This method is not appropriate for large `length` and potentially uses a lot +/// of memory; because of this we only implement for `u32` index (which improves +/// performance in all cases). +/// +/// Set-up is `O(length)` time and memory and shuffling is `O(amount)` time. +</span><span class="kw">fn </span>sample_inplace<R>(rng: <span class="kw-2">&mut </span>R, length: u32, amount: u32) -> IndexVec +<span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="macro">debug_assert!</span>(amount <= length); + <span class="kw">let </span><span class="kw-2">mut </span>indices: Vec<u32> = Vec::with_capacity(length <span class="kw">as </span>usize); + indices.extend(<span class="number">0</span>..length); + <span class="kw">for </span>i <span class="kw">in </span><span class="number">0</span>..amount { + <span class="kw">let </span>j: u32 = rng.gen_range(i..length); + indices.swap(i <span class="kw">as </span>usize, j <span class="kw">as </span>usize); + } + indices.truncate(amount <span class="kw">as </span>usize); + <span class="macro">debug_assert_eq!</span>(indices.len(), amount <span class="kw">as </span>usize); + IndexVec::from(indices) +} + +<span class="kw">trait </span>UInt: Copy + PartialOrd + Ord + PartialEq + Eq + SampleUniform + + core::hash::Hash + core::ops::AddAssign { + <span class="kw">fn </span>zero() -> <span class="self">Self</span>; + <span class="kw">fn </span>one() -> <span class="self">Self</span>; + <span class="kw">fn </span>as_usize(<span class="self">self</span>) -> usize; +} +<span class="kw">impl </span>UInt <span class="kw">for </span>u32 { + <span class="attribute">#[inline] + </span><span class="kw">fn </span>zero() -> <span class="self">Self </span>{ + <span class="number">0 + </span>} + + <span class="attribute">#[inline] + </span><span class="kw">fn </span>one() -> <span class="self">Self </span>{ + <span class="number">1 + </span>} + + <span class="attribute">#[inline] + </span><span class="kw">fn </span>as_usize(<span class="self">self</span>) -> usize { + <span class="self">self </span><span class="kw">as </span>usize + } +} +<span class="kw">impl </span>UInt <span class="kw">for </span>usize { + <span class="attribute">#[inline] + </span><span class="kw">fn </span>zero() -> <span class="self">Self </span>{ + <span class="number">0 + </span>} + + <span class="attribute">#[inline] + </span><span class="kw">fn </span>one() -> <span class="self">Self </span>{ + <span class="number">1 + </span>} + + <span class="attribute">#[inline] + </span><span class="kw">fn </span>as_usize(<span class="self">self</span>) -> usize { + <span class="self">self + </span>} +} + +<span class="doccomment">/// Randomly sample exactly `amount` indices from `0..length`, using rejection +/// sampling. +/// +/// Since `amount <<< length` there is a low chance of a random sample in +/// `0..length` being a duplicate. We test for duplicates and resample where +/// necessary. The algorithm is `O(amount)` time and memory. +/// +/// This function is generic over X primarily so that results are value-stable +/// over 32-bit and 64-bit platforms. +</span><span class="kw">fn </span>sample_rejection<X: UInt, R>(rng: <span class="kw-2">&mut </span>R, length: X, amount: X) -> IndexVec +<span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + IndexVec: From<Vec<X>>, +{ + <span class="macro">debug_assert!</span>(amount < length); + <span class="attribute">#[cfg(feature = <span class="string">"std"</span>)] + </span><span class="kw">let </span><span class="kw-2">mut </span>cache = HashSet::with_capacity(amount.as_usize()); + <span class="attribute">#[cfg(not(feature = <span class="string">"std"</span>))] + </span><span class="kw">let </span><span class="kw-2">mut </span>cache = BTreeSet::new(); + <span class="kw">let </span>distr = Uniform::new(X::zero(), length); + <span class="kw">let </span><span class="kw-2">mut </span>indices = Vec::with_capacity(amount.as_usize()); + <span class="kw">for _ in </span><span class="number">0</span>..amount.as_usize() { + <span class="kw">let </span><span class="kw-2">mut </span>pos = distr.sample(rng); + <span class="kw">while </span>!cache.insert(pos) { + pos = distr.sample(rng); + } + indices.push(pos); + } + + <span class="macro">debug_assert_eq!</span>(indices.len(), amount.as_usize()); + IndexVec::from(indices) +} + +<span class="attribute">#[cfg(test)] +</span><span class="kw">mod </span>test { + <span class="kw">use super</span>::<span class="kw-2">*</span>; + + <span class="attribute">#[test] + #[cfg(feature = <span class="string">"serde1"</span>)] + </span><span class="kw">fn </span>test_serialization_index_vec() { + <span class="kw">let </span>some_index_vec = IndexVec::from(<span class="macro">vec!</span>[<span class="number">254_usize</span>, <span class="number">234</span>, <span class="number">2</span>, <span class="number">1</span>]); + <span class="kw">let </span>de_some_index_vec: IndexVec = bincode::deserialize(<span class="kw-2">&</span>bincode::serialize(<span class="kw-2">&</span>some_index_vec).unwrap()).unwrap(); + <span class="kw">match </span>(some_index_vec, de_some_index_vec) { + (IndexVec::U32(a), IndexVec::U32(b)) => { + <span class="macro">assert_eq!</span>(a, b); + }, + (IndexVec::USize(a), IndexVec::USize(b)) => { + <span class="macro">assert_eq!</span>(a, b); + }, + <span class="kw">_ </span>=> {<span class="macro">panic!</span>(<span class="string">"failed to seralize/deserialize `IndexVec`"</span>)} + } + } + + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] </span><span class="kw">use </span>alloc::vec; + + <span class="attribute">#[test] + </span><span class="kw">fn </span>test_sample_boundaries() { + <span class="kw">let </span><span class="kw-2">mut </span>r = <span class="kw">crate</span>::test::rng(<span class="number">404</span>); + + <span class="macro">assert_eq!</span>(sample_inplace(<span class="kw-2">&mut </span>r, <span class="number">0</span>, <span class="number">0</span>).len(), <span class="number">0</span>); + <span class="macro">assert_eq!</span>(sample_inplace(<span class="kw-2">&mut </span>r, <span class="number">1</span>, <span class="number">0</span>).len(), <span class="number">0</span>); + <span class="macro">assert_eq!</span>(sample_inplace(<span class="kw-2">&mut </span>r, <span class="number">1</span>, <span class="number">1</span>).into_vec(), <span class="macro">vec!</span>[<span class="number">0</span>]); + + <span class="macro">assert_eq!</span>(sample_rejection(<span class="kw-2">&mut </span>r, <span class="number">1u32</span>, <span class="number">0</span>).len(), <span class="number">0</span>); + + <span class="macro">assert_eq!</span>(sample_floyd(<span class="kw-2">&mut </span>r, <span class="number">0</span>, <span class="number">0</span>).len(), <span class="number">0</span>); + <span class="macro">assert_eq!</span>(sample_floyd(<span class="kw-2">&mut </span>r, <span class="number">1</span>, <span class="number">0</span>).len(), <span class="number">0</span>); + <span class="macro">assert_eq!</span>(sample_floyd(<span class="kw-2">&mut </span>r, <span class="number">1</span>, <span class="number">1</span>).into_vec(), <span class="macro">vec!</span>[<span class="number">0</span>]); + + <span class="comment">// These algorithms should be fast with big numbers. Test average. + </span><span class="kw">let </span>sum: usize = sample_rejection(<span class="kw-2">&mut </span>r, <span class="number">1 </span><< <span class="number">25</span>, <span class="number">10u32</span>).into_iter().sum(); + <span class="macro">assert!</span>(<span class="number">1 </span><< <span class="number">25 </span>< sum && sum < (<span class="number">1 </span><< <span class="number">25</span>) * <span class="number">25</span>); + + <span class="kw">let </span>sum: usize = sample_floyd(<span class="kw-2">&mut </span>r, <span class="number">1 </span><< <span class="number">25</span>, <span class="number">10</span>).into_iter().sum(); + <span class="macro">assert!</span>(<span class="number">1 </span><< <span class="number">25 </span>< sum && sum < (<span class="number">1 </span><< <span class="number">25</span>) * <span class="number">25</span>); + } + + <span class="attribute">#[test] + #[cfg_attr(miri, ignore)] </span><span class="comment">// Miri is too slow + </span><span class="kw">fn </span>test_sample_alg() { + <span class="kw">let </span>seed_rng = <span class="kw">crate</span>::test::rng; + + <span class="comment">// We can't test which algorithm is used directly, but Floyd's alg + // should produce different results from the others. (Also, `inplace` + // and `cached` currently use different sizes thus produce different results.) + + // A small length and relatively large amount should use inplace + </span><span class="kw">let </span>(length, amount): (usize, usize) = (<span class="number">100</span>, <span class="number">50</span>); + <span class="kw">let </span>v1 = sample(<span class="kw-2">&mut </span>seed_rng(<span class="number">420</span>), length, amount); + <span class="kw">let </span>v2 = sample_inplace(<span class="kw-2">&mut </span>seed_rng(<span class="number">420</span>), length <span class="kw">as </span>u32, amount <span class="kw">as </span>u32); + <span class="macro">assert!</span>(v1.iter().all(|e| e < length)); + <span class="macro">assert_eq!</span>(v1, v2); + + <span class="comment">// Test Floyd's alg does produce different results + </span><span class="kw">let </span>v3 = sample_floyd(<span class="kw-2">&mut </span>seed_rng(<span class="number">420</span>), length <span class="kw">as </span>u32, amount <span class="kw">as </span>u32); + <span class="macro">assert!</span>(v1 != v3); + + <span class="comment">// A large length and small amount should use Floyd + </span><span class="kw">let </span>(length, amount): (usize, usize) = (<span class="number">1 </span><< <span class="number">20</span>, <span class="number">50</span>); + <span class="kw">let </span>v1 = sample(<span class="kw-2">&mut </span>seed_rng(<span class="number">421</span>), length, amount); + <span class="kw">let </span>v2 = sample_floyd(<span class="kw-2">&mut </span>seed_rng(<span class="number">421</span>), length <span class="kw">as </span>u32, amount <span class="kw">as </span>u32); + <span class="macro">assert!</span>(v1.iter().all(|e| e < length)); + <span class="macro">assert_eq!</span>(v1, v2); + + <span class="comment">// A large length and larger amount should use cache + </span><span class="kw">let </span>(length, amount): (usize, usize) = (<span class="number">1 </span><< <span class="number">20</span>, <span class="number">600</span>); + <span class="kw">let </span>v1 = sample(<span class="kw-2">&mut </span>seed_rng(<span class="number">422</span>), length, amount); + <span class="kw">let </span>v2 = sample_rejection(<span class="kw-2">&mut </span>seed_rng(<span class="number">422</span>), length <span class="kw">as </span>u32, amount <span class="kw">as </span>u32); + <span class="macro">assert!</span>(v1.iter().all(|e| e < length)); + <span class="macro">assert_eq!</span>(v1, v2); + } + + <span class="attribute">#[cfg(feature = <span class="string">"std"</span>)] + #[test] + </span><span class="kw">fn </span>test_sample_weighted() { + <span class="kw">let </span>seed_rng = <span class="kw">crate</span>::test::rng; + <span class="kw">for </span><span class="kw-2">&</span>(amount, len) <span class="kw">in </span><span class="kw-2">&</span>[(<span class="number">0</span>, <span class="number">10</span>), (<span class="number">5</span>, <span class="number">10</span>), (<span class="number">10</span>, <span class="number">10</span>)] { + <span class="kw">let </span>v = sample_weighted(<span class="kw-2">&mut </span>seed_rng(<span class="number">423</span>), len, |i| i <span class="kw">as </span>f64, amount).unwrap(); + <span class="kw">match </span>v { + IndexVec::U32(<span class="kw-2">mut </span>indices) => { + <span class="macro">assert_eq!</span>(indices.len(), amount); + indices.sort_unstable(); + indices.dedup(); + <span class="macro">assert_eq!</span>(indices.len(), amount); + <span class="kw">for </span><span class="kw-2">&</span>i <span class="kw">in </span><span class="kw-2">&</span>indices { + <span class="macro">assert!</span>((i <span class="kw">as </span>usize) < len); + } + }, + IndexVec::USize(<span class="kw">_</span>) => <span class="macro">panic!</span>(<span class="string">"expected `IndexVec::U32`"</span>), + } + } + } + + <span class="attribute">#[test] + </span><span class="kw">fn </span>value_stability_sample() { + <span class="kw">let </span>do_test = |length, amount, values: <span class="kw-2">&</span>[u32]| { + <span class="kw">let </span><span class="kw-2">mut </span>buf = [<span class="number">0u32</span>; <span class="number">8</span>]; + <span class="kw">let </span><span class="kw-2">mut </span>rng = <span class="kw">crate</span>::test::rng(<span class="number">410</span>); + + <span class="kw">let </span>res = sample(<span class="kw-2">&mut </span>rng, length, amount); + <span class="kw">let </span>len = res.len().min(buf.len()); + <span class="kw">for </span>(x, y) <span class="kw">in </span>res.into_iter().zip(buf.iter_mut()) { + <span class="kw-2">*</span>y = x <span class="kw">as </span>u32; + } + <span class="macro">assert_eq!</span>( + <span class="kw-2">&</span>buf[<span class="number">0</span>..len], + values, + <span class="string">"failed sampling {}, {}"</span>, + length, + amount + ); + }; + + do_test(<span class="number">10</span>, <span class="number">6</span>, <span class="kw-2">&</span>[<span class="number">8</span>, <span class="number">0</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">9</span>, <span class="number">6</span>]); <span class="comment">// floyd + </span>do_test(<span class="number">25</span>, <span class="number">10</span>, <span class="kw-2">&</span>[<span class="number">18</span>, <span class="number">15</span>, <span class="number">14</span>, <span class="number">9</span>, <span class="number">0</span>, <span class="number">13</span>, <span class="number">5</span>, <span class="number">24</span>]); <span class="comment">// floyd + </span>do_test(<span class="number">300</span>, <span class="number">8</span>, <span class="kw-2">&</span>[<span class="number">30</span>, <span class="number">283</span>, <span class="number">150</span>, <span class="number">1</span>, <span class="number">73</span>, <span class="number">13</span>, <span class="number">285</span>, <span class="number">35</span>]); <span class="comment">// floyd + </span>do_test(<span class="number">300</span>, <span class="number">80</span>, <span class="kw-2">&</span>[<span class="number">31</span>, <span class="number">289</span>, <span class="number">248</span>, <span class="number">154</span>, <span class="number">5</span>, <span class="number">78</span>, <span class="number">19</span>, <span class="number">286</span>]); <span class="comment">// inplace + </span>do_test(<span class="number">300</span>, <span class="number">180</span>, <span class="kw-2">&</span>[<span class="number">31</span>, <span class="number">289</span>, <span class="number">248</span>, <span class="number">154</span>, <span class="number">5</span>, <span class="number">78</span>, <span class="number">19</span>, <span class="number">286</span>]); <span class="comment">// inplace + + </span>do_test(<span class="number">1_000_000</span>, <span class="number">8</span>, <span class="kw-2">&</span>[ + <span class="number">103717</span>, <span class="number">963485</span>, <span class="number">826422</span>, <span class="number">509101</span>, <span class="number">736394</span>, <span class="number">807035</span>, <span class="number">5327</span>, <span class="number">632573</span>, + ]); <span class="comment">// floyd + </span>do_test(<span class="number">1_000_000</span>, <span class="number">180</span>, <span class="kw-2">&</span>[ + <span class="number">103718</span>, <span class="number">963490</span>, <span class="number">826426</span>, <span class="number">509103</span>, <span class="number">736396</span>, <span class="number">807036</span>, <span class="number">5327</span>, <span class="number">632573</span>, + ]); <span class="comment">// rejection + </span>} +} +</code></pre></div> +</section></div></main><div id="rustdoc-vars" data-root-path="../../../" data-current-crate="rand" data-themes="ayu,dark,light" data-resource-suffix="" data-rustdoc-version="1.66.0 (69f9c33d7 2022-12-12) (Arch Linux rust 1:1.66.0-1)" ></div></body></html>
\ No newline at end of file diff --git a/rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq/mod.rs.html b/rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq/mod.rs.html new file mode 100644 index 0000000..99cd32d --- /dev/null +++ b/rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq/mod.rs.html @@ -0,0 +1,2715 @@ +<!DOCTYPE html><html lang="en"><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="generator" content="rustdoc"><meta name="description" content="Source of the Rust file `/home/pico/.local/share/cargo/registry/src/github.com-1ecc6299db9ec823/rand-0.8.5/src/seq/mod.rs`."><meta name="keywords" content="rust, rustlang, rust-lang"><title>mod.rs - source</title><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceSerif4-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../FiraSans-Regular.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../FiraSans-Medium.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceCodePro-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceSerif4-Bold.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceCodePro-Semibold.ttf.woff2"><link rel="stylesheet" href="../../../normalize.css"><link rel="stylesheet" href="../../../rustdoc.css" id="mainThemeStyle"><link rel="stylesheet" href="../../../ayu.css" disabled><link rel="stylesheet" href="../../../dark.css" disabled><link rel="stylesheet" href="../../../light.css" id="themeStyle"><script id="default-settings" ></script><script src="../../../storage.js"></script><script defer src="../../../source-script.js"></script><script defer src="../../../source-files.js"></script><script defer src="../../../main.js"></script><noscript><link rel="stylesheet" href="../../../noscript.css"></noscript><link rel="icon" href="https://www.rust-lang.org/favicon.ico"></head><body class="rustdoc source"><!--[if lte IE 11]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><nav class="sidebar"></nav><main><div class="width-limiter"><nav class="sub"><a class="sub-logo-container" href="../../../rand/index.html"> + <img src="https://www.rust-lang.org/logos/rust-logo-128x128-blk.png" alt="logo"></a><form class="search-form"><span></span><input class="search-input" name="search" autocomplete="off" spellcheck="false" placeholder="Click or press ‘S’ to search, ‘?’ for more options…" type="search"><div id="help-button" title="help" tabindex="-1"><a href="../../../help.html">?</a></div><div id="settings-menu" tabindex="-1"><a href="../../../settings.html" title="settings"><img width="22" height="22" alt="Change settings" src="../../../wheel.svg"></a></div></form></nav><section id="main-content" class="content"><div class="example-wrap"><pre class="src-line-numbers"><span id="1">1</span> +<span id="2">2</span> +<span id="3">3</span> +<span id="4">4</span> +<span id="5">5</span> +<span id="6">6</span> +<span id="7">7</span> +<span id="8">8</span> +<span id="9">9</span> +<span id="10">10</span> +<span id="11">11</span> +<span id="12">12</span> +<span id="13">13</span> +<span id="14">14</span> +<span id="15">15</span> +<span id="16">16</span> +<span id="17">17</span> +<span id="18">18</span> +<span id="19">19</span> +<span id="20">20</span> +<span id="21">21</span> +<span id="22">22</span> +<span id="23">23</span> +<span id="24">24</span> +<span id="25">25</span> +<span id="26">26</span> +<span id="27">27</span> +<span id="28">28</span> +<span id="29">29</span> +<span id="30">30</span> +<span id="31">31</span> +<span id="32">32</span> +<span id="33">33</span> +<span id="34">34</span> +<span id="35">35</span> +<span id="36">36</span> +<span id="37">37</span> +<span id="38">38</span> +<span id="39">39</span> +<span id="40">40</span> +<span id="41">41</span> +<span id="42">42</span> +<span id="43">43</span> +<span id="44">44</span> +<span id="45">45</span> +<span id="46">46</span> +<span id="47">47</span> +<span id="48">48</span> +<span id="49">49</span> +<span id="50">50</span> +<span id="51">51</span> +<span id="52">52</span> +<span id="53">53</span> +<span id="54">54</span> +<span id="55">55</span> +<span id="56">56</span> +<span id="57">57</span> +<span id="58">58</span> +<span id="59">59</span> +<span id="60">60</span> +<span id="61">61</span> +<span id="62">62</span> +<span id="63">63</span> +<span id="64">64</span> +<span id="65">65</span> +<span id="66">66</span> +<span id="67">67</span> +<span id="68">68</span> +<span id="69">69</span> +<span id="70">70</span> +<span id="71">71</span> +<span id="72">72</span> +<span id="73">73</span> +<span id="74">74</span> +<span id="75">75</span> +<span id="76">76</span> +<span id="77">77</span> +<span id="78">78</span> +<span id="79">79</span> +<span id="80">80</span> +<span id="81">81</span> +<span id="82">82</span> +<span id="83">83</span> +<span id="84">84</span> +<span id="85">85</span> +<span id="86">86</span> +<span id="87">87</span> +<span id="88">88</span> +<span id="89">89</span> +<span id="90">90</span> +<span id="91">91</span> +<span id="92">92</span> +<span id="93">93</span> +<span id="94">94</span> +<span id="95">95</span> +<span id="96">96</span> +<span id="97">97</span> +<span id="98">98</span> +<span id="99">99</span> +<span id="100">100</span> +<span id="101">101</span> +<span id="102">102</span> +<span id="103">103</span> +<span id="104">104</span> +<span id="105">105</span> +<span id="106">106</span> +<span id="107">107</span> +<span id="108">108</span> +<span id="109">109</span> +<span id="110">110</span> +<span id="111">111</span> +<span id="112">112</span> +<span id="113">113</span> +<span id="114">114</span> +<span id="115">115</span> +<span id="116">116</span> +<span id="117">117</span> +<span id="118">118</span> +<span id="119">119</span> +<span id="120">120</span> +<span id="121">121</span> +<span id="122">122</span> +<span id="123">123</span> +<span id="124">124</span> +<span id="125">125</span> +<span id="126">126</span> +<span id="127">127</span> +<span id="128">128</span> +<span id="129">129</span> +<span id="130">130</span> +<span id="131">131</span> +<span id="132">132</span> +<span id="133">133</span> +<span id="134">134</span> +<span id="135">135</span> +<span id="136">136</span> +<span id="137">137</span> +<span id="138">138</span> +<span id="139">139</span> +<span id="140">140</span> +<span id="141">141</span> +<span id="142">142</span> +<span id="143">143</span> +<span id="144">144</span> +<span id="145">145</span> +<span id="146">146</span> +<span id="147">147</span> +<span id="148">148</span> +<span id="149">149</span> +<span id="150">150</span> +<span id="151">151</span> +<span id="152">152</span> +<span id="153">153</span> +<span id="154">154</span> +<span id="155">155</span> +<span id="156">156</span> +<span id="157">157</span> +<span id="158">158</span> +<span id="159">159</span> +<span id="160">160</span> +<span id="161">161</span> +<span id="162">162</span> +<span id="163">163</span> +<span id="164">164</span> +<span id="165">165</span> +<span id="166">166</span> +<span id="167">167</span> +<span id="168">168</span> +<span id="169">169</span> +<span id="170">170</span> +<span id="171">171</span> +<span id="172">172</span> +<span id="173">173</span> +<span id="174">174</span> +<span id="175">175</span> +<span id="176">176</span> +<span id="177">177</span> +<span id="178">178</span> +<span id="179">179</span> +<span id="180">180</span> +<span id="181">181</span> +<span id="182">182</span> +<span id="183">183</span> +<span id="184">184</span> +<span id="185">185</span> +<span id="186">186</span> +<span id="187">187</span> +<span id="188">188</span> +<span id="189">189</span> +<span id="190">190</span> +<span id="191">191</span> +<span id="192">192</span> +<span id="193">193</span> +<span id="194">194</span> +<span id="195">195</span> +<span id="196">196</span> +<span id="197">197</span> +<span id="198">198</span> +<span id="199">199</span> +<span id="200">200</span> +<span id="201">201</span> +<span id="202">202</span> +<span id="203">203</span> +<span id="204">204</span> +<span id="205">205</span> +<span id="206">206</span> +<span id="207">207</span> +<span id="208">208</span> +<span id="209">209</span> +<span id="210">210</span> +<span id="211">211</span> +<span id="212">212</span> +<span id="213">213</span> +<span id="214">214</span> +<span id="215">215</span> +<span id="216">216</span> +<span id="217">217</span> +<span id="218">218</span> +<span id="219">219</span> +<span id="220">220</span> +<span id="221">221</span> +<span id="222">222</span> +<span id="223">223</span> +<span id="224">224</span> +<span id="225">225</span> +<span id="226">226</span> +<span id="227">227</span> +<span id="228">228</span> +<span id="229">229</span> +<span id="230">230</span> +<span id="231">231</span> +<span id="232">232</span> +<span id="233">233</span> +<span id="234">234</span> +<span id="235">235</span> +<span id="236">236</span> +<span id="237">237</span> +<span id="238">238</span> +<span id="239">239</span> +<span id="240">240</span> +<span id="241">241</span> +<span id="242">242</span> +<span id="243">243</span> +<span id="244">244</span> +<span id="245">245</span> +<span id="246">246</span> +<span id="247">247</span> +<span id="248">248</span> +<span id="249">249</span> +<span id="250">250</span> +<span id="251">251</span> +<span id="252">252</span> +<span id="253">253</span> +<span id="254">254</span> +<span id="255">255</span> +<span id="256">256</span> +<span id="257">257</span> +<span id="258">258</span> +<span id="259">259</span> +<span id="260">260</span> +<span id="261">261</span> +<span id="262">262</span> +<span id="263">263</span> +<span id="264">264</span> +<span id="265">265</span> +<span id="266">266</span> +<span id="267">267</span> +<span id="268">268</span> +<span id="269">269</span> +<span id="270">270</span> +<span id="271">271</span> +<span id="272">272</span> +<span id="273">273</span> +<span id="274">274</span> +<span id="275">275</span> +<span id="276">276</span> +<span id="277">277</span> +<span id="278">278</span> +<span id="279">279</span> +<span id="280">280</span> +<span id="281">281</span> +<span id="282">282</span> +<span id="283">283</span> +<span id="284">284</span> +<span id="285">285</span> +<span id="286">286</span> +<span id="287">287</span> +<span id="288">288</span> +<span id="289">289</span> +<span id="290">290</span> +<span id="291">291</span> +<span id="292">292</span> +<span id="293">293</span> +<span id="294">294</span> +<span id="295">295</span> +<span id="296">296</span> +<span id="297">297</span> +<span id="298">298</span> +<span id="299">299</span> +<span id="300">300</span> +<span id="301">301</span> +<span id="302">302</span> +<span id="303">303</span> +<span id="304">304</span> +<span id="305">305</span> +<span id="306">306</span> +<span id="307">307</span> +<span id="308">308</span> +<span id="309">309</span> +<span id="310">310</span> +<span id="311">311</span> +<span id="312">312</span> +<span id="313">313</span> +<span id="314">314</span> +<span id="315">315</span> +<span id="316">316</span> +<span id="317">317</span> +<span id="318">318</span> +<span id="319">319</span> +<span id="320">320</span> +<span id="321">321</span> +<span id="322">322</span> +<span id="323">323</span> +<span id="324">324</span> +<span id="325">325</span> +<span id="326">326</span> +<span id="327">327</span> +<span id="328">328</span> +<span id="329">329</span> +<span id="330">330</span> +<span id="331">331</span> +<span id="332">332</span> +<span id="333">333</span> +<span id="334">334</span> +<span id="335">335</span> +<span id="336">336</span> +<span id="337">337</span> +<span id="338">338</span> +<span id="339">339</span> +<span id="340">340</span> +<span id="341">341</span> +<span id="342">342</span> +<span id="343">343</span> +<span id="344">344</span> +<span id="345">345</span> +<span id="346">346</span> +<span id="347">347</span> +<span id="348">348</span> +<span id="349">349</span> +<span id="350">350</span> +<span id="351">351</span> +<span id="352">352</span> +<span id="353">353</span> +<span id="354">354</span> +<span id="355">355</span> +<span id="356">356</span> +<span id="357">357</span> +<span id="358">358</span> +<span id="359">359</span> +<span id="360">360</span> +<span id="361">361</span> +<span id="362">362</span> +<span id="363">363</span> +<span id="364">364</span> +<span id="365">365</span> +<span id="366">366</span> +<span id="367">367</span> +<span id="368">368</span> +<span id="369">369</span> +<span id="370">370</span> +<span id="371">371</span> +<span id="372">372</span> +<span id="373">373</span> +<span id="374">374</span> +<span id="375">375</span> +<span id="376">376</span> +<span id="377">377</span> +<span id="378">378</span> +<span id="379">379</span> +<span id="380">380</span> +<span id="381">381</span> +<span id="382">382</span> +<span id="383">383</span> +<span id="384">384</span> +<span id="385">385</span> +<span id="386">386</span> +<span id="387">387</span> +<span id="388">388</span> +<span id="389">389</span> +<span id="390">390</span> +<span id="391">391</span> +<span id="392">392</span> +<span id="393">393</span> +<span id="394">394</span> +<span id="395">395</span> +<span id="396">396</span> +<span id="397">397</span> +<span id="398">398</span> +<span id="399">399</span> +<span id="400">400</span> +<span id="401">401</span> +<span id="402">402</span> +<span id="403">403</span> +<span id="404">404</span> +<span id="405">405</span> +<span id="406">406</span> +<span id="407">407</span> +<span id="408">408</span> +<span id="409">409</span> +<span id="410">410</span> +<span id="411">411</span> +<span id="412">412</span> +<span id="413">413</span> +<span id="414">414</span> +<span id="415">415</span> +<span id="416">416</span> +<span id="417">417</span> +<span id="418">418</span> +<span id="419">419</span> +<span id="420">420</span> +<span id="421">421</span> +<span id="422">422</span> +<span id="423">423</span> +<span id="424">424</span> +<span id="425">425</span> +<span id="426">426</span> +<span id="427">427</span> +<span id="428">428</span> +<span id="429">429</span> +<span id="430">430</span> +<span id="431">431</span> +<span id="432">432</span> +<span id="433">433</span> +<span id="434">434</span> +<span id="435">435</span> +<span id="436">436</span> +<span id="437">437</span> +<span id="438">438</span> +<span id="439">439</span> +<span id="440">440</span> +<span id="441">441</span> +<span id="442">442</span> +<span id="443">443</span> +<span id="444">444</span> +<span id="445">445</span> +<span id="446">446</span> +<span id="447">447</span> +<span id="448">448</span> +<span id="449">449</span> +<span id="450">450</span> +<span id="451">451</span> +<span id="452">452</span> +<span id="453">453</span> +<span id="454">454</span> +<span id="455">455</span> +<span id="456">456</span> +<span id="457">457</span> +<span id="458">458</span> +<span id="459">459</span> +<span id="460">460</span> +<span id="461">461</span> +<span id="462">462</span> +<span id="463">463</span> +<span id="464">464</span> +<span id="465">465</span> +<span id="466">466</span> +<span id="467">467</span> +<span id="468">468</span> +<span id="469">469</span> +<span id="470">470</span> +<span id="471">471</span> +<span id="472">472</span> +<span id="473">473</span> +<span id="474">474</span> +<span id="475">475</span> +<span id="476">476</span> +<span id="477">477</span> +<span id="478">478</span> +<span id="479">479</span> +<span id="480">480</span> +<span id="481">481</span> +<span id="482">482</span> +<span id="483">483</span> +<span id="484">484</span> +<span id="485">485</span> +<span id="486">486</span> +<span id="487">487</span> +<span id="488">488</span> +<span id="489">489</span> +<span id="490">490</span> +<span id="491">491</span> +<span id="492">492</span> +<span id="493">493</span> +<span id="494">494</span> +<span id="495">495</span> +<span id="496">496</span> +<span id="497">497</span> +<span id="498">498</span> +<span id="499">499</span> +<span id="500">500</span> +<span id="501">501</span> +<span id="502">502</span> +<span id="503">503</span> +<span id="504">504</span> +<span id="505">505</span> +<span id="506">506</span> +<span id="507">507</span> +<span id="508">508</span> +<span id="509">509</span> +<span id="510">510</span> +<span id="511">511</span> +<span id="512">512</span> +<span id="513">513</span> +<span id="514">514</span> +<span id="515">515</span> +<span id="516">516</span> +<span id="517">517</span> +<span id="518">518</span> +<span id="519">519</span> +<span id="520">520</span> +<span id="521">521</span> +<span id="522">522</span> +<span id="523">523</span> +<span id="524">524</span> +<span id="525">525</span> +<span id="526">526</span> +<span id="527">527</span> +<span id="528">528</span> +<span id="529">529</span> +<span id="530">530</span> +<span id="531">531</span> +<span id="532">532</span> +<span id="533">533</span> +<span id="534">534</span> +<span id="535">535</span> +<span id="536">536</span> +<span id="537">537</span> +<span id="538">538</span> +<span id="539">539</span> +<span id="540">540</span> +<span id="541">541</span> +<span id="542">542</span> +<span id="543">543</span> +<span id="544">544</span> +<span id="545">545</span> +<span id="546">546</span> +<span id="547">547</span> +<span id="548">548</span> +<span id="549">549</span> +<span id="550">550</span> +<span id="551">551</span> +<span id="552">552</span> +<span id="553">553</span> +<span id="554">554</span> +<span id="555">555</span> +<span id="556">556</span> +<span id="557">557</span> +<span id="558">558</span> +<span id="559">559</span> +<span id="560">560</span> +<span id="561">561</span> +<span id="562">562</span> +<span id="563">563</span> +<span id="564">564</span> +<span id="565">565</span> +<span id="566">566</span> +<span id="567">567</span> +<span id="568">568</span> +<span id="569">569</span> +<span id="570">570</span> +<span id="571">571</span> +<span id="572">572</span> +<span id="573">573</span> +<span id="574">574</span> +<span id="575">575</span> +<span id="576">576</span> +<span id="577">577</span> +<span id="578">578</span> +<span id="579">579</span> +<span id="580">580</span> +<span id="581">581</span> +<span id="582">582</span> +<span id="583">583</span> +<span id="584">584</span> +<span id="585">585</span> +<span id="586">586</span> +<span id="587">587</span> +<span id="588">588</span> +<span id="589">589</span> +<span id="590">590</span> +<span id="591">591</span> +<span id="592">592</span> +<span id="593">593</span> +<span id="594">594</span> +<span id="595">595</span> +<span id="596">596</span> +<span id="597">597</span> +<span id="598">598</span> +<span id="599">599</span> +<span id="600">600</span> +<span id="601">601</span> +<span id="602">602</span> +<span id="603">603</span> +<span id="604">604</span> +<span id="605">605</span> +<span id="606">606</span> +<span id="607">607</span> +<span id="608">608</span> +<span id="609">609</span> +<span id="610">610</span> +<span id="611">611</span> +<span id="612">612</span> +<span id="613">613</span> +<span id="614">614</span> +<span id="615">615</span> +<span id="616">616</span> +<span id="617">617</span> +<span id="618">618</span> +<span id="619">619</span> +<span id="620">620</span> +<span id="621">621</span> +<span id="622">622</span> +<span id="623">623</span> +<span id="624">624</span> +<span id="625">625</span> +<span id="626">626</span> +<span id="627">627</span> +<span id="628">628</span> +<span id="629">629</span> +<span id="630">630</span> +<span id="631">631</span> +<span id="632">632</span> +<span id="633">633</span> +<span id="634">634</span> +<span id="635">635</span> +<span id="636">636</span> +<span id="637">637</span> +<span id="638">638</span> +<span id="639">639</span> +<span id="640">640</span> +<span id="641">641</span> +<span id="642">642</span> +<span id="643">643</span> +<span id="644">644</span> +<span id="645">645</span> +<span id="646">646</span> +<span id="647">647</span> +<span id="648">648</span> +<span id="649">649</span> +<span id="650">650</span> +<span id="651">651</span> +<span id="652">652</span> +<span id="653">653</span> +<span id="654">654</span> +<span id="655">655</span> +<span id="656">656</span> +<span id="657">657</span> +<span id="658">658</span> +<span id="659">659</span> +<span id="660">660</span> +<span id="661">661</span> +<span id="662">662</span> +<span id="663">663</span> +<span id="664">664</span> +<span id="665">665</span> +<span id="666">666</span> +<span id="667">667</span> +<span id="668">668</span> +<span id="669">669</span> +<span id="670">670</span> +<span id="671">671</span> +<span id="672">672</span> +<span id="673">673</span> +<span id="674">674</span> +<span id="675">675</span> +<span id="676">676</span> +<span id="677">677</span> +<span id="678">678</span> +<span id="679">679</span> +<span id="680">680</span> +<span id="681">681</span> +<span id="682">682</span> +<span id="683">683</span> +<span id="684">684</span> +<span id="685">685</span> +<span id="686">686</span> +<span id="687">687</span> +<span id="688">688</span> +<span id="689">689</span> +<span id="690">690</span> +<span id="691">691</span> +<span id="692">692</span> +<span id="693">693</span> +<span id="694">694</span> +<span id="695">695</span> +<span id="696">696</span> +<span id="697">697</span> +<span id="698">698</span> +<span id="699">699</span> +<span id="700">700</span> +<span id="701">701</span> +<span id="702">702</span> +<span id="703">703</span> +<span id="704">704</span> +<span id="705">705</span> +<span id="706">706</span> +<span id="707">707</span> +<span id="708">708</span> +<span id="709">709</span> +<span id="710">710</span> +<span id="711">711</span> +<span id="712">712</span> +<span id="713">713</span> +<span id="714">714</span> +<span id="715">715</span> +<span id="716">716</span> +<span id="717">717</span> +<span id="718">718</span> +<span id="719">719</span> +<span id="720">720</span> +<span id="721">721</span> +<span id="722">722</span> +<span id="723">723</span> +<span id="724">724</span> +<span id="725">725</span> +<span id="726">726</span> +<span id="727">727</span> +<span id="728">728</span> +<span id="729">729</span> +<span id="730">730</span> +<span id="731">731</span> +<span id="732">732</span> +<span id="733">733</span> +<span id="734">734</span> +<span id="735">735</span> +<span id="736">736</span> +<span id="737">737</span> +<span id="738">738</span> +<span id="739">739</span> +<span id="740">740</span> +<span id="741">741</span> +<span id="742">742</span> +<span id="743">743</span> +<span id="744">744</span> +<span id="745">745</span> +<span id="746">746</span> +<span id="747">747</span> +<span id="748">748</span> +<span id="749">749</span> +<span id="750">750</span> +<span id="751">751</span> +<span id="752">752</span> +<span id="753">753</span> +<span id="754">754</span> +<span id="755">755</span> +<span id="756">756</span> +<span id="757">757</span> +<span id="758">758</span> +<span id="759">759</span> +<span id="760">760</span> +<span id="761">761</span> +<span id="762">762</span> +<span id="763">763</span> +<span id="764">764</span> +<span id="765">765</span> +<span id="766">766</span> +<span id="767">767</span> +<span id="768">768</span> +<span id="769">769</span> +<span id="770">770</span> +<span id="771">771</span> +<span id="772">772</span> +<span id="773">773</span> +<span id="774">774</span> +<span id="775">775</span> +<span id="776">776</span> +<span id="777">777</span> +<span id="778">778</span> +<span id="779">779</span> +<span id="780">780</span> +<span id="781">781</span> +<span id="782">782</span> +<span id="783">783</span> +<span id="784">784</span> +<span id="785">785</span> +<span id="786">786</span> +<span id="787">787</span> +<span id="788">788</span> +<span id="789">789</span> +<span id="790">790</span> +<span id="791">791</span> +<span id="792">792</span> +<span id="793">793</span> +<span id="794">794</span> +<span id="795">795</span> +<span id="796">796</span> +<span id="797">797</span> +<span id="798">798</span> +<span id="799">799</span> +<span id="800">800</span> +<span id="801">801</span> +<span id="802">802</span> +<span id="803">803</span> +<span id="804">804</span> +<span id="805">805</span> +<span id="806">806</span> +<span id="807">807</span> +<span id="808">808</span> +<span id="809">809</span> +<span id="810">810</span> +<span id="811">811</span> +<span id="812">812</span> +<span id="813">813</span> +<span id="814">814</span> +<span id="815">815</span> +<span id="816">816</span> +<span id="817">817</span> +<span id="818">818</span> +<span id="819">819</span> +<span id="820">820</span> +<span id="821">821</span> +<span id="822">822</span> +<span id="823">823</span> +<span id="824">824</span> +<span id="825">825</span> +<span id="826">826</span> +<span id="827">827</span> +<span id="828">828</span> +<span id="829">829</span> +<span id="830">830</span> +<span id="831">831</span> +<span id="832">832</span> +<span id="833">833</span> +<span id="834">834</span> +<span id="835">835</span> +<span id="836">836</span> +<span id="837">837</span> +<span id="838">838</span> +<span id="839">839</span> +<span id="840">840</span> +<span id="841">841</span> +<span id="842">842</span> +<span id="843">843</span> +<span id="844">844</span> +<span id="845">845</span> +<span id="846">846</span> +<span id="847">847</span> +<span id="848">848</span> +<span id="849">849</span> +<span id="850">850</span> +<span id="851">851</span> +<span id="852">852</span> +<span id="853">853</span> +<span id="854">854</span> +<span id="855">855</span> +<span id="856">856</span> +<span id="857">857</span> +<span id="858">858</span> +<span id="859">859</span> +<span id="860">860</span> +<span id="861">861</span> +<span id="862">862</span> +<span id="863">863</span> +<span id="864">864</span> +<span id="865">865</span> +<span id="866">866</span> +<span id="867">867</span> +<span id="868">868</span> +<span id="869">869</span> +<span id="870">870</span> +<span id="871">871</span> +<span id="872">872</span> +<span id="873">873</span> +<span id="874">874</span> +<span id="875">875</span> +<span id="876">876</span> +<span id="877">877</span> +<span id="878">878</span> +<span id="879">879</span> +<span id="880">880</span> +<span id="881">881</span> +<span id="882">882</span> +<span id="883">883</span> +<span id="884">884</span> +<span id="885">885</span> +<span id="886">886</span> +<span id="887">887</span> +<span id="888">888</span> +<span id="889">889</span> +<span id="890">890</span> +<span id="891">891</span> +<span id="892">892</span> +<span id="893">893</span> +<span id="894">894</span> +<span id="895">895</span> +<span id="896">896</span> +<span id="897">897</span> +<span id="898">898</span> +<span id="899">899</span> +<span id="900">900</span> +<span id="901">901</span> +<span id="902">902</span> +<span id="903">903</span> +<span id="904">904</span> +<span id="905">905</span> +<span id="906">906</span> +<span id="907">907</span> +<span id="908">908</span> +<span id="909">909</span> +<span id="910">910</span> +<span id="911">911</span> +<span id="912">912</span> +<span id="913">913</span> +<span id="914">914</span> +<span id="915">915</span> +<span id="916">916</span> +<span id="917">917</span> +<span id="918">918</span> +<span id="919">919</span> +<span id="920">920</span> +<span id="921">921</span> +<span id="922">922</span> +<span id="923">923</span> +<span id="924">924</span> +<span id="925">925</span> +<span id="926">926</span> +<span id="927">927</span> +<span id="928">928</span> +<span id="929">929</span> +<span id="930">930</span> +<span id="931">931</span> +<span id="932">932</span> +<span id="933">933</span> +<span id="934">934</span> +<span id="935">935</span> +<span id="936">936</span> +<span id="937">937</span> +<span id="938">938</span> +<span id="939">939</span> +<span id="940">940</span> +<span id="941">941</span> +<span id="942">942</span> +<span id="943">943</span> +<span id="944">944</span> +<span id="945">945</span> +<span id="946">946</span> +<span id="947">947</span> +<span id="948">948</span> +<span id="949">949</span> +<span id="950">950</span> +<span id="951">951</span> +<span id="952">952</span> +<span id="953">953</span> +<span id="954">954</span> +<span id="955">955</span> +<span id="956">956</span> +<span id="957">957</span> +<span id="958">958</span> +<span id="959">959</span> +<span id="960">960</span> +<span id="961">961</span> +<span id="962">962</span> +<span id="963">963</span> +<span id="964">964</span> +<span id="965">965</span> +<span id="966">966</span> +<span id="967">967</span> +<span id="968">968</span> +<span id="969">969</span> +<span id="970">970</span> +<span id="971">971</span> +<span id="972">972</span> +<span id="973">973</span> +<span id="974">974</span> +<span id="975">975</span> +<span id="976">976</span> +<span id="977">977</span> +<span id="978">978</span> +<span id="979">979</span> +<span id="980">980</span> +<span id="981">981</span> +<span id="982">982</span> +<span id="983">983</span> +<span id="984">984</span> +<span id="985">985</span> +<span id="986">986</span> +<span id="987">987</span> +<span id="988">988</span> +<span id="989">989</span> +<span id="990">990</span> +<span id="991">991</span> +<span id="992">992</span> +<span id="993">993</span> +<span id="994">994</span> +<span id="995">995</span> +<span id="996">996</span> +<span id="997">997</span> +<span id="998">998</span> +<span id="999">999</span> +<span id="1000">1000</span> +<span id="1001">1001</span> +<span id="1002">1002</span> +<span id="1003">1003</span> +<span id="1004">1004</span> +<span id="1005">1005</span> +<span id="1006">1006</span> +<span id="1007">1007</span> +<span id="1008">1008</span> +<span id="1009">1009</span> +<span id="1010">1010</span> +<span id="1011">1011</span> +<span id="1012">1012</span> +<span id="1013">1013</span> +<span id="1014">1014</span> +<span id="1015">1015</span> +<span id="1016">1016</span> +<span id="1017">1017</span> +<span id="1018">1018</span> +<span id="1019">1019</span> +<span id="1020">1020</span> +<span id="1021">1021</span> +<span id="1022">1022</span> +<span id="1023">1023</span> +<span id="1024">1024</span> +<span id="1025">1025</span> +<span id="1026">1026</span> +<span id="1027">1027</span> +<span id="1028">1028</span> +<span id="1029">1029</span> +<span id="1030">1030</span> +<span id="1031">1031</span> +<span id="1032">1032</span> +<span id="1033">1033</span> +<span id="1034">1034</span> +<span id="1035">1035</span> +<span id="1036">1036</span> +<span id="1037">1037</span> +<span id="1038">1038</span> +<span id="1039">1039</span> +<span id="1040">1040</span> +<span id="1041">1041</span> +<span id="1042">1042</span> +<span id="1043">1043</span> +<span id="1044">1044</span> +<span id="1045">1045</span> +<span id="1046">1046</span> +<span id="1047">1047</span> +<span id="1048">1048</span> +<span id="1049">1049</span> +<span id="1050">1050</span> +<span id="1051">1051</span> +<span id="1052">1052</span> +<span id="1053">1053</span> +<span id="1054">1054</span> +<span id="1055">1055</span> +<span id="1056">1056</span> +<span id="1057">1057</span> +<span id="1058">1058</span> +<span id="1059">1059</span> +<span id="1060">1060</span> +<span id="1061">1061</span> +<span id="1062">1062</span> +<span id="1063">1063</span> +<span id="1064">1064</span> +<span id="1065">1065</span> +<span id="1066">1066</span> +<span id="1067">1067</span> +<span id="1068">1068</span> +<span id="1069">1069</span> +<span id="1070">1070</span> +<span id="1071">1071</span> +<span id="1072">1072</span> +<span id="1073">1073</span> +<span id="1074">1074</span> +<span id="1075">1075</span> +<span id="1076">1076</span> +<span id="1077">1077</span> +<span id="1078">1078</span> +<span id="1079">1079</span> +<span id="1080">1080</span> +<span id="1081">1081</span> +<span id="1082">1082</span> +<span id="1083">1083</span> +<span id="1084">1084</span> +<span id="1085">1085</span> +<span id="1086">1086</span> +<span id="1087">1087</span> +<span id="1088">1088</span> +<span id="1089">1089</span> +<span id="1090">1090</span> +<span id="1091">1091</span> +<span id="1092">1092</span> +<span id="1093">1093</span> +<span id="1094">1094</span> +<span id="1095">1095</span> +<span id="1096">1096</span> +<span id="1097">1097</span> +<span id="1098">1098</span> +<span id="1099">1099</span> +<span id="1100">1100</span> +<span id="1101">1101</span> +<span id="1102">1102</span> +<span id="1103">1103</span> +<span id="1104">1104</span> +<span id="1105">1105</span> +<span id="1106">1106</span> +<span id="1107">1107</span> +<span id="1108">1108</span> +<span id="1109">1109</span> +<span id="1110">1110</span> +<span id="1111">1111</span> +<span id="1112">1112</span> +<span id="1113">1113</span> +<span id="1114">1114</span> +<span id="1115">1115</span> +<span id="1116">1116</span> +<span id="1117">1117</span> +<span id="1118">1118</span> +<span id="1119">1119</span> +<span id="1120">1120</span> +<span id="1121">1121</span> +<span id="1122">1122</span> +<span id="1123">1123</span> +<span id="1124">1124</span> +<span id="1125">1125</span> +<span id="1126">1126</span> +<span id="1127">1127</span> +<span id="1128">1128</span> +<span id="1129">1129</span> +<span id="1130">1130</span> +<span id="1131">1131</span> +<span id="1132">1132</span> +<span id="1133">1133</span> +<span id="1134">1134</span> +<span id="1135">1135</span> +<span id="1136">1136</span> +<span id="1137">1137</span> +<span id="1138">1138</span> +<span id="1139">1139</span> +<span id="1140">1140</span> +<span id="1141">1141</span> +<span id="1142">1142</span> +<span id="1143">1143</span> +<span id="1144">1144</span> +<span id="1145">1145</span> +<span id="1146">1146</span> +<span id="1147">1147</span> +<span id="1148">1148</span> +<span id="1149">1149</span> +<span id="1150">1150</span> +<span id="1151">1151</span> +<span id="1152">1152</span> +<span id="1153">1153</span> +<span id="1154">1154</span> +<span id="1155">1155</span> +<span id="1156">1156</span> +<span id="1157">1157</span> +<span id="1158">1158</span> +<span id="1159">1159</span> +<span id="1160">1160</span> +<span id="1161">1161</span> +<span id="1162">1162</span> +<span id="1163">1163</span> +<span id="1164">1164</span> +<span id="1165">1165</span> +<span id="1166">1166</span> +<span id="1167">1167</span> +<span id="1168">1168</span> +<span id="1169">1169</span> +<span id="1170">1170</span> +<span id="1171">1171</span> +<span id="1172">1172</span> +<span id="1173">1173</span> +<span id="1174">1174</span> +<span id="1175">1175</span> +<span id="1176">1176</span> +<span id="1177">1177</span> +<span id="1178">1178</span> +<span id="1179">1179</span> +<span id="1180">1180</span> +<span id="1181">1181</span> +<span id="1182">1182</span> +<span id="1183">1183</span> +<span id="1184">1184</span> +<span id="1185">1185</span> +<span id="1186">1186</span> +<span id="1187">1187</span> +<span id="1188">1188</span> +<span id="1189">1189</span> +<span id="1190">1190</span> +<span id="1191">1191</span> +<span id="1192">1192</span> +<span id="1193">1193</span> +<span id="1194">1194</span> +<span id="1195">1195</span> +<span id="1196">1196</span> +<span id="1197">1197</span> +<span id="1198">1198</span> +<span id="1199">1199</span> +<span id="1200">1200</span> +<span id="1201">1201</span> +<span id="1202">1202</span> +<span id="1203">1203</span> +<span id="1204">1204</span> +<span id="1205">1205</span> +<span id="1206">1206</span> +<span id="1207">1207</span> +<span id="1208">1208</span> +<span id="1209">1209</span> +<span id="1210">1210</span> +<span id="1211">1211</span> +<span id="1212">1212</span> +<span id="1213">1213</span> +<span id="1214">1214</span> +<span id="1215">1215</span> +<span id="1216">1216</span> +<span id="1217">1217</span> +<span id="1218">1218</span> +<span id="1219">1219</span> +<span id="1220">1220</span> +<span id="1221">1221</span> +<span id="1222">1222</span> +<span id="1223">1223</span> +<span id="1224">1224</span> +<span id="1225">1225</span> +<span id="1226">1226</span> +<span id="1227">1227</span> +<span id="1228">1228</span> +<span id="1229">1229</span> +<span id="1230">1230</span> +<span id="1231">1231</span> +<span id="1232">1232</span> +<span id="1233">1233</span> +<span id="1234">1234</span> +<span id="1235">1235</span> +<span id="1236">1236</span> +<span id="1237">1237</span> +<span id="1238">1238</span> +<span id="1239">1239</span> +<span id="1240">1240</span> +<span id="1241">1241</span> +<span id="1242">1242</span> +<span id="1243">1243</span> +<span id="1244">1244</span> +<span id="1245">1245</span> +<span id="1246">1246</span> +<span id="1247">1247</span> +<span id="1248">1248</span> +<span id="1249">1249</span> +<span id="1250">1250</span> +<span id="1251">1251</span> +<span id="1252">1252</span> +<span id="1253">1253</span> +<span id="1254">1254</span> +<span id="1255">1255</span> +<span id="1256">1256</span> +<span id="1257">1257</span> +<span id="1258">1258</span> +<span id="1259">1259</span> +<span id="1260">1260</span> +<span id="1261">1261</span> +<span id="1262">1262</span> +<span id="1263">1263</span> +<span id="1264">1264</span> +<span id="1265">1265</span> +<span id="1266">1266</span> +<span id="1267">1267</span> +<span id="1268">1268</span> +<span id="1269">1269</span> +<span id="1270">1270</span> +<span id="1271">1271</span> +<span id="1272">1272</span> +<span id="1273">1273</span> +<span id="1274">1274</span> +<span id="1275">1275</span> +<span id="1276">1276</span> +<span id="1277">1277</span> +<span id="1278">1278</span> +<span id="1279">1279</span> +<span id="1280">1280</span> +<span id="1281">1281</span> +<span id="1282">1282</span> +<span id="1283">1283</span> +<span id="1284">1284</span> +<span id="1285">1285</span> +<span id="1286">1286</span> +<span id="1287">1287</span> +<span id="1288">1288</span> +<span id="1289">1289</span> +<span id="1290">1290</span> +<span id="1291">1291</span> +<span id="1292">1292</span> +<span id="1293">1293</span> +<span id="1294">1294</span> +<span id="1295">1295</span> +<span id="1296">1296</span> +<span id="1297">1297</span> +<span id="1298">1298</span> +<span id="1299">1299</span> +<span id="1300">1300</span> +<span id="1301">1301</span> +<span id="1302">1302</span> +<span id="1303">1303</span> +<span id="1304">1304</span> +<span id="1305">1305</span> +<span id="1306">1306</span> +<span id="1307">1307</span> +<span id="1308">1308</span> +<span id="1309">1309</span> +<span id="1310">1310</span> +<span id="1311">1311</span> +<span id="1312">1312</span> +<span id="1313">1313</span> +<span id="1314">1314</span> +<span id="1315">1315</span> +<span id="1316">1316</span> +<span id="1317">1317</span> +<span id="1318">1318</span> +<span id="1319">1319</span> +<span id="1320">1320</span> +<span id="1321">1321</span> +<span id="1322">1322</span> +<span id="1323">1323</span> +<span id="1324">1324</span> +<span id="1325">1325</span> +<span id="1326">1326</span> +<span id="1327">1327</span> +<span id="1328">1328</span> +<span id="1329">1329</span> +<span id="1330">1330</span> +<span id="1331">1331</span> +<span id="1332">1332</span> +<span id="1333">1333</span> +<span id="1334">1334</span> +<span id="1335">1335</span> +<span id="1336">1336</span> +<span id="1337">1337</span> +<span id="1338">1338</span> +<span id="1339">1339</span> +<span id="1340">1340</span> +<span id="1341">1341</span> +<span id="1342">1342</span> +<span id="1343">1343</span> +<span id="1344">1344</span> +<span id="1345">1345</span> +<span id="1346">1346</span> +<span id="1347">1347</span> +<span id="1348">1348</span> +<span id="1349">1349</span> +<span id="1350">1350</span> +<span id="1351">1351</span> +<span id="1352">1352</span> +<span id="1353">1353</span> +<span id="1354">1354</span> +<span id="1355">1355</span> +<span id="1356">1356</span> +</pre><pre class="rust"><code><span class="comment">// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +</span><span class="doccomment">//! Sequence-related functionality +//! +//! This module provides: +//! +//! * [`SliceRandom`] slice sampling and mutation +//! * [`IteratorRandom`] iterator sampling +//! * [`index::sample`] low-level API to choose multiple indices from +//! `0..length` +//! +//! Also see: +//! +//! * [`crate::distributions::WeightedIndex`] distribution which provides +//! weighted index sampling. +//! +//! In order to make results reproducible across 32-64 bit architectures, all +//! `usize` indices are sampled as a `u32` where possible (also providing a +//! small performance boost in some cases). + + +</span><span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] +#[cfg_attr(doc_cfg, doc(cfg(feature = <span class="string">"alloc"</span>)))] +</span><span class="kw">pub mod </span>index; + +<span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] </span><span class="kw">use </span>core::ops::Index; + +<span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] </span><span class="kw">use </span>alloc::vec::Vec; + +<span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] +</span><span class="kw">use </span><span class="kw">crate</span>::distributions::uniform::{SampleBorrow, SampleUniform}; +<span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] </span><span class="kw">use </span><span class="kw">crate</span>::distributions::WeightedError; +<span class="kw">use </span><span class="kw">crate</span>::Rng; + +<span class="doccomment">/// Extension trait on slices, providing random mutation and sampling methods. +/// +/// This trait is implemented on all `[T]` slice types, providing several +/// methods for choosing and shuffling elements. You must `use` this trait: +/// +/// ``` +/// use rand::seq::SliceRandom; +/// +/// let mut rng = rand::thread_rng(); +/// let mut bytes = "Hello, random!".to_string().into_bytes(); +/// bytes.shuffle(&mut rng); +/// let str = String::from_utf8(bytes).unwrap(); +/// println!("{}", str); +/// ``` +/// Example output (non-deterministic): +/// ```none +/// l,nmroHado !le +/// ``` +</span><span class="kw">pub trait </span>SliceRandom { + <span class="doccomment">/// The element type. + </span><span class="kw">type </span>Item; + + <span class="doccomment">/// Returns a reference to one random element of the slice, or `None` if the + /// slice is empty. + /// + /// For slices, complexity is `O(1)`. + /// + /// # Example + /// + /// ``` + /// use rand::thread_rng; + /// use rand::seq::SliceRandom; + /// + /// let choices = [1, 2, 4, 8, 16, 32]; + /// let mut rng = thread_rng(); + /// println!("{:?}", choices.choose(&mut rng)); + /// assert_eq!(choices[..0].choose(&mut rng), None); + /// ``` + </span><span class="kw">fn </span>choose<R>(<span class="kw-2">&</span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R) -> <span class="prelude-ty">Option</span><<span class="kw-2">&</span><span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized; + + <span class="doccomment">/// Returns a mutable reference to one random element of the slice, or + /// `None` if the slice is empty. + /// + /// For slices, complexity is `O(1)`. + </span><span class="kw">fn </span>choose_mut<R>(<span class="kw-2">&mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R) -> <span class="prelude-ty">Option</span><<span class="kw-2">&mut </span><span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized; + + <span class="doccomment">/// Chooses `amount` elements from the slice at random, without repetition, + /// and in random order. The returned iterator is appropriate both for + /// collection into a `Vec` and filling an existing buffer (see example). + /// + /// In case this API is not sufficiently flexible, use [`index::sample`]. + /// + /// For slices, complexity is the same as [`index::sample`]. + /// + /// # Example + /// ``` + /// use rand::seq::SliceRandom; + /// + /// let mut rng = &mut rand::thread_rng(); + /// let sample = "Hello, audience!".as_bytes(); + /// + /// // collect the results into a vector: + /// let v: Vec<u8> = sample.choose_multiple(&mut rng, 3).cloned().collect(); + /// + /// // store in a buffer: + /// let mut buf = [0u8; 5]; + /// for (b, slot) in sample.choose_multiple(&mut rng, buf.len()).zip(buf.iter_mut()) { + /// *slot = *b; + /// } + /// ``` + </span><span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + #[cfg_attr(doc_cfg, doc(cfg(feature = <span class="string">"alloc"</span>)))] + </span><span class="kw">fn </span>choose_multiple<R>(<span class="kw-2">&</span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, amount: usize) -> SliceChooseIter<<span class="self">Self</span>, <span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized; + + <span class="doccomment">/// Similar to [`choose`], but where the likelihood of each outcome may be + /// specified. + /// + /// The specified function `weight` maps each item `x` to a relative + /// likelihood `weight(x)`. The probability of each item being selected is + /// therefore `weight(x) / s`, where `s` is the sum of all `weight(x)`. + /// + /// For slices of length `n`, complexity is `O(n)`. + /// See also [`choose_weighted_mut`], [`distributions::weighted`]. + /// + /// # Example + /// + /// ``` + /// use rand::prelude::*; + /// + /// let choices = [('a', 2), ('b', 1), ('c', 1)]; + /// let mut rng = thread_rng(); + /// // 50% chance to print 'a', 25% chance to print 'b', 25% chance to print 'c' + /// println!("{:?}", choices.choose_weighted(&mut rng, |item| item.1).unwrap().0); + /// ``` + /// [`choose`]: SliceRandom::choose + /// [`choose_weighted_mut`]: SliceRandom::choose_weighted_mut + /// [`distributions::weighted`]: crate::distributions::weighted + </span><span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + #[cfg_attr(doc_cfg, doc(cfg(feature = <span class="string">"alloc"</span>)))] + </span><span class="kw">fn </span>choose_weighted<R, F, B, X>( + <span class="kw-2">&</span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, weight: F, + ) -> <span class="prelude-ty">Result</span><<span class="kw-2">&</span><span class="self">Self</span>::Item, WeightedError> + <span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + F: Fn(<span class="kw-2">&</span><span class="self">Self</span>::Item) -> B, + B: SampleBorrow<X>, + X: SampleUniform + + <span class="kw">for</span><<span class="lifetime">'a</span>> ::core::ops::AddAssign<<span class="kw-2">&</span><span class="lifetime">'a </span>X> + + ::core::cmp::PartialOrd<X> + + Clone + + Default; + + <span class="doccomment">/// Similar to [`choose_mut`], but where the likelihood of each outcome may + /// be specified. + /// + /// The specified function `weight` maps each item `x` to a relative + /// likelihood `weight(x)`. The probability of each item being selected is + /// therefore `weight(x) / s`, where `s` is the sum of all `weight(x)`. + /// + /// For slices of length `n`, complexity is `O(n)`. + /// See also [`choose_weighted`], [`distributions::weighted`]. + /// + /// [`choose_mut`]: SliceRandom::choose_mut + /// [`choose_weighted`]: SliceRandom::choose_weighted + /// [`distributions::weighted`]: crate::distributions::weighted + </span><span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + #[cfg_attr(doc_cfg, doc(cfg(feature = <span class="string">"alloc"</span>)))] + </span><span class="kw">fn </span>choose_weighted_mut<R, F, B, X>( + <span class="kw-2">&mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, weight: F, + ) -> <span class="prelude-ty">Result</span><<span class="kw-2">&mut </span><span class="self">Self</span>::Item, WeightedError> + <span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + F: Fn(<span class="kw-2">&</span><span class="self">Self</span>::Item) -> B, + B: SampleBorrow<X>, + X: SampleUniform + + <span class="kw">for</span><<span class="lifetime">'a</span>> ::core::ops::AddAssign<<span class="kw-2">&</span><span class="lifetime">'a </span>X> + + ::core::cmp::PartialOrd<X> + + Clone + + Default; + + <span class="doccomment">/// Similar to [`choose_multiple`], but where the likelihood of each element's + /// inclusion in the output may be specified. The elements are returned in an + /// arbitrary, unspecified order. + /// + /// The specified function `weight` maps each item `x` to a relative + /// likelihood `weight(x)`. The probability of each item being selected is + /// therefore `weight(x) / s`, where `s` is the sum of all `weight(x)`. + /// + /// If all of the weights are equal, even if they are all zero, each element has + /// an equal likelihood of being selected. + /// + /// The complexity of this method depends on the feature `partition_at_index`. + /// If the feature is enabled, then for slices of length `n`, the complexity + /// is `O(n)` space and `O(n)` time. Otherwise, the complexity is `O(n)` space and + /// `O(n * log amount)` time. + /// + /// # Example + /// + /// ``` + /// use rand::prelude::*; + /// + /// let choices = [('a', 2), ('b', 1), ('c', 1)]; + /// let mut rng = thread_rng(); + /// // First Draw * Second Draw = total odds + /// // ----------------------- + /// // (50% * 50%) + (25% * 67%) = 41.7% chance that the output is `['a', 'b']` in some order. + /// // (50% * 50%) + (25% * 67%) = 41.7% chance that the output is `['a', 'c']` in some order. + /// // (25% * 33%) + (25% * 33%) = 16.6% chance that the output is `['b', 'c']` in some order. + /// println!("{:?}", choices.choose_multiple_weighted(&mut rng, 2, |item| item.1).unwrap().collect::<Vec<_>>()); + /// ``` + /// [`choose_multiple`]: SliceRandom::choose_multiple + </span><span class="comment">// + // Note: this is feature-gated on std due to usage of f64::powf. + // If necessary, we may use alloc+libm as an alternative (see PR #1089). + </span><span class="attribute">#[cfg(feature = <span class="string">"std"</span>)] + #[cfg_attr(doc_cfg, doc(cfg(feature = <span class="string">"std"</span>)))] + </span><span class="kw">fn </span>choose_multiple_weighted<R, F, X>( + <span class="kw-2">&</span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, amount: usize, weight: F, + ) -> <span class="prelude-ty">Result</span><SliceChooseIter<<span class="self">Self</span>, <span class="self">Self</span>::Item>, WeightedError> + <span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + F: Fn(<span class="kw-2">&</span><span class="self">Self</span>::Item) -> X, + X: Into<f64>; + + <span class="doccomment">/// Shuffle a mutable slice in place. + /// + /// For slices of length `n`, complexity is `O(n)`. + /// + /// # Example + /// + /// ``` + /// use rand::seq::SliceRandom; + /// use rand::thread_rng; + /// + /// let mut rng = thread_rng(); + /// let mut y = [1, 2, 3, 4, 5]; + /// println!("Unshuffled: {:?}", y); + /// y.shuffle(&mut rng); + /// println!("Shuffled: {:?}", y); + /// ``` + </span><span class="kw">fn </span>shuffle<R>(<span class="kw-2">&mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R) + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized; + + <span class="doccomment">/// Shuffle a slice in place, but exit early. + /// + /// Returns two mutable slices from the source slice. The first contains + /// `amount` elements randomly permuted. The second has the remaining + /// elements that are not fully shuffled. + /// + /// This is an efficient method to select `amount` elements at random from + /// the slice, provided the slice may be mutated. + /// + /// If you only need to choose elements randomly and `amount > self.len()/2` + /// then you may improve performance by taking + /// `amount = values.len() - amount` and using only the second slice. + /// + /// If `amount` is greater than the number of elements in the slice, this + /// will perform a full shuffle. + /// + /// For slices, complexity is `O(m)` where `m = amount`. + </span><span class="kw">fn </span>partial_shuffle<R>( + <span class="kw-2">&mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, amount: usize, + ) -> (<span class="kw-2">&mut </span>[<span class="self">Self</span>::Item], <span class="kw-2">&mut </span>[<span class="self">Self</span>::Item]) + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized; +} + +<span class="doccomment">/// Extension trait on iterators, providing random sampling methods. +/// +/// This trait is implemented on all iterators `I` where `I: Iterator + Sized` +/// and provides methods for +/// choosing one or more elements. You must `use` this trait: +/// +/// ``` +/// use rand::seq::IteratorRandom; +/// +/// let mut rng = rand::thread_rng(); +/// +/// let faces = "😀😎😐😕😠😢"; +/// println!("I am {}!", faces.chars().choose(&mut rng).unwrap()); +/// ``` +/// Example output (non-deterministic): +/// ```none +/// I am 😀! +/// ``` +</span><span class="kw">pub trait </span>IteratorRandom: Iterator + Sized { + <span class="doccomment">/// Choose one element at random from the iterator. + /// + /// Returns `None` if and only if the iterator is empty. + /// + /// This method uses [`Iterator::size_hint`] for optimisation. With an + /// accurate hint and where [`Iterator::nth`] is a constant-time operation + /// this method can offer `O(1)` performance. Where no size hint is + /// available, complexity is `O(n)` where `n` is the iterator length. + /// Partial hints (where `lower > 0`) also improve performance. + /// + /// Note that the output values and the number of RNG samples used + /// depends on size hints. In particular, `Iterator` combinators that don't + /// change the values yielded but change the size hints may result in + /// `choose` returning different elements. If you want consistent results + /// and RNG usage consider using [`IteratorRandom::choose_stable`]. + </span><span class="kw">fn </span>choose<R>(<span class="kw-2">mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R) -> <span class="prelude-ty">Option</span><<span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">let </span>(<span class="kw-2">mut </span>lower, <span class="kw-2">mut </span>upper) = <span class="self">self</span>.size_hint(); + <span class="kw">let </span><span class="kw-2">mut </span>consumed = <span class="number">0</span>; + <span class="kw">let </span><span class="kw-2">mut </span>result = <span class="prelude-val">None</span>; + + <span class="comment">// Handling for this condition outside the loop allows the optimizer to eliminate the loop + // when the Iterator is an ExactSizeIterator. This has a large performance impact on e.g. + // seq_iter_choose_from_1000. + </span><span class="kw">if </span>upper == <span class="prelude-val">Some</span>(lower) { + <span class="kw">return if </span>lower == <span class="number">0 </span>{ + <span class="prelude-val">None + </span>} <span class="kw">else </span>{ + <span class="self">self</span>.nth(gen_index(rng, lower)) + }; + } + + <span class="comment">// Continue until the iterator is exhausted + </span><span class="kw">loop </span>{ + <span class="kw">if </span>lower > <span class="number">1 </span>{ + <span class="kw">let </span>ix = gen_index(rng, lower + consumed); + <span class="kw">let </span>skip = <span class="kw">if </span>ix < lower { + result = <span class="self">self</span>.nth(ix); + lower - (ix + <span class="number">1</span>) + } <span class="kw">else </span>{ + lower + }; + <span class="kw">if </span>upper == <span class="prelude-val">Some</span>(lower) { + <span class="kw">return </span>result; + } + consumed += lower; + <span class="kw">if </span>skip > <span class="number">0 </span>{ + <span class="self">self</span>.nth(skip - <span class="number">1</span>); + } + } <span class="kw">else </span>{ + <span class="kw">let </span>elem = <span class="self">self</span>.next(); + <span class="kw">if </span>elem.is_none() { + <span class="kw">return </span>result; + } + consumed += <span class="number">1</span>; + <span class="kw">if </span>gen_index(rng, consumed) == <span class="number">0 </span>{ + result = elem; + } + } + + <span class="kw">let </span>hint = <span class="self">self</span>.size_hint(); + lower = hint.<span class="number">0</span>; + upper = hint.<span class="number">1</span>; + } + } + + <span class="doccomment">/// Choose one element at random from the iterator. + /// + /// Returns `None` if and only if the iterator is empty. + /// + /// This method is very similar to [`choose`] except that the result + /// only depends on the length of the iterator and the values produced by + /// `rng`. Notably for any iterator of a given length this will make the + /// same requests to `rng` and if the same sequence of values are produced + /// the same index will be selected from `self`. This may be useful if you + /// need consistent results no matter what type of iterator you are working + /// with. If you do not need this stability prefer [`choose`]. + /// + /// Note that this method still uses [`Iterator::size_hint`] to skip + /// constructing elements where possible, however the selection and `rng` + /// calls are the same in the face of this optimization. If you want to + /// force every element to be created regardless call `.inspect(|e| ())`. + /// + /// [`choose`]: IteratorRandom::choose + </span><span class="kw">fn </span>choose_stable<R>(<span class="kw-2">mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R) -> <span class="prelude-ty">Option</span><<span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">let </span><span class="kw-2">mut </span>consumed = <span class="number">0</span>; + <span class="kw">let </span><span class="kw-2">mut </span>result = <span class="prelude-val">None</span>; + + <span class="kw">loop </span>{ + <span class="comment">// Currently the only way to skip elements is `nth()`. So we need to + // store what index to access next here. + // This should be replaced by `advance_by()` once it is stable: + // https://github.com/rust-lang/rust/issues/77404 + </span><span class="kw">let </span><span class="kw-2">mut </span>next = <span class="number">0</span>; + + <span class="kw">let </span>(lower, <span class="kw">_</span>) = <span class="self">self</span>.size_hint(); + <span class="kw">if </span>lower >= <span class="number">2 </span>{ + <span class="kw">let </span>highest_selected = (<span class="number">0</span>..lower) + .filter(|ix| gen_index(rng, consumed+ix+<span class="number">1</span>) == <span class="number">0</span>) + .last(); + + consumed += lower; + next = lower; + + <span class="kw">if let </span><span class="prelude-val">Some</span>(ix) = highest_selected { + result = <span class="self">self</span>.nth(ix); + next -= ix + <span class="number">1</span>; + <span class="macro">debug_assert!</span>(result.is_some(), <span class="string">"iterator shorter than size_hint().0"</span>); + } + } + + <span class="kw">let </span>elem = <span class="self">self</span>.nth(next); + <span class="kw">if </span>elem.is_none() { + <span class="kw">return </span>result + } + + <span class="kw">if </span>gen_index(rng, consumed+<span class="number">1</span>) == <span class="number">0 </span>{ + result = elem; + } + consumed += <span class="number">1</span>; + } + } + + <span class="doccomment">/// Collects values at random from the iterator into a supplied buffer + /// until that buffer is filled. + /// + /// Although the elements are selected randomly, the order of elements in + /// the buffer is neither stable nor fully random. If random ordering is + /// desired, shuffle the result. + /// + /// Returns the number of elements added to the buffer. This equals the length + /// of the buffer unless the iterator contains insufficient elements, in which + /// case this equals the number of elements available. + /// + /// Complexity is `O(n)` where `n` is the length of the iterator. + /// For slices, prefer [`SliceRandom::choose_multiple`]. + </span><span class="kw">fn </span>choose_multiple_fill<R>(<span class="kw-2">mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, buf: <span class="kw-2">&mut </span>[<span class="self">Self</span>::Item]) -> usize + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">let </span>amount = buf.len(); + <span class="kw">let </span><span class="kw-2">mut </span>len = <span class="number">0</span>; + <span class="kw">while </span>len < amount { + <span class="kw">if let </span><span class="prelude-val">Some</span>(elem) = <span class="self">self</span>.next() { + buf[len] = elem; + len += <span class="number">1</span>; + } <span class="kw">else </span>{ + <span class="comment">// Iterator exhausted; stop early + </span><span class="kw">return </span>len; + } + } + + <span class="comment">// Continue, since the iterator was not exhausted + </span><span class="kw">for </span>(i, elem) <span class="kw">in </span><span class="self">self</span>.enumerate() { + <span class="kw">let </span>k = gen_index(rng, i + <span class="number">1 </span>+ amount); + <span class="kw">if let </span><span class="prelude-val">Some</span>(slot) = buf.get_mut(k) { + <span class="kw-2">*</span>slot = elem; + } + } + len + } + + <span class="doccomment">/// Collects `amount` values at random from the iterator into a vector. + /// + /// This is equivalent to `choose_multiple_fill` except for the result type. + /// + /// Although the elements are selected randomly, the order of elements in + /// the buffer is neither stable nor fully random. If random ordering is + /// desired, shuffle the result. + /// + /// The length of the returned vector equals `amount` unless the iterator + /// contains insufficient elements, in which case it equals the number of + /// elements available. + /// + /// Complexity is `O(n)` where `n` is the length of the iterator. + /// For slices, prefer [`SliceRandom::choose_multiple`]. + </span><span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + #[cfg_attr(doc_cfg, doc(cfg(feature = <span class="string">"alloc"</span>)))] + </span><span class="kw">fn </span>choose_multiple<R>(<span class="kw-2">mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, amount: usize) -> Vec<<span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">let </span><span class="kw-2">mut </span>reservoir = Vec::with_capacity(amount); + reservoir.extend(<span class="self">self</span>.by_ref().take(amount)); + + <span class="comment">// Continue unless the iterator was exhausted + // + // note: this prevents iterators that "restart" from causing problems. + // If the iterator stops once, then so do we. + </span><span class="kw">if </span>reservoir.len() == amount { + <span class="kw">for </span>(i, elem) <span class="kw">in </span><span class="self">self</span>.enumerate() { + <span class="kw">let </span>k = gen_index(rng, i + <span class="number">1 </span>+ amount); + <span class="kw">if let </span><span class="prelude-val">Some</span>(slot) = reservoir.get_mut(k) { + <span class="kw-2">*</span>slot = elem; + } + } + } <span class="kw">else </span>{ + <span class="comment">// Don't hang onto extra memory. There is a corner case where + // `amount` was much less than `self.len()`. + </span>reservoir.shrink_to_fit(); + } + reservoir + } +} + + +<span class="kw">impl</span><T> SliceRandom <span class="kw">for </span>[T] { + <span class="kw">type </span>Item = T; + + <span class="kw">fn </span>choose<R>(<span class="kw-2">&</span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R) -> <span class="prelude-ty">Option</span><<span class="kw-2">&</span><span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">if </span><span class="self">self</span>.is_empty() { + <span class="prelude-val">None + </span>} <span class="kw">else </span>{ + <span class="prelude-val">Some</span>(<span class="kw-2">&</span><span class="self">self</span>[gen_index(rng, <span class="self">self</span>.len())]) + } + } + + <span class="kw">fn </span>choose_mut<R>(<span class="kw-2">&mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R) -> <span class="prelude-ty">Option</span><<span class="kw-2">&mut </span><span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">if </span><span class="self">self</span>.is_empty() { + <span class="prelude-val">None + </span>} <span class="kw">else </span>{ + <span class="kw">let </span>len = <span class="self">self</span>.len(); + <span class="prelude-val">Some</span>(<span class="kw-2">&mut </span><span class="self">self</span>[gen_index(rng, len)]) + } + } + + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span><span class="kw">fn </span>choose_multiple<R>(<span class="kw-2">&</span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, amount: usize) -> SliceChooseIter<<span class="self">Self</span>, <span class="self">Self</span>::Item> + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">let </span>amount = ::core::cmp::min(amount, <span class="self">self</span>.len()); + SliceChooseIter { + slice: <span class="self">self</span>, + _phantom: Default::default(), + indices: index::sample(rng, <span class="self">self</span>.len(), amount).into_iter(), + } + } + + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span><span class="kw">fn </span>choose_weighted<R, F, B, X>( + <span class="kw-2">&</span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, weight: F, + ) -> <span class="prelude-ty">Result</span><<span class="kw-2">&</span><span class="self">Self</span>::Item, WeightedError> + <span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + F: Fn(<span class="kw-2">&</span><span class="self">Self</span>::Item) -> B, + B: SampleBorrow<X>, + X: SampleUniform + + <span class="kw">for</span><<span class="lifetime">'a</span>> ::core::ops::AddAssign<<span class="kw-2">&</span><span class="lifetime">'a </span>X> + + ::core::cmp::PartialOrd<X> + + Clone + + Default, + { + <span class="kw">use </span><span class="kw">crate</span>::distributions::{Distribution, WeightedIndex}; + <span class="kw">let </span>distr = WeightedIndex::new(<span class="self">self</span>.iter().map(weight))<span class="question-mark">?</span>; + <span class="prelude-val">Ok</span>(<span class="kw-2">&</span><span class="self">self</span>[distr.sample(rng)]) + } + + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span><span class="kw">fn </span>choose_weighted_mut<R, F, B, X>( + <span class="kw-2">&mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, weight: F, + ) -> <span class="prelude-ty">Result</span><<span class="kw-2">&mut </span><span class="self">Self</span>::Item, WeightedError> + <span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + F: Fn(<span class="kw-2">&</span><span class="self">Self</span>::Item) -> B, + B: SampleBorrow<X>, + X: SampleUniform + + <span class="kw">for</span><<span class="lifetime">'a</span>> ::core::ops::AddAssign<<span class="kw-2">&</span><span class="lifetime">'a </span>X> + + ::core::cmp::PartialOrd<X> + + Clone + + Default, + { + <span class="kw">use </span><span class="kw">crate</span>::distributions::{Distribution, WeightedIndex}; + <span class="kw">let </span>distr = WeightedIndex::new(<span class="self">self</span>.iter().map(weight))<span class="question-mark">?</span>; + <span class="prelude-val">Ok</span>(<span class="kw-2">&mut </span><span class="self">self</span>[distr.sample(rng)]) + } + + <span class="attribute">#[cfg(feature = <span class="string">"std"</span>)] + </span><span class="kw">fn </span>choose_multiple_weighted<R, F, X>( + <span class="kw-2">&</span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, amount: usize, weight: F, + ) -> <span class="prelude-ty">Result</span><SliceChooseIter<<span class="self">Self</span>, <span class="self">Self</span>::Item>, WeightedError> + <span class="kw">where + </span>R: Rng + <span class="question-mark">?</span>Sized, + F: Fn(<span class="kw-2">&</span><span class="self">Self</span>::Item) -> X, + X: Into<f64>, + { + <span class="kw">let </span>amount = ::core::cmp::min(amount, <span class="self">self</span>.len()); + <span class="prelude-val">Ok</span>(SliceChooseIter { + slice: <span class="self">self</span>, + _phantom: Default::default(), + indices: index::sample_weighted( + rng, + <span class="self">self</span>.len(), + |idx| weight(<span class="kw-2">&</span><span class="self">self</span>[idx]).into(), + amount, + )<span class="question-mark">? + </span>.into_iter(), + }) + } + + <span class="kw">fn </span>shuffle<R>(<span class="kw-2">&mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R) + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="kw">for </span>i <span class="kw">in </span>(<span class="number">1</span>..<span class="self">self</span>.len()).rev() { + <span class="comment">// invariant: elements with index > i have been locked in place. + </span><span class="self">self</span>.swap(i, gen_index(rng, i + <span class="number">1</span>)); + } + } + + <span class="kw">fn </span>partial_shuffle<R>( + <span class="kw-2">&mut </span><span class="self">self</span>, rng: <span class="kw-2">&mut </span>R, amount: usize, + ) -> (<span class="kw-2">&mut </span>[<span class="self">Self</span>::Item], <span class="kw-2">&mut </span>[<span class="self">Self</span>::Item]) + <span class="kw">where </span>R: Rng + <span class="question-mark">?</span>Sized { + <span class="comment">// This applies Durstenfeld's algorithm for the + // [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) + // for an unbiased permutation, but exits early after choosing `amount` + // elements. + + </span><span class="kw">let </span>len = <span class="self">self</span>.len(); + <span class="kw">let </span>end = <span class="kw">if </span>amount >= len { <span class="number">0 </span>} <span class="kw">else </span>{ len - amount }; + + <span class="kw">for </span>i <span class="kw">in </span>(end..len).rev() { + <span class="comment">// invariant: elements with index > i have been locked in place. + </span><span class="self">self</span>.swap(i, gen_index(rng, i + <span class="number">1</span>)); + } + <span class="kw">let </span>r = <span class="self">self</span>.split_at_mut(end); + (r.<span class="number">1</span>, r.<span class="number">0</span>) + } +} + +<span class="kw">impl</span><I> IteratorRandom <span class="kw">for </span>I <span class="kw">where </span>I: Iterator + Sized {} + + +<span class="doccomment">/// An iterator over multiple slice elements. +/// +/// This struct is created by +/// [`SliceRandom::choose_multiple`](trait.SliceRandom.html#tymethod.choose_multiple). +</span><span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] +#[cfg_attr(doc_cfg, doc(cfg(feature = <span class="string">"alloc"</span>)))] +#[derive(Debug)] +</span><span class="kw">pub struct </span>SliceChooseIter<<span class="lifetime">'a</span>, S: <span class="question-mark">?</span>Sized + <span class="lifetime">'a</span>, T: <span class="lifetime">'a</span>> { + slice: <span class="kw-2">&</span><span class="lifetime">'a </span>S, + _phantom: ::core::marker::PhantomData<T>, + indices: index::IndexVecIntoIter, +} + +<span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] +</span><span class="kw">impl</span><<span class="lifetime">'a</span>, S: Index<usize, Output = T> + <span class="question-mark">?</span>Sized + <span class="lifetime">'a</span>, T: <span class="lifetime">'a</span>> Iterator <span class="kw">for </span>SliceChooseIter<<span class="lifetime">'a</span>, S, T> { + <span class="kw">type </span>Item = <span class="kw-2">&</span><span class="lifetime">'a </span>T; + + <span class="kw">fn </span>next(<span class="kw-2">&mut </span><span class="self">self</span>) -> <span class="prelude-ty">Option</span><<span class="self">Self</span>::Item> { + <span class="comment">// TODO: investigate using SliceIndex::get_unchecked when stable + </span><span class="self">self</span>.indices.next().map(|i| <span class="kw-2">&</span><span class="self">self</span>.slice[i <span class="kw">as </span>usize]) + } + + <span class="kw">fn </span>size_hint(<span class="kw-2">&</span><span class="self">self</span>) -> (usize, <span class="prelude-ty">Option</span><usize>) { + (<span class="self">self</span>.indices.len(), <span class="prelude-val">Some</span>(<span class="self">self</span>.indices.len())) + } +} + +<span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] +</span><span class="kw">impl</span><<span class="lifetime">'a</span>, S: Index<usize, Output = T> + <span class="question-mark">?</span>Sized + <span class="lifetime">'a</span>, T: <span class="lifetime">'a</span>> ExactSizeIterator + <span class="kw">for </span>SliceChooseIter<<span class="lifetime">'a</span>, S, T> +{ + <span class="kw">fn </span>len(<span class="kw-2">&</span><span class="self">self</span>) -> usize { + <span class="self">self</span>.indices.len() + } +} + + +<span class="comment">// Sample a number uniformly between 0 and `ubound`. Uses 32-bit sampling where +// possible, primarily in order to produce the same output on 32-bit and 64-bit +// platforms. +</span><span class="attribute">#[inline] +</span><span class="kw">fn </span>gen_index<R: Rng + <span class="question-mark">?</span>Sized>(rng: <span class="kw-2">&mut </span>R, ubound: usize) -> usize { + <span class="kw">if </span>ubound <= (core::u32::MAX <span class="kw">as </span>usize) { + rng.gen_range(<span class="number">0</span>..ubound <span class="kw">as </span>u32) <span class="kw">as </span>usize + } <span class="kw">else </span>{ + rng.gen_range(<span class="number">0</span>..ubound) + } +} + + +<span class="attribute">#[cfg(test)] +</span><span class="kw">mod </span>test { + <span class="kw">use super</span>::<span class="kw-2">*</span>; + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] </span><span class="kw">use </span><span class="kw">crate</span>::Rng; + <span class="attribute">#[cfg(all(feature = <span class="string">"alloc"</span>, not(feature = <span class="string">"std"</span>)))] </span><span class="kw">use </span>alloc::vec::Vec; + + <span class="attribute">#[test] + </span><span class="kw">fn </span>test_slice_choose() { + <span class="kw">let </span><span class="kw-2">mut </span>r = <span class="kw">crate</span>::test::rng(<span class="number">107</span>); + <span class="kw">let </span>chars = [ + <span class="string">'a'</span>, <span class="string">'b'</span>, <span class="string">'c'</span>, <span class="string">'d'</span>, <span class="string">'e'</span>, <span class="string">'f'</span>, <span class="string">'g'</span>, <span class="string">'h'</span>, <span class="string">'i'</span>, <span class="string">'j'</span>, <span class="string">'k'</span>, <span class="string">'l'</span>, <span class="string">'m'</span>, <span class="string">'n'</span>, + ]; + <span class="kw">let </span><span class="kw-2">mut </span>chosen = [<span class="number">0i32</span>; <span class="number">14</span>]; + <span class="comment">// The below all use a binomial distribution with n=1000, p=1/14. + // binocdf(40, 1000, 1/14) ~= 2e-5; 1-binocdf(106, ..) ~= 2e-5 + </span><span class="kw">for _ in </span><span class="number">0</span>..<span class="number">1000 </span>{ + <span class="kw">let </span>picked = <span class="kw-2">*</span>chars.choose(<span class="kw-2">&mut </span>r).unwrap(); + chosen[(picked <span class="kw">as </span>usize) - (<span class="string">'a' </span><span class="kw">as </span>usize)] += <span class="number">1</span>; + } + <span class="kw">for </span>count <span class="kw">in </span>chosen.iter() { + <span class="macro">assert!</span>(<span class="number">40 </span>< <span class="kw-2">*</span>count && <span class="kw-2">*</span>count < <span class="number">106</span>); + } + + chosen.iter_mut().for_each(|x| <span class="kw-2">*</span>x = <span class="number">0</span>); + <span class="kw">for _ in </span><span class="number">0</span>..<span class="number">1000 </span>{ + <span class="kw-2">*</span>chosen.choose_mut(<span class="kw-2">&mut </span>r).unwrap() += <span class="number">1</span>; + } + <span class="kw">for </span>count <span class="kw">in </span>chosen.iter() { + <span class="macro">assert!</span>(<span class="number">40 </span>< <span class="kw-2">*</span>count && <span class="kw-2">*</span>count < <span class="number">106</span>); + } + + <span class="kw">let </span><span class="kw-2">mut </span>v: [isize; <span class="number">0</span>] = []; + <span class="macro">assert_eq!</span>(v.choose(<span class="kw-2">&mut </span>r), <span class="prelude-val">None</span>); + <span class="macro">assert_eq!</span>(v.choose_mut(<span class="kw-2">&mut </span>r), <span class="prelude-val">None</span>); + } + + <span class="attribute">#[test] + </span><span class="kw">fn </span>value_stability_slice() { + <span class="kw">let </span><span class="kw-2">mut </span>r = <span class="kw">crate</span>::test::rng(<span class="number">413</span>); + <span class="kw">let </span>chars = [ + <span class="string">'a'</span>, <span class="string">'b'</span>, <span class="string">'c'</span>, <span class="string">'d'</span>, <span class="string">'e'</span>, <span class="string">'f'</span>, <span class="string">'g'</span>, <span class="string">'h'</span>, <span class="string">'i'</span>, <span class="string">'j'</span>, <span class="string">'k'</span>, <span class="string">'l'</span>, <span class="string">'m'</span>, <span class="string">'n'</span>, + ]; + <span class="kw">let </span><span class="kw-2">mut </span>nums = [<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">9</span>, <span class="number">10</span>, <span class="number">11</span>, <span class="number">12</span>]; + + <span class="macro">assert_eq!</span>(chars.choose(<span class="kw-2">&mut </span>r), <span class="prelude-val">Some</span>(<span class="kw-2">&</span><span class="string">'l'</span>)); + <span class="macro">assert_eq!</span>(nums.choose_mut(<span class="kw-2">&mut </span>r), <span class="prelude-val">Some</span>(<span class="kw-2">&mut </span><span class="number">10</span>)); + + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span><span class="macro">assert_eq!</span>( + <span class="kw-2">&</span>chars + .choose_multiple(<span class="kw-2">&mut </span>r, <span class="number">8</span>) + .cloned() + .collect::<Vec<char>>(), + <span class="kw-2">&</span>[<span class="string">'d'</span>, <span class="string">'m'</span>, <span class="string">'b'</span>, <span class="string">'n'</span>, <span class="string">'c'</span>, <span class="string">'k'</span>, <span class="string">'h'</span>, <span class="string">'e'</span>] + ); + + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span><span class="macro">assert_eq!</span>(chars.choose_weighted(<span class="kw-2">&mut </span>r, |<span class="kw">_</span>| <span class="number">1</span>), <span class="prelude-val">Ok</span>(<span class="kw-2">&</span><span class="string">'f'</span>)); + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span><span class="macro">assert_eq!</span>(nums.choose_weighted_mut(<span class="kw-2">&mut </span>r, |<span class="kw">_</span>| <span class="number">1</span>), <span class="prelude-val">Ok</span>(<span class="kw-2">&mut </span><span class="number">5</span>)); + + <span class="kw">let </span><span class="kw-2">mut </span>r = <span class="kw">crate</span>::test::rng(<span class="number">414</span>); + nums.shuffle(<span class="kw-2">&mut </span>r); + <span class="macro">assert_eq!</span>(nums, [<span class="number">9</span>, <span class="number">5</span>, <span class="number">3</span>, <span class="number">10</span>, <span class="number">7</span>, <span class="number">12</span>, <span class="number">8</span>, <span class="number">11</span>, <span class="number">6</span>, <span class="number">4</span>, <span class="number">0</span>, <span class="number">2</span>, <span class="number">1</span>]); + nums = [<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">9</span>, <span class="number">10</span>, <span class="number">11</span>, <span class="number">12</span>]; + <span class="kw">let </span>res = nums.partial_shuffle(<span class="kw-2">&mut </span>r, <span class="number">6</span>); + <span class="macro">assert_eq!</span>(res.<span class="number">0</span>, <span class="kw-2">&mut </span>[<span class="number">7</span>, <span class="number">4</span>, <span class="number">8</span>, <span class="number">6</span>, <span class="number">9</span>, <span class="number">3</span>]); + <span class="macro">assert_eq!</span>(res.<span class="number">1</span>, <span class="kw-2">&mut </span>[<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">12</span>, <span class="number">11</span>, <span class="number">5</span>, <span class="number">10</span>]); + } + + <span class="attribute">#[derive(Clone)] + </span><span class="kw">struct </span>UnhintedIterator<I: Iterator + Clone> { + iter: I, + } + <span class="kw">impl</span><I: Iterator + Clone> Iterator <span class="kw">for </span>UnhintedIterator<I> { + <span class="kw">type </span>Item = I::Item; + + <span class="kw">fn </span>next(<span class="kw-2">&mut </span><span class="self">self</span>) -> <span class="prelude-ty">Option</span><<span class="self">Self</span>::Item> { + <span class="self">self</span>.iter.next() + } + } + + <span class="attribute">#[derive(Clone)] + </span><span class="kw">struct </span>ChunkHintedIterator<I: ExactSizeIterator + Iterator + Clone> { + iter: I, + chunk_remaining: usize, + chunk_size: usize, + hint_total_size: bool, + } + <span class="kw">impl</span><I: ExactSizeIterator + Iterator + Clone> Iterator <span class="kw">for </span>ChunkHintedIterator<I> { + <span class="kw">type </span>Item = I::Item; + + <span class="kw">fn </span>next(<span class="kw-2">&mut </span><span class="self">self</span>) -> <span class="prelude-ty">Option</span><<span class="self">Self</span>::Item> { + <span class="kw">if </span><span class="self">self</span>.chunk_remaining == <span class="number">0 </span>{ + <span class="self">self</span>.chunk_remaining = ::core::cmp::min(<span class="self">self</span>.chunk_size, <span class="self">self</span>.iter.len()); + } + <span class="self">self</span>.chunk_remaining = <span class="self">self</span>.chunk_remaining.saturating_sub(<span class="number">1</span>); + + <span class="self">self</span>.iter.next() + } + + <span class="kw">fn </span>size_hint(<span class="kw-2">&</span><span class="self">self</span>) -> (usize, <span class="prelude-ty">Option</span><usize>) { + ( + <span class="self">self</span>.chunk_remaining, + <span class="kw">if </span><span class="self">self</span>.hint_total_size { + <span class="prelude-val">Some</span>(<span class="self">self</span>.iter.len()) + } <span class="kw">else </span>{ + <span class="prelude-val">None + </span>}, + ) + } + } + + <span class="attribute">#[derive(Clone)] + </span><span class="kw">struct </span>WindowHintedIterator<I: ExactSizeIterator + Iterator + Clone> { + iter: I, + window_size: usize, + hint_total_size: bool, + } + <span class="kw">impl</span><I: ExactSizeIterator + Iterator + Clone> Iterator <span class="kw">for </span>WindowHintedIterator<I> { + <span class="kw">type </span>Item = I::Item; + + <span class="kw">fn </span>next(<span class="kw-2">&mut </span><span class="self">self</span>) -> <span class="prelude-ty">Option</span><<span class="self">Self</span>::Item> { + <span class="self">self</span>.iter.next() + } + + <span class="kw">fn </span>size_hint(<span class="kw-2">&</span><span class="self">self</span>) -> (usize, <span class="prelude-ty">Option</span><usize>) { + ( + ::core::cmp::min(<span class="self">self</span>.iter.len(), <span class="self">self</span>.window_size), + <span class="kw">if </span><span class="self">self</span>.hint_total_size { + <span class="prelude-val">Some</span>(<span class="self">self</span>.iter.len()) + } <span class="kw">else </span>{ + <span class="prelude-val">None + </span>}, + ) + } + } + + <span class="attribute">#[test] + #[cfg_attr(miri, ignore)] </span><span class="comment">// Miri is too slow + </span><span class="kw">fn </span>test_iterator_choose() { + <span class="kw">let </span>r = <span class="kw-2">&mut </span><span class="kw">crate</span>::test::rng(<span class="number">109</span>); + <span class="kw">fn </span>test_iter<R: Rng + <span class="question-mark">?</span>Sized, Iter: Iterator<Item = usize> + Clone>(r: <span class="kw-2">&mut </span>R, iter: Iter) { + <span class="kw">let </span><span class="kw-2">mut </span>chosen = [<span class="number">0i32</span>; <span class="number">9</span>]; + <span class="kw">for _ in </span><span class="number">0</span>..<span class="number">1000 </span>{ + <span class="kw">let </span>picked = iter.clone().choose(r).unwrap(); + chosen[picked] += <span class="number">1</span>; + } + <span class="kw">for </span>count <span class="kw">in </span>chosen.iter() { + <span class="comment">// Samples should follow Binomial(1000, 1/9) + // Octave: binopdf(x, 1000, 1/9) gives the prob of *count == x + // Note: have seen 153, which is unlikely but not impossible. + </span><span class="macro">assert!</span>( + <span class="number">72 </span>< <span class="kw-2">*</span>count && <span class="kw-2">*</span>count < <span class="number">154</span>, + <span class="string">"count not close to 1000/9: {}"</span>, + count + ); + } + } + + test_iter(r, <span class="number">0</span>..<span class="number">9</span>); + test_iter(r, [<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>].iter().cloned()); + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span>test_iter(r, (<span class="number">0</span>..<span class="number">9</span>).collect::<Vec<<span class="kw">_</span>>>().into_iter()); + test_iter(r, UnhintedIterator { iter: <span class="number">0</span>..<span class="number">9 </span>}); + test_iter(r, ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + chunk_size: <span class="number">4</span>, + chunk_remaining: <span class="number">4</span>, + hint_total_size: <span class="bool-val">false</span>, + }); + test_iter(r, ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + chunk_size: <span class="number">4</span>, + chunk_remaining: <span class="number">4</span>, + hint_total_size: <span class="bool-val">true</span>, + }); + test_iter(r, WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + window_size: <span class="number">2</span>, + hint_total_size: <span class="bool-val">false</span>, + }); + test_iter(r, WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + window_size: <span class="number">2</span>, + hint_total_size: <span class="bool-val">true</span>, + }); + + <span class="macro">assert_eq!</span>((<span class="number">0</span>..<span class="number">0</span>).choose(r), <span class="prelude-val">None</span>); + <span class="macro">assert_eq!</span>(UnhintedIterator { iter: <span class="number">0</span>..<span class="number">0 </span>}.choose(r), <span class="prelude-val">None</span>); + } + + <span class="attribute">#[test] + #[cfg_attr(miri, ignore)] </span><span class="comment">// Miri is too slow + </span><span class="kw">fn </span>test_iterator_choose_stable() { + <span class="kw">let </span>r = <span class="kw-2">&mut </span><span class="kw">crate</span>::test::rng(<span class="number">109</span>); + <span class="kw">fn </span>test_iter<R: Rng + <span class="question-mark">?</span>Sized, Iter: Iterator<Item = usize> + Clone>(r: <span class="kw-2">&mut </span>R, iter: Iter) { + <span class="kw">let </span><span class="kw-2">mut </span>chosen = [<span class="number">0i32</span>; <span class="number">9</span>]; + <span class="kw">for _ in </span><span class="number">0</span>..<span class="number">1000 </span>{ + <span class="kw">let </span>picked = iter.clone().choose_stable(r).unwrap(); + chosen[picked] += <span class="number">1</span>; + } + <span class="kw">for </span>count <span class="kw">in </span>chosen.iter() { + <span class="comment">// Samples should follow Binomial(1000, 1/9) + // Octave: binopdf(x, 1000, 1/9) gives the prob of *count == x + // Note: have seen 153, which is unlikely but not impossible. + </span><span class="macro">assert!</span>( + <span class="number">72 </span>< <span class="kw-2">*</span>count && <span class="kw-2">*</span>count < <span class="number">154</span>, + <span class="string">"count not close to 1000/9: {}"</span>, + count + ); + } + } + + test_iter(r, <span class="number">0</span>..<span class="number">9</span>); + test_iter(r, [<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>].iter().cloned()); + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span>test_iter(r, (<span class="number">0</span>..<span class="number">9</span>).collect::<Vec<<span class="kw">_</span>>>().into_iter()); + test_iter(r, UnhintedIterator { iter: <span class="number">0</span>..<span class="number">9 </span>}); + test_iter(r, ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + chunk_size: <span class="number">4</span>, + chunk_remaining: <span class="number">4</span>, + hint_total_size: <span class="bool-val">false</span>, + }); + test_iter(r, ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + chunk_size: <span class="number">4</span>, + chunk_remaining: <span class="number">4</span>, + hint_total_size: <span class="bool-val">true</span>, + }); + test_iter(r, WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + window_size: <span class="number">2</span>, + hint_total_size: <span class="bool-val">false</span>, + }); + test_iter(r, WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + window_size: <span class="number">2</span>, + hint_total_size: <span class="bool-val">true</span>, + }); + + <span class="macro">assert_eq!</span>((<span class="number">0</span>..<span class="number">0</span>).choose(r), <span class="prelude-val">None</span>); + <span class="macro">assert_eq!</span>(UnhintedIterator { iter: <span class="number">0</span>..<span class="number">0 </span>}.choose(r), <span class="prelude-val">None</span>); + } + + <span class="attribute">#[test] + #[cfg_attr(miri, ignore)] </span><span class="comment">// Miri is too slow + </span><span class="kw">fn </span>test_iterator_choose_stable_stability() { + <span class="kw">fn </span>test_iter(iter: <span class="kw">impl </span>Iterator<Item = usize> + Clone) -> [i32; <span class="number">9</span>] { + <span class="kw">let </span>r = <span class="kw-2">&mut </span><span class="kw">crate</span>::test::rng(<span class="number">109</span>); + <span class="kw">let </span><span class="kw-2">mut </span>chosen = [<span class="number">0i32</span>; <span class="number">9</span>]; + <span class="kw">for _ in </span><span class="number">0</span>..<span class="number">1000 </span>{ + <span class="kw">let </span>picked = iter.clone().choose_stable(r).unwrap(); + chosen[picked] += <span class="number">1</span>; + } + chosen + } + + <span class="kw">let </span>reference = test_iter(<span class="number">0</span>..<span class="number">9</span>); + <span class="macro">assert_eq!</span>(test_iter([<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>].iter().cloned()), reference); + + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span><span class="macro">assert_eq!</span>(test_iter((<span class="number">0</span>..<span class="number">9</span>).collect::<Vec<<span class="kw">_</span>>>().into_iter()), reference); + <span class="macro">assert_eq!</span>(test_iter(UnhintedIterator { iter: <span class="number">0</span>..<span class="number">9 </span>}), reference); + <span class="macro">assert_eq!</span>(test_iter(ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + chunk_size: <span class="number">4</span>, + chunk_remaining: <span class="number">4</span>, + hint_total_size: <span class="bool-val">false</span>, + }), reference); + <span class="macro">assert_eq!</span>(test_iter(ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + chunk_size: <span class="number">4</span>, + chunk_remaining: <span class="number">4</span>, + hint_total_size: <span class="bool-val">true</span>, + }), reference); + <span class="macro">assert_eq!</span>(test_iter(WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + window_size: <span class="number">2</span>, + hint_total_size: <span class="bool-val">false</span>, + }), reference); + <span class="macro">assert_eq!</span>(test_iter(WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">9</span>, + window_size: <span class="number">2</span>, + hint_total_size: <span class="bool-val">true</span>, + }), reference); + } + + <span class="attribute">#[test] + #[cfg_attr(miri, ignore)] </span><span class="comment">// Miri is too slow + </span><span class="kw">fn </span>test_shuffle() { + <span class="kw">let </span><span class="kw-2">mut </span>r = <span class="kw">crate</span>::test::rng(<span class="number">108</span>); + <span class="kw">let </span>empty: <span class="kw-2">&mut </span>[isize] = <span class="kw-2">&mut </span>[]; + empty.shuffle(<span class="kw-2">&mut </span>r); + <span class="kw">let </span><span class="kw-2">mut </span>one = [<span class="number">1</span>]; + one.shuffle(<span class="kw-2">&mut </span>r); + <span class="kw">let </span>b: <span class="kw-2">&</span>[<span class="kw">_</span>] = <span class="kw-2">&</span>[<span class="number">1</span>]; + <span class="macro">assert_eq!</span>(one, b); + + <span class="kw">let </span><span class="kw-2">mut </span>two = [<span class="number">1</span>, <span class="number">2</span>]; + two.shuffle(<span class="kw-2">&mut </span>r); + <span class="macro">assert!</span>(two == [<span class="number">1</span>, <span class="number">2</span>] || two == [<span class="number">2</span>, <span class="number">1</span>]); + + <span class="kw">fn </span>move_last(slice: <span class="kw-2">&mut </span>[usize], pos: usize) { + <span class="comment">// use slice[pos..].rotate_left(1); once we can use that + </span><span class="kw">let </span>last_val = slice[pos]; + <span class="kw">for </span>i <span class="kw">in </span>pos..slice.len() - <span class="number">1 </span>{ + slice[i] = slice[i + <span class="number">1</span>]; + } + <span class="kw-2">*</span>slice.last_mut().unwrap() = last_val; + } + <span class="kw">let </span><span class="kw-2">mut </span>counts = [<span class="number">0i32</span>; <span class="number">24</span>]; + <span class="kw">for _ in </span><span class="number">0</span>..<span class="number">10000 </span>{ + <span class="kw">let </span><span class="kw-2">mut </span>arr: [usize; <span class="number">4</span>] = [<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>]; + arr.shuffle(<span class="kw-2">&mut </span>r); + <span class="kw">let </span><span class="kw-2">mut </span>permutation = <span class="number">0usize</span>; + <span class="kw">let </span><span class="kw-2">mut </span>pos_value = counts.len(); + <span class="kw">for </span>i <span class="kw">in </span><span class="number">0</span>..<span class="number">4 </span>{ + pos_value /= <span class="number">4 </span>- i; + <span class="kw">let </span>pos = arr.iter().position(|<span class="kw-2">&</span>x| x == i).unwrap(); + <span class="macro">assert!</span>(pos < (<span class="number">4 </span>- i)); + permutation += pos * pos_value; + move_last(<span class="kw-2">&mut </span>arr, pos); + <span class="macro">assert_eq!</span>(arr[<span class="number">3</span>], i); + } + <span class="kw">for </span>(i, <span class="kw-2">&</span>a) <span class="kw">in </span>arr.iter().enumerate() { + <span class="macro">assert_eq!</span>(a, i); + } + counts[permutation] += <span class="number">1</span>; + } + <span class="kw">for </span>count <span class="kw">in </span>counts.iter() { + <span class="comment">// Binomial(10000, 1/24) with average 416.667 + // Octave: binocdf(n, 10000, 1/24) + // 99.9% chance samples lie within this range: + </span><span class="macro">assert!</span>(<span class="number">352 </span><= <span class="kw-2">*</span>count && <span class="kw-2">*</span>count <= <span class="number">483</span>, <span class="string">"count: {}"</span>, count); + } + } + + <span class="attribute">#[test] + </span><span class="kw">fn </span>test_partial_shuffle() { + <span class="kw">let </span><span class="kw-2">mut </span>r = <span class="kw">crate</span>::test::rng(<span class="number">118</span>); + + <span class="kw">let </span><span class="kw-2">mut </span>empty: [u32; <span class="number">0</span>] = []; + <span class="kw">let </span>res = empty.partial_shuffle(<span class="kw-2">&mut </span>r, <span class="number">10</span>); + <span class="macro">assert_eq!</span>((res.<span class="number">0</span>.len(), res.<span class="number">1</span>.len()), (<span class="number">0</span>, <span class="number">0</span>)); + + <span class="kw">let </span><span class="kw-2">mut </span>v = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>]; + <span class="kw">let </span>res = v.partial_shuffle(<span class="kw-2">&mut </span>r, <span class="number">2</span>); + <span class="macro">assert_eq!</span>((res.<span class="number">0</span>.len(), res.<span class="number">1</span>.len()), (<span class="number">2</span>, <span class="number">3</span>)); + <span class="macro">assert!</span>(res.<span class="number">0</span>[<span class="number">0</span>] != res.<span class="number">0</span>[<span class="number">1</span>]); + <span class="comment">// First elements are only modified if selected, so at least one isn't modified: + </span><span class="macro">assert!</span>(res.<span class="number">1</span>[<span class="number">0</span>] == <span class="number">1 </span>|| res.<span class="number">1</span>[<span class="number">1</span>] == <span class="number">2 </span>|| res.<span class="number">1</span>[<span class="number">2</span>] == <span class="number">3</span>); + } + + <span class="attribute">#[test] + #[cfg(feature = <span class="string">"alloc"</span>)] + </span><span class="kw">fn </span>test_sample_iter() { + <span class="kw">let </span>min_val = <span class="number">1</span>; + <span class="kw">let </span>max_val = <span class="number">100</span>; + + <span class="kw">let </span><span class="kw-2">mut </span>r = <span class="kw">crate</span>::test::rng(<span class="number">401</span>); + <span class="kw">let </span>vals = (min_val..max_val).collect::<Vec<i32>>(); + <span class="kw">let </span>small_sample = vals.iter().choose_multiple(<span class="kw-2">&mut </span>r, <span class="number">5</span>); + <span class="kw">let </span>large_sample = vals.iter().choose_multiple(<span class="kw-2">&mut </span>r, vals.len() + <span class="number">5</span>); + + <span class="macro">assert_eq!</span>(small_sample.len(), <span class="number">5</span>); + <span class="macro">assert_eq!</span>(large_sample.len(), vals.len()); + <span class="comment">// no randomization happens when amount >= len + </span><span class="macro">assert_eq!</span>(large_sample, vals.iter().collect::<Vec<<span class="kw">_</span>>>()); + + <span class="macro">assert!</span>(small_sample + .iter() + .all(|e| { <span class="kw-2">**</span>e >= min_val && <span class="kw-2">**</span>e <= max_val })); + } + + <span class="attribute">#[test] + #[cfg(feature = <span class="string">"alloc"</span>)] + #[cfg_attr(miri, ignore)] </span><span class="comment">// Miri is too slow + </span><span class="kw">fn </span>test_weighted() { + <span class="kw">let </span><span class="kw-2">mut </span>r = <span class="kw">crate</span>::test::rng(<span class="number">406</span>); + <span class="kw">const </span>N_REPS: u32 = <span class="number">3000</span>; + <span class="kw">let </span>weights = [<span class="number">1u32</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">0</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>]; + <span class="kw">let </span>total_weight = weights.iter().sum::<u32>() <span class="kw">as </span>f32; + + <span class="kw">let </span>verify = |result: [i32; <span class="number">14</span>]| { + <span class="kw">for </span>(i, count) <span class="kw">in </span>result.iter().enumerate() { + <span class="kw">let </span>exp = (weights[i] * N_REPS) <span class="kw">as </span>f32 / total_weight; + <span class="kw">let </span><span class="kw-2">mut </span>err = (<span class="kw-2">*</span>count <span class="kw">as </span>f32 - exp).abs(); + <span class="kw">if </span>err != <span class="number">0.0 </span>{ + err /= exp; + } + <span class="macro">assert!</span>(err <= <span class="number">0.25</span>); + } + }; + + <span class="comment">// choose_weighted + </span><span class="kw">fn </span>get_weight<T>(item: <span class="kw-2">&</span>(u32, T)) -> u32 { + item.<span class="number">0 + </span>} + <span class="kw">let </span><span class="kw-2">mut </span>chosen = [<span class="number">0i32</span>; <span class="number">14</span>]; + <span class="kw">let </span><span class="kw-2">mut </span>items = [(<span class="number">0u32</span>, <span class="number">0usize</span>); <span class="number">14</span>]; <span class="comment">// (weight, index) + </span><span class="kw">for </span>(i, item) <span class="kw">in </span>items.iter_mut().enumerate() { + <span class="kw-2">*</span>item = (weights[i], i); + } + <span class="kw">for _ in </span><span class="number">0</span>..N_REPS { + <span class="kw">let </span>item = items.choose_weighted(<span class="kw-2">&mut </span>r, get_weight).unwrap(); + chosen[item.<span class="number">1</span>] += <span class="number">1</span>; + } + verify(chosen); + + <span class="comment">// choose_weighted_mut + </span><span class="kw">let </span><span class="kw-2">mut </span>items = [(<span class="number">0u32</span>, <span class="number">0i32</span>); <span class="number">14</span>]; <span class="comment">// (weight, count) + </span><span class="kw">for </span>(i, item) <span class="kw">in </span>items.iter_mut().enumerate() { + <span class="kw-2">*</span>item = (weights[i], <span class="number">0</span>); + } + <span class="kw">for _ in </span><span class="number">0</span>..N_REPS { + items.choose_weighted_mut(<span class="kw-2">&mut </span>r, get_weight).unwrap().<span class="number">1 </span>+= <span class="number">1</span>; + } + <span class="kw">for </span>(ch, item) <span class="kw">in </span>chosen.iter_mut().zip(items.iter()) { + <span class="kw-2">*</span>ch = item.<span class="number">1</span>; + } + verify(chosen); + + <span class="comment">// Check error cases + </span><span class="kw">let </span>empty_slice = <span class="kw-2">&mut </span>[<span class="number">10</span>][<span class="number">0</span>..<span class="number">0</span>]; + <span class="macro">assert_eq!</span>( + empty_slice.choose_weighted(<span class="kw-2">&mut </span>r, |<span class="kw">_</span>| <span class="number">1</span>), + <span class="prelude-val">Err</span>(WeightedError::NoItem) + ); + <span class="macro">assert_eq!</span>( + empty_slice.choose_weighted_mut(<span class="kw-2">&mut </span>r, |<span class="kw">_</span>| <span class="number">1</span>), + <span class="prelude-val">Err</span>(WeightedError::NoItem) + ); + <span class="macro">assert_eq!</span>( + [<span class="string">'x'</span>].choose_weighted_mut(<span class="kw-2">&mut </span>r, |<span class="kw">_</span>| <span class="number">0</span>), + <span class="prelude-val">Err</span>(WeightedError::AllWeightsZero) + ); + <span class="macro">assert_eq!</span>( + [<span class="number">0</span>, -<span class="number">1</span>].choose_weighted_mut(<span class="kw-2">&mut </span>r, |x| <span class="kw-2">*</span>x), + <span class="prelude-val">Err</span>(WeightedError::InvalidWeight) + ); + <span class="macro">assert_eq!</span>( + [-<span class="number">1</span>, <span class="number">0</span>].choose_weighted_mut(<span class="kw-2">&mut </span>r, |x| <span class="kw-2">*</span>x), + <span class="prelude-val">Err</span>(WeightedError::InvalidWeight) + ); + } + + <span class="attribute">#[test] + </span><span class="kw">fn </span>value_stability_choose() { + <span class="kw">fn </span>choose<I: Iterator<Item = u32>>(iter: I) -> <span class="prelude-ty">Option</span><u32> { + <span class="kw">let </span><span class="kw-2">mut </span>rng = <span class="kw">crate</span>::test::rng(<span class="number">411</span>); + iter.choose(<span class="kw-2">&mut </span>rng) + } + + <span class="macro">assert_eq!</span>(choose([].iter().cloned()), <span class="prelude-val">None</span>); + <span class="macro">assert_eq!</span>(choose(<span class="number">0</span>..<span class="number">100</span>), <span class="prelude-val">Some</span>(<span class="number">33</span>)); + <span class="macro">assert_eq!</span>(choose(UnhintedIterator { iter: <span class="number">0</span>..<span class="number">100 </span>}), <span class="prelude-val">Some</span>(<span class="number">40</span>)); + <span class="macro">assert_eq!</span>( + choose(ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">100</span>, + chunk_size: <span class="number">32</span>, + chunk_remaining: <span class="number">32</span>, + hint_total_size: <span class="bool-val">false</span>, + }), + <span class="prelude-val">Some</span>(<span class="number">39</span>) + ); + <span class="macro">assert_eq!</span>( + choose(ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">100</span>, + chunk_size: <span class="number">32</span>, + chunk_remaining: <span class="number">32</span>, + hint_total_size: <span class="bool-val">true</span>, + }), + <span class="prelude-val">Some</span>(<span class="number">39</span>) + ); + <span class="macro">assert_eq!</span>( + choose(WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">100</span>, + window_size: <span class="number">32</span>, + hint_total_size: <span class="bool-val">false</span>, + }), + <span class="prelude-val">Some</span>(<span class="number">90</span>) + ); + <span class="macro">assert_eq!</span>( + choose(WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">100</span>, + window_size: <span class="number">32</span>, + hint_total_size: <span class="bool-val">true</span>, + }), + <span class="prelude-val">Some</span>(<span class="number">90</span>) + ); + } + + <span class="attribute">#[test] + </span><span class="kw">fn </span>value_stability_choose_stable() { + <span class="kw">fn </span>choose<I: Iterator<Item = u32>>(iter: I) -> <span class="prelude-ty">Option</span><u32> { + <span class="kw">let </span><span class="kw-2">mut </span>rng = <span class="kw">crate</span>::test::rng(<span class="number">411</span>); + iter.choose_stable(<span class="kw-2">&mut </span>rng) + } + + <span class="macro">assert_eq!</span>(choose([].iter().cloned()), <span class="prelude-val">None</span>); + <span class="macro">assert_eq!</span>(choose(<span class="number">0</span>..<span class="number">100</span>), <span class="prelude-val">Some</span>(<span class="number">40</span>)); + <span class="macro">assert_eq!</span>(choose(UnhintedIterator { iter: <span class="number">0</span>..<span class="number">100 </span>}), <span class="prelude-val">Some</span>(<span class="number">40</span>)); + <span class="macro">assert_eq!</span>( + choose(ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">100</span>, + chunk_size: <span class="number">32</span>, + chunk_remaining: <span class="number">32</span>, + hint_total_size: <span class="bool-val">false</span>, + }), + <span class="prelude-val">Some</span>(<span class="number">40</span>) + ); + <span class="macro">assert_eq!</span>( + choose(ChunkHintedIterator { + iter: <span class="number">0</span>..<span class="number">100</span>, + chunk_size: <span class="number">32</span>, + chunk_remaining: <span class="number">32</span>, + hint_total_size: <span class="bool-val">true</span>, + }), + <span class="prelude-val">Some</span>(<span class="number">40</span>) + ); + <span class="macro">assert_eq!</span>( + choose(WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">100</span>, + window_size: <span class="number">32</span>, + hint_total_size: <span class="bool-val">false</span>, + }), + <span class="prelude-val">Some</span>(<span class="number">40</span>) + ); + <span class="macro">assert_eq!</span>( + choose(WindowHintedIterator { + iter: <span class="number">0</span>..<span class="number">100</span>, + window_size: <span class="number">32</span>, + hint_total_size: <span class="bool-val">true</span>, + }), + <span class="prelude-val">Some</span>(<span class="number">40</span>) + ); + } + + <span class="attribute">#[test] + </span><span class="kw">fn </span>value_stability_choose_multiple() { + <span class="kw">fn </span>do_test<I: Iterator<Item = u32>>(iter: I, v: <span class="kw-2">&</span>[u32]) { + <span class="kw">let </span><span class="kw-2">mut </span>rng = <span class="kw">crate</span>::test::rng(<span class="number">412</span>); + <span class="kw">let </span><span class="kw-2">mut </span>buf = [<span class="number">0u32</span>; <span class="number">8</span>]; + <span class="macro">assert_eq!</span>(iter.choose_multiple_fill(<span class="kw-2">&mut </span>rng, <span class="kw-2">&mut </span>buf), v.len()); + <span class="macro">assert_eq!</span>(<span class="kw-2">&</span>buf[<span class="number">0</span>..v.len()], v); + } + + do_test(<span class="number">0</span>..<span class="number">4</span>, <span class="kw-2">&</span>[<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>]); + do_test(<span class="number">0</span>..<span class="number">8</span>, <span class="kw-2">&</span>[<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>]); + do_test(<span class="number">0</span>..<span class="number">100</span>, <span class="kw-2">&</span>[<span class="number">58</span>, <span class="number">78</span>, <span class="number">80</span>, <span class="number">92</span>, <span class="number">43</span>, <span class="number">8</span>, <span class="number">96</span>, <span class="number">7</span>]); + + <span class="attribute">#[cfg(feature = <span class="string">"alloc"</span>)] + </span>{ + <span class="kw">fn </span>do_test<I: Iterator<Item = u32>>(iter: I, v: <span class="kw-2">&</span>[u32]) { + <span class="kw">let </span><span class="kw-2">mut </span>rng = <span class="kw">crate</span>::test::rng(<span class="number">412</span>); + <span class="macro">assert_eq!</span>(iter.choose_multiple(<span class="kw-2">&mut </span>rng, v.len()), v); + } + + do_test(<span class="number">0</span>..<span class="number">4</span>, <span class="kw-2">&</span>[<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>]); + do_test(<span class="number">0</span>..<span class="number">8</span>, <span class="kw-2">&</span>[<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>]); + do_test(<span class="number">0</span>..<span class="number">100</span>, <span class="kw-2">&</span>[<span class="number">58</span>, <span class="number">78</span>, <span class="number">80</span>, <span class="number">92</span>, <span class="number">43</span>, <span class="number">8</span>, <span class="number">96</span>, <span class="number">7</span>]); + } + } + + <span class="attribute">#[test] + #[cfg(feature = <span class="string">"std"</span>)] + </span><span class="kw">fn </span>test_multiple_weighted_edge_cases() { + <span class="kw">use super</span>::<span class="kw-2">*</span>; + + <span class="kw">let </span><span class="kw-2">mut </span>rng = <span class="kw">crate</span>::test::rng(<span class="number">413</span>); + + <span class="comment">// Case 1: One of the weights is 0 + </span><span class="kw">let </span>choices = [(<span class="string">'a'</span>, <span class="number">2</span>), (<span class="string">'b'</span>, <span class="number">1</span>), (<span class="string">'c'</span>, <span class="number">0</span>)]; + <span class="kw">for _ in </span><span class="number">0</span>..<span class="number">100 </span>{ + <span class="kw">let </span>result = choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">2</span>, |item| item.<span class="number">1</span>) + .unwrap() + .collect::<Vec<<span class="kw">_</span>>>(); + + <span class="macro">assert_eq!</span>(result.len(), <span class="number">2</span>); + <span class="macro">assert!</span>(!result.iter().any(|val| val.<span class="number">0 </span>== <span class="string">'c'</span>)); + } + + <span class="comment">// Case 2: All of the weights are 0 + </span><span class="kw">let </span>choices = [(<span class="string">'a'</span>, <span class="number">0</span>), (<span class="string">'b'</span>, <span class="number">0</span>), (<span class="string">'c'</span>, <span class="number">0</span>)]; + + <span class="macro">assert_eq!</span>(choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">2</span>, |item| item.<span class="number">1</span>) + .unwrap().count(), <span class="number">2</span>); + + <span class="comment">// Case 3: Negative weights + </span><span class="kw">let </span>choices = [(<span class="string">'a'</span>, -<span class="number">1</span>), (<span class="string">'b'</span>, <span class="number">1</span>), (<span class="string">'c'</span>, <span class="number">1</span>)]; + <span class="macro">assert_eq!</span>( + choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">2</span>, |item| item.<span class="number">1</span>) + .unwrap_err(), + WeightedError::InvalidWeight + ); + + <span class="comment">// Case 4: Empty list + </span><span class="kw">let </span>choices = []; + <span class="macro">assert_eq!</span>(choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">0</span>, |<span class="kw">_</span>: <span class="kw-2">&</span>()| <span class="number">0</span>) + .unwrap().count(), <span class="number">0</span>); + + <span class="comment">// Case 5: NaN weights + </span><span class="kw">let </span>choices = [(<span class="string">'a'</span>, core::f64::NAN), (<span class="string">'b'</span>, <span class="number">1.0</span>), (<span class="string">'c'</span>, <span class="number">1.0</span>)]; + <span class="macro">assert_eq!</span>( + choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">2</span>, |item| item.<span class="number">1</span>) + .unwrap_err(), + WeightedError::InvalidWeight + ); + + <span class="comment">// Case 6: +infinity weights + </span><span class="kw">let </span>choices = [(<span class="string">'a'</span>, core::f64::INFINITY), (<span class="string">'b'</span>, <span class="number">1.0</span>), (<span class="string">'c'</span>, <span class="number">1.0</span>)]; + <span class="kw">for _ in </span><span class="number">0</span>..<span class="number">100 </span>{ + <span class="kw">let </span>result = choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">2</span>, |item| item.<span class="number">1</span>) + .unwrap() + .collect::<Vec<<span class="kw">_</span>>>(); + <span class="macro">assert_eq!</span>(result.len(), <span class="number">2</span>); + <span class="macro">assert!</span>(result.iter().any(|val| val.<span class="number">0 </span>== <span class="string">'a'</span>)); + } + + <span class="comment">// Case 7: -infinity weights + </span><span class="kw">let </span>choices = [(<span class="string">'a'</span>, core::f64::NEG_INFINITY), (<span class="string">'b'</span>, <span class="number">1.0</span>), (<span class="string">'c'</span>, <span class="number">1.0</span>)]; + <span class="macro">assert_eq!</span>( + choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">2</span>, |item| item.<span class="number">1</span>) + .unwrap_err(), + WeightedError::InvalidWeight + ); + + <span class="comment">// Case 8: -0 weights + </span><span class="kw">let </span>choices = [(<span class="string">'a'</span>, -<span class="number">0.0</span>), (<span class="string">'b'</span>, <span class="number">1.0</span>), (<span class="string">'c'</span>, <span class="number">1.0</span>)]; + <span class="macro">assert!</span>(choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">2</span>, |item| item.<span class="number">1</span>) + .is_ok()); + } + + <span class="attribute">#[test] + #[cfg(feature = <span class="string">"std"</span>)] + </span><span class="kw">fn </span>test_multiple_weighted_distributions() { + <span class="kw">use super</span>::<span class="kw-2">*</span>; + + <span class="comment">// The theoretical probabilities of the different outcomes are: + // AB: 0.5 * 0.5 = 0.250 + // AC: 0.5 * 0.5 = 0.250 + // BA: 0.25 * 0.67 = 0.167 + // BC: 0.25 * 0.33 = 0.082 + // CA: 0.25 * 0.67 = 0.167 + // CB: 0.25 * 0.33 = 0.082 + </span><span class="kw">let </span>choices = [(<span class="string">'a'</span>, <span class="number">2</span>), (<span class="string">'b'</span>, <span class="number">1</span>), (<span class="string">'c'</span>, <span class="number">1</span>)]; + <span class="kw">let </span><span class="kw-2">mut </span>rng = <span class="kw">crate</span>::test::rng(<span class="number">414</span>); + + <span class="kw">let </span><span class="kw-2">mut </span>results = [<span class="number">0i32</span>; <span class="number">3</span>]; + <span class="kw">let </span>expected_results = [<span class="number">4167</span>, <span class="number">4167</span>, <span class="number">1666</span>]; + <span class="kw">for _ in </span><span class="number">0</span>..<span class="number">10000 </span>{ + <span class="kw">let </span>result = choices + .choose_multiple_weighted(<span class="kw-2">&mut </span>rng, <span class="number">2</span>, |item| item.<span class="number">1</span>) + .unwrap() + .collect::<Vec<<span class="kw">_</span>>>(); + + <span class="macro">assert_eq!</span>(result.len(), <span class="number">2</span>); + + <span class="kw">match </span>(result[<span class="number">0</span>].<span class="number">0</span>, result[<span class="number">1</span>].<span class="number">0</span>) { + (<span class="string">'a'</span>, <span class="string">'b'</span>) | (<span class="string">'b'</span>, <span class="string">'a'</span>) => { + results[<span class="number">0</span>] += <span class="number">1</span>; + } + (<span class="string">'a'</span>, <span class="string">'c'</span>) | (<span class="string">'c'</span>, <span class="string">'a'</span>) => { + results[<span class="number">1</span>] += <span class="number">1</span>; + } + (<span class="string">'b'</span>, <span class="string">'c'</span>) | (<span class="string">'c'</span>, <span class="string">'b'</span>) => { + results[<span class="number">2</span>] += <span class="number">1</span>; + } + (<span class="kw">_</span>, <span class="kw">_</span>) => <span class="macro">panic!</span>(<span class="string">"unexpected result"</span>), + } + } + + <span class="kw">let </span><span class="kw-2">mut </span>diffs = results + .iter() + .zip(<span class="kw-2">&</span>expected_results) + .map(|(a, b)| (a - b).abs()); + <span class="macro">assert!</span>(!diffs.any(|deviation| deviation > <span class="number">100</span>)); + } +} +</code></pre></div> +</section></div></main><div id="rustdoc-vars" data-root-path="../../../" data-current-crate="rand" data-themes="ayu,dark,light" data-resource-suffix="" data-rustdoc-version="1.66.0 (69f9c33d7 2022-12-12) (Arch Linux rust 1:1.66.0-1)" ></div></body></html>
\ No newline at end of file |