<?xml version="1.0" encoding="ascii"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>flumotion.common.avltree</title>
<link rel="stylesheet" href="epydoc.css" type="text/css" />
<script type="text/javascript" src="epydoc.js"></script>
</head>
<body bgcolor="white" text="black" link="blue" vlink="#204080"
alink="#204080">
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
bgcolor="#a0c0ff" cellspacing="0">
<tr valign="middle">
<!-- Tree link -->
<th> <a
href="module-tree.html">Trees</a> </th>
<!-- Index link -->
<th> <a
href="identifier-index.html">Indices</a> </th>
<!-- Help link -->
<th> <a
href="help.html">Help</a> </th>
<th class="navbar" width="100%"></th>
</tr>
</table>
<table width="100%" cellpadding="0" cellspacing="0">
<tr valign="top">
<td width="100%">
<span class="breadcrumbs">
Package flumotion ::
<a href="flumotion.common-module.html">Package common</a> ::
Module avltree
</span>
</td>
<td>
<table cellpadding="0" cellspacing="0">
<!-- hide/show private -->
<tr><td align="right"><span class="options">[<a href="javascript:void(0);" class="privatelink"
onclick="toggle_private();">hide private</a>]</span></td></tr>
</table>
</td>
</tr>
</table>
<!-- ==================== MODULE DESCRIPTION ==================== -->
<h1 class="epydoc">Module avltree</h1><p class="nomargin-top"><span class="codelink"><a href="flumotion.common.avltree-pysrc.html">source code</a></span></p>
<p>self-balancing binary search tree. A pure python functional-style
self-balancing binary search tree implementation, with an object-oriented
wrapper. Useful for maintaining sorted sets, traversing sets in order,
and closest-match lookups.</p>
<hr />
<div class="fields"> <p><strong>Version:</strong>
$Rev: 7138 $
</p>
</div><!-- ==================== CLASSES ==================== -->
<a name="section-Classes"></a>
<table class="summary" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
<td colspan="2" class="table-header">
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tr valign="top">
<td align="left"><span class="table-header">Classes</span></td>
<td align="right" valign="top"
><span class="options">[<a href="#section-Classes"
class="privatelink" onclick="toggle_private();"
>hide private</a>]</span></td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<a href="flumotion.common.avltree.AVLTree-class.html" class="summary-name">AVLTree</a>
</td>
</tr>
</table>
<!-- ==================== FUNCTIONS ==================== -->
<a name="section-Functions"></a>
<table class="summary" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
<td colspan="2" class="table-header">
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tr valign="top">
<td align="left"><span class="table-header">Functions</span></td>
<td align="right" valign="top"
><span class="options">[<a href="#section-Functions"
class="privatelink" onclick="toggle_private();"
>hide private</a>]</span></td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a name="node"></a><span class="summary-sig-name">node</span>(<span class="summary-sig-arg">l</span>,
<span class="summary-sig-arg">v</span>,
<span class="summary-sig-arg">r</span>,
<span class="summary-sig-arg">b</span>)</span><br />
Make an AVL tree node, consisting of a left tree, a value, a right
tree, and the "balance factor": the difference in lengths
between the right and left sides, respectively.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#node">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="flumotion.common.avltree-module.html#height" class="summary-sig-name">height</a>(<span class="summary-sig-arg">tree</span>)</span><br />
Return the height of an AVL tree.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#height">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a name="debug"></a><span class="summary-sig-name">debug</span>(<span class="summary-sig-arg">tree</span>,
<span class="summary-sig-arg">level</span>=<span class="summary-sig-default">0</span>)</span><br />
Print out a debugging representation of an AVL tree.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#debug">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a name="fromseq"></a><span class="summary-sig-name">fromseq</span>(<span class="summary-sig-arg">seq</span>)</span><br />
Populate and return an AVL tree from an iterable sequence.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#fromseq">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr class="private">
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a name="_balance"></a><span class="summary-sig-name">_balance</span>(<span class="summary-sig-arg">hdiff</span>,
<span class="summary-sig-arg">l</span>,
<span class="summary-sig-arg">v</span>,
<span class="summary-sig-arg">r</span>,
<span class="summary-sig-arg">b</span>)</span><br />
Internal method to rebalance an AVL tree, called as needed.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#_balance">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="flumotion.common.avltree-module.html#insert" class="summary-sig-name">insert</a>(<span class="summary-sig-arg">tree</span>,
<span class="summary-sig-arg">value</span>)</span><br />
Insert a value into an AVL tree.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#insert">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="flumotion.common.avltree-module.html#delete" class="summary-sig-name">delete</a>(<span class="summary-sig-arg">tree</span>,
<span class="summary-sig-arg">value</span>)</span><br />
Delete a value from an AVL tree.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#delete">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a href="flumotion.common.avltree-module.html#lookup" class="summary-sig-name">lookup</a>(<span class="summary-sig-arg">tree</span>,
<span class="summary-sig-arg">value</span>)</span><br />
Look up a node in an AVL tree.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#lookup">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a name="iterate"></a><span class="summary-sig-name">iterate</span>(<span class="summary-sig-arg">tree</span>)</span><br />
Iterate over an AVL tree, starting with the lowest-ordered value.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#iterate">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr>
<td><span class="summary-sig"><a name="iteratereversed"></a><span class="summary-sig-name">iteratereversed</span>(<span class="summary-sig-arg">tree</span>)</span><br />
Iterate over an AVL tree, starting with the highest-ordered value.</td>
<td align="right" valign="top">
<span class="codelink"><a href="flumotion.common.avltree-pysrc.html#iteratereversed">source code</a></span>
</td>
</tr>
</table>
</td>
</tr>
</table>
<!-- ==================== VARIABLES ==================== -->
<a name="section-Variables"></a>
<table class="summary" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
<td colspan="2" class="table-header">
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tr valign="top">
<td align="left"><span class="table-header">Variables</span></td>
<td align="right" valign="top"
><span class="options">[<a href="#section-Variables"
class="privatelink" onclick="toggle_private();"
>hide private</a>]</span></td>
</tr>
</table>
</td>
</tr>
<tr>
<td width="15%" align="right" valign="top" class="summary">
<span class="summary-type"> </span>
</td><td class="summary">
<a name="__package__"></a><span class="summary-name">__package__</span> = <code title="None">None</code><br />
hash(x)
</td>
</tr>
</table>
<!-- ==================== FUNCTION DETAILS ==================== -->
<a name="section-FunctionDetails"></a>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
<td colspan="2" class="table-header">
<table border="0" cellpadding="0" cellspacing="0" width="100%">
<tr valign="top">
<td align="left"><span class="table-header">Function Details</span></td>
<td align="right" valign="top"
><span class="options">[<a href="#section-FunctionDetails"
class="privatelink" onclick="toggle_private();"
>hide private</a>]</span></td>
</tr>
</table>
</td>
</tr>
</table>
<a name="height"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">height</span>(<span class="sig-arg">tree</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="flumotion.common.avltree-pysrc.html#height">source code</a></span>
</td>
</tr></table>
<p>Return the height of an AVL tree. Relies on the balance factors being
consistent.</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="insert"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">insert</span>(<span class="sig-arg">tree</span>,
<span class="sig-arg">value</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="flumotion.common.avltree-pysrc.html#insert">source code</a></span>
</td>
</tr></table>
<p>Insert a value into an AVL tree. Returns a tuple of (heightdifference,
tree). The original tree is unmodified.</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="delete"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">delete</span>(<span class="sig-arg">tree</span>,
<span class="sig-arg">value</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="flumotion.common.avltree-pysrc.html#delete">source code</a></span>
</td>
</tr></table>
<p>Delete a value from an AVL tree. Like <a
href="flumotion.common.avltree-module.html#insert"
class="link">insert</a>, returns a tuple of (heightdifference, tree). The
original tree is unmodified.</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<a name="lookup"></a>
<div>
<table class="details" border="1" cellpadding="3"
cellspacing="0" width="100%" bgcolor="white">
<tr><td>
<table width="100%" cellpadding="0" cellspacing="0" border="0">
<tr valign="top"><td>
<h3 class="epydoc"><span class="sig"><span class="sig-name">lookup</span>(<span class="sig-arg">tree</span>,
<span class="sig-arg">value</span>)</span>
</h3>
</td><td align="right" valign="top"
><span class="codelink"><a href="flumotion.common.avltree-pysrc.html#lookup">source code</a></span>
</td>
</tr></table>
<p>Look up a node in an AVL tree. Returns a node tuple or False if the
value was not found.</p>
<dl class="fields">
</dl>
</td></tr></table>
</div>
<br />
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
bgcolor="#a0c0ff" cellspacing="0">
<tr valign="middle">
<!-- Tree link -->
<th> <a
href="module-tree.html">Trees</a> </th>
<!-- Index link -->
<th> <a
href="identifier-index.html">Indices</a> </th>
<!-- Help link -->
<th> <a
href="help.html">Help</a> </th>
<th class="navbar" width="100%"></th>
</tr>
</table>
<table border="0" cellpadding="0" cellspacing="0" width="100%%">
<tr>
<td align="left" class="footer">
Generated by Epydoc 3.0.1 on Wed Aug 11 21:33:10 2010
</td>
<td align="right" class="footer">
<a target="mainFrame" href="http://epydoc.sourceforge.net"
>http://epydoc.sourceforge.net</a>
</td>
</tr>
</table>
<script type="text/javascript">
<!--
// Private objects are initially displayed (because if
// javascript is turned off then we want them to be
// visible); but by default, we want to hide them. So hide
// them unless we have a cookie that says to show them.
checkCookie();
// -->
</script>
</body>
</html>
