sorting_searching_algorithms.py

"""
排序与搜索算法模块
Sorting and Searching Algorithms Module
"""

from heap_structure_app import HeapOptimizedNetwork
from collections import defaultdict


def quicksort(arr, key_func=None, ascending=True):
    """
    快速排序算法
    QuickSort algorithm
    
    Args:
        arr (list): 待排序数组 Array to sort
        key_func (function): 提取比较键的函数 Function to extract comparison key
        ascending (bool): 是否升序排列 Whether to sort in ascending order
        
    Returns:
        list: 排序后的数组 Sorted array
    """
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    pivot_key = key_func(pivot) if key_func else pivot
    
    # 分割数组 Partition array
    if key_func:
        if ascending:
            left = [x for x in arr if key_func(x) < pivot_key]
            right = [x for x in arr if key_func(x) > pivot_key]
        else:
            left = [x for x in arr if key_func(x) > pivot_key]
            right = [x for x in arr if key_func(x) < pivot_key]
        middle = [x for x in arr if key_func(x) == pivot_key]
    else:
        if ascending:
            left = [x for x in arr if x < pivot_key]
            right = [x for x in arr if x > pivot_key]
        else:
            left = [x for x in arr if x > pivot_key]
            right = [x for x in arr if x < pivot_key]
        middle = [x for x in arr if x == pivot_key]
    
    # 递归排序并合并 Recursively sort and merge
    return quicksort(left, key_func, ascending) + middle + quicksort(right, key_func, ascending)


def mergesort(arr, key_func=None, ascending=True):
    """
    归并排序算法
    MergeSort algorithm
    
    Args:
        arr (list): 待排序数组 Array to sort
        key_func (function): 提取比较键的函数 Function to extract comparison key
        ascending (bool): 是否升序排列 Whether to sort in ascending order
        
    Returns:
        list: 排序后的数组 Sorted array
    """
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = mergesort(arr[:mid], key_func, ascending)
    right = mergesort(arr[mid:], key_func, ascending)
    
    # 合并两个有序数组 Merge two sorted arrays
    return merge(left, right, key_func, ascending)


def merge(left, right, key_func=None, ascending=True):
    """
    合并两个有序数组
    Merge two sorted arrays
    
    Args:
        left (list): 左侧有序数组 Left sorted array
        right (list): 右侧有序数组 Right sorted array
        key_func (function): 提取比较键的函数 Function to extract comparison key
        ascending (bool): 是否升序排列 Whether to sort in ascending order
        
    Returns:
        list: 合并后的有序数组 Merged sorted array
    """
    result = []
    i = j = 0
    
    # 比较并合并 Compare and merge
    while i < len(left) and j < len(right):
        left_val = key_func(left[i]) if key_func else left[i]
        right_val = key_func(right[j]) if key_func else right[j]
        
        if (left_val <= right_val) if ascending else (left_val >= right_val):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 添加剩余元素 Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result


