1

Тема: Маніпуляції з деревом елементів

Вітаю.
Нехай у нас є набір елементів, котрі можуть бути двох типів:
1. Простий елемент
2. Секція, що може містити інші елементи

Відпочатку всі елементи знаходяться на рівні 1, але якщо ми беремо простий елемент, і вставляємо його в секцію, то цей простий елемент отримує рівень ( рівень_секції + 1 ), і тепер ми можемо розкривати, або згортати цю секцію, що, відповідно, показує та приховує простий елемент, котрий в ній знаходиться.

І ось деякі правила:

1. Секція може містити як прості елементи, так і інші секції, що також можуть мати вкладені елементи
2. Ми можемо перетягувати елементи з одного рівня, на інший, наприклад, пернести простий елемент, що знаходиться в секції, на один рівень з самою секцією, після чого та секція вже не містить той елемент, і, відповідно, не може приховувати, або згортати його.
3. Ми можемо перетягувати з рівня на рівень самі секції, і тоді сама секція і її вкладені елементи переміщуються разом з нею, при цьому їхні індекси та рівні змінюються відповідно.
4. Ми можемо додавати нові прості елементи, і секції.
5. Ми можемо видаляти прості елементи і секції, при цьому, якщо ми видаляємо секцію, то й всі елементи і секції, котрі вона містить, теж видаляються.

Код, котрий будує дерево, отримує на вхід простий масив з елементів, кожен з котрих має позначку - секція це, чи простий елемент, та значення рівня.
Наприклад, у нас є такий масив

Секція: рівень 1
Елемент: рівень 2
Елемент: рівень 2
Елемент: рівень 2
Секція: рівень 2
Елемент: рівень 3
Елемент: рівень 3
Секція: рівень 1
Секція: рівень 2
Елемент: рівень 3
Елемент: рівень 3
Елемент: рівень 1
Елемент: рівень 1

Ми побачимо ось таку картину, коли розкриємо всі секції.
(прикріпив).
На початку (коли секції згорнуті) мій код побудує ось такий масив

Елемент дерева: Секція, рівень: 1, дітки: [Елемент, рівень 2(x3), Секція, рівень: 2, дітки: [Елемент, рівень 3(x2)]]
Елемент дерева: Секція, рівень 1, дітки: [Секція, рівень: 2, дітки: [Елемент: рівень 3(x2)]]
Елемент дерева: Елемент, рівень 1
Елемент дерева: Елемент, рівень 1

і поверне мені його назад, і з нього я створю 4 елементи на сторінці, з котрими користувач зможе взаємодіяти.

Як воно працює зараз:

Нехай у нас є невелика кількість секцій, кожна з котрих містить велику кількість елементів включаючи інші секції, що теж містять інші елементи. Ми розгортуємо всі секції, і наше дерево показує нам всі можливі елементи.
Коли я розгортаю певний елемент, то я додаю його ID в Set.
Потім, скажімо, ми хочемо додати ще один елемент в наше дерево. На вхід коду, що будує дерево, надходить новий масив з елементами, і він спочатку будує дерево таким чином, що всі його секції згорнуті, а потім він перевіряє Set, і якщо там є якісь ID - то він починає шукати ці елементи (а це секції) в нашому вже обробленому масиві, і використовуючи поле "дітки", додавати дітей кожної такої секції до вже існуючого масиву, у відповідні місця, після чого цей масив повертається назад, і я вже малюю всі елементи, а це і секції, і вкладені в ці секції елементи.

Проблема:

Коли вкладених елементів багацько, то при додаванні, видаленні елементів, або при зміні структури дерева, воно отримує на вхід новий масив, і занов будує всю структуру, після чого розкриває необхідні секції, і чим більше у нас елементів, тим більше часу це займає, до моменту, коли нам доводиться чекати секунд 5,  а то й більше, аби додати простий елемент.

Питання:

Чи можна якось спростити це завдання? Адже, якщо ми додаємо 1 новий елемент в кінець дерева, то нам непотрібно перебудовувати все дерево. І один цей кейс я б зміг сам зробити, але треба ще брати до уваги додавання елементів десь всередині дерева, видалення цих елементів, і просто зміну рівня елементів, коли ми перетягуємо їх з рівня на рівень, а бо  ж просто міняємо місцями два елемента.

Post's attachments

tree_structure.png 12.34 kb, 97 downloads since 2019-06-19 

