class RatingMatrix {
  private ratings: Map<string, Map<string, number>> = new Map();
  private users: Set<string> = new Set();
  private items: Set<string> = new Set();

  addRating(userId: string, itemId: string, rating: number): void {
    if (!this.ratings.has(userId)) {
      this.ratings.set(userId, new Map());
    }
    this.ratings.get(userId)!.set(itemId, rating);
    this.users.add(userId);
    this.items.add(itemId);
  }

  getRating(userId: string, itemId: string): number | null {
    const userRatings = this.ratings.get(userId);
    return userRatings ? userRatings.get(itemId) || null : null;
  }

  getUserRatings(userId: string): Map<string, number> {
    return this.ratings.get(userId) || new Map();
  }

  getItemRatings(itemId: string): Map<string, number> {
    const itemRatings: Map<string, number> = new Map();
    for (const [userId, userRatings] of this.ratings) {
      const rating = userRatings.get(itemId);
      if (rating !== undefined) {
        itemRatings.set(userId, rating);
      }
    }
    return itemRatings;
  }

  getUsers(): string[] {
    return Array.from(this.users);
  }

  getItems(): string[] {
    return Array.from(this.items);
  }

  getAverageRating(): number {
    let total = 0;
    let count = 0;

    for (const userRatings of this.ratings.values()) {
      for (const rating of userRatings.values()) {
        total += rating;
        count += 1;
      }
    }

    return count > 0 ? total / count : 0;
  }
}

class UserBasedCollaborativeFiltering {
  private matrix: RatingMatrix;
  private similarityMatrix: Map<string, Map<string, number>> = new Map();

  constructor(matrix: RatingMatrix) {
    this.matrix = matrix;
    this.computeSimilarities();
  }

  private computeSimilarities(): void {
    const users = this.matrix.getUsers();

    for (let i = 0; i < users.length; i += 1) {
      for (let j = i + 1; j < users.length; j += 1) {
        const similarity = this.cosineSimilarity(users[i], users[j]);

        if (!this.similarityMatrix.has(users[i])) {
          this.similarityMatrix.set(users[i], new Map());
        }
        if (!this.similarityMatrix.has(users[j])) {
          this.similarityMatrix.set(users[j], new Map());
        }

        this.similarityMatrix.get(users[i])!.set(users[j], similarity);
        this.similarityMatrix.get(users[j])!.set(users[i], similarity);
      }
    }
  }

  private cosineSimilarity(user1: string, user2: string): number {
    const ratings1 = this.matrix.getUserRatings(user1);
    const ratings2 = this.matrix.getUserRatings(user2);

    const commonItems = new Set([...ratings1.keys()].filter((item) => ratings2.has(item)));

    if (commonItems.size === 0) return 0;

    let dotProduct = 0;
    let norm1 = 0;
    let norm2 = 0;

    for (const item of commonItems) {
      const r1 = ratings1.get(item)!;
      const r2 = ratings2.get(item)!;
      dotProduct += r1 * r2;
      norm1 += r1 * r1;
      norm2 += r2 * r2;
    }

    norm1 = Math.sqrt(norm1);
    norm2 = Math.sqrt(norm2);

    return norm1 > 0 && norm2 > 0 ? dotProduct / (norm1 * norm2) : 0;
  }

  predictRating(userId: string, itemId: string, k: number = 5): number {
    const userRatings = this.matrix.getUserRatings(userId);
    if (userRatings.has(itemId)) {
      return userRatings.get(itemId)!;
    }

    const similarities: Array<{ user: string; similarity: number }> = [];
    for (const [otherUser, similarity] of this.similarityMatrix.get(userId) || []) {
      const otherUserRatings = this.matrix.getUserRatings(otherUser);
      if (otherUserRatings.has(itemId)) {
        similarities.push({ user: otherUser, similarity });
      }
    }

    similarities.sort((a, b) => b.similarity - a.similarity);
    const topK = similarities.slice(0, k);

    if (topK.length === 0) return this.matrix.getAverageRating();

    let weightedSum = 0;
    let totalWeight = 0;

    for (const { user, similarity } of topK) {
      const rating = this.matrix.getUserRatings(user).get(itemId)!;
      weightedSum += similarity * rating;
      totalWeight += Math.abs(similarity);
    }

    return totalWeight > 0 ? weightedSum / totalWeight : this.matrix.getAverageRating();
  }

