wie erstelle ich am besten ein Baum-Array?

[Cystasy]

Hey,
Also.. ich möchte derzeit ein Hacking Spiel entwickeln das im Grunde genommen eine Konsole inklusive Dateisystem, Programme & co. simuliert.
Ich habe nun die Grundlegende Simulation der Konsole (annehmen von Befehlen usw) fertig vom Grundsätzlichen, stecke aber jetzt beim Konzept / der Strukturierung des simulierten Dateisystems fest. Ich dachte daran die Dateistruktur in ein Array / JSON Objekt zu packen, aber genau daran scheitert es leider.

Probleme die ich habe:
- navigieren innerhalb des Array / Json Objekt (Virtuelle Ordner)

- JSON / Array / Baum ???
Kurz gesagt - ich weiß nicht was ich am besten nehmen soll.. ein JSON Objekt? Array? Oder vielleicht doch was komplett anderes?
Ich habe bisher noch nie etwas programmiert wo ich solch eine Datenstruktur benötigt hätte und habe somit auch keine Idee wie ich das ganze am besten einfach & performant lösen könnte. Grundlegend betrachtet brauche ich eine Datenstruktur wie z.b https://de.wikipedia.org/wiki/Baum_(Graphentheorie) - nur weiß ich nicht wie ich das so wie ichs brauche dann in Code umsetze :confused:

Ich hatte im laufe von 2-3 Wochen schon unterschiedliche Ansätze, die ich aber bisher alle verwerfen musste weil sie entweder im Laufe der Zeit zu komplex wurden und nicht funktionierten, oder einfach vom Gedankenkonzept her falsch durchdacht waren und dann nicht das ermöglichten was ich brauche :abnormal:

Als Grundsätzliche Anforderungen & Gedankenmodell habe ich folgendes:

Dateien und Ordner sind von der Struktur her ähnlich aufgebaut.. und zwar so:

FS_NAME | FS_TYPE | FS_CONTENT

FS_NAME = Der Datei / Ordnername
FS_TYPE = 1 oder 0.. jenachdem obs ein Ordner ist oder eine Datei
FS_CONTENT = Wenn es eine Datei ist, steht dort der Dateinhalt in Form eines Strings drine, ist es ein Ordner enthält es wiederum ein Array / Objekt das weitere Dateistrukturen enthält die genau aufgebaut sind wie alle anderen Dateien.

In Javascript würde solch ein Objekt z.b so aussehen können..



var File = ['Helloworld.txt', 1, 'This is a Example!'];
var Directory = ['logs', 0, [['log1.txt', 1, 'Logfile 1!'], ['log2.txt', 1, 'Logfile 2!']]];


Das ganze ist aber von der Struktur nicht wirklich sinnvoll weil man dann nicht wirklich darin navigieren kann (mittels cd / cd.. befehl).. vorallem wenns dann mehr als eine Ordnertiefe hat. Ich bräuchte hier irgendeine Referenz auf die "vorherige Tiefe", aber hier scheitert es weil ich ja nicht jedesmal das komplette Dateistruktur Objekt übergeben kann.. das artet in extreme Komplexität & Aufwand aus (und ich habs bisher auch noch nicht bugfrei hinbekommen).

Daher ist jetzt meine Frage.. hat jemand eine Idee wie ich sowas am besten lösen könnte? Das Problem ist jetzt nicht spezifisch Javascript bezogen.. das ist eher eine Frage von "Wie baue ich das am besten als Code?". Entweder ich bin zu unkreativ oder whatever.. ergo.. bitte helft mir wenn ihr ne Idee habt wie man sowas umsetzen könnte^^

p.s: Vorallem muss ich dann halt das Dateistruktur Objekt auch entsprechend anpassen können, heißt Elemente entfernen / hinzufügen etc.. was es wieder komplexer werden lässt eventuell.. momentan ist das für mich ein totaler mindf*ck :x Habe auch schon gefühlt das halbe Internet danach abgesucht wie man solch eine Baumstruktur in JS aufbauen kann, aber habe dort nur Dinge gefunden die nicht das tun was ich brauche.

grüße & danke schon einmal

[ChEeTaH182]

Kennst du das Kompositum? https://de.wikipedia.org/wiki/Kompositum_(Entwurfsmuster) Damit lassen sich Bäume gut darstellen. Ansonsten kannst du dir ja anschauen wie es unter Unix gemacht wird (siehe INodes). Das ist die Dateisystemstruktur des OS, welche ziemlich ausgeklügelt ist.

