148 lines
5.7 KiB
HTML
Executable File
148 lines
5.7 KiB
HTML
Executable File
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
|
|
|
|
<html xmlns="http://www.w3.org/1999/xhtml">
|
|
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=iso-8859-1" />
|
|
<title>LOOP: Priority Queue</title>
|
|
<style type="text/css" media="all"><!--
|
|
@import "../../loop.css";
|
|
@import "../../layout1.css";
|
|
--></style>
|
|
</head>
|
|
|
|
<body>
|
|
|
|
<div id="Header">Class Models for Lua</div>
|
|
<div id="Logo"><img alt="small (1K)" src="../../small.gif" height="70"></div>
|
|
|
|
<div id="Menu">
|
|
<div class="outside"><div class="inside"><ul>
|
|
<li><a href="../../index.html", title="">Home</a></li>
|
|
<li><a href="../../release/index.html", title="Installation">Install</a></li>
|
|
<li><a href="../../manual/index.html", title="User Manual">Manual</a></li>
|
|
<li><a href="../index.html", title="Class Library">Library</a>
|
|
<div class="outside"><div class="inside"><ul>
|
|
<li><a href="../overview.html#collection", title="Collections">collection</a>
|
|
</li>
|
|
<li><a href="../overview.html#compiler", title="Compiling">compiler</a>
|
|
</li>
|
|
<li><a href="../overview.html#debug", title="Debugging">debug</a>
|
|
</li>
|
|
<li><a href="../overview.html#object", title="Objects">object</a>
|
|
</li>
|
|
<li><a href="../overview.html#serial", title="Serialization">serial</a>
|
|
</li>
|
|
<li><a href="../overview.html#thread", title="Threading">thread</a>
|
|
</li>
|
|
</ul></div></div>
|
|
</li>
|
|
<li><a href="../../contact.html", title="Contact People">Contact</a></li>
|
|
<li><a href="http://luaforge.net/projects/oil/", title="Project at LuaForge">LuaForge</a></li>
|
|
</ul></div></div>
|
|
|
|
</div>
|
|
|
|
<div class="content">
|
|
<h1>Priority Queue</h1>
|
|
<h2><code>loop.collection.PriorityQueue</code></h2><br>
|
|
<p>Class of objects that store a set of values with associated weight values so that these values are arranged in the descending order of weight.
|
|
The values are stored like in the <a href="OrderedSet.html"><code>OrderedSet</code></a> class, but the values are sorted in descending order of weight.
|
|
This class is useful for implementing priority queues with no repeated values and which priorities are comparable values like numbers or strings.</p>
|
|
|
|
<p>Each instance holds an additional table containing the priority of each value inserted in the queue that are used to keep the values properly sorted.</p>
|
|
|
|
<h2>Behavior</h2>
|
|
|
|
<h3>Methods</h3>
|
|
|
|
<dl>
|
|
|
|
<dt><code><b>contains</b>(value)</code></dt>
|
|
<dd>
|
|
Return true if a <code>value</code> is inserted in the queue or false otherwise.
|
|
</dd>
|
|
|
|
<dt><code><b>dequeue</b>()</code></dt>
|
|
<dd>
|
|
Removes the first value of the queue and then returns it.
|
|
If the queue is empty this function has no effect.
|
|
</dd>
|
|
|
|
<dt><code><b>empty</b>()</code></dt>
|
|
<dd>
|
|
Return true if there is no value inserted in the queue or false otherwise.
|
|
</dd>
|
|
|
|
<dt><code><b>enqueue</b>(value, priority)</code></dt>
|
|
<dd>
|
|
Adds <code>value</code> to the queue just before the value with priority larger than <code>priority</code>.
|
|
<code>value</code> is returned if successfully added.
|
|
If <code>value</code> is already inserted then the call has no effect and no value is returned.
|
|
</dd>
|
|
|
|
<dt><code><b>head</b>()</code></dt>
|
|
<dd>
|
|
Returns the value at the start of the queue.
|
|
</dd>
|
|
|
|
<dt><code><b>remove</b>(value [, start])</code></dt>
|
|
<dd>
|
|
Searches for <code>value</code> and removes it from the queue starting the search after the value of <code>start</code>.
|
|
If <code>start</code> is not provided the search is done through the entire set.
|
|
The removed value and its priority are returned or no value is returned if <code>value</code> is not found.
|
|
</dd>
|
|
|
|
<dt><code><b>priority</b>(value)</code></dt>
|
|
<dd>
|
|
Returns the priority associated to the value <code>value</code> inserted in the queue.
|
|
</dd>
|
|
|
|
<dt><code><b>tail</b>()</code></dt>
|
|
<dd>
|
|
Returns the value at the end of the queue.
|
|
</dd>
|
|
|
|
</dl>
|
|
|
|
<h2>Remarks</h2>
|
|
|
|
<ul>
|
|
<li>
|
|
Instances cannot store the name of class members as strings.
|
|
To do so, use the class operations over an empty table like in the following example:
|
|
<pre>
|
|
PriorityQueue = require "loop.collection.PriorityQueue"
|
|
queue = {}
|
|
PriorityQueue.enqueue(queue, "first", 1)
|
|
PriorityQueue.enqueue(queue, "enqueue", 2)
|
|
PriorityQueue.enqueue(queue, "head", 3)
|
|
for word in PriorityQueue.sequence(queue) do
|
|
io.write(word, " ")
|
|
end
|
|
</pre>
|
|
</li>
|
|
</ul>
|
|
<!--
|
|
<h2>Examples</h2>
|
|
|
|
<h3>$ExampleName</h3>
|
|
|
|
<pre>
|
|
- - example missing
|
|
</pre>
|
|
-->
|
|
|
|
</div>
|
|
|
|
<div class="content">
|
|
<p><small><strong>Copyright (C) 2004-2008 Tecgraf, PUC-Rio</strong></small></p>
|
|
<small>This project is currently being maintained by <a href="http://www.tecgraf.puc-rio.br">Tecgraf</a> at <a href="http://www.puc-rio.br">PUC-Rio</a>.</small>
|
|
</div>
|
|
|
|
|
|
|
|
</body>
|
|
|
|
</html>
|