如果我们希望加入一条新的街道，应用程序必须存储街道的坐标并计算其边界盒。
- Street street;
- mco_rect_t wr;
- wr.l.x = DOUBLE_MAX;
- wr.l.y = DOUBLE_MAX;
- wr.r.x = DOUBLE_MIN;
- wr.r.y = DOUBLE_MIN;
- Street_new(trans, &street);
- Street_points_alloc(&street, n_points);
- for (i = 0; i < n_points; i++)
- {
- if (points[i].latitude < wr.l.latitude) {
- wr.l.latitude = points[i].latitude;
- }
- if (points[i].longitude < wr.l.longitude) {
- wr.l.longitude = points[i].longitude;
- }
- if (points[i].latitude > wr.r.latitude) {
- wr.r.latitude = points[i].latitude;
- }
- if (points[i].longitude > wr.r.longitude) {
- wr.r.longitude = points[i].longitude;
- }
- Street_points_put(&street, i, &points[i]);
- }
- Street_wrap_rect_put(&street, &wr);
|
如果用户搜索一个位置，地图应用程序将结果（街道）在窗口中表示为一个坐标为||的地图长方形。
- mco_rect_t r;
- mco_cursor_t c;
- MCO_RET rc;
- r.l.x = min_longitude;
- r.l.y = min_latitude;
- r.r.x = max_longitude;
- r.r.y = max_latitude;
- if (Street_streets_idx_search(trans, MCO_EQ, &c, (double*)&r) == MCO_S_OK)
- {
- for (; rc == MCO_S_OK; rc = mco_cursor_next(trans, &c))
- {
- Street street;
- Street_from_cursor(trans, &c, &street);
- // display it
- }
- }
|
Patricia trie
B树可以利用指定的前缀来定位关键字，例如，寻找以名字以“AAA”开头的公司。然而，一些应用程序必须搜索代表着一个特定值最长前缀的关键字。B树可以实现这种需求，但必须从最长的前缀开始进行多次迭代并且查询不同的给定值前缀。
一种更加有效的前缀查找索引是用于查询字母-数字编码的实践算法，即通常所说的Patricia trie。Patricia trie是二叉树的一种变形，通常用于电话路由以及IP过滤。在第一种情况中，给定接入电话以及一张带有已知前缀的接线员表，应用程序必须选择正确的接线员接到该电话。在第二种情况下，给定了有效/拒绝域的IP掩码，收到的(一个)HTTP请求应被分类为接受、拒绝、转发，等等。下面的数据库模式定义了一张路由表，带有一个由位向量表示的掩码。
- class Route
- {
- Vector<bool> dest;
- uint4 gateway;
- uint4 interf;
- uint2 metric;
- unique patricia by_dest;
- };
|
