1 /*
2 exact duplicate point filter utility.
3
4 Copyright (C) 2002-2014 Robert Lipe, robertlipe+source@gpsbabel.org
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19
20 */
21
22 #include <cstdio> // for sprintf
23 #include <cstdlib> // for qsort
24 #include <cstring> // for memset, strncpy
25
26 #include <QtCore/QDateTime> // for QDateTime
27 #include <QtCore/QtGlobal> // for foreach
28
29 #include "defs.h"
30 #include "duplicate.h"
31 #include "src/core/datetime.h" // for DateTime
32
33
34 #if FILTERS_ENABLED
35
addnode(btree_node * tree,btree_node * newnode,btree_node ** oldnode)36 DuplicateFilter::btree_node* DuplicateFilter::addnode(btree_node* tree, btree_node* newnode, btree_node** oldnode)
37 {
38 btree_node* last = nullptr;
39
40 if (*oldnode) {
41 *oldnode = nullptr;
42 }
43
44 if (!tree) {
45 return (newnode);
46 }
47
48 btree_node* tmp = tree;
49
50 while (tmp) {
51 last = tmp;
52 if (newnode->data < tmp->data) {
53 tmp = tmp->right;
54 } else if (newnode->data > tmp->data) {
55 tmp = tmp->left;
56 } else {
57 if (oldnode) {
58 *oldnode = tmp;
59 }
60 return (nullptr);
61 }
62 }
63
64 if (newnode->data < last->data) {
65 last->right = newnode;
66 } else {
67 last->left = newnode;
68 }
69
70 return (tree);
71 }
72
free_tree(btree_node * tree)73 void DuplicateFilter::free_tree(btree_node* tree)
74 {
75 if (tree->left) {
76 free_tree(tree->left);
77 }
78 if (tree->right) {
79 free_tree(tree->right);
80 }
81 xfree(tree);
82 }
83
84 /*
85
86 It looks odd that we have different comparisons for date and index.
87 If exported if a < b return 1
88 if index if a < b return -1
89
90 The reason is that we want to sort in reverse order by date, but forward
91 order by index. So if we have four records:
92
93 date index
94 June 24 0
95 June 25 1
96 June 25 2
97 June 24 3
98
99 we want to sort them like this:
100
101 date index
102 June 25 1
103 June 25 2
104 June 24 0
105 June 24 3
106
107 Thus, the first point we come across is the latest point, but if we
108 have two points with the same export date/time, we will first see the
109 one with the smaller index (i.e. the first of those two points that we
110 came across while importing waypoints.)
111
112 In the (common) case that we have no exported dates, the dates will all
113 be zero so the sort will end up being an expensive no-op (expensive
114 because, sadly, quicksort can be O(n^2) on presorted elements.)
115 */
116
117
compare(const void * a,const void * b)118 int DuplicateFilter::compare(const void* a, const void* b)
119 {
120 const wpt_ptr* wa = (wpt_ptr*)a;
121 const wpt_ptr* wb = (wpt_ptr*)b;
122
123 if (wa->wpt->gc_data->exported < wb->wpt->gc_data->exported) {
124 return 1;
125 } else if (wa->wpt->gc_data->exported > wb->wpt->gc_data->exported) {
126 return -1;
127 }
128
129 /* If the exported dates are the same, sort by index. */
130 if (wa->index < wb->index) {
131 return -1;
132 } else if (wa->index > wb->index) {
133 return 1;
134 }
135
136 /* If index and date are the same, it's the same element. */
137 return 0;
138
139 }
140
process()141 void DuplicateFilter::process()
142 {
143 btree_node* newnode, * btmp, * sup_tree = nullptr;
144 btree_node* oldnode = nullptr;
145 unsigned long crc = 0;
146 struct {
147 char shortname[32];
148 char lat[13];
149 char lon[13];
150 } dupe;
151 Waypoint* delwpt = nullptr;
152
153 int ct = waypt_count();
154
155 auto* htable = (wpt_ptr*) xmalloc(ct * sizeof(wpt_ptr));
156 wpt_ptr* bh = htable;
157
158 int i = 0;
159 foreach (Waypoint* waypointp, *global_waypoint_list) {
160 bh->wpt = waypointp;
161 bh->index = i;
162 i ++;
163 bh ++;
164 }
165 qsort(htable, ct, sizeof(*htable), compare);
166
167 for (i=0; i<ct; i++) {
168 auto waypointp = htable[i].wpt;
169
170 memset(&dupe, '\0', sizeof(dupe));
171
172 if (snopt) {
173 strncpy(dupe.shortname, CSTRc(waypointp->shortname), sizeof(dupe.shortname) - 1);
174 }
175
176 if (lcopt) {
177 /* let sprintf take care of rounding */
178 sprintf(dupe.lat, "%11.4f", waypointp->latitude);
179 sprintf(dupe.lon, "%11.4f", waypointp->longitude);
180 /* The degrees2ddmm stuff is a feeble attempt to
181 * get everything rounded the same way in a precision
182 * that's "close enough" for determining duplicates.
183 */
184 sprintf(dupe.lat, "%11.3f", degrees2ddmm(waypointp->latitude));
185 sprintf(dupe.lon, "%11.3f", degrees2ddmm(waypointp->longitude));
186
187 }
188
189 crc = get_crc32(&dupe, sizeof(dupe));
190
191 newnode = (btree_node*)xcalloc(sizeof(btree_node), 1);
192 newnode->data = crc;
193 newnode->wpt = waypointp;
194
195 btmp = addnode(sup_tree, newnode, &oldnode);
196
197 if (btmp == nullptr) {
198 delete delwpt;
199 if (correct_coords && oldnode && oldnode->wpt) {
200 oldnode->wpt->latitude = waypointp->latitude;
201 oldnode->wpt->longitude = waypointp->longitude;
202 }
203 delwpt = waypointp;
204 waypt_del(waypointp); /* collision */
205 xfree(newnode);
206 if (purge_duplicates && oldnode) {
207 if (oldnode->wpt) {
208 waypt_del(oldnode->wpt);
209 delete oldnode->wpt;
210 oldnode->wpt = nullptr;
211 }
212 }
213
214 } else {
215 sup_tree = btmp;
216 }
217 }
218
219 delete delwpt;
220
221 xfree(htable);
222 if (sup_tree) {
223 free_tree(sup_tree);
224 }
225 }
226
227 #endif
228