| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| <html xmlns="http://www.w3.org/1999/xhtml"> |
| <head> |
| <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> |
| <meta http-equiv="X-UA-Compatible" content="IE=9"/> |
| <meta name="generator" content="Doxygen 1.9.1"/> |
| <meta name="viewport" content="width=device-width, initial-scale=1"/> |
| <title>datasketches-cpp: count/include/count_min.hpp Source File</title> |
| <link href="tabs.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="jquery.js"></script> |
| <script type="text/javascript" src="dynsections.js"></script> |
| <link href="search/search.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="search/searchdata.js"></script> |
| <script type="text/javascript" src="search/search.js"></script> |
| <link href="doxygen.css" rel="stylesheet" type="text/css" /> |
| </head> |
| <body> |
| <div id="top"><!-- do not remove this div, it is closed by doxygen! --> |
| <div id="titlearea"> |
| <table cellspacing="0" cellpadding="0"> |
| <tbody> |
| <tr style="height: 56px;"> |
| <td id="projectalign" style="padding-left: 0.5em;"> |
| <div id="projectname">datasketches-cpp |
| </div> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| </div> |
| <!-- end header part --> |
| <!-- Generated by Doxygen 1.9.1 --> |
| <script type="text/javascript"> |
| /* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&dn=gpl-2.0.txt GPL-v2 */ |
| var searchBox = new SearchBox("searchBox", "search",false,'Search','.html'); |
| /* @license-end */ |
| </script> |
| <script type="text/javascript" src="menudata.js"></script> |
| <script type="text/javascript" src="menu.js"></script> |
| <script type="text/javascript"> |
| /* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&dn=gpl-2.0.txt GPL-v2 */ |
| $(function() { |
| initMenu('',true,false,'search.php','Search'); |
| $(document).ready(function() { init_search(); }); |
| }); |
| /* @license-end */</script> |
| <div id="main-nav"></div> |
| <!-- window showing the filter options --> |
| <div id="MSearchSelectWindow" |
| onmouseover="return searchBox.OnSearchSelectShow()" |
| onmouseout="return searchBox.OnSearchSelectHide()" |
| onkeydown="return searchBox.OnSearchSelectKey(event)"> |
| </div> |
| |
| <!-- iframe showing the search results (closed by default) --> |
| <div id="MSearchResultsWindow"> |
| <iframe src="javascript:void(0)" frameborder="0" |
| name="MSearchResults" id="MSearchResults"> |
| </iframe> |
| </div> |
| |
| <div id="nav-path" class="navpath"> |
| <ul> |
| <li class="navelem"><a class="el" href="dir_2629d1132294f29f2b0f1e3bcedeca02.html">count</a></li><li class="navelem"><a class="el" href="dir_11a63523d45f2cb33b1e510397fbe77e.html">include</a></li> </ul> |
| </div> |
| </div><!-- top --> |
| <div class="header"> |
| <div class="headertitle"> |
| <div class="title">count_min.hpp</div> </div> |
| </div><!--header--> |
| <div class="contents"> |
| <div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno"> 1</span> <span class="comment">/*</span></div> |
| <div class="line"><a name="l00002"></a><span class="lineno"> 2</span> <span class="comment"> * Licensed to the Apache Software Foundation (ASF) under one</span></div> |
| <div class="line"><a name="l00003"></a><span class="lineno"> 3</span> <span class="comment"> * or more contributor license agreements. See the NOTICE file</span></div> |
| <div class="line"><a name="l00004"></a><span class="lineno"> 4</span> <span class="comment"> * distributed with this work for additional information</span></div> |
| <div class="line"><a name="l00005"></a><span class="lineno"> 5</span> <span class="comment"> * regarding copyright ownership. The ASF licenses this file</span></div> |
| <div class="line"><a name="l00006"></a><span class="lineno"> 6</span> <span class="comment"> * to you under the Apache License, Version 2.0 (the</span></div> |
| <div class="line"><a name="l00007"></a><span class="lineno"> 7</span> <span class="comment"> * "License"); you may not use this file except in compliance</span></div> |
| <div class="line"><a name="l00008"></a><span class="lineno"> 8</span> <span class="comment"> * with the License. You may obtain a copy of the License at</span></div> |
| <div class="line"><a name="l00009"></a><span class="lineno"> 9</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00010"></a><span class="lineno"> 10</span> <span class="comment"> * http://www.apache.org/licenses/LICENSE-2.0</span></div> |
| <div class="line"><a name="l00011"></a><span class="lineno"> 11</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00012"></a><span class="lineno"> 12</span> <span class="comment"> * Unless required by applicable law or agreed to in writing,</span></div> |
| <div class="line"><a name="l00013"></a><span class="lineno"> 13</span> <span class="comment"> * software distributed under the License is distributed on an</span></div> |
| <div class="line"><a name="l00014"></a><span class="lineno"> 14</span> <span class="comment"> * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY</span></div> |
| <div class="line"><a name="l00015"></a><span class="lineno"> 15</span> <span class="comment"> * KIND, either express or implied. See the License for the</span></div> |
| <div class="line"><a name="l00016"></a><span class="lineno"> 16</span> <span class="comment"> * specific language governing permissions and limitations</span></div> |
| <div class="line"><a name="l00017"></a><span class="lineno"> 17</span> <span class="comment"> * under the License.</span></div> |
| <div class="line"><a name="l00018"></a><span class="lineno"> 18</span> <span class="comment"> */</span></div> |
| <div class="line"><a name="l00019"></a><span class="lineno"> 19</span>  </div> |
| <div class="line"><a name="l00020"></a><span class="lineno"> 20</span> <span class="preprocessor">#ifndef COUNT_MIN_HPP_</span></div> |
| <div class="line"><a name="l00021"></a><span class="lineno"> 21</span> <span class="preprocessor">#define COUNT_MIN_HPP_</span></div> |
| <div class="line"><a name="l00022"></a><span class="lineno"> 22</span>  </div> |
| <div class="line"><a name="l00023"></a><span class="lineno"> 23</span> <span class="preprocessor">#include <iterator></span></div> |
| <div class="line"><a name="l00024"></a><span class="lineno"> 24</span> <span class="preprocessor">#include "common_defs.hpp"</span></div> |
| <div class="line"><a name="l00025"></a><span class="lineno"> 25</span>  </div> |
| <div class="line"><a name="l00026"></a><span class="lineno"> 26</span> <span class="keyword">namespace </span><a class="code" href="namespacedatasketches.html">datasketches</a> {</div> |
| <div class="line"><a name="l00027"></a><span class="lineno"> 27</span>  </div> |
| <div class="line"><a name="l00035"></a><span class="lineno"> 35</span> <span class="keyword">template</span> <<span class="keyword">typename</span> W,</div> |
| <div class="line"><a name="l00036"></a><span class="lineno"> 36</span>  <span class="keyword">typename</span> Allocator = std::allocator<W>></div> |
| <div class="line"><a name="l00037"></a><span class="lineno"><a class="line" href="classdatasketches_1_1count__min__sketch.html"> 37</a></span> <span class="keyword">class </span><a class="code" href="classdatasketches_1_1count__min__sketch.html">count_min_sketch</a>{</div> |
| <div class="line"><a name="l00038"></a><span class="lineno"> 38</span>  static_assert(std::is_arithmetic<W>::value, <span class="stringliteral">"Arithmetic type expected"</span>);</div> |
| <div class="line"><a name="l00039"></a><span class="lineno"> 39</span> <span class="keyword">public</span>:</div> |
| <div class="line"><a name="l00040"></a><span class="lineno"> 40</span>  <span class="keyword">using</span> allocator_type = Allocator;</div> |
| <div class="line"><a name="l00041"></a><span class="lineno"> 41</span>  <span class="keyword">using</span> const_iterator = <span class="keyword">typename</span> std::vector<W, Allocator>::const_iterator;</div> |
| <div class="line"><a name="l00042"></a><span class="lineno"> 42</span>  </div> |
| <div class="line"><a name="l00053"></a><span class="lineno"> 53</span>  <a class="code" href="classdatasketches_1_1count__min__sketch.html#a8dbb00b2bf984b434482e3da006e2238">count_min_sketch</a>(uint8_t num_hashes, uint32_t num_buckets, uint64_t seed = DEFAULT_SEED, <span class="keyword">const</span> Allocator& allocator = Allocator());</div> |
| <div class="line"><a name="l00054"></a><span class="lineno"> 54</span>  </div> |
| <div class="line"><a name="l00058"></a><span class="lineno"> 58</span>  uint8_t <a class="code" href="classdatasketches_1_1count__min__sketch.html#a6bd30e22135f7abd37d5b2b45d577d0c">get_num_hashes</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00059"></a><span class="lineno"> 59</span>  </div> |
| <div class="line"><a name="l00063"></a><span class="lineno"> 63</span>  uint32_t <a class="code" href="classdatasketches_1_1count__min__sketch.html#a56843138b87eb57c033f4ad26d8eb146">get_num_buckets</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00064"></a><span class="lineno"> 64</span>  </div> |
| <div class="line"><a name="l00068"></a><span class="lineno"> 68</span>  uint64_t <a class="code" href="classdatasketches_1_1count__min__sketch.html#a9004656ac2e34c35d8a7a0773285385a">get_seed</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00069"></a><span class="lineno"> 69</span>  </div> |
| <div class="line"><a name="l00075"></a><span class="lineno"> 75</span>  <span class="keywordtype">double</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#a5356c92bb629951dcb748e51677a3886">get_relative_error</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00076"></a><span class="lineno"> 76</span>  </div> |
| <div class="line"><a name="l00081"></a><span class="lineno"> 81</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a68bf5133e42650cdfe20a7916037ab4b">get_total_weight</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00082"></a><span class="lineno"> 82</span>  </div> |
| <div class="line"><a name="l00093"></a><span class="lineno"> 93</span>  <span class="keyword">static</span> uint32_t <a class="code" href="classdatasketches_1_1count__min__sketch.html#a2909753e9106aad95a740580c3865d98">suggest_num_buckets</a>(<span class="keywordtype">double</span> relative_error);</div> |
| <div class="line"><a name="l00094"></a><span class="lineno"> 94</span>  </div> |
| <div class="line"><a name="l00104"></a><span class="lineno"> 104</span>  <span class="keyword">static</span> uint8_t <a class="code" href="classdatasketches_1_1count__min__sketch.html#a40b2f93d707496a57b16679be4a58a2f">suggest_num_hashes</a>(<span class="keywordtype">double</span> confidence);</div> |
| <div class="line"><a name="l00105"></a><span class="lineno"> 105</span>  </div> |
| <div class="line"><a name="l00112"></a><span class="lineno"> 112</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a8c7a3314a5665e9d244acc5c1b5c43d6">get_estimate</a>(uint64_t item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00113"></a><span class="lineno"> 113</span>  </div> |
| <div class="line"><a name="l00120"></a><span class="lineno"> 120</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a8c7a3314a5665e9d244acc5c1b5c43d6">get_estimate</a>(int64_t item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00121"></a><span class="lineno"> 121</span>  </div> |
| <div class="line"><a name="l00128"></a><span class="lineno"> 128</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a8c7a3314a5665e9d244acc5c1b5c43d6">get_estimate</a>(<span class="keyword">const</span> std::string& item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00129"></a><span class="lineno"> 129</span>  </div> |
| <div class="line"><a name="l00138"></a><span class="lineno"> 138</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a8c7a3314a5665e9d244acc5c1b5c43d6">get_estimate</a>(<span class="keyword">const</span> <span class="keywordtype">void</span>* item, <span class="keywordtype">size_t</span> size) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00139"></a><span class="lineno"> 139</span>  </div> |
| <div class="line"><a name="l00147"></a><span class="lineno"> 147</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a70356e097d2d952c8f0d843087556b52">get_upper_bound</a>(<span class="keyword">const</span> <span class="keywordtype">void</span>* item, <span class="keywordtype">size_t</span> size) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00148"></a><span class="lineno"> 148</span>  </div> |
| <div class="line"><a name="l00155"></a><span class="lineno"> 155</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a70356e097d2d952c8f0d843087556b52">get_upper_bound</a>(int64_t item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00156"></a><span class="lineno"> 156</span>  </div> |
| <div class="line"><a name="l00163"></a><span class="lineno"> 163</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a70356e097d2d952c8f0d843087556b52">get_upper_bound</a>(uint64_t item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00164"></a><span class="lineno"> 164</span>  </div> |
| <div class="line"><a name="l00171"></a><span class="lineno"> 171</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a70356e097d2d952c8f0d843087556b52">get_upper_bound</a>(<span class="keyword">const</span> std::string& item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00172"></a><span class="lineno"> 172</span>  </div> |
| <div class="line"><a name="l00180"></a><span class="lineno"> 180</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a7d1d4341a397ae681f03e4dc00423391">get_lower_bound</a>(<span class="keyword">const</span> <span class="keywordtype">void</span>* item, <span class="keywordtype">size_t</span> size) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00181"></a><span class="lineno"> 181</span>  </div> |
| <div class="line"><a name="l00188"></a><span class="lineno"> 188</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a7d1d4341a397ae681f03e4dc00423391">get_lower_bound</a>(int64_t item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00189"></a><span class="lineno"> 189</span>  </div> |
| <div class="line"><a name="l00196"></a><span class="lineno"> 196</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a7d1d4341a397ae681f03e4dc00423391">get_lower_bound</a>(uint64_t item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00197"></a><span class="lineno"> 197</span>  </div> |
| <div class="line"><a name="l00204"></a><span class="lineno"> 204</span>  W <a class="code" href="classdatasketches_1_1count__min__sketch.html#a7d1d4341a397ae681f03e4dc00423391">get_lower_bound</a>(<span class="keyword">const</span> std::string& item) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00205"></a><span class="lineno"> 205</span>  </div> |
| <div class="line"><a name="l00214"></a><span class="lineno"> 214</span>  <span class="keywordtype">void</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#adf1fad8a6035d808e06ea84fbffb6a86">update</a>(<span class="keyword">const</span> <span class="keywordtype">void</span>* item, <span class="keywordtype">size_t</span> size, W weight);</div> |
| <div class="line"><a name="l00215"></a><span class="lineno"> 215</span>  </div> |
| <div class="line"><a name="l00221"></a><span class="lineno"> 221</span>  <span class="keywordtype">void</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#adf1fad8a6035d808e06ea84fbffb6a86">update</a>(uint64_t item, W weight = 1);</div> |
| <div class="line"><a name="l00222"></a><span class="lineno"> 222</span>  </div> |
| <div class="line"><a name="l00228"></a><span class="lineno"> 228</span>  <span class="keywordtype">void</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#adf1fad8a6035d808e06ea84fbffb6a86">update</a>(int64_t item, W weight = 1);</div> |
| <div class="line"><a name="l00229"></a><span class="lineno"> 229</span>  </div> |
| <div class="line"><a name="l00235"></a><span class="lineno"> 235</span>  <span class="keywordtype">void</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#adf1fad8a6035d808e06ea84fbffb6a86">update</a>(<span class="keyword">const</span> std::string& item, W weight = 1);</div> |
| <div class="line"><a name="l00236"></a><span class="lineno"> 236</span>  </div> |
| <div class="line"><a name="l00241"></a><span class="lineno"> 241</span>  <span class="keywordtype">void</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#ab53a0403cb869426c5eb6a8c70ca3e7f">merge</a>(<span class="keyword">const</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html">count_min_sketch</a>& other_sketch);</div> |
| <div class="line"><a name="l00242"></a><span class="lineno"> 242</span>  </div> |
| <div class="line"><a name="l00249"></a><span class="lineno"> 249</span>  <span class="keywordtype">bool</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#a5a2b7a58dc85678d08752945ff655362">is_empty</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00250"></a><span class="lineno"> 250</span>  </div> |
| <div class="line"><a name="l00255"></a><span class="lineno"> 255</span>  string<Allocator> <a class="code" href="classdatasketches_1_1count__min__sketch.html#aed372241c10ffd041bee85602edb199a">to_string</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00256"></a><span class="lineno"> 256</span>  </div> |
| <div class="line"><a name="l00262"></a><span class="lineno"> 262</span>  const_iterator <a class="code" href="classdatasketches_1_1count__min__sketch.html#afa7956f1d2c14624431b3fb7cd976f63">begin</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00263"></a><span class="lineno"> 263</span>  </div> |
| <div class="line"><a name="l00270"></a><span class="lineno"> 270</span>  const_iterator <a class="code" href="classdatasketches_1_1count__min__sketch.html#a2c2da097065929e9f586049b19039fc9">end</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00271"></a><span class="lineno"> 271</span>  </div> |
| <div class="line"><a name="l00272"></a><span class="lineno"> 272</span>  <span class="comment">/*</span></div> |
| <div class="line"><a name="l00273"></a><span class="lineno"> 273</span> <span class="comment"> * The serialized sketch binary form has the following structure</span></div> |
| <div class="line"><a name="l00274"></a><span class="lineno"> 274</span> <span class="comment"> * Byte 0:</span></div> |
| <div class="line"><a name="l00275"></a><span class="lineno"> 275</span> <span class="comment"> * 1 - if and only if the sketch is empty</span></div> |
| <div class="line"><a name="l00276"></a><span class="lineno"> 276</span> <span class="comment"> * 0 - otherwise</span></div> |
| <div class="line"><a name="l00277"></a><span class="lineno"> 277</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00278"></a><span class="lineno"> 278</span> <span class="comment"> * Byte 1 (serial version), byte 2 (family id), byte 3 (flags):</span></div> |
| <div class="line"><a name="l00279"></a><span class="lineno"> 279</span> <span class="comment"> * 00000001 - default for now.</span></div> |
| <div class="line"><a name="l00280"></a><span class="lineno"> 280</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00281"></a><span class="lineno"> 281</span> <span class="comment"> * Bytes 4 - 7:</span></div> |
| <div class="line"><a name="l00282"></a><span class="lineno"> 282</span> <span class="comment"> * uint8_t zero corresponding to ``empty''</span></div> |
| <div class="line"><a name="l00283"></a><span class="lineno"> 283</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00284"></a><span class="lineno"> 284</span> <span class="comment"> * Byte 8:</span></div> |
| <div class="line"><a name="l00285"></a><span class="lineno"> 285</span> <span class="comment"> * uint_8 for number of hash functions</span></div> |
| <div class="line"><a name="l00286"></a><span class="lineno"> 286</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00287"></a><span class="lineno"> 287</span> <span class="comment"> * Bytes 9, 13</span></div> |
| <div class="line"><a name="l00288"></a><span class="lineno"> 288</span> <span class="comment"> * 4 bytes : uint32 for number of buckets.</span></div> |
| <div class="line"><a name="l00289"></a><span class="lineno"> 289</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00290"></a><span class="lineno"> 290</span> <span class="comment"> * Bytes 14, 15:</span></div> |
| <div class="line"><a name="l00291"></a><span class="lineno"> 291</span> <span class="comment"> * seed_hash</span></div> |
| <div class="line"><a name="l00292"></a><span class="lineno"> 292</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00293"></a><span class="lineno"> 293</span> <span class="comment"> * Byte 16:</span></div> |
| <div class="line"><a name="l00294"></a><span class="lineno"> 294</span> <span class="comment"> * uint8_t zero corresponding to ``empty''</span></div> |
| <div class="line"><a name="l00295"></a><span class="lineno"> 295</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00296"></a><span class="lineno"> 296</span> <span class="comment"> * All remaining bytes from 17-24 follow the pattern of</span></div> |
| <div class="line"><a name="l00297"></a><span class="lineno"> 297</span> <span class="comment"> * Bytes 17-24:</span></div> |
| <div class="line"><a name="l00298"></a><span class="lineno"> 298</span> <span class="comment"> * Sketch array entry</span></div> |
| <div class="line"><a name="l00299"></a><span class="lineno"> 299</span> <span class="comment"> *</span></div> |
| <div class="line"><a name="l00300"></a><span class="lineno"> 300</span> <span class="comment"></span> </div> |
| <div class="line"><a name="l00301"></a><span class="lineno"> 301</span> <span class="comment"> 0 || 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |</span></div> |
| <div class="line"><a name="l00302"></a><span class="lineno"> 302</span> <span class="comment"> ||is_empty|ser__ver|familyId| flags |xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx|</span></div> |
| <div class="line"><a name="l00303"></a><span class="lineno"> 303</span> <span class="comment"></span> </div> |
| <div class="line"><a name="l00304"></a><span class="lineno"> 304</span> <span class="comment"> 1 || 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |</span></div> |
| <div class="line"><a name="l00305"></a><span class="lineno"> 305</span> <span class="comment"> ||---------- _num_buckets -----------|num_hash|__seed__ __hash__|xxxxxxxx|</span></div> |
| <div class="line"><a name="l00306"></a><span class="lineno"> 306</span> <span class="comment"></span> </div> |
| <div class="line"><a name="l00307"></a><span class="lineno"> 307</span> <span class="comment"> 2 || 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |</span></div> |
| <div class="line"><a name="l00308"></a><span class="lineno"> 308</span> <span class="comment"> ||---------------------------- total weight ----------------------------|</span></div> |
| <div class="line"><a name="l00309"></a><span class="lineno"> 309</span> <span class="comment"></span> </div> |
| <div class="line"><a name="l00310"></a><span class="lineno"> 310</span> <span class="comment"> 3 || 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |</span></div> |
| <div class="line"><a name="l00311"></a><span class="lineno"> 311</span> <span class="comment"> ||---------------------------- sketch entries ---------------------------|</span></div> |
| <div class="line"><a name="l00312"></a><span class="lineno"> 312</span> <span class="comment"> ...</span></div> |
| <div class="line"><a name="l00313"></a><span class="lineno"> 313</span> <span class="comment"></span> </div> |
| <div class="line"><a name="l00314"></a><span class="lineno"> 314</span> <span class="comment"> */</span></div> |
| <div class="line"><a name="l00315"></a><span class="lineno"> 315</span>  </div> |
| <div class="line"><a name="l00316"></a><span class="lineno"> 316</span>  </div> |
| <div class="line"><a name="l00321"></a><span class="lineno"> 321</span>  <span class="keywordtype">size_t</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#af900f66ecee1991981f6f33c52a10bc9">get_serialized_size_bytes</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00322"></a><span class="lineno"> 322</span>  </div> |
| <div class="line"><a name="l00327"></a><span class="lineno"> 327</span>  <span class="keywordtype">void</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html#a1bcdd98ee6e6eb9b501b8dc5de5e8924">serialize</a>(std::ostream& os) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00328"></a><span class="lineno"> 328</span>  </div> |
| <div class="line"><a name="l00329"></a><span class="lineno"> 329</span>  <span class="comment">// This is a convenience alias for users</span></div> |
| <div class="line"><a name="l00330"></a><span class="lineno"> 330</span>  <span class="comment">// The type returned by the following serialize method</span></div> |
| <div class="line"><a name="l00331"></a><span class="lineno"> 331</span>  <span class="keyword">using</span> vector_bytes = std::vector<uint8_t, typename std::allocator_traits<Allocator>::template rebind_alloc<uint8_t>>;</div> |
| <div class="line"><a name="l00332"></a><span class="lineno"> 332</span>  </div> |
| <div class="line"><a name="l00340"></a><span class="lineno"> 340</span>  vector_bytes <a class="code" href="classdatasketches_1_1count__min__sketch.html#a1bcdd98ee6e6eb9b501b8dc5de5e8924">serialize</a>(<span class="keywordtype">unsigned</span> header_size_bytes = 0) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00341"></a><span class="lineno"> 341</span>  </div> |
| <div class="line"><a name="l00349"></a><span class="lineno"><a class="line" href="classdatasketches_1_1count__min__sketch.html#a0a9f344e0399b775f82358b8807727af"> 349</a></span>  <span class="keyword">static</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html">count_min_sketch</a> <a class="code" href="classdatasketches_1_1count__min__sketch.html#a0a9f344e0399b775f82358b8807727af">deserialize</a>(std::istream& is, uint64_t seed=DEFAULT_SEED, <span class="keyword">const</span> Allocator& allocator = Allocator());</div> |
| <div class="line"><a name="l00350"></a><span class="lineno"> 350</span>  </div> |
| <div class="line"><a name="l00359"></a><span class="lineno"><a class="line" href="classdatasketches_1_1count__min__sketch.html#afc0d4bcd3c9df114cec65f2332ec626e"> 359</a></span>  <span class="keyword">static</span> <a class="code" href="classdatasketches_1_1count__min__sketch.html">count_min_sketch</a> <a class="code" href="classdatasketches_1_1count__min__sketch.html#afc0d4bcd3c9df114cec65f2332ec626e">deserialize</a>(<span class="keyword">const</span> <span class="keywordtype">void</span>* bytes, <span class="keywordtype">size_t</span> size, uint64_t seed=DEFAULT_SEED, <span class="keyword">const</span> Allocator& allocator = Allocator());</div> |
| <div class="line"><a name="l00360"></a><span class="lineno"> 360</span>  </div> |
| <div class="line"><a name="l00364"></a><span class="lineno"><a class="line" href="classdatasketches_1_1count__min__sketch.html#a6e99c6263568d88f95ca01dc694f1051"> 364</a></span>  allocator_type <a class="code" href="classdatasketches_1_1count__min__sketch.html#a6e99c6263568d88f95ca01dc694f1051">get_allocator</a>() <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00365"></a><span class="lineno"> 365</span>  </div> |
| <div class="line"><a name="l00366"></a><span class="lineno"> 366</span> <span class="keyword">private</span>:</div> |
| <div class="line"><a name="l00367"></a><span class="lineno"> 367</span>  Allocator _allocator;</div> |
| <div class="line"><a name="l00368"></a><span class="lineno"> 368</span>  uint8_t _num_hashes;</div> |
| <div class="line"><a name="l00369"></a><span class="lineno"> 369</span>  uint32_t _num_buckets;</div> |
| <div class="line"><a name="l00370"></a><span class="lineno"> 370</span>  std::vector<W, Allocator> _sketch_array; <span class="comment">// the array stored by the sketch</span></div> |
| <div class="line"><a name="l00371"></a><span class="lineno"> 371</span>  uint64_t _seed;</div> |
| <div class="line"><a name="l00372"></a><span class="lineno"> 372</span>  W _total_weight;</div> |
| <div class="line"><a name="l00373"></a><span class="lineno"> 373</span>  std::vector<uint64_t> hash_seeds;</div> |
| <div class="line"><a name="l00374"></a><span class="lineno"> 374</span>  </div> |
| <div class="line"><a name="l00375"></a><span class="lineno"> 375</span>  <span class="keyword">enum</span> flags {IS_EMPTY};</div> |
| <div class="line"><a name="l00376"></a><span class="lineno"> 376</span>  <span class="keyword">static</span> <span class="keyword">const</span> uint8_t PREAMBLE_LONGS_SHORT = 2; <span class="comment">// Empty -> need second byte for sketch parameters</span></div> |
| <div class="line"><a name="l00377"></a><span class="lineno"> 377</span>  <span class="keyword">static</span> <span class="keyword">const</span> uint8_t PREAMBLE_LONGS_FULL = 3; <span class="comment">// Not empty -> need (at least) third byte for total weight.</span></div> |
| <div class="line"><a name="l00378"></a><span class="lineno"> 378</span>  <span class="keyword">static</span> <span class="keyword">const</span> uint8_t SERIAL_VERSION_1 = 1;</div> |
| <div class="line"><a name="l00379"></a><span class="lineno"> 379</span>  <span class="keyword">static</span> <span class="keyword">const</span> uint8_t FAMILY_ID = 18;</div> |
| <div class="line"><a name="l00380"></a><span class="lineno"> 380</span>  <span class="keyword">static</span> <span class="keyword">const</span> uint8_t NULL_8 = 0;</div> |
| <div class="line"><a name="l00381"></a><span class="lineno"> 381</span>  <span class="keyword">static</span> <span class="keyword">const</span> uint32_t NULL_32 = 0;</div> |
| <div class="line"><a name="l00382"></a><span class="lineno"> 382</span>  </div> |
| <div class="line"><a name="l00389"></a><span class="lineno"> 389</span>  <span class="keyword">static</span> <span class="keywordtype">void</span> check_header_validity(uint8_t preamble_longs, uint8_t serial_version, uint8_t family_id, uint8_t flags_byte);</div> |
| <div class="line"><a name="l00390"></a><span class="lineno"> 390</span>  </div> |
| <div class="line"><a name="l00391"></a><span class="lineno"> 391</span>  <span class="comment">/*</span></div> |
| <div class="line"><a name="l00392"></a><span class="lineno"> 392</span> <span class="comment"> * Obtain the hash values when inserting an item into the sketch.</span></div> |
| <div class="line"><a name="l00393"></a><span class="lineno"> 393</span> <span class="comment"> * @param item pointer to the data item to be inserted into the sketch.</span></div> |
| <div class="line"><a name="l00394"></a><span class="lineno"> 394</span> <span class="comment"> * @param size of the data in bytes</span></div> |
| <div class="line"><a name="l00395"></a><span class="lineno"> 395</span> <span class="comment"> * @return vector of uint64_t which each represent the index to which `value' must update in the sketch</span></div> |
| <div class="line"><a name="l00396"></a><span class="lineno"> 396</span> <span class="comment"> */</span></div> |
| <div class="line"><a name="l00397"></a><span class="lineno"> 397</span>  std::vector<uint64_t> get_hashes(<span class="keyword">const</span> <span class="keywordtype">void</span>* item, <span class="keywordtype">size_t</span> size) <span class="keyword">const</span>;</div> |
| <div class="line"><a name="l00398"></a><span class="lineno"> 398</span>  </div> |
| <div class="line"><a name="l00399"></a><span class="lineno"> 399</span> };</div> |
| <div class="line"><a name="l00400"></a><span class="lineno"> 400</span>  </div> |
| <div class="line"><a name="l00401"></a><span class="lineno"> 401</span> } <span class="comment">/* namespace datasketches */</span></div> |
| <div class="line"><a name="l00402"></a><span class="lineno"> 402</span>  </div> |
| <div class="line"><a name="l00403"></a><span class="lineno"> 403</span> <span class="preprocessor">#include "count_min_impl.hpp"</span></div> |
| <div class="line"><a name="l00404"></a><span class="lineno"> 404</span>  </div> |
| <div class="line"><a name="l00405"></a><span class="lineno"> 405</span> <span class="preprocessor">#endif</span></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html">datasketches::count_min_sketch</a></div><div class="ttdoc">C++ implementation of the CountMin sketch data structure of Cormode and Muthukrishnan.</div><div class="ttdef"><b>Definition:</b> count_min.hpp:37</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a0a9f344e0399b775f82358b8807727af"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a0a9f344e0399b775f82358b8807727af">datasketches::count_min_sketch::deserialize</a></div><div class="ttdeci">static count_min_sketch deserialize(std::istream &is, uint64_t seed=DEFAULT_SEED, const Allocator &allocator=Allocator())</div><div class="ttdoc">This method deserializes a sketch from a given stream.</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a1bcdd98ee6e6eb9b501b8dc5de5e8924"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a1bcdd98ee6e6eb9b501b8dc5de5e8924">datasketches::count_min_sketch::serialize</a></div><div class="ttdeci">void serialize(std::ostream &os) const</div><div class="ttdoc">This method serializes the sketch into a given stream in a binary form.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:270</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a2909753e9106aad95a740580c3865d98"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a2909753e9106aad95a740580c3865d98">datasketches::count_min_sketch::suggest_num_buckets</a></div><div class="ttdeci">static uint32_t suggest_num_buckets(double relative_error)</div><div class="ttdoc">Suggests the number of buckets required to achieve the given relative error.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:86</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a2c2da097065929e9f586049b19039fc9"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a2c2da097065929e9f586049b19039fc9">datasketches::count_min_sketch::end</a></div><div class="ttdeci">const_iterator end() const</div><div class="ttdoc">Iterator pointing to the past-the-end item in the sketch.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:265</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a40b2f93d707496a57b16679be4a58a2f"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a40b2f93d707496a57b16679be4a58a2f">datasketches::count_min_sketch::suggest_num_hashes</a></div><div class="ttdeci">static uint8_t suggest_num_hashes(double confidence)</div><div class="ttdoc">Suggests the number of hash functions required to achieve the given confidence.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:98</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a5356c92bb629951dcb748e51677a3886"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a5356c92bb629951dcb748e51677a3886">datasketches::count_min_sketch::get_relative_error</a></div><div class="ttdeci">double get_relative_error() const</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:76</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a56843138b87eb57c033f4ad26d8eb146"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a56843138b87eb57c033f4ad26d8eb146">datasketches::count_min_sketch::get_num_buckets</a></div><div class="ttdeci">uint32_t get_num_buckets() const</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:66</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a5a2b7a58dc85678d08752945ff655362"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a5a2b7a58dc85678d08752945ff655362">datasketches::count_min_sketch::is_empty</a></div><div class="ttdeci">bool is_empty() const</div><div class="ttdoc">Returns true if this sketch is empty.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:443</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a68bf5133e42650cdfe20a7916037ab4b"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a68bf5133e42650cdfe20a7916037ab4b">datasketches::count_min_sketch::get_total_weight</a></div><div class="ttdeci">W get_total_weight() const</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:81</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a6bd30e22135f7abd37d5b2b45d577d0c"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a6bd30e22135f7abd37d5b2b45d577d0c">datasketches::count_min_sketch::get_num_hashes</a></div><div class="ttdeci">uint8_t get_num_hashes() const</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:61</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a6e99c6263568d88f95ca01dc694f1051"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a6e99c6263568d88f95ca01dc694f1051">datasketches::count_min_sketch::get_allocator</a></div><div class="ttdeci">allocator_type get_allocator() const</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a70356e097d2d952c8f0d843087556b52"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a70356e097d2d952c8f0d843087556b52">datasketches::count_min_sketch::get_upper_bound</a></div><div class="ttdeci">W get_upper_bound(const void *item, size_t size) const</div><div class="ttdoc">Query the sketch for the upper bound of a given item.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:209</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a7d1d4341a397ae681f03e4dc00423391"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a7d1d4341a397ae681f03e4dc00423391">datasketches::count_min_sketch::get_lower_bound</a></div><div class="ttdeci">W get_lower_bound(const void *item, size_t size) const</div><div class="ttdoc">Query the sketch for the lower bound of a given item.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:226</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a8c7a3314a5665e9d244acc5c1b5c43d6"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a8c7a3314a5665e9d244acc5c1b5c43d6">datasketches::count_min_sketch::get_estimate</a></div><div class="ttdeci">W get_estimate(uint64_t item) const</div><div class="ttdoc">Specific get_estimate function for uint64_t type see generic get_estimate function.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:143</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a8dbb00b2bf984b434482e3da006e2238"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a8dbb00b2bf984b434482e3da006e2238">datasketches::count_min_sketch::count_min_sketch</a></div><div class="ttdeci">count_min_sketch(uint8_t num_hashes, uint32_t num_buckets, uint64_t seed=DEFAULT_SEED, const Allocator &allocator=Allocator())</div><div class="ttdoc">Creates an instance of the sketch given parameters _num_hashes, _num_buckets and hash seed,...</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:35</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_a9004656ac2e34c35d8a7a0773285385a"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#a9004656ac2e34c35d8a7a0773285385a">datasketches::count_min_sketch::get_seed</a></div><div class="ttdeci">uint64_t get_seed() const</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:71</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_ab53a0403cb869426c5eb6a8c70ca3e7f"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#ab53a0403cb869426c5eb6a8c70ca3e7f">datasketches::count_min_sketch::merge</a></div><div class="ttdeci">void merge(const count_min_sketch &other_sketch)</div><div class="ttdoc">Merges another count_min_sketch into this count_min_sketch.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:231</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_adf1fad8a6035d808e06ea84fbffb6a86"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#adf1fad8a6035d808e06ea84fbffb6a86">datasketches::count_min_sketch::update</a></div><div class="ttdeci">void update(const void *item, size_t size, W weight)</div><div class="ttdoc">Update this sketch with given data of any type.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:184</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_aed372241c10ffd041bee85602edb199a"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#aed372241c10ffd041bee85602edb199a">datasketches::count_min_sketch::to_string</a></div><div class="ttdeci">string< Allocator > to_string() const</div><div class="ttdoc">Returns a string describing the sketch.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:448</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_af900f66ecee1991981f6f33c52a10bc9"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#af900f66ecee1991981f6f33c52a10bc9">datasketches::count_min_sketch::get_serialized_size_bytes</a></div><div class="ttdeci">size_t get_serialized_size_bytes() const</div><div class="ttdoc">Computes size needed to serialize the current state of the sketch.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:341</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_afa7956f1d2c14624431b3fb7cd976f63"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#afa7956f1d2c14624431b3fb7cd976f63">datasketches::count_min_sketch::begin</a></div><div class="ttdeci">const_iterator begin() const</div><div class="ttdoc">Iterator pointing to the first item in the sketch.</div><div class="ttdef"><b>Definition:</b> count_min_impl.hpp:260</div></div> |
| <div class="ttc" id="aclassdatasketches_1_1count__min__sketch_html_afc0d4bcd3c9df114cec65f2332ec626e"><div class="ttname"><a href="classdatasketches_1_1count__min__sketch.html#afc0d4bcd3c9df114cec65f2332ec626e">datasketches::count_min_sketch::deserialize</a></div><div class="ttdeci">static count_min_sketch deserialize(const void *bytes, size_t size, uint64_t seed=DEFAULT_SEED, const Allocator &allocator=Allocator())</div><div class="ttdoc">This method deserializes a sketch from a given array of bytes.</div></div> |
| <div class="ttc" id="anamespacedatasketches_html"><div class="ttname"><a href="namespacedatasketches.html">datasketches</a></div><div class="ttdoc">DataSketches namespace.</div><div class="ttdef"><b>Definition:</b> binomial_bounds.hpp:38</div></div> |
| </div><!-- fragment --></div><!-- contents --> |
| <!-- start footer part --> |
| <hr class="footer"/><address class="footer"><small> |
| Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.9.1 |
| </small></address> |
| </body> |
| </html> |
