Te hogy oldanád meg? - Rekurzív kategória fa struktúra építés szöveges sorokból

SZERK: PHP-ben írt megoldások előnyben, komplett kód vagy akárcsak vázlat.

-----

A megoldandó probléma:

Adott egy rakás termék, kategórianevekkel, egybe írva több szintet, pl:

"Főkategória1|Alkategória2|Al-abb-kategória"
és
"Főkategória2|Alkategória3"
és
"Főkategória3"

Amit el kéne érni, hogy egy ilyen listát kapjunk:

ID - név - szükőkategória ID-je
0 - root
1 - Főkategória1 - 0
2 - Főkategória2 - 0
...
12 - Alkategória2 - 1
13 - Al-Abb-kategória - 12

Az ideális egy rekurzív megoldás lenne, végtelen kategóriaszintig feltérképezve, kezelve az üres kategóriákat (példában a Főkategória3), és azt, ha a közbenső kategória nincs létrehozva előre (Pl Fő1-Al2-Alabb előbb lesz feldolgozva, mint a Fő1-Al2).

Mindezt úgy, hogy ezeket a string-eket előbb a termékek adatlapjaiból nyerjük ki, és később oda a kategória ID-jét vissza kéne írni.

Van egy 3 szintig működő, nem túl elegáns megoldásom, 3 különféle megközelítéssel probálkoztm, de még keresem a legjobbat.

Tanácsokat elfogadok, akár csak elvi leírást, kódra nem feltétlen van szükségem.

7683 megtekintés

Feltéve, hogy a példában elírás az, hogy az Alkategória2 (hacsak nem az ékezet különbözteti meg azokat) két főkategóriában is előfordulhat:


awk -F'|' '
   BEGIN { id2txt[ 0] = "root" }

   {
      for (i=1; i<=NF; ++i) {
         if ( ! ($i in txt2id)) {
            txt2id[ $i] = ++maxid
            id2txt[ maxid] = $i
         }
         parent[maxid] = i>1 ? txt2id[$(i-1)] : 0
      }
   }

   END {
      print
      for (i=0; i<=maxid; ++i) {
         printf "%d - %s %s\n", i, id2txt[i], (i>0 ? " - " parent[i] : "")
      }
   }
' <<EOF
Allat|Gerinces|Emlos
Allat|Gerinces|Madar
Allat|Gerinces
Allat|Izeltlabu|Rovar|Szarnyas rovar
Noveny|Moha
EOF

0 - root
1 - Allat  - 0
2 - Gerinces  - 1
3 - Emlos  - 1
4 - Madar  - 0
5 - Izeltlabu  - 1
6 - Rovar  - 5
7 - Szarnyas rovar  - 6
8 - Noveny  - 0
9 - Moha  - 8

0 szavazat

A hozzászóláshoz be kell jelentkezni

Elírás volt az ékezethiba, egyúttal rosszul is írtam le a feladatot, nem cél felismerni hogy egy kategória két helyre is be van csatolva, ha ugyan az a neve, de más a parent-je, akkor külön kategória, és kész.

Egyébként köszönet a megoldásod, még reggel van ahhoz hogy teszteljem, elsőre megfelelőnek tűnik.

0 szavazat

A hozzászóláshoz be kell jelentkezni

"ha ugyan az a neve, de más a parent-je, akkor külön kategória,"

Nincs mit, de ha a Kat1|Kat11 és Kat2|Kat11 esetén a két Kat11 nem azonos node-ot jelent, akkor az én megoldásom nem jó, mert a szülőt nem, csak a saját megnevezését használja az id képzésére.

0 szavazat

A hozzászóláshoz be kell jelentkezni

Követelmény, hogy az IDek szint szerint is rendezve legyenek? Tehát 1..N-ig Főkategória1..FőkategóriaN, aztán N+1-től az alkategóriák és gyermekeik?

Ha nem, az alábbi megoldás jó lehet:


#!/usr/bin/perl

use strict;
use warnings;
use feature qw/say/;

my ($tree, $list);

binmode(STDIN, "utf8");

while (<>) {
	next if /^\s+$/;
	chomp;
	s/\|/"}{"/g;
	$_ = q/$tree->{root}->{"/.$_.q/"}++/;
	eval;
}

$list = descend($list, $tree, 0);

say "0 - root";
for (1..$#$list) {
	say join " - ", $_, @{$list->[$_]};
}

