rparedis
/
PythonDEVS-BBL


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242
							
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="X-UA-Compatible" content="IE=Edge" />
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <title>pypdevsbbl.extra.heap &#8212; Python(P)DEVS-BBL  documentation</title>
    <link rel="stylesheet" href="../../../_static/nature.css" type="text/css" />
    <link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
    <link rel="stylesheet" type="text/css" href="../../../_static/custom.css" />
    <script type="text/javascript" id="documentation_options" data-url_root="../../../" src="../../../_static/documentation_options.js"></script>
    <script type="text/javascript" src="../../../_static/jquery.js"></script>
    <script type="text/javascript" src="../../../_static/underscore.js"></script>
    <script type="text/javascript" src="../../../_static/doctools.js"></script>
    <script type="text/javascript" src="../../../_static/language_data.js"></script>
    <script async="async" type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <link rel="index" title="Index" href="../../../genindex.html" />
    <link rel="search" title="Search" href="../../../search.html" /> 
  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">Python(P)DEVS-BBL  documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" >Module code</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="../extra.html" accesskey="U">pypdevsbbl.extra</a> &#187;</li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <h1>Source code for pypdevsbbl.extra.heap</h1><div class="highlight"><pre>
<span></span><span class="c1">#  Copyright 2020 Modelling, Simulation and Design Lab (MSDL) at</span>
<span class="c1">#  McGill University and the University of Antwerp (http://msdl.cs.mcgill.ca/)</span>
<span class="c1">#</span>
<span class="c1">#  Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);</span>
<span class="c1">#  you may not use this file except in compliance with the License.</span>
<span class="c1">#  You may obtain a copy of the License at</span>
<span class="c1">#</span>
<span class="c1">#     http://www.apache.org/licenses/LICENSE-2.0</span>
<span class="c1">#</span>
<span class="c1">#  Unless required by applicable law or agreed to in writing, software</span>
<span class="c1">#  distributed under the License is distributed on an &quot;AS IS&quot; BASIS,</span>
<span class="c1">#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.</span>
<span class="c1">#  See the License for the specific language governing permissions and</span>
<span class="c1">#  limitations under the License.</span>

<span class="sd">&quot;&quot;&quot;This file is a python-implementation for a heap.</span>

<span class="sd">This file allows for both a min-heap and a max-heap by making</span>
<span class="sd">use of the :meth:`MIN_HEAP` and :meth:`MAX_HEAP` comparator</span>
<span class="sd">functions listed below.</span>
<span class="sd">&quot;&quot;&quot;</span>

<span class="n">MIN_HEAP</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">x</span><span class="p">,</span> <span class="n">l</span><span class="p">:</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="n">l</span>
<span class="sd">&quot;&quot;&quot;Comparator function, indicating to use a min-heap as the heap.</span>

<span class="sd">See Also:</span>
<span class="sd">    :class:`heap`</span>
<span class="sd">&quot;&quot;&quot;</span>

<span class="n">MAX_HEAP</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">x</span><span class="p">,</span> <span class="n">l</span><span class="p">:</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="n">l</span>
<span class="sd">&quot;&quot;&quot;Comparator function, indicating to use a max-heap as the heap.</span>

<span class="sd">See Also:</span>
<span class="sd">    :class:`heap`</span>
<span class="sd">&quot;&quot;&quot;</span>

<div class="viewcode-block" id="heap"><a class="viewcode-back" href="../../../pypdevsbbl.extra.heap.html#pypdevsbbl.extra.heap.heap">[docs]</a><span class="k">class</span> <span class="nc">heap</span><span class="p">:</span>
    <span class="sd">&quot;&quot;&quot;The heap class is a simple heap implementation.</span>

<span class="sd">    Note:</span>
<span class="sd">        The comparator function takes two arguments (``x`` and ``l``, as</span>
<span class="sd">        described below) and should return ``True`` if ``x`` should be</span>
<span class="sd">        swapped with ``l``.</span>

<span class="sd">        - ``x``: The value of a node in the heap.</span>
<span class="sd">        - ``l``: The root to compare ``x`` to.</span>

<span class="sd">    Warning:</span>
<span class="sd">        You shouldn&#39;t need any other than :meth:`MIN_HEAP` or :meth:`MAX_HEAP`</span>
<span class="sd">        for the comparison function. If you do, you&#39;re probably doing strange</span>
<span class="sd">        things and you should consider using another datastructure.</span>

<span class="sd">    Args:</span>
<span class="sd">        comparator (def):   The comparison function. Defaults to :meth:`MAX_HEAP`.</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">comparator</span> <span class="o">=</span> <span class="n">MAX_HEAP</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">comparator</span> <span class="o">=</span> <span class="n">comparator</span>

    <span class="k">def</span> <span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Gets the heap size.&quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

<div class="viewcode-block" id="heap.items"><a class="viewcode-back" href="../../../pypdevsbbl.extra.heap.html#pypdevsbbl.extra.heap.heap.items">[docs]</a>    <span class="k">def</span> <span class="nf">items</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Get a copy of the contents of the heap as a list.&quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span></div>

<div class="viewcode-block" id="heap.empty"><a class="viewcode-back" href="../../../pypdevsbbl.extra.heap.html#pypdevsbbl.extra.heap.heap.empty">[docs]</a>    <span class="k">def</span> <span class="nf">empty</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Check if the heap is empty.</span>

