1 #Region "Microsoft.VisualBasic::fa8b3cc7757e3eebf57da0d645f14bb2, Microsoft.VisualBasic.Core\ComponentModel\Algorithm\BinaryTree\AVLSupports.vb"
2
3     ' Author:
4     
5     '       asuka (amethyst.asuka@gcmodeller.org)
6     '       xie (genetics@smrucc.org)
7     '       xieguigang (xie.guigang@live.com)
8     
9     ' Copyright (c) 2018 GPL3 Licensed
10     
11     
12     ' GNU GENERAL PUBLIC LICENSE (GPL3)
13     
14     
15     ' This program is free software: you can redistribute it and/or modify
16     ' it under the terms of the GNU General Public License as published by
17     ' the Free Software Foundation, either version 3 of the License, or
18     ' (at your option) any later version.
19     
20     ' This program is distributed in the hope that it will be useful,
21     ' but WITHOUT ANY WARRANTY; without even the implied warranty of
22     ' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23     ' GNU General Public License for more details.
24     
25     ' You should have received a copy of the GNU General Public License
26     ' along with this program. If not, see <http://www.gnu.org/licenses/>.
27
28
29
30     ' /********************************************************************************/
31
32     ' Summaries:
33
34     '     Module AVLSupports
35     
36     '         Function: height, RotateLL, RotateLR, RotateRL, RotateRR
37     
38     '         Sub: PutHeight
39     
40     
41     ' /********************************************************************************/
42
43 #End Region
44
45 Imports System.Runtime.CompilerServices
46
47 Namespace ComponentModel.Algorithm.BinaryTree
48
49     ''' <summary>
50     ''' Binary tree balance helper
51     ''' </summary>
52     Public Module AVLSupports
53
54         <Extension>
55         Public Function RotateLL(Of K, V)(node As BinaryTree(Of K, V)) As BinaryTree(Of K, V)
56             Dim top = node.Left
57
58             node.Left = top.Right
59             top.Right = node
60
61             node.PutHeight
62             top.PutHeight
63
64             Return top
65         End Function
66
67         <Extension>
68         Public Function RotateRR(Of K, V)(node As BinaryTree(Of K, V)) As BinaryTree(Of K, V)
69             Dim top = node.Right
70
71             node.Right = top.Left
72             top.Left = node
73
74             Call node.PutHeight
75             Call top.PutHeight
76
77             Return top
78         End Function
79
80         <Extension>
81         Public Function RotateLR(Of K, V)(node As BinaryTree(Of K, V)) As BinaryTree(Of K, V)
82             node.Left = node.Left.RotateRR
83             Return node.RotateLL
84         End Function
85
86         <Extension>
87         Public Function RotateRL(Of K, V)(node As BinaryTree(Of K, V)) As BinaryTree(Of K, V)
88             node.Right = node.Right.RotateLL
89             Return node.RotateRR
90         End Function
91
92         <MethodImpl(MethodImplOptions.AggressiveInlining)>
93         <Extension>
94         Friend Function height(Of K, V)(node As BinaryTree(Of K, V)) As Double
95             Return If(node Is Nothing, -1, CDbl(node!height))
96         End Function
97
98         <MethodImpl(MethodImplOptions.AggressiveInlining)>
99         <Extension>
100         Friend Sub PutHeight(Of K, V)(node As BinaryTree(Of K, V))
101             node.SetValue("height", Math.Max(node.Left.height, node.Right.height) + 1)
102         End Sub
103     End Module
104 End Namespace