junit-quickcheck - zufällige Bäume erzeugen, die die Tiefe endlich halten

Question

Ich übe Junit-Quickcheck.

Ich habe Generatoren für die drei Sortierkomponenten eines Binärbaums vorbereitet (Node, Leaf, Empty).

Ich möchte zufällige Bäume erstellen und Eigenschaften auf ihnen überprüfen.

Der Generator für Node s wählt nach bestimmten Wahrscheinlichkeiten weitere Generatoren für seine beiden Zweige aus.

Allerdings möchte ich, dass die Bäume irgendwann während jedes Laufs aufhören zu wachsen. Die Wahrscheinlichkeit, einen Teilbaum zu erstellen, der Node ist, muss mit der Entwicklung der Generation abnehmen.

Ich hatte gehofft, die Tiefe des Baumes mit Hilfe der GenerationStatus zu kontrollieren, aber ich kann nicht genau sehen, wie. Eine andere Hypothese ist, die Methode configure() des nächsten Generators vor generate() aufzurufen, aber ich habe es noch nicht geschafft.

Was ist der richtige Weg, um all das zu erreichen?

Answer 1

Sie können GenerationStatus#setValue(Key, Object) verwenden, um Werte zwischen Generatoren zu übergeben. Hier

ist ein Beispiel, das ich schrieb, dass streng monoton fallend Listen von positiven ganzen Zahlen erzeugt:

import com.pholser.junit.quickcheck.generator.GenerationStatus; 
import com.pholser.junit.quickcheck.generator.Generator; 
import com.pholser.junit.quickcheck.random.SourceOfRandomness; 

import java.util.ArrayList; 
import java.util.List; 

public class ListGenerator extends Generator<List<Integer>> { 

    private static final int MAX_VALUE = 100; 
    private static final GenerationStatus.Key<Integer> PREVIOUS_KEY = new GenerationStatus.Key<>("previous", Integer.class); 

    @SuppressWarnings("unchecked") 
    public ListGenerator() { 
     super((Class<List<Integer>>) (Class) List.class); 
    } 

    public List<Integer> generate(SourceOfRandomness sourceOfRandomness, GenerationStatus generationStatus) { 
     List<Integer> result = new ArrayList<>(); 

     int previous = generationStatus.valueOf(PREVIOUS_KEY).orElse(MAX_VALUE); 
     int current = sourceOfRandomness.nextInt(previous); 

     if (current > 0) { 
      result.add(current); 

      generationStatus.setValue(PREVIOUS_KEY, current); 
      Generator<List<Integer>> listGen = gen().make(ListGenerator.class); 
      result.addAll(listGen.generate(sourceOfRandomness, generationStatus)); 
      generationStatus.setValue(PREVIOUS_KEY, null); 
     } 

     return result; 
    } 
} 

Answer 2

Wie über Sie erzeugen eine (begrenzte) Liste der Werte in den Baum zu setzen, und bilden den Baum von diesen Werten . Dann wissen Sie sicher, dass die Struktur begrenzt ist.

Sie sollten darauf achten, den Baum auszugleichen, falls der Aufruf von add sequentiell einen stark unausgeglichenen Baum erzeugt, aber dies hängt von Ihrer Baumimplementierung ab.

Ähnlich für Helder-Pereiras answer, es gibt keine Notwendigkeit für rekursive Generatoren: Ich würde eine Liste von ganzen Zahlen generieren und die Liste sortieren.