Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.98 KB | None | 0 0
  1. #!/bin/python3
  2.  
  3. import math
  4. import os
  5. import random
  6. import re
  7. import sys
  8.  
  9.  
  10. class Tree:
  11.     class Node:
  12.         def __init__(self, key, value):
  13.             self.key = key
  14.             self.value = {value}
  15.             self.left = None
  16.             self.right = None
  17.             self.high = 1
  18.  
  19.     def __init__(self):
  20.         self.root = None
  21.         self.size = 0
  22.  
  23.  
  24.     @staticmethod
  25.     def get_height(current):
  26.         if current is None:
  27.             return 0
  28.         return current.high
  29.  
  30.     def get_difference(self, current):
  31.         if current is None:
  32.             return 0
  33.         return self.get_height(current.left) - self.get_height(current.right)
  34.  
  35.     def get(self, key):
  36.         current = self.root
  37.         while current is not None:
  38.             if key < current.key:
  39.                 current = current.left
  40.             elif key > current.key:
  41.                 current = current.right
  42.             else:
  43.                 return current
  44.         return None
  45.  
  46.     def put(self, key, value):
  47.         self.root = self.__put(self.root, key, value)
  48.  
  49.     def __put(self, current, key, value):
  50.         if current is None:
  51.             self.size += 1
  52.             return Tree.Node(key, value)
  53.  
  54.         if key < current.key:
  55.             current.left = self.__put(current.left, key, value)
  56.         elif key > current.key:
  57.             current.right = self.__put(current.right, key, value)
  58.         else:
  59.             current.value.add(value)
  60.  
  61.         current.high = 1 + max(self.get_height(current.left), self.get_height(current.right))
  62.         difference = self.get_difference(current)
  63.  
  64.         if difference > 1 and key < current.left.key:
  65.             return self.right_rotation(current)
  66.         elif difference < -1 and key > current.right.key:
  67.             return self.left_rotation(current)
  68.         elif difference > 1 and key > current.left.key:
  69.             current.left = self.left_rotation(current.left)
  70.             return self.right_rotation(current)
  71.         elif difference < -1 and key < current.right.key:
  72.             current.right = self.right_rotation(current.right)
  73.             return self.left_rotation(current)
  74.         return current
  75.    
  76.     def right_rotation(self, node):
  77.         change = node.left
  78.         tree = change.right
  79.  
  80.         change.right = node
  81.         node.left = tree
  82.  
  83.         node.high = max(self.get_height(node.left), self.get_height(node.right)) + 1
  84.         change.high = max(self.get_height(change.left), self.get_height(change.right)) + 1
  85.         return change
  86.    
  87.     def left_rotation(self, node):
  88.         change = node.right
  89.         tree = change.left
  90.  
  91.         change.left = node
  92.         node.right = tree
  93.  
  94.         node.high = max(self.get_height(node.left), self.get_height(node.right)) + 1
  95.         change.high = max(self.get_height(change.left), self.get_height(change.right)) + 1
  96.         return change
  97.    
  98.     def __print(self, current):
  99.         if current is not None:
  100.             print(current.key, end=" ")
  101.             self.__print(current.left)
  102.             self.__print(current.right)
  103.            
  104.     def print(self):
  105.         self.__print(self.root)
  106.        
  107.     def _get_all_elements(self, current):
  108.         if current is None:
  109.             return 0
  110.         return len(current.value) + self._get_all_elements(current.left) + self._get_all_elements(current.right)
  111.    
  112.     def get_all_elements(self):
  113.         return self._get_all_elements(self.root)
  114.    
  115.     def print_increase(self, node):
  116.         if node is None:
  117.             return
  118.         self.print_increase(node.left)
  119.         print (node.key, end=" ")
  120.         self.print_increase(node.right)
  121.  
  122.  
  123. class InvertedIndex:
  124.     def __init__(self):
  125.         self.docs = Tree()
  126.        
  127.     def index_document(self, document, document_id):
  128.         words = document.split()
  129.         for element in words:
  130.             self.docs.put(element, document_id)
  131.  
  132.     def search(self, words):
  133.         element = self.docs.get(words)
  134.         if element is None:
  135.             return {-1}
  136.         return element.value
  137.    
  138.     def get_average_documents_per_key(self):
  139.         if self.docs.size == 0:
  140.             return 0
  141.         all_words = self.docs.get_all_elements()
  142.         return round(all_words / self.docs.size)
  143.    
  144.     def get_keys(self):
  145.         self.docs.print_increase(self.docs.root)
  146.  
  147.  
  148.        
  149. def main():
  150.     num_documents = int(input().strip())
  151.     a = InvertedIndex()
  152.     documents = []
  153.  
  154.     for _ in range(num_documents):
  155.         documents_item = input()
  156.         documents.append(documents_item)
  157.         a.index_document(documents_item, _)
  158.  
  159.     num_queries = int(input().strip())
  160.     queries = []
  161.  
  162.     for _ in range(num_queries):
  163.         queries_item = input()
  164.         queries.append(queries_item)
  165.     p = input()
  166.     for word in queries:
  167.         positions = a.search(word)
  168.         print(*positions)
  169.  
  170.    
  171.     print(a.get_average_documents_per_key())
  172.    
  173.     if p == "print_keys":
  174.         a.get_keys()
  175.  
  176.  
  177. if __name__ == "__main__":
  178.     main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement