-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathOpenListInFavorOfSmallerG.py
executable file
·107 lines (89 loc) · 4.17 KB
/
OpenListInFavorOfSmallerG.py
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
from Node import Node
import random
class OpenListInFavorOfSmallerG:
def __init__(self):
self.heap = [Node(-9, -9)]
self.current_size = 0
def is_empty(self):
if self.current_size == 0:
return True
return False
def parent_pos(self, child_pos):
return (int(child_pos / 2))
def left_child_pos(self, parent_pos):
return int(parent_pos * 2)
def right_child_pos(self, parent_pos):
return int((parent_pos * 2) + 1)
def is_leaf(self, pos):
if pos <= int(self.current_size / 2):
return False
return True
def swap(self, parent_pos, child_pos):
self.heap[parent_pos], self.heap[child_pos] = self.heap[child_pos], self.heap[parent_pos]
def swim(self, child_pos):
while self.heap[self.parent_pos(child_pos)].f >= self.heap[child_pos].f and child_pos > 1:
if self.heap[self.parent_pos(child_pos)].f == self.heap[child_pos].f:
if self.heap[self.parent_pos(child_pos)].g > self.heap[child_pos].g:
self.swap(self.parent_pos(child_pos), child_pos)
break
elif self.heap[self.parent_pos(child_pos)].g < self.heap[child_pos].g:
break
elif self.heap[self.parent_pos(child_pos)].g == self.heap[child_pos].g:
intt = random.randint(0, 1)
if intt == 0:
self.swap(self.parent_pos(child_pos), child_pos)
break
self.swap(self.parent_pos(child_pos), child_pos)
child_pos = self.parent_pos(child_pos)
def sink(self, parent_pos):
while ((self.is_leaf(parent_pos) is False) and (
self.right_child_pos(parent_pos) <= self.current_size and self.heap[parent_pos].f > self.heap[
self.left_child_pos(parent_pos)].f or
(self.right_child_pos(parent_pos) <= self.current_size and self.heap[parent_pos].f > self.heap[
self.right_child_pos(parent_pos)].f))):
k = self.heap[self.left_child_pos(parent_pos)].f > self.heap[self.right_child_pos(parent_pos)].f
if k is False:
if self.heap[self.left_child_pos(parent_pos)].f == self.heap[self.right_child_pos(parent_pos)].f:
if self.heap[self.left_child_pos(parent_pos)].g > self.heap[self.right_child_pos(parent_pos)].g:
k = True
elif self.heap[self.left_child_pos(parent_pos)].g == self.heap[self.right_child_pos(parent_pos)].g:
intt = random.randint(0, 1)
if intt == 0: k = True
if k is True:
if self.heap[parent_pos].f > self.heap[self.right_child_pos(parent_pos)].f:
self.swap(parent_pos, self.right_child_pos(parent_pos))
parent_pos = self.right_child_pos(parent_pos)
if self.is_leaf(parent_pos) is True:
break
elif k is False:
if self.heap[parent_pos].f > self.heap[self.left_child_pos(parent_pos)].f:
self.swap(parent_pos, self.left_child_pos(parent_pos))
parent_pos = self.left_child_pos(parent_pos)
if self.is_leaf(parent_pos) is True:
break
def insert(self, element):
if element in self.heap:
for i in self.heap:
if i.x == element.x and i.y == element.y:
self.sink(self.heap.index(i))
self.swim(self.heap.index(i))
else:
self.heap.append(element)
self.current_size += 1
self.swim(self.current_size)
def contains(self, element):
if element in self.heap:
return True
return False
def get_min(self):
return self.heap[1]
def del_min(self):
min = self.heap[1]
self.swap(1, self.current_size)
self.heap.pop()
self.current_size -= 1
self.sink(1)
return min
def print(self):
for i in range(1, self.current_size + 1):
print(self.heap[i].f, "(", self.heap[i].x, ", ", self.heap[i].y, ")")