StringStartsWithKeyMap <T>в Java?(соответствует, если ключ начинается с entry.key)

Question

Мне нужен Map, который сравнивает ключи с startsWith(): ключи должны совпадать, если key.startsWith(entry.getKey()).Существует ли существующая реализация этого?

Что я нашел: дерево префиксов ( trie ) - это что-то немного другое, а также radixдерево ( дерево компактных префиксов ) и дерево ПАТРИЦИИ .Я нашел несколько реализаций, но они не определяют методы, такие как navigableMap.floorEntry(key) и navigableMap.higherEntry(key).

Сложная часть использования startsWith() для сравнения ключей - это разрешение конфликтов: если карта содержит записи для обоих "foo"и" foobar ", что должно произойти?

Легко реализовать желаемую функциональность, используя NavigableMap, например, TreeMap, если мы запрещаем конфликтующие клавиши, что-то вроде:

private Map.Entry<String, T> findEntry(String key) {
    Map.Entry<String, T> entry = map.floorEntry(key);
    if (entry != null && key.startsWith(entry.getKey())) {
        return entry;
    }
    return null;
}

Но если мы хотим поддерживать конфликтующие ключи, мы не можем полагаться на floorEntry(), как в коде выше: map.floorEntry("foobaz") найдет запись для "foobar" вместо "foo".Эту проблему можно решить, указав в записи «foobar» указатель на запись «foo» ... И похоже, мы заново изобретаем компактное префиксное дерево поверх TreeMap.

Итак:

1) Существует ли существующая реализация дерева, которое сравнивает ключи узла с startWith?

2) Существует ли реализация дерева компактных префиксов ( Основное дерево ), которое также implements NavigableMap?

и в лучшем случае это будет:

3) некоторый аналог HashMap, поддерживающий StartWith ()матч

UPD

Я понял, что это очень общая проблема: повторная классификация .

Учитывая домадрес (ну, написано в обратном порядке, страна-город-улица-дом-номер), найдите соответствующее почтовое отделение (почтовый индекс).

По IP-адресу найдите соответствующего провайдера.

В общем случае проблема заключается в следующем: по заданному ключу объекта определить класс объекта.Объект идентифицируется ключом из M бит, но только первые N бит, N

Answer 1

Это то, что я использую в данный момент. Он не поддерживает конфликтующие ключи (возникает исключение RuntimeException при их обнаружении).

StringStartsWithKeyMap.java:

import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * A map in which a key matches an entry if key.startsWith(entry.key)
 * @param <T>
 */
public class StringStartsWithKeyMap<T> implements Map<String, T> {
    TreeMap<String, T> map = new TreeMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean containsKey(Object key) {
        return null != findEntry((String)key);
    }

    @Override
    public boolean containsValue(Object value) {
        return map.containsValue(value);
    }

    @Override
    public T get(Object key) {
        Entry<String, T> e = findEntry((String) key);
        return e == null ? null : e.getValue();
    }

    @Override
    public T put(String key, T value) {
        if (map.containsKey(key)) {
            return map.put(key, value);
        } else if (null == findEntry(key) && null == findHigherEntry(key)) {
            return map.put(key, value);
        }
        throw new RuntimeException("Conflicting keys: \""+key+"\" after "+findEntry(key)+" or before "+findHigherEntry(key));
    }

    @Override
    public T remove(Object key) {
        return map.remove(key);
    }

    @Override
    public void putAll(Map<? extends String, ? extends T> m) {
        m.forEach(this::put);
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public Set<String> keySet() {
        return map.keySet();
    }

    @Override
    public Collection<T> values() {
        return map.values();
    }

    @Override
    public Set<Entry<String, T>> entrySet() {
        return map.entrySet();
    }

    public StringStartsWithKeyMap<T> putSameValueFor(T value, String... keys) {
        for (String k : keys) {
            put(k, value);
        }
        return this;
    }
    public StringStartsWithKeyMap<T> putSameValueFor(T value, Iterable<String> keys) {
        for (String k : keys) {
            put(k, value);
        }
        return this;
    }
    private Map.Entry<String, T> findEntry(String key) {
        Map.Entry<String, T> entry = map.floorEntry(key);
        if (entry != null && key.startsWith(entry.getKey())) {
            return entry;
        }
        return null;
    }
    private Map.Entry<String, T> findHigherEntry(String key) {
        Map.Entry<String, T> entry = map.higherEntry(key);
        if (entry != null && entry.getKey().startsWith(key)) {
            return entry;
        }
        return null;
    }
}

и тесты:

StringStartsWithKeyMapTest.java:

import org.junit.Test;

import java.util.Arrays;
import java.util.Map;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

public class StringStartsWithKeyMapTest {

