diff options
| author | garhve <git@garhve.com> | 2022-12-20 11:07:35 +0800 |
|---|---|---|
| committer | garhve <git@garhve.com> | 2022-12-20 11:07:35 +0800 |
| commit | b5aa889f7fced8ba2cc1698ae9696d7bd0ca8ab5 (patch) | |
| tree | 6fb532d8da57cf502b2a06844a743bf12789306a /rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq | |
| parent | 369d11587339ce74f8ebc76f2607fe55545eaf7d (diff) | |
remove compiled binary
Diffstat (limited to 'rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq')
2 files changed, 0 insertions, 4074 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 deleted file mode 100644 index 9f59f7f..0000000 --- a/rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq/index.rs.html +++ /dev/null @@ -1,1359 +0,0 @@ -<!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 deleted file mode 100644 index 99cd32d..0000000 --- a/rust/theBook/chapter-2-guessing-game/guessing_game/target/doc/src/rand/seq/mod.rs.html +++ /dev/null @@ -1,2715 +0,0 @@ -<!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 |