<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://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"/>
<title>CVC3: hash_table.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.7.4 -->
<div id="top">
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">CVC3 <span id="projectnumber">2.4.1</span></div>
</td>
</tr>
</tbody>
</table>
</div>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</span></a></li>
</ul>
</div>
<div class="header">
<div class="headertitle">
<div class="title">hash_table.h</div> </div>
</div>
<div class="contents">
<a href="hash__table_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*****************************************************************************/</span><span class="comment"></span>
<a name="l00002"></a>00002 <span class="comment">/*!</span>
<a name="l00003"></a>00003 <span class="comment"> *\file hash_table.h</span>
<a name="l00004"></a>00004 <span class="comment"> *\brief hash table implementation</span>
<a name="l00005"></a>00005 <span class="comment"> *</span>
<a name="l00006"></a>00006 <span class="comment"> * Author: Alexander Fuchs</span>
<a name="l00007"></a>00007 <span class="comment"> *</span>
<a name="l00008"></a>00008 <span class="comment"> * Created: Thu Oct 19 11:04:00 2006</span>
<a name="l00009"></a>00009 <span class="comment"> *</span>
<a name="l00010"></a>00010 <span class="comment"> * <hr></span>
<a name="l00011"></a>00011 <span class="comment"> *</span>
<a name="l00012"></a>00012 <span class="comment"> * License to use, copy, modify, sell and/or distribute this software</span>
<a name="l00013"></a>00013 <span class="comment"> * and its documentation for any purpose is hereby granted without</span>
<a name="l00014"></a>00014 <span class="comment"> * royalty, subject to the terms and conditions defined in the \ref</span>
<a name="l00015"></a>00015 <span class="comment"> * LICENSE file provided with this distribution.</span>
<a name="l00016"></a>00016 <span class="comment"> * </span>
<a name="l00017"></a>00017 <span class="comment"> * <hr></span>
<a name="l00018"></a>00018 <span class="comment"> */</span>
<a name="l00019"></a>00019 <span class="comment">/*****************************************************************************/</span>
<a name="l00020"></a>00020
<a name="l00021"></a>00021 <span class="comment">/*</span>
<a name="l00022"></a>00022 <span class="comment"> * Copyright (c) 1996,1997</span>
<a name="l00023"></a>00023 <span class="comment"> * Silicon Graphics Computer Systems, Inc.</span>
<a name="l00024"></a>00024 <span class="comment"> *</span>
<a name="l00025"></a>00025 <span class="comment"> * Permission to use, copy, modify, distribute and sell this software</span>
<a name="l00026"></a>00026 <span class="comment"> * and its documentation for any purpose is hereby granted without fee,</span>
<a name="l00027"></a>00027 <span class="comment"> * provided that the above copyright notice appear in all copies and</span>
<a name="l00028"></a>00028 <span class="comment"> * that both that copyright notice and this permission notice appear</span>
<a name="l00029"></a>00029 <span class="comment"> * in supporting documentation. Silicon Graphics makes no</span>
<a name="l00030"></a>00030 <span class="comment"> * representations about the suitability of this software for any</span>
<a name="l00031"></a>00031 <span class="comment"> * purpose. It is provided "as is" without express or implied warranty.</span>
<a name="l00032"></a>00032 <span class="comment"> *</span>
<a name="l00033"></a>00033 <span class="comment"> *</span>
<a name="l00034"></a>00034 <span class="comment"> * Copyright (c) 1994</span>
<a name="l00035"></a>00035 <span class="comment"> * Hewlett-Packard Company</span>
<a name="l00036"></a>00036 <span class="comment"> *</span>
<a name="l00037"></a>00037 <span class="comment"> * Permission to use, copy, modify, distribute and sell this software</span>
<a name="l00038"></a>00038 <span class="comment"> * and its documentation for any purpose is hereby granted without fee,</span>
<a name="l00039"></a>00039 <span class="comment"> * provided that the above copyright notice appear in all copies and</span>
<a name="l00040"></a>00040 <span class="comment"> * that both that copyright notice and this permission notice appear</span>
<a name="l00041"></a>00041 <span class="comment"> * in supporting documentation. Hewlett-Packard Company makes no</span>
<a name="l00042"></a>00042 <span class="comment"> * representations about the suitability of this software for any</span>
<a name="l00043"></a>00043 <span class="comment"> * purpose. It is provided "as is" without express or implied warranty.</span>
<a name="l00044"></a>00044 <span class="comment"> *</span>
<a name="l00045"></a>00045 <span class="comment"> */</span>
<a name="l00046"></a>00046
<a name="l00047"></a>00047 <span class="comment">// this implementation is in essence a subset of the SGI implementation:</span>
<a name="l00048"></a>00048 <span class="comment">// http://www.sgi.com/tech/stl/stl_hashtable.h</span>
<a name="l00049"></a>00049
<a name="l00050"></a>00050 <span class="preprocessor">#ifndef _cvc3__hash__hash_table_h_</span>
<a name="l00051"></a>00051 <span class="preprocessor"></span><span class="preprocessor">#define _cvc3__hash__hash_table_h_</span>
<a name="l00052"></a>00052 <span class="preprocessor"></span>
<a name="l00053"></a>00053 <span class="preprocessor">#include <vector></span>
<a name="l00054"></a>00054 <span class="preprocessor">#include <string></span>
<a name="l00055"></a>00055 <span class="preprocessor">#include <functional></span>
<a name="l00056"></a>00056 <span class="preprocessor">#include <algorithm></span>
<a name="l00057"></a>00057 <span class="preprocessor">#include "<a class="code" href="hash__fun_8h.html" title="hash functions">hash_fun.h</a>"</span>
<a name="l00058"></a>00058 <span class="preprocessor">#include "<a class="code" href="os_8h.html" title="Abstraction over different operating systems.">os.h</a>"</span>
<a name="l00059"></a>00059
<a name="l00060"></a>00060 <span class="comment">// For some reason, including debug.h doesn't work--so redeclare macros here</span>
<a name="l00061"></a>00061
<a name="l00062"></a>00062 <span class="preprocessor">#ifdef _CVC3_DEBUG_MODE</span>
<a name="l00063"></a>00063 <span class="preprocessor"></span><span class="preprocessor">#define DebugAssert(cond, str) if(!(cond)) \</span>
<a name="l00064"></a>00064 <span class="preprocessor"> CVC3::debugError(__FILE__, __LINE__, #cond, str)</span>
<a name="l00065"></a>00065 <span class="preprocessor"></span><span class="keyword">namespace </span>CVC3 {
<a name="l00066"></a>00066 <span class="keyword">extern</span> <a class="code" href="os_8h.html#a0035aac6379df39aa69feba98b2751ba">CVC_DLL</a> <span class="keywordtype">void</span> debugError(<span class="keyword">const</span> std::string& file, <span class="keywordtype">int</span> line,
<a name="l00067"></a>00067 <span class="keyword">const</span> std::string& cond, <span class="keyword">const</span> std::string& msg);
<a name="l00068"></a>00068 }
<a name="l00069"></a>00069 <span class="preprocessor">#else</span>
<a name="l00070"></a><a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">00070</a> <span class="preprocessor"></span><span class="preprocessor">#define DebugAssert(cond, str)</span>
<a name="l00071"></a>00071 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00072"></a>00072 <span class="preprocessor"></span>
<a name="l00073"></a>00073 <span class="keyword">namespace </span>Hash {
<a name="l00074"></a>00074 <span class="comment">// get size_t from hash_fun, which gets it from cstddef</span>
<a name="l00075"></a><a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">00075</a> <span class="keyword">typedef</span> <span class="keywordtype">size_t</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a>;
<a name="l00076"></a>00076 <span class="comment"></span>
<a name="l00077"></a>00077 <span class="comment"> /// primes for increasing the hash table size</span>
<a name="l00078"></a>00078 <span class="comment"></span>
<a name="l00079"></a>00079 <span class="comment">// Note: assumes size_type is unsigned and at least 32 bits.</span>
<a name="l00080"></a><a class="code" href="namespaceHash.html#ad82cc804178188cd35c373e97323da1f">00080</a> <span class="keyword">const</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a> <a class="code" href="namespaceHash.html#ad82cc804178188cd35c373e97323da1f" title="primes for increasing the hash table size">num_primes</a> = 28;
<a name="l00081"></a>00081
<a name="l00082"></a><a class="code" href="namespaceHash.html#ad803517740157e5d73f9e863e80e1229">00082</a> <span class="keyword">static</span> <span class="keyword">const</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a> <a class="code" href="namespaceHash.html#ad803517740157e5d73f9e863e80e1229">prime_list</a>[<a class="code" href="namespaceHash.html#ad82cc804178188cd35c373e97323da1f" title="primes for increasing the hash table size">num_primes</a>] = {
<a name="l00083"></a>00083 53ul, 97ul, 193ul, 389ul, 769ul,
<a name="l00084"></a>00084 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
<a name="l00085"></a>00085 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
<a name="l00086"></a>00086 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
<a name="l00087"></a>00087 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
<a name="l00088"></a>00088 1610612741ul, 3221225473ul, 4294967291ul
<a name="l00089"></a>00089 };
<a name="l00090"></a>00090
<a name="l00091"></a><a class="code" href="namespaceHash.html#ae59d4ed6f1ad169bdcc914168ce74c04">00091</a> <span class="keyword">inline</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a> <a class="code" href="namespaceHash.html#ae59d4ed6f1ad169bdcc914168ce74c04">next_prime</a>(<a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a> n)
<a name="l00092"></a>00092 {
<a name="l00093"></a>00093 <span class="keyword">const</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a>* first = <a class="code" href="namespaceHash.html#ad803517740157e5d73f9e863e80e1229">prime_list</a>;
<a name="l00094"></a>00094 <span class="keyword">const</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a>* last = <a class="code" href="namespaceHash.html#ad803517740157e5d73f9e863e80e1229">prime_list</a> + (<a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a>)<a class="code" href="namespaceHash.html#ad82cc804178188cd35c373e97323da1f" title="primes for increasing the hash table size">num_primes</a>;
<a name="l00095"></a>00095 <span class="keyword">const</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">size_type</a>* pos = std::lower_bound(first, last, n);
<a name="l00096"></a>00096 <span class="keywordflow">return</span> pos == last ? *(last - 1) : *pos;
<a name="l00097"></a>00097 }
<a name="l00098"></a>00098
<a name="l00099"></a>00099 <span class="comment"></span>
<a name="l00100"></a>00100 <span class="comment"> /*! template to instante to hash map and hash set</span>
<a name="l00101"></a>00101 <span class="comment"></span>
<a name="l00102"></a>00102 <span class="comment"> based on the sgi implementation:</span>
<a name="l00103"></a>00103 <span class="comment"> http://www.sgi.com/tech/stl/HashedAssociativeContainer.html</span>
<a name="l00104"></a>00104 <span class="comment"></span>
<a name="l00105"></a>00105 <span class="comment"> _Key: hash key type</span>
<a name="l00106"></a>00106 <span class="comment"> _Data: key + value data to store</span>
<a name="l00107"></a>00107 <span class="comment"> _HashFcn: functional class providing a hash function: int(_Key)</span>
<a name="l00108"></a>00108 <span class="comment"> Note: in some STL implementations hash is already part of</span>
<a name="l00109"></a>00109 <span class="comment"> some extension an in namespace std or stdext, in some it is not.</span>
<a name="l00110"></a>00110 <span class="comment"> So we assume that it is not available. :TODO:</span>
<a name="l00111"></a>00111 <span class="comment"> _EqualKey: functional class providing a comparison function: bool(_Key, _Key)</span>
<a name="l00112"></a>00112 <span class="comment"> returns true iff two keys are considered to be equal</span>
<a name="l00113"></a>00113 <span class="comment"> _ExtractKey: extracts key from _Data: _Key(_Data)</span>
<a name="l00114"></a>00114 <span class="comment"> */</span>
<a name="l00115"></a>00115 <span class="comment">//</span>
<a name="l00116"></a>00116 <span class="comment">// can't use debug.h as debug.h uses hash maps...</span>
<a name="l00117"></a>00117 <span class="comment">//</span>
<a name="l00118"></a>00118 <span class="comment">// implemented as an array of lists (buckets)</span>
<a name="l00119"></a>00119 <span class="keyword">template</span> <<span class="keyword">class </span>_Key, <span class="keyword">class </span>_Value,
<a name="l00120"></a>00120 <span class="keyword">class </span>_HashFcn, <span class="keyword">class </span>_EqualKey, <span class="keyword">class </span>_ExtractKey>
<a name="l00121"></a><a class="code" href="classHash_1_1hash__table.html">00121</a> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table.html">hash_table</a> {
<a name="l00122"></a>00122 <span class="comment"></span>
<a name="l00123"></a>00123 <span class="comment"> /// types</span>
<a name="l00124"></a>00124 <span class="comment"></span>
<a name="l00125"></a>00125 <span class="keyword">public</span>:
<a name="l00126"></a>00126 <span class="comment">// interface typedefs</span>
<a name="l00127"></a><a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5">00127</a> <span class="keyword">typedef</span> <a class="code" href="namespaceHash.html#a34e07ea2356b048f9871d1cfdf478da6">Hash::size_type</a> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a>;
<a name="l00128"></a><a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">00128</a> <span class="keyword">typedef</span> _Key <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>;
<a name="l00129"></a><a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">00129</a> <span class="keyword">typedef</span> _Value <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>;
<a name="l00130"></a><a class="code" href="classHash_1_1hash__table.html#adc97d1ce5a0c04a5083faea47e2bf6a7">00130</a> <span class="keyword">typedef</span> _HashFcn <a class="code" href="classHash_1_1hash__table.html#adc97d1ce5a0c04a5083faea47e2bf6a7">hasher</a>;
<a name="l00131"></a><a class="code" href="classHash_1_1hash__table.html#a03e9ef2c5a815421589495e96bb9a6fb">00131</a> <span class="keyword">typedef</span> _EqualKey <a class="code" href="classHash_1_1hash__table.html#a03e9ef2c5a815421589495e96bb9a6fb">key_equal</a>;
<a name="l00132"></a>00132
<a name="l00133"></a>00133 <span class="keyword">protected</span>:
<a name="l00134"></a>00134 <span class="comment">// a bucket is a list of values</span>
<a name="l00135"></a>00135 <span class="comment">// using an STL list makes it more complicated to have a nice end iterator,</span>
<a name="l00136"></a>00136 <span class="comment">// as iterators of different lists can not be compared</span>
<a name="l00137"></a>00137 <span class="comment">// (at least in the MS STL).</span>
<a name="l00138"></a>00138 <span class="comment">// so instead we implement our own single-linked list here,</span>
<a name="l00139"></a>00139 <span class="comment">// where NULL is the end iterator for all lists.</span>
<a name="l00140"></a><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html">00140</a> <span class="keyword">struct </span><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html">BucketNode</a> {
<a name="l00141"></a><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a2ae8c29fa0b362c3606ee8f533aa3a12">00141</a> <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a2ae8c29fa0b362c3606ee8f533aa3a12">BucketNode</a>(<a class="code" href="structHash_1_1hash__table_1_1BucketNode.html">BucketNode</a>* next, <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>& value)
<a name="l00142"></a>00142 : <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#aa7b55da0e77d2d0b71abe55797221808">d_next</a>(next), <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a1ad02ed823e6d9a3e8deead75a9b0fe7">d_value</a>(value)
<a name="l00143"></a><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#aa7b55da0e77d2d0b71abe55797221808">00143</a> { };
<a name="l00144"></a>00144 <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html">BucketNode</a>* <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#aa7b55da0e77d2d0b71abe55797221808">d_next</a>;
<a name="l00145"></a><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a1ad02ed823e6d9a3e8deead75a9b0fe7">00145</a> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a> <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a1ad02ed823e6d9a3e8deead75a9b0fe7">d_value</a>;
<a name="l00146"></a>00146 };
<a name="l00147"></a><a class="code" href="classHash_1_1hash__table.html#a726c713690774b69bea52a661d791f5f">00147</a> <span class="keyword">typedef</span> BucketNode <a class="code" href="classHash_1_1hash__table.html#a726c713690774b69bea52a661d791f5f">Bucket</a>;
<a name="l00148"></a>00148
<a name="l00149"></a>00149 <span class="comment">// the buckets are kept in an array</span>
<a name="l00150"></a><a class="code" href="classHash_1_1hash__table.html#ad11e604d35ccd38f696bd50d305190d2">00150</a> <span class="keyword">typedef</span> std::vector<Bucket*> <a class="code" href="classHash_1_1hash__table.html#ad11e604d35ccd38f696bd50d305190d2">Data</a>;
<a name="l00151"></a><a class="code" href="classHash_1_1hash__table.html#acdb3b6be3fee024a9671e59be1d5bcba">00151</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> Data::iterator <a class="code" href="classHash_1_1hash__table.html#acdb3b6be3fee024a9671e59be1d5bcba">data_iter</a>;
<a name="l00152"></a><a class="code" href="classHash_1_1hash__table.html#a4609af00f7b225edce055dc8d6e150d7">00152</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> Data::const_iterator <a class="code" href="classHash_1_1hash__table.html#a4609af00f7b225edce055dc8d6e150d7">data_const_iter</a>;
<a name="l00153"></a>00153
<a name="l00154"></a>00154
<a name="l00155"></a>00155 <span class="keyword">public</span>:
<a name="l00156"></a>00156 <span class="comment">// iterators</span>
<a name="l00157"></a><a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">00157</a> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a>;
<a name="l00158"></a>00158 <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a>;
<a name="l00159"></a><a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">00159</a> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a>;
<a name="l00160"></a>00160 <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a>;
<a name="l00161"></a>00161
<a name="l00162"></a>00162
<a name="l00163"></a>00163 <span class="comment"></span>
<a name="l00164"></a>00164 <span class="comment"> /// variables</span>
<a name="l00165"></a>00165 <span class="comment"></span>
<a name="l00166"></a>00166 <span class="keyword">protected</span>:<span class="comment"></span>
<a name="l00167"></a>00167 <span class="comment"> /// template parameters</span>
<a name="l00168"></a>00168 <span class="comment"></span>
<a name="l00169"></a>00169 <span class="comment">// the hash function for a key</span>
<a name="l00170"></a><a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471">00170</a> <a class="code" href="structHash_1_1hash_3_01long_01_4.html">hasher</a> <a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>;
<a name="l00171"></a>00171
<a name="l00172"></a>00172 <span class="comment">// the equality function between keys</span>
<a name="l00173"></a><a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">00173</a> <a class="code" href="classHash_1_1hash__table.html#a03e9ef2c5a815421589495e96bb9a6fb">key_equal</a> <a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>;
<a name="l00174"></a>00174
<a name="l00175"></a>00175 <span class="comment">// extraction of key from data</span>
<a name="l00176"></a><a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">00176</a> _ExtractKey <a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>;
<a name="l00177"></a>00177
<a name="l00178"></a>00178
<a name="l00179"></a>00179 <span class="comment">// the current number of elements - stored for efficiency</span>
<a name="l00180"></a><a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">00180</a> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>;
<a name="l00181"></a>00181
<a name="l00182"></a>00182 <span class="comment">// the hash table - an array of buckets</span>
<a name="l00183"></a><a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">00183</a> <a class="code" href="classHash_1_1hash__table.html#ad11e604d35ccd38f696bd50d305190d2">Data</a> <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>;
<a name="l00184"></a>00184
<a name="l00185"></a>00185 <span class="comment"></span>
<a name="l00186"></a>00186 <span class="comment"> /// methods</span>
<a name="l00187"></a>00187 <span class="comment"></span>
<a name="l00188"></a>00188 <span class="keyword">protected</span>:
<a name="l00189"></a>00189 <span class="comment"></span>
<a name="l00190"></a>00190 <span class="comment"> /// template parameters</span>
<a name="l00191"></a>00191 <span class="comment"></span>
<a name="l00192"></a>00192
<a name="l00193"></a>00193 <span class="comment">// the hash function for a key</span>
<a name="l00194"></a><a class="code" href="classHash_1_1hash__table.html#ab696a5a06c6f9f3e4fa43cc01002530a">00194</a> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> <a class="code" href="classHash_1_1hash__table.html#ab696a5a06c6f9f3e4fa43cc01002530a" title="methods">hash</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key)<span class="keyword"> const </span>{
<a name="l00195"></a>00195 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>(key);
<a name="l00196"></a>00196 }
<a name="l00197"></a>00197
<a name="l00198"></a>00198 <span class="comment">// equality between keys</span>
<a name="l00199"></a><a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">00199</a> <span class="keywordtype">bool</span> <a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">equal</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key1, <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key2)<span class="keyword"> const </span>{
<a name="l00200"></a>00200 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>(key1, key2);
<a name="l00201"></a>00201 }
<a name="l00202"></a>00202
<a name="l00203"></a>00203 <span class="comment">// extraction of a key</span>
<a name="l00204"></a><a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">00204</a> <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& <a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>& value)<span class="keyword"> const </span>{
<a name="l00205"></a>00205 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>(value);
<a name="l00206"></a>00206 }
<a name="l00207"></a>00207
<a name="l00208"></a>00208 <span class="comment"></span>
<a name="l00209"></a>00209 <span class="comment"> /// bucket retrieval</span>
<a name="l00210"></a>00210 <span class="comment"></span>
<a name="l00211"></a>00211 <span class="comment">// returns the index in the array which contains the bucket</span>
<a name="l00212"></a>00212 <span class="comment">// with the keys mapping to the same hash value as key</span>
<a name="l00213"></a><a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150">00213</a> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> <a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key)<span class="keyword"> const </span>{
<a name="l00214"></a>00214 <span class="keywordflow">return</span> (<a class="code" href="classHash_1_1hash__table.html#ab696a5a06c6f9f3e4fa43cc01002530a" title="methods">hash</a>(key) % <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size());
<a name="l00215"></a>00215 }
<a name="l00216"></a>00216
<a name="l00217"></a><a class="code" href="classHash_1_1hash__table.html#a6f03b296545b6baf8fd1eecda5291b7a">00217</a> <a class="code" href="classHash_1_1hash__table.html#a726c713690774b69bea52a661d791f5f">Bucket</a>* <a class="code" href="classHash_1_1hash__table.html#a6f03b296545b6baf8fd1eecda5291b7a">getBucketByKey</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key) {
<a name="l00218"></a>00218 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#aae1c6c79029e4744c28cb765fd6d9698">getBucketByIndex</a>(<a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(key));
<a name="l00219"></a>00219 }
<a name="l00220"></a>00220
<a name="l00221"></a><a class="code" href="classHash_1_1hash__table.html#a1e064e91899da2aa65fc5b21b85e5759">00221</a> <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a726c713690774b69bea52a661d791f5f">Bucket</a>* <a class="code" href="classHash_1_1hash__table.html#a1e064e91899da2aa65fc5b21b85e5759">getBucketByKey</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key)<span class="keyword"> const </span>{
<a name="l00222"></a>00222 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#aae1c6c79029e4744c28cb765fd6d9698">getBucketByIndex</a>(<a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(key));
<a name="l00223"></a>00223 }
<a name="l00224"></a>00224
<a name="l00225"></a><a class="code" href="classHash_1_1hash__table.html#aae1c6c79029e4744c28cb765fd6d9698">00225</a> <a class="code" href="classHash_1_1hash__table.html#a726c713690774b69bea52a661d791f5f">Bucket</a>* <a class="code" href="classHash_1_1hash__table.html#aae1c6c79029e4744c28cb765fd6d9698">getBucketByIndex</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index) {
<a name="l00226"></a>00226 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(index < <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size(),<span class="stringliteral">"hash_table::getBucketByIndex"</span>);
<a name="l00227"></a>00227 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.at(index);
<a name="l00228"></a>00228 }
<a name="l00229"></a>00229
<a name="l00230"></a><a class="code" href="classHash_1_1hash__table.html#a6e7cb65aacfb880dd1196821e7652197">00230</a> <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a726c713690774b69bea52a661d791f5f">Bucket</a>* <a class="code" href="classHash_1_1hash__table.html#a6e7cb65aacfb880dd1196821e7652197">getBucketByIndex</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index)<span class="keyword"> const </span>{
<a name="l00231"></a>00231 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(index < <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size(),<span class="stringliteral">"hash_table::getBucketByIndex (const)"</span>);
<a name="l00232"></a>00232 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.at(index);
<a name="l00233"></a>00233 }
<a name="l00234"></a>00234
<a name="l00235"></a>00235
<a name="l00236"></a>00236 <span class="comment"></span>
<a name="l00237"></a>00237 <span class="comment"> /// resize</span>
<a name="l00238"></a>00238 <span class="comment"></span>
<a name="l00239"></a>00239 <span class="comment">// increase the size of the table, typically if the load factor is too high</span>
<a name="l00240"></a><a class="code" href="classHash_1_1hash__table.html#a47532315fb2a36897f1e866d72e64dab">00240</a> <span class="keywordtype">void</span> <a class="code" href="classHash_1_1hash__table.html#a47532315fb2a36897f1e866d72e64dab" title="resize">resize</a>() {
<a name="l00241"></a>00241 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#a956196112f728577cbd0e280694ed58e">load_factor</a>() > 1) {
<a name="l00242"></a>00242 <span class="comment">// create new table with doubled size size</span>
<a name="l00243"></a>00243 <span class="comment">//size_type size = 2 * d_data.size();</span>
<a name="l00244"></a>00244 <span class="comment">// this is simple, but might not be efficient for bad hash functions,</span>
<a name="l00245"></a>00245 <span class="comment">// which for example mainly hash to values which contain 2 as a factor.</span>
<a name="l00246"></a>00246 <span class="comment">// thus, instead we go from a prime to a prime of more or less double size.</span>
<a name="l00247"></a>00247 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> <a class="code" href="classHash_1_1hash__table.html#ae30a43e1914f9fabf997e2190fdd6679">size</a> = <a class="code" href="namespaceHash.html#ae59d4ed6f1ad169bdcc914168ce74c04">next_prime</a>(<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size() + 1);
<a name="l00248"></a>00248 <a class="code" href="classHash_1_1hash__table.html#ad11e604d35ccd38f696bd50d305190d2">Data</a> copy(size, NULL);
<a name="l00249"></a>00249
<a name="l00250"></a>00250 <span class="comment">// move entries to new table</span>
<a name="l00251"></a>00251 <span class="keywordflow">for</span> (<a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> i = 0; i < <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size(); ++i) {
<a name="l00252"></a>00252 <span class="comment">// head of current bucket to move</span>
<a name="l00253"></a>00253 BucketNode* bucket = <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[i];
<a name="l00254"></a>00254 <span class="keywordflow">while</span> (bucket != NULL) {
<a name="l00255"></a>00255 <span class="comment">// move head of old bucket</span>
<a name="l00256"></a>00256 BucketNode* current = bucket;
<a name="l00257"></a>00257 bucket = bucket->d_next;
<a name="l00258"></a>00258
<a name="l00259"></a>00259 <span class="comment">// move old head to new bucket</span>
<a name="l00260"></a>00260 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> new_index = <a class="code" href="classHash_1_1hash__table.html#ab696a5a06c6f9f3e4fa43cc01002530a" title="methods">hash</a>(<a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(current->d_value)) % <a class="code" href="classHash_1_1hash__table.html#ae30a43e1914f9fabf997e2190fdd6679">size</a>;
<a name="l00261"></a>00261 BucketNode* new_bucket = copy[new_index];
<a name="l00262"></a>00262 current->d_next = new_bucket;
<a name="l00263"></a>00263 copy[new_index] = current;
<a name="l00264"></a>00264 }
<a name="l00265"></a>00265 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[i] = NULL;
<a name="l00266"></a>00266 }
<a name="l00267"></a>00267
<a name="l00268"></a>00268 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.swap(copy);
<a name="l00269"></a>00269 }
<a name="l00270"></a>00270 }
<a name="l00271"></a>00271
<a name="l00272"></a>00272
<a name="l00273"></a>00273 <span class="keyword">public</span>:<span class="comment"></span>
<a name="l00274"></a>00274 <span class="comment"> /// constructors</span>
<a name="l00275"></a>00275 <span class="comment"></span>
<a name="l00276"></a>00276 <span class="comment">// default size is 16 buckets</span>
<a name="l00277"></a><a class="code" href="classHash_1_1hash__table.html#a5604e07141e8a5da11b22758b3345aad">00277</a> <a class="code" href="classHash_1_1hash__table.html#a5604e07141e8a5da11b22758b3345aad" title="constructors">hash_table</a>() :
<a name="l00278"></a>00278 <a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>(_HashFcn()), <a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>(_EqualKey()), <a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>(_ExtractKey()),
<a name="l00279"></a>00279 <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>(0), <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>(16)
<a name="l00280"></a>00280 {
<a name="l00281"></a>00281 <a class="code" href="classHash_1_1hash__table.html#adcd76fb541eef5a417fd16ceb189a1a7">init</a>();
<a name="l00282"></a>00282 };
<a name="l00283"></a>00283
<a name="l00284"></a>00284 <span class="comment">// specifiy initial number of buckets - must be positive</span>
<a name="l00285"></a><a class="code" href="classHash_1_1hash__table.html#ad181cd6cd366b21d31d80ee80781ad45">00285</a> <a class="code" href="classHash_1_1hash__table.html#a5604e07141e8a5da11b22758b3345aad" title="constructors">hash_table</a>(<a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> initial_capacity) :
<a name="l00286"></a>00286 <a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>(_HashFcn()), <a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>(_EqualKey()), <a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>(_ExtractKey()),
<a name="l00287"></a>00287 <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>(0), <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>(initial_capacity)
<a name="l00288"></a>00288 {
<a name="l00289"></a>00289 <a class="code" href="classHash_1_1hash__table.html#adcd76fb541eef5a417fd16ceb189a1a7">init</a>();
<a name="l00290"></a>00290 };
<a name="l00291"></a>00291
<a name="l00292"></a>00292 <span class="comment">// specifiy initial number of buckets and hash function</span>
<a name="l00293"></a><a class="code" href="classHash_1_1hash__table.html#a964217287a7a948e895d14475f21b9cf">00293</a> <a class="code" href="classHash_1_1hash__table.html#a5604e07141e8a5da11b22758b3345aad" title="constructors">hash_table</a>(<a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> initial_capacity, <span class="keyword">const</span> _HashFcn& <a class="code" href="structHash_1_1hash.html">hash</a>) :
<a name="l00294"></a>00294 <a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>(hash), <a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>(_EqualKey()), <a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>(_ExtractKey()),
<a name="l00295"></a>00295 <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>(0), <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>(initial_capacity)
<a name="l00296"></a>00296 {
<a name="l00297"></a>00297 <a class="code" href="classHash_1_1hash__table.html#adcd76fb541eef5a417fd16ceb189a1a7">init</a>();
<a name="l00298"></a>00298 };
<a name="l00299"></a>00299
<a name="l00300"></a>00300 <span class="comment">// specifiy initial number of buckets, hash and equal function</span>
<a name="l00301"></a><a class="code" href="classHash_1_1hash__table.html#a306c7dc9fa9c107d9d4495f262074cd6">00301</a> <a class="code" href="classHash_1_1hash__table.html#a5604e07141e8a5da11b22758b3345aad" title="constructors">hash_table</a>(<a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> initial_capacity,
<a name="l00302"></a>00302 <span class="keyword">const</span> _HashFcn& <a class="code" href="structHash_1_1hash.html">hash</a>, <span class="keyword">const</span> _EqualKey& <a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">equal</a>) :
<a name="l00303"></a>00303 <a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>(hash), <a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>(equal), <a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>(_ExtractKey()),
<a name="l00304"></a>00304 <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>(0), <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>(initial_capacity)
<a name="l00305"></a>00305 {
<a name="l00306"></a>00306 <a class="code" href="classHash_1_1hash__table.html#adcd76fb541eef5a417fd16ceb189a1a7">init</a>();
<a name="l00307"></a>00307 };
<a name="l00308"></a>00308
<a name="l00309"></a>00309 <span class="comment">// copy hash table</span>
<a name="l00310"></a><a class="code" href="classHash_1_1hash__table.html#ae34073cf63557321d39dfdd51091e1fd">00310</a> <a class="code" href="classHash_1_1hash__table.html#a5604e07141e8a5da11b22758b3345aad" title="constructors">hash_table</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html">hash_table</a>& other) :
<a name="l00311"></a>00311 <a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>(other.<a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>), <a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>(other.<a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>), <a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>(other.<a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>),
<a name="l00312"></a>00312 <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>(other.<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>), <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>(0)
<a name="l00313"></a>00313 {
<a name="l00314"></a>00314 <a class="code" href="classHash_1_1hash__table.html#a9e7fdb3d406496af9dd4722880eed6a1">assignTable</a>(other.<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>);
<a name="l00315"></a>00315 };
<a name="l00316"></a>00316
<a name="l00317"></a><a class="code" href="classHash_1_1hash__table.html#a84381207cad54641a77bf93bde6f1472">00317</a> <a class="code" href="classHash_1_1hash__table.html#a84381207cad54641a77bf93bde6f1472">~hash_table</a>() {
<a name="l00318"></a>00318 <a class="code" href="classHash_1_1hash__table.html#a51fe4b7db4b7be59ea3531c1ae921de7">clear</a>();
<a name="l00319"></a>00319 }
<a name="l00320"></a>00320
<a name="l00321"></a>00321 <span class="comment">// assign hash table</span>
<a name="l00322"></a><a class="code" href="classHash_1_1hash__table.html#a577dc5179652c4d45d2accbd5a369bcf">00322</a> <a class="code" href="classHash_1_1hash__table.html">hash_table</a>& <a class="code" href="classHash_1_1hash__table.html#a577dc5179652c4d45d2accbd5a369bcf">operator=</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html">hash_table</a>& other) {
<a name="l00323"></a>00323 <span class="keywordflow">if</span> (<span class="keyword">this</span> != &other) {
<a name="l00324"></a>00324 <a class="code" href="classHash_1_1hash__table.html#a51fe4b7db4b7be59ea3531c1ae921de7">clear</a>();
<a name="l00325"></a>00325
<a name="l00326"></a>00326 <a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a> = other.<a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>;
<a name="l00327"></a>00327 <a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a> = other.<a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>;
<a name="l00328"></a>00328 <a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a> = other.<a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>;
<a name="l00329"></a>00329 <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a> = other.<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>;
<a name="l00330"></a>00330 <a class="code" href="classHash_1_1hash__table.html#a9e7fdb3d406496af9dd4722880eed6a1">assignTable</a>(other.<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>);
<a name="l00331"></a>00331 }
<a name="l00332"></a>00332
<a name="l00333"></a>00333 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00334"></a>00334 }
<a name="l00335"></a>00335
<a name="l00336"></a>00336
<a name="l00337"></a>00337 <span class="comment">// replaces the current hash table with the given one</span>
<a name="l00338"></a><a class="code" href="classHash_1_1hash__table.html#a9e7fdb3d406496af9dd4722880eed6a1">00338</a> <span class="keywordtype">void</span> <a class="code" href="classHash_1_1hash__table.html#a9e7fdb3d406496af9dd4722880eed6a1">assignTable</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#ad11e604d35ccd38f696bd50d305190d2">Data</a>& data) {
<a name="l00339"></a>00339 <span class="comment">// copy elements:</span>
<a name="l00340"></a>00340 <span class="comment">// default assignment operator does not work if value_type contains</span>
<a name="l00341"></a>00341 <span class="comment">// constants, which should be the case as the key should be constant.</span>
<a name="l00342"></a>00342 <span class="comment">// so not even shrinking a vector is possible,</span>
<a name="l00343"></a>00343 <span class="comment">// so create a new table instead and swap with the current one.</span>
<a name="l00344"></a>00344 <a class="code" href="classHash_1_1hash__table.html#ad11e604d35ccd38f696bd50d305190d2">Data</a> tmp(data.size());
<a name="l00345"></a>00345 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.swap(tmp);
<a name="l00346"></a>00346
<a name="l00347"></a>00347 <span class="comment">// for each bucket ...</span>
<a name="l00348"></a>00348 <span class="keywordflow">for</span> (<a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> i = 0; i < data.size(); ++i) {
<a name="l00349"></a>00349 <span class="comment">// .. copy each element</span>
<a name="l00350"></a>00350 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(i < <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size(),<span class="stringliteral">"hash_table::operator="</span>);
<a name="l00351"></a>00351
<a name="l00352"></a>00352 <span class="comment">// copy bucket if not empty</span>
<a name="l00353"></a>00353 <a class="code" href="classHash_1_1hash__table.html#a726c713690774b69bea52a661d791f5f">Bucket</a>* source = data[i];
<a name="l00354"></a>00354 <span class="keywordflow">if</span> (source != NULL) {
<a name="l00355"></a>00355 <span class="comment">// set first element</span>
<a name="l00356"></a>00356 <a class="code" href="classHash_1_1hash__table.html#a726c713690774b69bea52a661d791f5f">Bucket</a>* target = <span class="keyword">new</span> BucketNode(NULL, source->d_value);
<a name="l00357"></a>00357 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[i] = target;
<a name="l00358"></a>00358 source = source->d_next;
<a name="l00359"></a>00359
<a name="l00360"></a>00360 <span class="comment">// copy remaining nodes</span>
<a name="l00361"></a>00361 <span class="keywordflow">while</span> (source != NULL) {
<a name="l00362"></a>00362 target->d_next = <span class="keyword">new</span> BucketNode(NULL, source->d_value);
<a name="l00363"></a>00363 target = target->d_next;
<a name="l00364"></a>00364 source = source->d_next;
<a name="l00365"></a>00365 }
<a name="l00366"></a>00366 }
<a name="l00367"></a>00367 }
<a name="l00368"></a>00368 }
<a name="l00369"></a>00369
<a name="l00370"></a><a class="code" href="classHash_1_1hash__table.html#afcf03a783b1b22e2115405494e99407d">00370</a> <span class="keywordtype">void</span> <a class="code" href="classHash_1_1hash__table.html#afcf03a783b1b22e2115405494e99407d">swap</a>(<a class="code" href="classHash_1_1hash__table.html">hash_table</a>& other) {
<a name="l00371"></a>00371 <a class="code" href="classHash_1_1hash__table.html#afcf03a783b1b22e2115405494e99407d">std::swap</a>(<a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>, other.<a class="code" href="classHash_1_1hash__table.html#a2fbce4d745b9f31d387ce1eb958d6471" title="variables">d_hash</a>);
<a name="l00372"></a>00372 <a class="code" href="classHash_1_1hash__table.html#afcf03a783b1b22e2115405494e99407d">std::swap</a>(<a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>, other.<a class="code" href="classHash_1_1hash__table.html#ad37e9550a0180b8596f27edad570920d">d_equal</a>);
<a name="l00373"></a>00373 <a class="code" href="classHash_1_1hash__table.html#afcf03a783b1b22e2115405494e99407d">std::swap</a>(<a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>, other.<a class="code" href="classHash_1_1hash__table.html#a122b71fe085bb139055bbbf063db6d91">d_extractKey</a>);
<a name="l00374"></a>00374 <a class="code" href="classHash_1_1hash__table.html#afcf03a783b1b22e2115405494e99407d">std::swap</a>(<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>, other.<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>);
<a name="l00375"></a>00375 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.swap(other.<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>);
<a name="l00376"></a>00376 }
<a name="l00377"></a>00377
<a name="l00378"></a>00378 <span class="comment">// sets all buckets to NULL</span>
<a name="l00379"></a><a class="code" href="classHash_1_1hash__table.html#adcd76fb541eef5a417fd16ceb189a1a7">00379</a> <span class="keywordtype">void</span> <a class="code" href="classHash_1_1hash__table.html#adcd76fb541eef5a417fd16ceb189a1a7">init</a>() {
<a name="l00380"></a>00380 <span class="keywordflow">for</span> (<a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> i = 0; i < <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size(); ++i) {
<a name="l00381"></a>00381 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[i] = NULL;
<a name="l00382"></a>00382 }
<a name="l00383"></a>00383 }
<a name="l00384"></a>00384
<a name="l00385"></a>00385 <span class="comment">// empty all buckets</span>
<a name="l00386"></a><a class="code" href="classHash_1_1hash__table.html#a51fe4b7db4b7be59ea3531c1ae921de7">00386</a> <span class="keywordtype">void</span> <a class="code" href="classHash_1_1hash__table.html#a51fe4b7db4b7be59ea3531c1ae921de7">clear</a>() {
<a name="l00387"></a>00387 <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a> = 0;
<a name="l00388"></a>00388
<a name="l00389"></a>00389 <span class="keywordflow">for</span> (<a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> i = 0; i < <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size(); ++i) {
<a name="l00390"></a>00390 BucketNode* head = <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[i];
<a name="l00391"></a>00391 <span class="keywordflow">while</span> (head != NULL) {
<a name="l00392"></a>00392 BucketNode* next = head->d_next;
<a name="l00393"></a>00393 <span class="keyword">delete</span> head;
<a name="l00394"></a>00394 head = next;
<a name="l00395"></a>00395 }
<a name="l00396"></a>00396 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[i] = NULL;
<a name="l00397"></a>00397 }
<a name="l00398"></a>00398 }
<a name="l00399"></a>00399
<a name="l00400"></a>00400
<a name="l00401"></a>00401 <span class="comment"></span>
<a name="l00402"></a>00402 <span class="comment"> /// operations</span>
<a name="l00403"></a>00403 <span class="comment"></span>
<a name="l00404"></a>00404
<a name="l00405"></a>00405 <span class="comment">// returns end iterator if key was not bound</span>
<a name="l00406"></a><a class="code" href="classHash_1_1hash__table.html#a968b856ff972a7614418f9d4827848ed">00406</a> <a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a> <a class="code" href="classHash_1_1hash__table.html#a968b856ff972a7614418f9d4827848ed" title="operations">find</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key) {
<a name="l00407"></a>00407 <span class="keywordflow">for</span> (BucketNode* node = <a class="code" href="classHash_1_1hash__table.html#a6f03b296545b6baf8fd1eecda5291b7a">getBucketByKey</a>(key); node != NULL; node = node-><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#aa7b55da0e77d2d0b71abe55797221808">d_next</a>) {
<a name="l00408"></a>00408 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">equal</a>(<a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(node->d_value), key)) {
<a name="l00409"></a>00409 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a>(<span class="keyword">this</span>, node);
<a name="l00410"></a>00410 }
<a name="l00411"></a>00411 }
<a name="l00412"></a>00412 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>();
<a name="l00413"></a>00413 }
<a name="l00414"></a>00414
<a name="l00415"></a>00415 <span class="comment">// const version of find</span>
<a name="l00416"></a><a class="code" href="classHash_1_1hash__table.html#a437d3dd3e3296ec25fa49a01e7801d59">00416</a> <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a> <a class="code" href="classHash_1_1hash__table.html#a437d3dd3e3296ec25fa49a01e7801d59">find</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key)<span class="keyword"> const </span>{
<a name="l00417"></a>00417 <span class="keywordflow">for</span> (<span class="keyword">const</span> BucketNode* node = <a class="code" href="classHash_1_1hash__table.html#a6f03b296545b6baf8fd1eecda5291b7a">getBucketByKey</a>(key); node != NULL; node = node-><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#aa7b55da0e77d2d0b71abe55797221808">d_next</a>) {
<a name="l00418"></a>00418 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">equal</a>(<a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(node->d_value), key)) {
<a name="l00419"></a>00419 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a>(<span class="keyword">this</span>, node);
<a name="l00420"></a>00420 }
<a name="l00421"></a>00421 }
<a name="l00422"></a>00422 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>();
<a name="l00423"></a>00423 }
<a name="l00424"></a>00424
<a name="l00425"></a>00425
<a name="l00426"></a>00426 <span class="comment">// adds the mapping from key to data, if key is still unbound</span>
<a name="l00427"></a>00427 <span class="comment">// otherwise returns false</span>
<a name="l00428"></a><a class="code" href="classHash_1_1hash__table.html#a3a934472ef2bcb68a64b37435572843c">00428</a> std::pair<iterator, bool> <a class="code" href="classHash_1_1hash__table.html#a3a934472ef2bcb68a64b37435572843c">insert</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>& value) {
<a name="l00429"></a>00429 <span class="comment">// resize in case we insert</span>
<a name="l00430"></a>00430 <a class="code" href="classHash_1_1hash__table.html#a47532315fb2a36897f1e866d72e64dab" title="resize">resize</a>();
<a name="l00431"></a>00431
<a name="l00432"></a>00432 <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key = <a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(value);
<a name="l00433"></a>00433 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index = <a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(key);
<a name="l00434"></a>00434
<a name="l00435"></a>00435 <span class="comment">// check if key is already bound</span>
<a name="l00436"></a>00436 <span class="keywordflow">for</span> (BucketNode* node = <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index]; node != NULL; node = node->d_next) {
<a name="l00437"></a>00437 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">equal</a>(<a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(node->d_value), key)) {
<a name="l00438"></a>00438 <span class="keywordflow">return</span> std::make_pair(<a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>(), <span class="keyword">false</span>);
<a name="l00439"></a>00439 }
<a name="l00440"></a>00440 }
<a name="l00441"></a>00441
<a name="l00442"></a>00442 <span class="comment">// insert new value</span>
<a name="l00443"></a>00443 ++<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>;
<a name="l00444"></a>00444 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index] = <span class="keyword">new</span> BucketNode(<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index], value);
<a name="l00445"></a>00445 <span class="keywordflow">return</span> std::make_pair(<a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a>(<span class="keyword">this</span>, <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index]), <span class="keyword">true</span>);
<a name="l00446"></a>00446 }
<a name="l00447"></a>00447
<a name="l00448"></a>00448 <span class="comment">// if key in value is already bound,</span>
<a name="l00449"></a>00449 <span class="comment">// returns that bindings,</span>
<a name="l00450"></a>00450 <span class="comment">// otherwise inserts value and returns it.</span>
<a name="l00451"></a><a class="code" href="classHash_1_1hash__table.html#a999ccd1ec65f74547b592b432d1de46d">00451</a> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>& <a class="code" href="classHash_1_1hash__table.html#a999ccd1ec65f74547b592b432d1de46d">find_or_insert</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>& value) {
<a name="l00452"></a>00452 <span class="comment">// resize in case we insert</span>
<a name="l00453"></a>00453 <a class="code" href="classHash_1_1hash__table.html#a47532315fb2a36897f1e866d72e64dab" title="resize">resize</a>();
<a name="l00454"></a>00454
<a name="l00455"></a>00455 <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key = <a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(value);
<a name="l00456"></a>00456 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index = <a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(key);
<a name="l00457"></a>00457
<a name="l00458"></a>00458 <span class="comment">// check if key is already bound</span>
<a name="l00459"></a>00459 <span class="keywordflow">for</span> (BucketNode* node = <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index]; node != NULL; node = node->d_next) {
<a name="l00460"></a>00460 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">equal</a>(<a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(node->d_value), key)) {
<a name="l00461"></a>00461 <span class="keywordflow">return</span> node->d_value;
<a name="l00462"></a>00462 }
<a name="l00463"></a>00463 }
<a name="l00464"></a>00464
<a name="l00465"></a>00465 <span class="comment">// insert new value</span>
<a name="l00466"></a>00466 ++<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>;
<a name="l00467"></a>00467 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index] = <span class="keyword">new</span> BucketNode(<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index], value);
<a name="l00468"></a>00468 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index]->d_value;
<a name="l00469"></a>00469 }
<a name="l00470"></a>00470
<a name="l00471"></a>00471
<a name="l00472"></a>00472 <span class="comment">// removes binding of key</span>
<a name="l00473"></a>00473 <span class="comment">// returns number of keys removed,</span>
<a name="l00474"></a>00474 <span class="comment">// i.e. 1 if key was bound, 0 if key was not bound.</span>
<a name="l00475"></a><a class="code" href="classHash_1_1hash__table.html#a04a1a587d97f5cf542ed64fc6b10d972">00475</a> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> <a class="code" href="classHash_1_1hash__table.html#a04a1a587d97f5cf542ed64fc6b10d972">erase</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key) {
<a name="l00476"></a>00476 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index = <a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(key);
<a name="l00477"></a>00477
<a name="l00478"></a>00478 <span class="comment">// keep track of the node previous to the current one</span>
<a name="l00479"></a>00479 BucketNode* prev = NULL;
<a name="l00480"></a>00480 <span class="keywordflow">for</span> (BucketNode* node = <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index]; node != NULL; node = node->d_next) {
<a name="l00481"></a>00481 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">equal</a>(<a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(node->d_value), key)) {
<a name="l00482"></a>00482 --<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>;
<a name="l00483"></a>00483
<a name="l00484"></a>00484 <span class="comment">// remove the bucket's head</span>
<a name="l00485"></a>00485 <span class="keywordflow">if</span> (prev == NULL) {
<a name="l00486"></a>00486 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index] = node->d_next;
<a name="l00487"></a>00487 }
<a name="l00488"></a>00488 <span class="comment">// remove within the list;</span>
<a name="l00489"></a>00489 <span class="keywordflow">else</span> {
<a name="l00490"></a>00490 prev->d_next = node->d_next;
<a name="l00491"></a>00491 }
<a name="l00492"></a>00492 <span class="keyword">delete</span> node;
<a name="l00493"></a>00493 <span class="keywordflow">return</span> 1;
<a name="l00494"></a>00494 }
<a name="l00495"></a>00495
<a name="l00496"></a>00496 prev = node;
<a name="l00497"></a>00497 }
<a name="l00498"></a>00498
<a name="l00499"></a>00499 <span class="keywordflow">return</span> 0;
<a name="l00500"></a>00500 }
<a name="l00501"></a>00501
<a name="l00502"></a>00502 <span class="comment">// removes element pointed to by iter,</span>
<a name="l00503"></a>00503 <span class="comment">// returns element after iter.</span>
<a name="l00504"></a><a class="code" href="classHash_1_1hash__table.html#a82657fd6be4270f6a560d6026901fb5f">00504</a> <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a> <a class="code" href="classHash_1_1hash__table.html#a82657fd6be4270f6a560d6026901fb5f">erase</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a>& iter) {
<a name="l00505"></a>00505 <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a> next(iter);
<a name="l00506"></a>00506 ++next;
<a name="l00507"></a>00507
<a name="l00508"></a>00508 <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key = <a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(*iter);
<a name="l00509"></a>00509 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index = <a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(key);
<a name="l00510"></a>00510
<a name="l00511"></a>00511 <span class="comment">// keep track of the node previous to the current one</span>
<a name="l00512"></a>00512 BucketNode* prev = NULL;
<a name="l00513"></a>00513 <span class="keywordflow">for</span> (BucketNode* node = <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index]; node != NULL; node = node->d_next) {
<a name="l00514"></a>00514 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#a552326f25eda0b2a6adc5d7a9b99b5f4">equal</a>(<a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(node->d_value), key)) {
<a name="l00515"></a>00515 --<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>;
<a name="l00516"></a>00516
<a name="l00517"></a>00517 <span class="comment">// remove the bucket's head</span>
<a name="l00518"></a>00518 <span class="keywordflow">if</span> (prev == NULL) {
<a name="l00519"></a>00519 <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index] = node->d_next;
<a name="l00520"></a>00520 }
<a name="l00521"></a>00521 <span class="comment">// remove within the list;</span>
<a name="l00522"></a>00522 <span class="keywordflow">else</span> {
<a name="l00523"></a>00523 prev->d_next = node->d_next;
<a name="l00524"></a>00524 }
<a name="l00525"></a>00525 <span class="keyword">delete</span> node;
<a name="l00526"></a>00526 <span class="keywordflow">return</span> next;
<a name="l00527"></a>00527 }
<a name="l00528"></a>00528
<a name="l00529"></a>00529 prev = node;
<a name="l00530"></a>00530 }
<a name="l00531"></a>00531
<a name="l00532"></a>00532 <span class="keywordflow">return</span> next;
<a name="l00533"></a>00533 }
<a name="l00534"></a>00534
<a name="l00535"></a>00535 <span class="comment"></span>
<a name="l00536"></a>00536 <span class="comment"> /// status</span>
<a name="l00537"></a>00537 <span class="comment"></span>
<a name="l00538"></a>00538 <span class="comment">// is the key bound?</span>
<a name="l00539"></a><a class="code" href="classHash_1_1hash__table.html#a4b6eae473c46342713bfeb163c4e8559">00539</a> <span class="keywordtype">bool</span> <a class="code" href="classHash_1_1hash__table.html#a4b6eae473c46342713bfeb163c4e8559" title="status">contains</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a169157d3eb001aad4379ae2b2858d947">key_type</a>& key)<span class="keyword"> const </span>{
<a name="l00540"></a>00540 <span class="keywordflow">return</span> (<a class="code" href="classHash_1_1hash__table.html#a968b856ff972a7614418f9d4827848ed" title="operations">find</a>(key) != <a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>());
<a name="l00541"></a>00541 }
<a name="l00542"></a>00542
<a name="l00543"></a>00543 <span class="comment">// returns the number of times a key is bound,</span>
<a name="l00544"></a>00544 <span class="comment">// i.e. 0 or 1</span>
<a name="l00545"></a><a class="code" href="classHash_1_1hash__table.html#a7ffa2f780f2d8614b4b6b2b91d55f62e">00545</a> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> <a class="code" href="classHash_1_1hash__table.html#a7ffa2f780f2d8614b4b6b2b91d55f62e">count</a>(<span class="keyword">const</span> _Key& key)<span class="keyword"> const </span>{
<a name="l00546"></a>00546 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#a4b6eae473c46342713bfeb163c4e8559" title="status">contains</a>(key)) {
<a name="l00547"></a>00547 <span class="keywordflow">return</span> 1;
<a name="l00548"></a>00548 }
<a name="l00549"></a>00549 <span class="keywordflow">else</span> {
<a name="l00550"></a>00550 <span class="keywordflow">return</span> 0;
<a name="l00551"></a>00551 }
<a name="l00552"></a>00552 }
<a name="l00553"></a>00553
<a name="l00554"></a>00554 <span class="comment">// is the hash table empty?</span>
<a name="l00555"></a><a class="code" href="classHash_1_1hash__table.html#a7065f077c220601df60db97a73b0027d">00555</a> <span class="keywordtype">bool</span> <a class="code" href="classHash_1_1hash__table.html#a7065f077c220601df60db97a73b0027d">empty</a>()<span class="keyword"> const </span>{
<a name="l00556"></a>00556 <span class="keywordflow">return</span> (<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a> == 0);
<a name="l00557"></a>00557 }
<a name="l00558"></a>00558
<a name="l00559"></a>00559 <span class="comment">// the number of elements in the hash table</span>
<a name="l00560"></a><a class="code" href="classHash_1_1hash__table.html#ae30a43e1914f9fabf997e2190fdd6679">00560</a> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> <a class="code" href="classHash_1_1hash__table.html#ae30a43e1914f9fabf997e2190fdd6679">size</a>()<span class="keyword"> const </span>{
<a name="l00561"></a>00561 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>;
<a name="l00562"></a>00562 }
<a name="l00563"></a>00563
<a name="l00564"></a>00564 <span class="comment">// the number of buckets in the hash table</span>
<a name="l00565"></a><a class="code" href="classHash_1_1hash__table.html#a462c80ab1a76fd7a1c2e0c5372e66f86">00565</a> <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> <a class="code" href="classHash_1_1hash__table.html#a462c80ab1a76fd7a1c2e0c5372e66f86">bucket_count</a>()<span class="keyword"> const </span>{
<a name="l00566"></a>00566 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size();
<a name="l00567"></a>00567 }
<a name="l00568"></a>00568
<a name="l00569"></a>00569 <span class="comment">// returns the average number of elements per bucket</span>
<a name="l00570"></a><a class="code" href="classHash_1_1hash__table.html#a956196112f728577cbd0e280694ed58e">00570</a> <span class="keywordtype">float</span> <a class="code" href="classHash_1_1hash__table.html#a956196112f728577cbd0e280694ed58e">load_factor</a>()<span class="keyword"> const </span>{
<a name="l00571"></a>00571 <span class="keywordflow">return</span> (<span class="keywordtype">float</span>(<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a>) / <span class="keywordtype">float</span>(<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size()));
<a name="l00572"></a>00572 }
<a name="l00573"></a>00573
<a name="l00574"></a>00574
<a name="l00575"></a>00575 <span class="comment"></span>
<a name="l00576"></a>00576 <span class="comment"> /// iterators</span>
<a name="l00577"></a>00577 <span class="comment"></span>
<a name="l00578"></a>00578 <span class="comment">// returns forward iterator to iterate over all key/data pairs</span>
<a name="l00579"></a><a class="code" href="classHash_1_1hash__table.html#a96bd3fd3ef6ce56fef55ccec727aacd2">00579</a> <a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a> <a class="code" href="classHash_1_1hash__table.html#a96bd3fd3ef6ce56fef55ccec727aacd2" title="iterators">begin</a>() {
<a name="l00580"></a>00580 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a> > 0) {
<a name="l00581"></a>00581 <span class="comment">// find first non-empty bucket</span>
<a name="l00582"></a>00582 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index = 0;
<a name="l00583"></a>00583 <span class="keywordflow">while</span> (<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index] == NULL) {
<a name="l00584"></a>00584 ++index;
<a name="l00585"></a>00585 }
<a name="l00586"></a>00586
<a name="l00587"></a>00587 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a>(<span class="keyword">this</span>, <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index]);
<a name="l00588"></a>00588 }
<a name="l00589"></a>00589 <span class="keywordflow">else</span> {
<a name="l00590"></a>00590 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>();
<a name="l00591"></a>00591 }
<a name="l00592"></a>00592 }
<a name="l00593"></a>00593
<a name="l00594"></a>00594 <span class="comment">// const version of begin</span>
<a name="l00595"></a><a class="code" href="classHash_1_1hash__table.html#a8e4791d16ec23f4247062bb6489113c8">00595</a> <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a> <a class="code" href="classHash_1_1hash__table.html#a8e4791d16ec23f4247062bb6489113c8">begin</a>()<span class="keyword"> const </span>{
<a name="l00596"></a>00596 <span class="keywordflow">if</span> (<a class="code" href="classHash_1_1hash__table.html#ad2b709825135549a6f4cfa9e7678d3b9">d_size</a> > 0) {
<a name="l00597"></a>00597 <span class="comment">// find first non-empty bucket</span>
<a name="l00598"></a>00598 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index = 0;
<a name="l00599"></a>00599 <span class="keywordflow">while</span> (<a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index] == NULL) {
<a name="l00600"></a>00600 ++index;
<a name="l00601"></a>00601 }
<a name="l00602"></a>00602
<a name="l00603"></a>00603 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a>(<span class="keyword">this</span>, <a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>[index]);
<a name="l00604"></a>00604 }
<a name="l00605"></a>00605 <span class="keywordflow">else</span> {
<a name="l00606"></a>00606 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>();
<a name="l00607"></a>00607 }
<a name="l00608"></a>00608 }
<a name="l00609"></a>00609
<a name="l00610"></a>00610
<a name="l00611"></a>00611 <span class="comment">// returns end iterator</span>
<a name="l00612"></a><a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">00612</a> <a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a> <a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>() {
<a name="l00613"></a>00613 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#a67171474c4da6cc8efe0c7fafefd2b2d">iterator</a>(<span class="keyword">this</span>, NULL);
<a name="l00614"></a>00614 }
<a name="l00615"></a>00615
<a name="l00616"></a>00616 <span class="comment">// const version of end</span>
<a name="l00617"></a><a class="code" href="classHash_1_1hash__table.html#a5cc02698184f3be6703b3eeeb8ff6402">00617</a> <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a> <a class="code" href="classHash_1_1hash__table.html#a5cc02698184f3be6703b3eeeb8ff6402">end</a>()<span class="keyword"> const </span>{
<a name="l00618"></a>00618 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table.html#ac220ce1c155db1ac44146c12d178056f">const_iterator</a>(<span class="keyword">this</span>, NULL);
<a name="l00619"></a>00619 }
<a name="l00620"></a>00620
<a name="l00621"></a>00621
<a name="l00622"></a>00622
<a name="l00623"></a>00623 <span class="comment"></span>
<a name="l00624"></a>00624 <span class="comment"> /// inner classes</span>
<a name="l00625"></a>00625 <span class="comment"></span>
<a name="l00626"></a>00626
<a name="l00627"></a>00627
<a name="l00628"></a>00628
<a name="l00629"></a>00629 <span class="comment">// iterator over hashtable elements</span>
<a name="l00630"></a>00630
<a name="l00631"></a>00631 <span class="comment">// modifying the hash table leaves iterator intact,</span>
<a name="l00632"></a>00632 <span class="comment">// unless the key in the value it points to is modified/deleted</span>
<a name="l00633"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html">00633</a> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a> {
<a name="l00634"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#ac043297a8910af173cabd977c1ddf474">00634</a> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table.html">hash_table</a>;
<a name="l00635"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#ac220ce1c155db1ac44146c12d178056f">00635</a> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a>;
<a name="l00636"></a>00636 <span class="comment"></span>
<a name="l00637"></a>00637 <span class="comment"> /// variables</span>
<a name="l00638"></a>00638 <span class="comment"></span>
<a name="l00639"></a>00639 <span class="keyword">protected</span>:
<a name="l00640"></a>00640 <span class="comment">// the hash table of this iterator</span>
<a name="l00641"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d">00641</a> <a class="code" href="classHash_1_1hash__table.html">hash_table</a>* <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>;
<a name="l00642"></a>00642 <span class="comment">// iterator points to current element in some bucket</span>
<a name="l00643"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">00643</a> <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html">BucketNode</a>* <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>;
<a name="l00644"></a>00644
<a name="l00645"></a>00645 <span class="comment"></span>
<a name="l00646"></a>00646 <span class="comment"> /// methods</span>
<a name="l00647"></a>00647 <span class="comment"></span> <span class="keyword">protected</span>:
<a name="l00648"></a>00648 <span class="comment">// used by hash_table to create an iterator</span>
<a name="l00649"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#ad137625a72d0171d8c5fbd4042035af5">00649</a> <a class="code" href="classHash_1_1hash__table_1_1iterator.html#ac8e96aa21ba412c3b5b0b7ae2c5d7417">iterator</a>(<a class="code" href="classHash_1_1hash__table.html">hash_table</a>* <a class="code" href="classHash_1_1hash__table.html">hash_table</a>, <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html">BucketNode</a>* node)
<a name="l00650"></a>00650 : <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>(hash_table), <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>(node)
<a name="l00651"></a>00651 { }
<a name="l00652"></a>00652
<a name="l00653"></a>00653 <span class="keyword">public</span>:
<a name="l00654"></a>00654 <span class="comment">// public default constructor,</span>
<a name="l00655"></a>00655 <span class="comment">// leaves the iterator in undefined state.</span>
<a name="l00656"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#ac8e96aa21ba412c3b5b0b7ae2c5d7417">00656</a> <a class="code" href="classHash_1_1hash__table_1_1iterator.html#ac8e96aa21ba412c3b5b0b7ae2c5d7417">iterator</a>()
<a name="l00657"></a>00657 : <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>(NULL), <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>(NULL)
<a name="l00658"></a>00658 { }
<a name="l00659"></a>00659
<a name="l00660"></a>00660 <span class="comment">// copy constructor</span>
<a name="l00661"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#a9714587c12ba74ded0ee4a078c521f41">00661</a> <a class="code" href="classHash_1_1hash__table_1_1iterator.html#ac8e96aa21ba412c3b5b0b7ae2c5d7417">iterator</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a>& other)
<a name="l00662"></a>00662 : <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>(other.<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>), <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>(other.<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>)
<a name="l00663"></a>00663 { }
<a name="l00664"></a>00664
<a name="l00665"></a>00665 <span class="comment">// assignment</span>
<a name="l00666"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#aa825af4ff4c4dd291347500af456db94">00666</a> <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a>& <a class="code" href="classHash_1_1hash__table_1_1iterator.html#aa825af4ff4c4dd291347500af456db94">operator=</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a>& other) {
<a name="l00667"></a>00667 <span class="keywordflow">if</span> (<span class="keyword">this</span> != &other) {
<a name="l00668"></a>00668 <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a> = other.<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>;
<a name="l00669"></a>00669 <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> = other.<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>;
<a name="l00670"></a>00670 }
<a name="l00671"></a>00671
<a name="l00672"></a>00672 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00673"></a>00673 }
<a name="l00674"></a>00674
<a name="l00675"></a>00675 <span class="comment">// go to next data - pre-increment</span>
<a name="l00676"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#ae78954163c7f67f11a741465a09a3b25">00676</a> <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a>& <a class="code" href="classHash_1_1hash__table_1_1iterator.html#ae78954163c7f67f11a741465a09a3b25">operator++</a>() {
<a name="l00677"></a>00677 <span class="comment">// must not be the end iterator</span>
<a name="l00678"></a>00678 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> != NULL, <span class="stringliteral">"hash operator++"</span>);
<a name="l00679"></a>00679
<a name="l00680"></a>00680 <span class="comment">// get current bucket index</span>
<a name="l00681"></a>00681 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index = <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>-><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a1ad02ed823e6d9a3e8deead75a9b0fe7">d_value</a>));
<a name="l00682"></a>00682
<a name="l00683"></a>00683 <span class="comment">// go to next entry in bucket</span>
<a name="l00684"></a>00684 <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> = <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>-><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#aa7b55da0e77d2d0b71abe55797221808">d_next</a>;
<a name="l00685"></a>00685
<a name="l00686"></a>00686 <span class="comment">// while current bucket empty</span>
<a name="l00687"></a>00687 <span class="keywordflow">while</span> (<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> == NULL) {
<a name="l00688"></a>00688 <span class="comment">// go to next bucket</span>
<a name="l00689"></a>00689 ++index;
<a name="l00690"></a>00690
<a name="l00691"></a>00691 <span class="comment">// all buckets exhausted</span>
<a name="l00692"></a>00692 <span class="keywordflow">if</span> (index == <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size()) {
<a name="l00693"></a>00693 <span class="comment">// unfortunately this does not work, as end() returns a tmp value</span>
<a name="l00694"></a>00694 <span class="comment">// return d_hash_table->end();</span>
<a name="l00695"></a>00695 *<span class="keyword">this</span> = <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>();
<a name="l00696"></a>00696 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00697"></a>00697 }
<a name="l00698"></a>00698 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(index < d_hash_table-><a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size(),
<a name="l00699"></a>00699 <span class="stringliteral">"hash operator++ 2"</span>);
<a name="l00700"></a>00700
<a name="l00701"></a>00701 <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> = <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#aae1c6c79029e4744c28cb765fd6d9698">getBucketByIndex</a>(index);
<a name="l00702"></a>00702 }
<a name="l00703"></a>00703
<a name="l00704"></a>00704 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00705"></a>00705 };
<a name="l00706"></a>00706
<a name="l00707"></a>00707 <span class="comment">// go to next data - post-increment</span>
<a name="l00708"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#aa9955083a6eaa909858a738e793c096e">00708</a> <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a> <a class="code" href="classHash_1_1hash__table_1_1iterator.html#aa9955083a6eaa909858a738e793c096e">operator++</a>(<span class="keywordtype">int</span>) {
<a name="l00709"></a>00709 <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a> tmp = *<span class="keyword">this</span>;
<a name="l00710"></a>00710 ++(*this);
<a name="l00711"></a>00711 <span class="keywordflow">return</span> tmp;
<a name="l00712"></a>00712 }
<a name="l00713"></a>00713
<a name="l00714"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#a2fd5f61656f58fd34b6339b45bc48a5a">00714</a> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>& <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a2fd5f61656f58fd34b6339b45bc48a5a">operator*</a>()<span class="keyword"> const </span>{
<a name="l00715"></a>00715 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>-><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a1ad02ed823e6d9a3e8deead75a9b0fe7">d_value</a>;
<a name="l00716"></a>00716 }
<a name="l00717"></a>00717
<a name="l00718"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#af278d93e6b85c2b06e7bdef87a810b47">00718</a> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>* <a class="code" href="classHash_1_1hash__table_1_1iterator.html#af278d93e6b85c2b06e7bdef87a810b47">operator-></a>()<span class="keyword"> const </span>{
<a name="l00719"></a>00719 <span class="keywordflow">return</span> &(<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a2fd5f61656f58fd34b6339b45bc48a5a">operator*</a>());
<a name="l00720"></a>00720 }
<a name="l00721"></a>00721
<a name="l00722"></a>00722 <span class="comment">// are two iterator identical?</span>
<a name="l00723"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7553104f27d551ec147bec3194a68ee3">00723</a> <span class="keywordtype">bool</span> <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7553104f27d551ec147bec3194a68ee3">operator==</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a>& other)<span class="keyword"> const </span>{
<a name="l00724"></a>00724 <span class="comment">// if the same bucket iterator, then it must be the same hash table</span>
<a name="l00725"></a>00725 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> == NULL || <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> != other.<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> || <a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a> == other.<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a7580fa73b7528b2b3c5156a39119e84d" title="variables">d_hash_table</a>, <span class="stringliteral">"hash operator=="</span>);
<a name="l00726"></a>00726 <span class="keywordflow">return</span> (<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a> == other.<a class="code" href="classHash_1_1hash__table_1_1iterator.html#a4a96b26c66b5fafb2f8806beb87d0852">d_node</a>);
<a name="l00727"></a>00727 }
<a name="l00728"></a>00728
<a name="l00729"></a>00729 <span class="comment">// negation of ==</span>
<a name="l00730"></a><a class="code" href="classHash_1_1hash__table_1_1iterator.html#aa1fe01250a82e35e25a524f5048aef84">00730</a> <span class="keywordtype">bool</span> <a class="code" href="classHash_1_1hash__table_1_1iterator.html#aa1fe01250a82e35e25a524f5048aef84">operator!=</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a>& other)<span class="keyword"> const </span>{
<a name="l00731"></a>00731 <span class="keywordflow">return</span> !(*<span class="keyword">this</span> == other);
<a name="l00732"></a>00732 }
<a name="l00733"></a>00733 };
<a name="l00734"></a>00734
<a name="l00735"></a>00735
<a name="l00736"></a>00736
<a name="l00737"></a>00737
<a name="l00738"></a>00738 <span class="comment">// const iterator over hashtable elements</span>
<a name="l00739"></a>00739
<a name="l00740"></a>00740 <span class="comment">// modifying the hash table leaves iterator intact,</span>
<a name="l00741"></a>00741 <span class="comment">// unless the key in the value it points to is modified/deleted</span>
<a name="l00742"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">00742</a> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a> {
<a name="l00743"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#ac043297a8910af173cabd977c1ddf474">00743</a> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="classHash_1_1hash__table.html">hash_table</a>;
<a name="l00744"></a>00744 <span class="comment"></span>
<a name="l00745"></a>00745 <span class="comment"> /// variables</span>
<a name="l00746"></a>00746 <span class="comment"></span>
<a name="l00747"></a>00747 <span class="keyword">protected</span>:
<a name="l00748"></a>00748 <span class="comment">// the hash table of this iterator</span>
<a name="l00749"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f">00749</a> <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html">hash_table</a>* <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>;
<a name="l00750"></a>00750 <span class="comment">// iterator points to current element in some bucket</span>
<a name="l00751"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">00751</a> <span class="keyword">const</span> <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html">BucketNode</a>* <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>;
<a name="l00752"></a>00752
<a name="l00753"></a>00753 <span class="comment"></span>
<a name="l00754"></a>00754 <span class="comment"> /// methods</span>
<a name="l00755"></a>00755 <span class="comment"></span> <span class="keyword">protected</span>:
<a name="l00756"></a>00756 <span class="comment">// used by hash_table to create an iterator</span>
<a name="l00757"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#ae89db441356b44e640c761f8c145eeed">00757</a> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a4388108a4ffb25c593b2b34643d49a4e">const_iterator</a>(<a class="code" href="classHash_1_1hash__table.html">hash_table</a> <span class="keyword">const</span>* <a class="code" href="classHash_1_1hash__table.html">hash_table</a>, <span class="keyword">const</span> <a class="code" href="structHash_1_1hash__table_1_1BucketNode.html">BucketNode</a>* node)
<a name="l00758"></a>00758 : <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>(hash_table), <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>(node)
<a name="l00759"></a>00759 { }
<a name="l00760"></a>00760
<a name="l00761"></a>00761 <span class="keyword">public</span>:
<a name="l00762"></a>00762 <span class="comment">// public default constructor,</span>
<a name="l00763"></a>00763 <span class="comment">// leaves the iterator in undefined state.</span>
<a name="l00764"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a4388108a4ffb25c593b2b34643d49a4e">00764</a> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a4388108a4ffb25c593b2b34643d49a4e">const_iterator</a>()
<a name="l00765"></a>00765 : <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>(NULL), <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>(NULL)
<a name="l00766"></a>00766 { }
<a name="l00767"></a>00767
<a name="l00768"></a>00768 <span class="comment">// copy constructor</span>
<a name="l00769"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7aa49c3d434109581a1b0f478b7340da">00769</a> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a4388108a4ffb25c593b2b34643d49a4e">const_iterator</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a>& other)
<a name="l00770"></a>00770 : <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>(other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>), <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>(other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>)
<a name="l00771"></a>00771 { }
<a name="l00772"></a>00772
<a name="l00773"></a>00773 <span class="comment">// conversion constructor from non-const iterator</span>
<a name="l00774"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a514711d3d08934aa831a7b464c225c17">00774</a> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a4388108a4ffb25c593b2b34643d49a4e">const_iterator</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1iterator.html" title="inner classes">iterator</a>& other)
<a name="l00775"></a>00775 : <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>(other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>), <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>(other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>)
<a name="l00776"></a>00776 { }
<a name="l00777"></a>00777
<a name="l00778"></a>00778 <span class="comment">// assignment</span>
<a name="l00779"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a1fc1bac1edee28a699c77d3c1c320ebb">00779</a> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a>& <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a1fc1bac1edee28a699c77d3c1c320ebb">operator=</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a>& other) {
<a name="l00780"></a>00780 <span class="keywordflow">if</span> (<span class="keyword">this</span> != &other) {
<a name="l00781"></a>00781 <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a> = other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>;
<a name="l00782"></a>00782 <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> = other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>;
<a name="l00783"></a>00783 }
<a name="l00784"></a>00784
<a name="l00785"></a>00785 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00786"></a>00786 }
<a name="l00787"></a>00787
<a name="l00788"></a>00788 <span class="comment">// go to next data - pre-increment</span>
<a name="l00789"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#afe033f7a44d265dfc8bf4d1d70729777">00789</a> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a>& <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#afe033f7a44d265dfc8bf4d1d70729777">operator++</a>() {
<a name="l00790"></a>00790 <span class="comment">// must not be the end iterator</span>
<a name="l00791"></a>00791 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> != NULL, <span class="stringliteral">""</span>);
<a name="l00792"></a>00792
<a name="l00793"></a>00793 <span class="comment">// get current bucket index</span>
<a name="l00794"></a>00794 <a class="code" href="classHash_1_1hash__table.html#a324f81cab1c1e0a66f14b93bde73ffe5" title="types">size_type</a> index = <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#a4e1031a62a15711020bcb03009fa0150" title="bucket retrieval">getBucketIndex</a>(<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#addec8273ec53040b0b19cbcd10228832">extractKey</a>(<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>-><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a1ad02ed823e6d9a3e8deead75a9b0fe7">d_value</a>));
<a name="l00795"></a>00795
<a name="l00796"></a>00796 <span class="comment">// go to next entry in bucket</span>
<a name="l00797"></a>00797 <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> = <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>-><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#aa7b55da0e77d2d0b71abe55797221808">d_next</a>;
<a name="l00798"></a>00798
<a name="l00799"></a>00799 <span class="comment">// while current bucket empty</span>
<a name="l00800"></a>00800 <span class="keywordflow">while</span> (<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> == NULL) {
<a name="l00801"></a>00801 <span class="comment">// go to next bucket</span>
<a name="l00802"></a>00802 ++index;
<a name="l00803"></a>00803
<a name="l00804"></a>00804 <span class="comment">// all buckets exhausted</span>
<a name="l00805"></a>00805 <span class="keywordflow">if</span> (index == <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size()) {
<a name="l00806"></a>00806 <span class="comment">// unfortunately this does not work, as end() returns a tmp value</span>
<a name="l00807"></a>00807 <span class="comment">// return d_hash_table->end();</span>
<a name="l00808"></a>00808 *<span class="keyword">this</span> = <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#a0b55d938bbf33696c4e75a18bbeb2e8a">end</a>();
<a name="l00809"></a>00809 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00810"></a>00810 }
<a name="l00811"></a>00811 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(index < d_hash_table-><a class="code" href="classHash_1_1hash__table.html#abc097aa6579848853c89c5e669ec0648">d_data</a>.size(),<span class="stringliteral">""</span>);
<a name="l00812"></a>00812
<a name="l00813"></a>00813 <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> = <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>-><a class="code" href="classHash_1_1hash__table.html#aae1c6c79029e4744c28cb765fd6d9698">getBucketByIndex</a>(index);
<a name="l00814"></a>00814 }
<a name="l00815"></a>00815
<a name="l00816"></a>00816 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00817"></a>00817 };
<a name="l00818"></a>00818
<a name="l00819"></a>00819 <span class="comment">// go to next data - post-increment</span>
<a name="l00820"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7a8e1cc11076983a923badbf75a172ae">00820</a> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7a8e1cc11076983a923badbf75a172ae">operator++</a>(<span class="keywordtype">int</span>) {
<a name="l00821"></a>00821 <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a> tmp = *<span class="keyword">this</span>;
<a name="l00822"></a>00822 ++(*this);
<a name="l00823"></a>00823 <span class="keywordflow">return</span> tmp;
<a name="l00824"></a>00824 }
<a name="l00825"></a>00825
<a name="l00826"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#af843780535483fe7a9311762e8905d15">00826</a> <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>& <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#af843780535483fe7a9311762e8905d15">operator*</a>()<span class="keyword"> const </span>{
<a name="l00827"></a>00827 <span class="keywordflow">return</span> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>-><a class="code" href="structHash_1_1hash__table_1_1BucketNode.html#a1ad02ed823e6d9a3e8deead75a9b0fe7">d_value</a>;
<a name="l00828"></a>00828 }
<a name="l00829"></a>00829
<a name="l00830"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#af68ad09f5adbece35ef4a14dbcc9fed2">00830</a> <span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table.html#a73a266824c6f4b1e7398bdb95ee7cb51">value_type</a>* <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#af68ad09f5adbece35ef4a14dbcc9fed2">operator-></a>()<span class="keyword"> const </span>{
<a name="l00831"></a>00831 <span class="keywordflow">return</span> &(<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#af843780535483fe7a9311762e8905d15">operator*</a>());
<a name="l00832"></a>00832 }
<a name="l00833"></a>00833
<a name="l00834"></a>00834 <span class="comment">// are two iterator identical?</span>
<a name="l00835"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#ac2a78e639ad76a07f2d513c73a701377">00835</a> <span class="keywordtype">bool</span> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#ac2a78e639ad76a07f2d513c73a701377">operator==</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a>& other)<span class="keyword"> const </span>{
<a name="l00836"></a>00836 <span class="comment">// if the same bucket iterator, then it must be the same hash table</span>
<a name="l00837"></a>00837 <a class="code" href="hash__table_8h.html#a40dac3bdb2166ffc852ee8b1489d2b56">DebugAssert</a>(<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> == NULL || <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> != other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> || <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a> == other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a57c3c9c56835e37e58448ba57780f27f" title="variables">d_hash_table</a>,<span class="stringliteral">""</span>);
<a name="l00838"></a>00838 <span class="keywordflow">return</span> (<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a> == other.<a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#a7475024efd861e8f9d7a60c67583ff76">d_node</a>);
<a name="l00839"></a>00839 }
<a name="l00840"></a>00840
<a name="l00841"></a>00841 <span class="comment">// negation of ==</span>
<a name="l00842"></a><a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#ad87fd0c36dd8cf6ce6429992f941674c">00842</a> <span class="keywordtype">bool</span> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html#ad87fd0c36dd8cf6ce6429992f941674c">operator!=</a>(<span class="keyword">const</span> <a class="code" href="classHash_1_1hash__table_1_1const__iterator.html">const_iterator</a>& other)<span class="keyword"> const </span>{
<a name="l00843"></a>00843 <span class="keywordflow">return</span> !(*<span class="keyword">this</span> == other);
<a name="l00844"></a>00844 }
<a name="l00845"></a>00845 };
<a name="l00846"></a>00846 };
<a name="l00847"></a>00847
<a name="l00848"></a>00848 }
<a name="l00849"></a>00849
<a name="l00850"></a>00850 <span class="preprocessor">#endif</span>
</pre></div></div>
</div>
<hr class="footer"/><address class="footer"><small>Generated on Wed Sep 7 2011 for CVC3 by 
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.4 </small></address>
</body>
</html>