    @Test
    public void sizeTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.size(), is(3));
        assertThat(map0.size(), is(0));
    }

    @Test
    public void isEmptyTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.isEmpty(), is(false));
        assertThat(map0.isEmpty(), is(true));
    }

    @Test
    public void containsKeyTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.containsKey("foo"), is(true));
        assertThat(map3.containsKey("foobar"), is(true));
        assertThat(map3.containsKey("quux"), is(false));
        assertThat(map3.containsKey("quuxfoo"), is(false));
        assertThat(map0.containsKey("foo"), is(false));
    }

    @Test
    public void containsValueTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.containsValue(1), is(true));
        assertThat(map3.containsValue(1000), is(false));
        assertThat(map0.containsValue(1), is(false));
    }

    @Test
    public void getTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map3.get("foo"), is(1));
        assertThat(map3.get("foobar"), is(1));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baraboo"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("bah"), is((Integer) null));
        assertThat(map0.get("foo"), is((Integer) null));
        assertThat(map0.get(null), is((Integer) null));
    }

    @Test
    public void putTest() {
        Map<String, Integer> map3 = makeMap3();
        map3.put("qux",100);
        assertThat(map3.get("qux"), is(100));
        map3.put("foo",200);
        assertThat(map3.get("foo"), is(200));
        try {
            map3.put("foobar",6);
            assertThat(true, is(false));
        } catch (RuntimeException re) {
        }
        try {
            map3.put("fo",60);
            assertThat(true, is(false));
        } catch (RuntimeException re) {
        }
    }

    @Test
    public void removeTest() {
        Map<String, Integer> map3 = makeMap3();
        map3.remove("foo");
        map3.remove("baraboo");
        assertThat(map3.size(), is(2));
        assertThat(map3.get("foo"), is((Integer)null));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("baraboo"), is(2)); // need exact match for removal
    }

    @Test
    public void putAllTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map3a = makeMap3a();
        map3.putAll(map3a);
        assertThat(map3a.size(), is(3));
        assertThat(map3.size(), is(5));
        assertThat(map3.get("foo"), is(100));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("corge"), is(5));
        assertThat(map3.get("grault"), is(6));
        assertThat(map3.get("corgegrault"), is(5));
    }

    @Test
    public void clearTest() {
        Map<String, Integer> map3 = makeMap3();
        assertThat(map3.get("foo"), is(1));
        assertThat(map3.get("foobar"), is(1));
        map3.clear();
        assertThat(map3.get("foo"), is((Integer) null));
        assertThat(map3.get("foobar"), is((Integer) null));
        assertThat(map3.containsKey("foo"), is(false));
        assertThat(map3.containsValue(1), is(false));
        assertThat(map3.size(), is(0));
    }

    @Test
    public void keySetTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map0.keySet().isEmpty(), is(true));
        assertThat(map0.keySet().contains("foo"), is(false));
        assertThat(map3.keySet().size(), is(3));
        assertThat(map3.keySet().contains("foo"), is(true));
    }

    @Test
    public void valuesTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map0.values().isEmpty(), is(true));
        assertThat(map3.values().size(), is(3));
        assertThat(map3.values().contains(1), is(true));
        assertThat(map3.values().contains(2), is(true));
        assertThat(map3.values().contains(3), is(true));
    }

    @Test
    public void entrySetTest() {
        Map<String, Integer> map3 = makeMap3();
        Map<String, Integer> map0 = makeMap0();
        assertThat(map0.entrySet().isEmpty(), is(true));
        assertThat(map3.entrySet().size(), is(3));
    }

    @Test
    public void putSameValueForTest() {
        StringStartsWithKeyMap<Integer> map3 = makeMap3();
        map3.putSameValueFor(400,"foo","corge","grault");
        assertThat(map3.size(), is(5));
        assertThat(map3.get("foo"), is(400));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("corge"), is(400));
        assertThat(map3.get("grault"), is(400));
        assertThat(map3.get("corgegrault"), is(400));
    }

    @Test
    public void putSameValueForTest2() {
        StringStartsWithKeyMap<Integer> map3 = makeMap3();
        map3.putSameValueFor(400, Arrays.asList("foo","corge","grault"));
        assertThat(map3.size(), is(5));
        assertThat(map3.get("foo"), is(400));
        assertThat(map3.get("bar"), is(2));
        assertThat(map3.get("baz"), is(3));
        assertThat(map3.get("corge"), is(400));
        assertThat(map3.get("grault"), is(400));
        assertThat(map3.get("corgegrault"), is(400));
    }

    private StringStartsWithKeyMap<Integer> makeMap3() {
        StringStartsWithKeyMap<Integer> res = new StringStartsWithKeyMap<>();
        res.put("foo",1);
        res.put("bar",2);
        res.put("baz",3);
        return res;
    }

    private StringStartsWithKeyMap<Integer> makeMap0() {
        StringStartsWithKeyMap<Integer> res = new StringStartsWithKeyMap<>();
        return res;
    }
    private StringStartsWithKeyMap<Integer> makeMap3a() {
        StringStartsWithKeyMap<Integer> res = new StringStartsWithKeyMap<>();
        res.put("foo",100);
        res.put("corge",5);
        res.put("grault",6);
        return res;
    }
}

Answer 2

Насколько я знаю, для этого нет реализации по умолчанию, но вы можете легко написать это самостоятельно:

    List<String> matchingKeys = map.keySet().stream().
            filter(key -> key.startsWith(prefix)).
            collect(Collectors.toList());

Когда у вас есть соответствующие ключи, вы можете настроить, что делать.Может быть, что-то вроде этого:

    for(Map.Entry<String, Object> entry : map.entrySet()) {
        if(matchingKeys.indexOf(entry.getKey()) != -1) {
            return entry;
        }
    }

Или другой подход:

Optional<Entry<String, T>> matchingEntry = map.entrySet().stream().
        filter((k) -> k.getKey().startsWith(prefix)).findFirst();

if(matchingEntry.isPresent()) {
    return matchingEntry.get();
}

return null;