Я предполагаю, что вы хотели бы вставить входную версию в двоичное дерево поиска (BST). Это позволит вам найти запрошенные версии за O (log (n)) время
Это основные шагидля достижения вашей цели: 1) Используйте реализацию Java BST.2) Реализовать String Comparator, чтобы определить, какая версия больше.3) Добавить элементы в дерево.4) Печать элементов в вашем любимом формате.
1) Я использовал эту реализацию: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/code/BST.java
2) Я реализовал компаратор, который отображает строки версии в целые числа.Это позволяет мне сравнивать закодированные числовые значения версий
открытый класс VersionsComparator реализует Comparator {
@Override
public int compare(String s1, String s2) {
String versionPattern = "(\\d+)[.](\\d+)[.](\\d+)[.](\\d+)";
final int numOfMatchers = 2;
Pattern pattern = Pattern.compile(versionPattern);
Matcher[] matchers = new Matcher[numOfMatchers];
matchers[0] = pattern.matcher(s1);
matchers[1] = pattern.matcher(s2);
for (Matcher matcher : matchers) {
if(!matcher.matches()) {
throw new RuntimeException("Invalid version format");
}
}
int version1 = parseVersion(s1, matchers[0]);
int version2 = parseVersion(s2, matchers[1]);
return version2 - version1;
}
private int parseVersion(String version, Matcher matcher) {
int length = matcher.groupCount();
int[] v = new int[length];
int parsedVersion = 0;
for (int i = 0; i < length; i++) {
v[i] = Integer.parseInt(matcher.group(length - i));
parsedVersion += Math.pow(10, i) * v[i];
}
return parsedVersion;
}
}
3) Добавление всех строк в дерево:
private static BST getBST(String[] strArr) {
BST<String> bst = new BST<String>();
Arrays.asList(strArr).stream().forEach(str -> bst.insert(str));
return bst;
}
4) Печать элементов дерева:
Я добавил свой собственный стиль печати, добавив 2 метода в класс BST:
public void inOrderTraversalWithHierarchy() {
inOrderWithHierarchyHelper(root, 0);
}
private void inOrderWithHierarchyHelper(Node r, int level) {
if (r != null) {
inOrderWithHierarchyHelper(r.left, level + 1);
for (int i = 0; i < level; System.out.print("|"), i++);
System.out.println(r);
inOrderWithHierarchyHelper(r.right, level + 1);
}
}
Это код класса клиента:
открытый класс CodeToMakeTreeStructureFromVersionNames {
public class VersionsComparator implements Comparator<String>{
@Override
public int compare(String s1, String s2) {
String versionPattern = "(\\d+)[.](\\d+)[.](\\d+)[.](\\d+)";
final int numOfMatchers = 2;
Pattern pattern = Pattern.compile(versionPattern);
Matcher[] matchers = new Matcher[numOfMatchers];
matchers[0] = pattern.matcher(s1);
matchers[1] = pattern.matcher(s2);
for (Matcher matcher : matchers) {
if(!matcher.matches()) {
throw new RuntimeException("Invalid version format");
}
}
int version1 = parseVersion(s1, matchers[0]);
int version2 = parseVersion(s2, matchers[1]);
return version2 - version1;
}
private int parseVersion(String version, Matcher matcher) {
int length = matcher.groupCount();
int[] v = new int[length];
int parsedVersion = 0;
for (int i = 0; i < length; i++) {
v[i] = Integer.parseInt(matcher.group(length - i));
parsedVersion += Math.pow(10, i) * v[i];
}
return parsedVersion;
}
}
public static void main(String[] args) {
String[] versions = {"1.0.0.0","1.5.0.0","1.5.0.1","1.5.0.2","1.5.0.3","1.5.0.4","1.5.0.7","1.6.0.0","1.6.0.1","1.13.0.0","1.13.1.0","1.13.1.1","1.13.1.2","1.13.1.3","1.13.1.4","1.22.0.0","1.22.1.0","1.22.1.1"};
printBST(getBST(versions));
}
private static BST<String> getBST(String[] strArr) {
BST<String> bst = new BST<String>();
Arrays.asList(strArr).stream().forEach(str -> bst.insert(str));
return bst;
}
private static void printBST(BST bst) {
bst.inOrderTraversalWithHierarchy();
}
}