Почему `floorEntry` и другие методы недоступны в PatriciaTrie?

Question

При реализации структуры ip-lookup я пытался поддерживать набор ключей в структуре типа trie, которая позволяет мне искать «пол» ключа (то есть самый большой ключ, который меньше или равен данный ключ). Я решил использовать Apache Collections 4 PatriciaTrie, но, к сожалению, я обнаружил, что floorEntry и связанные с ним методы не являются public. Мое текущее «грязное» решение вынуждают их с отражением (в Scala):

val pt = new PatriciaTrie[String]() 
val method = pt.getClass.getSuperclass.getDeclaredMethod("floorEntry", classOf[Object]) 
method.setAccessible(true) 
// and then for retrieving the entry for floor(key) 
val entry = method.invoke(pt, key).asInstanceOf[Entry[String, String]] 

Есть ли чистый способ иметь такую ​​же функциональность? Почему эти методы не являются общедоступными?

Answer 1

Почему эти методы не являются общедоступными, я не знаю. (Возможно, это потому, что вы можете добиться того, чего хотите, с общим API Map).

Вот способ, чтобы выполнить ваше требование:

PatriciaTrie<String> trie = new PatriciaTrie<>(); 
trie.put("a", "a"); 
trie.put("b", "b"); 
trie.put("d", "d"); 

String floorKey = trie.headMap("d").lastKey(); // d 

Согласно документации, это очень эффективно, так как это зависит от количества битов самого большого ключа синтаксического дерева.

EDIT: В соответствии с @ kaktusito свой комментарий, приведенный выше код имеет проблему ограничений: headMap() возвращает представление карты, чьи ключи строго ниже заданного ключа. Это означает, что, например, для вышеуказанного примера trie.headMap("b").lastKey() вернет "a" вместо "b" (при необходимости).

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

String cFloorKey = trie.headMap("c" + "\uefff").lastKey(); // b 

String dFloorKey = trie.headMap("d" + "\uefff").lastKey(); // d 

Теперь все работает, как и следовало ожидать, так как \uefff самый высокий юникода характер. На самом деле, поиск key + "\uefff", независимо от того, key есть, всегда будет возвращать key, если он принадлежит к trie или элементу, который непосредственно перед key, если key нет в trie.

Теперь этот трюк работает для ключей String, но также доступен для других типов. то есть для Integer ключей можно найти key + 1, для Date ключей можно добавить 1 миллисекунду и т.д.