diff options
| author | neodarz <neodarz@neodarz.net> | 2018-08-11 20:21:34 +0200 |
|---|---|---|
| committer | neodarz <neodarz@neodarz.net> | 2018-08-11 20:21:34 +0200 |
| commit | 0ea5fc66924303d1bf73ba283a383e2aadee02f2 (patch) | |
| tree | 2568e71a7ccc44ec23b8bb3f0ff97fb6bf2ed709 /docs/doxygen/nel/radix__sort_8h-source.html | |
| download | nevrax-website-self-hostable-0ea5fc66924303d1bf73ba283a383e2aadee02f2.tar.xz nevrax-website-self-hostable-0ea5fc66924303d1bf73ba283a383e2aadee02f2.zip | |
Initial commit
Diffstat (limited to 'docs/doxygen/nel/radix__sort_8h-source.html')
| -rw-r--r-- | docs/doxygen/nel/radix__sort_8h-source.html | 236 |
1 files changed, 236 insertions, 0 deletions
diff --git a/docs/doxygen/nel/radix__sort_8h-source.html b/docs/doxygen/nel/radix__sort_8h-source.html new file mode 100644 index 00000000..6b7bc0b1 --- /dev/null +++ b/docs/doxygen/nel/radix__sort_8h-source.html @@ -0,0 +1,236 @@ +<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd"> +<HTML> +<HEAD> + <TITLE>nevrax.org : docs</TITLE> + <LINK REL=stylesheet TYPE="text/css" HREF="http://www.nevrax.org/inc/css/nevrax.css"> + <link href="doxygen.css" rel="stylesheet" type="text/css"> +</HEAD> +<BODY MARGINHEIGHT="0" MARGINWIDTH="0"> + +<!-- uplinks --> +<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0> + <TR> + <TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD> + <TD WIDTH=140 BGCOLOR=#dddddd><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="16" BORDER=0 ALT=""></TD> + <TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD> + <TD><IMG width=6 height=14 SRC="http://www.nevrax.org/inc/img/reddots.gif" ALT="#" VSPACE=2 HSPACE=2 BORDER=0 ></TD><TD VALIGN=middle> <A CLASS=uplinks HREF=http://www.nevrax.org><b>Home</B></FONT></A> </TD> + <TD><IMG width=6 height=14 SRC="http://www.nevrax.org/inc/img/reddots.gif" ALT="#" VSPACE=2 HSPACE=2 BORDER=0 ></TD><TD VALIGN=middle> <A CLASS=uplinks HREF=http://www.nevrax.com><b>nevrax.com</B></FONT></A> </TD> + </TR> +</TABLE> + +<!-- banner Nevrax --> +<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0 WIDTH=100%> + <TR><TD BGCOLOR="#000000" BACKGROUND="http://www.nevrax.org/inc/img/black_banner.jpg"><A HREF="http://www.nevrax.org"><IMG SRC="http://www.nevrax.org/inc/img/nevrax.gif" WIDTH="170" HEIGHT="45" BORDER=0 ALT="Nevrax" ></A></TD></TR> +</TABLE> + +<!-- main table --> +<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0 height=100%> + <TR> + <TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="10" BORDER=0 ALT=""></TD> + <TD WIDTH=140 BGCOLOR=#dddddd VALIGN=TOP ALIGN=middle><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="10" BORDER=0 ALT=""> + + <!------ Begin Box ------> + <TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 BGCOLOR=black><TR><TD><TABLE border=0 cellspacing=2 cellpadding=0 width=120><tr><TD ALIGN=middle bgcolor=black> + <FONT COLOR=white FACE="sans-serif"><B>Nevrax.org</B></FONT></TD></TR><tr><td colspan=2 bgcolor=#FFFFFF> + <TABLE cellspacing=0 cellpadding=1 border=0> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/news/" TITLE="Rubrique news"><img width=13 height=15 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-news.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/news/" TITLE="News">News</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/mail/" TITLE="Rubrique mail"><img width=15 height=11 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-mail.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/mail/" TITLE="Mailing list archive">Mailing-list</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/docs/" TITLE="Rubrique docs"><img width=14 height=16 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-docs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/docs/" TITLE="Documentation">Documentation</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/cvs/" TITLE="Rubrique cvs"><img width=13 height=17 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-cvs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/cvs/" TITLE="CVS Web">CVS</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/bugs/" TITLE="Rubrique bugs"><img width=20 height=16 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-bugs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/bugs/" TITLE="Bugtracking">Bugs</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/GPL.php3" TITLE="Rubrique license"><img width=18 height=12 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-gpl.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/GPL.php3" TITLE="License">License</a></td></tr> + </TABLE> + </TD></TR></TABLE></TD></TR></TABLE> + <!------ End Box ------> + + </TD> + <TD WIDTH=15><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD> + <TD ALIGN=left valign=top><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="10" BORDER=0 ALT=""> + +<!-- title --> +<TABLE background="http://www.nevrax.org/inc/img/redline.gif" CELLSPACING=0 CELLPADDING=0 BORDER=0 width=100%><tr><td> +<A HREF="http://www.nevrax.org/docs/"><img src="http://www.nevrax.org/inc/img/t_docs.gif" ALT="Docs" HEIGHT=20 BORDER=0></A> +</td><td><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="1" HEIGHT="1" BORDER=0 ALT=""> +</td></tr></table> + + +<!-- block --> +<TABLE bgcolor="#dddddd" CELLSPACING=0 CELLPADDING=0 BORDER=0 width=100%><tr><td width=1% valign=middle><img width=6 height=14 hspace=2 vspace=2 src="http://www.nevrax.org/inc/img/reddots.gif"></TD> + <TD><B>Documentation</B></TD> + <TD ALIGN=RIGHT> </td> +</tr></table> +<!-- Generated by Doxygen 1.2.14 --> +<center> +<a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="namespaces.html">Namespace List</a> <a class="qindex" href="hierarchy.html">Class Hierarchy</a> <a class="qindex" href="classes.html">Alphabetical List</a> <a class="qindex" href="annotated.html">Compound List</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="namespacemembers.html">Namespace Members</a> <a class="qindex" href="functions.html">Compound Members</a> <a class="qindex" href="globals.html">File Members</a> <a class="qindex" href="pages.html">Related Pages</a> <a class="qindexRef" doxygen="_cgi:http://www.nevrax.org/cgi-bin/nel-search.cgi" href="http://www.nevrax.org/cgi-bin/nel-search.cgi">Search</a> </center> +<hr><h1>radix_sort.h</h1><a href="radix__sort_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre>00001 +00007 <font class="comment">/* Copyright, 2001 Nevrax Ltd.</font> +00008 <font class="comment"> *</font> +00009 <font class="comment"> * This file is part of NEVRAX NEL.</font> +00010 <font class="comment"> * NEVRAX NEL is free software; you can redistribute it and/or modify</font> +00011 <font class="comment"> * it under the terms of the GNU General Public License as published by</font> +00012 <font class="comment"> * the Free Software Foundation; either version 2, or (at your option)</font> +00013 <font class="comment"> * any later version.</font> +00014 <font class="comment"></font> +00015 <font class="comment"> * NEVRAX NEL is distributed in the hope that it will be useful, but</font> +00016 <font class="comment"> * WITHOUT ANY WARRANTY; without even the implied warranty of</font> +00017 <font class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</font> +00018 <font class="comment"> * General Public License for more details.</font> +00019 <font class="comment"></font> +00020 <font class="comment"> * You should have received a copy of the GNU General Public License</font> +00021 <font class="comment"> * along with NEVRAX NEL; see the file COPYING. If not, write to the</font> +00022 <font class="comment"> * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,</font> +00023 <font class="comment"> * MA 02111-1307, USA.</font> +00024 <font class="comment"> */</font> +00025 +00026 <font class="preprocessor">#ifndef NL_RADIX_SORT_H</font> +00027 <font class="preprocessor"></font><font class="preprocessor">#define NL_RADIX_SORT_H</font> +00028 <font class="preprocessor"></font> +00029 <font class="preprocessor">#include "<a class="code" href="types__nl_8h.html">nel/misc/types_nl.h</a>"</font> +00030 <font class="preprocessor">#include "<a class="code" href="common_8h.html">nel/misc/common.h</a>"</font> +00031 +00032 +00033 <font class="keyword">namespace </font>NL3D { +00034 +00035 +00036 <font class="comment">// ***************************************************************************</font> +<a name="l00049"></a><a class="code" href="classNL3D_1_1CRadixSort.html">00049</a> <font class="comment"></font><font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keyword">class </font>CRadixSort +00050 { +00051 <font class="keyword">public</font>: +00052 +<a name="l00062"></a><a class="code" href="classNL3D_1_1CRadixSort.html#a0">00062</a> <a class="code" href="classNL3D_1_1CRadixSort.html#a0">CRadixSort</a>(uint keyDepth= 32, uint digitDepth= 8) +00063 { +00064 <font class="comment">// setup</font> +00065 <a class="code" href="classNL3D_1_1CRadixSort.html#o0">_KeyDepth</a>= keyDepth; +00066 <a class="code" href="namespaceNLMISC.html#a215">NLMISC::clamp</a>(<a class="code" href="classNL3D_1_1CRadixSort.html#o0">_KeyDepth</a>, 1U, 32U); +00067 <a class="code" href="classNL3D_1_1CRadixSort.html#o1">_DigitDepth</a>= digitDepth; +00068 <a class="code" href="namespaceNLMISC.html#a215">NLMISC::clamp</a>(<a class="code" href="classNL3D_1_1CRadixSort.html#o1">_DigitDepth</a>, 1U, 16U); +00069 <a class="code" href="classNL3D_1_1CRadixSort.html#o1">_DigitDepth</a>= <a class="code" href="bit__set_8cpp.html#a0">std::min</a>(<a class="code" href="classNL3D_1_1CRadixSort.html#o1">_DigitDepth</a>, <a class="code" href="classNL3D_1_1CRadixSort.html#o0">_KeyDepth</a>); +00070 +00071 <font class="comment">// resize the array of digits.</font> +00072 <a class="code" href="classNL3D_1_1CRadixSort.html#o2">_DigitSize</a>= 1<<<a class="code" href="classNL3D_1_1CRadixSort.html#o1">_DigitDepth</a>; +00073 <a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>.resize(<a class="code" href="classNL3D_1_1CRadixSort.html#o2">_DigitSize</a>); +00074 } +00075 +<a name="l00084"></a><a class="code" href="classNL3D_1_1CRadixSort.html#a1">00084</a> T *<a class="code" href="classNL3D_1_1CRadixSort.html#a1">sort</a>(T *array0, T *array1, uint size) {<font class="keywordflow">return</font> <a class="code" href="classNL3D_1_1CRadixSort.html#c0">doSort</a>(array0, array1, size, <font class="keyword">true</font>);} +00085 +00086 +<a name="l00090"></a><a class="code" href="classNL3D_1_1CRadixSort.html#a2">00090</a> T *<a class="code" href="classNL3D_1_1CRadixSort.html#a2">reverse_sort</a>(T *array0, T *array1, uint size) {<font class="keywordflow">return</font> <a class="code" href="classNL3D_1_1CRadixSort.html#c0">doSort</a>(array0, array1, size, <font class="keyword">false</font>);} +00091 +00092 +00093 <font class="comment">// ***********************</font> +00094 <font class="keyword">private</font>: +00095 +<a name="l00096"></a><a class="code" href="structNL3D_1_1CRadixSort_1_1CSortDigit.html">00096</a> <font class="keyword">struct </font>CSortDigit +00097 { +00098 <font class="comment">// For a digit, how many elements it has in the array.</font> +<a name="l00099"></a><a class="code" href="structNL3D_1_1CRadixSort_1_1CSortDigit.html#m0">00099</a> uint <a class="code" href="structNL3D_1_1CRadixSort_1_1CSortDigit.html#m0">Count</a>; +00100 <font class="comment">// current ptr where to write in destArray</font> +<a name="l00101"></a><a class="code" href="structNL3D_1_1CRadixSort_1_1CSortDigit.html#m1">00101</a> T *<a class="code" href="structNL3D_1_1CRadixSort_1_1CSortDigit.html#m1">Ptr</a>; +00102 }; +00103 +00104 <font class="comment">// setup</font> +<a name="l00105"></a><a class="code" href="classNL3D_1_1CRadixSort.html#o0">00105</a> uint <a class="code" href="classNL3D_1_1CRadixSort.html#o0">_KeyDepth</a>; +<a name="l00106"></a><a class="code" href="classNL3D_1_1CRadixSort.html#o1">00106</a> uint <a class="code" href="classNL3D_1_1CRadixSort.html#o1">_DigitDepth</a>; +<a name="l00107"></a><a class="code" href="classNL3D_1_1CRadixSort.html#o2">00107</a> uint <a class="code" href="classNL3D_1_1CRadixSort.html#o2">_DigitSize</a>; +00108 <font class="comment">// We sort digits per digit (default is byte per byte)</font> +<a name="l00109"></a><a class="code" href="classNL3D_1_1CRadixSort.html#o3">00109</a> std::vector<CSortDigit> <a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>; +00110 +00111 +<a name="l00113"></a><a class="code" href="classNL3D_1_1CRadixSort.html#c0">00113</a> T *<a class="code" href="classNL3D_1_1CRadixSort.html#c0">doSort</a>(T *arraySrc, T *arrayDst, uint size, <font class="keywordtype">bool</font> increasingOrder) +00114 { +00115 <font class="keywordflow">if</font>(size==0) +00116 <font class="keywordflow">return</font> arraySrc; +00117 +00118 <font class="comment">// for all digits.</font> +00119 <font class="keywordflow">for</font>(uint digit=0; digit< <a class="code" href="classNL3D_1_1CRadixSort.html#o0">_KeyDepth</a>; digit+=<a class="code" href="classNL3D_1_1CRadixSort.html#o1">_DigitDepth</a> ) +00120 { +00121 sint i; +00122 <font class="comment">// how many bits do we shift?</font> +00123 uint digitShift= digit; +00124 uint digitMask= <a class="code" href="classNL3D_1_1CRadixSort.html#o2">_DigitSize</a> - 1; +00125 +00126 <font class="comment">// Init digit count.</font> +00127 <font class="keywordflow">for</font>(i=0; i<(sint)<a class="code" href="classNL3D_1_1CRadixSort.html#o2">_DigitSize</a>; i++) +00128 { +00129 <a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>[i].Count= 0; +00130 } +00131 +00132 <font class="comment">// for all elements in array, count the usage of current digit.</font> +00133 T *srcPtr= arraySrc; +00134 <font class="keywordflow">for</font>(i=0; i<(sint)size; i++, srcPtr++) +00135 { +00136 <font class="comment">// get the key for this element</font> +00137 uint32 key= srcPtr->getRadixKey(); +00138 <font class="comment">// get the actual digit of interest</font> +00139 key>>= digitShift; +00140 key&= digitMask; +00141 <font class="comment">// increment the use of this digit.</font> +00142 <a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>[key].Count++; +00143 } +00144 +00145 <font class="comment">// for all digit, init start Ptr.</font> +00146 T *dstPtr= arrayDst; +00147 <font class="keywordflow">if</font>(increasingOrder) +00148 { +00149 <font class="keywordflow">for</font>(i=0; i<(sint)<a class="code" href="classNL3D_1_1CRadixSort.html#o2">_DigitSize</a>; i++) +00150 { +00151 <font class="comment">// setup the dest ptr for this digit.</font> +00152 <a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>[i].Ptr= dstPtr; +00153 <font class="comment">// increment the ptr of digit usage</font> +00154 dstPtr+= <a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>[i].Count; +00155 } +00156 } +00157 <font class="keywordflow">else</font> +00158 { +00159 <font class="comment">// reverse order of copy for digits, so the biggest one will </font> +00160 <font class="comment">// copy in the beginning of the array</font> +00161 <font class="keywordflow">for</font>(i=<a class="code" href="classNL3D_1_1CRadixSort.html#o2">_DigitSize</a>-1; i>=0; i--) +00162 { +00163 <font class="comment">// setup the dest ptr for this digit.</font> +00164 <a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>[i].Ptr= dstPtr; +00165 <font class="comment">// increment the ptr of digit usage</font> +00166 dstPtr+= <a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>[i].Count; +00167 } +00168 } +00169 +00170 <font class="comment">// for all elements, sort for this digit, by copying from src to dest.</font> +00171 srcPtr= arraySrc; +00172 <font class="keywordflow">for</font>(i=0; i<(sint)size; i++, srcPtr++) +00173 { +00174 <font class="comment">// get the key for this element</font> +00175 uint32 key= srcPtr->getRadixKey(); +00176 <font class="comment">// get the actual digit of interest</font> +00177 key>>= digitShift; +00178 key&= digitMask; +00179 <font class="comment">// copy to good digit dst, and increment dest ptr.</font> +00180 *(<a class="code" href="classNL3D_1_1CRadixSort.html#o3">_SortDigits</a>[key].Ptr++)= *srcPtr; +00181 } +00182 +00183 <font class="comment">// arraDst has now values of arraySrc sorted for the current digit.</font> +00184 <font class="comment">// now, restart with next digit, so swap src / dst</font> +00185 std::swap(arraySrc, arrayDst); +00186 } +00187 +00188 <font class="comment">// return the array correctly sorted. because of last swap, this is arraySrc</font> +00189 <font class="keywordflow">return</font> arraySrc; +00190 } +00191 +00192 }; +00193 +00194 +00195 } <font class="comment">// NL3D</font> +00196 +00197 +00198 <font class="preprocessor">#endif // NL_RADIX_SORT_H</font> +00199 <font class="preprocessor"></font> +00200 <font class="comment">/* End of radix_sort.h */</font> +</pre></div> + +<!-- footer --> +<BR><FONT Size=+5> </FONT> +</TD> +<TD WIDTH=15><IMG SRC=http://www.nevrax.org/inc/img/pixel.gif WIDTH=15 HEIGHT=15 BORDER=0 ALT=""></TD> +</TR> +</TABLE> +</BODY> +</HTML> |