<span class="sd">        Returns:</span>
<span class="sd">            ``True`` if the heap is empty, ``False`` otherwise.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span></div>

<div class="viewcode-block" id="heap._heapify"><a class="viewcode-back" href="../../../pypdevsbbl.extra.heap.html#pypdevsbbl.extra.heap.heap._heapify">[docs]</a>    <span class="k">def</span> <span class="nf">_heapify</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Fix the heap, making sure the heap condition remains satisfied.</span>

<span class="sd">        Warning:</span>
<span class="sd">            This function should not be called from an external source.</span>

<span class="sd">        Args:</span>
<span class="sd">            i (int):    Index of the root node to heapify.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">largest</span> <span class="o">=</span> <span class="n">i</span>
        <span class="n">l</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span>   <span class="c1"># left</span>
        <span class="n">r</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">2</span>   <span class="c1"># right</span>
        <span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

        <span class="k">if</span> <span class="n">l</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="ow">and</span> <span class="bp">self</span><span class="o">.</span><span class="n">comparator</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">l</span><span class="p">],</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">largest</span><span class="p">]):</span>
            <span class="n">largest</span> <span class="o">=</span> <span class="n">l</span>

        <span class="k">if</span> <span class="n">r</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="ow">and</span> <span class="bp">self</span><span class="o">.</span><span class="n">comparator</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">r</span><span class="p">],</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">largest</span><span class="p">]):</span>
            <span class="n">largest</span> <span class="o">=</span> <span class="n">r</span>

        <span class="k">if</span> <span class="n">largest</span> <span class="o">!=</span> <span class="n">i</span><span class="p">:</span>
            <span class="c1"># Swap</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">largest</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">largest</span><span class="p">],</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>

            <span class="bp">self</span><span class="o">.</span><span class="n">_heapify</span><span class="p">(</span><span class="n">largest</span><span class="p">)</span>
            <span class="n">d</span> <span class="o">=</span> <span class="p">(</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">//</span> <span class="mi">2</span>
            <span class="k">if</span> <span class="n">d</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">_heapify</span><span class="p">(</span><span class="n">d</span><span class="p">)</span></div>

<div class="viewcode-block" id="heap.insert"><a class="viewcode-back" href="../../../pypdevsbbl.extra.heap.html#pypdevsbbl.extra.heap.heap.insert">[docs]</a>    <span class="k">def</span> <span class="nf">insert</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">node</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Insert a new node into the heap.</span>

<span class="sd">        Args:</span>
<span class="sd">            node (object):  A comparable object to insert.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">node</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_heapify</span><span class="p">((</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span> <span class="o">-</span> <span class="mi">2</span><span class="p">)</span> <span class="o">//</span> <span class="mi">2</span><span class="p">)</span></div>

<div class="viewcode-block" id="heap.pop"><a class="viewcode-back" href="../../../pypdevsbbl.extra.heap.html#pypdevsbbl.extra.heap.heap.pop">[docs]</a>    <span class="k">def</span> <span class="nf">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Remove the ith item of the heap.</span>

<span class="sd">        Args:</span>
<span class="sd">            i (int):    The index of the node to pop.</span>
<span class="sd">                        Defaults to 0 (the top).</span>

<span class="sd">        Returns:</span>
<span class="sd">            The item that was removed.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">top</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">peek</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
        <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_heapify</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">top</span></div>

<div class="viewcode-block" id="heap.indexOf"><a class="viewcode-back" href="../../../pypdevsbbl.extra.heap.html#pypdevsbbl.extra.heap.heap.indexOf">[docs]</a>    <span class="k">def</span> <span class="nf">indexOf</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">node</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Gets the index of a node.</span>

<span class="sd">        Args:</span>
<span class="sd">            node (object):  The node to get the index for.</span>

<span class="sd">        Returns:</span>
<span class="sd">            The index of that node.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">index</span><span class="p">(</span><span class="n">node</span><span class="p">)</span></div>

<div class="viewcode-block" id="heap.peek"><a class="viewcode-back" href="../../../pypdevsbbl.extra.heap.html#pypdevsbbl.extra.heap.heap.peek">[docs]</a>    <span class="k">def</span> <span class="nf">peek</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Look at the item at location i in the heap.</span>

<span class="sd">        Args:</span>
<span class="sd">            i (int):    The index of the node to peek.</span>
<span class="sd">                        Defaults to 0 (the top).</span>

<span class="sd">        Returns:</span>
<span class="sd">            ``None`` if the heap is empty, otherwise the item at index ``i``.</span>

<span class="sd">        Raises:</span>
<span class="sd">           IndexError: When the index is not found.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="kc">None</span> <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">empty</span><span class="p">()</span> <span class="k">else</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span></div></div>
</pre></div>

          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
<div id="searchbox" style="display: none" role="search">
  <h3>Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="../../../search.html" method="get">
      <input type="text" name="q" />
      <input type="submit" value="Go" />
      <input type="hidden" name="check_keywords" value="yes" />
      <input type="hidden" name="area" value="default" />
    </form>
    </div>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">Python(P)DEVS-BBL  documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" >Module code</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="../extra.html" >pypdevsbbl.extra</a> &#187;</li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2020, Randy Paredis.
      Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.8.5.
    </div>
  </body>
</html>