You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

duplicate.cc 6.3KB

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