Мои исходные данные – массив структур с географической информацией:
struct Geo {
std::string airport; // level: 1
std::string city; // level: 2
std::string province; // level: 3
std::string nation; // level: 4
std::uint8_t subarea; // level: 5 | values: 11, 12, 13, 14, 21, 22, 23, 31, 32, 33, 34
std::uint8_t area; // level: 6 | values: 1, 2, 3
};
Надо много (и желательно быстро) отвечать на запрос «принадлежит ли Needle к Haystack». Где Needle всегда более специфично нежели Haystack, например:
belongsTo(Needle=City{Munich}, Haystack=Subarea{21}) -> true
Я думаю посортировать данные иерархически:
std::vector<Geo> geos = allGeos();
std::sort(geos.begin(), geos.end(),
[](const Geo& lhs, const Geo& rhs) {
int areaCmp = lhs.area - rhs.area;
if (areaCmp != 0)
return areaCmp < 0;
int subareaCmp = lhs.subarea - rhs.subarea;
if (subareaCmp != 0)
return subareaCmp < 0;
int countryCmp = lhs.nation.compare(rhs.nation);
if (countryCmp != 0)
return countryCmp < 0;
int provinceCmp = lhs.province.compare(rhs.province);
if (provinceCmp != 0)
return provinceCmp < 0;
int cityCmp = lhs.city.compare(rhs.city);
if (cityCmp != 0)
return cityCmp < 0;
return lhs.airport.compare(rhs.airport) < 0;
}
);
И потом использовать bsearch() по партициям типа Needle на пути от Haystack. Т.е (псевдокод):
int level = levelOf(Haystack);
std::vector stack{ Range{geos.begin(), geos.end()} };
while (!stack.empty()) {
Range partition = stack.back();
if (partition.empty()) {
stack.pop_back();
++level;
}
// depth-first
if (level > levelOf(Needle)) {
iterator begin = partition.begin();
iterator end = lower_bound(begin, partition.end(), valueOf(*begin, level));
stack.push(Range{begin, end})
level -= 1;
continue;
}
// level == levelOf(Needle)
if (bsearch(partition, Needle))
return true;
// trim parent's begin()
stack.pop_back();
stack.back().begin() = partition.end();
++level;
}
Где level обозначает поле из Geo, соответсвенно комментарию.
Вопрос такой: может есть алгоритм (или структура данных) лучше подходящая под цель?
