abstractlongfpset.html

用JAVA编写的,在做实验的时候留下来的,本来想删的,但是传上来,大家分享吧

<a name="157" href="#157">157</a>     }
<a name="158" href="#158">158</a> 
<a name="159" href="#159">159</a>     <em>/**<em>*</em></em>
<a name="160" href="#160">160</a> <em>     * Make additional space to keep the load under the target</em>
<a name="161" href="#161">161</a> <em>     * loadFactor level.</em>
<a name="162" href="#162">162</a> <em>     * </em>
<a name="163" href="#163">163</a> <em>     * Subclasses may grow or discard entries to satisfy.</em>
<a name="164" href="#164">164</a> <em>     */</em>
<a name="165" href="#165">165</a>     <strong>protected</strong> <strong>abstract</strong> <strong>void</strong> makeSpace();
<a name="166" href="#166">166</a> 
<a name="167" href="#167">167</a>     <em>/**<em>*</em></em>
<a name="168" href="#168">168</a> <em>     * Set the stored value at the given slot.</em>
<a name="169" href="#169">169</a> <em>     *</em>
<a name="170" href="#170">170</a> <em>     * @param i the slot index</em>
<a name="171" href="#171">171</a> <em>     * @param l the value to set</em>
<a name="172" href="#172">172</a> <em>     */</em>
<a name="173" href="#173">173</a>     <strong>protected</strong> <strong>abstract</strong> <strong>void</strong> setAt(<strong>long</strong> i, <strong>long</strong> l);
<a name="174" href="#174">174</a> 
<a name="175" href="#175">175</a>     <em>/**<em>* </em></em>
<a name="176" href="#176">176</a> <em>     * Get the stored value at the given slot.</em>
<a name="177" href="#177">177</a> <em>     *</em>
<a name="178" href="#178">178</a> <em>     * @param i the slot index</em>
<a name="179" href="#179">179</a> <em>     * @return The stored value at the given slot.</em>
<a name="180" href="#180">180</a> <em>     */</em>
<a name="181" href="#181">181</a>     <strong>protected</strong> <strong>abstract</strong> <strong>long</strong> getAt(<strong>long</strong> i);
<a name="182" href="#182">182</a> 
<a name="183" href="#183">183</a>     <em>/**<em>* </em></em>
<a name="184" href="#184">184</a> <em>     * Given a value, check the store for its existence. If it exists, it</em>
<a name="185" href="#185">185</a> <em>     * will return the index where the value resides.  Otherwise it return</em>
<a name="186" href="#186">186</a> <em>     * an encoded index, which is a possible storage location for the value.</em>
<a name="187" href="#187">187</a> <em>     *</em>
<a name="188" href="#188">188</a> <em>     * &lt;p>Note, if we have a loading factor less than 1.0, there should always</em>
<a name="189" href="#189">189</a> <em>     * be an empty location where we can store the value</em>
<a name="190" href="#190">190</a> <em>     *</em>
<a name="191" href="#191">191</a> <em>     * @param val the fingerprint value to check for</em>
<a name="192" href="#192">192</a> <em>     * @return The (positive) index where the value already resides,</em>
<a name="193" href="#193">193</a> <em>     * or an empty index where it could be inserted (encoded as a</em>
<a name="194" href="#194">194</a> <em>     * negative number).</em>
<a name="195" href="#195">195</a> <em>     */</em>
<a name="196" href="#196">196</a>     <strong>private</strong> <strong>long</strong> indexFor(<strong>long</strong> val) {
<a name="197" href="#197">197</a>         <strong>long</strong> candidateIndex = startIndexFor(val);
<a name="198" href="#198">198</a>         <strong>while</strong> (<strong>true</strong>) {
<a name="199" href="#199">199</a>             <strong>if</strong> (getSlotState(candidateIndex) &lt; 0) {
<a name="200" href="#200">200</a>                 <em class="comment">// slot empty; return negative number encoding index</em>
<a name="201" href="#201">201</a>                 <strong>return</strong> asEmptySlot(candidateIndex);
<a name="202" href="#202">202</a>             }
<a name="203" href="#203">203</a>             <strong>if</strong> (getAt(candidateIndex) == val) {
<a name="204" href="#204">204</a>                 <em class="comment">// already present; return positive index</em>
<a name="205" href="#205">205</a>                 <strong>return</strong> candidateIndex;
<a name="206" href="#206">206</a>             }
<a name="207" href="#207">207</a>             candidateIndex++;
<a name="208" href="#208">208</a>             <strong>if</strong> (candidateIndex == 1 &lt;&lt; capacityPowerOfTwo) {
<a name="209" href="#209">209</a>                 candidateIndex = 0; <em class="comment">// wraparound</em>
<a name="210" href="#210">210</a>             }
<a name="211" href="#211">211</a>         }
<a name="212" href="#212">212</a>     }
<a name="213" href="#213">213</a> 
<a name="214" href="#214">214</a>     <em>/**<em>*</em></em>
<a name="215" href="#215">215</a> <em>     * Return the recommended storage index for the given value.</em>
<a name="216" href="#216">216</a> <em>     * Assumes values are already well-distributed; merely uses</em>
<a name="217" href="#217">217</a> <em>     * high-order bits.</em>
<a name="218" href="#218">218</a> <em>     *</em>
<a name="219" href="#219">219</a> <em>     * @param val</em>
<a name="220" href="#220">220</a> <em>     * @return The recommended storage index for the given value.</em>
<a name="221" href="#221">221</a> <em>     */</em>
<a name="222" href="#222">222</a>     <strong>private</strong> <strong>long</strong> startIndexFor(<strong>long</strong> val) {
<a name="223" href="#223">223</a>         <strong>return</strong> (val >>> (64 - capacityPowerOfTwo));
<a name="224" href="#224">224</a>     }
<a name="225" href="#225">225</a> 
<a name="226" href="#226">226</a>     <strong>public</strong> <strong>boolean</strong> remove(<strong>long</strong> l) {
<a name="227" href="#227">227</a>         <strong>long</strong> i = indexFor(l);
<a name="228" href="#228">228</a>         <strong>if</strong> (!slotHasData(i)) {
<a name="229" href="#229">229</a>             <em class="comment">// not present, not changed</em>
<a name="230" href="#230">230</a>             <strong>return</strong> false;
<a name="231" href="#231">231</a>         }
<a name="232" href="#232">232</a>         removeAt(i);
<a name="233" href="#233">233</a>         <strong>return</strong> <strong>true</strong>;
<a name="234" href="#234">234</a>     }
<a name="235" href="#235">235</a> 
<a name="236" href="#236">236</a>     <em>/**<em>*</em></em>
<a name="237" href="#237">237</a> <em>     * Remove the value at the given index, relocating its</em>
<a name="238" href="#238">238</a> <em>     * successors as necessary.</em>
<a name="239" href="#239">239</a> <em>     *</em>
<a name="240" href="#240">240</a> <em>     *  @param index</em>
<a name="241" href="#241">241</a> <em>     */</em>
<a name="242" href="#242">242</a>     <strong>protected</strong> <strong>void</strong> removeAt(<strong>long</strong> index) {
<a name="243" href="#243">243</a>         count--;
<a name="244" href="#244">244</a>         clearAt(index);
<a name="245" href="#245">245</a>         <strong>long</strong> probeIndex = index + 1;
<a name="246" href="#246">246</a>         <strong>while</strong> (<strong>true</strong>) {
<a name="247" href="#247">247</a>             <strong>if</strong> (probeIndex == 1 &lt;&lt; capacityPowerOfTwo) {
<a name="248" href="#248">248</a>                 probeIndex = 0; <em class="comment">//wraparound</em>
<a name="249" href="#249">249</a>             }
<a name="250" href="#250">250</a>             <strong>if</strong> (getSlotState(probeIndex) &lt; 0) {
<a name="251" href="#251">251</a>                 <em class="comment">// vacant</em>
<a name="252" href="#252">252</a>                 <strong>break</strong>;
<a name="253" href="#253">253</a>             }
<a name="254" href="#254">254</a>             <strong>long</strong> val = getAt(probeIndex);
<a name="255" href="#255">255</a>             <strong>long</strong> newIndex = indexFor(val);
<a name="256" href="#256">256</a>             <strong>if</strong> (newIndex != probeIndex) {
<a name="257" href="#257">257</a>                 <em class="comment">// value must shift down</em>
<a name="258" href="#258">258</a>                 newIndex = asDataSlot(newIndex); <em class="comment">// positivize</em>
<a name="259" href="#259">259</a>                 relocate(val, probeIndex, newIndex);
<a name="260" href="#260">260</a>             }
<a name="261" href="#261">261</a>             probeIndex++;
<a name="262" href="#262">262</a>         }
<a name="263" href="#263">263</a>     }
<a name="264" href="#264">264</a> 
<a name="265" href="#265">265</a>     <strong>protected</strong> <strong>abstract</strong> <strong>void</strong> clearAt(<strong>long</strong> index);
<a name="266" href="#266">266</a> 
<a name="267" href="#267">267</a>     <strong>protected</strong> <strong>abstract</strong> <strong>void</strong> relocate(<strong>long</strong> value, <strong>long</strong> fromIndex, <strong>long</strong> toIndex);
<a name="268" href="#268">268</a> 
<a name="269" href="#269">269</a>     <em>/**<em>*</em></em>
<a name="270" href="#270">270</a> <em>     * Low-cost, non-definitive (except when true) contains</em>
<a name="271" href="#271">271</a> <em>     * test. Default answer of false is acceptable.</em>
<a name="272" href="#272">272</a> <em>     *</em>
<a name="273" href="#273">273</a> <em>     * @see org.archive.util.fingerprint.LongFPSet#quickContains(long)</em>
<a name="274" href="#274">274</a> <em>     */</em>
<a name="275" href="#275">275</a>     <strong>public</strong> <strong>boolean</strong> quickContains(<strong>long</strong> fp) {
<a name="276" href="#276">276</a>         <strong>return</strong> false;
<a name="277" href="#277">277</a>     }
<a name="278" href="#278">278</a> 
<a name="279" href="#279">279</a>     <em>/**<em>*</em></em>
<a name="280" href="#280">280</a> <em>     * given a slot index, which could or could not be empty, return it as</em>
<a name="281" href="#281">281</a> <em>     * a slot index indicating an non-empty slot</em>
<a name="282" href="#282">282</a> <em>     *</em>
<a name="283" href="#283">283</a> <em>     * @param index the slot index to convert</em>
<a name="284" href="#284">284</a> <em>     * @return the index, converted to represent an slot with data</em>
<a name="285" href="#285">285</a> <em>     */</em>
<a name="286" href="#286">286</a>     <strong>private</strong> <strong>long</strong> asDataSlot(<strong>final</strong> <strong>long</strong> index) {
<a name="287" href="#287">287</a>         <strong>if</strong> (slotHasData(index)) { <em class="comment">// slot already has data</em>
<a name="288" href="#288">288</a>             <strong>return</strong> index;
<a name="289" href="#289">289</a>         }
<a name="290" href="#290">290</a>         <strong>return</strong> - (index + 1);
<a name="291" href="#291">291</a>     }
<a name="292" href="#292">292</a> 
<a name="293" href="#293">293</a>     <em>/**<em>* </em></em>
<a name="294" href="#294">294</a> <em>     * Given a slot index, which could or could not be empty, return it as</em>
<a name="295" href="#295">295</a> <em>     * a slot index indicating an empty slot</em>
<a name="296" href="#296">296</a> <em>     * @param index the slot index to convert</em>
<a name="297" href="#297">297</a> <em>     * @return the index, converted to represent an empty slot</em>
<a name="298" href="#298">298</a> <em>     */</em>
<a name="299" href="#299">299</a>     <strong>private</strong> <strong>long</strong> asEmptySlot(<strong>final</strong> <strong>long</strong> index) {
<a name="300" href="#300">300</a>         <strong>if</strong> (!slotHasData(index)) { <em class="comment">// already empty slot</em>
<a name="301" href="#301">301</a>             <strong>return</strong> index;
<a name="302" href="#302">302</a>         }
<a name="303" href="#303">303</a>         <strong>return</strong> -index - 1;
<a name="304" href="#304">304</a>     }
<a name="305" href="#305">305</a> 
<a name="306" href="#306">306</a>     <em>/**<em>* </em></em>
<a name="307" href="#307">307</a> <em>     * Does this index represent a slot with data?</em>
<a name="308" href="#308">308</a> <em>     *</em>
<a name="309" href="#309">309</a> <em>     * @param index the index to check</em>
<a name="310" href="#310">310</a> <em>     * @return &lt;code>true&lt;/code> if the slot has data</em>
<a name="311" href="#311">311</a> <em>     */</em>
<a name="312" href="#312">312</a>     <strong>private</strong> <strong>boolean</strong> slotHasData(<strong>final</strong> <strong>long</strong> index) {
<a name="313" href="#313">313</a>         <strong>return</strong> index >= 0;
<a name="314" href="#314">314</a>     }
<a name="315" href="#315">315</a> }
</pre>
<hr/><div id="footer">This page was automatically generated by <a href="http://maven.apache.org/">Maven</a></div></body>
</html>