File: AVL_TREE.html

package info (click to toggle)
lisaac 1%3A0.13.1-3
  • links: PTS
  • area: main
  • in suites: squeeze
  • size: 15,276 kB
  • ctags: 6,396
  • sloc: ansic: 242,479; xml: 635; lisp: 333; makefile: 116; sh: 73; asm: 38
file content (141 lines) | stat: -rwxr-xr-x 11,335 bytes parent folder | download | duplicates (2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
<!DOCTYPE HTML SYSTEM>
<!-- Generated by Lisaac shorter / html style -->
<html>
<head>
<title>
Lisaac prototype interface
</title>
</head>
<body BGCOLOR="#FFFFFF">

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Header</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">name</font></strong> := <a href="AVL_TREE.html"><font color="#008000">AVL_TREE</font></a>[<font color="#008000">E</font>];
  
  <br><font FACE="Sans-serif" color="#000000"><B> Definition of a mathematical set of comparable objects. All common</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> operations on mathematical sets are available.</B></font>

<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Insert</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">parent_avl_constants</font></strong>:<a href="AVL_CONSTANTS.html"><font color="#008000">AVL_CONSTANTS</font></a> := 

<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">debug_string</font></strong>:<a href="STRING.html"><font color="#008000">STRING</font></a> <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">count</font></strong>:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a>;
  
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong>
  
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> Adding and removing:</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">remove</font></strong> e:<font color="#008000">E</font> <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_remove</font></strong> e:<font color="#008000">E</font> <-
  
<br><br><strong><font color="#A020F0">Section</font></strong> <font color="#008000">SELF</font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">root</font></strong>:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>];

  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">rebalance</font></strong>:<a href="BOOLEAN.html"><font color="#008000">BOOLEAN</font></a>;

  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">item_memory</font></strong>:<font color="#008000">E</font>;

  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">set_value_and_key</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">set_value</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_do_insert</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">do_insert</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">left_grown</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">right_grown</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_do_remove</font></strong> (n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>],e:<font color="#008000">E</font>) :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">do_remove</font></strong> (n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>],e:<font color="#008000">E</font>) :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">remove_right</font></strong> (n1, n2:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>]) :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">left_shrunk</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">right_shrunk</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] :<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">exchange_and_discard</font></strong> (n1, n2:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>]) <-
  	
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">clear_nodes</font></strong> node:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">node_height</font></strong> node:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] :<a href="INTEGER.html"><font color="#008000">INTEGER</font></a> <-
  		
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong>		
  
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> Looking and searching:</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">has</font></strong> e:<font color="#008000">E</font> :<a href="BOOLEAN.html"><font color="#008000">BOOLEAN</font></a> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Is element `e' in the set?</font></strong></em>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_has</font></strong> e:<font color="#008000">E</font> :<a href="BOOLEAN.html"><font color="#008000">BOOLEAN</font></a> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Is element `e' in the set?</font></strong></em>
  
<br><br><strong><font color="#A020F0">Section</font></strong> <font color="#008000">SELF</font>
  
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> Iterating internals:</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">build_map</font></strong> <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">map</font></strong>:<a href="FAST_ARRAY.html"><font color="#008000">FAST_ARRAY</font></a>[<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>]];
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Elements in a row for iteration. See `build_map'.</font></strong></em>

  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">map_dirty</font></strong>:<a href="BOOLEAN.html"><font color="#008000">BOOLEAN</font></a>;
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  True when the map needs to be built again for the iterators. </font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  See `build_map'.</font></strong></em>

<br><br><strong><font color="#A020F0">Section</font></strong> <font color="#008000">SELF</font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">new_node</font></strong>:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">a_new_node</font></strong>:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  	
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">discard_node</font></strong> n:<a href="AVL_TREE_NODE.html"><font color="#008000">AVL_TREE_NODE</font></a>[<font color="#008000">E</font>] <-
  	
  <br><font FACE="Sans-serif" color="#000000"><B>	</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> invariant</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
<br><font FACE="Sans-serif" color="#000000"><B>  [</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>    -? {map != NULL};</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>    -? {(! map_dirty) -> (map.count = count)};</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>    -? {(count > 0) -> ((root != NULL) && {root.count = count})};</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>  ]</B></font>

</body>
</html>