Облако тэгов на ASP.Net с кэшированием.

Одим хмурым воскресным утром мне было нечего делать и я решил попробовать написать свой вариант велосипеда – облако тэгов на ASP.Net. Результат получился довольно интересным, поэтому решил оформить его в виде статьи и выложить на Хабре.
Сразу оговорюсь – это результат всего-лишь полуторачасового кодинга, соответственно просьба не воспринимать его как полностью готовый контрол, а лишь как концепт, который еще можно развивать и развивать.


Итак. Что мы знаем об облаке тэгов? Облако тэгов это множество обьектов, которые описываются парой значений <КоличествоВхождений, Тэг>. В свою очередь, тэг представляет собой пару <ИмяТэга, Ссылка>. Итак, давайте создадим класс, который будет инкапсулировать в себе информацию о тэге.

  public class Tag
  {
    public string Text { get; set; }
    public string Href { get; set; }
  }

* This source code was highlighted with Source Code Highlighter.

Количество вхождений – скорее внешняя сущность по отношению к тэгу, поэтому мы отделим мухи от котлет и будем оперировать обьектом Pair<int, Tag>, который полностью аналогичен стандартному KeyValuePair<int, Tag> за исключением того, что свойства Key и Value не помечены как readonly. Это нам пригодится в будущем. Соответственно в свойстве Key у нас будет лежать количество вхождений тєга, по которому мы будем их ранжировать, а в Value собственно сам тэг.
Окей, давайте представим, что сайт каждую минуту посещает несколько сотен человек. Очевидно, что надо сделать так, чтоб генерация облака тэгов не занимала много времени. Тэги – довольно статическая вещь, вряд ли есть смысл генерировать облако чаще чем раз в N минут, они ведь не должны резко менятся. Значит нужно организовать кэширование. С учетом этих соображений напишем наш контрол.

  [ToolboxData("<{0}:TagCloudControl runat=server></{0}:TagCloudControl>")]
  public class TagCloudControl : WebControl
  {
    public const int MULTIPLIER = 2;
    public const int MIN_SIZE = 5;

    public event TagListDelegate TagsCollected;

    protected override void Render(HtmlTextWriter writer)
    {
      writer.AddAttribute(HtmlTextWriterAttribute.Align, "Center");
      writer.AddAttribute(HtmlTextWriterAttribute.Width, Width.ToString());
      writer.AddAttribute(HtmlTextWriterAttribute.Height, Height.ToString());
      writer.AddAttribute(HtmlTextWriterAttribute.Class, CssClass);
      writer.RenderBeginTag(HtmlTextWriterTag.Div);

      if (TagsCollected != null)
      {
        foreach (var tag in TagCloudCache.GetTags(TagsCollected))
        {
          writer.WriteEncodedText(" ");
          writer.AddStyleAttribute(HtmlTextWriterStyle.FontSize, string.Format("{0}px", (tag.Key+MIN_SIZE)*MULTIPLIER));
          writer.RenderBeginTag(HtmlTextWriterTag.Span);
          writer.AddAttribute(HtmlTextWriterAttribute.Href, tag.Value.Href);
          writer.RenderBeginTag(HtmlTextWriterTag.A);
          writer.WriteEncodedText(tag.Value.Text);
          writer.RenderEndTag();
        }
      }

      writer.RenderEndTag();
    }
  }

* This source code was highlighted with Source Code Highlighter.

Все очень просто – он наследуется от абстрактного класса WebControl и перегружает метод Render. Контролу передается параметром делегат

public delegate IEnumerable<Pair<int, Tag>> TagListDelegate();

* This source code was highlighted with Source Code Highlighter.

, который должен возвращать список пар с информацией о тэгах и их вхождениях. Кэш должен уметь смотреть на делегат и определять, нужно ли перегенерировать тэги. Итак, напишем класс, который будет инкапсулировать в себе информацию о генерированом облаке тэгов:

  public class TagCalculationInfo
  {
    public TimeSpan TimeOut { get; set; }
    public DateTime LastFiring { get; set; }
    public IEnumerable<Pair<int, Tag>> CalculatedTags { get; set; }

    public bool IsExpired
    {
      get
      {
        return DateTime.Now - LastFiring > TimeOut;
      }
    }
  }

