SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 71 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
  20.             #list as the head
  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. OK, I Understand
 
Top