Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/bin/python3
- import math
- import os
- import random
- import re
- import sys
- class Tree:
- class Node:
- def __init__(self, key, value):
- self.key = key
- self.value = {value}
- self.left = None
- self.right = None
- self.high = 1
- def __init__(self):
- self.root = None
- self.size = 0
- @staticmethod
- def get_height(current):
- if current is None:
- return 0
- return current.high
- def get_difference(self, current):
- if current is None:
- return 0
- return self.get_height(current.left) - self.get_height(current.right)
- def get(self, key):
- current = self.root
- while current is not None:
- if key < current.key:
- current = current.left
- elif key > current.key:
- current = current.right
- else:
- return current
- return None
- def put(self, key, value):
- self.root = self.__put(self.root, key, value)
- def __put(self, current, key, value):
- if current is None:
- self.size += 1
- return Tree.Node(key, value)
- if key < current.key:
- current.left = self.__put(current.left, key, value)
- elif key > current.key:
- current.right = self.__put(current.right, key, value)
- else:
- current.value.add(value)
- current.high = 1 + max(self.get_height(current.left), self.get_height(current.right))
- difference = self.get_difference(current)
- if difference > 1 and key < current.left.key:
- return self.right_rotation(current)
- elif difference < -1 and key > current.right.key:
- return self.left_rotation(current)
- elif difference > 1 and key > current.left.key:
- current.left = self.left_rotation(current.left)
- return self.right_rotation(current)
- elif difference < -1 and key < current.right.key:
- current.right = self.right_rotation(current.right)
- return self.left_rotation(current)
- return current
- def right_rotation(self, node):
- change = node.left
- tree = change.right
- change.right = node
- node.left = tree
- node.high = max(self.get_height(node.left), self.get_height(node.right)) + 1
- change.high = max(self.get_height(change.left), self.get_height(change.right)) + 1
- return change
- def left_rotation(self, node):
- change = node.right
- tree = change.left
- change.left = node
- node.right = tree
- node.high = max(self.get_height(node.left), self.get_height(node.right)) + 1
- change.high = max(self.get_height(change.left), self.get_height(change.right)) + 1
- return change
- def __print(self, current):
- if current is not None:
- print(current.key, end=" ")
- self.__print(current.left)
- self.__print(current.right)
- def print(self):
- self.__print(self.root)
- def _get_all_elements(self, current):
- if current is None:
- return 0
- return len(current.value) + self._get_all_elements(current.left) + self._get_all_elements(current.right)
- def get_all_elements(self):
- return self._get_all_elements(self.root)
- def print_increase(self, node):
- if node is None:
- return
- self.print_increase(node.left)
- print (node.key, end=" ")
- self.print_increase(node.right)
- class InvertedIndex:
- def __init__(self):
- self.docs = Tree()
- def index_document(self, document, document_id):
- words = document.split()
- for element in words:
- self.docs.put(element, document_id)
- def search(self, words):
- element = self.docs.get(words)
- if element is None:
- return {-1}
- return element.value
- def get_average_documents_per_key(self):
- if self.docs.size == 0:
- return 0
- all_words = self.docs.get_all_elements()
- return round(all_words / self.docs.size)
- def get_keys(self):
- self.docs.print_increase(self.docs.root)
- def main():
- num_documents = int(input().strip())
- a = InvertedIndex()
- documents = []
- for _ in range(num_documents):
- documents_item = input()
- documents.append(documents_item)
- a.index_document(documents_item, _)
- num_queries = int(input().strip())
- queries = []
- for _ in range(num_queries):
- queries_item = input()
- queries.append(queries_item)
- p = input()
- for word in queries:
- positions = a.search(word)
- print(*positions)
- print(a.get_average_documents_per_key())
- if p == "print_keys":
- a.get_keys()
- if __name__ == "__main__":
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement