Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse files

Initial docs

  • Loading branch information...
commit 938de8aef4d11329a9749d92abf1c6851b305ebb 1 parent 78d2914
@kanwei authored
Showing with 24,007 additions and 1 deletion.
  1. +165 −0 classes/Algorithms.html
  2. +149 −0 classes/Algorithms/Search.html
  3. +390 −0 classes/Algorithms/Sort.html
  4. +83 −0 classes/Algorithms/String.html
  5. +93 −0 classes/Containers.html
  6. +167 −0 classes/Containers/CBst.html
  7. +296 −0 classes/Containers/CDeque.html
  8. +308 −0 classes/Containers/CRBTreeMap.html
  9. +291 −0 classes/Containers/CSplayTreeMap.html
  10. +399 −0 classes/Containers/Heap.html
  11. +143 −0 classes/Containers/KDTree.html
  12. +144 −0 classes/Containers/MaxHeap.html
  13. +144 −0 classes/Containers/MinHeap.html
  14. +288 −0 classes/Containers/PriorityQueue.html
  15. +233 −0 classes/Containers/Queue.html
  16. +358 −0 classes/Containers/RubyDeque.html
  17. +412 −0 classes/Containers/RubyRBTreeMap.html
  18. +362 −0 classes/Containers/RubySplayTreeMap.html
  19. +233 −0 classes/Containers/Stack.html
  20. +137 −0 classes/Containers/SuffixArray.html
  21. +300 −0 classes/Containers/Trie.html
  22. +171 −0 classes/Object.html
  23. +296 −0 classes/Object/Deque.html
  24. +308 −0 classes/Object/RBTreeMap.html
  25. +291 −0 classes/Object/SplayTreeMap.html
  26. +63 −0 classes/String.html
  27. +50 −0 created.rid
  28. +328 −0 css/style.css
  29. +61 −0 files/Gemfile.html
  30. +73 −0 files/Manifest.html
  31. +80 −0 files/Rakefile.html
  32. +58 −0 files/benchmarks/deque_rb.html
  33. +58 −0 files/benchmarks/sorts_rb.html
  34. +58 −0 files/benchmarks/treemaps_rb.html
  35. +56 −0 files/ext/algorithms/string/extconf_rb.html
  36. +50 −0 files/ext/algorithms/string/string_c.html
  37. +50 −0 files/ext/containers/bst/bst_c.html
  38. +56 −0 files/ext/containers/bst/extconf_rb.html
  39. +50 −0 files/ext/containers/deque/deque_c.html
  40. +56 −0 files/ext/containers/deque/extconf_rb.html
  41. +56 −0 files/ext/containers/rbtree_map/extconf_rb.html
  42. +50 −0 files/ext/containers/rbtree_map/rbtree_c.html
  43. +56 −0 files/ext/containers/splaytree_map/extconf_rb.html
  44. +50 −0 files/ext/containers/splaytree_map/splaytree_c.html
  45. +54 −0 files/lib/algorithms/search_rb.html
  46. +56 −0 files/lib/algorithms/sort_rb.html
  47. +60 −0 files/lib/algorithms/string_rb.html
  48. +170 −0 files/lib/algorithms_rb.html
  49. +64 −0 files/lib/containers/deque_rb.html
  50. +66 −0 files/lib/containers/heap_rb.html
  51. +73 −0 files/lib/containers/kd_tree_rb.html
  52. +56 −0 files/lib/containers/priority_queue_rb.html
  53. +56 −0 files/lib/containers/queue_rb.html
  54. +57 −0 files/lib/containers/rb_tree_map_rb.html
  55. +57 −0 files/lib/containers/splay_tree_map_rb.html
  56. +56 −0 files/lib/containers/stack_rb.html
  57. +59 −0 files/lib/containers/suffix_array_rb.html
  58. +61 −0 files/lib/containers/trie_rb.html
  59. +61 −0 files/spec/bst_gc_mark_spec_rb.html
  60. +60 −0 files/spec/bst_spec_rb.html
  61. +56 −0 files/spec/deque_gc_mark_spec_rb.html
  62. +56 −0 files/spec/deque_spec_rb.html
  63. +56 −0 files/spec/heap_spec_rb.html
  64. +2,856 −0 files/spec/kd_expected_out_txt.html
  65. +6,716 −0 files/spec/kd_test_in_txt.html
  66. +56 −0 files/spec/kd_tree_spec_rb.html
  67. +56 −0 files/spec/map_gc_mark_spec_rb.html
  68. +56 −0 files/spec/priority_queue_spec_rb.html
  69. +56 −0 files/spec/queue_spec_rb.html
  70. +56 −0 files/spec/rb_tree_map_spec_rb.html
  71. +56 −0 files/spec/search_spec_rb.html
  72. +56 −0 files/spec/sort_spec_rb.html
  73. +56 −0 files/spec/splay_tree_map_spec_rb.html
  74. +56 −0 files/spec/stack_spec_rb.html
  75. +56 −0 files/spec/string_spec_rb.html
  76. +56 −0 files/spec/suffix_array_spec_rb.html
  77. +56 −0 files/spec/trie_spec_rb.html
  78. +75 −0 fr_class_index.html
  79. +68 −0 fr_file_index.html
  80. +4,851 −0 fr_method_index.html
  81. +15 −1 index.html
