Существует ли древовидная структура или алгоритм для перемещения по уровням в дереве? - PullRequest
Новая
       16

Существует ли древовидная структура или алгоритм для перемещения по уровням в дереве?

9 голосов
/ 18 августа 2011

У меня есть интересная проблема.

По сути, у меня есть список Предметов, где у каждого Предмета есть фиксированный набор метаданных разных значений.

Например:

  • Элемент 1: {Type = "Text", Автор = "Пользователь A", Дата редактирования = "03/03/2003"}
  • Элемент 2: {Type = "Таблица", Автор = "Пользователь A", Дата редактирования = "04/05/2006"}
  • Элемент 3: {Type = "Изображение", Автор = "Пользователь B", Дата редактирования = "05/05/2005"}
  • Элемент 4: {Type = "Text", Author = "Пользователь B", Дата редактирования = "05/07/2007"}

Теперь, в существующем виде, этот список предметов сведен и представлен в таблице.

Однако мы хотели бы найти способ, позволяющий пользователям просматривать его в дереве, но с дополнительной гибкостью, позволяющей им «поворачивать» порядок, в котором каждый из тегов метаданных появляется в дереве.

Итак, изначально это может выглядеть так: 

Items
+ Table
  + User A
    + 04/05/2006
      -> Item 2
    -> Item 2
  -> Item 2
+ Text
  + User A
    + 03/03/2003
      -> Item 1
    -> Item 1
  + User B
    + 05/07/2007
      -> Item 4
    -> Item 4
  -> Item 1
  -> Item 4
+ Image
  ..

Однако, предположим, что вместо этого пользователь хочет перевернуть его и просмотреть все элементы, связанные с конкретным пользователем: 

Items
+ User A
  + Text
  + Table
  -> Item 1
  -> Item 2
+ User B
  + Image
  + Text
  -> Item 3
  -> Item 4

и т. Д.

Надеюсь, это имеет смысл.

Итак, что меня интересует, так это то, что существует ли наилучший практический подход для достижения этого при низких затратах? Результат каждого 'flip / shuffle / pivot' красиво представлен в дереве, поэтому очевидно, что первая мысль состоит в том, что, когда пользователь запрашивает изменение представления, может быть сгенерировано новое дерево из списка элементов по мере необходимости. Однако я надеялся, что, возможно, найдется лучший способ, просто повернув одно дерево и т. Д.

Кроме того, это можно сделать вычислительно дешево в JavaScript в браузере пользователя, если бэкэнд просто вернет плоский список элементов?

Большое спасибо и всего наилучшего,

Джейми

Ответы [ 2 ]

1 голос
/ 19 августа 2011

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

Я думаю, вам следует подумать, что мир плоский (как в вашей таблице). База данных JavaScript может помочь (есть http://taffydb.com/)

Несмотря на то, что мир плоский, вы также можете создать функцию подписи, которая возвращает строку 

separator="µ"; //TODO Find something better
function signature() {
  return item.Type + separator + item.Author + separator + item.EditedDate;
}


assert(item1.signature == "TextµUser Aµ03/03/2003")

Затем вы сохраняете свои объекты в простом словаре, используя эту подпись в качестве ключа.

И затем вы можете выполнить регулярное выражение для ключей, чтобы получить нужные вам объекты. Сначала отредактируйте функцию подписи, чтобы она возвращала «([^ separator] +)», если соответствующее свойство элемента не определено. 

assert ({Type="Text"}.signature() == "Textµ[^µ]+µ[^µ]+")

function find(filterItem) {
  retval= = new generic.list();
  for (var k in dict.keys()) {
    if (k.match(regexp)) {
      retval.add(dcit[k]);
    }
  }
}

Я понятия не имею, быстрее ли это, чем просматривать все элементы.

0 голосов
/ 19 августа 2011

Чтобы решить эту проблему, я бы определил элемент списка, который выглядит примерно так: 

public class Item
{
    string NodeName {get; set;}
    string Url {get; set;}
    List<Item> Children {get; set;}
}

Это код на c #, но идея должна быть применима на любом языке, который поддерживаетобъекты.Теперь ваш список должен поддерживать только один тип списка, и это список Item, поэтому все, что вам нужно сделать, - это найти способ преобразовать ваши данные в такой список.

...