sub descend {
	my ($listref, $hashref, $rootid) = @_;
	my $last = $#$listref;
	
	for (sort keys %$hashref) {
		push @$listref, [$_, $last];
		if (ref $hashref->{$_} eq "HASH") {
			$listref = descend($listref, $hashref->{$_}, $#$listref);
		}
	}
	return $listref;
}

Ebben két nemtriviális dolog van, az egyik a while ciklusban, ahol a fát tartalmazó hash-in-hash struktúrát úgy építem fel, hogy a bementet reguláris kifejezésekkel Perl értékadássá alakítom, és a kapott stringet kiértékelem, közben támaszkodva a Perl autovivification nevű találmányára; a másik pedig a rekurzív fabejárás, ami felépíti a listát, amit a végén simán kiíratok.

0 szavazat

A hozzászóláshoz be kell jelentkezni

Bár nem kódot kértél, de megtetszett a feladat :) Remélem elég jól olvasható a kód külön magyarázat nélkül is.

Itt. Nem feltétlen hibatűrő, nem teszteltem. A lényegi logika a TreeBuilder.java-ban van.

Félreértettem a feladatot, ez csak struktúrát épít, nem pedig bejár :)

Szerk:
Mégse értettem félre, csak meg kell írni a bejárást.

0 szavazat

A hozzászóláshoz be kell jelentkezni

Na, ha már, akkor kicsit átvariáltam, meg adtam hozzá teszteket, meg megcsináltam a TreeWalkert.

Röviden egyébként annyit csinál a cucc (bár elég jól látni a kódon), hogy:

Node - node, vannak childNode-jai.
IdGenerator - ID-t generál

TreeBuilderService:
szétszedi a stringet az adott szintre beillesztendő kategóriára és maradékra.
megnézi, hogy van-e beillesztendő kategória, ha van akkor megkeresi, hogy van-e már ilyen néven kategória az adott szinten. Ha van, akkor a maradék Stringgel meghívja a következő szintet, ha nincs akkor létrehozza, és utána hívja meg a maradékkal a következő szintet.

TreeWalkerService:
összeszámolja az adott node összes childNode-ját

Szerk: amúgy egyre jobban érzem, hogy ez a CleanCode brutál jó cucc. Ha megnézed a TreeBuilderService.addNodeToNextLevel(Node root, String string) függvényt, akkor ez gyakorlatilag pszeudokódnak is elmenne, annyira jól olvasható a kód. Mondjuk pár átnevezést még kellene benne csinálnom, pl nem getCategory, hanem getCategoryForThisLevel és nem getRest, hanem getCategoriesForTheNextLevel. Át is írom izibe.

Szerk2:

Szerintem ez tök elmegy pszeudokódszerűségnek:)

public void addNodeToNextLevel(Node root, String string) { String category = getCategoryForThisLevel(string); String rest = getCategoriesForNextLevel(string);

  if (isAnyCategoryLeft(category)) {
    Node nodeToAddTo = searchForCategoryWithName(root, category);
    if (nodeToAddTo == null) {
      nodeToAddTo = addNodeToSameLevel(root, category);
    }
    if (!rest.isEmpty()) {
      addNodeToNextLevel(nodeToAddTo, rest);
    }
  }
}

0 szavazat

A hozzászóláshoz be kell jelentkezni

Sziasztok,
Bár , nyelv megjelölést nem látok, talán nem lövök mellé, hogy általános megoldást kérsz :)
Személy szerint erre az adatforrásra több dimenziós láncolt listát adnék, már csak amiatt is, mivel a végtelen*végtelen könnyebben ábrázolható "egymásba ágyazott" listákkal (bocsi, a tökéletes szakkifejezés nem ugrik be :) )
Egész pontosan, egy ciklikus listára fűznék fel ütköző elemes listákat (aka. lenne egy infinite típusú eleme, ami a legutolsó lista elem funkció szerepét látja el...)
Persze, itt jön még az általad adott kitétel, hogy a Fő1-Al2-Alabb értelmes legyen addig is, amíg Fő1-Al2 nem kerül elő...
Erre töredék listákat hoznék létre (Ha az adott elem csatlakozási pontja még nem értelmezett), amolyan cache-ként, és ha új értelmezhető elemet találok, végig futnám ezt a lista köteget...
Persze, ez most elég vadul megfogalmazva, de ha további kérdésed van, szívesen konkretizálom az elképzelést :)
Üdv,
LuiseX
Szerk: Mit fedne itt a feldolgozás? Amennyiben az általad adott példa fedi a teljes adattartalmát a file-oknak, az al-al kategóriákkal is fel lehet építeni ezt a listát, és csak léptetni kell a forrást, ha már létező lista elemet találunk...
Szerk2: Most néztem csak a feladat másik felét :) Ez a felépítés után még könnyebb :) Csak be kell járnod rendre a listát :)

0 szavazat