nicht angemeldet
Hi Jörg,
ich hatte deine Anfrage bezüglich des gesuchten Algorithmuses ganz vergessen, sorry. Kerki hat dir nun vorgeschlagen, die Infos aus den Quelltexten zum "PHP-phorum" zu ziehen.
Ich hatte mich mal mit dem Problem rumgeschlagen und hatte mir diesen Algorithmus hier ausgedacht.
Der erste Teil ist eine theoretische Abhandlung im 2.Teil gehts dann mittels einer HTML-JS-Datei um ein programmiertechnisches Beispiel. Das Problem ist es dann, die Daten in einer passenden Form aus der DB zu holen und sie dem Algorithmus zur Verfügung zu stellen, was aber gehen sollte.
Sei nicht böse, dass ich erst so vorsichtig gefragt habe, aber dir zu erklären, was zu tun ist, ist 'ne heiden arbeit. Ich weis, wie es geht, aber es jemanden zu erklären ist besonders bei dieser Sache ein Problem. Es ist ein typischer Fall von eine Nacht wach liegen, und dann auf die Lösung kommen, nachdem man schon 14 Tage drüber nachdenkt. Nicht erschrecken, der Thread ist lang, sehr lang. Lies ihn dir bitte genau durch und frag dann nach.
Ich kann dir keine Perllösung aus dem Ärmel schütteln, aber ich habe das Problem mal mit JavaScript gelöst, da ich der Meinenug war/bin: der User hat RechenPower - soll er sie auch nutzen :-)
Nur zur Vorwarnung, die Lösung ist zu 100% auf meinem Mist gewachsen, d.h. möglicherweise gibt es deutlich performantere oder einfachere, Ich habe sie von niemanden nachprüfen lassen. Allerdings habe ich auch nie einen anderen Algorithmus gefunden. Aber sie funktioniert, ich habe sie in 3 Foren im Einsatz. Meine Foren sind nicht SQL-basiert, die Daten werden in Form von JavaScript-Arrays an den User gesendet und bei diesem clientseitig in Divs geschrieben, wie gesagt um den Server zu entlasten. Es ändert nichts am Prinzip: Du hast den Vaterthread und seine Söhne und diese Söhne haben einen Zeiger auf den Thread, auf den sie sich beziehen.
Das eigentliche Problem:
Die Katze beist sich in den Schwanz. Warum? Du musst als erstes die Reihenfolge der Söhne ermitteln. Das ist so schwierig, weil du beim Vater anfängst und dann theoretisch jeden weiteren fragen musst, ob er sich auf den Vater bezieht. Aus denen, die sich auf den Vater beziehen, musst du dann den aktuellsten aussieben. Diese Prozedur ist für jeden Sohn zu wiederholen. Dass das natürlich Wahnsinn ist, kannst du dir vorstellen. Ein Performancekiller vom Feinsten. Einfacher wäre es, beim Letzten anzufangen. Allerdings muss man vorher rausfinden, welcher der Letzte (in der Baumansicht) ist. Und das kannst du unmöglich wissen, womit sich die Katze in den Schwanz beist.
Der folgende Ansatz soll zeigen wie es trotzdem, und sogar erstaunlich schnell geht, wenn man das Problem 2-dimensional angeht.
Nun denn, die Voraussetzungen.
- Der Vater hat die Null, die erste Antwort hat die eins und sie bezieht sich immer auf den Vater. Die zweite Antwort kann sich nun entweder auf den Vater beziehen oder auf den ersten Sohn, and so on...
-->Bekannt sein muss die Ordnugsnummer des Sohnes, die sich aus der Postingreihenfolge ergibt.
- Um festzustellen, auf wen sich der Sohn bezieht, muss in ihm die Nummer des Sohnes gespeichert sein, auf den er sich bezieht. Bezieht er sich direkt auf den Vater, heist sein Bezugspunkt (ich habe ihn referer benannt) "0"
-->Bekannt sein muss die Ordnungsnummer des Sohnes, bzw. Vaters, auf den sich das aktuelle Posting bezieht, im Nachfolgenden als Referer bezeichnet
Schauen wir uns mal einen (schön zerpflückten) Beispielthread an. Klammer vorne bedeuted die Nummerierung, Klammer hinten bedeuted, auf welchen es sich bezieht. Anordnung wie aus SELFForum gewohnt, d.h. bei gleicher Einrückungsstufe befindet sich der Jüngste am weitesten oben:
( 0.) Vaterthread (kein Bezug, als -1 gekennzeichnet) (12.) Sohn ( 0) ( 4.) Sohn ( 0) ( 8.) Sohn) ( 4) ( 2.) Sohn ( 0) (19.) Sohn ( 2) (23.) Sohn (19) (25.) Sohn EOF(19) (14.) Sohn ( 2) ( 9.) Sohn ( 2) (11.) Sohn ( 9) (10.) Sohn ( 9) (17.) Sohn (10) ( 3.) Sohn ( 2) ( 5.) Sohn ( 3) ( 6.) Sohn ( 5) (11.) Sohn ( 6) (15.) Sohn (13) (16.) Sohn (15) (18.) Sohn (16) (20.) Sohn (18) (21.) Sohn (20) (22.) Sohn (21) (24.) Sohn (22) ( 1.) Sohn ( 0) ( 7.) Sohn ( 1)
Weitere logische Bedingung ist, dass sich die Nummer 3 zB. unmöglich auf die Nummer 7 beziehen kann, da die 3 ja vor der 7 geschrieben wurde. Nun kommt der schwierige Teil, die Sortierung. Nach langer Überlegung bin ich auf die Idee gekommen, dass eine eindimensionale Variante zu lange dauert, d.h. zu viele if()-abfragen. Deshalb habe ich das Problem 2-Dimensional gelöst. Ich versuche dir den Ansatz mal grafisch zu vermitteln. Wir beginnen mit einem leeren 2-dimensionalen Array, welches so groß ist, wie die Anzahl der Söhne + den Vater, also im Beispiel = 25, aber beginnend mit 0 also 0-24, ok. Um genau zu sein, erzeugen wir ein Array, dass 25 Elemente lang ist, und jedes Element ist wieder ein Array, welches bislang nur einen Eintrag hat: sein 0.Element ist seine Ordnungszahl.
structure[ 0] = [ 0] structure[ 1] = [ 1] structure[ 2] = [ 2] structure[ 3] = [ 3] structure[ 4] = [ 4] structure[ 5] = [ 5] structure[ 6] = [ 6] structure[ 7] = [ 7] structure[ 8] = [ 8] structure[ 9] = [ 9] structure[10] = [10] structure[11] = [11] structure[12] = [12] structure[13] = [13] structure[14] = [14] structure[15] = [15] structure[16] = [16] structure[17] = [17] structure[18] = [18] structure[19] = [19] structure[20] = [20] structure[21] = [21] structure[22] = [22] structure[23] = [23] structure[24] = [24] structure[25] = [25]
Jetzt passiert folgendes, wir arbeiten rückwärts, und hängen das jeweilige Array an das jenige an, auf welches es referenziert(siehe Samplethread). Also die 25 referenziert auf die 19, die 24 auf die 22, 23->19, 22->21, 21->20, 20->18, 19->2 usw.:
[ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2,19,25,23] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 4] [ 4] [ 4] [ 4] [ 4] [ 4] [ 4] [ 5] [ 5] [ 5] [ 5] [ 5] [ 5] [ 5] [ 6] [ 6] [ 6] [ 6] [ 6] [ 6] [ 6] [ 7] [ 7] [ 7] [ 7] [ 7] [ 7] [ 7] [ 8] [ 8] [ 8] [ 8] [ 8] [ 8] [ 8] [ 9] [ 9] [ 9] [ 9] [ 9] [ 9] [ 9] [10] [10] [10] [10] [10] [10] [10] [11] [11] [11] [11] [11] [11] [11] [12] [12] [12] [12] [12] [12] [12] [13] [13] [13] [13] [13] [13] [13] [14] [14] [14] [14] [14] [14] [14] [15] [15] [15] [15] [15] [15] [15] [16] [16] [16] [16] [16] [16] [16] [17] [17] [17] [17] [17] [17] [17] [18] [18] [18] [18] [18] [18,20,21,22,24] [18,20,21,22,24] [19] [19,25] [19,25] [19,25,23] [19,25,23] [19,25,23] [20] [20] [20] [20] [20] [21] [21] [21] [21] [21,22,24] [22] [22] [22,24] [22,24] [23] [23] [23] [24] [24] [25]
wichtig ist immer, dass das ganze Array an das Referenzierende angehangen wird.
Aus der erfolgten Sortierung ergibt sich 1 Array, welches in sich nun die Reihenfolge der Söhne beinhaltet, dieses Array ist das erste Array in structure, also structure[0].
Sehen wir uns das an: erste Spalte ist die Reihenfole, dahinter kommt die Abbildung:
structure[0]| Anzeige
0 | ( 0.) Vaterthread (kein bezug, als -1 gekennzeichnet) 12 | (12.) Sohn ( 0) 4 | ( 4.) Sohn ( 0) 8 | ( 8.) Sohn) ( 4) 2 | ( 2.) Sohn ( 0) 19 | (19.) Sohn ( 2) 23 | (23.) Sohn (19) 25 | (25.) Sohn EOF(19) 14 | (14.) Sohn ( 2) 9 | ( 9.) Sohn ( 2) 11 | (11.) Sohn ( 9) 10 | (10.) Sohn ( 9) 17 | (17.) Sohn (10) 3 | ( 3.) Sohn ( 2) 5 | ( 5.) Sohn ( 3) 6 | ( 6.) Sohn ( 5) 13 | (13.) Sohn ( 6) 15 | (15.) Sohn (13) 16 | (16.) Sohn (15) 18 | (18.) Sohn (16) 20 | (20.) Sohn (18) 21 | (21.) Sohn (20) 22 | (22.) Sohn (21) 24 | (24.) Sohn (22) 1 | ( 1.) Sohn ( 0) 7 | ( 7.) Sohn ( 1)
Nun stellt sich ja vielleicht die Frage, warum haben wir dabei nicht gleich die Einrückunstiefe mitermittelt und z.B einen Array "level" geschaffen, den wir bei der Ausgabe nur abfragen müssen. Der Grund liegt in der Performance: Wenn wir zum Beispiel von Sohn 2 zu Sohn 19 gehen, brauchen wir keinerlei Information über die Einrückung, denn da sich die 19 auf die 2 bezieht ist klar, dass wir nur eine Stufe tiefer gehen müssen. Wir merken uns nur, wie oft wir das machen - in der Variable "level". Die wird jedesmal um einen erhöht.
Nur wenn wir z.B. von der 17 auf die 3 gehen, müssen wir die Einrücktiefe gesondert ermitteln, um die Anzahl der schließenden "</ul>"'s zu rauszubekommen. So geht's:
Wir setzen einen Wert "nextlevel = 0". Dieser Wert wird am Ende der Prozedur den level des folgenden Sohnes haben. Wir erfragen den referer des naechsten Sohns, dann erfragen wir den referer von dem und so weiter bis wir beim Vater sind (referer-Wert = -1), jedes mal zaehlen wir dabei den nextlevel-Wert einen hoch. Aus der Differenz des aktuellen level und dem nextlevel erhalten wir die Anzahl der schliessenden </ul>'s.
That's it. Puh, damit sind wir mit der Theorie durch :-). Im nächsten Thread steht eine auskommentierte HTML-Datei. Komplett in den Editor kopieren, abspeichern, austesten. Diese beinhaltet das programmiertechnische Konzept. Dieses Konzept sollte IMHO recht einfach auf jede andere Sprache umsetzbar sein. Das Problem besteht also mehr oder minder darin, die Daten in der benötigten Form aus der DB zu ziehen. Zur Erinnerung: du brauchst die Ordnungsnummer(Reihenfolge) und zu jedem Sohn die Nummer von dem, auf den er sich bezieht.
Viel Spass beim Probieren, bye eddie