import math
from itertools import combinations

# ===============================
# Step 0: 数据结构与参数
# ===============================

# 空间实例格式：{'id':..., 'feature':..., 'x':..., 'y':...}
data = [
    {'id': 1, 'feature': 'Restaurant', 'x': 10, 'y': 20},
    {'id': 2, 'feature': 'Bar', 'x': 12, 'y': 18},
    {'id': 3, 'feature': 'Restaurant', 'x': 15, 'y': 25},
    {'id': 4, 'feature': 'Cafe', 'x': 11, 'y': 22},
    # 这里可填更多实例
]

# 用户偏好权重（手动定义）
user_weight = {
    'Restaurant': 0.9,
    'Bar': 0.8,
    'Cafe': 0.7,
    'Factory': 0.2
}

# 距离阈值
distance_threshold = 5.0

# 最小 Participation Index
min_PI = 0.3

# 输出 Top-K
top_k_patterns = 5

# ===============================
# Step 1: 计算邻居关系
# ===============================
def euclidean_distance(p1, p2):
    return math.sqrt((p1['x'] - p2['x'])**2 + (p1['y'] - p2['y'])**2)

def are_neighbors(inst1, inst2, d_thresh):
    return euclidean_distance(inst1, inst2) <= d_thresh

# 构建邻居字典
neighbors = {}
for inst in data:
    neighbors[inst['id']] = []
    for other in data:
        if inst['id'] != other['id'] and are_neighbors(inst, other, distance_threshold):
            neighbors[inst['id']].append(other['id'])

# ===============================
# Step 2: 挖掘 candidate co-location patterns
# ===============================
# 先获取所有 feature types
features = list(set([inst['feature'] for inst in data]))

# 生成 2-feature patterns
candidate_patterns = list(combinations(features, 2))
# 可以扩展到 k-feature patterns
# candidate_patterns = list(combinations(features, k))  # 可自行循环 k=2..max

# ===============================
# Step 3: 计算 Participation Index (PI)
# ===============================
def compute_PI(pattern, data, neighbors):
    """
    pattern: tuple of feature types, e.g., ('Restaurant', 'Bar')
    """
    PR_list = []
    for f in pattern:
        instances_f = [inst for inst in data if inst['feature'] == f]
        participating = 0
        for inst in instances_f:
            # 检查 inst 是否与 pattern 中其他 feature 有邻居
            flag = True
            for other_f in pattern:
                if other_f == f:
                    continue
                # 是否有 neighbor 属于 other_f
                has_neighbor = False
                for n_id in neighbors[inst['id']]:
                    n_inst = next((x for x in data if x['id'] == n_id), None)
                    if n_inst and n_inst['feature'] == other_f:
                        has_neighbor = True
                        break
                if not has_neighbor:
                    flag = False
                    break
            if flag:
                participating += 1
        PR = participating / len(instances_f) if len(instances_f) > 0 else 0
        PR_list.append(PR)
    PI = min(PR_list)
    return PI

# ===============================
# Step 4: 计算 Preference-aware Score
# ===============================
def compute_preference_weight(pattern, user_weight):
    weights = [user_weight.get(f, 0.5) for f in pattern]  # 默认0.5
    return sum(weights)/len(weights)

# ===============================
# Step 5: 挖掘 Preference-aware Patterns
# ===============================
results = []
for pattern in candidate_patterns:
    PI = compute_PI(pattern, data, neighbors)
    if PI < min_PI:
        continue
    PW = compute_preference_weight(pattern, user_weight)
    score = PI * PW
    results.append({'pattern': pattern, 'PI': PI, 'PW': PW, 'Score': score})

# 排序输出 Top-K
results.sort(key=lambda x: x['Score'], reverse=True)

print("Top Preference-aware Patterns:")
for r in results[:top_k_patterns]:
    print(f"Pattern: {r['pattern']}, PI: {r['PI']:.2f}, PW: {r['PW']:.2f}, Score: {r['Score']:.2f}")