-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbst.f90
129 lines (109 loc) · 2.57 KB
/
bst.f90
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
module bst_mod
use posting_mod
implicit none
type bst_node
type(bst_node), pointer :: left, right
character(len=:), allocatable :: key
type(posting) :: post
end type bst_node
type bst
type(bst_node), pointer :: root
integer :: size
contains
procedure :: initialize
procedure :: insert
procedure :: print
procedure :: write
end type bst
private :: initialize, insert, print, write
contains
subroutine initialize(tree)
class(bst) :: tree
tree%size = 0
nullify(tree%root)
end subroutine initialize
subroutine insert(tree, key, docid)
class(bst) :: tree
character(len=*), intent(in) :: key
integer :: docid
type(bst_node), pointer :: p
tree%size = tree%size + 1
if (.NOT. associated(tree%root)) then
call make_node(tree%root, key, docid)
end if
p => tree%root
do
!print *, "a"
if (key < p%key) then
!print *, "b"
if (.NOT. associated(p%left)) then
call make_node(p%left, key, docid)
return
end if
p => p%left
else if (key > p%key) then
!print *, "b"
if (.NOT. associated(p%right)) then
call make_node(p%right, key, docid)
return
end if
p => p%right
else
!print *, "b"
call p%post%append(docid)
tree%size = tree%size - 1
return
end if
end do
end subroutine insert
subroutine make_node(node, key, docid)
type(bst_node), pointer, intent(inout) :: node
character(len=*), intent(in) :: key
integer, intent(in) :: docid
allocate(node)
nullify(node%left)
nullify(node%right)
node%key = key
call node%post%initialize()
call node%post%append(docid)
end subroutine make_node
subroutine print(tree)
class(bst) :: tree
call print_inorder(tree%root)
end subroutine print
recursive subroutine print_inorder(node)
type(bst_node), pointer :: node
if (.NOT. associated(node)) then
return
end if
call print_inorder(node%left)
print *, node%key
call node%post%print()
call print_inorder(node%right)
end subroutine print_inorder
subroutine write(tree)
class(bst) :: tree
write(10) tree%size
call write_key_inorder(tree%root)
call write_post_inorder(tree%root)
end subroutine write
recursive subroutine write_key_inorder(node)
type(bst_node), pointer :: node
if (.NOT. associated(node)) then
return
end if
call write_key_inorder(node%left)
write(10) len(node%key)
write(10) node%key
call write_key_inorder(node%right)
end subroutine write_key_inorder
recursive subroutine write_post_inorder(node)
type(bst_node), pointer :: node
if (.NOT. associated(node)) then
return
end if
call write_post_inorder(node%left)
call node%post%write()
call write_post_inorder(node%right)
end subroutine write_post_inorder
end module bst_mod