5
votes

Comment créer une structure de données arborescente récursive en Java en utilisant Map ?

J'ai un blocage mental en essayant de créer une structure de données qui suit le modèle:

Map est un bloc de construction principal et T est soit Map soit en tant qu'opérateur de terminal < code> Liste . Est-il possible de construire quelque chose de similaire en Java , cette idée vient de langages fonctionnels comme F # ou Haskell .

J'ai recherché SO mais jusqu'à présent je n'ai rien trouvé qui corresponde à mon idée en Java .

java recursive-datastructures

0 commentaires

4 Réponses :

4
votes

Oui: vous pouvez faire quelque chose comme ceci:

public abstract class T {
...
}
public class NonTerminal extends T {
    private Map<String,T> map = new HashMap<>();
...
}
public class Terminal extends T {
    private List<String> list;
---
}

2 commentaires

J'irais avec une interface plutôt qu'une classe abstraite. Il n'est pas nécessaire de limiter l'héritage pour cela.

J'ajouterais un constructeur privé à la classe abstraite et placerais les sous-classes en tant que classes imbriquées statiques pour le faire ressembler à un type de données algébrique.

3
votes

Recréer des éléments de programmation fonctionnelle en Java n'est pas vraiment une bonne idée (du moins pas en Java 8, je ne connais pas Java 11).

Vous pouvez faire quelque chose comme ceci:

class EitherMapOrList {
    private Map<String, EitherMapOrList> map;
    private List<String> list;

    public EitherMapOrList(Map<String, EitherMapOrList> map) {
        this.map = map;
    }

    public EitherMapOrList(List<String> list) {
        this.list = list;
    }
    // you can remove the optionals here and use null directly.
    public Optional<Map<String, EitherMapOrList>> getMap() {
        return Optional.ofNullable(map);
    }

    public Optional<List<String>> getList() {
        return Optional.ofNullable(list);
    }
}

Et puis créez une Map .

Mais j'imagine que ce serait pénible d'utiliser cette chose en Java.

0 commentaires

2
votes

Si vous voulez traduire haskell

class Map<T> {
    String key;
    T value;
    Map<T> left;
    Map<T> right;
}

en java, vous pouvez utiliser:

data Map a = Branch { key :: String, value :: a, left :: Map a, right :: Map a} | MapNul

vous n'avez pas besoin de MapNul en java car vous pouvez utiliser null à la place.

0 commentaires

3
votes

Vous pouvez utiliser une seule Map où la valeur peut être une interface de marqueur avec deux implémentations

public List<String> getValues(String key) {
    KeyOrValue keyOrValue;
    List<String> values = null;
    do {
        keyOrValue = map.get(key);
        if(keyOrValue instanceof Key) {
            // is a key, so iterate further
            key = ((Key) keyOrValue).key;
        } else if(keyOrValue instanceof Value) {
            // is a value, so get the values out and set the key to null to break the loop
            values = ((Value) keyOrValue).values;
            key = null;
        }
    } while(key != null);

    // return the values, may be null due to nothing being found
    return values;
}

Vous pouvez alors simplement créer un méthode de recherche qui s'appelle de manière récursive puis renvoie la valeur une fois qu'elle a atteint la fin:

private final Map<String, KeyOrValue> map = ...

public List<String> getValues(String key) {
    KeyOrValue keyOrValue = map.get(key);
    if(keyOrValue instanceof Key) {
        // is a key, so use recursion to get the value
        key = ((Key) keyOrValue).key;
        return getValues(key);
    } else if(keyOrValue instanceof Value) {
        // is a value, so just return the value it holds
        return ((Value) keyOrValue).values;
    } else {
        // no mapping was found for "key"
        return null;
    }
}

Vous pouvez également faire de même sans récursivité:

interface KeyOrValue {}

class Key implements KeyOrValue {
    private String key;
}

class Value implements KeyOrValue {
    private List<String> values;
}

L'interface du marqueur n'est cependant pas vraiment nécessaire, vous pouvez obtenir le même résultat si vous utilisez simplement Map où la valeur peut être un String ou une List puis les vérifications instanceof devraient également être adaptées, mais j'aime l'approche avec un interface plus

0 commentaires