javascript - Async/Await för trädtraversering rekursivt i TypeScript

Jag har den enkla trädstrukturen som följer:

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
}

Till exempel har Grupp A två undergrupper, Grupp B och C, och Grupp C har tre undergrupper, Grupp F, G, H, osv.

Jag behöver implementera en algoritm för att hämta alla grupper rekursivt: Förväntat resultat=[Grupp A, Grupp B, Grupp C, Grupp D, Grupp E, Grupp F, Grupp G, Grupp H, Grupp I, Grupp J]

Men jag behöver hämta undergrupperna från databasen så det bör vara asynkront/await.

Metod 1

    const tr = async (group: Group, result: Group[]) => {
      console.log(group);
      result.push(group);
      for (const id of group.subGroups) {
        const groupId = id.toHexString();
        const subGroup = this.findGroup(groupId);
        tr(await subGroup, result);
      }
    };

    const result = [];
    await tr(user.group, result);
    console.log(result);

Metod 2

  async transverse(group: Group, result: Group[]) {
    console.log(group);
    result.push(group);
    for (const id of group.subGroups) {
      const groupId = id.toHexString();
      const subGroup = await this.findGroup(groupId);
      await this.transverse(subGroup, result);
    }
  }

  const result = [];
  await transverse(user.group, result);
  console.log(result);

Metod 1 kan inte ge ut rätt array, och den ger inte ut den kompletta Gruppen A till J. Metod 2 kan få rätt array, men koden ser inte ren ut. Vet någon hur man kan uppnå detta mål på ett elegant sätt och kan svara mig varför metod 1 inte fungerar?

Svar #1

Du kan utnyttja några moderna funktioner, som en asynkron generator, för att göra en genomgång av ditt träd.

Som i exemplet du har gett, är genomgången bred först, jag skulle inte välja rekursion, utan iterera med en loop över varje nivå av trädet. Group-objekten kan lösas "parallellt" när de är på samma nivå, eftersom dessa resultat inte beror på varandra. Detta är ett bra användningsfall för att använda Promise.all istället för individuella awaits för varje nod separat.

Så här skulle det kunna se ut -- jag har inkluderat en mock för databasedelen:

class Group {
    constructor(id, subGroups) {
        this.id = id;
        this.subGroups = subGroups;
    }
}

// Mock of asynchronous DB
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));
const db = {
    _tree: {
        "A": ["B", "C"],
        "B": ["D", "E"],
        "C": ["F", "G", "H"],
        "D": [],
        "E": [],
        "F": ["I", "J"],
        "G": [],
        "H": [],
        "I": [],
        "J": []
    },
    async findGroup(groupId) {
        await delay(Math.random() * 1000);
        return new Group(groupId, db._tree[groupId]);
    }
};

// Make an async generator
async function* tr(groupId) {
    let result = [await db.findGroup(groupId)];
    while (result.length) {
        yield* result;
        // Use Breadth-first traversal order, and allow some parallellism
        result = await Promise.all(result.flatMap(group => group.subGroups.map(db.findGroup)));
    }
};

// Consume the async iterator you get from the above function. The call starts with the id of the tree's root:
(async () => {
    for await (const result of tr("A")) {
        console.log(result);
    }
})();

Svar #2

Okej, så din klass ser ut som

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
} 

Vi behöver definiera vad vi behöver, så förväntat resultat är:

[Grupp A, Grupp B, Grupp C, Grupp D, Grupp E, Grupp F, Grupp G, Grupp H, Grupp I, Grupp J]

Med andra ord, vi behöver loopa på följande sätt: grupp -> alla barn och upprepa.

Vi kan använda en variabel som kommer att hålla de nästa grupperna och sedan loopa igenom den. Denna variabel kommer att initieras med den första gruppen som du hämtar (till exempel grupp A) och sedan kommer loopen att skriva ut dess namn, loopa igenom dess barn och spara varje barn till att vara nästa i skriv-till-variabeln som vi just skapade. Efter att vi har avslutat loopen genom dess barn, kommer vi att ta bort huvudgruppen.

Vi kommer att använda en while-loop som bara kommer att stoppas när variabeln nextToPrint är en tom array.

nextToPrint = []; // variable to hold the next groups to print so it will need to be initialized with groupA.


// some method that runs when your app starting, like mounted() on Vue, attached() on aureliaJS or ngOnInit on Angular
async someMethod() {
  const first = await getGroup(first) // get first group
  nextToPrint.push(first); // push to the queue-like variable


  // loop through the next to print 
  while(nextToPrint.length) {
      printGroup(nextToPrint[0]); // print first item in the next list
  }
}

async printGroup(group: Group) {
   console.log(group.name); // print Group name
   group.subGroups.forEach(g => {
       const child = await getGroup(g); // send it to get the next group
       nextToPrint.push(child); // add child to be the last one to print
       console.log(child.name); // print the child name
   });

   nextToPrint.shift(); // remove first element from the next to print
}

Hoppas det hjälper, känn dig fri att kommentera och ställa fler frågor tills vi får det rätt