* This source code was highlighted with Source Code Highlighter.

Класс содержит в себе таймаут – время жизни генерированого облака тэгов, в течении которого оно считается актуальным и не нуждается в перегенерировании. Свойство LastFiring – это время последней перегенерации тэгов. CalculatedTags – собственно тэги. Свойство IsExpired возвращает истину, когда с момента последней перегенерации тєгов проходит необходимое время. Теперь у нас есть все кирпичики, из которых можно построить кэш:

  public static class TagCloudCache
  {
    private const int TAG_GROUPS = 10;
    private static readonly TimeSpan DEFAULT_TIMEOUT = new TimeSpan(0, 1, 0);
    private static readonly Dictionary<string, TagCalculationInfo> m_Cache = new Dictionary<string, TagCalculationInfo>();

    public static IEnumerable<Pair<int, Tag>> GetTags(TagListDelegate target)
    {
      lock(m_Cache)
      {
        string key = target.GetKey();
        if (!m_Cache.ContainsKey(key))
        {
          m_Cache.Add(key, new TagCalculationInfo { TimeOut = DEFAULT_TIMEOUT });
        }
        var tagInfo = m_Cache[key];
        if(tagInfo.IsExpired)
        {
          tagInfo.CalculatedTags = RecalculateTags(target);
          tagInfo.LastFiring = DateTime.Now;
        }
        return tagInfo.CalculatedTags;
      }
    }
  }

* This source code was highlighted with Source Code Highlighter.

Итак, кэш совсем не сложен – в словаре m_Cache лежит информация об уже генерированных облаках тэгов. Когда контрол обращается к методу GetTags, мы проверяем, есть ли в кэше нужное облако – если нет, то добавляем пустую информацию. Далее смотрим, не устарело ли облако. Если устарело – обновляем его и устанавливаем время последней перегенерации на теперешнее. Здесь необходимо помнить, что нельзя использовать Dictionary<TagListDelegate, TagCalculationInfo> так как, к сожалению, метод Equals у делегата всегда возвращает false. Я решил использовать в качестве ключа строку, которая формируеся экстеншн методом:

    public static string GetKey(this TagListDelegate del)
    {
      return string.Format("{0}{1}{2}", ((MulticastDelegate)del.Target).Method.DeclaringType, ((MulticastDelegate)del.Target).Method.Name, ((MulticastDelegate)del.Target).Method.MethodHandle.Value);
    }

* This source code was highlighted with Source Code Highlighter.

Во время тестирования строка получалась вот такая: «TagCloud.TagCloud.TagCloudCacheGetTestTags84221360». К сожалению, так и не нашел в интернете информации о том, как правильно кешировать результаты методов в .Net, так что если кому-либо вздумается применять этот метод в реальном проекте – нужно хорошо подумать и погуглить, как это сделать.
Двигаемся дальше. Осталось лишь придумать, как будет вычислятся облако тэгов из входных данных. Еще два метода:

    private static IEnumerable<Pair<int, Tag>> RecalculateTags(TagListDelegate target)
    {
      var tags = new List<Pair<int, Tag>>(target());
      var max = tags.Max().Key;
      var min = tags.Min().Key;
      var clusters = new int[TAG_GROUPS];
      var step = (max - min)/(TAG_GROUPS - 1);
      for(int i = 0; i < TAG_GROUPS; i++)
      {
        clusters[i] = min + i*step;
      }
      foreach (var tag in tags)
      {
        tag.Key = FindClosestPosition(clusters, tag.Key);
      }
      tags.Sort();
      for(int i = 0; i < tags.Count; i += 2)
      {
        yield return tags[i];
      }
      for(int i = tags.Count % 2 == 0 ? tags.Count - 1 : tags.Count - 2; i >= 0; i -= 2)
      {
        yield return tags[i];
      }
    }

* This source code was highlighted with Source Code Highlighter.

