• API
• FAQ
• Tools
• Archive
daily pastebin goal
30%
SHARE
TWEET

# Untitled

a guest Mar 22nd, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class WebpagePriorityQueue:
2.     def __init__(self, q, indexes):
3.         #The query is saved as a list of strings
4.         self.query = parsequery(q)
5.         self.count = len(indexes)
6.         self.data = self.heapify(self.query, indexes)
7.
8.     def peek(self):
9.         return self.data[0]
10.
11.     #Extracts the top value and shifts down
12.     def poll(self):
13.         if self.count <= 0:
14.             print('Cannot pop from empty queue')
15.         else:
16.             #Returns the 'top' item of the heap, which
17.             #is the first element of the list
18.             ret = self.data[0]
19.             #Temporarily assigns the last element of the
21.             self.data[0] = self.data[self.count - 1]
22.             self.count -= 1
23.             #Shifts the new head element down the heap
24.             self.shiftdown(0)
25.             return ret
26.
27.     #Builds a maxheap using the provided indexes and
28.     #the query phrase
29.     def heapify(self, indexes):
30.         tempheap = []
31.         for index in indexes:
32.             #Append the index and ensure the heap is valid
33.             tempheap.append(index)
34.             self.shiftup(self.count - 1)
35.         return tempheap
36.
37.     #Both shifts are based on the priority value of the index
38.     #calculated with the given query
39.     def shiftup(self, i):
40.         #Calculate the index of the parent node
41.         p = (i - 1) >> 1 #Use shift to perform integer division
42.         #While the child priority is higher than the parent's:
43.         while i > 0 and calcPrio(self.query, self.data[p]) < calcPrio(self.query, self.data[i]):
44.             #Swap the child and parent and move upwards
45.             temp = self.data[i]
46.             self.data[i] = self.data[p]
47.             self.data[p] = temp
48.             #Repeat shiftup on the parent node
49.             i = p
50.             #Calculate the new parent index value
51.             p = (i - 1) >> 1
52.
53.     def shiftdown(self, i):
54.         #Calculate the index of the left child node
55.         c = 2 * i + 1
56.         while c < self.count:
57.             if c + 1 < self.count and calcPrio(self.query, self.data[c+1]) > calcPrio(self.query, self.data[c]):
58.                 #If left child is not larger, checks if right child exists
59.                 c += 1
60.             if calcPrio(self.query, self.data[i]) >= calcPrio(self.query, self.data[c]):
61.                 #If current has higher priority than the child, stop
62.                 break
63.             #Swap the current node with the larger of its child nodes
64.             temp = self.data[i]
65.             self.data[i] = self.data[c]
66.             self.data[c] = temp
67.             #Repeat shiftdown on the child node
68.             i = j
69.             #Calculate the new child index value
70.             j = 2 * i + 1
71.
72.     #This should be done using an in-place heapsort, but
73.     #I did not have the time :(
74.     def reheap(self, newQ):
75.         #Parses the new query and builds a new maxheap
76.         self.query = parsequery(newQ)
77.         return self.heapify(self.query, self.data)
78.
79. #Helper function which parses the query string
80. #into a list of strings delimited by spaces
81. def parsequery(string):
82.     allowed = 'abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ'
83.     tempS = ''
84.     for c in string:
85.         if c in allowed:
86.             tempS += c.lower()
87.     return tempS.split(' ')
88.
89. #Helper function that calculates the priority
90. #of an WebPageIndex object based on a query
91. def calcPrio(query, index):
92.     p = 0
93.     for q in query:
94.         p += index.getCount(q)
95.     return p
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top