from typing import List, Dict, Set, Optional
from datetime import datetime

class BPlusNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []
        self.next = None

class BPlusTree:
    def __init__(self, order):
        self.root = BPlusNode(True)
        self.order = order
        
    def insert(self, key, value):
        if len(self.root.keys) == (2 * self.order) - 1:
            new_root = BPlusNode(False)
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root
        self._insert_non_full(self.root, key, value)
    
    def _split_child(self, parent, index):
        order = self.order
        child = parent.children[index]
        new_child = BPlusNode(child.leaf)
        
        parent.keys.insert(index, child.keys[order - 1])
        parent.children.insert(index + 1, new_child)
        
        new_child.keys = child.keys[order:]
        child.keys = child.keys[:order - 1]
        
        if not child.leaf:
            new_child.children = child.children[order:]
            child.children = child.children[:order]
        
        if child.leaf:
            new_child.next = child.next
            child.next = new_child
    
    def _insert_non_full(self, node, key, value):
        i = len(node.keys) - 1
        
        if node.leaf:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            node.keys.insert(i + 1, (key, value))
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            
            if len(node.children[i].keys) == (2 * self.order) - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key, value)
    
    def search(self, key, partial_match=False):
        return self._search(self.root, key, partial_match)
    
    def _search(self, node, key, partial_match=False):
        results = []
        i = 0
        while i < len(node.keys) and (not partial_match and key > node.keys[i][0] or 
              partial_match and not key(node.keys[i][0])):
            i += 1
            
        if node.leaf:
            while i < len(node.keys) and (partial_match and key(node.keys[i][0])):
                results.append(node.keys[i])
                i += 1
            return results if partial_match else (
                [node.keys[i]] if i < len(node.keys) and node.keys[i][0] == key else []
            )
        else:
            if partial_match:
                results.extend(self._search(node.children[i], key, partial_match))
                while i < len(node.keys) and key(node.keys[i][0]):
                    results.extend(self._search(node.children[i + 1], key, partial_match))
                    i += 1
                return results
            else:
                return self._search(node.children[i], key, partial_match)

class ExtendibleHash:
    def __init__(self, bucket_size):
        self.global_depth = 1
        self.bucket_size = bucket_size
        self.directory = [[] for _ in range(2)]
        self.local_depth = [1, 1]
    
    def _hash(self, key):
        return hash(key) & ((1 << self.global_depth) - 1)
    
    def insert(self, key, value):
        h = self._hash(key)
        bucket = self.directory[h]
        
        if len(bucket) < self.bucket_size:
            bucket.append((key, value))
            return
        
        if self.local_depth[h] == self.global_depth:
            self._double_directory()
        
        self._split_bucket(h)
        self.insert(key, value)
    
    def _double_directory(self):
        self.global_depth += 1
        old_size = len(self.directory)
        self.directory.extend(self.directory)
        self.local_depth.extend(self.local_depth)
    
    def _split_bucket(self, bucket_index):
        local_depth = self.local_depth[bucket_index]
        bit_mask = 1 << local_depth
        
        zero_bucket = []
        one_bucket = []
        for key, value in self.directory[bucket_index]:
            if hash(key) & bit_mask:
                one_bucket.append((key, value))
            else:
                zero_bucket.append((key, value))
        
        for i in range(len(self.directory)):
            if i & ((1 << local_depth) - 1) == bucket_index:
                if i & bit_mask:
                    self.directory[i] = one_bucket
                else:
                    self.directory[i] = zero_bucket
                self.local_depth[i] = local_depth + 1
    
    def search(self, key):
        h = self._hash(key)
        bucket = self.directory[h]
        return [item for item in bucket if item[0] == key]