View
165 classes/Algorithms.html
@@ -0,0 +1,165 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<html lang='en'>
+ <head>
+ <title>Algorithms</title>
+ <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'>
+ <link href='../css/style.css' media='screen' rel='stylesheet' type='text/css'>
+ <script type='text/javascript'>
+ //<![CDATA[
+ function popupCode(url) {
+ window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
+ }
+
+ function toggleCode(id) {
+ var code = document.getElementById(id)
+
+ code.style.display = code.style.display != 'block' ? 'block' : 'none'
+ return true
+ }
+
+ // Make codeblocks hidden by default
+ document.writeln('<' + 'style type="text/css">.method .source pre { display: none }<\/style>')
+ //]]>
+ </script>
+ </head>
+ <body class='page'>
+ <div class='class' id='wrapper'>
+ <div class='header'>
+ <h1 class='name'>
+ <span class='type'>module</span>
+ Algorithms
+ </h1>
+ <ol class='paths'>
+ <li>
+ <a target="docwin" href="../files/ext/algorithms/string/string_c.html">ext/algorithms/string/string.c</a>
+ </li>
+ <li class='other'>
+ <a target="docwin" href="../files/lib/algorithms_rb.html">lib/algorithms.rb</a>
+ </li>
+ <li>
+ <a class='show' href='#' onclick='this.parentNode.parentNode.className += " expanded"; this.parentNode.removeChild(this); return false'>show all</a>
+ </li>
+ </ol>
+ <div class='parent'>
+ Parent:
+ <strong><a target="docwin" href="../files/lib/algorithms_rb.html">algorithms.rb</a></strong>
+ </div>
+ </div>
+ <div id='content'>
+ <div id='text'>
+ <div id='description'>
+
+ <p>The ‘<a href="Algorithms.html">Algorithms</a> and Containers’ library is an
+ effort to provide a set of commonly used algorithms and containers to Ruby
+ programmers.</p>
+
+ <p>This is a Google Summer of Code 2008 project</p>
+
+ <p>Written by Kanwei Li, mentored by Austin Ziegler</p>
+
+ <p>To avoid typing Containers::xxx to initialize containers, include the <a
+ href="Containers.html">Containers</a> module.</p>
+
+ <pre class="ruby"><span class="ruby-identifier">require</span> <span class="ruby-string">'algorithms'</span>&#x000A;<span class="ruby-identifier">include</span> <span class="ruby-constant">Containers</span>&#x000A;&#x000A;<span class="ruby-identifier">tree</span> = <span class="ruby-constant">RBTreeMap</span>.<span class="ruby-identifier">new</span></pre>
+
+ <p>instead of:</p>
+
+ <pre class="ruby"><span class="ruby-identifier">require</span> <span class="ruby-string">'algorithms'</span>&#x000A;&#x000A;<span class="ruby-identifier">tree</span> = <span class="ruby-constant">Containers</span><span class="ruby-operator">::</span><span class="ruby-constant">RBTreeMap</span>.<span class="ruby-identifier">new</span></pre>
+
+ <p>Done so far:</p>
+ <ul><li>
+ <p>Heaps - <a href="Containers/Heap.html">Containers::Heap</a>, <a
+ href="Containers/MaxHeap.html">Containers::MaxHeap</a>, <a
+ href="Containers/MinHeap.html">Containers::MinHeap</a></p>
+ </li><li>
+ <p>Priority Queue - <a
+ href="Containers/PriorityQueue.html">Containers::PriorityQueue</a></p>
+ </li><li>
+ <p>Stack - <a href="Containers/Stack.html">Containers::Stack</a></p>
+ </li><li>
+ <p>Queue - <a href="Containers/Queue.html">Containers::Queue</a></p>
+ </li><li>
+ <p><a href="Containers/CDeque.html">Deque</a> - Containers::Deque,
+ <a href="Containers/CDeque.html">Containers::CDeque</a> (C extension), <a
+ href="Containers/RubyDeque.html">Containers::RubyDeque</a></p>
+ </li><li>
+ <p>Red-Black Trees - Containers::RBTreeMap, <a
+ href="Containers/CRBTreeMap.html">Containers::CRBTreeMap</a> (C extension),
+ <a href="Containers/RubyRBTreeMap.html">Containers::RubyRBTreeMap</a></p>
+ </li><li>
+ <p>Splay Trees - Containers::SplayTreeMap</p>
+ </li><li>
+ <p>Tries - <a href="Containers/Trie.html">Containers::Trie</a></p>
+ </li><li>
+ <p>Suffix Array - <a
+ href="Containers/SuffixArray.html">Containers::SuffixArray</a></p>
+ </li><li>
+ <p>kd Tree - <a href="Containers/KDTree.html">Containers::KDTree</a></p>
+ </li><li>
+ <p><a href="Algorithms/Search.html">Search</a> algorithms</p>
+ <ul><li>
+ <p>Binary <a href="Algorithms/Search.html">Search</a> - <a
+ href="Algorithms/Search.html#method-c-binary_search">Algorithms::Search.binary_search</a></p>
+ </li><li>
+ <p>Knuth-Morris-Pratt - <a
+ href="Algorithms/Search.html#method-c-kmp_search">Algorithms::Search.kmp_search</a></p>
+ </li></ul>
+ </li><li>
+ <p><a href="Algorithms/Sort.html">Sort</a> algorithms</p>
+ <ul><li>
+ <p>Bubble sort - <a
+ href="Algorithms/Sort.html#method-c-bubble_sort">Algorithms::Sort.bubble_sort</a></p>
+ </li><li>
+ <p>Comb sort - <a
+ href="Algorithms/Sort.html#method-c-comb_sort">Algorithms::Sort.comb_sort</a></p>
+ </li><li>
+ <p>Selection sort - <a
+ href="Algorithms/Sort.html#method-c-selection_sort">Algorithms::Sort.selection_sort</a></p>
+ </li><li>
+ <p>Heapsort - <a
+ href="Algorithms/Sort.html#method-c-heapsort">Algorithms::Sort.heapsort</a></p>
+ </li><li>
+ <p>Insertion sort - <a
+ href="Algorithms/Sort.html#method-c-insertion_sort">Algorithms::Sort.insertion_sort</a></p>
+ </li><li>
+ <p>Shell sort - <a
+ href="Algorithms/Sort.html#method-c-shell_sort">Algorithms::Sort.shell_sort</a></p>
+ </li><li>
+ <p>Quicksort - <a
+ href="Algorithms/Sort.html#method-c-quicksort">Algorithms::Sort.quicksort</a></p>
+ </li><li>
+ <p>Mergesort - <a
+ href="Algorithms/Sort.html#method-c-mergesort">Algorithms::Sort.mergesort</a></p>
+ </li><li>
+ <p>Dual-Pivot Quicksort - <a
+ href="Algorithms/Sort.html#method-c-dualpivotquicksort">Algorithms::Sort.dualpivotquicksort</a></p>
+ </li></ul>
+ </li><li>
+ <p><a href="Algorithms/String.html">String</a> algorithms</p>
+ <ul><li>
+ <p>Levenshtein distance - <a
+ href="Algorithms/String.html#method-c-levenshtein_dist">Algorithms::String.levenshtein_dist</a></p>
+ </li></ul>
+ </li></ul>
+ </div>
+ <div id='context'>
+ </div>
+ <div id='class-list'>
+ <h2>Classes and Modules</h2>
+ <ol>
+ <li><a target="docwin" href="Algorithms/Search.html">Algorithms::Search</a></li>
+ <li><a target="docwin" href="Algorithms/Sort.html">Algorithms::Sort</a></li>
+ <li><a target="docwin" href="Algorithms/String.html">Algorithms::String</a></li>
+ </ol>
+ </div>
+ <div id='section'>
+ </div>
+ </div>
+ </div>
+ <div id='footer-push'></div>
+ </div>
+ <div id='footer'>
+ <a target="docwin" href="http://github.com/mislav/hanna/tree/master"><strong>Hanna</strong> RDoc template</a>
+ </div>
+ </body>
+</html>
View
149 classes/Algorithms/Search.html
@@ -0,0 +1,149 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<html lang='en'>
+ <head>
+ <title>Algorithms::Search</title>
+ <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'>
+ <link href='../../css/style.css' media='screen' rel='stylesheet' type='text/css'>
+ <script type='text/javascript'>
+ //<![CDATA[
+ function popupCode(url) {
+ window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
+ }
+
+ function toggleCode(id) {
+ var code = document.getElementById(id)
+
+ code.style.display = code.style.display != 'block' ? 'block' : 'none'
+ return true
+ }
+
+ // Make codeblocks hidden by default
+ document.writeln('<' + 'style type="text/css">.method .source pre { display: none }<\/style>')
+ //]]>
+ </script>
+ </head>
+ <body class='page'>
+ <div class='class' id='wrapper'>
+ <div class='header'>
+ <h1 class='name'>
+ <span class='type'>module</span>
+ Algorithms::Search
+ </h1>
+ <ol class='paths'>
+ <li>
+ <a target="docwin" href="../../files/lib/algorithms/search_rb.html">lib/algorithms/search.rb</a>
+ </li>
+ </ol>
+ <div class='parent'>
+ Parent:
+ <strong><a target="docwin" href="../Algorithms.html">Algorithms</a></strong>
+ </div>
+ </div>
+ <div id='content'>
+ <div id='text'>
+ <div id='description'>
+
+ <p>This module implements search algorithms. Documentation is provided for
+ each algorithm.</p>
+ </div>
+ <div id='method-list'>
+ <h2>Methods</h2>
+ <h3>Public Class</h3>
+ <ol>
+ <li><a target="docwin" href="#method-c-binary_search">binary_search</a></li>
+ <li><a target="docwin" href="#method-c-kmp_search">kmp_search</a></li>
+ </ol>
+ <h3>Public Instance</h3>
+ <ol>
+ <li><a target="docwin" href="#method-i-kmp_search">kmp_search</a></li>
+ </ol>
+ </div>
+ <div id='context'>
+ </div>
+ <div id='section'>
+ <div id='methods'>
+ <h2>Public Class methods</h2>
+ <div class='method public-class' id='method-method-c-binary_search'>
+ <a name='method-c-binary_search'></a>
+ <div class='synopsis'>
+ <span class='name'>binary_search</span>
+ <span class='arguments'>(container, item)</span>
+ </div>
+ <div class='description'>
+
+ <p>Binary Search: This search finds an item in log(n) time provided that the
+ container is already sorted. The method returns the item if it is found, or
+ nil if it is not. If there are duplicates, the first one found is returned,
+ and this is not guaranteed to be the smallest or largest item.</p>
+
+ <p>Complexity: O(lg N)</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Search</span>.<span class="ruby-identifier">binary_search</span>([<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>], <span class="ruby-value">1</span>) <span class="ruby-comment">#=&gt; 1</span>&#x000A;<span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Search</span>.<span class="ruby-identifier">binary_search</span>([<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>], <span class="ruby-value">4</span>) <span class="ruby-comment">#=&gt; nil</span></pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-binary_search-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-binary_search-source'><span class="ruby-comment"># File lib/algorithms/search.rb, line 14</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">binary_search</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">item</span>)&#x000A; <span class="ruby-keyword">return</span> <span class="ruby-keyword">nil</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">item</span>.<span class="ruby-identifier">nil?</span>&#x000A; <span class="ruby-identifier">low</span> = <span class="ruby-value">0</span>&#x000A; <span class="ruby-identifier">high</span> = <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span> <span class="ruby-operator">-</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">low</span> <span class="ruby-operator">&lt;=</span> <span class="ruby-identifier">high</span>&#x000A; <span class="ruby-identifier">mid</span> = (<span class="ruby-identifier">low</span> <span class="ruby-operator">+</span> <span class="ruby-identifier">high</span>) <span class="ruby-operator">/</span> <span class="ruby-value">2</span>&#x000A; <span class="ruby-identifier">val</span> = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">mid</span>]&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">val</span> <span class="ruby-operator">&gt;</span> <span class="ruby-identifier">item</span>&#x000A; <span class="ruby-identifier">high</span> = <span class="ruby-identifier">mid</span> <span class="ruby-operator">-</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">elsif</span> <span class="ruby-identifier">val</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">item</span>&#x000A; <span class="ruby-identifier">low</span> = <span class="ruby-identifier">mid</span> <span class="ruby-operator">+</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">else</span>&#x000A; <span class="ruby-keyword">return</span> <span class="ruby-identifier">val</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">nil</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-kmp_search'>
+ <a name='method-c-kmp_search'></a>
+ <div class='synopsis'>
+ <span class='name'>kmp_search</span>
+ <span class='arguments'>(string, substring)</span>
+ </div>
+ <div class='description'>
+
+ <p>Knuth-Morris-Pratt Algorithm substring search algorithm: Efficiently finds
+ the starting position of a substring in a string. The algorithm calculates
+ the best position to resume searching from if a failure occurs.</p>
+
+ <p>The method returns the index of the starting position in the string where
+ the substring is found. If there is no match, nil is returned.</p>
+
+ <p>Complexity: O(n + k), where n is the length of the string and k is the
+ length of the substring.</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Search</span>.<span class="ruby-identifier">kmp_search</span>(<span class="ruby-string">&quot;ABC ABCDAB ABCDABCDABDE&quot;</span>, <span class="ruby-string">&quot;ABCDABD&quot;</span>) <span class="ruby-comment">#=&gt; 15</span>&#x000A;<span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Search</span>.<span class="ruby-identifier">kmp_search</span>(<span class="ruby-string">&quot;ABC ABCDAB ABCDABCDABDE&quot;</span>, <span class="ruby-string">&quot;ABCDEF&quot;</span>) <span class="ruby-comment">#=&gt; nil</span></pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-kmp_search-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-kmp_search-source'><span class="ruby-comment"># File lib/algorithms/search.rb, line 43</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">kmp_search</span>(<span class="ruby-identifier">string</span>, <span class="ruby-identifier">substring</span>)&#x000A; <span class="ruby-keyword">return</span> <span class="ruby-keyword">nil</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">string</span>.<span class="ruby-identifier">nil?</span> <span class="ruby-keyword">or</span> <span class="ruby-identifier">substring</span>.<span class="ruby-identifier">nil?</span>&#x000A; &#x000A; <span class="ruby-comment"># create failure function table</span>&#x000A; <span class="ruby-identifier">pos</span> = <span class="ruby-value">2</span>&#x000A; <span class="ruby-identifier">cnd</span> = <span class="ruby-value">0</span>&#x000A; <span class="ruby-identifier">failure_table</span> = [<span class="ruby-value">-1</span>, <span class="ruby-value">0</span>]&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">pos</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">substring</span>.<span class="ruby-identifier">length</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">substring</span>[<span class="ruby-identifier">pos</span> <span class="ruby-operator">-</span> <span class="ruby-value">1</span>] <span class="ruby-operator">==</span> <span class="ruby-identifier">substring</span>[<span class="ruby-identifier">cnd</span>]&#x000A; <span class="ruby-identifier">failure_table</span>[<span class="ruby-identifier">pos</span>] = <span class="ruby-identifier">cnd</span> <span class="ruby-operator">+</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">pos</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">cnd</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">elsif</span> <span class="ruby-identifier">cnd</span> <span class="ruby-operator">&gt;</span> <span class="ruby-value">0</span>&#x000A; <span class="ruby-identifier">cnd</span> = <span class="ruby-identifier">failure_table</span>[<span class="ruby-identifier">cnd</span>]&#x000A; <span class="ruby-keyword">else</span>&#x000A; <span class="ruby-identifier">failure_table</span>[<span class="ruby-identifier">pos</span>] = <span class="ruby-value">0</span>&#x000A; <span class="ruby-identifier">pos</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A;&#x000A; <span class="ruby-identifier">m</span> = <span class="ruby-identifier">i</span> = <span class="ruby-value">0</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">m</span> <span class="ruby-operator">+</span> <span class="ruby-identifier">i</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">string</span>.<span class="ruby-identifier">length</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">substring</span>[<span class="ruby-identifier">i</span>] <span class="ruby-operator">==</span> <span class="ruby-identifier">string</span>[<span class="ruby-identifier">m</span> <span class="ruby-operator">+</span> <span class="ruby-identifier">i</span>]&#x000A; <span class="ruby-identifier">i</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">return</span> <span class="ruby-identifier">m</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">i</span> <span class="ruby-operator">==</span> <span class="ruby-identifier">substring</span>.<span class="ruby-identifier">length</span>&#x000A; <span class="ruby-keyword">else</span>&#x000A; <span class="ruby-identifier">m</span> = <span class="ruby-identifier">m</span> <span class="ruby-operator">+</span> <span class="ruby-identifier">i</span> <span class="ruby-operator">-</span> <span class="ruby-identifier">failure_table</span>[<span class="ruby-identifier">i</span>]&#x000A; <span class="ruby-identifier">i</span> = <span class="ruby-identifier">failure_table</span>[<span class="ruby-identifier">i</span>] <span class="ruby-keyword">if</span> <span class="ruby-identifier">i</span> <span class="ruby-operator">&gt;</span> <span class="ruby-value">0</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">return</span> <span class="ruby-keyword">nil</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <h2>Public Instance methods</h2>
+ <div class='method public-instance' id='method-method-i-kmp_search'>
+ <a name='method-i-kmp_search'></a>
+ <div class='synopsis'>
+ <span class='name'>kmp_search</span>
+ <span class='arguments'>(substring)</span>
+ </div>
+ <div class='description'>
+
+ <p>Allows <a href="Search.html#method-c-kmp_search">::kmp_search</a> to be
+ called as an instance method in classes that include the <a
+ href="Search.html">Search</a> module.</p>
+
+ <pre class="ruby"><span class="ruby-keyword">class</span> <span class="ruby-constant">String</span>; <span class="ruby-identifier">include</span> <span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Search</span>; <span class="ruby-keyword">end</span>&#x000A;<span class="ruby-string">&quot;ABC ABCDAB ABCDABCDABDE&quot;</span>.<span class="ruby-identifier">kmp_search</span>(<span class="ruby-string">&quot;ABCDABD&quot;</span>) <span class="ruby-comment">#=&gt; 15</span></pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-kmp_search-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-kmp_search-source'><span class="ruby-comment"># File lib/algorithms/search.rb, line 80</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-identifier">kmp_search</span>(<span class="ruby-identifier">substring</span>)&#x000A; <span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Search</span>.<span class="ruby-identifier">kmp_search</span>(<span class="ruby-keyword">self</span>, <span class="ruby-identifier">substring</span>)&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ <div id='footer-push'></div>
+ </div>
+ <div id='footer'>
+ <a target="docwin" href="http://github.com/mislav/hanna/tree/master"><strong>Hanna</strong> RDoc template</a>
+ </div>
+ </body>
+</html>
View
390 classes/Algorithms/Sort.html
@@ -0,0 +1,390 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<html lang='en'>
+ <head>
+ <title>Algorithms::Sort</title>
+ <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'>
+ <link href='../../css/style.css' media='screen' rel='stylesheet' type='text/css'>
+ <script type='text/javascript'>
+ //<![CDATA[
+ function popupCode(url) {
+ window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
+ }
+
+ function toggleCode(id) {
+ var code = document.getElementById(id)
+
+ code.style.display = code.style.display != 'block' ? 'block' : 'none'
+ return true
+ }
+
+ // Make codeblocks hidden by default
+ document.writeln('<' + 'style type="text/css">.method .source pre { display: none }<\/style>')
+ //]]>
+ </script>
+ </head>
+ <body class='page'>
+ <div class='class' id='wrapper'>
+ <div class='header'>
+ <h1 class='name'>
+ <span class='type'>module</span>
+ Algorithms::Sort
+ </h1>
+ <ol class='paths'>
+ <li>
+ <a target="docwin" href="../../files/lib/algorithms/sort_rb.html">lib/algorithms/sort.rb</a>
+ </li>
+ </ol>
+ <div class='parent'>
+ Parent:
+ <strong><a target="docwin" href="../Algorithms.html">Algorithms</a></strong>
+ </div>
+ </div>
+ <div id='content'>
+ <div id='text'>
+ <div id='description'>
+
+ <p>This module implements sorting algorithms. Documentation is provided for
+ each algorithm.</p>
+ </div>
+ <div id='method-list'>
+ <h2>Methods</h2>
+ <h3>Public Class</h3>
+ <ol>
+ <li><a target="docwin" href="#method-c-bubble_sort">bubble_sort</a></li>
+ <li><a target="docwin" href="#method-c-comb_sort">comb_sort</a></li>
+ <li><a target="docwin" href="#method-c-dualpivot">dualpivot</a></li>
+ <li><a target="docwin" href="#method-c-dualpivot_swap">dualpivot_swap</a></li>
+ <li><a target="docwin" href="#method-c-dualpivotquicksort">dualpivotquicksort</a></li>
+ <li><a target="docwin" href="#method-c-heapsort">heapsort</a></li>
+ <li><a target="docwin" href="#method-c-insertion_sort">insertion_sort</a></li>
+ <li><a target="docwin" href="#method-c-merge">merge</a></li>
+ <li><a target="docwin" href="#method-c-mergesort">mergesort</a></li>
+ <li><a target="docwin" href="#method-c-partition">partition</a></li>
+ <li><a target="docwin" href="#method-c-quicksort">quicksort</a></li>
+ <li><a target="docwin" href="#method-c-selection_sort">selection_sort</a></li>
+ <li><a target="docwin" href="#method-c-shell_sort">shell_sort</a></li>
+ </ol>
+ </div>
+ <div id='context'>
+ </div>
+ <div id='section'>
+ <div id='methods'>
+ <h2>Public Class methods</h2>
+ <div class='method public-class' id='method-method-c-bubble_sort'>
+ <a name='method-c-bubble_sort'></a>
+ <div class='synopsis'>
+ <span class='name'>bubble_sort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>Bubble sort: A very naive sort that keeps swapping elements until the
+ container is sorted. Requirements: Needs to be able to compare elements
+ with &lt;=&gt;, and the [] []= methods should be implemented for the
+ container. Time Complexity: О(n^2) Space Complexity: О(n) total, O(1)
+ auxiliary Stable: Yes</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">bubble_sort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-bubble_sort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-bubble_sort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 16</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">bubble_sort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-identifier">loop</span> <span class="ruby-keyword">do</span>&#x000A; <span class="ruby-identifier">swapped</span> = <span class="ruby-keyword">false</span>&#x000A; (<span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>).<span class="ruby-identifier">times</span> <span class="ruby-keyword">do</span> <span class="ruby-operator">|</span><span class="ruby-identifier">i</span><span class="ruby-operator">|</span>&#x000A; <span class="ruby-keyword">if</span> (<span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>] <span class="ruby-operator">&lt;=&gt;</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>]) <span class="ruby-operator">==</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>], <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>], <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>] <span class="ruby-comment"># Swap</span>&#x000A; <span class="ruby-identifier">swapped</span> = <span class="ruby-keyword">true</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">break</span> <span class="ruby-keyword">unless</span> <span class="ruby-identifier">swapped</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-comb_sort'>
+ <a name='method-c-comb_sort'></a>
+ <div class='synopsis'>
+ <span class='name'>comb_sort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>Comb sort: A variation on bubble sort that dramatically improves
+ performance. Source: <a
+ href="http://yagni.com/combsort/">yagni.com/combsort/</a> Requirements:
+ Needs to be able to compare elements with &lt;=&gt;, and the [] []= methods
+ should be implemented for the container. Time Complexity: О(n^2) Space
+ Complexity: О(n) total, O(1) auxiliary Stable: Yes</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">comb_sort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-comb_sort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-comb_sort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 39</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">comb_sort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-identifier">container</span>&#x000A; <span class="ruby-identifier">gap</span> = <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span>&#x000A; <span class="ruby-identifier">loop</span> <span class="ruby-keyword">do</span>&#x000A; <span class="ruby-identifier">gap</span> = <span class="ruby-identifier">gap</span> * <span class="ruby-value">10</span><span class="ruby-operator">/</span><span class="ruby-value">13</span>&#x000A; <span class="ruby-identifier">gap</span> = <span class="ruby-value">11</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">gap</span> <span class="ruby-operator">==</span> <span class="ruby-value">9</span> <span class="ruby-operator">||</span> <span class="ruby-identifier">gap</span> <span class="ruby-operator">==</span> <span class="ruby-value">10</span>&#x000A; <span class="ruby-identifier">gap</span> = <span class="ruby-value">1</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">gap</span> <span class="ruby-operator">&lt;</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">swapped</span> = <span class="ruby-keyword">false</span>&#x000A; (<span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span> <span class="ruby-operator">-</span> <span class="ruby-identifier">gap</span>).<span class="ruby-identifier">times</span> <span class="ruby-keyword">do</span> <span class="ruby-operator">|</span><span class="ruby-identifier">i</span><span class="ruby-operator">|</span>&#x000A; <span class="ruby-keyword">if</span> (<span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>] <span class="ruby-operator">&lt;=&gt;</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span> <span class="ruby-operator">+</span> <span class="ruby-identifier">gap</span>]) <span class="ruby-operator">==</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>], <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span><span class="ruby-operator">+</span><span class="ruby-identifier">gap</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span><span class="ruby-operator">+</span><span class="ruby-identifier">gap</span>], <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>] <span class="ruby-comment"># Swap</span>&#x000A; <span class="ruby-identifier">swapped</span> = <span class="ruby-keyword">true</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">break</span> <span class="ruby-keyword">if</span> <span class="ruby-operator">!</span><span class="ruby-identifier">swapped</span> <span class="ruby-operator">&amp;&amp;</span> <span class="ruby-identifier">gap</span> <span class="ruby-operator">==</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-dualpivot'>
+ <a name='method-c-dualpivot'></a>
+ <div class='synopsis'>
+ <span class='name'>dualpivot</span>
+ <span class='arguments'>(container, left=0, right=container.size-1, div=3)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-dualpivot-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-dualpivot-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 278</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">dualpivot</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">left</span>=<span class="ruby-value">0</span>, <span class="ruby-identifier">right</span>=<span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>, <span class="ruby-identifier">div</span>=<span class="ruby-value">3</span>)&#x000A; <span class="ruby-identifier">length</span> = <span class="ruby-identifier">right</span> <span class="ruby-operator">-</span> <span class="ruby-identifier">left</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">length</span> <span class="ruby-operator">&lt;</span> <span class="ruby-value">27</span> <span class="ruby-comment"># insertion sort for tiny array</span>&#x000A; <span class="ruby-identifier">container</span>.<span class="ruby-identifier">each_with_index</span> <span class="ruby-keyword">do</span> <span class="ruby-operator">|</span><span class="ruby-identifier">data</span>,<span class="ruby-identifier">i</span><span class="ruby-operator">|</span>&#x000A; <span class="ruby-identifier">j</span> = <span class="ruby-identifier">i</span> <span class="ruby-operator">-</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">j</span> <span class="ruby-operator">&gt;=</span> <span class="ruby-value">0</span>&#x000A; <span class="ruby-keyword">break</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>] <span class="ruby-operator">&lt;=</span> <span class="ruby-identifier">data</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span> <span class="ruby-operator">+</span> <span class="ruby-value">1</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>]&#x000A; <span class="ruby-identifier">j</span> = <span class="ruby-identifier">j</span> <span class="ruby-operator">-</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span> <span class="ruby-operator">+</span> <span class="ruby-value">1</span>] = <span class="ruby-identifier">data</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">else</span> <span class="ruby-comment"># full dual-pivot quicksort</span>&#x000A; <span class="ruby-identifier">third</span> = <span class="ruby-identifier">length</span> <span class="ruby-operator">/</span> <span class="ruby-identifier">div</span>&#x000A; <span class="ruby-comment"># medians</span>&#x000A; <span class="ruby-identifier">m1</span> = <span class="ruby-identifier">left</span> <span class="ruby-operator">+</span> <span class="ruby-identifier">third</span>&#x000A; <span class="ruby-identifier">m2</span> = <span class="ruby-identifier">right</span> <span class="ruby-operator">-</span> <span class="ruby-identifier">third</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">m1</span> <span class="ruby-operator">&lt;=</span> <span class="ruby-identifier">left</span> &#x000A; <span class="ruby-identifier">m1</span> = <span class="ruby-identifier">left</span> <span class="ruby-operator">+</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">m2</span> <span class="ruby-operator">&gt;=</span> <span class="ruby-identifier">right</span>&#x000A; <span class="ruby-identifier">m2</span> = <span class="ruby-identifier">right</span> <span class="ruby-operator">-</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">m1</span>] <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">m2</span>]&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">m1</span>, <span class="ruby-identifier">left</span>)&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">m2</span>, <span class="ruby-identifier">right</span>)&#x000A; <span class="ruby-keyword">else</span>&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">m1</span>, <span class="ruby-identifier">right</span>)&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">m2</span>, <span class="ruby-identifier">left</span>)&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-comment"># pivots</span>&#x000A; <span class="ruby-identifier">pivot1</span> = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">left</span>]&#x000A; <span class="ruby-identifier">pivot2</span> = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">right</span>]&#x000A; <span class="ruby-comment"># pointers</span>&#x000A; <span class="ruby-identifier">less</span> = <span class="ruby-identifier">left</span> <span class="ruby-operator">+</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">great</span> = <span class="ruby-identifier">right</span> <span class="ruby-value">-1</span>&#x000A; <span class="ruby-comment"># sorting</span>&#x000A; <span class="ruby-identifier">k</span> = <span class="ruby-identifier">less</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">k</span> <span class="ruby-operator">&lt;=</span> <span class="ruby-identifier">great</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">k</span>] <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">pivot1</span>&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">k</span>, <span class="ruby-identifier">less</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>)&#x000A; <span class="ruby-keyword">elsif</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">k</span>] <span class="ruby-operator">&gt;</span> <span class="ruby-identifier">pivot2</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">k</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">great</span> <span class="ruby-operator">&amp;&amp;</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">great</span>] <span class="ruby-operator">&gt;</span> <span class="ruby-identifier">pivot2</span>&#x000A; <span class="ruby-identifier">great</span> <span class="ruby-operator">-=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">k</span>, <span class="ruby-identifier">great</span> <span class="ruby-operator">-=</span> <span class="ruby-value">1</span>)&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">k</span>] <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">pivot1</span>&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">k</span>, <span class="ruby-identifier">less</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>)&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">k</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-comment"># swaps</span>&#x000A; <span class="ruby-identifier">dist</span> = <span class="ruby-identifier">great</span> <span class="ruby-operator">-</span> <span class="ruby-identifier">less</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">dist</span> <span class="ruby-operator">&lt;</span> <span class="ruby-value">13</span>&#x000A; <span class="ruby-identifier">div</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">less</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>, <span class="ruby-identifier">left</span>)&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">great</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>, <span class="ruby-identifier">right</span>)&#x000A; <span class="ruby-comment"># subarrays</span>&#x000A; <span class="ruby-identifier">dualpivot</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">left</span>, <span class="ruby-identifier">less</span><span class="ruby-operator">-</span><span class="ruby-value">2</span>, <span class="ruby-identifier">div</span>)&#x000A; <span class="ruby-identifier">dualpivot</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">great</span><span class="ruby-operator">+</span><span class="ruby-value">2</span>, <span class="ruby-identifier">right</span>, <span class="ruby-identifier">div</span>)&#x000A; <span class="ruby-comment"># equal elements</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">dist</span> <span class="ruby-operator">&gt;</span> <span class="ruby-identifier">length</span> <span class="ruby-operator">-</span> <span class="ruby-value">13</span> <span class="ruby-operator">&amp;&amp;</span> <span class="ruby-identifier">pivot1</span> <span class="ruby-operator">!=</span> <span class="ruby-identifier">pivot2</span>&#x000A; <span class="ruby-keyword">for</span> <span class="ruby-identifier">k</span> <span class="ruby-keyword">in</span> <span class="ruby-identifier">less</span><span class="ruby-operator">..</span><span class="ruby-identifier">great</span> <span class="ruby-keyword">do</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">k</span>] <span class="ruby-operator">==</span> <span class="ruby-identifier">pivot1</span>&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">k</span>, <span class="ruby-identifier">less</span>)&#x000A; <span class="ruby-identifier">less</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">elsif</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">k</span>] <span class="ruby-operator">==</span> <span class="ruby-identifier">pivot2</span>&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">k</span>, <span class="ruby-identifier">great</span>)&#x000A; <span class="ruby-identifier">great</span> <span class="ruby-operator">-=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">k</span>] <span class="ruby-operator">==</span> <span class="ruby-identifier">pivot1</span>&#x000A; <span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">k</span>, <span class="ruby-identifier">less</span>)&#x000A; <span class="ruby-identifier">less</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-comment"># subarray</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">pivot1</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">pivot2</span>&#x000A; <span class="ruby-identifier">dualpivot</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">less</span>, <span class="ruby-identifier">great</span>, <span class="ruby-identifier">div</span>)&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-dualpivot_swap'>
+ <a name='method-c-dualpivot_swap'></a>
+ <div class='synopsis'>
+ <span class='name'>dualpivot_swap</span>
+ <span class='arguments'>(container, i, j)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-dualpivot_swap-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-dualpivot_swap-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 364</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">dualpivot_swap</span>(<span class="ruby-identifier">container</span>, <span class="ruby-identifier">i</span>, <span class="ruby-identifier">j</span>)&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>], <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>], <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>]&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-dualpivotquicksort'>
+ <a name='method-c-dualpivotquicksort'></a>
+ <div class='synopsis'>
+ <span class='name'>dualpivotquicksort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>Dual-Pivot Quicksort is a variation of Quicksort by Vladimir Yaroslavskiy.
+ This is an implementation of the algorithm as it was found in the original
+ research paper:</p>
+
+ <p><a
+ href="http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf">iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf</a></p>
+
+ <p>Mirror: <a
+ href="http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf">codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf</a></p>
+
+ <p>“This algorithm offers O(n log(n)) performance on many data sets that cause
+ other quicksorts to degrade to quadratic performance, and is typically
+ faster than traditional (one-pivot) Quicksort implementations.”</p>
+
+ <pre>-- http://download.oracle.com/javase/7/docs/api/java/util/Arrays.html</pre>
+
+ <p>The algorithm was improved by Vladimir Yaroslavskiy, Jon Bentley, and
+ Joshua Bloch, and was implemented as the default sort algorithm for
+ primatives in Java 7.</p>
+
+ <p>Implementation in the Java JDK as of November, 2011: <a
+ href="http://www.docjar.com/html/api/java/util/DualPivotQuicksort.java.html">www.docjar.com/html/api/java/util/DualPivotQuicksort.java.html</a></p>
+
+ <p>It is proved that for the Dual-Pivot Quicksort the average number of
+ comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
+ whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
+ respectively. This has been fully examined mathematically and
+ experimentally.</p>
+
+ <p>Requirements: Container should implement pop and include the Enumerable
+ module. Time Complexity: О(n log n) average, О(n log n) worst-case Space
+ Complexity: О(n) auxiliary</p>
+
+ <p>Stable: No</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">dualpivotquicksort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-dualpivotquicksort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-dualpivotquicksort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 273</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">dualpivotquicksort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-keyword">return</span> <span class="ruby-identifier">container</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span> <span class="ruby-operator">&lt;=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">dualpivot</span>(<span class="ruby-identifier">container</span>, <span class="ruby-value">0</span>, <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>, <span class="ruby-value">3</span>)&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-heapsort'>
+ <a name='method-c-heapsort'></a>
+ <div class='synopsis'>
+ <span class='name'>heapsort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>Heap sort: Uses a heap (implemented by the <a
+ href="../Containers.html">Containers</a> module) to sort the collection.
+ Requirements: Needs to be able to compare elements with &lt;=&gt; Time
+ Complexity: О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">heapsort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-heapsort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-heapsort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 85</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">heapsort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-identifier">heap</span> = <span class="ruby-constant">Containers</span><span class="ruby-operator">::</span><span class="ruby-constant">Heap</span>.<span class="ruby-identifier">new</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-identifier">ary</span> = []&#x000A; <span class="ruby-identifier">ary</span> <span class="ruby-operator">&lt;&lt;</span> <span class="ruby-identifier">heap</span>.<span class="ruby-identifier">pop</span> <span class="ruby-keyword">until</span> <span class="ruby-identifier">heap</span>.<span class="ruby-identifier">empty?</span>&#x000A; <span class="ruby-identifier">ary</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-insertion_sort'>
+ <a name='method-c-insertion_sort'></a>
+ <div class='synopsis'>
+ <span class='name'>insertion_sort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>Insertion sort: Elements are inserted sequentially into the right position.
+ Requirements: Needs to be able to compare elements with &lt;=&gt;, and the
+ [] []= methods should be implemented for the container. Time Complexity:
+ О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">insertion_sort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-insertion_sort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-insertion_sort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 100</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">insertion_sort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-keyword">return</span> <span class="ruby-identifier">container</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span> <span class="ruby-operator">&lt;</span> <span class="ruby-value">2</span>&#x000A; (<span class="ruby-value">1</span><span class="ruby-operator">..</span><span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>).<span class="ruby-identifier">each</span> <span class="ruby-keyword">do</span> <span class="ruby-operator">|</span><span class="ruby-identifier">i</span><span class="ruby-operator">|</span>&#x000A; <span class="ruby-identifier">value</span> = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>]&#x000A; <span class="ruby-identifier">j</span> = <span class="ruby-identifier">i</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">j</span> <span class="ruby-operator">&gt;=</span> <span class="ruby-value">0</span> <span class="ruby-keyword">and</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>] <span class="ruby-operator">&gt;</span> <span class="ruby-identifier">value</span> <span class="ruby-keyword">do</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>]&#x000A; <span class="ruby-identifier">j</span> = <span class="ruby-identifier">j</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>] = <span class="ruby-identifier">value</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-merge'>
+ <a name='method-c-merge'></a>
+ <div class='synopsis'>
+ <span class='name'>merge</span>
+ <span class='arguments'>(left, right)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-merge-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-merge-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 230</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">merge</span>(<span class="ruby-identifier">left</span>, <span class="ruby-identifier">right</span>)&#x000A; <span class="ruby-identifier">sorted</span> = []&#x000A; <span class="ruby-keyword">until</span> <span class="ruby-identifier">left</span>.<span class="ruby-identifier">empty?</span> <span class="ruby-keyword">or</span> <span class="ruby-identifier">right</span>.<span class="ruby-identifier">empty?</span>&#x000A; <span class="ruby-identifier">left</span>.<span class="ruby-identifier">first</span> <span class="ruby-operator">&lt;=</span> <span class="ruby-identifier">right</span>.<span class="ruby-identifier">first</span> <span class="ruby-operator">?</span> <span class="ruby-identifier">sorted</span> <span class="ruby-operator">&lt;&lt;</span> <span class="ruby-identifier">left</span>.<span class="ruby-identifier">shift</span> <span class="ruby-operator">:</span> <span class="ruby-identifier">sorted</span> <span class="ruby-operator">&lt;&lt;</span> <span class="ruby-identifier">right</span>.<span class="ruby-identifier">shift</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">sorted</span> <span class="ruby-operator">+</span> <span class="ruby-identifier">left</span> <span class="ruby-operator">+</span> <span class="ruby-identifier">right</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-mergesort'>
+ <a name='method-c-mergesort'></a>
+ <div class='synopsis'>
+ <span class='name'>mergesort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>Mergesort: A stable divide-and-conquer sort that sorts small chunks of the
+ container and then merges them together. Returns an array of the sorted
+ elements. Requirements: Container should implement [] Time Complexity: О(n
+ log n) average and worst-case Space Complexity: О(n) auxiliary Stable: Yes</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">mergesort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-mergesort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-mergesort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 222</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">mergesort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-keyword">return</span> <span class="ruby-identifier">container</span> <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span> <span class="ruby-operator">&lt;=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">mid</span> = <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span> <span class="ruby-operator">/</span> <span class="ruby-value">2</span>&#x000A; <span class="ruby-identifier">left</span> = <span class="ruby-identifier">container</span>[<span class="ruby-value">0</span><span class="ruby-operator">...</span><span class="ruby-identifier">mid</span>]&#x000A; <span class="ruby-identifier">right</span> = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">mid</span><span class="ruby-operator">...</span><span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span>]&#x000A; <span class="ruby-identifier">merge</span>(<span class="ruby-identifier">mergesort</span>(<span class="ruby-identifier">left</span>), <span class="ruby-identifier">mergesort</span>(<span class="ruby-identifier">right</span>))&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-partition'>
+ <a name='method-c-partition'></a>
+ <div class='synopsis'>
+ <span class='name'>partition</span>
+ <span class='arguments'>(data, left, right)</span>
+ </div>
+ <div class='description'>
+
+ <p>Quicksort: A divide-and-conquer sort that recursively partitions a
+ container until it is sorted. Requirements: Container should implement pop
+ and include the Enumerable module. Time Complexity: О(n log n) average,
+ O(n^2) worst-case Space Complexity: О(n) auxiliary Stable: No</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">quicksort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+
+ <p>def self.quicksort(container)</p>
+
+ <pre class="ruby"><span class="ruby-keyword">return</span> [] <span class="ruby-keyword">if</span> <span class="ruby-identifier">container</span>.<span class="ruby-identifier">empty?</span>&#x000A;&#x000A;<span class="ruby-identifier">x</span>, *<span class="ruby-identifier">xs</span> = <span class="ruby-identifier">container</span>&#x000A;&#x000A;<span class="ruby-identifier">quicksort</span>(<span class="ruby-identifier">xs</span>.<span class="ruby-identifier">select</span> { <span class="ruby-operator">|</span><span class="ruby-identifier">i</span><span class="ruby-operator">|</span> <span class="ruby-identifier">i</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">x</span> }) <span class="ruby-operator">+</span> [<span class="ruby-identifier">x</span>] <span class="ruby-operator">+</span> <span class="ruby-identifier">quicksort</span>(<span class="ruby-identifier">xs</span>.<span class="ruby-identifier">select</span> { <span class="ruby-operator">|</span><span class="ruby-identifier">i</span><span class="ruby-operator">|</span> <span class="ruby-identifier">i</span> <span class="ruby-operator">&gt;=</span> <span class="ruby-identifier">x</span> })</pre>
+
+ <p>end</p>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-partition-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-partition-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 154</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">partition</span>(<span class="ruby-identifier">data</span>, <span class="ruby-identifier">left</span>, <span class="ruby-identifier">right</span>)&#x000A; <span class="ruby-identifier">pivot</span> = <span class="ruby-identifier">data</span>[<span class="ruby-identifier">front</span>]&#x000A; <span class="ruby-identifier">left</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A;&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">left</span> <span class="ruby-operator">&lt;=</span> <span class="ruby-identifier">right</span> <span class="ruby-keyword">do</span>&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">data</span>[<span class="ruby-identifier">frontUnknown</span>] <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">pivot</span>&#x000A; <span class="ruby-identifier">back</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">data</span>[<span class="ruby-identifier">frontUnknown</span>], <span class="ruby-identifier">data</span>[<span class="ruby-identifier">back</span>] = <span class="ruby-identifier">data</span>[<span class="ruby-identifier">back</span>], <span class="ruby-identifier">data</span>[<span class="ruby-identifier">frontUnknown</span>] <span class="ruby-comment"># Swap</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A;&#x000A; <span class="ruby-identifier">frontUnknown</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A;&#x000A; <span class="ruby-identifier">data</span>[<span class="ruby-identifier">front</span>], <span class="ruby-identifier">data</span>[<span class="ruby-identifier">back</span>] = <span class="ruby-identifier">data</span>[<span class="ruby-identifier">back</span>], <span class="ruby-identifier">data</span>[<span class="ruby-identifier">front</span>] <span class="ruby-comment"># Swap</span>&#x000A; <span class="ruby-identifier">back</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-quicksort'>
+ <a name='method-c-quicksort'></a>
+ <div class='synopsis'>
+ <span class='name'>quicksort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>def self.quicksort(container, left = 0, right = container.size - 1)</p>
+
+ <pre>if left &lt; right &#x000A; middle = partition(container, left, right)&#x000A; quicksort(container, left, middle - 1)&#x000A; quicksort(container, middle + 1, right)&#x000A;end</pre>
+
+ <p>end</p>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-quicksort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-quicksort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 180</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">quicksort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-identifier">bottom</span>, <span class="ruby-identifier">top</span> = [], []&#x000A; <span class="ruby-identifier">top</span>[<span class="ruby-value">0</span>] = <span class="ruby-value">0</span>&#x000A; <span class="ruby-identifier">bottom</span>[<span class="ruby-value">0</span>] = <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span>&#x000A; <span class="ruby-identifier">i</span> = <span class="ruby-value">0</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">i</span> <span class="ruby-operator">&gt;=</span> <span class="ruby-value">0</span> <span class="ruby-keyword">do</span>&#x000A; <span class="ruby-identifier">l</span> = <span class="ruby-identifier">top</span>[<span class="ruby-identifier">i</span>]&#x000A; <span class="ruby-identifier">r</span> = <span class="ruby-identifier">bottom</span>[<span class="ruby-identifier">i</span>] <span class="ruby-operator">-</span> <span class="ruby-value">1</span>;&#x000A; <span class="ruby-keyword">if</span> <span class="ruby-identifier">l</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">r</span>&#x000A; <span class="ruby-identifier">pivot</span> = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">l</span>]&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">l</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">r</span> <span class="ruby-keyword">do</span>&#x000A; <span class="ruby-identifier">r</span> <span class="ruby-operator">-=</span> <span class="ruby-value">1</span> <span class="ruby-keyword">while</span> (<span class="ruby-identifier">container</span>[<span class="ruby-identifier">r</span>] <span class="ruby-operator">&gt;=</span> <span class="ruby-identifier">pivot</span> <span class="ruby-operator">&amp;&amp;</span> <span class="ruby-identifier">l</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">r</span>)&#x000A; <span class="ruby-keyword">if</span> (<span class="ruby-identifier">l</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">r</span>)&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">l</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">r</span>]&#x000A; <span class="ruby-identifier">l</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">l</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span> <span class="ruby-keyword">while</span> (<span class="ruby-identifier">container</span>[<span class="ruby-identifier">l</span>] <span class="ruby-operator">&lt;=</span> <span class="ruby-identifier">pivot</span> <span class="ruby-operator">&amp;&amp;</span> <span class="ruby-identifier">l</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">r</span>)&#x000A; <span class="ruby-keyword">if</span> (<span class="ruby-identifier">l</span> <span class="ruby-operator">&lt;</span> <span class="ruby-identifier">r</span>)&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">r</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">l</span>]&#x000A; <span class="ruby-identifier">r</span> <span class="ruby-operator">-=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">l</span>] = <span class="ruby-identifier">pivot</span>&#x000A; <span class="ruby-identifier">top</span>[<span class="ruby-identifier">i</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>] = <span class="ruby-identifier">l</span> <span class="ruby-operator">+</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-identifier">bottom</span>[<span class="ruby-identifier">i</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>] = <span class="ruby-identifier">bottom</span>[<span class="ruby-identifier">i</span>]&#x000A; <span class="ruby-identifier">bottom</span>[<span class="ruby-identifier">i</span>] = <span class="ruby-identifier">l</span>&#x000A; <span class="ruby-identifier">i</span> <span class="ruby-operator">+=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">else</span>&#x000A; <span class="ruby-identifier">i</span> <span class="ruby-operator">-=</span> <span class="ruby-value">1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span> &#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-selection_sort'>
+ <a name='method-c-selection_sort'></a>
+ <div class='synopsis'>
+ <span class='name'>selection_sort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>Selection sort: A naive sort that goes through the container and selects
+ the smallest element, putting it at the beginning. Repeat until the end is
+ reached. Requirements: Needs to be able to compare elements with &lt;=&gt;,
+ and the [] []= methods should be implemented for the container. Time
+ Complexity: О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">selection_sort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-selection_sort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-selection_sort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 67</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">selection_sort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-value">0</span>.<span class="ruby-identifier">upto</span>(<span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>) <span class="ruby-keyword">do</span> <span class="ruby-operator">|</span><span class="ruby-identifier">i</span><span class="ruby-operator">|</span>&#x000A; <span class="ruby-identifier">min</span> = <span class="ruby-identifier">i</span>&#x000A; (<span class="ruby-identifier">i</span><span class="ruby-operator">+</span><span class="ruby-value">1</span>).<span class="ruby-identifier">upto</span>(<span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>) <span class="ruby-keyword">do</span> <span class="ruby-operator">|</span><span class="ruby-identifier">j</span><span class="ruby-operator">|</span>&#x000A; <span class="ruby-identifier">min</span> = <span class="ruby-identifier">j</span> <span class="ruby-keyword">if</span> (<span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>] <span class="ruby-operator">&lt;=&gt;</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">min</span>]) <span class="ruby-operator">==</span> <span class="ruby-value">-1</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>], <span class="ruby-identifier">container</span>[<span class="ruby-identifier">min</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">min</span>], <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>] <span class="ruby-comment"># Swap</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ <div class='method public-class' id='method-method-c-shell_sort'>
+ <a name='method-c-shell_sort'></a>
+ <div class='synopsis'>
+ <span class='name'>shell_sort</span>
+ <span class='arguments'>(container)</span>
+ </div>
+ <div class='description'>
+
+ <p>Shell sort: Similar approach as insertion sort but slightly better.
+ Requirements: Needs to be able to compare elements with &lt;=&gt;, and the
+ [] []= methods should be implemented for the container. Time Complexity:
+ О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes</p>
+
+ <pre class="ruby"><span class="ruby-constant">Algorithms</span><span class="ruby-operator">::</span><span class="ruby-constant">Sort</span>.<span class="ruby-identifier">shell_sort</span> [<span class="ruby-value">5</span>, <span class="ruby-value">4</span>, <span class="ruby-value">3</span>, <span class="ruby-value">1</span>, <span class="ruby-value">2</span>] =<span class="ruby-operator">&gt;</span> [<span class="ruby-value">1</span>, <span class="ruby-value">2</span>, <span class="ruby-value">3</span>, <span class="ruby-value">4</span>, <span class="ruby-value">5</span>]</pre>
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-shell_sort-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-shell_sort-source'><span class="ruby-comment"># File lib/algorithms/sort.rb, line 122</span>&#x000A;<span class="ruby-keyword">def</span> <span class="ruby-keyword">self</span>.<span class="ruby-identifier">shell_sort</span>(<span class="ruby-identifier">container</span>)&#x000A; <span class="ruby-identifier">increment</span> = <span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span><span class="ruby-operator">/</span><span class="ruby-value">2</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">increment</span> <span class="ruby-operator">&gt;</span> <span class="ruby-value">0</span> <span class="ruby-keyword">do</span>&#x000A; (<span class="ruby-identifier">increment</span><span class="ruby-operator">..</span><span class="ruby-identifier">container</span>.<span class="ruby-identifier">size</span><span class="ruby-operator">-</span><span class="ruby-value">1</span>).<span class="ruby-identifier">each</span> <span class="ruby-keyword">do</span> <span class="ruby-operator">|</span><span class="ruby-identifier">i</span><span class="ruby-operator">|</span>&#x000A; <span class="ruby-identifier">temp</span> = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">i</span>]&#x000A; <span class="ruby-identifier">j</span> = <span class="ruby-identifier">i</span>&#x000A; <span class="ruby-keyword">while</span> <span class="ruby-identifier">j</span> <span class="ruby-operator">&gt;=</span> <span class="ruby-identifier">increment</span> <span class="ruby-operator">&amp;&amp;</span> <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span> <span class="ruby-operator">-</span> <span class="ruby-identifier">increment</span>] <span class="ruby-operator">&gt;</span> <span class="ruby-identifier">temp</span> <span class="ruby-keyword">do</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>] = <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span><span class="ruby-operator">-</span><span class="ruby-identifier">increment</span>]&#x000A; <span class="ruby-identifier">j</span> <span class="ruby-operator">-=</span> <span class="ruby-identifier">increment</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>[<span class="ruby-identifier">j</span>] = <span class="ruby-identifier">temp</span>&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">increment</span> = (<span class="ruby-identifier">increment</span> <span class="ruby-operator">==</span> <span class="ruby-value">2</span> <span class="ruby-operator">?</span> <span class="ruby-value">1</span> <span class="ruby-operator">:</span> (<span class="ruby-identifier">increment</span> <span class="ruby-operator">/</span> <span class="ruby-value">2.2</span>).<span class="ruby-identifier">round</span>)&#x000A; <span class="ruby-keyword">end</span>&#x000A; <span class="ruby-identifier">container</span>&#x000A;<span class="ruby-keyword">end</span></pre>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ <div id='footer-push'></div>
+ </div>
+ <div id='footer'>
+ <a target="docwin" href="http://github.com/mislav/hanna/tree/master"><strong>Hanna</strong> RDoc template</a>
+ </div>
+ </body>
+</html>
View
83 classes/Algorithms/String.html
@@ -0,0 +1,83 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<html lang='en'>
+ <head>
+ <title>Algorithms::String</title>
+ <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'>
+ <link href='../../css/style.css' media='screen' rel='stylesheet' type='text/css'>
+ <script type='text/javascript'>
+ //<![CDATA[
+ function popupCode(url) {
+ window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
+ }
+
+ function toggleCode(id) {
+ var code = document.getElementById(id)
+
+ code.style.display = code.style.display != 'block' ? 'block' : 'none'
+ return true
+ }
+
+ // Make codeblocks hidden by default
+ document.writeln('<' + 'style type="text/css">.method .source pre { display: none }<\/style>')
+ //]]>
+ </script>
+ </head>
+ <body class='page'>
+ <div class='class' id='wrapper'>
+ <div class='header'>
+ <h1 class='name'>
+ <span class='type'>module</span>
+ Algorithms::String
+ </h1>
+ <ol class='paths'>
+ <li>
+ <a target="docwin" href="../../files/ext/algorithms/string/string_c.html">ext/algorithms/string/string.c</a>
+ </li>
+ </ol>
+ <div class='parent'>
+ Parent:
+ <strong><a target="docwin" href="../Algorithms.html">Algorithms</a></strong>
+ </div>
+ </div>
+ <div id='content'>
+ <div id='text'>
+ <div id='description'></div>
+ <div id='method-list'>
+ <h2>Methods</h2>
+ <h3>Public Class</h3>
+ <ol>
+ <li><a target="docwin" href="#method-c-levenshtein_dist">levenshtein_dist</a></li>
+ </ol>
+ </div>
+ <div id='context'>
+ </div>
+ <div id='section'>
+ <div id='methods'>
+ <h2>Public Class methods</h2>
+ <div class='method public-class' id='method-method-c-levenshtein_dist'>
+ <a name='method-c-levenshtein_dist'></a>
+ <div class='synopsis'>
+ <span class='name'>levenshtein_dist</span>
+ <span class='arguments'>(p1, p2)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-levenshtein_dist-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-levenshtein_dist-source'>static VALUE lev_dist(VALUE self, VALUE str1, VALUE str2) {&#x000A; return LONG2FIX(levenshtein_distance( str1, str2 ));&#x000A;}</pre>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ <div id='footer-push'></div>
+ </div>
+ <div id='footer'>
+ <a target="docwin" href="http://github.com/mislav/hanna/tree/master"><strong>Hanna</strong> RDoc template</a>
+ </div>
+ </body>
+</html>
View
93 classes/Containers.html
@@ -0,0 +1,93 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<html lang='en'>
+ <head>
+ <title>Containers</title>
+ <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'>
+ <link href='../css/style.css' media='screen' rel='stylesheet' type='text/css'>
+ <script type='text/javascript'>
+ //<![CDATA[
+ function popupCode(url) {
+ window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
+ }
+
+ function toggleCode(id) {
+ var code = document.getElementById(id)
+
+ code.style.display = code.style.display != 'block' ? 'block' : 'none'
+ return true
+ }
+
+ // Make codeblocks hidden by default
+ document.writeln('<' + 'style type="text/css">.method .source pre { display: none }<\/style>')
+ //]]>
+ </script>
+ </head>
+ <body class='page'>
+ <div class='class' id='wrapper'>
+ <div class='header'>
+ <h1 class='name'>
+ <span class='type'>module</span>
+ Containers
+ </h1>
+ <ol class='paths'>
+ <li>
+ <a target="docwin" href="../files/ext/containers/bst/bst_c.html">ext/containers/bst/bst.c</a>
+ </li>
+ <li class='other'>
+ <a target="docwin" href="../files/ext/containers/deque/deque_c.html">ext/containers/deque/deque.c</a>
+ </li>
+ <li class='other'>
+ <a target="docwin" href="../files/ext/containers/rbtree_map/rbtree_c.html">ext/containers/rbtree_map/rbtree.c</a>
+ </li>
+ <li class='other'>
+ <a target="docwin" href="../files/ext/containers/splaytree_map/splaytree_c.html">ext/containers/splaytree_map/splaytree.c</a>
+ </li>
+ <li class='other'>
+ <a target="docwin" href="../files/lib/algorithms_rb.html">lib/algorithms.rb</a>
+ </li>
+ <li>
+ <a class='show' href='#' onclick='this.parentNode.parentNode.className += " expanded"; this.parentNode.removeChild(this); return false'>show all</a>
+ </li>
+ </ol>
+ <div class='parent'>
+ Parent:
+ <strong><a target="docwin" href="../files/lib/algorithms_rb.html">algorithms.rb</a></strong>
+ </div>
+ </div>
+ <div id='content'>
+ <div id='text'>
+ <div id='description'></div>
+ <div id='context'>
+ </div>
+ <div id='class-list'>
+ <h2>Classes and Modules</h2>
+ <ol>
+ <li><a target="docwin" href="Containers/CBst.html">Containers::CBst</a></li>
+ <li><a target="docwin" href="Containers/CDeque.html">Containers::CDeque</a></li>
+ <li><a target="docwin" href="Containers/CRBTreeMap.html">Containers::CRBTreeMap</a></li>
+ <li><a target="docwin" href="Containers/CSplayTreeMap.html">Containers::CSplayTreeMap</a></li>
+ <li><a target="docwin" href="Containers/Heap.html">Containers::Heap</a></li>
+ <li><a target="docwin" href="Containers/KDTree.html">Containers::KDTree</a></li>
+ <li><a target="docwin" href="Containers/MaxHeap.html">Containers::MaxHeap</a></li>
+ <li><a target="docwin" href="Containers/MinHeap.html">Containers::MinHeap</a></li>
+ <li><a target="docwin" href="Containers/PriorityQueue.html">Containers::PriorityQueue</a></li>
+ <li><a target="docwin" href="Containers/Queue.html">Containers::Queue</a></li>
+ <li><a target="docwin" href="Containers/RubyDeque.html">Containers::RubyDeque</a></li>
+ <li><a target="docwin" href="Containers/RubyRBTreeMap.html">Containers::RubyRBTreeMap</a></li>
+ <li><a target="docwin" href="Containers/RubySplayTreeMap.html">Containers::RubySplayTreeMap</a></li>
+ <li><a target="docwin" href="Containers/Stack.html">Containers::Stack</a></li>
+ <li><a target="docwin" href="Containers/SuffixArray.html">Containers::SuffixArray</a></li>
+ <li><a target="docwin" href="Containers/Trie.html">Containers::Trie</a></li>
+ </ol>
+ </div>
+ <div id='section'>
+ </div>
+ </div>
+ </div>
+ <div id='footer-push'></div>
+ </div>
+ <div id='footer'>
+ <a target="docwin" href="http://github.com/mislav/hanna/tree/master"><strong>Hanna</strong> RDoc template</a>
+ </div>
+ </body>
+</html>
View
167 classes/Containers/CBst.html
@@ -0,0 +1,167 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<html lang='en'>
+ <head>
+ <title>Containers::CBst</title>
+ <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'>
+ <link href='../../css/style.css' media='screen' rel='stylesheet' type='text/css'>
+ <script type='text/javascript'>
+ //<![CDATA[
+ function popupCode(url) {
+ window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
+ }
+
+ function toggleCode(id) {
+ var code = document.getElementById(id)
+
+ code.style.display = code.style.display != 'block' ? 'block' : 'none'
+ return true
+ }
+
+ // Make codeblocks hidden by default
+ document.writeln('<' + 'style type="text/css">.method .source pre { display: none }<\/style>')
+ //]]>
+ </script>
+ </head>
+ <body class='page'>
+ <div class='class' id='wrapper'>
+ <div class='header'>
+ <h1 class='name'>
+ <span class='type'>class</span>
+ Containers::CBst
+ </h1>
+ <ol class='paths'>
+ <li>
+ <a target="docwin" href="../../files/ext/containers/bst/bst_c.html">ext/containers/bst/bst.c</a>
+ </li>
+ </ol>
+ <div class='parent'>
+ Parent:
+ <strong><a target="docwin" href="../Containers.html">Containers</a></strong>
+ </div>
+ </div>
+ <div id='content'>
+ <div id='text'>
+ <div id='description'></div>
+ <div id='method-list'>
+ <h2>Methods</h2>
+ <h3>Public Class</h3>
+ <ol>
+ <li><a target="docwin" href="#method-c-new">new</a></li>
+ </ol>
+ <h3>Public Instance</h3>
+ <ol>
+ <li><a target="docwin" href="#method-i-delete">delete</a></li>
+ <li><a target="docwin" href="#method-i-each">each</a></li>
+ <li><a target="docwin" href="#method-i-push">push</a></li>
+ <li><a target="docwin" href="#method-i-size">size</a></li>
+ </ol>
+ </div>
+ <div id='context'>
+ </div>
+ <div id='section'>
+ <div id='aliases-list'>
+ <h2>Public Instance Aliases</h2>
+ <div class='name-list'>
+ <table summary='Public Instance Aliases'>
+ <tr class='top-aligned-row context-row'>
+ <td class='context-item-name'>[]=</td>
+ <td>-&gt;</td>
+ <td class='context-item-value'><a target="docwin" href="#method-i-push">push</a></td>
+ </tr>
+ </table>
+ </div>
+ </div>
+ <div id='methods'>
+ <h2>Public Class methods</h2>
+ <div class='method public-class' id='method-method-c-new'>
+ <a name='method-c-new'></a>
+ <div class='synopsis'>
+ <span class='name'>new</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-new-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-new-source'>static VALUE bst_initialize(VALUE self) {&#x000A; return self;&#x000A;}</pre>
+ </div>
+ </div>
+ <h2>Public Instance methods</h2>
+ <div class='method public-instance' id='method-method-i-delete'>
+ <a name='method-i-delete'></a>
+ <div class='synopsis'>
+ <span class='name'>delete</span>
+ <span class='arguments'>(p1)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-delete-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-delete-source'>static VALUE rb_bst_delete(VALUE self, VALUE key) {&#x000A; bst *tree = get_bst_from_self(self);&#x000A; bst_node *tobeDeleted = search_node(tree, tree-&gt;root, key);&#x000A; if(tobeDeleted) { &#x000A; tree-&gt;size -= 1;&#x000A; bst_node *deletedNode = delete_node(&amp;(tree-&gt;root),tobeDeleted);&#x000A; return deletedNode-&gt;value;&#x000A; }&#x000A; return Qnil;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-each'>
+ <a name='method-i-each'></a>
+ <div class='synopsis'>
+ <span class='name'>each</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-each-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-each-source'>static VALUE rb_bst_each(VALUE self) {&#x000A; bst *tree = get_bst_from_self(self);&#x000A; bst_each(tree, &amp;bst_each_helper, NULL);&#x000A; return self;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-push'>
+ <a name='method-i-push'></a>
+ <div class='synopsis'>
+ <span class='name'>push</span>
+ <span class='arguments'>(p1, p2)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-push-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-push-source'>static VALUE rb_bst_push_value(VALUE self, VALUE key, VALUE value) {&#x000A; bst *tree = get_bst_from_self(self);&#x000A; insert_element(tree, &amp;(tree-&gt;root), create_node(key,value));&#x000A; tree-&gt;size++;&#x000A; return self;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-size'>
+ <a name='method-i-size'></a>
+ <div class='synopsis'>
+ <span class='name'>size</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-size-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-size-source'>static VALUE rb_bst_size(VALUE self) { &#x000A; bst *tree;&#x000A; Data_Get_Struct(self,bst,tree);&#x000A; return INT2FIX(tree-&gt;size);&#x000A;}</pre>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ <div id='footer-push'></div>
+ </div>
+ <div id='footer'>
+ <a target="docwin" href="http://github.com/mislav/hanna/tree/master"><strong>Hanna</strong> RDoc template</a>
+ </div>
+ </body>
+</html>
View
296 classes/Containers/CDeque.html
@@ -0,0 +1,296 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<html lang='en'>
+ <head>
+ <title>Containers::CDeque</title>
+ <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'>
+ <link href='../../css/style.css' media='screen' rel='stylesheet' type='text/css'>
+ <script type='text/javascript'>
+ //<![CDATA[
+ function popupCode(url) {
+ window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
+ }
+
+ function toggleCode(id) {
+ var code = document.getElementById(id)
+
+ code.style.display = code.style.display != 'block' ? 'block' : 'none'
+ return true
+ }
+
+ // Make codeblocks hidden by default
+ document.writeln('<' + 'style type="text/css">.method .source pre { display: none }<\/style>')
+ //]]>
+ </script>
+ </head>
+ <body class='page'>
+ <div class='class' id='wrapper'>
+ <div class='header'>
+ <h1 class='name'>
+ <span class='type'>class</span>
+ Containers::CDeque
+ </h1>
+ <ol class='paths'>
+ <li>
+ <a target="docwin" href="../../files/ext/containers/bst/bst_c.html">ext/containers/bst/bst.c</a>
+ </li>
+ </ol>
+ <div class='parent'>
+ Parent:
+ <strong><a target="docwin" href="../Containers.html">Containers</a></strong>
+ </div>
+ </div>
+ <div id='content'>
+ <div id='text'>
+ <div id='description'></div>
+ <div id='method-list'>
+ <h2>Methods</h2>
+ <h3>Public Class</h3>
+ <ol>
+ <li><a target="docwin" href="#method-c-new">new</a></li>
+ </ol>
+ <h3>Public Instance</h3>
+ <ol>
+ <li><a target="docwin" href="#method-i-back">back</a></li>
+ <li><a target="docwin" href="#method-i-clear">clear</a></li>
+ <li><a target="docwin" href="#method-i-each_backward">each_backward</a></li>
+ <li><a target="docwin" href="#method-i-each_forward">each_forward</a></li>
+ <li><a target="docwin" href="#method-i-empty-3F">empty?</a></li>
+ <li><a target="docwin" href="#method-i-front">front</a></li>
+ <li><a target="docwin" href="#method-i-pop_back">pop_back</a></li>
+ <li><a target="docwin" href="#method-i-pop_front">pop_front</a></li>
+ <li><a target="docwin" href="#method-i-push_back">push_back</a></li>
+ <li><a target="docwin" href="#method-i-push_front">push_front</a></li>
+ <li><a target="docwin" href="#method-i-size">size</a></li>
+ </ol>
+ </div>
+ <div id='context'>
+ </div>
+ <div id='section'>
+ <div id='aliases-list'>
+ <h2>Public Instance Aliases</h2>
+ <div class='name-list'>
+ <table summary='Public Instance Aliases'>
+ <tr class='top-aligned-row context-row'>
+ <td class='context-item-name'>each</td>
+ <td>-&gt;</td>
+ <td class='context-item-value'><a target="docwin" href="#method-i-each_forward">each_forward</a></td>
+ </tr>
+ <tr class='top-aligned-row context-row'>
+ <td class='context-item-name'>length</td>
+ <td>-&gt;</td>
+ <td class='context-item-value'><a target="docwin" href="#method-i-size">size</a></td>
+ </tr>
+ <tr class='top-aligned-row context-row'>
+ <td class='context-item-name'>reverse_each</td>
+ <td>-&gt;</td>
+ <td class='context-item-value'><a target="docwin" href="#method-i-each_backward">each_backward</a></td>
+ </tr>
+ </table>
+ </div>
+ </div>
+ <div id='methods'>
+ <h2>Public Class methods</h2>
+ <div class='method public-class' id='method-method-c-new'>
+ <a name='method-c-new'></a>
+ <div class='synopsis'>
+ <span class='name'>new</span>
+ <span class='arguments'>(*args)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-new-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-new-source'>static VALUE deque_init(int argc, VALUE *argv, VALUE self)&#x000A;{&#x000A; long len, i;&#x000A; VALUE ary;&#x000A; &#x000A; if(argc == 0) {&#x000A; return self;&#x000A; }&#x000A; else if(argc &gt; 1) {&#x000A; rb_raise(rb_eArgError, &quot;wrong number of arguments&quot;);&#x000A; }&#x000A; else {&#x000A; ary = rb_check_array_type(argv[0]);&#x000A; if(!NIL_P(ary)) {&#x000A; len = RARRAY_LEN(ary);&#x000A; for (i = 0; i &lt; len; i++) {&#x000A; deque_push_back(self, RARRAY_PTR(ary)[i]);&#x000A; }&#x000A; }&#x000A; }&#x000A; return self;&#x000A;}</pre>
+ </div>
+ </div>
+ <h2>Public Instance methods</h2>
+ <div class='method public-instance' id='method-method-i-back'>
+ <a name='method-i-back'></a>
+ <div class='synopsis'>
+ <span class='name'>back</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-back-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-back-source'>static VALUE deque_back(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; if(deque-&gt;back)&#x000A; return deque-&gt;back-&gt;obj;&#x000A; &#x000A; return Qnil;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-clear'>
+ <a name='method-i-clear'></a>
+ <div class='synopsis'>
+ <span class='name'>clear</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-clear-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-clear-source'>static VALUE deque_clear(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; clear_deque(deque);&#x000A; return Qnil;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-each_backward'>
+ <a name='method-i-each_backward'></a>
+ <div class='synopsis'>
+ <span class='name'>each_backward</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-each_backward-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-each_backward-source'>static VALUE deque_each_backward(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; deque_node *node = deque-&gt;back;&#x000A; while(node) {&#x000A; rb_yield(node-&gt;obj);&#x000A; node = node-&gt;left;&#x000A; }&#x000A; return self;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-each_forward'>
+ <a name='method-i-each_forward'></a>
+ <div class='synopsis'>
+ <span class='name'>each_forward</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-each_forward-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-each_forward-source'>static VALUE deque_each_forward(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; deque_node *node = deque-&gt;front;&#x000A; while(node) {&#x000A; rb_yield(node-&gt;obj);&#x000A; node = node-&gt;right;&#x000A; }&#x000A; return self;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-empty-3F'>
+ <a name='method-i-empty-3F'></a>
+ <div class='synopsis'>
+ <span class='name'>empty?</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-empty-3F-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-empty-3F-source'>static VALUE deque_is_empty(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; return (deque-&gt;size == 0) ? Qtrue : Qfalse;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-front'>
+ <a name='method-i-front'></a>
+ <div class='synopsis'>
+ <span class='name'>front</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-front-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-front-source'>static VALUE deque_front(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; if(deque-&gt;front)&#x000A; return deque-&gt;front-&gt;obj;&#x000A; &#x000A; return Qnil;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-pop_back'>
+ <a name='method-i-pop_back'></a>
+ <div class='synopsis'>
+ <span class='name'>pop_back</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-pop_back-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-pop_back-source'>static VALUE deque_pop_back(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; VALUE obj;&#x000A; if(!deque-&gt;back)&#x000A; return Qnil;&#x000A; deque_node *node = deque-&gt;back;&#x000A; obj = node-&gt;obj;&#x000A; if(deque-&gt;size == 1) {&#x000A; clear_deque(deque);&#x000A; return obj;&#x000A; }&#x000A; deque-&gt;back-&gt;left-&gt;right = NULL;&#x000A; deque-&gt;back = deque-&gt;back-&gt;left;&#x000A; deque-&gt;size--;&#x000A; return obj;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-pop_front'>
+ <a name='method-i-pop_front'></a>
+ <div class='synopsis'>
+ <span class='name'>pop_front</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-pop_front-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-pop_front-source'>static VALUE deque_pop_front(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; VALUE obj;&#x000A; if(!deque-&gt;front)&#x000A; return Qnil;&#x000A; deque_node *node = deque-&gt;front;&#x000A; obj = node-&gt;obj;&#x000A; if(deque-&gt;size == 1) {&#x000A; clear_deque(deque);&#x000A; return obj;&#x000A; }&#x000A; deque-&gt;front-&gt;right-&gt;left = NULL;&#x000A; deque-&gt;front = deque-&gt;front-&gt;right;&#x000A; deque-&gt;size--;&#x000A; return obj;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-push_back'>
+ <a name='method-i-push_back'></a>
+ <div class='synopsis'>
+ <span class='name'>push_back</span>
+ <span class='arguments'>(p1)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-push_back-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-push_back-source'>static VALUE deque_push_back(VALUE self, VALUE obj) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; deque_node *node = create_node(obj);&#x000A; if(deque-&gt;back) {&#x000A; node-&gt;left = deque-&gt;back;&#x000A; deque-&gt;back-&gt;right = node;&#x000A; deque-&gt;back = node; &#x000A; }&#x000A; else {&#x000A; deque-&gt;front = node;&#x000A; deque-&gt;back = node;&#x000A; }&#x000A; deque-&gt;size++;&#x000A; return obj;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-push_front'>
+ <a name='method-i-push_front'></a>
+ <div class='synopsis'>
+ <span class='name'>push_front</span>
+ <span class='arguments'>(p1)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-push_front-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-push_front-source'>static VALUE deque_push_front(VALUE self, VALUE obj) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; deque_node *node = create_node(obj);&#x000A; if(deque-&gt;front) {&#x000A; node-&gt;right = deque-&gt;front;&#x000A; deque-&gt;front-&gt;left = node;&#x000A; deque-&gt;front = node; &#x000A; }&#x000A; else {&#x000A; deque-&gt;front = node;&#x000A; deque-&gt;back = node;&#x000A; }&#x000A; deque-&gt;size++;&#x000A; return obj;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-size'>
+ <a name='method-i-size'></a>
+ <div class='synopsis'>
+ <span class='name'>size</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-size-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-size-source'>static VALUE deque_size(VALUE self) {&#x000A; deque *deque = get_deque_from_self(self);&#x000A; return INT2NUM(deque-&gt;size);&#x000A;}</pre>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ </div>
+ <div id='footer-push'></div>
+ </div>
+ <div id='footer'>
+ <a target="docwin" href="http://github.com/mislav/hanna/tree/master"><strong>Hanna</strong> RDoc template</a>
+ </div>
+ </body>
+</html>
View
308 classes/Containers/CRBTreeMap.html
@@ -0,0 +1,308 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<html lang='en'>
+ <head>
+ <title>Containers::CRBTreeMap</title>
+ <meta content='text/html; charset=UTF-8' http-equiv='Content-Type'>
+ <link href='../../css/style.css' media='screen' rel='stylesheet' type='text/css'>
+ <script type='text/javascript'>
+ //<![CDATA[
+ function popupCode(url) {
+ window.open(url, "Code", "resizable=yes,scrollbars=yes,toolbar=no,status=no,height=150,width=400")
+ }
+
+ function toggleCode(id) {
+ var code = document.getElementById(id)
+
+ code.style.display = code.style.display != 'block' ? 'block' : 'none'
+ return true
+ }
+
+ // Make codeblocks hidden by default
+ document.writeln('<' + 'style type="text/css">.method .source pre { display: none }<\/style>')
+ //]]>
+ </script>
+ </head>
+ <body class='page'>
+ <div class='class' id='wrapper'>
+ <div class='header'>
+ <h1 class='name'>
+ <span class='type'>class</span>
+ Containers::CRBTreeMap
+ </h1>
+ <ol class='paths'>
+ <li>
+ <a target="docwin" href="../../files/ext/containers/bst/bst_c.html">ext/containers/bst/bst.c</a>
+ </li>
+ </ol>
+ <div class='parent'>
+ Parent:
+ <strong><a target="docwin" href="../Containers.html">Containers</a></strong>
+ </div>
+ </div>
+ <div id='content'>
+ <div id='text'>
+ <div id='description'></div>
+ <div id='method-list'>
+ <h2>Methods</h2>
+ <h3>Public Class</h3>
+ <ol>
+ <li><a target="docwin" href="#method-c-new">new</a></li>
+ </ol>
+ <h3>Public Instance</h3>
+ <ol>
+ <li><a target="docwin" href="#method-i-delete">delete</a></li>
+ <li><a target="docwin" href="#method-i-delete_max">delete_max</a></li>
+ <li><a target="docwin" href="#method-i-delete_min">delete_min</a></li>
+ <li><a target="docwin" href="#method-i-each">each</a></li>
+ <li><a target="docwin" href="#method-i-empty-3F">empty?</a></li>
+ <li><a target="docwin" href="#method-i-get">get</a></li>
+ <li><a target="docwin" href="#method-i-has_key-3F">has_key?</a></li>
+ <li><a target="docwin" href="#method-i-height">height</a></li>
+ <li><a target="docwin" href="#method-i-max_key">max_key</a></li>
+ <li><a target="docwin" href="#method-i-min_key">min_key</a></li>
+ <li><a target="docwin" href="#method-i-push">push</a></li>
+ <li><a target="docwin" href="#method-i-size">size</a></li>
+ </ol>
+ </div>
+ <div id='context'>
+ </div>
+ <div id='section'>
+ <div id='aliases-list'>
+ <h2>Public Instance Aliases</h2>
+ <div class='name-list'>
+ <table summary='Public Instance Aliases'>
+ <tr class='top-aligned-row context-row'>
+ <td class='context-item-name'>[]</td>
+ <td>-&gt;</td>
+ <td class='context-item-value'><a target="docwin" href="#method-i-get">get</a></td>
+ </tr>
+ <tr class='top-aligned-row context-row'>
+ <td class='context-item-name'>[]=</td>
+ <td>-&gt;</td>
+ <td class='context-item-value'><a target="docwin" href="#method-i-push">push</a></td>
+ </tr>
+ </table>
+ </div>
+ </div>
+ <div id='methods'>
+ <h2>Public Class methods</h2>
+ <div class='method public-class' id='method-method-c-new'>
+ <a name='method-c-new'></a>
+ <div class='synopsis'>
+ <span class='name'>new</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-c-new-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-c-new-source'>static VALUE rbtree_init(VALUE self)&#x000A;{&#x000A; return self;&#x000A;}</pre>
+ </div>
+ </div>
+ <h2>Public Instance methods</h2>
+ <div class='method public-instance' id='method-method-i-delete'>
+ <a name='method-i-delete'></a>
+ <div class='synopsis'>
+ <span class='name'>delete</span>
+ <span class='arguments'>(p1)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-delete-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-delete-source'>static VALUE rbtree_delete(VALUE self, VALUE key) {&#x000A; VALUE deleted_value;&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; if(!tree-&gt;root)&#x000A; return Qnil;&#x000A; &#x000A; tree-&gt;root = delete(tree, tree-&gt;root, key, &amp;deleted_value);&#x000A; if(tree-&gt;root)&#x000A; tree-&gt;root-&gt;color = BLACK;&#x000A; &#x000A; if(deleted_value) {&#x000A; return deleted_value;&#x000A; }&#x000A; &#x000A; return Qnil;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-delete_max'>
+ <a name='method-i-delete_max'></a>
+ <div class='synopsis'>
+ <span class='name'>delete_max</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-delete_max-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-delete_max-source'>static VALUE rbtree_delete_max(VALUE self) {&#x000A; VALUE deleted_value;&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; if(!tree-&gt;root)&#x000A; return Qnil;&#x000A; &#x000A; tree-&gt;root = delete_max(tree-&gt;root, &amp;deleted_value);&#x000A; if(tree-&gt;root)&#x000A; tree-&gt;root-&gt;color = BLACK;&#x000A; &#x000A; if(deleted_value) {&#x000A; return deleted_value;&#x000A; }&#x000A; &#x000A; return Qnil;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-delete_min'>
+ <a name='method-i-delete_min'></a>
+ <div class='synopsis'>
+ <span class='name'>delete_min</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-delete_min-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-delete_min-source'>static VALUE rbtree_delete_min(VALUE self) {&#x000A; VALUE deleted_value;&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; if(!tree-&gt;root)&#x000A; return Qnil;&#x000A; &#x000A; tree-&gt;root = delete_min(tree-&gt;root, &amp;deleted_value);&#x000A; if(tree-&gt;root)&#x000A; tree-&gt;root-&gt;color = BLACK;&#x000A; &#x000A; if(deleted_value) {&#x000A; return deleted_value;&#x000A; }&#x000A; &#x000A; return Qnil;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-each'>
+ <a name='method-i-each'></a>
+ <div class='synopsis'>
+ <span class='name'>each</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-each-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-each-source'>static VALUE rbtree_each(VALUE self) {&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; rbt_each(tree, &amp;rbtree_each_helper, NULL);&#x000A; return self;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-empty-3F'>
+ <a name='method-i-empty-3F'></a>
+ <div class='synopsis'>
+ <span class='name'>empty?</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-empty-3F-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-empty-3F-source'>static VALUE rbtree_is_empty(VALUE self) {&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; return (tree-&gt;root ? Qfalse : Qtrue);&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-get'>
+ <a name='method-i-get'></a>
+ <div class='synopsis'>
+ <span class='name'>get</span>
+ <span class='arguments'>(p1)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-get-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-get-source'>static VALUE rbtree_get(VALUE self, VALUE key) {&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; return get(tree, tree-&gt;root, key);&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-has_key-3F'>
+ <a name='method-i-has_key-3F'></a>
+ <div class='synopsis'>
+ <span class='name'>has_key?</span>
+ <span class='arguments'>(p1)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-has_key-3F-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-has_key-3F-source'>static VALUE rbtree_has_key(VALUE self, VALUE key) {&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; if(!tree-&gt;root) { return Qfalse; }&#x000A; if(get(tree, tree-&gt;root, key) == Qnil)&#x000A; return Qfalse;&#x000A; &#x000A; return Qtrue;&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-height'>
+ <a name='method-i-height'></a>
+ <div class='synopsis'>
+ <span class='name'>height</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-height-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-height-source'>static VALUE rbtree_height(VALUE self) {&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; return INT2NUM(height(tree-&gt;root));&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-max_key'>
+ <a name='method-i-max_key'></a>
+ <div class='synopsis'>
+ <span class='name'>max_key</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-max_key-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-max_key-source'>static VALUE rbtree_max_key(VALUE self) {&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; if(!tree-&gt;root)&#x000A; return Qnil;&#x000A; &#x000A; return max_key(tree-&gt;root);&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-min_key'>
+ <a name='method-i-min_key'></a>
+ <div class='synopsis'>
+ <span class='name'>min_key</span>
+ <span class='arguments'>()</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick="toggleCode('method-i-min_key-source'); return false">
+ [show source]
+ </a>
+ <pre id='method-i-min_key-source'>static VALUE rbtree_min_key(VALUE self) {&#x000A; rbtree *tree = get_tree_from_self(self);&#x000A; if(!tree-&gt;root)&#x000A; return Qnil;&#x000A; &#x000A; return min_key(tree-&gt;root);&#x000A;}</pre>
+ </div>
+ </div>
+ <div class='method public-instance' id='method-method-i-push'>
+ <a name='method-i-push'></a>
+ <div class='synopsis'>
+ <span class='name'>push</span>
+ <span class='arguments'>(p1, p2)</span>
+ </div>
+ <div class='description'>
+
+ </div>
+ <div class='source'>
+ <a class='source-toggle' href='#' onclick=