Как создать рекурсивную древовидную структуру данных в Java с помощью Map? - PullRequest
Новая
       7

Как создать рекурсивную древовидную структуру данных в Java с помощью Map?

0 голосов
/ 18 февраля 2019

У меня есть блок разума, когда я пытаюсь создать структуру данных, которая соответствует шаблону:

Map<String, T> является основным строительным блоком, а T является либо Map<String, T>, либо оператором терминала * 1006.*.Можно ли построить что-то подобное в Java, эта идея исходит от функциональных языков, подобных F# или Haskell -подобных.

Я искал SO, но до сих пор не смог найти ничего, что соответствовало бымоя идея в Java.

Ответы [ 4 ]

0 голосов
/ 18 февраля 2019

Вы можете использовать только один Map<String, KeyOrValue>, где значением может быть интерфейс маркера с двумя реализациями 

interface KeyOrValue {}

class Key implements KeyOrValue {
    private String key;
}

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

Затем вы можете просто создать метод поиска, который рекурсивно вызывает себя, а затем возвращает значение один раз.он достиг конца: 

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;
    }
}

Вы можете сделать то же самое и без рекурсии: 

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;
}

Интерфейс маркера на самом деле не нужен, но вы можете получить то же самоерезультат, если вы просто используете Map<String, Object>, где значение может быть либо String, либо List<String>, и тогда проверки instanceof также должны быть адаптированы, но мне нравится подход с добавлением interface

0 голосов
/ 18 февраля 2019

Воссоздание функционального программирования в Java не очень хорошая идея (по крайней мере, не в Java 8, я не знаю о Java 11).

Вы можете сделать что-то вроде этого: 

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);
    }
}

А затем создайте Map<String, EitherMapOrList>.

Но я бы подумал, что будет неудобно использовать эту вещь в Java.

0 голосов
/ 18 февраля 2019

Если вы хотите перевести haskell 

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

на Java, вы можете использовать: 

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

вам не нужно MapNul в Java, потому что вы можете использовать nullвместо этого.

0 голосов
/ 18 февраля 2019

Да: вы можете сделать что-то вроде этого: 

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;
---
}
...