class Database:
    def __init__(self):
        self.movie_id_index = BPlusTree(3)
        self.director_name_index = BPlusTree(3)
        self.purchase_date_index = BPlusTree(3)
        
        self.movie_hash = ExtendibleHash(5)
        self.director_hash = ExtendibleHash(5)
        self.purchase_hash = ExtendibleHash(5)
        
        self._load_sample_data()
    
    def _load_sample_data(self):
        movies = [
            ("St_Sp_0101", "Jaws_SP_0101", "Steven Spielberg", "Jaws"),
            ("St_Sp_0101", "E.T_SP_0102", "Steven Spielberg", "E.T."),
            ("Ch_No_0203", "Ince_CN_0203", "Christopher Nolan", "Inception"),
            ("Ch_No_0203", "Inte_CN_0204", "Christopher Nolan", "Interstellar"),
            ("Qu_Ta_0305", "Pulp_QT_0305", "Quentin Tarantino", "Pulp Fiction"),
            ("Qu_Ta_0305", "Kill_QT_0306", "Quentin Tarantino", "Kill Bill"),
            ("Ma_Sc_0407", "Good_MS_0407", "Martin Scorsese", "Goodfellas")
        ]
        
        for movie in movies:
            self.movie_id_index.insert(movie[1], movie)
            self.movie_hash.insert(movie[1], movie)
            self.director_name_index.insert(movie[2], movie)
    
        purchases = [
            ("Jaws_SP_0101", "Jaws", "2023-09-07", 3),
            ("E.T_SP_0102", "E.T.", "2023-09-05", 2),
            ("Ince_CN_0203", "Inception", "2023-09-06", 4),
            ("Inte_CN_0204", "Interstellar", "2023-09-06", 1),
            ("Pulp_QT_0305", "Pulp Fiction", "2023-09-05", 3),
            ("Kill_QT_0306", "Kill Bill", "2023-09-07", 2),
            ("Good_MS_0407", "Goodfellas", "2023-09-07", 1)
        ]
        
        for purchase in purchases:
            self.purchase_date_index.insert(purchase[2], purchase)
            self.purchase_hash.insert(purchase[0], purchase)

    def query1(self):
        """Movies purchased after Sep 5th with ≤ 2 copies"""
        print("\nQuery 1 result:")
        
        # Hash implementation
        hash_results = []
        for bucket in self.purchase_hash.directory:
            for _, purchase in bucket:
                if purchase[2] > "2023-09-05" and purchase[3] <= 2:
                    hash_results.append(purchase[0])
        
        # B+ Tree implementation
        def date_filter(date_str):
            return date_str > "2023-09-05"
        
        btree_results = []
        purchases = self.purchase_date_index.search(date_filter, partial_match=True)
        for _, purchase in purchases:
            if purchase[3] <= 2:
                btree_results.append(purchase[0])
        
        print(f"Hash: {sorted(hash_results)}")
        print(f"B+ Tree: {sorted(btree_results)}")

    def query2(self):
        """Movies by directors whose names begin with 'S', 'C', or 'M'"""
        print("\nQuery 2 result:")
        
        # Hash implementation
        hash_results = []
        for bucket in self.movie_hash.directory:
            for _, movie in bucket:
                if movie[2][0] in ['S', 'C', 'M']:
                    hash_results.append((movie[3], movie[2]))
        
        # B+ Tree implementation
        def name_filter(name):
            return name[0] in ['S', 'C', 'M']
        
        btree_results = []
        movies = self.director_name_index.search(name_filter, partial_match=True)
        for _, movie in movies:
            btree_results.append((movie[3], movie[2]))
        
        print(f"Hash: {sorted(hash_results)}")
        print(f"B+ Tree: {sorted(btree_results)}")

    def query3(self):
        """Directors with movies purchased across all dates"""
        print("\nQuery 3 result:")
        
        # Hash implementation
        hash_dates = set()
        hash_director_dates = {}
        
        for bucket in self.purchase_hash.directory:
            for _, purchase in bucket:
                hash_dates.add(purchase[2])
                movie_info = self.movie_hash.search(purchase[0])
                if movie_info:
                    director = movie_info[0][1][2]
                    if director not in hash_director_dates:
                        hash_director_dates[director] = set()
                    hash_director_dates[director].add(purchase[2])
        
        hash_results = [director for director, dates in hash_director_dates.items() 
                       if dates == hash_dates]
        
        # B+ Tree implementation
        btree_dates = set()
        btree_director_dates = {}
        
        purchases = self.purchase_date_index.search(lambda x: True, partial_match=True)
        for _, purchase in purchases:
            btree_dates.add(purchase[2])
            movie_info = self.movie_id_index.search(purchase[0])
            if movie_info:
                director = movie_info[0][1][2]
                if director not in btree_director_dates:
                    btree_director_dates[director] = set()
                btree_director_dates[director].add(purchase[2])
        
        btree_results = [director for director, dates in btree_director_dates.items() 
                        if dates == btree_dates]
        
        print(f"Hash: {sorted(hash_results)}")
        print(f"B+ Tree: {sorted(btree_results)}")

    def query4(self):
        """Directors of movies with only one copy"""
        print("\nQuery 4 result:")
        
        # Hash implementation
        hash_results = []
        for bucket in self.purchase_hash.directory:
            for _, purchase in bucket:
                if purchase[3] == 1:
                    movie_info = self.movie_hash.search(purchase[0])
                    if movie_info:
                        hash_results.append(movie_info[0][1][2])
        
        # B+ Tree implementation
        btree_results = []
        purchases = self.purchase_date_index.search(lambda x: True, partial_match=True)
        for _, purchase in purchases:
            if purchase[3] == 1:
                movie_info = self.movie_id_index.search(purchase[0])
                if movie_info:
                    btree_results.append(movie_info[0][1][2])
        
        print(f"Hash: {sorted(hash_results)}")
        print(f"B+ Tree: {sorted(btree_results)}")

def main():
    db = Database()
    db.query1()  # Movies purchased after Sep 5th with ≤ 2 copies
    db.query2()  # Movies by directors with names starting with S, C, or M
    db.query3()  # Directors with movies purchased across all dates
    db.query4()  # Directors of movies with only one copy

if __name__ == "__main__":
    main()

  File "c:\Users\auspi\OneDrive\Desktop\DBMS Labs\Lab 09\query_optimization.py", line 47, in _insert_non_full
    while i >= 0 and key < node.keys[i]:
                     ^^^^^^^^^^^^^^^^^^
TypeError: '<' not supported between instances of 'str' and 'tuple'