2

Re: Маніпуляції з деревом елементів

А нащо ви перебудовуєте дерево з нуля? Просто міняйте вказівники (батько-дитина) і все.
І не плутайте представлення зі структурою: згорнутість важлива лише для того, щоб зобразити дерево, тобто це одна булева змінна на секцію. А всередині там усе лишається те саме.
І ще складіть окремо мапу ID-шок (ключ - ID, значення - посилання на об'єкт). Тоді шукатимете значно швидше.

Подякували: leofun011

3

Re: Маніпуляції з деревом елементів

koala написав:

А нащо ви перебудовуєте дерево з нуля?

Тому що то видавалось логічно, коли я то починав писати.
У нас є сирий масив елементів, я його передаю компоненту, що будує дерево, той компонент змінює структуру під себе і віддає назад, і та структура вже відмальовується.
При цьому компонент, що будує дерево - ніяким чином не змінює порядок та вкладеність елементів, а лише слугує інтерфейсом, котрий дозволяє нам пертворити звичайний масив на дерево, та також дозволяє розгортувати та згортувати елементи секцій.

Маніпуляції над елементами проходять в іншому місці, там ми можемо створювати, видаляти, та міняти місцями елементи, і всі ці операції проводяться з простим масивом елементів, а не тим, котрого ми отримуємо після побудови дерева.

Відповідно, масив змінюється - ми передаємо цей новий масив в компонет, котрий перебудовує дерево, адже зміни над масивом кажуть нам, що дерево повинно бути інакшим, отже його треба перебудувати.

koala написав:

Просто міняйте вказівники (батько-дитина) і все.

Так тут ще ж треба відслідкувати, які саме зміни пройшли. Якби кожна зміна давала мені результат, як от - Елемент 1 перестав бути дитиною Секції 1, і став дитиною Секції 2, то можна було б знайти ті дві секції, і відфільтрувати дітей Сеції 1, аби серед них не було Елементу 1, і додати того елемента до дітей Секції 2, але ж ми отримуємо сирий масив.

Тут треба якийсь diff робити, чи що. І цей diff повинен містит купу всього, як от - тут видалили, а тут додали, а тут змінили рівень, а ось тут індекс, а тут змінили батьківський елемент, індекс і рівень.


koala написав:

не плутайте представлення зі структурою: згорнутість важлива лише для того, щоб зобразити дерево, тобто це одна булева змінна на секцію. А всередині там усе лишається те саме.

угу, так і є

koala написав:

І ще складіть окремо мапу ID-шок (ключ - ID, значення - посилання на об'єкт). Тоді шукатимете значно швидше.
.

так в мене тут всього 195 елементів, і то вже рахується багато, тому більше, швидше за все, не буде

4

Re: Маніпуляції з деревом елементів

Ще раз: не передавайте сирий масив, працюйте лише з деревом. Сирий масив - це для передачі між машинами, серіалізація-десеріалізація. А всередині програми працюйте з деревом.

5

Re: Маніпуляції з деревом елементів

А яка мова у вас взагалі? Масиви ж динамічні мабуть. Ще й не об'єкти зберігають, а посилання.

6

Re: Маніпуляції з деревом елементів

koala написав:

Ще раз: не передавайте сирий масив, працюйте лише з деревом. Сирий масив - це для передачі між машинами, серіалізація-десеріалізація. А всередині програми працюйте з деревом.

але той масив використовується не лише в компоненті, що дерево будує, а й в інших місцях, то доведеться їх переписувати.
От як - витягнути останній елемент. З масивом це зробити просто, а з деревом, якщо останній елемент -це секція з дітьми, то доведеться заглядувати туди. Тобто, спрощується одне, але ускладнюється інше.

7

Re: Маніпуляції з деревом елементів

koala написав:

А яка мова у вас взагалі? Масиви ж динамічні мабуть. Ще й не об'єкти зберігають, а посилання.

жабаскрипт

8

Re: Маніпуляції з деревом елементів

Тоді трохи поясніть, як ваш масив виглядає, і нащо вам шукати в ньому останній елемент, якщо це дерево. Якщо дерево - це лише відображення масиву, то нащо вам якісь операції із деревом узагалі робити, окрім як виводити?

9

Re: Маніпуляції з деревом елементів

koala написав:

Тоді трохи поясніть, як ваш масив виглядає, і нащо вам шукати в ньому останній елемент, якщо це дерево. Якщо дерево - це лише відображення масиву, то нащо вам якісь операції із деревом узагалі робити, окрім як виводити?

масив виглядає, як одновимірний масив зі схожими елементами, деякі елементи є секціями, деякі простими елементами. Кожен елемент має значення level, тобто рівень.
типу як

[
      {
        id: 123,
        level: 1,
        section: null,
        simpleElement: { id: 23411, name: "anime sticker" }
      },
      { id: 21312, level: 1, section: { id: 2313123, name: "shirts" } },
      {
        id: 123944,
        level: 2,
        section: null,
        simpleElement: { id: 4949, name: "shirt with print kawaii" }
      },
      {
        id: 33874,
        level: 2,
        section: null,
        simpleElement: { id: 3452, name: "shirt with boobies oppai" }
      }
    ]

це приклад масиву, а не точна копія, але тут, наче, є все, що важливо для побудови дерева

для побудови структури дерева я використовую  такий код

  private buildTree(allElements: any[]): any[] {
    return allElements
      .map((element: Element, index: number) => {
        if (element.level > 1) return null; // тому що елемент з рівнем більше 1 не може бути на без попередника з рівнем 1
        let children = [];
        if (this.isExpandable(element)) { // перевіряємо, чи елемент може мати дітей
          const slice = allElements.slice(index + 1, allElements.length);
          children = this.findChildren(slice, index, 2, allElements || []); // шукаємо дітей секції
        }
        return new TreeElement(
          children.length ? children : null,
          element,
          index
        );
      })
      .filter(obj => obj);
  }
// рекурсивно шукаємо всіх дітей та онуків певної секції
  findChildren(
    slice: any[],
    innerIndex: number,
    lookingForLevel: number,
    fullArray: any[]
  ) {
    const children = [];
    for (const element of slice) {
      innerIndex++;
      if (element.level === lookingForLevel) { // перевіряємо, чи даний елемент має рівень, котрий нам треба
        let innerChildren = [];
        if (this.isExpandable(element)) {
          innerChildren = this.findChildren(
            fullArray.slice(innerIndex + 1, fullArray.length),
            innerIndex,
            lookingForLevel + 1,
            fullArray
          );
        }
        children.push(
          new TreeElement(
            innerChildren.length ? innerChildren : null,
            element,
            innerIndex
          )
        );
      }
      if (element.level < lookingForLevel) {
        break;
      } else {
        continue;
      }
    }
    return children;
  }

10

Re: Маніпуляції з деревом елементів

Ну, поки що я бачу, що ви передаєте в findChildren і весь масив, і індекс, і слайс, починаючи з index+1-го елементу. А це вже явно надмірно - створювати копію (слайс), коли є всі потрібні дані.
Ну і я б радив переробити ті функції, що працюють з масивом, на роботу з деревом. Невдало вибрана структура даних.

Подякували: leofun01, FakiNyan2

11

Re: Маніпуляції з деревом елементів

А потім ще виявиться, що FakiNyan сам створив той масив, щоб зробити життя складнішим.

12

Re: Маніпуляції з деревом елементів

leofun01 написав:

А потім ще виявиться, що FakiNyan сам створив той масив, щоб зробити життя складнішим.

не зрозумів, який масив?

13

Re: Маніпуляції з деревом елементів

FakiNyan написав:

не зрозумів, який масив?

Отой початковий, який ви розбираєте для побудови дерева.
Той що має такий вигляд :

[
    {
        id: 123,
        level: 1,
        section: null,
        simpleElement: { id: 23411, name: "anime sticker" }
    },
    {
        id: 21312,
        level: 1,
        section: { id: 2313123, name: "shirts" }
    },
    {
        id: 123944,
        level: 2,
        section: null,
        simpleElement: { id: 4949, name: "shirt with print kawaii" }
    },
    {
        id: 33874,
        level: 2,
        section: null,
        simpleElement: { id: 3452, name: "shirt with boobies oppai" }
    }
]

14

Re: Маніпуляції з деревом елементів

leofun01 написав:
FakiNyan написав:

не зрозумів, який масив?

Отой початковий, який ви розбираєте для побудови дерева.
Той що має такий вигляд :

[
    {
        id: 123,
        level: 1,
        section: null,
        simpleElement: { id: 23411, name: "anime sticker" }
    },
    {
        id: 21312,
        level: 1,
        section: { id: 2313123, name: "shirts" }
    },
    {
        id: 123944,
        level: 2,
        section: null,
        simpleElement: { id: 4949, name: "shirt with print kawaii" }
    },
    {
        id: 33874,
        level: 2,
        section: null,
        simpleElement: { id: 3452, name: "shirt with boobies oppai" }
    }
]

так я це отримую з бекенду, я його не створюю

Подякували: leofun011

15

Re: Маніпуляції з деревом елементів

FakiNyan написав:

так я це отримую з бекенду, я його не створюю

бекенд ще в розробці чи вже завершений ?
Якщо в розробці і якщо є гарантія, що така структура може бути приведена до дерева (тобто не містить циклів), то в мене питання до розробників "Чому бекенд не роздає готове дерево ? чому саме масив ?".

16

Re: Маніпуляції з деревом елементів

Ну так один раз перетворюйте на дерево і далі працюйте з деревом.

17

Re: Маніпуляції з деревом елементів

Я тут вже почав зранку все то переписувати, для початку я виділив все, що стосується дерева, в окремий файл, і от я вже почав розбирати метод додавання елементу.

І тут така проблема, що отой початковий масив сирих даних (не структура типу дерева), зберігається в сховищі, і на цю структуру підписані різні підписанти, в різних місцях додатку. Коли ми змінюємо масив, як от додаємо дані, чи видаляємо, чи отримуємо їх від серверу, ми зберігаємо ці дані в сховище, після чого всі підписанти отримують оновлений масив зі сховища.

То як ви вважаєте, краще опрацьовувати цей сирий масив відразу  після отримання його від серверу, і записувати в сховище вже деревоподібну структуру, і тоді перписати код всіх підписантів, аби вони працювали з структурою дерева, або ж написати метод, котрий би "сериалізував" структуру дерева в простий масив, і тоді лише в певних, потрібних мені місцях, я б мав структуру дерева, додавав би в неї елементи, а потім серіалізував би її в масив, і оновлював би його в сховищі, таким чином, впотрібних місцях я б мав структуру в дерева, а в інших місцях я б мав простий масив, елементи котрого відповідали б елементам, що використовуються в дереві.

Також варто зауважити, що перша побудова дерева відбувається, коли один з підписантів отримує сирий масив з даними. Тобто, якщо я оберу другий варіант, де дерево серіалізується в масив, і масив оновлюється в сховищи, то це вже буде проблемою, адже відразу після того, як масив в сховищі оновлено - підписанти його тримують, і це запустить перебудову дерева.

Також варто зауважити #2, що в інших частинах додатку мені дерево зовсім непотрібне, але потрібен звичайний масив з тими самими даними.

18

Re: Маніпуляції з деревом елементів

leofun01 написав:
FakiNyan написав:

так я це отримую з бекенду, я його не створюю

бекенд ще в розробці чи вже завершений ?
Якщо в розробці і якщо є гарантія, що така структура може бути приведена до дерева (тобто не містить циклів), то в мене питання до розробників "Чому бекенд не роздає готове дерево ? чому саме масив ?".

Тому що дерево нам потрібне лише в одному місці, а в інших місцях нам потрібен простий масив.

19

Re: Маніпуляції з деревом елементів

Ок, тоді може, детальніше поясните, чому в тому місці потрібне саме дерево, а крива обробка масиву не підходить?

Подякували: leofun011

20

Re: Маніпуляції з деревом елементів

koala написав:

Ок, тоді може, детальніше поясните, чому в тому місці потрібне саме дерево, а крива обробка масиву не підходить?

в тому місці потрібне саме дерево, тому що воно відповідає саме за презинтацію, та повинно мати інтуітивний інтерфейс, аби користувачі могли розуміти, який елемент до якої секції відноситься, адже потім вся ця інформація буде надрукована на папері та представлена іншим людям, котрі повинні мати змогу швидко знайти елементи певної категорії, тобто, елементи, що відносяться до певної секції.

В іншому місці, де ми можемо додавати переклад до елементів, нам непотрібна структура дерева, нам просто потрібно побачити всі елементи, та додати до них переклад, тобто, немає різниці, на якому рівні і під якою секцією знаходиться елемент, коли нам потрібно лише перекласти його назву з англійської на німецьку.