Метод RecalculateTags разбивает тэги на группы – их будет 10. Находим минимальное и максимальное количество вхождений для тэга. Заполняем масив clusters значениями от минимума до максимума равномерно. Теперь для каждого тэга находим группу, к которой он находится ближе всего – массив clusters отсортирован, поэтому можно применить бинарный поиск:

    public static int FindClosestPosition(int[] arr, int key)
    {
      int h = arr.Length - 1, l = 0;
      while (h - l > 1)
      {
        int m = (h + l)/2;
        if(arr[m] > key)
        {
          h = m;
        }
        else
        {
          l = m;
        }
      }
      if(Math.Abs(arr[h] - key) < Math.Abs(arr[l] - key))
      {
        return h;
      }
      return l;
    }


* This source code was highlighted with Source Code Highlighter.

Теперь можно реализовать фичу – я хочу, чтоб размер тэгов возрастал от краев к середине облака. Сортируем тэги по группам. Возвращаем сначала все тэги, которые стоят на парных позициях от меньшего к большим, потом – те, которые стоят на непарных в обратном порядке.
Осталось немного — протестировать то, что получилось. Добавляем в файл с кодом страницы свойство, которое будет возвращать делегат с тестовыми тегами:

    public TagListDelegate TestTags
    {
      get
      {
        return TagCloudCache.GetTestTags;
      }
    }

* This source code was highlighted with Source Code Highlighter.

Регистрируем префикс для тегов:

<%@ Register Assembly="TagCloud" Namespace="TagCloud.TagCloud" TagPrefix="cc" %>

* This source code was highlighted with Source Code Highlighter.

И добавляем на страницу наше облако:

<cc:TagCloudControl runat="server" Name="TagCloudControl" OnTagsCollected="TestTags"/>

* This source code was highlighted with Source Code Highlighter.

Запускаем и получаем результат:

Конечно, контрол еще нуждается в тщательной доработке напильником, но основные принципы вряд ли изменятся.
Заранее извинясь за возможные ошибки – русский язык не родной. Ну и вообще, первая статья на Хабре :)

UPD: Контрол генерирует следующий HTML код:

<span style="font-size:10px;"><a href="#">PHP</a> <span style="font-size:10px;"><a href="#">Delphi</a> <span style="font-size:10px;"><a href="#">Internet</a> <span style="font-size:10px;"><a href="#">Nemerle</a> <span style="font-size:10px;"><a href="#">Outsourcing</a> <span style="font-size:10px;"><a href="#">VB.Net</a> <span style="font-size:10px;"><a href="#">JavaScript</a> <span style="font-size:12px;"><a href="#">C++</a> <span style="font-size:12px;"><a href="#">Apple</a> <span style="font-size:12px;"><a href="#">Intel</a> <span style="font-size:14px;"><a href="#">CLR</a> <span style="font-size:14px;"><a href="#">Java</a> <span style="font-size:16px;"><a href="#">WinForms</a> <span style="font-size:16px;"><a href="#">Web</a> <span style="font-size:18px;"><a href="#">WPF</a> <span style="font-size:22px;"><a href="#">AJAX</a> <span style="font-size:28px;"><a href="#">.Net</a> <span style="font-size:24px;"><a href="#">ASP.Net</a> <span style="font-size:20px;"><a href="#">C#</a> <span style="font-size:18px;"><a href="#">Google</a> <span style="font-size:16px;"><a href="#">MVC</a> <span style="font-size:14px;"><a href="#">Microsoft</a> <span style="font-size:14px;"><a href="#">SQL</a> <span style="font-size:12px;"><a href="#">SEO</a> <span style="font-size:12px;"><a href="#">jQuery</a> <span style="font-size:12px;"><a href="#">Habrahabr</a> <span style="font-size:12px;"><a href="#">Flash</a> <span style="font-size:10px;"><a href="#">Sun</a> <span style="font-size:10px;"><a href="#">LISP</a> <span style="font-size:10px;"><a href="#">Facebook</a> <span style="font-size:10px;"><a href="#">Perl</a> <span style="font-size:10px;"><a href="#">RSDN</a> <span style="font-size:10px;"><a href="#">Yandex</a></span>


* This source code was highlighted with Source Code Highlighter.