Edit: https://de.wikipedia.org/wiki/Inode

[Lindor]

Als wir uns neulich in der SB darüber unterhalten haben, habe ich folgendes PoC zusammengeworfen. Allerdings kann ich auch kein JavaScript. Bitte nicht hauen :)


function FS() {
this.root = new Dir("", "");
this.cwd = this.root;

this.cd = function(dirName) {
if (dirName == ".." && this.cwd != this.root) {
this.cwd = this.cwd.pDir;
}

this.cwd.contains.forEach(function(element) {
if (element.dirName == dirName) {
this.cwd = element;
}
}, this);
}

this.ls = function() {
this.cwd.contains.forEach(function(element) {
if (element.dirName) {
console.log(element.dirName);
} else if (element.fileName) {
console.log(element.fileName);
}
});
}

this.pwd = function() {
p = "";
dir = this.cwd;

while (dir != this.root) {
p = "" + (dir.dirName) + "/" + p;
dir = dir.pDir;
}

p = "/" + p;
console.log(p);
}
}

function Dir(dirName, contains, pDir) {
this.pDir = pDir;
this.dirName = dirName;
this.contains = [];

this.add = function(o) {
if (o.hasOwnProperty("pDir")) {
o.pDir = this;
}
this.contains.push(o)
};
}

function File(fileName, fileContents) {
this.fileName = fileName;
this.fileContents = fileContents;
}

var fs = new FS();

// Dateien Anlegen
fs.root.add(new File("Katzen.txt", "Ich mag Katzen"));
fs.root.add(new File("KatzenSindToll.txt", "Ich mag Katzen, denn sie sind sehr gut"));

// Ordner "Katzenbilder" anlegen.
var katzenBilder = new Dir("Katzenbilder")
katzenBilder.add(new File("001.jpg", "BILD-001"));
katzenBilder.add(new File("002.jpg", "BILD-002"));
fs.root.add(katzenBilder);

// Unterordner "Extra süße Katzen" anlegen.
var extraAwwKatzenbilder = new Dir("Extra süße Katzen")
extraAwwKatzenbilder.add(new File("extra001.jpg", "xxx"));
extraAwwKatzenbilder.add(new File("extra002.jpg", "xxx"));
katzenBilder.add(extraAwwKatzenbilder);

// Sinnlos durch die Gegend navigieren.
console.log("------");
fs.cd("Katzenbilder");
fs.pwd();
fs.ls();

console.log("------");
fs.cd("Extra süße Katzen");
fs.pwd();
fs.ls();

console.log("------");
fs.cd("..");
fs.pwd();
fs.ls();

console.log("------");
fs.cd("..");
fs.pwd();
fs.ls();

console.log("------");
fs.cd("..");
fs.pwd();
fs.ls();

[s3rb31]