  recommendItems(userId: string, n: number = 10): Array<{ itemId: string; predictedRating: number }> {
    const userRatings = this.matrix.getUserRatings(userId);
    const allItems = this.matrix.getItems();
    const unratedItems = allItems.filter((item) => !userRatings.has(item));

    const predictions: Array<{ itemId: string; predictedRating: number }> = [];

    for (const itemId of unratedItems) {
      const predictedRating = this.predictRating(userId, itemId);
      predictions.push({ itemId, predictedRating });
    }

    predictions.sort((a, b) => b.predictedRating - a.predictedRating);
    return predictions.slice(0, n);
  }
}

class ItemBasedCollaborativeFiltering {
  private matrix: RatingMatrix;
  private similarityMatrix: Map<string, Map<string, number>> = new Map();

  constructor(matrix: RatingMatrix) {
    this.matrix = matrix;
    this.computeSimilarities();
  }

  private computeSimilarities(): void {
    const items = this.matrix.getItems();

    for (let i = 0; i < items.length; i += 1) {
      for (let j = i + 1; j < items.length; j += 1) {
        const similarity = this.cosineSimilarity(items[i], items[j]);

        if (!this.similarityMatrix.has(items[i])) {
          this.similarityMatrix.set(items[i], new Map());
        }
        if (!this.similarityMatrix.has(items[j])) {
          this.similarityMatrix.set(items[j], new Map());
        }

        this.similarityMatrix.get(items[i])!.set(items[j], similarity);
        this.similarityMatrix.get(items[j])!.set(items[i], similarity);
      }
    }
  }

  private cosineSimilarity(item1: string, item2: string): number {
    const ratings1 = this.matrix.getItemRatings(item1);
    const ratings2 = this.matrix.getItemRatings(item2);

    const commonUsers = new Set([...ratings1.keys()].filter((user) => ratings2.has(user)));

    if (commonUsers.size === 0) return 0;

    let dotProduct = 0;
    let norm1 = 0;
    let norm2 = 0;

    for (const user of commonUsers) {
      const r1 = ratings1.get(user)!;
      const r2 = ratings2.get(user)!;
      dotProduct += r1 * r2;
      norm1 += r1 * r1;
      norm2 += r2 * r2;
    }

    norm1 = Math.sqrt(norm1);
    norm2 = Math.sqrt(norm2);

    return norm1 > 0 && norm2 > 0 ? dotProduct / (norm1 * norm2) : 0;
  }

  predictRating(userId: string, itemId: string, k: number = 5): number {
    const userRatings = this.matrix.getUserRatings(userId);
    if (userRatings.has(itemId)) {
      return userRatings.get(itemId)!;
    }

    const similarities: Array<{ item: string; similarity: number }> = [];
    for (const [otherItem, similarity] of this.similarityMatrix.get(itemId) || []) {
      if (userRatings.has(otherItem)) {
        similarities.push({ item: otherItem, similarity });
      }
    }

    similarities.sort((a, b) => b.similarity - a.similarity);
    const topK = similarities.slice(0, k);

    if (topK.length === 0) return this.matrix.getAverageRating();

    let weightedSum = 0;
    let totalWeight = 0;

    for (const { item, similarity } of topK) {
      const rating = userRatings.get(item)!;
      weightedSum += similarity * rating;
      totalWeight += Math.abs(similarity);
    }

    return totalWeight > 0 ? weightedSum / totalWeight : this.matrix.getAverageRating();
  }

  recommendItems(userId: string, n: number = 10): Array<{ itemId: string; predictedRating: number }> {
    const userRatings = this.matrix.getUserRatings(userId);
    const allItems = this.matrix.getItems();
    const unratedItems = allItems.filter((item) => !userRatings.has(item));

    const predictions: Array<{ itemId: string; predictedRating: number }> = [];

    for (const itemId of unratedItems) {
      const predictedRating = this.predictRating(userId, itemId);
      predictions.push({ itemId, predictedRating });
    }

    predictions.sort((a, b) => b.predictedRating - a.predictedRating);
    return predictions.slice(0, n);
  }
}

