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
|
# cython: cdivision=True
# cython: boundscheck=False
# cython: wraparound=False
# An implementation of a complete binary tree in breadth first order adapted
# from https://github.com/jfuentess/sea2015/blob/master/binary_trees.h
from libc.math cimport pow, log2, floor
from bp._bp cimport SIZE_t
# it might be useful to use a pow2 lookup. static const c arrays are not
# allowed, so it might be useful to do it as a memoryview but should only be
# done following benching
cdef inline SIZE_t bt_is_root(SIZE_t v) nogil:
"""Is v the root"""
return v == 0
cdef inline SIZE_t bt_is_left_child(SIZE_t v) nogil:
"""Is v a left child of some node"""
return 0 if bt_is_root(v) else v % 2
cdef inline SIZE_t bt_is_right_child(SIZE_t v) nogil:
"""Is v a right child of some node"""
return 0 if bt_is_root(v) else 1 - (v % 2)
cdef inline SIZE_t bt_parent(SIZE_t v) nogil:
"""Get the index of the parent of v"""
return 0 if bt_is_root(v) else (v - 1) // 2
cdef inline SIZE_t bt_left_child(SIZE_t v) nogil:
"""Get the index of the left child of v"""
return 2 * v + 1
cdef inline SIZE_t bt_right_child(SIZE_t v) nogil:
"""Get the index of the right child of v"""
return 2 * v + 2
cdef inline SIZE_t bt_left_sibling(SIZE_t v) nogil:
"""Get the index of the left sibling of v"""
return v - 1
cdef inline SIZE_t bt_right_sibling(SIZE_t v) nogil:
"""Get the index of the right sibling of v"""
return v + 1
cdef inline SIZE_t bt_is_leaf(SIZE_t v, SIZE_t height) nogil:
"""Determine if v is a leaf"""
return <SIZE_t>(v >= pow(2, height) - 1)
cdef inline SIZE_t bt_node_from_left(SIZE_t pos, SIZE_t height) nogil:
"""Get the index from the left of a node at a given height"""
return <SIZE_t>pow(2, height) - 1 + pos
cdef inline SIZE_t bt_offset_from_left(SIZE_t v) nogil:
"""Get the position from left of a node at its level
This is the inverse of bt_node_from_left
"""
cdef double leftmost_check
if bt_is_root(v):
return 0
leftmost_check = log2(v + 1)
if leftmost_check == floor(leftmost_check):
return 0
return v - <SIZE_t>pow(2, floor(log2(v))) + 1
cdef inline SIZE_t bt_offset_from_right(SIZE_t v) nogil:
"""Get the position from right of a node at its level"""
cdef SIZE_t lvl = <SIZE_t>floor(log2(v + 1))
cdef SIZE_t n_nodes_at_lvl = <SIZE_t>pow(2, lvl)
return n_nodes_at_lvl - bt_offset_from_left(v) - 1
cdef inline SIZE_t bt_left_leaf(SIZE_t v, SIZE_t height) nogil:
"""Determine the index of a nodes left most leaf"""
cdef SIZE_t left_tip = <SIZE_t>pow(2, height) - 1
cdef SIZE_t block_size
if bt_is_root(v):
return left_tip
block_size = <SIZE_t>pow(2, height - floor(log2(v + 1)))
return left_tip + (block_size * bt_offset_from_left(v))
cdef inline SIZE_t bt_right_leaf(SIZE_t v, SIZE_t height) nogil:
"""Determine the index of a nodes right most leaf"""
cdef SIZE_t right_tip = <SIZE_t>pow(2, height + 1) - 2
cdef SIZE_t block_size
if bt_is_root(v):
return right_tip
block_size = <SIZE_t>pow(2, height - floor(log2(v + 1)))
return right_tip - (block_size * bt_offset_from_right(v))
|