def binary_search(arr, target, key_func=None):
    """
    二分查找算法
    Binary search algorithm
    
    Args:
        arr (list): 已排序数组 Sorted array
        target: 目标值 Target value
        key_func (function): 提取比较键的函数 Function to extract comparison key
        
    Returns:
        int: 目标值索引，若未找到返回-1 Index of target value, -1 if not found
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        mid_val = key_func(arr[mid]) if key_func else arr[mid]
        
        if mid_val == target:
            return mid
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1


def binary_search_range(arr, target, key_func=None):
    """
    二分查找变种：查找目标值的范围
    Binary search variant: find range of target values
    
    Args:
        arr (list): 已排序数组 Sorted array
        target: 目标值 Target value
        key_func (function): 提取比较键的函数 Function to extract comparison key
        
    Returns:
        tuple: (起始索引, 结束索引) 或 (-1, -1) (start index, end index) or (-1, -1)
    """
    def find_first():
        left, right = 0, len(arr) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            mid_val = key_func(arr[mid]) if key_func else arr[mid]
            
            if mid_val == target:
                result = mid
                right = mid - 1  # 继续向左找 Keep searching to the left
            elif mid_val < target:
                left = mid + 1
            else:
                right = mid - 1
        return result
    
    def find_last():
        left, right = 0, len(arr) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            mid_val = key_func(arr[mid]) if key_func else arr[mid]
            
            if mid_val == target:
                result = mid
                left = mid + 1  # 继续向右找 Keep searching to the right
            elif mid_val < target:
                left = mid + 1
            else:
                right = mid - 1
        return result
    
    first = find_first()
    if first == -1:
        return (-1, -1)
    
    last = find_last()
    return (first, last)


def linear_search_multiple_conditions(arr, conditions):
    """
    多条件线性搜索
    Multi-condition linear search
    
    Args:
        arr (list): 搜索数组 Search array
        conditions (dict): 条件字典，键为属性名，值为条件值 Condition dictionary
        
    Returns:
        list: 满足条件的元素列表 List of elements satisfying conditions
    """
    result = []
    
    for item in arr:
        match = True
        for attr, condition_val in conditions.items():
            item_val = getattr(item, attr) if hasattr(item, attr) else item.get(attr) if isinstance(item, dict) else item[attr] if isinstance(item, list) else item
            if item_val != condition_val:
                match = False
                break
        
        if match:
            result.append(item)
    
    return result


from influence_propagation import InfluencePropagationNetwork
from community_detection import CommunityDetectionNetwork
from shortest_path_centrality import ShortestPathNetwork
from topological_sort import TopologicalSortNetwork


class SortingSearchingNetwork(
    ShortestPathNetwork, 
    CommunityDetectionNetwork, 
    InfluencePropagationNetwork, 
    TopologicalSortNetwork, 
    HeapOptimizedNetwork
):
    """
    具有排序和搜索功能的社交网络类（继承所有功能）
    Social Network class with sorting and searching capabilities (inherits all functionalities)
    """
    
    def sort_users_by_attribute(self, attribute, ascending=True):
        """
        按指定属性对用户进行排序
        Sort users by a specific attribute
        
        Args:
            attribute (str): 属性名 Attribute name
            ascending (bool): 是否升序 Whether to sort in ascending order
            
        Returns:
            list: 排序后的用户列表 Sorted list of users
        """
        users_with_attrs = []
        
        for user_id in range(self.n):
            user_info = self.quick_user_lookup(user_id)
            if user_info and attribute in user_info:
                users_with_attrs.append((user_info[attribute], user_id))
        
        # 使用快速排序 Sort using quicksort
        sorted_users = quicksort(users_with_attrs, key_func=lambda x: x[0], ascending=ascending)
        
        return [(user_id, attr_val) for attr_val, user_id in sorted_users]
    
    def search_users_by_conditions(self, conditions):
        """
        根据条件搜索用户
        Search users by conditions
        
        Args:
            conditions (dict): 搜索条件 Search conditions
            
        Returns:
            list: 满足条件的用户列表 List of users satisfying conditions
        """
        # 构建用户列表 Build user list
        users_list = []
        for user_id in range(self.n):
            user_info = self.quick_user_lookup(user_id)
            if user_info:
                user_info['id'] = user_id
                users_list.append(user_info)
        
        # 执行多条件搜索 Perform multi-condition search
        return linear_search_multiple_conditions(users_list, conditions)
    
    def get_users_by_follower_range(self, min_followers, max_followers):
        """
        获取粉丝数在指定范围内的用户
        Get users with follower count in specified range
        
        Args:
            min_followers (int): 最小粉丝数 Minimum followers
            max_followers (int): 最大粉丝数 Maximum followers
            
        Returns:
            list: 满足条件的用户列表 List of users satisfying conditions
        """
        result = []
        for user_id in range(self.n):
            user_info = self.quick_user_lookup(user_id)
            if user_info:
                followers = user_info.get('followers', 0)
                if min_followers <= followers <= max_followers:
                    result.append((user_id, followers))
        
        return result


# 测试示例
if __name__ == "__main__":
    print("排序与搜索算法 - 示例运行")
    print("Sorting and Searching Algorithms - Example Run")
    
    # 创建一个排序搜索网络 Create a sorting-searching network
    network = SortingSearchingNetwork(10, directed=True, storage_type="adj_list")
    
    # 添加一些边 Add some edges
    edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
    for u, v in edges:
        network.add_edge(u, v)
    
    # 设置一些用户的属性 Set attributes for some users
    import random
    for i in range(10):
        network.user_attributes[i]['followers'] = random.randint(50, 500)
        network.user_attributes[i]['posts'] = random.randint(10, 100)
        network.user_info_table.insert(i, network.user_attributes[i])
    
    print(f"添加了 {len(edges)} 条边并设置了用户属性")
    print(f"Added {len(edges)} edges and set user attributes")
    
    # 测试排序功能 Test sorting functionality
    sorted_by_followers = network.sort_users_by_attribute('followers', ascending=False)
    print(f"\n按粉丝数降序排列前5: {sorted_by_followers[:5]}")
    print(f"Top 5 by followers (descending): {sorted_by_followers[:5]}")
    
    sorted_by_posts = network.sort_users_by_attribute('posts', ascending=True)
    print(f"按发帖数升序排列前5: {sorted_by_posts[:5]}")
    print(f"Top 5 by posts (ascending): {sorted_by_posts[:5]}")
    
    # 测试搜索功能 Test search functionality
    users_in_range = network.get_users_by_follower_range(100, 300)
    print(f"\n粉丝数在100-300之间的用户: {users_in_range}")
    print(f"Users with followers between 100-300: {users_in_range}")
    
    # 测试条件搜索 Test conditional search
    conditions = {'followers': lambda x: x > 200}
    filtered_users = network.search_users_by_conditions({'followers': 250})  # 精确匹配
    print(f"粉丝数等于250的用户: {filtered_users}")
    print(f"Users with exactly 250 followers: {filtered_users}")
    
    # 测试排序算法 Test sorting algorithms
    print(f"\n测试排序算法...")
    print(f"Testing sorting algorithms...")
    
    test_data = [(random.randint(1, 100), chr(65+i)) for i in range(10)]
    print(f"原始数据: {test_data}")
    print(f"Original data: {test_data}")
    
    # 快速排序 QuickSort
    sorted_qs = quicksort(test_data[:], key_func=lambda x: x[0], ascending=True)
    print(f"快速排序结果: {sorted_qs}")
    print(f"QuickSort result: {sorted_qs}")
    
    # 归并排序 MergeSort
    sorted_ms = mergesort(test_data[:], key_func=lambda x: x[0], ascending=True)
    print(f"归并排序结果: {sorted_ms}")
    print(f"MergeSort result: {sorted_ms}")
    
    # 测试搜索算法 Test search algorithms
    print(f"\n测试搜索算法...")
    print(f"Testing search algorithms...")
    
    sorted_data = sorted(test_data, key=lambda x: x[0])
    print(f"已排序数据: {sorted_data}")
    print(f"Sorted data: {sorted_data}")
    
    # 二分查找 Binary search
    target = sorted_data[5][0]  # 取中间元素的值 Take value of middle element
    index = binary_search(sorted_data, target, key_func=lambda x: x[0])
    print(f"查找值 {target} 的索引: {index}")
    print(f"Index of value {target}: {index}")
    
    # 二分查找范围 Binary search range
    duplicate_val = sorted_data[2][0]  # 取一个可能重复的值 Take a value that might be duplicated
    range_result = binary_search_range(sorted_data, duplicate_val, key_func=lambda x: x[0])
    print(f"值 {duplicate_val} 的范围: {range_result}")
    print(f"Range of value {duplicate_val}: {range_result}")
    
    # 线性搜索多条件 Linear search with multiple conditions
    sample_users = [
        {'id': 0, 'followers': 100, 'posts': 20},
        {'id': 1, 'followers': 200, 'posts': 30},
        {'id': 2, 'followers': 150, 'posts': 25}
    ]
    conditions = {'followers': 150, 'posts': 25}
    result = linear_search_multiple_conditions(sample_users, conditions)
    print(f"满足条件 followers=150, posts=25 的用户: {result}")
    print(f"Users with followers=150, posts=25: {result}")