Es gibt einige unschöne Nebeneffekte wenn man Objekte einfach als Maps missbraucht. Daher gibt es inzwischen eine dedizierte Klasse dafür: Map (https://developer.mozilla.org/de/docs/Web/JavaScript/Reference/Global_Objects/Map).

Damit ist es dann nicht weiter schwer eine sich selbst enthaltene Datenstruktur aufzubauen. Und da JS ziemlich flexibel ist können wir sogar recht unkompliziert über mehrere Ebenen auflösen. Ein Beispiel in TypeScript:



class Stream
{
readonly name: string;
readonly content: string;

// ...

private constructor(name: string, content: string)
{
this.name = name;
this.content = content;
}

public static create(name: string, content: string)
{
return new Stream(name, content);
}


// ...
}

class Directory
{
readonly name: string;

private streams: Map<string, Stream>;
private dirs: Map<string, Directory>;

private constructor(name: string)
{
this.name = name;

this.streams = new Map<string, Stream>();
this.dirs = new Map<string, Directory>();
}

public static create(name: string)
{
return new Directory(name);
}

public addStream(stream: Stream)
{
this.streams.set(stream.name, stream);

return this;
}

public addDirectory(dir: Directory)
{
this.dirs.set(dir.name, dir);

return this;
}

public getStream(name: string)
{
return this.streams.get(name);
}

public getDirectory(...children: string[])
{
let obj: Directory | undefined = this;

if (children != undefined && children.length > 0)
{
let elem = undefined;

do {
elem = children.shift();

if (elem != undefined && obj != undefined) {
obj = obj.dirs.get(elem);
}
}
while (elem != undefined)
}

return obj;
}
}

// USAGE

let root = Directory.create("ROOT");

// add files

root.addStream(Stream.create("file1", "test1"));
root.addStream(Stream.create("file2", "test2"));

console.log("file1: " + root.getStream("file1").content);

// add dirs

root.addDirectory(Directory.create("subdir1"))
.addDirectory(Directory.create("subdir2").addDirectory(Directory.create("subsubdir1")));

// get directory by path

let subsubdir1 = root.getDirectory("subdir2", "subsubdir1");

console.log(subsubdir1);
console.log(root);



Hier (https://www.typescriptlang.org/play/#src=class%20Stream%0D%0A%7B%0D%0A%20%20%20%20read only%20name%3A%20string%3B%0D%0A%20%20%20%20readon ly%20content%3A%20string%3B%0D%0A%0D%0A%20%20%20%2 0%2F%2F%20...%0D%0A%0D%0A%20%20%20%20private%20con structor(name%3A%20string%2C%20content%3A%20string )%0D%0A%20%20%20%20%7B%0D%0A%20%20%20%20%20%20%20% 20this.name%20%3D%20name%3B%0D%0A%20%20%20%20%20%2 0%20%20this.content%20%3D%20content%3B%0D%0A%20%20 %20%20%7D%0D%0A%0D%0A%20%20%20%20public%20static%2 0create(name%3A%20string%2C%20content%3A%20string) %0D%0A%20%20%20%20%7B%0D%0A%20%20%20%20%20%20%20%2 0return%20new%20Stream(name%2C%20content)%3B%0D%0A %20%20%20%20%7D%0D%0A%0D%0A%0D%0A%20%20%20%20%2F%2 F%20...%0D%0A%7D%0D%0A%0D%0Aclass%20Directory%0D%0 A%7B%0D%0A%20%20%20%20readonly%20name%3A%20string% 3B%0D%0A%0D%0A%20%20%20%20private%20streams%3A%20M ap%3Cstring%2C%20Stream%3E%3B%0D%0A%20%20%20%20pri vate%20dirs%3A%20Map%3Cstring%2C%20Directory%3E%3B %0D%0A%0D%0A%20%20%20%20private%20constructor(name %3A%20string)%0D%0A%20%20%20%20%7B%0D%0A%20%20%20% 20%20%20%20%20this.name%20%3D%20name%3B%0D%0A%0D%0 A%20%20%20%20%20%20%20%20this.streams%20%3D%20new% 20Map%3Cstring%2C%20Stream%3E()%3B%0D%0A%20%20%20% 20%20%20%20%20this.dirs%20%3D%20new%20Map%3Cstring %2C%20Directory%3E()%3B%0D%0A%20%20%20%20%7D%0D%0A %0D%0A%20%20%20%20public%20static%20create(name%3A %20string)%0D%0A%20%20%20%20%7B%0D%0A%20%20%20%20% 20%20%20%20return%20new%20Directory(name)%3B%0D%0A %20%20%20%20%7D%0D%0A%0D%0A%20%20%20%20public%20ad dStream(stream%3A%20Stream)%0D%0A%20%20%20%20%7B%0 D%0A%20%20%20%20%20%20%20%20this.streams.set(strea m.name%2C%20stream)%3B%0D%0A%0D%0A%20%20%20%20%20% 20%20%20return%20this%3B%0D%0A%20%20%20%20%7D%0D%0 A%0D%0A%20%20%20%20public%20addDirectory(dir%3A%20 Directory)%0D%0A%20%20%20%20%7B%0D%0A%20%20%20%20% 20%20%20%20this.dirs.set(dir.name%2C%20dir)%3B%0D% 0A%0D%0A%20%20%20%20%20%20%20%20return%20this%3B%0 D%0A%20%20%20%20%7D%0D%0A%0D%0A%20%20%20%20public% 20getStream(name%3A%20string)%0D%0A%20%20%20%20%7B %0D%0A%20%20%20%20%20%20%20%20return%20this.stream s.get(name)%3B%0D%0A%20%20%20%20%7D%0D%0A%0D%0A%20 %20%20%20public%20getDirectory(...children%3A%20st ring%5B%5D)%0D%0A%20%20%20%20%7B%0D%0A%20%20%20%20 %20%20%20%20let%20obj%3A%20Directory%20%7C%20undef ined%20%3D%20this%3B%0D%0A%0D%0A%20%20%20%20%20%20 %20%20if%20(children%20!%3D%20undefined%20%26%26%2 0children.length%20%3E%200)%0D%0A%20%20%20%20%20%2 0%20%20%7B%0D%0A%20%20%20%20%20%20%20%20%20%20%20% 20let%20elem%20%3D%20undefined%3B%0D%0A%0D%0A%20%2 0%20%20%20%20%20%20%20%20%20%20do%20%7B%0D%0A%20%2 0%20%20%20%20%20%20%20%20%20%20%20%20%20%20elem%20 %3D%20children.shift()%3B%0D%0A%0D%0A%20%20%20%20% 20%20%20%20%20%20%20%20%20%20%20%20if%20(elem%20!% 3D%20undefined%20%26%26%20obj%20!%3D%20undefined)% 20%7B%0D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20 %20%20%20%20%20%20%20obj%20%3D%20obj.dirs.get(elem )%3B%0D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20% 20%20%20%7D%0D%0A%20%20%20%20%20%20%20%20%20%20%20 %20%7D%0D%0A%20%20%20%20%20%20%20%20%20%20%20%20wh ile%20(elem%20!%3D%20undefined)%0D%0A%20%20%20%20% 20%20%20%20%7D%0D%0A%0D%0A%20%20%20%20%20%20%20%20 return%20obj%3B%0D%0A%20%20%20%20%7D%0D%0A%7D%0D%0 A%0D%0A%2F%2F%20USAGE%0D%0A%0D%0Alet%20root%20%3D% 20Directory.create(%22ROOT%22)%3B%0D%0A%0D%0A%2F%2 F%20add%20files%0D%0A%0D%0Aroot.addStream(Stream.c reate(%22file1%22%2C%20%22test1%22))%3B%0D%0Aroot. addStream(Stream.create(%22file2%22%2C%20%22test2% 22))%3B%0D%0A%0D%0Aconsole.log(%22file1%3A%20%22%2 0%2B%20root.getStream(%22file1%22).content)%3B%0D% 0A%0D%0A%2F%2F%20add%20dirs%0D%0A%0D%0Aroot.addDir ectory(Directory.create(%22subdir1%22))%0D%0A%20%2 0%20%20.addDirectory(Directory.create(%22subdir2%2 2).addDirectory(Directory.create(%22subsubdir1%22) ))%3B%0D%0A%0D%0A%2F%2F%20get%20directory%20by%20p ath%0D%0A%0D%0Alet%20subsubdir1%20%3D%20root.getDi rectory(%22subdir2%22%2C%20%22subsubdir1%22)%3B%0D %0A%0D%0Aconsole.log(subsubdir1)%3B%0D%0Aconsole.l og(root)%3B%0D%0A) kannst du den Code testen.

PS. Das ganze ist nicht für deine Zwecke angepasst, sollte aber nicht schwer fallen. Eine möglichkeit wäre z. B. ein `parent` pro Ordner zu setzen und die Namensauflösung vielleicht anders zu gestalten, z. B. so dass ganze Pfade und nicht einzelne Argumente übergeben werden.

[Cystasy]

@s3rb31
Danke für deine Antwort & dein Codebeispiel. Ich habe mir jetzt mal das Map Objekt für Javascript ein bisschen angeschaut, aber glaube Lindor's Beispiel ist von den Beispielen die bisher gepostet wurden am besten in mein bisheriges Projekt implementierbar. Ich werde aber im laufe der Zukunft mich weiterhin mit dem Maps Objekt & deinem Beispiel beschäftigen und mal schauen ob ich es vllt doch verwende. Was ich mich aber frage - gibt es einen bestimmten Grund weshalb du Typescript verwendest? Kommst du damit besser klar beim scripten? Oder welche Gründe hast du für Typescript gegenüber vanilla JS?

@Lindor
Danke für dein Beispiel, ich habe jetzt etwas mehr Zeit gehabt (hatte viel zu tun RL) mir das ganze näher anzuschauen und das ganze sieht sehr vielversprechend aus. So wie du es gelöst hast ist es eigendlich glaub ich am besten - denn sowas ähnliches wollte ich hinbekommen, ich kam nur nicht auf die Idee es so zu lösen wie in deinem Beispiel - danke dir dafür. Ich werde das ganze jetzt mal auf mein bisheriges Projekt anpassen & dann mal schauen wie ich den Rest drum herum bastle :)

p.s: Dafür das du kein JS kannst, ist der Code ganz gut. Vorallem aber hast du mich dadurch auch auf ne Idee gebracht auf die ich ohne Hilfe nicht kam - danke nochma^-^


grüße