class AutoCompleteUtils {

  @VisibleForTesting
  static List<AutocompleteSuggestion> limitSuggestionsByType(
      List<AutocompleteSuggestion> orderedSuggestions,
      int maxSuggestions,
      int maxSuggestionsPerType) {
    if (orderedSuggestions.size() <= maxSuggestions) {
      return orderedSuggestions;
    }

    Map<SuggestionType, Integer> suggestionTypeCounts = new TreeMap<>();

    List<AutocompleteSuggestion> limitedSuggestions = new ArrayList<>();
    List<AutocompleteSuggestion> leftOverSuggestions = new ArrayList<>();

    for (AutocompleteSuggestion suggestion : orderedSuggestions) {
      if (limitedSuggestions.size() == maxSuggestions) {
        return limitedSuggestions;
      }

      Integer count = suggestionTypeCounts.getOrDefault(suggestion.getSuggestionType(), 0);

      if (count < maxSuggestionsPerType) {
        limitedSuggestions.add(suggestion);
        suggestionTypeCounts.put(suggestion.getSuggestionType(), count + 1);
      } else {
        leftOverSuggestions.add(suggestion);
      }
    }

    int suggestionsToAdd = maxSuggestions - limitedSuggestions.size();

    if (suggestionsToAdd > 0) {
      // add remaining suggestions from leftovers
      limitedSuggestions.addAll(
          leftOverSuggestions.subList(
              0, Integer.min(suggestionsToAdd, leftOverSuggestions.size())));
    }

    return limitedSuggestions;
  }

}