class MatrixFactorization {
  private matrix: RatingMatrix;
  private userFactors: Map<string, number[]> = new Map();
  private itemFactors: Map<string, number[]> = new Map();
  private k: number; // 隐因子维度
  private learningRate: number;
  private regularization: number;
  private epochs: number;

  constructor(matrix: RatingMatrix, k: number = 10, learningRate: number = 0.01, regularization: number = 0.1, epochs: number = 100) {
    this.matrix = matrix;
    this.k = k;
    this.learningRate = learningRate;
    this.regularization = regularization;
    this.epochs = epochs;
    this.initializeFactors();
  }

  private initializeFactors(): void {
    const users = this.matrix.getUsers();
    const items = this.matrix.getItems();

    for (const user of users) {
      this.userFactors.set(
        user,
        Array.from({ length: this.k }, () => Math.random()),
      );
    }

    for (const item of items) {
      this.itemFactors.set(
        item,
        Array.from({ length: this.k }, () => Math.random()),
      );
    }
  }

  train(): void {
    for (let epoch = 0; epoch < this.epochs; epoch += 1) {
      this.trainEpoch();
    }
  }

  private trainEpoch(): void {
    const users = this.matrix.getUsers();
    const items = this.matrix.getItems();

    for (const user of users) {
      for (const item of items) {
        const actualRating = this.matrix.getRating(user, item);
        if (actualRating !== null) {
          const predictedRating = this.predictRating(user, item);
          const error = actualRating - predictedRating;

          const userFactor = this.userFactors.get(user)!;
          const itemFactor = this.itemFactors.get(item)!;

          for (let i = 0; i < this.k; i += 1) {
            const userGrad = error * itemFactor[i] - this.regularization * userFactor[i];
            const itemGrad = error * userFactor[i] - this.regularization * itemFactor[i];

            userFactor[i] += this.learningRate * userGrad;
            itemFactor[i] += this.learningRate * itemGrad;
          }
        }
      }
    }
  }

  predictRating(userId: string, itemId: string): number {
    const userFactor = this.userFactors.get(userId);
    const itemFactor = this.itemFactors.get(itemId);

    if (!userFactor || !itemFactor) return this.matrix.getAverageRating();

    let prediction = 0;
    for (let i = 0; i < this.k; i += 1) {
      prediction += userFactor[i] * itemFactor[i];
    }

    return prediction;
  }

  recommendItems(userId: string, n: number = 10): Array<{ itemId: string; predictedRating: number }> {
    const userRatings = this.matrix.getUserRatings(userId);
    const allItems = this.matrix.getItems();
    const unratedItems = allItems.filter((item) => !userRatings.has(item));

    const predictions: Array<{ itemId: string; predictedRating: number }> = [];

    for (const itemId of unratedItems) {
      const predictedRating = this.predictRating(userId, itemId);
      predictions.push({ itemId, predictedRating });
    }

    predictions.sort((a, b) => b.predictedRating - a.predictedRating);
    return predictions.slice(0, n);
  }
}

class ContentBasedRecommender {
  private itemTags: Map<string, Set<string>> = new Map();
  private userPreferences: Map<string, Map<string, number>> = new Map();

  addItemTags(itemId: string, tags: string[]): void {
    this.itemTags.set(itemId, new Set(tags));
  }

  addUserRating(userId: string, itemId: string, rating: number): void {
    if (!this.userPreferences.has(userId)) {
      this.userPreferences.set(userId, new Map());
    }

    const preferences = this.userPreferences.get(userId)!;
    const tags = this.itemTags.get(itemId);

    if (tags) {
      for (const tag of tags) {
        const current = preferences.get(tag) || 0;
        preferences.set(tag, current + rating);
      }
    }
  }

  recommendItems(userId: string, items: string[], n: number = 10): Array<{ itemId: string; score: number }> {
    const preferences = this.userPreferences.get(userId);
    if (!preferences) return [];

    const scoredItems: Array<{ itemId: string; score: number }> = [];

    for (const itemId of items) {
      const tags = this.itemTags.get(itemId);
      if (!tags) continue;

      let score = 0;
      for (const tag of tags) {
        score += preferences.get(tag) || 0;
      }

      scoredItems.push({ itemId, score });
    }

    scoredItems.sort((a, b) => b.score - a.score);
    return scoredItems.slice(0, n);
  }
}