1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
2 <html xmlns="http://www.w3.org/1999/xhtml">
4 This file was generated by Devel::NYTProf version 4.06
7 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
8 <meta http-equiv="Content-Language" content="en-us" />
9 <title>Profile of Heap071/Fibonacci.pm</title>
10 <link rel="stylesheet" type="text/css" href="style.css" />
11 <script type="text/javascript" src="js/jquery-min.js"></script>
13 <script type="text/javascript" src="js/jquery-tablesorter-min.js"></script>
14 <link rel="stylesheet" type="text/css" href="js/style-tablesorter.css" />
15 <script type="text/javascript">
16 // when a column is first clicked on to sort it, use descending order
17 // XXX doesn't seem to work (and not just because the tablesorter formatSortingOrder() is broken)
18 $.tablesorter.defaults.sortInitialOrder = "desc";
19 // add parser through the tablesorter addParser method
20 $.tablesorter.addParser({
21 id: 'fmt_time', // name of this parser
23 return false; // return false so this parser is not auto detected
25 format: function(orig) { // format data for normalization
27 val = orig.replace(/ns/,'');
28 if (val != orig) { return val / (1000*1000*1000); }
29 val = orig.replace(/µs/,''); /* XXX use µ ? */
30 if (val != orig) { return val / (1000*1000); }
31 var val = orig.replace(/ms/,'');
32 if (val != orig) { return val / (1000); }
33 var val = orig.replace(/s/,'');
34 if (val != orig) { return val; }
35 if (orig == '0') { return orig; }
36 console.log('no match for fmt_time of '.concat(orig));
39 type: 'numeric' // set type, either numeric or text
45 <div class="header" style="position: relative; overflow-x: hidden; overflow-y: hidden; z-index: 0; ">
46 <div class="header_back">
47 <a href="index.html">← Index</a>
49 <div class="headerForeground" style="float: left">
50 <span class="siteTitle">NYTProf Performance Profile</span>
51 <span class="siteSubtitle">  <span>« <span class="mode_btn"><a href="Heap071-Fibonacci-pm-723-block.html">block view</a></span> • <span class="mode_btn"><a href="Heap071-Fibonacci-pm-723-line.html">line view</a></span> • <span class="mode_btn mode_btn_selected">sub view</span> »</span><br />
55 <div class="headerForeground" style="float: right; text-align: right">
56 <span class="siteTitle"> </span>
57 <span class="siteSubtitle">Run on Thu May 31 16:49:15 2012<br />Reported on Thu May 31 16:50:47 2012</span>
59 <div style="position: absolute; left: 0px; top: 0%; width: 100%; height: 101%; z-index: -1; background-color: rgb(17, 136, 255); "></div>
60 <div style="position: absolute; left: 0px; top: 2%; width: 100%; height: 99%; z-index: -1; background-color: rgb(16, 134, 253); "></div>
61 <div style="position: absolute; left: 0px; top: 4%; width: 100%; height: 97%; z-index: -1; background-color: rgb(16, 133, 252); "></div>
62 <div style="position: absolute; left: 0px; top: 6%; width: 100%; height: 95%; z-index: -1; background-color: rgb(15, 131, 250); "></div>
63 <div style="position: absolute; left: 0px; top: 8%; width: 100%; height: 93%; z-index: -1; background-color: rgb(15, 130, 249); "></div>
64 <div style="position: absolute; left: 0px; top: 10%; width: 100%; height: 91%; z-index: -1; background-color: rgb(15, 129, 248); "></div>
65 <div style="position: absolute; left: 0px; top: 12%; width: 100%; height: 89%; z-index: -1; background-color: rgb(14, 127, 246); "></div>
66 <div style="position: absolute; left: 0px; top: 14%; width: 100%; height: 87%; z-index: -1; background-color: rgb(14, 126, 245); "></div>
67 <div style="position: absolute; left: 0px; top: 16%; width: 100%; height: 85%; z-index: -1; background-color: rgb(14, 125, 244); "></div>
68 <div style="position: absolute; left: 0px; top: 18%; width: 100%; height: 83%; z-index: -1; background-color: rgb(13, 123, 242); "></div>
69 <div style="position: absolute; left: 0px; top: 20%; width: 100%; height: 81%; z-index: -1; background-color: rgb(13, 122, 241); "></div>
70 <div style="position: absolute; left: 0px; top: 22%; width: 100%; height: 79%; z-index: -1; background-color: rgb(13, 121, 240); "></div>
71 <div style="position: absolute; left: 0px; top: 24%; width: 100%; height: 77%; z-index: -1; background-color: rgb(12, 119, 238); "></div>
72 <div style="position: absolute; left: 0px; top: 26%; width: 100%; height: 75%; z-index: -1; background-color: rgb(12, 118, 237); "></div>
73 <div style="position: absolute; left: 0px; top: 28%; width: 100%; height: 73%; z-index: -1; background-color: rgb(12, 116, 235); "></div>
74 <div style="position: absolute; left: 0px; top: 30%; width: 100%; height: 71%; z-index: -1; background-color: rgb(11, 115, 234); "></div>
75 <div style="position: absolute; left: 0px; top: 32%; width: 100%; height: 69%; z-index: -1; background-color: rgb(11, 114, 233); "></div>
76 <div style="position: absolute; left: 0px; top: 34%; width: 100%; height: 67%; z-index: -1; background-color: rgb(11, 112, 231); "></div>
77 <div style="position: absolute; left: 0px; top: 36%; width: 100%; height: 65%; z-index: -1; background-color: rgb(10, 111, 230); "></div>
78 <div style="position: absolute; left: 0px; top: 38%; width: 100%; height: 63%; z-index: -1; background-color: rgb(10, 110, 229); "></div>
79 <div style="position: absolute; left: 0px; top: 40%; width: 100%; height: 61%; z-index: -1; background-color: rgb(10, 108, 227); "></div>
80 <div style="position: absolute; left: 0px; top: 42%; width: 100%; height: 59%; z-index: -1; background-color: rgb(9, 107, 226); "></div>
81 <div style="position: absolute; left: 0px; top: 44%; width: 100%; height: 57%; z-index: -1; background-color: rgb(9, 106, 225); "></div>
82 <div style="position: absolute; left: 0px; top: 46%; width: 100%; height: 55%; z-index: -1; background-color: rgb(9, 104, 223); "></div>
83 <div style="position: absolute; left: 0px; top: 48%; width: 100%; height: 53%; z-index: -1; background-color: rgb(8, 103, 222); "></div>
84 <div style="position: absolute; left: 0px; top: 50%; width: 100%; height: 51%; z-index: -1; background-color: rgb(8, 102, 221); "></div>
85 <div style="position: absolute; left: 0px; top: 52%; width: 100%; height: 49%; z-index: -1; background-color: rgb(8, 100, 219); "></div>
86 <div style="position: absolute; left: 0px; top: 54%; width: 100%; height: 47%; z-index: -1; background-color: rgb(7, 99, 218); "></div>
87 <div style="position: absolute; left: 0px; top: 56%; width: 100%; height: 45%; z-index: -1; background-color: rgb(7, 97, 216); "></div>
88 <div style="position: absolute; left: 0px; top: 58%; width: 100%; height: 43%; z-index: -1; background-color: rgb(7, 96, 215); "></div>
89 <div style="position: absolute; left: 0px; top: 60%; width: 100%; height: 41%; z-index: -1; background-color: rgb(6, 95, 214); "></div>
90 <div style="position: absolute; left: 0px; top: 62%; width: 100%; height: 39%; z-index: -1; background-color: rgb(6, 93, 212); "></div>
91 <div style="position: absolute; left: 0px; top: 64%; width: 100%; height: 37%; z-index: -1; background-color: rgb(6, 92, 211); "></div>
92 <div style="position: absolute; left: 0px; top: 66%; width: 100%; height: 35%; z-index: -1; background-color: rgb(5, 91, 210); "></div>
93 <div style="position: absolute; left: 0px; top: 68%; width: 100%; height: 33%; z-index: -1; background-color: rgb(5, 89, 208); "></div>
94 <div style="position: absolute; left: 0px; top: 70%; width: 100%; height: 31%; z-index: -1; background-color: rgb(5, 88, 207); "></div>
95 <div style="position: absolute; left: 0px; top: 72%; width: 100%; height: 29%; z-index: -1; background-color: rgb(4, 87, 206); "></div>
96 <div style="position: absolute; left: 0px; top: 74%; width: 100%; height: 27%; z-index: -1; background-color: rgb(4, 85, 204); "></div>
97 <div style="position: absolute; left: 0px; top: 76%; width: 100%; height: 25%; z-index: -1; background-color: rgb(4, 84, 203); "></div>
98 <div style="position: absolute; left: 0px; top: 78%; width: 100%; height: 23%; z-index: -1; background-color: rgb(3, 82, 201); "></div>
99 <div style="position: absolute; left: 0px; top: 80%; width: 100%; height: 21%; z-index: -1; background-color: rgb(3, 81, 200); "></div>
100 <div style="position: absolute; left: 0px; top: 82%; width: 100%; height: 19%; z-index: -1; background-color: rgb(3, 80, 199); "></div>
101 <div style="position: absolute; left: 0px; top: 84%; width: 100%; height: 17%; z-index: -1; background-color: rgb(2, 78, 197); "></div>
102 <div style="position: absolute; left: 0px; top: 86%; width: 100%; height: 15%; z-index: -1; background-color: rgb(2, 77, 196); "></div>
103 <div style="position: absolute; left: 0px; top: 88%; width: 100%; height: 13%; z-index: -1; background-color: rgb(2, 76, 195); "></div>
104 <div style="position: absolute; left: 0px; top: 90%; width: 100%; height: 11%; z-index: -1; background-color: rgb(1, 74, 193); "></div>
105 <div style="position: absolute; left: 0px; top: 92%; width: 100%; height: 9%; z-index: -1; background-color: rgb(1, 73, 192); "></div>
106 <div style="position: absolute; left: 0px; top: 94%; width: 100%; height: 7%; z-index: -1; background-color: rgb(1, 72, 191); "></div>
107 <div style="position: absolute; left: 0px; top: 96%; width: 100%; height: 5%; z-index: -1; background-color: rgb(0, 70, 189); "></div>
108 <div style="position: absolute; left: 0px; top: 98%; width: 100%; height: 3%; z-index: -1; background-color: rgb(0, 69, 188); "></div>
109 <div style="position: absolute; left: 0px; top: 100%; width: 100%; height: 1%; z-index: -1; background-color: rgb(0, 68, 187); "></div>
112 <div class="body_content"><br />
113 <table class="file_summary"><tr><td class="h">Filename</td><td align="left"><a href="file:///Users/edenc/perl5/lib/perl5/Heap071/Fibonacci.pm">/Users/edenc/perl5/lib/perl5/Heap071/Fibonacci.pm</a></td></tr>
114 <tr><td class="h">Statements</td><td align="left">Executed 18 statements in 1.46ms</td></tr></table>
116 <table id="subs_table" border="1" cellpadding="0" class="tablesorter">
117 <caption>Subroutines</caption>
121 <th><span title="Number of Places sub is called from">P</span></th>
122 <th><span title="Number of Files sub is called from">F</span></th>
123 <th>Exclusive<br />Time</th>
124 <th>Inclusive<br />Time</th>
129 <tr><td class="c3">1</td><td class="c3">1</td><td class="c3">1</td><td class="c3"><span title="0.0%">13µs</span></td><td class="c3"><span title="0.0%">16µs</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::BEGIN@3</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#3">BEGIN@3</a></span></td></tr>
130 <tr><td class="c3">1</td><td class="c3">1</td><td class="c3">1</td><td class="c3"><span title="0.0%">6µs</span></td><td class="c3"><span title="0.0%">58µs</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::BEGIN@4</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#4">BEGIN@4</a></span></td></tr>
131 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::DESTROY</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#152">DESTROY</a></span></td></tr>
132 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::absorb</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#233">absorb</a></span></td></tr>
133 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::add</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#158">add</a></span></td></tr>
134 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::ascending_cut</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#413">ascending_cut</a></span></td></tr>
135 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::bhcheck</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#98">bhcheck</a></span></td></tr>
136 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::consolidate</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#371">consolidate</a></span></td></tr>
137 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::debug</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#31">debug</a></span></td></tr>
138 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::decrease_key</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#267">decrease_key</a></span></td></tr>
139 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::delete</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#291">delete</a></span></td></tr>
140 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::elem</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#310">elem</a></span></td></tr>
141 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::elem_DESTROY</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#327">elem_DESTROY</a></span></td></tr>
142 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::extract_top</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#185">extract_top</a></span></td></tr>
143 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::hdump</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#57">hdump</a></span></td></tr>
144 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::heapcheck</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#121">heapcheck</a></span></td></tr>
145 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::heapdump</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#81">heapdump</a></span></td></tr>
146 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::link_as_parent_of</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#352">link_as_parent_of</a></span></td></tr>
147 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::link_to_left_of</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#344">link_to_left_of</a></span></td></tr>
148 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::new</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#145">new</a></span></td></tr>
149 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::set_width</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#45">set_width</a></span></td></tr>
150 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::top</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#178">top</a></span></td></tr>
151 <tr><td class="c3">0</td><td class="c3">0</td><td class="c3">0</td><td class="c3"><span title="0.0%">0s</span></td><td class="c3"><span title="0.0%">0s</span></td><td class="sub_name"><span style="display: none;">Heap071::Fibonacci::::validate</span>Heap071::Fibonacci::<a href="Heap071-Fibonacci-pm-723-sub.html#36">validate</a></span></td></tr>
153 Call graph for these subroutines as a
154 <a href="http://en.wikipedia.org/wiki/Graphviz">Graphviz</a>
155 <a href="Users-edenc-perl5-lib-perl5-Heap071-Fibonacci-pm.dot">dot language file</a>.
157 <table border="1" cellpadding="0">
160 <th><span title="Number of statements executed">State<br />ments</span></th>
161 <th><span title="Time spend executing statements on the line,
162 excluding time spent executing statements in any called subroutines">Time<br />on line</span></th>
163 <th><span title="Number of subroutines calls">Calls</span></th>
164 <th><span title="Time spent in subroutines called (inclusive)">Time<br />in subs</span></th>
165 <th class="left_indent_header">Code</th>
170 <tr><td class="h"><a name="1"></a>1</td><td></td><td></td><td></td><td></td><td class="s">package Heap071::Fibonacci;</td></tr>
171 <tr><td class="h"><a name="2"></a>2</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
172 <tr><td class="h"><a name="3"></a>3</td><td class="c1">2</td><td class="c0"><span title="Avg 12µs">25µs</span></td><td class="c3">2</td><td class="c3">19µs</td><td class="s"><div class="calls"><div class="calls_in"># spent 16µs (13+3) within Heap071::Fibonacci::BEGIN@3 which was called:
173 # once (13µs+3µs) by Graph::BEGIN@38 at <a href="Heap071-Fibonacci-pm-723-sub.html#3">line 3</a></div></div>use strict;<div class="calls"><div class="calls_out"># spent 16µs making 1 call to <a href="Heap071-Fibonacci-pm-723-sub.html#3">Heap071::Fibonacci::BEGIN@3</a>
174 # spent 3µs making 1 call to <a href="strict-pm-3-sub.html#34">strict::import</a></div></div></td></tr>
175 <tr><td class="h"><a name="4"></a>4</td><td class="c1">2</td><td class="c0"><span title="Avg 706µs">1.41ms</span></td><td class="c3">2</td><td class="c3">110µs</td><td class="s"><div class="calls"><div class="calls_in"># spent 58µs (6+52) within Heap071::Fibonacci::BEGIN@4 which was called:
176 # once (6µs+52µs) by Graph::BEGIN@38 at <a href="Heap071-Fibonacci-pm-723-sub.html#4">line 4</a></div></div>use vars qw($VERSION @ISA @EXPORT @EXPORT_OK);<div class="calls"><div class="calls_out"># spent 58µs making 1 call to <a href="Heap071-Fibonacci-pm-723-sub.html#4">Heap071::Fibonacci::BEGIN@4</a>
177 # spent 52µs making 1 call to <a href="vars-pm-6-sub.html#10">vars::import</a></div></div></td></tr>
178 <tr><td class="h"><a name="5"></a>5</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
179 <tr><td class="h"><a name="6"></a>6</td><td class="c3">1</td><td class="c0"><span title="Avg 400ns">400ns</span></td><td></td><td></td><td class="s">require Exporter;</td></tr>
180 <tr><td class="h"><a name="7"></a>7</td><td class="c3">1</td><td class="c3"><span title="Avg 200ns">200ns</span></td><td></td><td></td><td class="s">require AutoLoader;</td></tr>
181 <tr><td class="h"><a name="8"></a>8</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
182 <tr><td class="h"><a name="9"></a>9</td><td class="c3">1</td><td class="c0"><span title="Avg 7µs">7µs</span></td><td></td><td></td><td class="s">@ISA = qw(Exporter AutoLoader);</td></tr>
183 <tr><td class="h"><a name="10"></a>10</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
184 <tr><td class="h"><a name="11"></a>11</td><td></td><td></td><td></td><td></td><td class="s"># No names exported.</td></tr>
185 <tr><td class="h"><a name="12"></a>12</td><td></td><td></td><td></td><td></td><td class="s"># No names available for export.</td></tr>
186 <tr><td class="h"><a name="13"></a>13</td><td class="c3">1</td><td class="c3"><span title="Avg 200ns">200ns</span></td><td></td><td></td><td class="s">@EXPORT = ( );</td></tr>
187 <tr><td class="h"><a name="14"></a>14</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
188 <tr><td class="h"><a name="15"></a>15</td><td class="c3">1</td><td class="c1"><span title="Avg 300ns">300ns</span></td><td></td><td></td><td class="s">$VERSION = '0.71';</td></tr>
189 <tr><td class="h"><a name="16"></a>16</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
190 <tr><td class="h"><a name="17"></a>17</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
191 <tr><td class="h"><a name="18"></a>18</td><td></td><td></td><td></td><td></td><td class="s"># Preloaded methods go here.</td></tr>
192 <tr><td class="h"><a name="19"></a>19</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
193 <tr><td class="h"><a name="20"></a>20</td><td></td><td></td><td></td><td></td><td class="s"># common names</td></tr>
194 <tr><td class="h"><a name="21"></a>21</td><td></td><td></td><td></td><td></td><td class="s"># h - heap head</td></tr>
195 <tr><td class="h"><a name="22"></a>22</td><td></td><td></td><td></td><td></td><td class="s"># el - linkable element, contains user-provided value</td></tr>
196 <tr><td class="h"><a name="23"></a>23</td><td></td><td></td><td></td><td></td><td class="s"># v - user-provided value</td></tr>
197 <tr><td class="h"><a name="24"></a>24</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
198 <tr><td class="h"><a name="25"></a>25</td><td></td><td></td><td></td><td></td><td class="s">################################################# debugging control</td></tr>
199 <tr><td class="h"><a name="26"></a>26</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
200 <tr><td class="h"><a name="27"></a>27</td><td class="c3">1</td><td class="c3"><span title="Avg 200ns">200ns</span></td><td></td><td></td><td class="s">my $debug = 0;</td></tr>
201 <tr><td class="h"><a name="28"></a>28</td><td class="c3">1</td><td class="c3"><span title="Avg 100ns">100ns</span></td><td></td><td></td><td class="s">my $validate = 0;</td></tr>
202 <tr><td class="h"><a name="29"></a>29</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
203 <tr><td class="h"><a name="30"></a>30</td><td></td><td></td><td></td><td></td><td class="s"># enable/disable debugging output</td></tr>
204 <tr><td class="h"><a name="31"></a>31</td><td></td><td></td><td></td><td></td><td class="s">sub debug {</td></tr>
205 <tr><td class="h"><a name="32"></a>32</td><td></td><td></td><td></td><td></td><td class="s"> @_ ? ($debug = shift) : $debug;</td></tr>
206 <tr><td class="h"><a name="33"></a>33</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
207 <tr><td class="h"><a name="34"></a>34</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
208 <tr><td class="h"><a name="35"></a>35</td><td></td><td></td><td></td><td></td><td class="s"># enable/disable validation checks on values</td></tr>
209 <tr><td class="h"><a name="36"></a>36</td><td></td><td></td><td></td><td></td><td class="s">sub validate {</td></tr>
210 <tr><td class="h"><a name="37"></a>37</td><td></td><td></td><td></td><td></td><td class="s"> @_ ? ($validate = shift) : $validate;</td></tr>
211 <tr><td class="h"><a name="38"></a>38</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
212 <tr><td class="h"><a name="39"></a>39</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
213 <tr><td class="h"><a name="40"></a>40</td><td class="c3">1</td><td class="c3"><span title="Avg 100ns">100ns</span></td><td></td><td></td><td class="s">my $width = 3;</td></tr>
214 <tr><td class="h"><a name="41"></a>41</td><td class="c3">1</td><td class="c3"><span title="Avg 200ns">200ns</span></td><td></td><td></td><td class="s">my $bar = ' | ';</td></tr>
215 <tr><td class="h"><a name="42"></a>42</td><td class="c3">1</td><td class="c3"><span title="Avg 100ns">100ns</span></td><td></td><td></td><td class="s">my $corner = ' +-';</td></tr>
216 <tr><td class="h"><a name="43"></a>43</td><td class="c3">1</td><td class="c3"><span title="Avg 200ns">200ns</span></td><td></td><td></td><td class="s">my $vfmt = "%3d";</td></tr>
217 <tr><td class="h"><a name="44"></a>44</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
218 <tr><td class="h"><a name="45"></a>45</td><td></td><td></td><td></td><td></td><td class="s">sub set_width {</td></tr>
219 <tr><td class="h"><a name="46"></a>46</td><td></td><td></td><td></td><td></td><td class="s"> $width = shift;</td></tr>
220 <tr><td class="h"><a name="47"></a>47</td><td></td><td></td><td></td><td></td><td class="s"> $width = 2 if $width < 2;</td></tr>
221 <tr><td class="h"><a name="48"></a>48</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
222 <tr><td class="h"><a name="49"></a>49</td><td></td><td></td><td></td><td></td><td class="s"> $vfmt = "%${width}d";</td></tr>
223 <tr><td class="h"><a name="50"></a>50</td><td></td><td></td><td></td><td></td><td class="s"> $bar = $corner = ' ' x $width;</td></tr>
224 <tr><td class="h"><a name="51"></a>51</td><td></td><td></td><td></td><td></td><td class="s"> substr($bar,-2,1) = '|';</td></tr>
225 <tr><td class="h"><a name="52"></a>52</td><td></td><td></td><td></td><td></td><td class="s"> substr($corner,-2,2) = '+-';</td></tr>
226 <tr><td class="h"><a name="53"></a>53</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
227 <tr><td class="h"><a name="54"></a>54</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
228 <tr><td class="h"><a name="55"></a>55</td><td></td><td></td><td></td><td></td><td class="s">sub hdump;</td></tr>
229 <tr><td class="h"><a name="56"></a>56</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
230 <tr><td class="h"><a name="57"></a>57</td><td></td><td></td><td></td><td></td><td class="s">sub hdump {</td></tr>
231 <tr><td class="h"><a name="58"></a>58</td><td></td><td></td><td></td><td></td><td class="s"> my $el = shift;</td></tr>
232 <tr><td class="h"><a name="59"></a>59</td><td></td><td></td><td></td><td></td><td class="s"> my $l1 = shift;</td></tr>
233 <tr><td class="h"><a name="60"></a>60</td><td></td><td></td><td></td><td></td><td class="s"> my $b = shift;</td></tr>
234 <tr><td class="h"><a name="61"></a>61</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
235 <tr><td class="h"><a name="62"></a>62</td><td></td><td></td><td></td><td></td><td class="s"> my $ch;</td></tr>
236 <tr><td class="h"><a name="63"></a>63</td><td></td><td></td><td></td><td></td><td class="s"> my $ch1;</td></tr>
237 <tr><td class="h"><a name="64"></a>64</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
238 <tr><td class="h"><a name="65"></a>65</td><td></td><td></td><td></td><td></td><td class="s"> unless( $el ) {</td></tr>
239 <tr><td class="h"><a name="66"></a>66</td><td></td><td></td><td></td><td></td><td class="s"> print $l1, "\n";</td></tr>
240 <tr><td class="h"><a name="67"></a>67</td><td></td><td></td><td></td><td></td><td class="s"> return;</td></tr>
241 <tr><td class="h"><a name="68"></a>68</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
242 <tr><td class="h"><a name="69"></a>69</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
243 <tr><td class="h"><a name="70"></a>70</td><td></td><td></td><td></td><td></td><td class="s"> hdump $ch1 = $el->{child},</td></tr>
244 <tr><td class="h"><a name="71"></a>71</td><td></td><td></td><td></td><td></td><td class="s"> $l1 . sprintf( $vfmt, $el->{val}->val),</td></tr>
245 <tr><td class="h"><a name="72"></a>72</td><td></td><td></td><td></td><td></td><td class="s"> $b . $bar;</td></tr>
246 <tr><td class="h"><a name="73"></a>73</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
247 <tr><td class="h"><a name="74"></a>74</td><td></td><td></td><td></td><td></td><td class="s"> if( $ch1 ) {</td></tr>
248 <tr><td class="h"><a name="75"></a>75</td><td></td><td></td><td></td><td></td><td class="s"> for( $ch = $ch1->{right}; $ch != $ch1; $ch = $ch->{right} ) {</td></tr>
249 <tr><td class="h"><a name="76"></a>76</td><td></td><td></td><td></td><td></td><td class="s"> hdump $ch, $b . $corner, $b . $bar;</td></tr>
250 <tr><td class="h"><a name="77"></a>77</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
251 <tr><td class="h"><a name="78"></a>78</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
252 <tr><td class="h"><a name="79"></a>79</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
253 <tr><td class="h"><a name="80"></a>80</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
254 <tr><td class="h"><a name="81"></a>81</td><td></td><td></td><td></td><td></td><td class="s">sub heapdump {</td></tr>
255 <tr><td class="h"><a name="82"></a>82</td><td></td><td></td><td></td><td></td><td class="s"> my $h;</td></tr>
256 <tr><td class="h"><a name="83"></a>83</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
257 <tr><td class="h"><a name="84"></a>84</td><td></td><td></td><td></td><td></td><td class="s"> while( $h = shift ) {</td></tr>
258 <tr><td class="h"><a name="85"></a>85</td><td></td><td></td><td></td><td></td><td class="s"> my $top = $$h or last;</td></tr>
259 <tr><td class="h"><a name="86"></a>86</td><td></td><td></td><td></td><td></td><td class="s"> my $el = $top;</td></tr>
260 <tr><td class="h"><a name="87"></a>87</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
261 <tr><td class="h"><a name="88"></a>88</td><td></td><td></td><td></td><td></td><td class="s"> do {</td></tr>
262 <tr><td class="h"><a name="89"></a>89</td><td></td><td></td><td></td><td></td><td class="s"> hdump $el, sprintf( "%02d: ", $el->{degree}), ' ';</td></tr>
263 <tr><td class="h"><a name="90"></a>90</td><td></td><td></td><td></td><td></td><td class="s"> $el = $el->{right};</td></tr>
264 <tr><td class="h"><a name="91"></a>91</td><td></td><td></td><td></td><td></td><td class="s"> } until $el == $top;</td></tr>
265 <tr><td class="h"><a name="92"></a>92</td><td></td><td></td><td></td><td></td><td class="s"> print "\n";</td></tr>
266 <tr><td class="h"><a name="93"></a>93</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
267 <tr><td class="h"><a name="94"></a>94</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
268 <tr><td class="h"><a name="95"></a>95</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
269 <tr><td class="h"><a name="96"></a>96</td><td></td><td></td><td></td><td></td><td class="s">sub bhcheck;</td></tr>
270 <tr><td class="h"><a name="97"></a>97</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
271 <tr><td class="h"><a name="98"></a>98</td><td></td><td></td><td></td><td></td><td class="s">sub bhcheck {</td></tr>
272 <tr><td class="h"><a name="99"></a>99</td><td></td><td></td><td></td><td></td><td class="s"> my $el = shift;</td></tr>
273 <tr><td class="h"><a name="100"></a>100</td><td></td><td></td><td></td><td></td><td class="s"> my $p = shift;</td></tr>
274 <tr><td class="h"><a name="101"></a>101</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
275 <tr><td class="h"><a name="102"></a>102</td><td></td><td></td><td></td><td></td><td class="s"> my $cur = $el;</td></tr>
276 <tr><td class="h"><a name="103"></a>103</td><td></td><td></td><td></td><td></td><td class="s"> my $prev;</td></tr>
277 <tr><td class="h"><a name="104"></a>104</td><td></td><td></td><td></td><td></td><td class="s"> my $ch;</td></tr>
278 <tr><td class="h"><a name="105"></a>105</td><td></td><td></td><td></td><td></td><td class="s"> do {</td></tr>
279 <tr><td class="h"><a name="106"></a>106</td><td></td><td></td><td></td><td></td><td class="s"> $prev = $cur;</td></tr>
280 <tr><td class="h"><a name="107"></a>107</td><td></td><td></td><td></td><td></td><td class="s"> $cur = $cur->{right};</td></tr>
281 <tr><td class="h"><a name="108"></a>108</td><td></td><td></td><td></td><td></td><td class="s"> die "bad back link" unless $cur->{left} == $prev;</td></tr>
282 <tr><td class="h"><a name="109"></a>109</td><td></td><td></td><td></td><td></td><td class="s"> die "bad parent link"</td></tr>
283 <tr><td class="h"><a name="110"></a>110</td><td></td><td></td><td></td><td></td><td class="s"> unless (defined $p && defined $cur->{p} && $cur->{p} == $p)</td></tr>
284 <tr><td class="h"><a name="111"></a>111</td><td></td><td></td><td></td><td></td><td class="s"> || (!defined $p && !defined $cur->{p});</td></tr>
285 <tr><td class="h"><a name="112"></a>112</td><td></td><td></td><td></td><td></td><td class="s"> die "bad degree( $cur->{degree} > $p->{degree} )"</td></tr>
286 <tr><td class="h"><a name="113"></a>113</td><td></td><td></td><td></td><td></td><td class="s"> if $p && $p->{degree} <= $cur->{degree};</td></tr>
287 <tr><td class="h"><a name="114"></a>114</td><td></td><td></td><td></td><td></td><td class="s"> die "not heap ordered"</td></tr>
288 <tr><td class="h"><a name="115"></a>115</td><td></td><td></td><td></td><td></td><td class="s"> if $p && $p->{val}->cmp($cur->{val}) > 0;</td></tr>
289 <tr><td class="h"><a name="116"></a>116</td><td></td><td></td><td></td><td></td><td class="s"> $ch = $cur->{child} and bhcheck $ch, $cur;</td></tr>
290 <tr><td class="h"><a name="117"></a>117</td><td></td><td></td><td></td><td></td><td class="s"> } until $cur == $el;</td></tr>
291 <tr><td class="h"><a name="118"></a>118</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
292 <tr><td class="h"><a name="119"></a>119</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
293 <tr><td class="h"><a name="120"></a>120</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
294 <tr><td class="h"><a name="121"></a>121</td><td></td><td></td><td></td><td></td><td class="s">sub heapcheck {</td></tr>
295 <tr><td class="h"><a name="122"></a>122</td><td></td><td></td><td></td><td></td><td class="s"> my $h;</td></tr>
296 <tr><td class="h"><a name="123"></a>123</td><td></td><td></td><td></td><td></td><td class="s"> my $el;</td></tr>
297 <tr><td class="h"><a name="124"></a>124</td><td></td><td></td><td></td><td></td><td class="s"> while( $h = shift ) {</td></tr>
298 <tr><td class="h"><a name="125"></a>125</td><td></td><td></td><td></td><td></td><td class="s"> heapdump $h if $validate >= 2;</td></tr>
299 <tr><td class="h"><a name="126"></a>126</td><td></td><td></td><td></td><td></td><td class="s"> $el = $$h and bhcheck $el, undef;</td></tr>
300 <tr><td class="h"><a name="127"></a>127</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
301 <tr><td class="h"><a name="128"></a>128</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
302 <tr><td class="h"><a name="129"></a>129</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
303 <tr><td class="h"><a name="130"></a>130</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
304 <tr><td class="h"><a name="131"></a>131</td><td></td><td></td><td></td><td></td><td class="s">################################################# forward declarations</td></tr>
305 <tr><td class="h"><a name="132"></a>132</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
306 <tr><td class="h"><a name="133"></a>133</td><td></td><td></td><td></td><td></td><td class="s">sub ascending_cut;</td></tr>
307 <tr><td class="h"><a name="134"></a>134</td><td></td><td></td><td></td><td></td><td class="s">sub elem;</td></tr>
308 <tr><td class="h"><a name="135"></a>135</td><td></td><td></td><td></td><td></td><td class="s">sub elem_DESTROY;</td></tr>
309 <tr><td class="h"><a name="136"></a>136</td><td></td><td></td><td></td><td></td><td class="s">sub link_to_left_of;</td></tr>
310 <tr><td class="h"><a name="137"></a>137</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
311 <tr><td class="h"><a name="138"></a>138</td><td></td><td></td><td></td><td></td><td class="s">################################################# heap methods</td></tr>
312 <tr><td class="h"><a name="139"></a>139</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
313 <tr><td class="h"><a name="140"></a>140</td><td></td><td></td><td></td><td></td><td class="s"># Cormen et al. use two values for the heap, a pointer to an element in the</td></tr>
314 <tr><td class="h"><a name="141"></a>141</td><td></td><td></td><td></td><td></td><td class="s"># list at the top, and a count of the number of elements. The count is only</td></tr>
315 <tr><td class="h"><a name="142"></a>142</td><td></td><td></td><td></td><td></td><td class="s"># used to determine the size of array required to hold log(count) pointers,</td></tr>
316 <tr><td class="h"><a name="143"></a>143</td><td></td><td></td><td></td><td></td><td class="s"># but perl can set array sizes as needed and doesn't need to know their size</td></tr>
317 <tr><td class="h"><a name="144"></a>144</td><td></td><td></td><td></td><td></td><td class="s"># when they are created, so we're not maintaining that field.</td></tr>
318 <tr><td class="h"><a name="145"></a>145</td><td></td><td></td><td></td><td></td><td class="s">sub new {</td></tr>
319 <tr><td class="h"><a name="146"></a>146</td><td></td><td></td><td></td><td></td><td class="s"> my $self = shift;</td></tr>
320 <tr><td class="h"><a name="147"></a>147</td><td></td><td></td><td></td><td></td><td class="s"> my $class = ref($self) || $self;</td></tr>
321 <tr><td class="h"><a name="148"></a>148</td><td></td><td></td><td></td><td></td><td class="s"> my $h = undef;</td></tr>
322 <tr><td class="h"><a name="149"></a>149</td><td></td><td></td><td></td><td></td><td class="s"> bless \$h, $class;</td></tr>
323 <tr><td class="h"><a name="150"></a>150</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
324 <tr><td class="h"><a name="151"></a>151</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
325 <tr><td class="h"><a name="152"></a>152</td><td></td><td></td><td></td><td></td><td class="s">sub DESTROY {</td></tr>
326 <tr><td class="h"><a name="153"></a>153</td><td></td><td></td><td></td><td></td><td class="s"> my $h = shift;</td></tr>
327 <tr><td class="h"><a name="154"></a>154</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
328 <tr><td class="h"><a name="155"></a>155</td><td></td><td></td><td></td><td></td><td class="s"> elem_DESTROY $$h;</td></tr>
329 <tr><td class="h"><a name="156"></a>156</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
330 <tr><td class="h"><a name="157"></a>157</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
331 <tr><td class="h"><a name="158"></a>158</td><td></td><td></td><td></td><td></td><td class="s">sub add {</td></tr>
332 <tr><td class="h"><a name="159"></a>159</td><td></td><td></td><td></td><td></td><td class="s"> my $h = shift;</td></tr>
333 <tr><td class="h"><a name="160"></a>160</td><td></td><td></td><td></td><td></td><td class="s"> my $v = shift;</td></tr>
334 <tr><td class="h"><a name="161"></a>161</td><td></td><td></td><td></td><td></td><td class="s"> $validate && do {</td></tr>
335 <tr><td class="h"><a name="162"></a>162</td><td></td><td></td><td></td><td></td><td class="s"> die "Method 'heap' required for element on heap"</td></tr>
336 <tr><td class="h"><a name="163"></a>163</td><td></td><td></td><td></td><td></td><td class="s"> unless $v->can('heap');</td></tr>
337 <tr><td class="h"><a name="164"></a>164</td><td></td><td></td><td></td><td></td><td class="s"> die "Method 'cmp' required for element on heap"</td></tr>
338 <tr><td class="h"><a name="165"></a>165</td><td></td><td></td><td></td><td></td><td class="s"> unless $v->can('cmp');</td></tr>
339 <tr><td class="h"><a name="166"></a>166</td><td></td><td></td><td></td><td></td><td class="s"> };</td></tr>
340 <tr><td class="h"><a name="167"></a>167</td><td></td><td></td><td></td><td></td><td class="s"> my $el = elem $v;</td></tr>
341 <tr><td class="h"><a name="168"></a>168</td><td></td><td></td><td></td><td></td><td class="s"> my $top;</td></tr>
342 <tr><td class="h"><a name="169"></a>169</td><td></td><td></td><td></td><td></td><td class="s"> if( !($top = $$h) ) {</td></tr>
343 <tr><td class="h"><a name="170"></a>170</td><td></td><td></td><td></td><td></td><td class="s"> $$h = $el;</td></tr>
344 <tr><td class="h"><a name="171"></a>171</td><td></td><td></td><td></td><td></td><td class="s"> } else {</td></tr>
345 <tr><td class="h"><a name="172"></a>172</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $top->{left}, $el ;</td></tr>
346 <tr><td class="h"><a name="173"></a>173</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $el,$top;</td></tr>
347 <tr><td class="h"><a name="174"></a>174</td><td></td><td></td><td></td><td></td><td class="s"> $$h = $el if $v->cmp($top->{val}) < 0;</td></tr>
348 <tr><td class="h"><a name="175"></a>175</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
349 <tr><td class="h"><a name="176"></a>176</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
350 <tr><td class="h"><a name="177"></a>177</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
351 <tr><td class="h"><a name="178"></a>178</td><td></td><td></td><td></td><td></td><td class="s">sub top {</td></tr>
352 <tr><td class="h"><a name="179"></a>179</td><td></td><td></td><td></td><td></td><td class="s"> my $h = shift;</td></tr>
353 <tr><td class="h"><a name="180"></a>180</td><td></td><td></td><td></td><td></td><td class="s"> $$h && $$h->{val};</td></tr>
354 <tr><td class="h"><a name="181"></a>181</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
355 <tr><td class="h"><a name="182"></a>182</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
356 <tr><td class="h"><a name="183"></a>183</td><td class="c3">1</td><td class="c0"><span title="Avg 1µs">1µs</span></td><td></td><td></td><td class="s">*minimum = \&top;</td></tr>
357 <tr><td class="h"><a name="184"></a>184</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
358 <tr><td class="h"><a name="185"></a>185</td><td></td><td></td><td></td><td></td><td class="s">sub extract_top {</td></tr>
359 <tr><td class="h"><a name="186"></a>186</td><td></td><td></td><td></td><td></td><td class="s"> my $h = shift;</td></tr>
360 <tr><td class="h"><a name="187"></a>187</td><td></td><td></td><td></td><td></td><td class="s"> my $el = $$h or return undef;</td></tr>
361 <tr><td class="h"><a name="188"></a>188</td><td></td><td></td><td></td><td></td><td class="s"> my $ltop = $el->{left};</td></tr>
362 <tr><td class="h"><a name="189"></a>189</td><td></td><td></td><td></td><td></td><td class="s"> my $cur;</td></tr>
363 <tr><td class="h"><a name="190"></a>190</td><td></td><td></td><td></td><td></td><td class="s"> my $next;</td></tr>
364 <tr><td class="h"><a name="191"></a>191</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
365 <tr><td class="h"><a name="192"></a>192</td><td></td><td></td><td></td><td></td><td class="s"> # $el is the heap with the lowest value on it</td></tr>
366 <tr><td class="h"><a name="193"></a>193</td><td></td><td></td><td></td><td></td><td class="s"> # move all of $el's children (if any) to the top list (between</td></tr>
367 <tr><td class="h"><a name="194"></a>194</td><td></td><td></td><td></td><td></td><td class="s"> # $ltop and $el)</td></tr>
368 <tr><td class="h"><a name="195"></a>195</td><td></td><td></td><td></td><td></td><td class="s"> if( $cur = $el->{child} ) {</td></tr>
369 <tr><td class="h"><a name="196"></a>196</td><td></td><td></td><td></td><td></td><td class="s"> # remember the beginning of the list of children</td></tr>
370 <tr><td class="h"><a name="197"></a>197</td><td></td><td></td><td></td><td></td><td class="s"> my $first = $cur;</td></tr>
371 <tr><td class="h"><a name="198"></a>198</td><td></td><td></td><td></td><td></td><td class="s"> do {</td></tr>
372 <tr><td class="h"><a name="199"></a>199</td><td></td><td></td><td></td><td></td><td class="s"> # the children are moving to the top, clear the p</td></tr>
373 <tr><td class="h"><a name="200"></a>200</td><td></td><td></td><td></td><td></td><td class="s"> # pointer for all of them</td></tr>
374 <tr><td class="h"><a name="201"></a>201</td><td></td><td></td><td></td><td></td><td class="s"> $cur->{p} = undef;</td></tr>
375 <tr><td class="h"><a name="202"></a>202</td><td></td><td></td><td></td><td></td><td class="s"> } until ($cur = $cur->{right}) == $first;</td></tr>
376 <tr><td class="h"><a name="203"></a>203</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
377 <tr><td class="h"><a name="204"></a>204</td><td></td><td></td><td></td><td></td><td class="s"> # remember the end of the list</td></tr>
378 <tr><td class="h"><a name="205"></a>205</td><td></td><td></td><td></td><td></td><td class="s"> $cur = $cur->{left};</td></tr>
379 <tr><td class="h"><a name="206"></a>206</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $ltop, $first;</td></tr>
380 <tr><td class="h"><a name="207"></a>207</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $cur, $el;</td></tr>
381 <tr><td class="h"><a name="208"></a>208</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
382 <tr><td class="h"><a name="209"></a>209</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
383 <tr><td class="h"><a name="210"></a>210</td><td></td><td></td><td></td><td></td><td class="s"> if( $el->{right} == $el ) {</td></tr>
384 <tr><td class="h"><a name="211"></a>211</td><td></td><td></td><td></td><td></td><td class="s"> # $el had no siblings or children, the top only contains $el</td></tr>
385 <tr><td class="h"><a name="212"></a>212</td><td></td><td></td><td></td><td></td><td class="s"> # and $el is being removed</td></tr>
386 <tr><td class="h"><a name="213"></a>213</td><td></td><td></td><td></td><td></td><td class="s"> $$h = undef;</td></tr>
387 <tr><td class="h"><a name="214"></a>214</td><td></td><td></td><td></td><td></td><td class="s"> } else {</td></tr>
388 <tr><td class="h"><a name="215"></a>215</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $el->{left}, $$h = $el->{right};</td></tr>
389 <tr><td class="h"><a name="216"></a>216</td><td></td><td></td><td></td><td></td><td class="s"> # now all those loose ends have to be merged together as we</td></tr>
390 <tr><td class="h"><a name="217"></a>217</td><td></td><td></td><td></td><td></td><td class="s"> # search for the</td></tr>
391 <tr><td class="h"><a name="218"></a>218</td><td></td><td></td><td></td><td></td><td class="s"> # new smallest element</td></tr>
392 <tr><td class="h"><a name="219"></a>219</td><td></td><td></td><td></td><td></td><td class="s"> $h->consolidate;</td></tr>
393 <tr><td class="h"><a name="220"></a>220</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
394 <tr><td class="h"><a name="221"></a>221</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
395 <tr><td class="h"><a name="222"></a>222</td><td></td><td></td><td></td><td></td><td class="s"> # extract the actual value and return that, $el is no longer used</td></tr>
396 <tr><td class="h"><a name="223"></a>223</td><td></td><td></td><td></td><td></td><td class="s"> # but break all of its links so that it won't be pointed to...</td></tr>
397 <tr><td class="h"><a name="224"></a>224</td><td></td><td></td><td></td><td></td><td class="s"> my $top = $el->{val};</td></tr>
398 <tr><td class="h"><a name="225"></a>225</td><td></td><td></td><td></td><td></td><td class="s"> $top->heap(undef);</td></tr>
399 <tr><td class="h"><a name="226"></a>226</td><td></td><td></td><td></td><td></td><td class="s"> $el->{left} = $el->{right} = $el->{p} = $el->{child} = $el->{val} =</td></tr>
400 <tr><td class="h"><a name="227"></a>227</td><td></td><td></td><td></td><td></td><td class="s"> undef;</td></tr>
401 <tr><td class="h"><a name="228"></a>228</td><td></td><td></td><td></td><td></td><td class="s"> $top;</td></tr>
402 <tr><td class="h"><a name="229"></a>229</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
403 <tr><td class="h"><a name="230"></a>230</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
404 <tr><td class="h"><a name="231"></a>231</td><td class="c3">1</td><td class="c3"><span title="Avg 200ns">200ns</span></td><td></td><td></td><td class="s">*extract_minimum = \&extract_top;</td></tr>
405 <tr><td class="h"><a name="232"></a>232</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
406 <tr><td class="h"><a name="233"></a>233</td><td></td><td></td><td></td><td></td><td class="s">sub absorb {</td></tr>
407 <tr><td class="h"><a name="234"></a>234</td><td></td><td></td><td></td><td></td><td class="s"> my $h = shift;</td></tr>
408 <tr><td class="h"><a name="235"></a>235</td><td></td><td></td><td></td><td></td><td class="s"> my $h2 = shift;</td></tr>
409 <tr><td class="h"><a name="236"></a>236</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
410 <tr><td class="h"><a name="237"></a>237</td><td></td><td></td><td></td><td></td><td class="s"> my $el = $$h;</td></tr>
411 <tr><td class="h"><a name="238"></a>238</td><td></td><td></td><td></td><td></td><td class="s"> unless( $el ) {</td></tr>
412 <tr><td class="h"><a name="239"></a>239</td><td></td><td></td><td></td><td></td><td class="s"> $$h = $$h2;</td></tr>
413 <tr><td class="h"><a name="240"></a>240</td><td></td><td></td><td></td><td></td><td class="s"> $$h2 = undef;</td></tr>
414 <tr><td class="h"><a name="241"></a>241</td><td></td><td></td><td></td><td></td><td class="s"> return $h;</td></tr>
415 <tr><td class="h"><a name="242"></a>242</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
416 <tr><td class="h"><a name="243"></a>243</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
417 <tr><td class="h"><a name="244"></a>244</td><td></td><td></td><td></td><td></td><td class="s"> my $el2 = $$h2 or return $h;</td></tr>
418 <tr><td class="h"><a name="245"></a>245</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
419 <tr><td class="h"><a name="246"></a>246</td><td></td><td></td><td></td><td></td><td class="s"> # add $el2 and its siblings to the head list for $h</td></tr>
420 <tr><td class="h"><a name="247"></a>247</td><td></td><td></td><td></td><td></td><td class="s"> # at start, $ell -> $el -> ... -> $ell is on $h (where $ell is</td></tr>
421 <tr><td class="h"><a name="248"></a>248</td><td></td><td></td><td></td><td></td><td class="s"> # $el->{left})</td></tr>
422 <tr><td class="h"><a name="249"></a>249</td><td></td><td></td><td></td><td></td><td class="s"> # $el2l -> $el2 -> ... -> $el2l are on $h2</td></tr>
423 <tr><td class="h"><a name="250"></a>250</td><td></td><td></td><td></td><td></td><td class="s"> # at end, $ell -> $el2l -> ... -> $el2 -> $el -> ... -> $ell are</td></tr>
424 <tr><td class="h"><a name="251"></a>251</td><td></td><td></td><td></td><td></td><td class="s"> # all on $h</td></tr>
425 <tr><td class="h"><a name="252"></a>252</td><td></td><td></td><td></td><td></td><td class="s"> my $el2l = $el2->{left};</td></tr>
426 <tr><td class="h"><a name="253"></a>253</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $el->{left}, $el2;</td></tr>
427 <tr><td class="h"><a name="254"></a>254</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $el2l, $el;</td></tr>
428 <tr><td class="h"><a name="255"></a>255</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
429 <tr><td class="h"><a name="256"></a>256</td><td></td><td></td><td></td><td></td><td class="s"> # change the top link if needed</td></tr>
430 <tr><td class="h"><a name="257"></a>257</td><td></td><td></td><td></td><td></td><td class="s"> $$h = $el2 if $el->{val}->cmp( $el2->{val} ) > 0;</td></tr>
431 <tr><td class="h"><a name="258"></a>258</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
432 <tr><td class="h"><a name="259"></a>259</td><td></td><td></td><td></td><td></td><td class="s"> # clean out $h2</td></tr>
433 <tr><td class="h"><a name="260"></a>260</td><td></td><td></td><td></td><td></td><td class="s"> $$h2 = undef;</td></tr>
434 <tr><td class="h"><a name="261"></a>261</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
435 <tr><td class="h"><a name="262"></a>262</td><td></td><td></td><td></td><td></td><td class="s"> # return the heap</td></tr>
436 <tr><td class="h"><a name="263"></a>263</td><td></td><td></td><td></td><td></td><td class="s"> $h;</td></tr>
437 <tr><td class="h"><a name="264"></a>264</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
438 <tr><td class="h"><a name="265"></a>265</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
439 <tr><td class="h"><a name="266"></a>266</td><td></td><td></td><td></td><td></td><td class="s"># a key has been decreased, it may have to percolate up in its heap</td></tr>
440 <tr><td class="h"><a name="267"></a>267</td><td></td><td></td><td></td><td></td><td class="s">sub decrease_key {</td></tr>
441 <tr><td class="h"><a name="268"></a>268</td><td></td><td></td><td></td><td></td><td class="s"> my $h = shift;</td></tr>
442 <tr><td class="h"><a name="269"></a>269</td><td></td><td></td><td></td><td></td><td class="s"> my $top = $$h;</td></tr>
443 <tr><td class="h"><a name="270"></a>270</td><td></td><td></td><td></td><td></td><td class="s"> my $v = shift;</td></tr>
444 <tr><td class="h"><a name="271"></a>271</td><td></td><td></td><td></td><td></td><td class="s"> my $el = $v->heap or return undef;</td></tr>
445 <tr><td class="h"><a name="272"></a>272</td><td></td><td></td><td></td><td></td><td class="s"> my $p;</td></tr>
446 <tr><td class="h"><a name="273"></a>273</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
447 <tr><td class="h"><a name="274"></a>274</td><td></td><td></td><td></td><td></td><td class="s"> # first, link $h to $el if it is now the smallest (we will</td></tr>
448 <tr><td class="h"><a name="275"></a>275</td><td></td><td></td><td></td><td></td><td class="s"> # soon link $el to $top to properly put it up to the top list,</td></tr>
449 <tr><td class="h"><a name="276"></a>276</td><td></td><td></td><td></td><td></td><td class="s"> # if it isn't already there)</td></tr>
450 <tr><td class="h"><a name="277"></a>277</td><td></td><td></td><td></td><td></td><td class="s"> $$h = $el if $top->{val}->cmp( $v ) > 0;</td></tr>
451 <tr><td class="h"><a name="278"></a>278</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
452 <tr><td class="h"><a name="279"></a>279</td><td></td><td></td><td></td><td></td><td class="s"> if( $p = $el->{p} and $v->cmp($p->{val}) < 0 ) {</td></tr>
453 <tr><td class="h"><a name="280"></a>280</td><td></td><td></td><td></td><td></td><td class="s"> # remove $el from its parent's list - it is now smaller</td></tr>
454 <tr><td class="h"><a name="281"></a>281</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
455 <tr><td class="h"><a name="282"></a>282</td><td></td><td></td><td></td><td></td><td class="s"> ascending_cut $top, $p, $el;</td></tr>
456 <tr><td class="h"><a name="283"></a>283</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
457 <tr><td class="h"><a name="284"></a>284</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
458 <tr><td class="h"><a name="285"></a>285</td><td></td><td></td><td></td><td></td><td class="s"> $v;</td></tr>
459 <tr><td class="h"><a name="286"></a>286</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
460 <tr><td class="h"><a name="287"></a>287</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
461 <tr><td class="h"><a name="288"></a>288</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
462 <tr><td class="h"><a name="289"></a>289</td><td></td><td></td><td></td><td></td><td class="s"># to delete an item, we bubble it to the top of its heap (as if its key</td></tr>
463 <tr><td class="h"><a name="290"></a>290</td><td></td><td></td><td></td><td></td><td class="s"># had been decreased to -infinity), and then remove it (as in extract_top)</td></tr>
464 <tr><td class="h"><a name="291"></a>291</td><td></td><td></td><td></td><td></td><td class="s">sub delete {</td></tr>
465 <tr><td class="h"><a name="292"></a>292</td><td></td><td></td><td></td><td></td><td class="s"> my $h = shift;</td></tr>
466 <tr><td class="h"><a name="293"></a>293</td><td></td><td></td><td></td><td></td><td class="s"> my $v = shift;</td></tr>
467 <tr><td class="h"><a name="294"></a>294</td><td></td><td></td><td></td><td></td><td class="s"> my $el = $v->heap or return undef;</td></tr>
468 <tr><td class="h"><a name="295"></a>295</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
469 <tr><td class="h"><a name="296"></a>296</td><td></td><td></td><td></td><td></td><td class="s"> # if there is a parent, cut $el to the top (as if it had just had its</td></tr>
470 <tr><td class="h"><a name="297"></a>297</td><td></td><td></td><td></td><td></td><td class="s"> # key decreased to a smaller value than $p's value</td></tr>
471 <tr><td class="h"><a name="298"></a>298</td><td></td><td></td><td></td><td></td><td class="s"> my $p;</td></tr>
472 <tr><td class="h"><a name="299"></a>299</td><td></td><td></td><td></td><td></td><td class="s"> $p = $el->{p} and ascending_cut $$h, $p, $el;</td></tr>
473 <tr><td class="h"><a name="300"></a>300</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
474 <tr><td class="h"><a name="301"></a>301</td><td></td><td></td><td></td><td></td><td class="s"> # $el is in the top list now, make it look like the smallest and</td></tr>
475 <tr><td class="h"><a name="302"></a>302</td><td></td><td></td><td></td><td></td><td class="s"> # remove it</td></tr>
476 <tr><td class="h"><a name="303"></a>303</td><td></td><td></td><td></td><td></td><td class="s"> $$h = $el;</td></tr>
477 <tr><td class="h"><a name="304"></a>304</td><td></td><td></td><td></td><td></td><td class="s"> $h->extract_top;</td></tr>
478 <tr><td class="h"><a name="305"></a>305</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
479 <tr><td class="h"><a name="306"></a>306</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
480 <tr><td class="h"><a name="307"></a>307</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
481 <tr><td class="h"><a name="308"></a>308</td><td></td><td></td><td></td><td></td><td class="s">################################################# internal utility functions</td></tr>
482 <tr><td class="h"><a name="309"></a>309</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
483 <tr><td class="h"><a name="310"></a>310</td><td></td><td></td><td></td><td></td><td class="s">sub elem {</td></tr>
484 <tr><td class="h"><a name="311"></a>311</td><td></td><td></td><td></td><td></td><td class="s"> my $v = shift;</td></tr>
485 <tr><td class="h"><a name="312"></a>312</td><td></td><td></td><td></td><td></td><td class="s"> my $el = undef;</td></tr>
486 <tr><td class="h"><a name="313"></a>313</td><td></td><td></td><td></td><td></td><td class="s"> $el = {</td></tr>
487 <tr><td class="h"><a name="314"></a>314</td><td></td><td></td><td></td><td></td><td class="s"> p => undef,</td></tr>
488 <tr><td class="h"><a name="315"></a>315</td><td></td><td></td><td></td><td></td><td class="s"> degree => 0,</td></tr>
489 <tr><td class="h"><a name="316"></a>316</td><td></td><td></td><td></td><td></td><td class="s"> mark => 0,</td></tr>
490 <tr><td class="h"><a name="317"></a>317</td><td></td><td></td><td></td><td></td><td class="s"> child => undef,</td></tr>
491 <tr><td class="h"><a name="318"></a>318</td><td></td><td></td><td></td><td></td><td class="s"> val => $v,</td></tr>
492 <tr><td class="h"><a name="319"></a>319</td><td></td><td></td><td></td><td></td><td class="s"> left => undef,</td></tr>
493 <tr><td class="h"><a name="320"></a>320</td><td></td><td></td><td></td><td></td><td class="s"> right => undef,</td></tr>
494 <tr><td class="h"><a name="321"></a>321</td><td></td><td></td><td></td><td></td><td class="s"> };</td></tr>
495 <tr><td class="h"><a name="322"></a>322</td><td></td><td></td><td></td><td></td><td class="s"> $el->{left} = $el->{right} = $el;</td></tr>
496 <tr><td class="h"><a name="323"></a>323</td><td></td><td></td><td></td><td></td><td class="s"> $v->heap($el);</td></tr>
497 <tr><td class="h"><a name="324"></a>324</td><td></td><td></td><td></td><td></td><td class="s"> $el;</td></tr>
498 <tr><td class="h"><a name="325"></a>325</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
499 <tr><td class="h"><a name="326"></a>326</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
500 <tr><td class="h"><a name="327"></a>327</td><td></td><td></td><td></td><td></td><td class="s">sub elem_DESTROY {</td></tr>
501 <tr><td class="h"><a name="328"></a>328</td><td></td><td></td><td></td><td></td><td class="s"> my $el = shift;</td></tr>
502 <tr><td class="h"><a name="329"></a>329</td><td></td><td></td><td></td><td></td><td class="s"> my $ch;</td></tr>
503 <tr><td class="h"><a name="330"></a>330</td><td></td><td></td><td></td><td></td><td class="s"> my $next;</td></tr>
504 <tr><td class="h"><a name="331"></a>331</td><td></td><td></td><td></td><td></td><td class="s"> $el->{left}->{right} = undef;</td></tr>
505 <tr><td class="h"><a name="332"></a>332</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
506 <tr><td class="h"><a name="333"></a>333</td><td></td><td></td><td></td><td></td><td class="s"> while( $el ) {</td></tr>
507 <tr><td class="h"><a name="334"></a>334</td><td></td><td></td><td></td><td></td><td class="s"> $ch = $el->{child} and elem_DESTROY $ch;</td></tr>
508 <tr><td class="h"><a name="335"></a>335</td><td></td><td></td><td></td><td></td><td class="s"> $next = $el->{right};</td></tr>
509 <tr><td class="h"><a name="336"></a>336</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
510 <tr><td class="h"><a name="337"></a>337</td><td></td><td></td><td></td><td></td><td class="s"> defined $el->{val} and $el->{val}->heap(undef);</td></tr>
511 <tr><td class="h"><a name="338"></a>338</td><td></td><td></td><td></td><td></td><td class="s"> $el->{child} = $el->{right} = $el->{left} = $el->{p} = $el->{val}</td></tr>
512 <tr><td class="h"><a name="339"></a>339</td><td></td><td></td><td></td><td></td><td class="s"> = undef;</td></tr>
513 <tr><td class="h"><a name="340"></a>340</td><td></td><td></td><td></td><td></td><td class="s"> $el = $next;</td></tr>
514 <tr><td class="h"><a name="341"></a>341</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
515 <tr><td class="h"><a name="342"></a>342</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
516 <tr><td class="h"><a name="343"></a>343</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
517 <tr><td class="h"><a name="344"></a>344</td><td></td><td></td><td></td><td></td><td class="s">sub link_to_left_of {</td></tr>
518 <tr><td class="h"><a name="345"></a>345</td><td></td><td></td><td></td><td></td><td class="s"> my $l = shift;</td></tr>
519 <tr><td class="h"><a name="346"></a>346</td><td></td><td></td><td></td><td></td><td class="s"> my $r = shift;</td></tr>
520 <tr><td class="h"><a name="347"></a>347</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
521 <tr><td class="h"><a name="348"></a>348</td><td></td><td></td><td></td><td></td><td class="s"> $l->{right} = $r;</td></tr>
522 <tr><td class="h"><a name="349"></a>349</td><td></td><td></td><td></td><td></td><td class="s"> $r->{left} = $l;</td></tr>
523 <tr><td class="h"><a name="350"></a>350</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
524 <tr><td class="h"><a name="351"></a>351</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
525 <tr><td class="h"><a name="352"></a>352</td><td></td><td></td><td></td><td></td><td class="s">sub link_as_parent_of {</td></tr>
526 <tr><td class="h"><a name="353"></a>353</td><td></td><td></td><td></td><td></td><td class="s"> my $p = shift;</td></tr>
527 <tr><td class="h"><a name="354"></a>354</td><td></td><td></td><td></td><td></td><td class="s"> my $c = shift;</td></tr>
528 <tr><td class="h"><a name="355"></a>355</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
529 <tr><td class="h"><a name="356"></a>356</td><td></td><td></td><td></td><td></td><td class="s"> my $pc;</td></tr>
530 <tr><td class="h"><a name="357"></a>357</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
531 <tr><td class="h"><a name="358"></a>358</td><td></td><td></td><td></td><td></td><td class="s"> if( $pc = $p->{child} ) {</td></tr>
532 <tr><td class="h"><a name="359"></a>359</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $pc->{left}, $c;</td></tr>
533 <tr><td class="h"><a name="360"></a>360</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $c, $pc;</td></tr>
534 <tr><td class="h"><a name="361"></a>361</td><td></td><td></td><td></td><td></td><td class="s"> } else {</td></tr>
535 <tr><td class="h"><a name="362"></a>362</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $c, $c;</td></tr>
536 <tr><td class="h"><a name="363"></a>363</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
537 <tr><td class="h"><a name="364"></a>364</td><td></td><td></td><td></td><td></td><td class="s"> $p->{child} = $c;</td></tr>
538 <tr><td class="h"><a name="365"></a>365</td><td></td><td></td><td></td><td></td><td class="s"> $c->{p} = $p;</td></tr>
539 <tr><td class="h"><a name="366"></a>366</td><td></td><td></td><td></td><td></td><td class="s"> $p->{degree}++;</td></tr>
540 <tr><td class="h"><a name="367"></a>367</td><td></td><td></td><td></td><td></td><td class="s"> $c->{mark} = 0;</td></tr>
541 <tr><td class="h"><a name="368"></a>368</td><td></td><td></td><td></td><td></td><td class="s"> $p;</td></tr>
542 <tr><td class="h"><a name="369"></a>369</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
543 <tr><td class="h"><a name="370"></a>370</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
544 <tr><td class="h"><a name="371"></a>371</td><td></td><td></td><td></td><td></td><td class="s">sub consolidate {</td></tr>
545 <tr><td class="h"><a name="372"></a>372</td><td></td><td></td><td></td><td></td><td class="s"> my $h = shift;</td></tr>
546 <tr><td class="h"><a name="373"></a>373</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
547 <tr><td class="h"><a name="374"></a>374</td><td></td><td></td><td></td><td></td><td class="s"> my $cur;</td></tr>
548 <tr><td class="h"><a name="375"></a>375</td><td></td><td></td><td></td><td></td><td class="s"> my $this;</td></tr>
549 <tr><td class="h"><a name="376"></a>376</td><td></td><td></td><td></td><td></td><td class="s"> my $next = $$h;</td></tr>
550 <tr><td class="h"><a name="377"></a>377</td><td></td><td></td><td></td><td></td><td class="s"> my $last = $next->{left};</td></tr>
551 <tr><td class="h"><a name="378"></a>378</td><td></td><td></td><td></td><td></td><td class="s"> my @a;</td></tr>
552 <tr><td class="h"><a name="379"></a>379</td><td></td><td></td><td></td><td></td><td class="s"> do {</td></tr>
553 <tr><td class="h"><a name="380"></a>380</td><td></td><td></td><td></td><td></td><td class="s"> # examine next item on top list</td></tr>
554 <tr><td class="h"><a name="381"></a>381</td><td></td><td></td><td></td><td></td><td class="s"> $this = $cur = $next;</td></tr>
555 <tr><td class="h"><a name="382"></a>382</td><td></td><td></td><td></td><td></td><td class="s"> $next = $cur->{right};</td></tr>
556 <tr><td class="h"><a name="383"></a>383</td><td></td><td></td><td></td><td></td><td class="s"> my $d = $cur->{degree};</td></tr>
557 <tr><td class="h"><a name="384"></a>384</td><td></td><td></td><td></td><td></td><td class="s"> my $alt;</td></tr>
558 <tr><td class="h"><a name="385"></a>385</td><td></td><td></td><td></td><td></td><td class="s"> while( $alt = $a[$d] ) {</td></tr>
559 <tr><td class="h"><a name="386"></a>386</td><td></td><td></td><td></td><td></td><td class="s"> # we already saw another item of the same degree,</td></tr>
560 <tr><td class="h"><a name="387"></a>387</td><td></td><td></td><td></td><td></td><td class="s"> # put the larger valued one under the smaller valued</td></tr>
561 <tr><td class="h"><a name="388"></a>388</td><td></td><td></td><td></td><td></td><td class="s"> # one - switch $cur and $alt if necessary so that $cur</td></tr>
562 <tr><td class="h"><a name="389"></a>389</td><td></td><td></td><td></td><td></td><td class="s"> # is the smaller</td></tr>
563 <tr><td class="h"><a name="390"></a>390</td><td></td><td></td><td></td><td></td><td class="s"> ($cur,$alt) = ($alt,$cur)</td></tr>
564 <tr><td class="h"><a name="391"></a>391</td><td></td><td></td><td></td><td></td><td class="s"> if $cur->{val}->cmp( $alt->{val} ) > 0;</td></tr>
565 <tr><td class="h"><a name="392"></a>392</td><td></td><td></td><td></td><td></td><td class="s"> # remove $alt from the top list</td></tr>
566 <tr><td class="h"><a name="393"></a>393</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $alt->{left}, $alt->{right};</td></tr>
567 <tr><td class="h"><a name="394"></a>394</td><td></td><td></td><td></td><td></td><td class="s"> # and put it under $cur</td></tr>
568 <tr><td class="h"><a name="395"></a>395</td><td></td><td></td><td></td><td></td><td class="s"> link_as_parent_of $cur, $alt;</td></tr>
569 <tr><td class="h"><a name="396"></a>396</td><td></td><td></td><td></td><td></td><td class="s"> # make sure that $h still points to a node at the top</td></tr>
570 <tr><td class="h"><a name="397"></a>397</td><td></td><td></td><td></td><td></td><td class="s"> $$h = $cur;</td></tr>
571 <tr><td class="h"><a name="398"></a>398</td><td></td><td></td><td></td><td></td><td class="s"> # we've removed the old $d degree entry</td></tr>
572 <tr><td class="h"><a name="399"></a>399</td><td></td><td></td><td></td><td></td><td class="s"> $a[$d] = undef;</td></tr>
573 <tr><td class="h"><a name="400"></a>400</td><td></td><td></td><td></td><td></td><td class="s"> # and we now have a $d+1 degree entry to try to insert</td></tr>
574 <tr><td class="h"><a name="401"></a>401</td><td></td><td></td><td></td><td></td><td class="s"> # into @a</td></tr>
575 <tr><td class="h"><a name="402"></a>402</td><td></td><td></td><td></td><td></td><td class="s"> ++$d;</td></tr>
576 <tr><td class="h"><a name="403"></a>403</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
577 <tr><td class="h"><a name="404"></a>404</td><td></td><td></td><td></td><td></td><td class="s"> # found a previously unused degree</td></tr>
578 <tr><td class="h"><a name="405"></a>405</td><td></td><td></td><td></td><td></td><td class="s"> $a[$d] = $cur;</td></tr>
579 <tr><td class="h"><a name="406"></a>406</td><td></td><td></td><td></td><td></td><td class="s"> } until $this == $last;</td></tr>
580 <tr><td class="h"><a name="407"></a>407</td><td></td><td></td><td></td><td></td><td class="s"> $cur = $$h;</td></tr>
581 <tr><td class="h"><a name="408"></a>408</td><td></td><td></td><td></td><td></td><td class="s"> for $cur (grep defined, @a) {</td></tr>
582 <tr><td class="h"><a name="409"></a>409</td><td></td><td></td><td></td><td></td><td class="s"> $$h = $cur if $$h->{val}->cmp( $cur->{val} ) > 0;</td></tr>
583 <tr><td class="h"><a name="410"></a>410</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
584 <tr><td class="h"><a name="411"></a>411</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
585 <tr><td class="h"><a name="412"></a>412</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
586 <tr><td class="h"><a name="413"></a>413</td><td></td><td></td><td></td><td></td><td class="s">sub ascending_cut {</td></tr>
587 <tr><td class="h"><a name="414"></a>414</td><td></td><td></td><td></td><td></td><td class="s"> my $top = shift;</td></tr>
588 <tr><td class="h"><a name="415"></a>415</td><td></td><td></td><td></td><td></td><td class="s"> my $p = shift;</td></tr>
589 <tr><td class="h"><a name="416"></a>416</td><td></td><td></td><td></td><td></td><td class="s"> my $el = shift;</td></tr>
590 <tr><td class="h"><a name="417"></a>417</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
591 <tr><td class="h"><a name="418"></a>418</td><td></td><td></td><td></td><td></td><td class="s"> while( 1 ) {</td></tr>
592 <tr><td class="h"><a name="419"></a>419</td><td></td><td></td><td></td><td></td><td class="s"> if( --$p->{degree} ) {</td></tr>
593 <tr><td class="h"><a name="420"></a>420</td><td></td><td></td><td></td><td></td><td class="s"> # there are still other children below $p</td></tr>
594 <tr><td class="h"><a name="421"></a>421</td><td></td><td></td><td></td><td></td><td class="s"> my $l = $el->{left};</td></tr>
595 <tr><td class="h"><a name="422"></a>422</td><td></td><td></td><td></td><td></td><td class="s"> $p->{child} = $l;</td></tr>
596 <tr><td class="h"><a name="423"></a>423</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $l, $el->{right};</td></tr>
597 <tr><td class="h"><a name="424"></a>424</td><td></td><td></td><td></td><td></td><td class="s"> } else {</td></tr>
598 <tr><td class="h"><a name="425"></a>425</td><td></td><td></td><td></td><td></td><td class="s"> # $el was the only child of $p</td></tr>
599 <tr><td class="h"><a name="426"></a>426</td><td></td><td></td><td></td><td></td><td class="s"> $p->{child} = undef;</td></tr>
600 <tr><td class="h"><a name="427"></a>427</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
601 <tr><td class="h"><a name="428"></a>428</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $top->{left}, $el;</td></tr>
602 <tr><td class="h"><a name="429"></a>429</td><td></td><td></td><td></td><td></td><td class="s"> link_to_left_of $el, $top;</td></tr>
603 <tr><td class="h"><a name="430"></a>430</td><td></td><td></td><td></td><td></td><td class="s"> $el->{p} = undef;</td></tr>
604 <tr><td class="h"><a name="431"></a>431</td><td></td><td></td><td></td><td></td><td class="s"> $el->{mark} = 0;</td></tr>
605 <tr><td class="h"><a name="432"></a>432</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
606 <tr><td class="h"><a name="433"></a>433</td><td></td><td></td><td></td><td></td><td class="s"> # propagate up the list</td></tr>
607 <tr><td class="h"><a name="434"></a>434</td><td></td><td></td><td></td><td></td><td class="s"> $el = $p;</td></tr>
608 <tr><td class="h"><a name="435"></a>435</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
609 <tr><td class="h"><a name="436"></a>436</td><td></td><td></td><td></td><td></td><td class="s"> # quit at the top</td></tr>
610 <tr><td class="h"><a name="437"></a>437</td><td></td><td></td><td></td><td></td><td class="s"> last unless $p = $el->{p};</td></tr>
611 <tr><td class="h"><a name="438"></a>438</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
612 <tr><td class="h"><a name="439"></a>439</td><td></td><td></td><td></td><td></td><td class="s"> # quit if we can mark $el</td></tr>
613 <tr><td class="h"><a name="440"></a>440</td><td></td><td></td><td></td><td></td><td class="s"> $el->{mark} = 1, last unless $el->{mark};</td></tr>
614 <tr><td class="h"><a name="441"></a>441</td><td></td><td></td><td></td><td></td><td class="s"> }</td></tr>
615 <tr><td class="h"><a name="442"></a>442</td><td></td><td></td><td></td><td></td><td class="s">}</td></tr>
616 <tr><td class="h"><a name="443"></a>443</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
617 <tr><td class="h"><a name="444"></a>444</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
618 <tr><td class="h"><a name="445"></a>445</td><td class="c3">1</td><td class="c0"><span title="Avg 13µs">13µs</span></td><td></td><td></td><td class="s">1;</td></tr>
619 <tr><td class="h"><a name="446"></a>446</td><td></td><td></td><td></td><td></td><td class="s"></td></tr>
620 <tr><td class="h"><a name="447"></a>447</td><td></td><td></td><td></td><td></td><td class="s">__END__</td></tr>
621 </tbody></table></div>
623 <script type="text/javascript"> $(document).ready(function() {
625 $("#subs_table").tablesorter({
628 3: { sorter: 'fmt_time' },
629 4: { sorter: 'fmt_time' }
635 <div class="footer">Report produced by the
636 <a href="http://search.cpan.org/dist/Devel-NYTProf/">NYTProf 4.06</a>
637 Perl profiler, developed by
638 <a href="http://www.linkedin.com/in/timbunce">Tim Bunce</a> and
639 <a href="http://code.nytimes.com">Adam Kaplan</a>.
641 <br /><br /><br /><br /><br /><br /><br /><br /><br /><br />
projects / scpubgit/stemmatology.git / blob