1	#Region "Microsoft.VisualBasic::07da39e5070630eee10fd652e7ee005a, 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