/**
 * Navit, a modular navigation system.
 * Copyright (C) 2005-2017 Navit Team
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * version 2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA  02110-1301, USA.
 */

/** @file
 * @brief Contains code related to processing traffic messages into map items.
 *
 * Currently the only map items supported are traffic distortions. More may be added in the future.
 *
 * Traffic distortions are used by Navit to route around traffic problems.
 */

#include <string.h>
#include <stdlib.h>
#include <time.h>

#ifdef _POSIX_C_SOURCE
#include <sys/types.h>
#endif
#include <sys/time.h>
#include "glib_slice.h"
#include "config.h"
#include "navit.h"
#include "util.h"
#include "coord.h"
#include "item.h"
#include "map.h"
#include "mapset.h"
#include "route_protected.h"
#include "route.h"
#include "transform.h"
#include "xmlconfig.h"
#include "traffic.h"
#include "plugin.h"
#include "fib.h"
#include "event.h"
#include "callback.h"
#include "vehicleprofile.h"
#include "debug.h"

#undef TRAFFIC_DEBUG

/** Flag to indicate new messages have been received */
#define MESSAGE_UPDATE_MESSAGES 1 << 0

/** Flag to indicate segments have changed */
#define MESSAGE_UPDATE_SEGMENTS 1 << 1

/** The penalty applied to an off-road link */
#define PENALTY_OFFROAD 8

/** The penalty applied to segments with non-matching attributes */
#define PENALTY_SEGMENT_MATCH 4

/** The maximum penalty applied to points with non-matching attributes */
#define PENALTY_POINT_MATCH 24

/** Flag to indicate expired messages should be purged */
#define PROCESS_MESSAGES_PURGE_EXPIRED 1 << 0

/** Flag to indicate the message store should not be exported */
#define PROCESS_MESSAGES_NO_DUMP_STORE 1 << 1

/** The lowest order of items to consider */
#define ROUTE_ORDER 18

/** The buffer zone around the enclosing rectangle used in route calculations, absolute distance */
#define ROUTE_RECT_DIST_ABS 1000

/** The buffer zone around the enclosing rectangle used in route calculations, relative to rect size */
#define ROUTE_RECT_DIST_REL 0

/** Time slice for idle loops, in milliseconds */
#define TIME_SLICE 40

/**
 * @brief Private data shared between all traffic instances.
 */
struct traffic_shared_priv {
    GList * messages;           /**< Currently active messages */
    GList * message_queue;      /**< Queued messages, waiting to be processed */
    // TODO messages by ID?                 In a later phase…
};

/**
 * @brief A traffic plugin instance.
 *
 * If multiple traffic plugins are loaded, each will have its own `struct traffic` instance.
 */
struct traffic {
    NAVIT_OBJECT
    struct navit *navit;         /**< The navit instance */
    struct traffic_shared_priv *shared; /**< Private data shared between all instances */
    struct traffic_priv *priv;   /**< Private data used by the plugin */
    struct traffic_methods meth; /**< Methods implemented by the plugin */
    struct callback * callback;  /**< The callback function for the idle loop */
    struct event_timeout * timeout; /**< The timeout event that triggers the loop function */
    struct callback *idle_cb;    /**< Idle callback to process new messages */
    struct event_idle *idle_ev;  /**< The pointer to the idle event */
    struct mapset *ms;           /**< The mapset used for routing */
    struct route *rt;            /**< The route to notify of traffic changes */
    struct map *map;             /**< The traffic map, in which traffic distortions are stored */
};

struct traffic_location_priv {
    struct coord_geo * sw;             /*!< Southwestern corner of rectangle enclosing all points.
	                                    *   Calculated by Navit from the points of the location. */
    struct coord_geo * ne;             /*!< Northeastern corner of rectangle enclosing all points.
	                                    *   Calculated by Navit from the points of the location. */
};

struct traffic_message_priv {
    struct item **items;        /**< The items for this message in the traffic map */
};

/**
 * @brief Private data for the traffic map.
 *
 * If multiple traffic plugins are loaded, the map is shared between all of them.
 */
struct map_priv {
    GList * items;              /**< The map items */
    // TODO items by start/end coordinates? In a later phase…
};

/**
 * @brief Implementation-specific map rect data
 */
struct map_rect_priv {
    struct map_priv *mpriv;     /**< The map to which this map rect refers */
    struct item *item;          /**< The current item, i.e. the last item returned by the `map_rect_get_item` method */
    GList * next_item;          /**< `GList` entry for the next item to be returned by `map_rect_get_item` */
};

/**
 * @brief Message-specific map private data
 *
 * This structure is needed to handle segments referenced by multiple messages. When a message changes,
 * is cancelled or expires, the data of the remaining messages is used to determine the new attributes
 * for the segment.
 */
struct item_msg_priv {
    char * message_id;           /**< Message ID for the associated message */
    int speed;                   /**< The expected speed in km/h (`INT_MAX` for unlimited, 0 indicates
	                              *   that the road is closed) */
    int delay;                   /**< Expected delay for this segment, in 1/10 s */
    struct attr ** attrs;        /**< Additional attributes to add to the segment */
};

/**
 * @brief Implementation-specific item data for traffic map items
 */
struct item_priv {
    struct map_rect_priv * mr;  /**< The private data for the map rect from which the item was obtained */
    struct attr **attrs;        /**< The attributes for the item, `NULL`-terminated */
    struct coord *coords;       /**< The coordinates for the item */
    int coord_count;            /**< The number of elements in `coords` */
    int refcount;               /**< How many references to this item exist */
    GList * message_data;       /**< Message-specific data, see `struct item_msg_priv` */
    struct attr **next_attr;    /**< The next attribute of `item` to be returned by the `item_attr_get` method */
    unsigned int
    next_coord;    /**< The index of the next coordinate of `item` to be returned by the `item_coord_get` method */
    struct route *rt;           /**< The route to which the item has been added */
};

/**
 * @brief Data for segments affected by a traffic message.
 *
 * Speed can be specified in three different ways:
 * \li `speed` replaces the maximum speed of the segment, if lower
 * \li `speed_penalty` subtracts the specified amount from the maximum speed of the segment
 * \li `speed_factor` is the percentage of the maximum speed of the segment to be assumed
 *
 * Where more than one of these values is set, the lowest speed applies.
 */
struct seg_data {
    enum item_type type;         /**< The item type; currently only `type_traffic_distortion` is supported */
    int speed;                   /**< The expected speed in km/h (`INT_MAX` for unlimited, 0 indicates
	                              *   that the road is closed) */
    int speed_penalty;           /**< Difference between expected speed and the posted speed limit of
	                              *   the segment (0 for none); the resulting maximum speed is never
	                              *   less than 5 km/h */
    int speed_factor;            /**< Expected speed expressed as a percentage of the posted limit (100
	                              *   for full speed) */
    int delay;                   /**< Expected delay for all segments combined, in 1/10 s */
    enum location_dir dir;       /**< Directionality */
    int flags;                   /**< Access flags (modes of transportation to which the message applies) */
    struct attr ** attrs;        /**< Additional attributes to add to the segments */
};

struct point_data {
    struct route_graph_point * p; /**< The point in the route graph */
    int score;                   /**< The attribute matching score */
};

/**
 * @brief State for the XML parser.
 *
 * Several members of this struct are used to cache traffic data model objects until they can be
 * incorporated in a message.
 *
 * All `struct traffic_point` members are reset to NULL when the `location` member is set. Likewise, the
 * `si` member is reset to NULL when a new event is added. The `location` and `events` members are reset
 * to NULL when a message is created.
 */
struct xml_state {
    GList * messages;                   /**< Messages read so far */
    GList * tagstack;                   /**< Currently open tags (order is bottom to top) */
    int is_valid;                       /**< Whether `tagstack` represents a hierarchy of elements we recognize */
    int is_opened;                      /**< True if we have just opened an element;
	                                     *   false if child elements have been opened and closed since */
    struct traffic_point * at;          /**< The point for a point location, NULL for linear locations. */
    struct traffic_point * from;        /**< The start of a linear location, or a point before `at`. */
    struct traffic_point * to;          /**< The end of a linear location, or a point after `at`. */
    struct traffic_point * via;         /**< A point between `from` and `to`. Required on ring roads
	                                     *   unless `not_via` is used; cannot be used together with `at`. */
    struct traffic_point * not_via;     /**< A point NOT between `from` and `to`. Required on ring roads
	                                     *   unless `via` is used; cannot be used together with `at`. */
    struct traffic_location * location; /**< The location to which the next message refers. */
    GList * si;                         /**< Supplementary information items for the next event. */
    GList * events;                     /**< The events for the next message. */
};

/**
 * @brief Data for an XML element
 *
 * `names` and `values` are always two separate arrays for this struct, regardless of what is indicated by
 * `XML_ATTR_DISTANCE`.
 */
struct xml_element {
    char * tag_name;             /**< The tag name */
    char ** names;               /**< Attribute names */
    char ** values;              /**< Attribute values (indices correspond to `names`) */
    char * text;                 /**< Character data (NULL-terminated) */
};

static struct seg_data * seg_data_new(void);
static struct item * tm_add_item(struct map *map, enum item_type type, int id_hi, int id_lo,
                                 int flags, struct attr **attrs, struct coord *c, int count, char * id);
#ifdef TRAFFIC_DEBUG
static void tm_dump_item_to_textfile(struct item * item);
#endif
static void tm_destroy(struct map_priv *priv);
static void tm_coord_rewind(void *priv_data);
static void tm_item_destroy(struct item * item);
static struct item * tm_item_ref(struct item * item);
static struct item * tm_item_unref(struct item * item);
static void tm_item_update_attrs(struct item * item, struct route * route);
static int tm_coord_get(void *priv_data, struct coord *c, int count);
static void tm_attr_rewind(void *priv_data);
static int tm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr);
static int tm_type_set(void *priv_data, enum item_type type);
static struct route_graph * traffic_location_get_route_graph(struct traffic_location * this_,
        struct mapset * ms);
static int traffic_location_match_attributes(struct traffic_location * this_, struct item *item);
static int traffic_message_add_segments(struct traffic_message * this_, struct mapset * ms, struct seg_data * data,
                                        struct map *map, struct route * route);
static void traffic_location_populate_route_graph(struct traffic_location * this_, struct route_graph * rg,
        struct mapset * ms);
static void traffic_dump_messages_to_xml(struct traffic * this_);
static void traffic_loop(struct traffic * this_);
static struct traffic * traffic_new(struct attr *parent, struct attr **attrs);
static int traffic_process_messages_int(struct traffic * this_, int flags);
static void traffic_message_dump_to_stderr(struct traffic_message * this_);
static struct seg_data * traffic_message_parse_events(struct traffic_message * this_);
static struct route_graph_point * traffic_route_flood_graph(struct route_graph * rg, struct seg_data * data,
        struct coord * c_start, struct coord * c_dst, struct route_graph_point * start_existing);

static struct item_methods methods_traffic_item = {
    tm_coord_rewind,
    tm_coord_get,
    tm_attr_rewind,
    tm_attr_get,
    NULL,
    NULL,
    NULL,
    tm_type_set,
};

/**
 * @brief Creates a Boolean value from its string representation.
 *
 * If the string equals `true`, `yes` or can be parsed to a nonzero integer, the result is true.
 *
 * If the string equals `false`, `no` or begins with the digit 0 and returns zero when parsed to an
 * integer, the result is false.
 *
 * If NULL is supplied, or if the string does not match any known value, the result is the default value.
 *
 * String comparison is case-insensitive.
 *
 * Since true is always represented by a return value of 1, passing a `deflt` other than 0 or 1 allows
 * the caller to determine if the string could be parsed correctly.
 *
 * @param string The string representation
 * @param deflt The default value to return if `string` is not a valid representation of a Boolean value.
 *
 * @return The corresponding `enum event_class`, or `event_class_invalid` if `string` does not match a
 * known identifier
 */
static int boolean_new(const char * string, int deflt) {
    if (!string)
        return deflt;
    if (!g_ascii_strcasecmp(string, "yes") || !g_ascii_strcasecmp(string, "true") || atoi(string))
        return 1;
    if (!g_ascii_strcasecmp(string, "no") || !g_ascii_strcasecmp(string, "false") || ((string[0] == '0') && !atoi(string)))
        return 0;
    return deflt;
}

/**
 * @brief Creates a new `struct seg_data` and initializes it with default values.
 */
static struct seg_data * seg_data_new(void) {
    struct seg_data * ret = g_new0(struct seg_data, 1);
    ret->type = type_traffic_distortion;
    ret->speed = INT_MAX;
    ret->speed_factor = 100;
    return ret;
}

/**
 * @brief Creates a timestamp from its ISO8601 representation.
 *
 * @param string The ISO8601 timestamp
 *
 * @return The timestamp, or 0 if `string` is NULL.
 */
static time_t time_new(char * string) {
    if (!string)
        return 0;
    return iso8601_to_time(string);
}

/**
 * @brief Whether two `struct seg_data` contain the same data.
 *
 * @return true if `l` and `r` are equal, false if not. Two NULL values are considered equal; a NULL value and a
 * non-NULL value are not.
 */
static int seg_data_equals(struct seg_data * l, struct seg_data * r) {
    struct attr ** attrs;
    struct attr * attr;

    if (!l && !r)
        return 0;
    else if (!l || !r)
        return 1;
    if (l->type != r->type)
        return 0;
    if (l->speed != r->speed)
        return 0;
    if (l->speed_penalty != r->speed_penalty)
        return 0;
    if (l->speed_factor != r->speed_factor)
        return 0;
    if (l->delay != r->delay)
        return 0;
    if (l->dir != r->dir)
        return 0;
    if (l->flags != r->flags)
        return 0;
    if (!l->attrs && !r->attrs)
        return 1;
    if (!l->attrs || !r->attrs)
        return 0;
    /* FIXME this will break if multiple attributes of the same type are present and have different values */
    for (attrs = l->attrs; attrs; attrs++) {
        attr = attr_search(r->attrs, NULL, (*attrs)->type);
        if (!attr || (attr->u.data != (*attrs)->u.data))
            return 0;
    }
    for (attrs = r->attrs; attrs; attrs++) {
        attr = attr_search(l->attrs, NULL, (*attrs)->type);
        if (!attr || (attr->u.data != (*attrs)->u.data))
            return 0;
    }
    return 1;
}

/**
 * @brief Adds message data to a traffic map item.
 *
 * This method checks if the item already has data for the message specified in `msgid`. If so, the
 * existing data is updated, else a new entry is added.
 *
 * Data changes also trigger an update of the affected item’s attributes.
 *
 * @param item The item (its `priv_data` member must point to a `struct item_priv`)
 * @param msgid The message ID
 * @param speed The maximum speed for the segment (`INT_MAX` if none given)
 * @param delay The delay for the segment, in tenths of seconds (0 for none)
 * @param attrs Additional attributes specified by the message
 * @param route The route affected by the changes
 *
 * @return true if data was changed, false if not
 */
static int tm_item_add_message_data(struct item * item, char * msgid, int speed, int delay, struct attr ** attrs,
                                    struct route * route) {
    int ret = 0;
    struct item_priv * priv_data = item->priv_data;
    GList * msglist;
    struct item_msg_priv * msgdata;

    for (msglist = priv_data->message_data; msglist; msglist = g_list_next(msglist)) {
        msgdata = (struct item_msg_priv *) msglist->data;
        if (!strcmp(msgdata->message_id, msgid))
            break;
    }

    if (msglist) {
        /* we have an existing item, update it */
        ret |= ((msgdata->speed != speed) || (msgdata->delay != delay));
        msgdata->speed = speed;
        msgdata->delay = delay;
        /* TODO attrs */
    } else {
        ret = 1;
        /* we need to insert a new item */
        msgdata = g_new0(struct item_msg_priv, 1);
        msgdata->message_id = g_strdup(msgid);
        msgdata->speed = speed;
        msgdata->delay = delay;
        /* TODO attrs */
        priv_data->message_data = g_list_append(priv_data->message_data, msgdata);
    }

    if (ret)
        tm_item_update_attrs(item, route);

    return ret;
}

/**
 * @brief Destroys a traffic map item.
 *
 * This function should never be called directly. Instead, be sure to obtain all references by calling
 * `tm_item_ref()` and destroying them by calling `tm_item_unref()`.
 *
 * @param item The item (its `priv_data` member must point to a `struct item_priv`)
 */
static void tm_item_destroy(struct item * item) {
    struct item_priv * priv_data = item->priv_data;
    GList * msglist;
    struct item_msg_priv * msgdata;

    attr_list_free(priv_data->attrs);
    g_free(priv_data->coords);

    for (msglist = priv_data->message_data; msglist; msglist = g_list_remove(msglist, msglist->data)) {
        msgdata = (struct item_msg_priv *) msglist->data;
        g_free(msgdata->message_id);
        attr_list_free(msgdata->attrs);
        g_free(msgdata);
    }

    g_free(item->priv_data);
    g_free(item);
}

/**
 * @brief References a traffic map item.
 *
 * Storing a reference to a traffic map item should always be done by calling this function, passing the
 * item as its argument. This will return the item and increase its reference count by one.
 *
 * Never store a pointer to a traffic item not obtained via this function. Doing so may have undesired
 * side effects as the item will not be aware of the reference to it, and the reference may unexpectedly
 * become invalid, leading to a segmentation fault.
 *
 * @param item The item (its `priv_data` member must point to a `struct item_priv`)
 *
 * @return The item. `NULL` will be returned if the argument is `NULL` or points to an item whose
 * `priv_data` member is `NULL`.
 */
static struct item * tm_item_ref(struct item * item) {
    if (!item)
        return NULL;
    if (!item->priv_data)
        return NULL;
    ((struct item_priv *) item->priv_data)->refcount++;
    return item;
}

/**
 * @brief Unreferences a traffic map item.
 *
 * This must be called when destroying a reference to a traffic map item. It will decrease the reference
 * count of the item by one, and destroy the item if the last reference to is is removed.
 *
 * The map itself (and only the map) holds weak references to its items, which are not considered in the
 * reference count. Consequently, when the reference count reaches zero, the item is also removed from
 * the map.
 *
 * Unreferencing an item with a zero reference count (which is only possible for an item which has never
 * been referenced since its creation) is equivalent to dropping the last reference, i.e. it will destroy
 * the item.
 *
 * When the last reference is removed (or an item with a zero reference count is unreferenced) and the item’s `rt`
 * member is set (indicating the route to which the item was added), the item is removed from that route.
 *
 * If the unreference operation is successful, this function returns `NULL`. This allows one-line
 * operations such as:
 *
 * {@code some_item = tm_item_unref(some_item);}
 *
 * @param item The item (its `priv_data` member must point to a `struct item_priv`)
 *
 * @return `NULL` if the item was unreferenced successfully, `item` if it points to an item whose
 * `priv_data` member is `NULL`.
 */
static struct item * tm_item_unref(struct item * item) {
    struct item_priv * priv_data;
    struct map_rect * mr;
    struct item * mapitem;
    if (!item)
        return item;
    if (!item->priv_data)
        return item;
    priv_data = (struct item_priv *) item->priv_data;
    priv_data->refcount--;
    if (priv_data->refcount <= 0) {
        if (priv_data->rt)
            route_remove_traffic_distortion(priv_data->rt, item);
        mr = map_rect_new(item->map, NULL);
        do {
            mapitem = map_rect_get_item(mr);
        } while (mapitem && (mapitem != item));
        if (mapitem)
            item_type_set(mapitem, type_none);
        map_rect_destroy(mr);
        tm_item_destroy(item);
    }
    return NULL;
}

/**
 * @brief Updates the attributes of an item.
 *
 * This method must be called after changing the message data associated with an item, i.e. adding,
 * removing or modifying message data.
 *
 * @param item The item
 * @param route The route affected by the changes
 */
static void tm_item_update_attrs(struct item * item, struct route * route) {
    struct item_priv * priv_data = (struct item_priv *) item->priv_data;
    GList * msglist;
    struct item_msg_priv * msgdata;
    int speed = INT_MAX;
    int delay = 0;
    struct attr * attr = NULL;
    int has_changes = 0;

    for (msglist = priv_data->message_data; msglist; msglist = g_list_next(msglist)) {
        msgdata = (struct item_msg_priv *) msglist->data;
        if (msgdata->speed < speed)
            speed = msgdata->speed;
        if (msgdata->delay < delay)
            delay = msgdata->delay;
        /* TODO attrs */
    }

    if (!priv_data->attrs)
        priv_data->attrs = g_new0(struct attr *, 1);

    /* TODO maxspeed vs. delay:
     * Currently both values are interpreted as being cumulative, which may give erroneous results.
     * Consider a segment with a length of 1000 m and a maxspeed of 120 km/h, thus having a cost of 30 s.
     * One message reports a maxspeed of 60 km/h and no delay, increasing the cost to 60 s. A second
     * message reports no maxspeed but a delay of 30 s, also increasing the cost to 60 s. Both messages
     * together would be interpreted as reducing the maxspeed to 60 km/h and adding a delay of 30 s,
     * resulting in a cost of 90 s for the segment.
     */
    if (speed < INT_MAX) {
        attr = attr_search(priv_data->attrs, NULL, attr_maxspeed);
        if (!attr) {
            attr = g_new0(struct attr, 1);
            attr->type = attr_maxspeed;
            attr->u.num = speed;
            priv_data->attrs = attr_generic_add_attr(priv_data->attrs, attr);
            g_free(attr);
            attr = NULL;
            has_changes = 1;
        } else if (speed < attr->u.num) {
            has_changes = 1;
            attr->u.num = speed;
        } else if (speed > attr->u.num) {
            has_changes = 1;
            attr->u.num = speed;
        }
    } else {
        while ((attr = attr_search(priv_data->attrs, NULL, attr_maxspeed)))
            priv_data->attrs = attr_generic_remove_attr(priv_data->attrs, attr);
    }

    if (delay) {
        attr = attr_search(priv_data->attrs, NULL, attr_delay);
        if (!attr) {
            attr = g_new0(struct attr, 1);
            attr->type = attr_delay;
            attr->u.num = delay;
            priv_data->attrs = attr_generic_add_attr(priv_data->attrs, attr);
            g_free(attr);
            attr = NULL;
            has_changes = 1;
        } else if (delay > attr->u.num) {
            has_changes = 1;
            attr->u.num = delay;
        } else if (delay < attr->u.num) {
            has_changes = 1;
            attr->u.num = delay;
        }
    } else {
        while (1) {
            attr = attr_search(priv_data->attrs, NULL, attr_delay);
            if (!attr)
                break;
            priv_data->attrs = attr_generic_remove_attr(priv_data->attrs, attr);
        }
    }

    if (has_changes) {
        if (!priv_data->rt) {
            priv_data->rt = route;
            route_add_traffic_distortion(priv_data->rt, item);
        } else
            route_change_traffic_distortion(priv_data->rt, item);
    }
}

/**
 * @brief Returns an item from the map which matches the supplied data.
 *
 * Comparison criteria are as follows:
 *
 * \li The item type must match
 * \li Start and end coordinates must match (inverted coordinates will also match)
 * \li If `attr_flags` is supplied in `attrs`, the item must have this attribute and the rules listed
 * below are applied
 * \li Flags in `AF_ALL` must match
 * \li Flags in `AF_ONEWAYMASK` must be set either on both sides or neither side
 * \li If set, flags in `AF_ONEWAYMASK` must effectively match (equal for same direction, inverted for
 * opposite directions)
 * \li Other attributes are currently ignored
 *
 * This is due to the way different reports for the same segment are handled:
 *
 * \li If multiple reports with the same access flags exist, one item is created; speed and delay are
 * evaluated across all currently active reports in `tm_item_update_attrs()` (lowest speed and longest
 * delay wins)
 * \li If multiple reports exist and access flags differ, one item is created for each set of flags;
 * items are deduplicated in `route_get_traffic_distortion()`
 *
 * @param mr A map rectangle in the traffic map
 * @param type Type of the item
 * @param attrs The attributes for the item
 * @param c Points to an array of coordinates for the item
 * @param count Number of items in `c`
 */
static struct item * tm_find_item(struct map_rect *mr, enum item_type type, struct attr **attrs,
                                  struct coord *c, int count) {
    struct item * ret = NULL;
    struct item * curr;
    struct item_priv * curr_priv;
    struct attr wanted_flags_attr, curr_flags_attr;

    while ((curr = map_rect_get_item(mr)) && !ret) {
        if (curr->type != type)
            continue;
        if (attr_generic_get_attr(attrs, NULL, attr_flags, &wanted_flags_attr, NULL)) {
            if (!item_attr_get(curr, attr_flags, &curr_flags_attr))
                continue;
            if ((wanted_flags_attr.u.num & AF_ALL) != (curr_flags_attr.u.num & AF_ALL))
                continue;
            continue;
        } else
            wanted_flags_attr.type = attr_none;
        curr_priv = curr->priv_data;
        if (curr_priv->coords[0].x == c[0].x && curr_priv->coords[0].y == c[0].y
                && curr_priv->coords[curr_priv->coord_count-1].x == c[count-1].x
                && curr_priv->coords[curr_priv->coord_count-1].y == c[count-1].y) {
            if (wanted_flags_attr.type == attr_none) {
                /* no flag comparison, match */
            } else if ((wanted_flags_attr.u.num & AF_ONEWAYMASK) != (curr_flags_attr.u.num & AF_ONEWAYMASK))
                /* different oneway restrictions, no match */
                continue;
            ret = curr;
        } else if (curr_priv->coords[0].x == c[count-1].x
                   && curr_priv->coords[0].y == c[count-1].y
                   && curr_priv->coords[curr_priv->coord_count-1].x == c[0].x
                   && curr_priv->coords[curr_priv->coord_count-1].y == c[0].y) {
            if (wanted_flags_attr.type == attr_none) {
                /* no flag comparison, match */
            } else if (!(wanted_flags_attr.u.num & AF_ONEWAYMASK) && !(curr_flags_attr.u.num & AF_ONEWAYMASK)) {
                /* two bidirectional distortions, match */
            } else if (wanted_flags_attr.u.num & curr_flags_attr.u.num & AF_ONEWAYMASK) {
                /* oneway in opposite directions, no match */
                continue;
            } else if ((wanted_flags_attr.u.num ^ AF_ONEWAYMASK) & curr_flags_attr.u.num & AF_ONEWAYMASK) {
                /* oneway in same direction, match */
            } else {
                continue;
            }
            ret = curr;
        }
    }
    return ret;
}

#ifdef TRAFFIC_DEBUG
/**
 * @brief Dumps an item to a textfile map.
 *
 * This method writes the item to a textfile map named `distortion.txt` in the default data folder.
 * This map can be added to the active mapset in order for the distortions to be rendered on the map and
 * considered for routing.
 *
 * All data passed to this method is safe to free after the method returns, and doing so is the
 * responsibility of the caller.
 *
 * @param item The item
 */
static void tm_dump_item_to_textfile(struct item * item) {
    struct item_priv * ip = (struct item_priv *) item->priv_data;
    struct attr **attrs = ip->attrs;
    struct coord *c = ip->coords;
    int i;
    char * attr_text;

    /* add the configuration directory to the name of the file to use */
    char *dist_filename = g_strjoin(NULL, navit_get_user_data_directory(TRUE),
                                    "/distortion.txt", NULL);
    if (dist_filename) {
        FILE *map = fopen(dist_filename,"a");
        if (map) {
            fprintf(map, "type=%s", item_to_name(item->type));
            while (*attrs) {
                attr_text = attr_to_text(*attrs, NULL, 0);
                /* FIXME this may not work properly for all attribute types */
                fprintf(map, " %s=%s", attr_to_name((*attrs)->type), attr_text);
                g_free(attr_text);
                attrs++;
            }
            fprintf(map, "\n");

            for (i = 0; i < ip->coord_count; i++) {
                fprintf(map,"0x%x 0x%x\n", c[i].x, c[i].y);
            }
            fclose(map);
        } else {
            dbg(lvl_error,"could not open file for distortions !!");

        } /* else - if (map) */
        g_free(dist_filename);			/* free the file name */
    } /* if (dist_filename) */
}

/**
 * @brief Dumps the traffic map to a textfile map.
 *
 * This method writes all items to a textfile map named `distortion.txt` in the default data folder.
 * This map can be added to the active mapset in order for the distortions to be rendered on the map and
 * considered for routing.
 *
 * @param map The traffic map
 */
static void tm_dump_to_textfile(struct map * map) {
    /* external method, verifies the public API as well as internal structure */
    struct map_rect * mr;
    struct item * item;

    mr = map_rect_new(map, NULL);
    while ((item = map_rect_get_item(mr)))
        tm_dump_item_to_textfile(item);
    map_rect_destroy(mr);
}
#endif

/**
 * @brief Adds an item to the map.
 *
 * If a matching item is already in the map, that item will be returned.
 *
 * All data passed to this method is safe to free after the method returns, and doing so is the
 * responsibility of the caller.
 *
 * @param map The traffic map
 * @param type Type of the item
 * @param id_hi First part of the ID of the item (item IDs have two parts)
 * @param id_lo Second part of the ID of the item
 * @param flags Flags used as a matching criterion, and added to newly-created items
 * @param attrs The attributes for the item
 * @param c Points to an array of coordinates for the item
 * @param count Number of items in `c`
 * @param id Message ID for the associated message
 *
 * @return The map item
 */
static struct item * tm_add_item(struct map *map, enum item_type type, int id_hi, int id_lo,
                                 int flags, struct attr **attrs, struct coord *c, int count, char * id) {
    struct item * ret = NULL;
    struct item_priv * priv_data;
    struct map_rect * mr;
    struct attr ** int_attrs = NULL;
    struct attr flags_attr;

    flags_attr.type = attr_flags;
    flags_attr.u.num = flags;
    int_attrs = attr_generic_set_attr(attr_list_dup(attrs), &flags_attr);

    mr = map_rect_new(map, NULL);
    ret = tm_find_item(mr, type, int_attrs, c, count);
    if (!ret) {
        ret = map_rect_create_item(mr, type);
        ret->id_hi = id_hi;
        ret->id_lo = id_lo;
        ret->map = map;
        ret->meth = &methods_traffic_item;
        priv_data = (struct item_priv *) ret->priv_data;
        priv_data->attrs = int_attrs;
        priv_data->coords = g_memdup(c, sizeof(struct coord) * count);
        priv_data->coord_count = count;
        priv_data->next_attr = int_attrs;
        priv_data->next_coord = 0;
    } else if (int_attrs) {
        /* free up our copy of the attribute list if we’re not attaching it to a new item */
        attr_list_free(int_attrs);
    }
    map_rect_destroy(mr);
    //tm_dump_item(ret);
    return ret;
}

/**
 * @brief Destroys (closes) the traffic map.
 *
 * @param priv The private data for the traffic map instance
 */
static void tm_destroy(struct map_priv *priv) {
    g_free(priv);
}

/**
 * @brief Opens a new map rectangle on the traffic map.
 *
 * This function opens a new map rectangle on the route graph's map.
 *
 * @param priv The traffic graph map's private data
 * @param sel The map selection (to restrict search to a rectangle, order and/or item types)
 * @return A new map rect's private data
 */
static struct map_rect_priv * tm_rect_new(struct map_priv *priv, struct map_selection *sel) {
    struct map_rect_priv * mr;
    dbg(lvl_debug,"enter");
    mr=g_new0(struct map_rect_priv, 1);
    mr->mpriv = priv;
    mr->next_item = priv->items;
    /* all other pointers are initially NULL */
    return mr;
}

/**
 * @brief Destroys a map rectangle on the traffic map.
 */
static void tm_rect_destroy(struct map_rect_priv *mr) {
    /* just free the map_rect_priv, all its members are pointers to data "owned" by others */
    g_free(mr);
}

/**
 * @brief Returns the next item from the traffic map
 *
 * @param mr The map rect to search for items
 *
 * @return The next item, or `NULL` if the last item has already been retrieved.
 */
static struct item * tm_get_item(struct map_rect_priv *mr) {
    struct item * ret = NULL;
    struct item_priv * ip;

    if (mr->item) {
        ip = (struct item_priv *) mr->item->priv_data;
        ip->mr = NULL;
    }
    if (mr->next_item) {
        ret = (struct item *) mr->next_item->data;
        ip = (struct item_priv *) ret->priv_data;
        ip->mr = mr;
        tm_attr_rewind(ret->priv_data);
        tm_coord_rewind(ret->priv_data);
        mr->next_item = g_list_next(mr->next_item);
    }

    mr->item = ret;
    return ret;
}

/**
 * @brief Returns the next item with the supplied ID from the traffic map
 *
 * @param mr The map rect to search for items
 * @param id_hi The high-order portion of the ID
 * @param id_lo The low-order portion of the ID
 *
 * @return The next item matching the ID; `NULL` if there are no matching items or the last matching
 * item has already been retrieved.
 */
static struct item * tm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo) {
    struct item *ret = NULL;
    do {
        ret = tm_get_item(mr);
    } while (ret && (ret->id_lo != id_lo || ret->id_hi != id_hi));
    return ret;
}

/**
 * @brief Creates a new item of the specified type and inserts it into the map.
 *
 * @param mr The map rect in which to create the item
 * @param type The type of item to create
 *
 * @return The new item. The item is of type `type` and has an allocated `priv_data` member; all other
 * members of both structs are `NULL`.
 */
static struct item * tm_rect_create_item(struct map_rect_priv *mr, enum item_type type) {
    struct map_priv * map_priv = mr->mpriv;
    struct item * ret = NULL;
    struct item_priv * priv_data;

    priv_data = g_new0(struct item_priv, 1);

    ret = g_new0(struct item, 1);
    ret->type = type;
    ret->priv_data = priv_data;
    map_priv->items = g_list_append(map_priv->items, ret);

    return ret;
}

/**
 * @brief Rewinds the coordinates of the currently selected item.
 *
 * After rewinding, the next call to the `tm_coord_get()` will return the first coordinate of the
 * current item.
 *
 * @param priv_data The item's private data
 */
static void tm_coord_rewind(void *priv_data) {
    struct item_priv * ip = priv_data;

    ip->next_coord = 0;
}

/**
 * @brief Returns the coordinates of a traffic item.
 *
 * @param priv_data The item's private data
 * @param c Pointer to a `struct coord` array where coordinates will be stored
 * @param count The maximum number of coordinates to retrieve (must be less than or equal to the number
 * of items `c` can hold)
 * @return The number of coordinates retrieved
 */
static int tm_coord_get(void *priv_data, struct coord *c, int count) {
    struct item_priv * ip = priv_data;
    int ret = count;

    if (!ip)
        return 0;
    if (ip->next_coord >= ip->coord_count)
        return 0;
    if (ip->next_coord + count > ip->coord_count)
        ret = ip->coord_count - ip->next_coord;
    memcpy(c, &ip->coords[ip->next_coord], ret * sizeof(struct coord));
    ip->next_coord += ret;
    return ret;
}

/**
 * @brief Rewinds the attributes of the currently selected item.
 *
 * After rewinding, the next call to `tm_attr_get()` will return the first attribute.
 *
 * @param priv_data The item's private data
 */
static void tm_attr_rewind(void *priv_data) {
    struct item_priv * ip = priv_data;

    ip->next_attr = ip->attrs;
}

/**
 * @brief Returns the next attribute of a traffic item which matches the specified type.
 *
 * @param priv_data The item's private data
 * @param attr_type The attribute type to retrieve, or `attr_any` to retrieve the next attribute,
 * regardless of type
 * @param attr Receives the attribute
 *
 * @return True on success, false on failure
 */
static int tm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr) {
    struct item_priv * ip = priv_data;
    int ret = 0;

    if (!ip->next_attr)
        return 0;
    while (*(ip->next_attr) && !ret) {
        ret = (attr_type == attr_any) || (attr_type == (*(ip->next_attr))->type);
        if (ret)
            attr_dup_content(*(ip->next_attr), attr);
        ip->next_attr++;
    }
    return ret;
}

/**
 * @brief Sets the type of a traffic item.
 *
 * @param priv_data The item's private data
 * @param type The new type for the item. Setting it to `type_none` deletes the item from the map.
 *
 * @return 0 on failure, nonzero on success
 */
static int tm_type_set(void *priv_data, enum item_type type) {
    struct item_priv * ip = priv_data;

    if (!ip->mr || !ip->mr->item || (ip->mr->item->priv_data != priv_data)) {
        dbg(lvl_error, "this function can only be called for the last item retrieved from its map rect");
        return 0;
    }

    if (type == type_none) {
        /* if we have multiple occurrences of this item in the list, move forward beyond the last one */
        while (ip->mr->next_item && (ip->mr->next_item->data == ip->mr->item))
            ip->mr->next_item = g_list_next(ip->mr->next_item);

        /* remove the item from the map and set last retrieved item to NULL */
        ip->mr->mpriv->items = g_list_remove_all(ip->mr->mpriv->items, ip->mr->item);
        ip->mr->item = NULL;
    } else {
        ip->mr->item->type = type;
    }

    return 1;
}

static struct map_methods traffic_map_meth = {
    projection_mg,    /* pro: The projection used for that type of map */
    "utf-8",          /* charset: The charset this map uses. */
    tm_destroy,       /* map_destroy: Destroy ("close") a map. */
    tm_rect_new,      /* map_rect_new: Create a new map rect on the map. */
    tm_rect_destroy,  /* map_rect_destroy: Destroy a map rect */
    tm_get_item,      /* map_rect_get_item: Return the next item from a map rect */
    tm_get_item_byid, /* map_rect_get_item_byid: Get an item with a specific ID from a map rect, can be NULL */
    NULL,             /* map_search_new: Start a new search on the map, can be NULL */
    NULL,             /* map_search_destroy: Destroy a map search struct, ignored if `map_search_new` is NULL */
    NULL,             /* map_search_get_item: Get the next item of a search on the map */
    tm_rect_create_item, /* map_rect_create_item: Create a new item in the map */
    NULL,             /* map_get_attr */
    NULL,             /* map_set_attr */
};

/**
 * @brief Whether the contents of an event are valid.
 *
 * This identifies any malformed events in which mandatory members are not set.
 *
 * @return true if the event is valid, false if it is malformed
 */
static int traffic_event_is_valid(struct traffic_event * this_) {
    if (!this_->event_class || !this_->type) {
        dbg(lvl_debug, "event_class (%d) or type (%d) are unknown", this_->event_class, this_->type);
        return 0;
    }
    switch (this_->event_class) {
    case event_class_congestion:
        if ((this_->type < event_congestion_cleared) || (this_->type >= event_delay_clearance)) {
            dbg(lvl_debug, "illegal type (%d) for event_class_congestion", this_->type);
            return 0;
        }
        break;
    case event_class_delay:
        if ((this_->type < event_delay_clearance)
                || (this_->type >= event_restriction_access_restrictions_lifted)) {
            dbg(lvl_debug, "illegal type (%d) for event_class_delay", this_->type);
            return 0;
        }
        break;
    case event_class_restriction:
        if ((this_->type < event_restriction_access_restrictions_lifted)
                || (this_->type > event_restriction_speed_limit_lifted)) {
            dbg(lvl_debug, "illegal type (%d) for event_class_restriction", this_->type);
            return 0;
        }
        break;
    default:
        dbg(lvl_debug, "unknown event class %d", this_->event_class);
        return 0;
    }
    if (this_->si_count && !this_->si) {
        dbg(lvl_debug, "si_count=%d but no supplementary information", this_->si_count);
        return 0;
    }
    /* TODO check SI */
    return 1;
}

/**
 * @brief Determines the degree to which the attributes of a location and a map item match.
 *
 * The result of this method is used to match a location to a map item. Its result is a score—the higher
 * the score, the better the match.
 *
 * To calculate the score, all supplied attributes are examined and points are given for each attribute
 * which is defined for the location. An exact match adds 4 points, a partial match adds 2. Values of 1
 * and 3 are added where additional granularity is needed. The number of points attained is divided by
 * the maximum number of points attainable, and the result is returned as a percentage value.
 *
 * If no points can be attained (because no attributes which must match are supplied), the score is 100
 * for any item supplied.
 *
 * @param this_ The location
 * @param item The map item
 *
 * @return The score, as a percentage value
 */
static int traffic_location_match_attributes(struct traffic_location * this_, struct item *item) {
    int score = 0;
    int maxscore = 0;
    struct attr attr;

    /* road type */
    if ((this_->road_type != type_line_unspecified)) {
        maxscore += 400;
        if (item->type == this_->road_type)
            score += 400;
        else
            switch (this_->road_type) {
            /* motorway */
            case type_highway_land:
                if (item->type == type_highway_city)
                    score += 300;
                else if (item->type == type_street_n_lanes)
                    score += 200;
                break;
            case type_highway_city:
                if (item->type == type_highway_land)
                    score += 300;
                else if (item->type == type_street_n_lanes)
                    score += 200;
                break;
            /* trunk */
            case type_street_n_lanes:
                if ((item->type == type_highway_land) || (item->type == type_highway_city)
                        || (item->type == type_street_4_land)
                        || (item->type == type_street_4_city))
                    score += 200;
                break;
            /* primary */
            case type_street_4_land:
                if (item->type == type_street_4_city)
                    score += 300;
                else if ((item->type == type_street_n_lanes)
                         || (item->type == type_street_3_land))
                    score += 200;
                else if (item->type == type_street_3_city)
                    score += 100;
                break;
            case type_street_4_city:
                if (item->type == type_street_4_land)
                    score += 300;
                else if ((item->type == type_street_n_lanes)
                         || (item->type == type_street_3_city))
                    score += 200;
                else if (item->type == type_street_3_land)
                    score += 100;
                break;
            /* secondary */
            case type_street_3_land:
                if (item->type == type_street_3_city)
                    score += 300;
                else if ((item->type == type_street_4_land)
                         || (item->type == type_street_2_land))
                    score += 200;
                else if ((item->type == type_street_4_city)
                         || (item->type == type_street_2_city))
                    score += 100;
                break;
            case type_street_3_city:
                if (item->type == type_street_3_land)
                    score += 300;
                else if ((item->type == type_street_4_city)
                         || (item->type == type_street_2_city))
                    score += 200;
                else if ((item->type == type_street_4_land)
                         || (item->type == type_street_2_land))
                    score += 100;
                break;
            /* tertiary */
            case type_street_2_land:
                if (item->type == type_street_2_city)
                    score += 300;
                else if (item->type == type_street_3_land)
                    score += 200;
                else if (item->type == type_street_3_city)
                    score += 100;
                break;
            case type_street_2_city:
                if (item->type == type_street_2_land)
                    score += 300;
                else if (item->type == type_street_3_city)
                    score += 200;
                else if (item->type == type_street_3_land)
                    score += 100;
                break;
            default:
                break;
            }
    }

    /* road_ref */
    if (this_->road_ref) {
        maxscore += 400;
        if (item_attr_get(item, attr_street_name_systematic, &attr))
            score += (400 * (MAX_MISMATCH - compare_name_systematic(this_->road_ref, attr.u.str))) / MAX_MISMATCH;
    }

    /* road_name */
    if (this_->road_name) {
        maxscore += 200;
        if (item_attr_get(item, attr_street_name, &attr)) {
            // TODO crude comparison in need of refinement
            if (!strcmp(this_->road_name, attr.u.str))
                score += 200;
        }
    }

    // TODO direction
    // TODO destination

    // TODO ramps

    if (!maxscore)
        return 100;
    return (score * 100) / maxscore;
}

/**
 * @brief Determines the degree to which the attributes of a point and a map item match.
 *
 * The result of this method is used to match a location to a map item. Its result is a score—the higher
 * the score, the better the match.
 *
 * To calculate the score, all supplied attributes are examined and points are given for each attribute
 * which is defined for the location. An exact match adds 4 points, a partial match adds 2. Values of 1
 * and 3 are added where additional granularity is needed. The number of points attained is divided by
 * the maximum number of points attainable, and the result is returned as a percentage value.
 *
 * If no points can be attained (because no attributes which must match are supplied), the score is 0
 * for any item supplied.
 *
 * @param this_ The traffic point
 * @param item The map item
 *
 * @return The score, as a percentage value
 */
static int traffic_point_match_attributes(struct traffic_point * this_, struct item *item) {
    int score = 0;
    int maxscore = 0;
    struct attr attr;

    /* junction_ref */
    if (this_->junction_ref) {
        maxscore += 400;
        if (item_attr_get(item, attr_ref, &attr))
            score += (400 * (MAX_MISMATCH - compare_name_systematic(this_->junction_ref, attr.u.str))) / MAX_MISMATCH;
    }

    /* junction_name */
    if (this_->junction_name) {
        if (item_attr_get(item, attr_label, &attr)) {
            maxscore += 400;
            // TODO crude comparison in need of refinement
            if (!strcmp(this_->junction_name, attr.u.str))
                score += 400;
        }
    }

    // TODO tmc_table, point->tmc_id

    if (!maxscore)
        return 0;
    return (score * 100) / maxscore;
}

/**
 * @brief Determines the degree to which the attributes of a point match those of the segments connecting to it.
 *
 * The result of this method is used to match a location to a map item. Its result is a score—the higher the score, the
 * better the match.
 *
 * To calculate the score, this method iterates over all segments which begin or end at `p`. The `junction_name`
 * member of the location is compared against the name of the segment, and the highest score for any segment is
 * returned. Currently the name must match completely, resulting in a score of 100, while everything else is considered
 * a mismatch (with a score of 0). Future versions may introduce support for partial matches, with the score indicating
 * the quality of the match.
 *
 * Segments which are part of the route are treated in a different manner, as the direction in which the segment is
 * traversed (not the direction of the segment itself) is taken into account, which is needed to govern whether the
 * matched segment ends up being part of the route or not.
 *
 * In some cases, `this_` refers to a point which is actually a segment (such as a bridge or tunnel), which we want to
 * include in the route. In other cases, `this_` refers to an intersection with another road, and the junction name is
 * the name of the other road; these segments need to be excluded from the route.
 *
 * This is controlled by the `match_start` argument: if true, we are evaluating the start point of a route, else we are
 * evaluating its end point. To include the matched segment in the route, only the first point (whose `seg` member
 * points to the segment) will match for the start point, the opposite is true for the end point. To exclude the
 * matched segment, this logic is reversed.
 *
 * A heuristic is in place to distinguish whether or not we want the matched segment included.
 *
 * If no points can be attained (because no attributes which must match are supplied), the score is 0 for any point.
 *
 * @param this_ The traffic point
 * @param p The point shared by all segments to examine
 * @param start The first point of the path
 * @param match_start True to evaluate for the start point of a route, false for the end point
 *
 * @return The score, as a percentage value
 */
static int traffic_point_match_segment_attributes(struct traffic_point * this_, struct route_graph_point *p,
        struct route_graph_point * start, int match_start) {

    /*
     * Whether we want a match for the route segment starting at p (leading away from it) or the route segment ending
     * at p (leading towards it).
     */
    int want_start_match = match_start;

    /* Iterator for route graph points */
    struct route_graph_point *p_iter = start;

    /* The predecessor pf `p`in the route graph */
    struct route_graph_point *p_prev = NULL;

    /*
     * Whether this_ matches the route segment starting at p (leading away from it), the route segment ending at p
     * (leading towards it), or an off-route segment connected to p, respectively
     */
    int has_start_match = 0, has_end_match = 0, has_offroute_match = 0;

    /* The route segment being examined */
    struct route_graph_segment *s;

    /* Map rect for retrieving item data */
    struct map_rect *mr;

    /* The item being examined */
    struct item * item;

    /* The attribute being examined */
    struct attr attr;

    /* Name and systematic name for route segments starting and ending at p */
    char *start_name = NULL, *start_ref = NULL, *end_name = NULL, *end_ref = NULL;

    /* Whether or not the route follows the road (if both are true or both are false, the case is not clear) */
    int route_follows_road = 0, route_leaves_road = 0;

    if (!this_->junction_name) {
        /* nothing to compare, score is 0 */
        dbg(lvl_debug, "p=%p: no junction name, score 0", p);
        return 0;
    }

    /* find predecessor of p, if any */
    while (p_iter && (p_iter != p)) {
        if (!p_iter->seg) {
            p_prev = NULL;
            break;
        }
        p_prev = p_iter;
        if (p_iter == p_iter->seg->start)
            p_iter = p_iter->seg->end;
        else
            p_iter = p_iter->seg->start;
    }

    if (!p_prev && (p != start)) {
        /* not a point on the route */
        dbg(lvl_debug, "p=%p: not on the route, score 0", p);
        return 0;
    }
    /* check if we have a match for the start of a route segment */
    if (p->seg) {
        mr = map_rect_new(p->seg->data.item.map, NULL);
        if ((item = map_rect_get_item_byid(mr, p->seg->data.item.id_hi, p->seg->data.item.id_lo))) {
            if (item_attr_get(item, attr_street_name, &attr)) {
                start_name = g_strdup(attr.u.str);
                // TODO crude comparison in need of refinement
                if (!strcmp(this_->junction_name, attr.u.str))
                    has_start_match = 1;
            }
            if (item_attr_get(item, attr_street_name_systematic, &attr))
                start_ref = g_strdup(attr.u.str);
        }
        map_rect_destroy(mr);
    }

    /* check if we have a match for the end of a route segment */
    if (p_prev && p_prev->seg) {
        mr = map_rect_new(p_prev->seg->data.item.map, NULL);
        if ((item = map_rect_get_item_byid(mr, p_prev->seg->data.item.id_hi, p_prev->seg->data.item.id_lo))) {
            if (item_attr_get(item, attr_street_name, &attr)) {
                end_name = g_strdup(attr.u.str);
                // TODO crude comparison in need of refinement
                if (!strcmp(this_->junction_name, attr.u.str))
                    has_end_match = 1;
            }
            if (item_attr_get(item, attr_street_name_systematic, &attr))
                end_ref = g_strdup(attr.u.str);
        }
        map_rect_destroy(mr);
    }

    /*
     * If we have both a start match and an end match, the point is in the middle of a stretch of road which matches
     * the junction name. Regardless of whether we want that stretch included in the route or not, a middle point
     * cannot be an end point.
     */
    if (has_start_match && has_end_match) {
        dbg(lvl_debug, "p=%p: both start and end match, score 0", p);
        g_free(start_name);
        g_free(start_ref);
        g_free(end_name);
        g_free(end_ref);
        return 0;
    }

    if (start_name && end_name)
        // TODO crude comparison in need of refinement
        route_follows_road |= !strcmp(start_name, end_name);

    if (start_ref && end_ref)
        route_follows_road |= !compare_name_systematic(start_ref, end_ref);

    /* check if we have a match for an off-route segment */
    /* TODO consolidate these two loops, which differ only in their loop statement while the body is identical */
    for (s = p->start; s && !(has_offroute_match && route_leaves_road); s = s->start_next) {
        if ((p->seg == s) || (p_prev && (p_prev->seg == s)))
            /* segments is on the route, skip */
            continue;
        mr = map_rect_new(s->data.item.map, NULL);
        if ((item = map_rect_get_item_byid(mr, s->data.item.id_hi, s->data.item.id_lo))) {
            if (item_attr_get(item, attr_street_name, &attr)) {
                // TODO crude comparison in need of refinement
                if (!strcmp(this_->junction_name, attr.u.str))
                    has_offroute_match = 1;
                if (start_name)
                    route_leaves_road |= !strcmp(start_name, attr.u.str);
                if (end_name)
                    route_leaves_road |= !strcmp(end_name, attr.u.str);
            }
            if (!route_leaves_road && item_attr_get(item, attr_street_name_systematic, &attr)) {
                if (start_ref)
                    route_leaves_road |= !compare_name_systematic(start_ref, attr.u.str);
                if (end_ref)
                    route_leaves_road |= !compare_name_systematic(end_ref, attr.u.str);
            }
        }
        map_rect_destroy(mr);
    }

    for (s = p->end; s && !(has_offroute_match && route_leaves_road); s = s->end_next) {
        if ((p->seg == s) || (p_prev && (p_prev->seg == s)))
            /* segments is on the route, skip */
            continue;
        mr = map_rect_new(s->data.item.map, NULL);
        if ((item = map_rect_get_item_byid(mr, s->data.item.id_hi, s->data.item.id_lo))) {
            if (item_attr_get(item, attr_street_name, &attr)) {
                // TODO crude comparison in need of refinement
                if (!strcmp(this_->junction_name, attr.u.str))
                    has_offroute_match = 1;
                if (start_name)
                    route_leaves_road |= !strcmp(start_name, attr.u.str);
                if (end_name)
                    route_leaves_road |= !strcmp(end_name, attr.u.str);
            }
            if (!route_leaves_road && item_attr_get(item, attr_street_name_systematic, &attr)) {
                if (start_ref)
                    route_leaves_road |= !compare_name_systematic(start_ref, attr.u.str);
                if (end_ref)
                    route_leaves_road |= !compare_name_systematic(end_ref, attr.u.str);
            }
        }
        map_rect_destroy(mr);
    }

    dbg(lvl_debug,
        "p=%p: %s %s → %s %s\nhas_offroute_match=%d, has_start_match=%d, has_end_match=%d, route_follows_road=%d, route_leaves_road=%d",
        p, end_ref, end_name, start_ref, start_name,
        has_offroute_match, has_start_match, has_end_match, route_follows_road, route_leaves_road);

    g_free(start_name);
    g_free(start_ref);
    g_free(end_name);
    g_free(end_ref);

    if (route_leaves_road && !route_follows_road)
        want_start_match = !match_start;
    /* TODO decide how to handle ambiguous situations (both true or both false), currently we include the segment */

    if (has_offroute_match) {
        if (has_start_match || has_end_match) {
            /* we cannot have multiple matches in different categories */
            /* TODO maybe we can: e.g. one segment of the crossing road got added to the route, the other did not */
            dbg(lvl_debug, "p=%p: both off-route and start/end match, score 0", p);
            return 0;
        }
    } else {
        if ((want_start_match && !has_start_match) || (!want_start_match && !has_end_match)) {
            /* no match in requested category */
            dbg(lvl_debug, "p=%p: no match in requested category, score 0", p);
            return 0;
        }
    }

    dbg(lvl_debug, "p=%p: score 100 (full score)", p);
    return 100;
}

/**
 * @brief Returns the cost of the segment in the given direction.
 *
 * The cost is calculated based on the length of the segment and a penalty which depends on the score.
 * A segment with the maximum score of 100 is not penalized, i.e. its cost is equal to its length. A
 * segment with a zero score is penalized with a factor of `PENALTY_SEGMENT_MATCH`. For scores in between, a
 * penalty factor between 1 and `PENALTY_SEGMENT_MATCH` is applied.
 *
 * If the segment is impassable in the given direction, the cost is always `INT_MAX`.
 *
 * @param over The segment
 * @param data Data for the segments added to the map
 * @param dir The direction (positive numbers indicate positive direction)
 *
 * @return The cost of the segment
 */
static int traffic_route_get_seg_cost(struct route_graph_segment *over, struct seg_data * data, int dir) {
    if (over->data.flags & (dir >= 0 ? AF_ONEWAYREV : AF_ONEWAY))
        return INT_MAX;
    if (dir > 0 && (over->start->flags & RP_TURN_RESTRICTION))
        return INT_MAX;
    if (dir < 0 && (over->end->flags & RP_TURN_RESTRICTION))
        return INT_MAX;
    if ((over->data.item.type < route_item_first) || (over->data.item.type > route_item_last))
        return INT_MAX;
    /* at least a partial match is required for access flags */
    if (!(over->data.flags & data->flags & AF_ALL))
        return INT_MAX;

    return over->data.len * (100 - over->data.score) * (PENALTY_SEGMENT_MATCH - 1) / 100 + over->data.len;
}

/**
 * @brief Determines the “point triple” for a traffic location.
 *
 * Each traffic location is defined by up to three points:
 * \li a start and end point, and an optional auxiliary point in between
 * \li a single point, with one or two auxiliary points (one before, one after)
 * \li a start and end point, and a third point which is outside the location
 *
 * This method determines these three points, puts them in the order in which they are encountered and
 * returns a bit field indicating the end points. If a point in the array is NULL or refers to an
 * auxiliary point, its corresponding bit is not set. The following values are returned:
 * \li 2: Point location, the middle point is the actual point
 * \li 3: Point-to-point location from the first to the second point; the third point is an auxiliary
 * point outside the location
 * \li 5: Point-to-point location from the first to the last point; the second point (if not NULL) is an
 * auxiliary point located in between
 * \li 6: Point-to-point location from the second to the third point; the first point is an auxiliary
 * point outside the location
 *
 * @param this_ The location
 * @param coords Points to an array which will receive pointers to the coordinates. The array must be
 * able to store three pointers.
 *
 * @return A bit field indicating the end points for the location
 */
static int traffic_location_get_point_triple(struct traffic_location * this_, struct coord_geo ** coords) {
    /* Which members of coords are the end points */
    int ret = 0;

    /* Projected coordinates */
    struct coord c_from, c_to, c_not_via;

    if (this_->at) {
        coords[0] = this_->from ? &this_->from->coord : NULL;
        coords[1] = &this_->at->coord;
        coords[2] = this_->to ? &this_->to->coord : NULL;
        ret = 1 << 1;
    } else if (this_->via) {
        coords[0] = this_->from ? &this_->from->coord : NULL;
        coords[1] = &this_->via->coord;
        coords[2] = this_->to ? &this_->to->coord : NULL;
        ret = (1 << 2) | (1 << 0);
    } else if (this_->not_via) {
        /*
         * If not_via is set, we calculate a route either for not_via-from-to or for from-to-not_via,
         * then trim the ends. The order of points is determined by the distance between not_via and the
         * other two points.
         */
        if (!this_->from || !this_->to) {
            coords[0] = NULL;
            coords[1] = NULL;
            coords[2] = NULL;
            return ret;
        }
        transform_from_geo(projection_mg, &this_->from->coord, &c_from);
        transform_from_geo(projection_mg, &this_->to->coord, &c_to);
        transform_from_geo(projection_mg, &this_->not_via->coord, &c_not_via);
        if (transform_distance(projection_mg, &c_from, &c_not_via)
                < transform_distance(projection_mg, &c_to, &c_not_via)) {
            coords[0] = &this_->not_via->coord;
            coords[1] = &this_->from->coord;
            coords[2] = &this_->to->coord;
        } else {
            coords[0] = &this_->from->coord;
            coords[1] = &this_->to->coord;
            coords[2] = &this_->not_via->coord;
        }
    } else {
        coords[0] = this_->from ? &this_->from->coord : NULL;
        coords[1] = NULL;
        coords[2] = this_->to ? &this_->to->coord : NULL;
        ret = (1 << 2) | (1 << 0);
    }
    return ret;
}

/**
 * @brief Sets the rectangle enclosing all points of a location
 *
 * @param this_ The traffic location
 * @param coords The point triple, can be NULL
 */
static void traffic_location_set_enclosing_rect(struct traffic_location * this_, struct coord_geo ** coords) {
    struct coord_geo * sw;
    struct coord_geo * ne;
    struct coord_geo * int_coords[] = {NULL, NULL, NULL};
    int i;

    if (this_->priv->sw && this_->priv->ne)
        return;

    if (!coords) {
        coords = &int_coords[0];
        traffic_location_get_point_triple(this_, coords);
    }

    if (!this_->priv->sw) {
        sw = g_new0(struct coord_geo, 1);
        sw->lat = INT_MAX;
        sw->lng = INT_MAX;
        for (i = 0; i < 3; i++)
            if (coords[i]) {
                if (coords[i]->lat < sw->lat)
                    sw->lat = coords[i]->lat;
                if (coords[i]->lng < sw->lng)
                    sw->lng = coords[i]->lng;
            }
        this_->priv->sw = sw;
    }

    if (!this_->priv->ne) {
        ne = g_new0(struct coord_geo, 1);
        ne->lat = -INT_MAX;
        ne->lng = -INT_MAX;
        for (i = 0; i < 3; i++)
            if (coords[i]) {
                if (coords[i]->lat > ne->lat)
                    ne->lat = coords[i]->lat;
                if (coords[i]->lng > ne->lng)
                    ne->lng = coords[i]->lng;
            }
        this_->priv->ne = ne;
    }
}

/**
 * @brief Opens a map rectangle around the end points of the traffic location.
 *
 * Prior to calling this function, the caller must ensure `rg->m` points to the map to be used, and the enclosing
 * rectangle for the traffic location has been set (e.g. by calling `traffic_location_set_enclosing_rect()`).
 *
 * @param this_ The traffic location
 * @param rg The route graph
 *
 * @return NULL on failure, the map selection on success
 */
static struct map_rect * traffic_location_open_map_rect(struct traffic_location * this_, struct route_graph * rg) {
    /* Corners of the enclosing rectangle, in Mercator coordinates */
    struct coord c1, c2;

    transform_from_geo(map_projection(rg->m), this_->priv->sw, &c1);
    transform_from_geo(map_projection(rg->m), this_->priv->ne, &c2);

    rg->sel = route_rect(ROUTE_ORDER, &c1, &c2, ROUTE_RECT_DIST_REL, ROUTE_RECT_DIST_ABS);

    if (!rg->sel)
        return NULL;
    rg->mr = map_rect_new(rg->m, rg->sel);
    if (!rg->mr) {
        map_selection_destroy(rg->sel);
        rg->sel = NULL;
    }
    return rg->mr;
}

/**
 * @brief Populates a route graph.
 *
 * This adds all routable segments in the enclosing rectangle of the location (plus a safety margin) to
 * the route graph.
 *
 * @param rg The route graph
 * @param ms The mapset to read the ramps from
 */
static void traffic_location_populate_route_graph(struct traffic_location * this_, struct route_graph * rg,
        struct mapset * ms) {
    /* The item being processed */
    struct item *item;

    /* Mercator coordinates of current and previous point */
    struct coord c, l;

    /* Data for the route graph segment */
    struct route_graph_segment_data data;

    /* The length of the current segment */
#ifdef AVOID_FLOAT
    int len;
#else
    double len;
#endif

    /* Whether the current item is segmented */
    int segmented;

    /* Default value assumed for access flags if we cannot get flags for the item, nor for the item type */
    int default_flags_value = AF_ALL;

    /* Default flags assumed for the current item type */
    int *default_flags;

    /* Holds an attribute retrieved from the current item */
    struct attr attr;

    /* Start and end point of the current way or segment */
    struct route_graph_point *s_pnt, *e_pnt;

    traffic_location_set_enclosing_rect(this_, NULL);

    rg->h = mapset_open(ms);

    while ((rg->m = mapset_next(rg->h, 2))) {
        if (!traffic_location_open_map_rect(this_, rg))
            continue;
        while ((item = map_rect_get_item(rg->mr))) {
            if (item->type == type_street_turn_restriction_no || item->type == type_street_turn_restriction_only)
                route_graph_add_turn_restriction(rg, item);
            else if ((item->type < route_item_first) || (item->type > route_item_last))
                continue;
            if (item_get_default_flags(item->type)) {

                item_coord_rewind(item);
                if (item_coord_get(item, &l, 1)) {
                    data.score = traffic_location_match_attributes(this_, item);
                    data.flags=0;
                    data.offset=1;
                    data.maxspeed=-1;
                    data.item=item;
                    len = 0;
                    segmented = 0;

                    if (!(default_flags = item_get_default_flags(item->type)))
                        default_flags = &default_flags_value;
                    if (item_attr_get(item, attr_flags, &attr)) {
                        data.flags = attr.u.num;
                        segmented = (data.flags & AF_SEGMENTED);
                    } else
                        data.flags = *default_flags;

                    if ((data.flags & AF_SPEED_LIMIT) && (item_attr_get(item, attr_maxspeed, &attr)))
                        data.maxspeed = attr.u.num;

                    /* clear flags we're not copying here */
                    data.flags &= ~(AF_DANGEROUS_GOODS | AF_SIZE_OR_WEIGHT_LIMIT);

                    s_pnt = route_graph_add_point(rg, &l);

                    if (!segmented) {
                        while (item_coord_get(item, &c, 1)) {
                            len += transform_distance(map_projection(item->map), &l, &c);
                            l = c;
                        }
                        e_pnt = route_graph_add_point(rg, &l);
                        dbg_assert(len >= 0);
                        data.len = len;
                        if (!route_graph_segment_is_duplicate(s_pnt, &data))
                            route_graph_add_segment(rg, s_pnt, e_pnt, &data);
                    } else {
                        int isseg, rc;
                        int sc = 0;
                        do {
                            isseg = item_coord_is_node(item);
                            rc = item_coord_get(item, &c, 1);
                            if (rc) {
                                len += transform_distance(map_projection(item->map), &l, &c);
                                l = c;
                                if (isseg) {
                                    e_pnt = route_graph_add_point(rg, &l);
                                    data.len = len;
                                    if (!route_graph_segment_is_duplicate(s_pnt, &data))
                                        route_graph_add_segment(rg, s_pnt, e_pnt, &data);
                                    data.offset++;
                                    s_pnt = route_graph_add_point(rg, &l);
                                    len = 0;
                                }
                            }
                        } while(rc);
                        e_pnt = route_graph_add_point(rg, &l);
                        dbg_assert(len >= 0);
                        sc++;
                        data.len = len;
                        if (!route_graph_segment_is_duplicate(s_pnt, &data))
                            route_graph_add_segment(rg, s_pnt, e_pnt, &data);
                    }
                }
            }
        }
        map_selection_destroy(rg->sel);
        rg->sel = NULL;
        map_rect_destroy(rg->mr);
        rg->mr = NULL;
    }
    route_graph_build_done(rg, 0);
}

/**
 * @brief Builds a new route graph for traffic location matching.
 *
 * Traffic location matching is done by using a modified routing algorithm to identify the segments
 * affected by a traffic message.
 *
 * @param this_ The location to match to the map
 * @param ms The mapset to use for the route graph
 *
 * @return A route graph. The caller is responsible for destroying the route graph and all related data
 * when it is no longer needed.
 */
static struct route_graph * traffic_location_get_route_graph(struct traffic_location * this_,
        struct mapset * ms) {
    struct route_graph *rg;

    traffic_location_set_enclosing_rect(this_, NULL);

    rg = g_new0(struct route_graph, 1);

    rg->done_cb = NULL;
    rg->busy = 1;

    /* build the route graph */
    traffic_location_populate_route_graph(this_, rg, ms);

    return rg;
}

/**
 * @brief Whether two traffic points are equal.
 *
 * Comparison is done solely on coordinates and requires a precise match. This can result in two points
 * being reported as not equal, even though the locations using these points may translate to the same
 * segments later.
 *
 * @return true if `l` and `r` are equal, false if not
 */
static int traffic_point_equals(struct traffic_point * l, struct traffic_point * r) {
    if (l->coord.lat != r->coord.lat)
        return 0;
    if (l->coord.lng != r->coord.lng)
        return 0;
    return 1;
}

/**
 * @brief Whether two traffic locations are equal.
 *
 * Only directionality, the `ramps` member and reference points are considered for comparison; auxiliary
 * data (such as road names, road types and additional TMC information) is ignored.
 *
 * When in doubt, this function errs on the side of inequality, i.e. when equivalence cannot be reliably
 * determined, the locations will be reported as not equal, even though they may translate to the same
 * segments later.
 *
 * @return true if `l` and `r` are equal, false if not
 */
static int traffic_location_equals(struct traffic_location * l, struct traffic_location * r) {
    /* directionality and ramps must match for locations to be considered equal */
    if (l->directionality != r->directionality)
        return 0;
    if (l->ramps != r->ramps)
        return 0;

    /* locations must have the same points set to be considered equal */
    if (!l->from != !r->from)
        return 0;
    if (!l->to != !r->to)
        return 0;
    if (!l->at != !r->at)
        return 0;
    if (!l->via != !r->via)
        return 0;
    if (!l->not_via != !r->not_via)
        return 0;

    /* both locations have the same points set, compare them */
    if (l->from && !traffic_point_equals(l->from, r->from))
        return 0;
    if (l->to && !traffic_point_equals(l->to, r->to))
        return 0;
    if (l->at && !traffic_point_equals(l->at, r->at))
        return 0;
    if (l->via && !traffic_point_equals(l->via, r->via))
        return 0;
    if (l->not_via && !traffic_point_equals(l->not_via, r->not_via))
        return 0;

    /* No differences found, consider locations equal */
    return 1;
}

/**
 * @brief Determines the path between two reference points in a route graph.
 *
 * The reference points `from` and `to` are the beginning and end of the path and do not necessarily
 * coincide with the `from` and `to` members of the location. For a point location with an auxiliary
 * point, one will instead be the `at` member of the location; when examining the opposite direction of
 * a bidirectional location, `from` and `to` will be swapped with respect to the location.
 *
 * The coordinates contained in the reference points are typically approximate, i.e. they do not
 * precisely coincide with a point in the route graph.
 *
 * When this function returns, the route graph will be flooded, i.e. every point will have a cost
 * assigned to it and the `seg` member for each point will be set, indicating the next segment on which
 * to proceed in order to reach the destination. For the last point in the graph, `seg` will be `NULL`.
 * Unlike in common routing, the last point will have a nonzero cost if `to` does not coincide with a
 * point in the route graph.
 *
 * The cost of each node represents the cost to reach `to`. The cost is calculated in
 * `traffic_route_get_seg_cost()` for actual segments, and distance (with a penalty factor) for the
 * offroad connection from the last point in the graph to `to`.
 *
 * To obtain the path, start with the return value. Its `seg` member points to the next segment. Either
 * the `start` or the `end` value of that segment will coincide with the point currently being examined;
 * the other of the two is the point at the other end. Repeat this until you reach a point whose `seg`
 * member is `NULL`.
 *
 * This function can be run multiple times against the same route graph but with different reference
 * points. It is safe to call with `NULL` passed for one or both reference points, in which case `NULL`
 * will be returned.
 *
 * The caller is responsible for freeing up the data structures passed to this function when they are no
 * longer needed.
 *
 * @param rg The route graph
 * @param data Data for the segments added to the map
 * @param c_start Start coordinates
 * @param c_dst Destination coordinates
 * @param start_existing Start point of an existing route (whose points will not be used)
 *
 * @return The point in the route graph at which the path begins, or `NULL` if no path was found.
 */
static struct route_graph_point * traffic_route_flood_graph(struct route_graph * rg, struct seg_data * data,
        struct coord * c_start, struct coord * c_dst, struct route_graph_point * start_existing) {
    struct route_graph_point * ret;

    int i;

    GList * existing = NULL;

    /* This heap will hold all points with "temporarily" calculated costs */
    struct fibheap *heap;

    /* Cost of the start position */
    int start_value;

    /* The point currently being examined */
    struct route_graph_point *p;

    /* Cost of point being examined, other end of segment being examined, segment */
    int min, new, val;

    /* The segment currently being examined */
    struct route_graph_segment *s = NULL;

    if (!c_start || !c_dst)
        return NULL;

    /* store points of existing route */
    if (start_existing) {
        p = start_existing;
        while (p) {
            /* Do not exclude the last point (seg==NULL) from the heap as that may result in the existing route not
             * being joined properly to the new one */
            if (p->seg)
                existing = g_list_prepend(existing, p);
            if (!p->seg)
                p = NULL;
            else if (p == p->seg->start)
                p = p->seg->end;
            else
                p = p->seg->start;
        }
    }

    /* prime the route graph */
    heap = fh_makekeyheap();

    start_value = PENALTY_OFFROAD * transform_distance(projection_mg, c_start, c_dst);
    ret = NULL;

    dbg(lvl_debug, "start flooding route graph, start_value=%d", start_value);

    for (i = 0; i < HASH_SIZE; i++) {
        p = rg->hash[i];
        while (p) {
            if (!g_list_find(existing, p)) {
                if (!(p->flags & RP_TURN_RESTRICTION)) {
                    p->value = PENALTY_OFFROAD * transform_distance(projection_mg, &p->c, c_dst);
                    p->el = fh_insertkey(heap, p->value, p);
                } else {
                    /* ignore points which are part of turn restrictions */
                    p->value = INT_MAX;
                    p->el = NULL;
                }
                p->seg = NULL;
            }
            p = p->hash_next;
        }
    }

    /* flood the route graph */
    for (;;) {
        p = fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
        if (!p) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
            break;

        dbg(lvl_debug, "p=%p, value=%d", p, p->value);

        min = p->value;
        p->el = NULL; /* This point is permanently calculated now, we've taken it out of the heap */
        s = p->start;
        while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
            val = traffic_route_get_seg_cost(s, data, -1);

            dbg(lvl_debug, "  negative segment, val=%d", val);

            if (val != INT_MAX) {
                new = min + val;
                if (new < s->end->value) { /* We've found a less costly way to reach the end of s, update it */
                    s->end->value = new;
                    s->end->seg = s;
                    if (!s->end->el) {
                        s->end->el = fh_insertkey(heap, new, s->end);
                    } else {
                        fh_replacekey(heap, s->end->el, new);
                    }
                    new += PENALTY_OFFROAD * transform_distance(projection_mg, &s->end->c, c_start);
                    if (new < start_value) { /* We've found a less costly way from the start point, update */
                        start_value = new;
                        ret = s->end;
                    }
                }
            }
            s = s->start_next;
        }
        s = p->end;
        while (s) { /* Doing the same as above with the segments leading towards our point */
            val = traffic_route_get_seg_cost(s, data, 1);

            dbg(lvl_debug, "  positive segment, val=%d", val);

            if (val != INT_MAX) {
                new = min + val;
                if (new < s->start->value) {
                    s->start->value = new;
                    s->start->seg = s;
                    if (!s->start->el) {
                        s->start->el = fh_insertkey(heap, new, s->start);
                    } else {
                        fh_replacekey(heap, s->start->el, new);
                    }
                    new += PENALTY_OFFROAD * transform_distance(projection_mg, &s->start->c, c_start);
                    if (new < start_value) {
                        start_value = new;
                        ret = s->start;
                    }
                }
            }
            s = s->end_next;
        }
    }

    fh_deleteheap(heap);
    g_list_free(existing);
    return ret;
}

/**
 * @brief Extends the route beyond its end point.
 *
 * This function follows the road beginning at `end`, stopping at the next junction. It can be called
 * again on the result, again extending it to the next junction.
 *
 * To follow the road, each segment is compared to `last` and the segment whose attributes match it is
 * chosen, provided such a segment can be determined without ambiguity.
 *
 * When the function returns, all points added to the route will have their `seg` member set. To append
 * the new stretch to the route, set the `seg` member of its last point to the return value. After that,
 * the extended route can be walked in the usual manner.
 *
 * The value of each new point is the value of its predecessor on the route mins the length of the
 * segment which links the two points. Point values thus continue to decrease along the route, allowing
 * comparisons or difference calculations to be performed on the extended route. Note that this may
 * result in points having negative values.
 *
 * @param rg The flooded route graph
 * @param last The last segment in the current route graph (either the `start` or the `end` member of
 * this segment must be equal to the `end` argument)
 * @param end The last point of the current route graph (the `seg` member of this point must be NULL)
 *
 * @return The next segment in the route, or `NULL` if the route cannot be extended.
 */
static struct route_graph_segment * traffic_route_append(struct route_graph *rg,
        struct route_graph_segment * last, struct route_graph_point * end) {
    struct route_graph_segment * ret = NULL, * s = last, * s_cmp, * s_next;
    struct route_graph_point * p = end;
    int num_seg;
    int id_match;
    int is_ambiguous;

    if (!end) {
        dbg(lvl_error, "end point cannot be NULL");
        return NULL;
    }
    if (end->seg) {
        dbg(lvl_error, "end point cannot have a next segment");
        return NULL;
    }

    if ((end != last->end) && (end != last->start)) {
        dbg(lvl_error, "last segment must begin or end at end point");
        return NULL;
    }

    while (1) {
        num_seg = 0;
        id_match = 0;
        is_ambiguous = 0;
        s_next = NULL;
        for (s_cmp = p->start; s_cmp; s_cmp = s_cmp->start_next) {
            num_seg++;
            if ((s_cmp == s) || (s_cmp->data.flags & AF_ONEWAYREV) || (s_cmp->end->flags & RP_TURN_RESTRICTION))
                continue;
            if (item_is_equal_id(s_cmp->data.item, s->data.item)) {
                s_next = s_cmp;
                id_match = 1;
            } else if ((s_cmp->data.item.type == s->data.item.type) && !id_match && !is_ambiguous) {
                if (s_next) {
                    s_next = NULL;
                    is_ambiguous = 1;
                } else
                    s_next = s_cmp;
            }
        }
        for (s_cmp = p->end; s_cmp; s_cmp = s_cmp->end_next) {
            num_seg++;
            if ((s_cmp == s) || (s_cmp->data.flags & AF_ONEWAY) || (s_cmp->end->flags & RP_TURN_RESTRICTION))
                continue;
            if (item_is_equal_id(s_cmp->data.item, s->data.item)) {
                s_next = s_cmp;
                id_match = 1;
            } else if ((s_cmp->data.item.type == s->data.item.type) && !id_match && !is_ambiguous) {
                if (s_next) {
                    s_next = NULL;
                    is_ambiguous = 1;
                } else
                    s_next = s_cmp;
            }
        }

        /* cancel if we are past end and have hit a junction */
        if ((p != end) && (num_seg > 2))
            break;

        /* update links and move one step further */
        if (p != end)
            p->seg = s_next;
        else
            ret = s_next;
        if (s_next) {
            if (p == s_next->start) {
                s_next->end->value = p->value - s_next->data.len;
                p = s_next->end;
            } else {
                s_next->start->value = p->value - s_next->data.len;
                p = s_next->start;
            }
            s = s_next;
        } else
            break;
    }
    p->seg = NULL;
    dbg(lvl_debug, "return, last=%p, ret=%p", last, ret);
    return ret;
}

/**
 * @brief Extends the route beyond its start point.
 *
 * This function follows the road leading towards `start` backwards, stopping at the next junction. It
 * can be called again on the result, again extending it to the next junction.
 *
 * To follow the road, each segment is compared to `start->seg` and the segment whose attributes match
 * it is chosen, provided such a segment can be determined without ambiguity.
 *
 * When the function returns, all points added to the route will have their `seg` member set so the
 * extended route can be walked in the usual manner.
 *
 * @param rg The flooded route graph
 * @param start The current start of the route
 *
 * @return The start of the extended route, or `NULL` if the route cannot be extended (in which case
 * `start` continues to be the start of the route).
 */
static struct route_graph_point * traffic_route_prepend(struct route_graph * rg,
        struct route_graph_point * start) {
    struct route_graph_point * ret = start;
    struct route_graph_segment * s, * s_cmp, * s_prev = NULL;
    int num_seg;
    int id_match;
    int is_ambiguous;

    dbg(lvl_debug, "At %p (%d), start", start, start ? start->value : -1);
    if (!start)
        return NULL;

    s = start->seg;

    while (s) {
        num_seg = 0;
        id_match = 0;
        is_ambiguous = 0;
        for (s_cmp = ret->start; s_cmp; s_cmp = s_cmp->start_next) {
            num_seg++;
            if (s_cmp == s)
                continue;
            if (s_cmp->data.flags & AF_ONEWAY)
                continue;
            if (s_cmp->end->seg != s_cmp)
                continue;
            if (item_is_equal_id(s_cmp->data.item, s->data.item)) {
                s_prev = s_cmp;
                id_match = 1;
            } else if ((s_cmp->data.item.type == s->data.item.type) && !id_match && !is_ambiguous) {
                if (s_prev) {
                    s_prev = NULL;
                    is_ambiguous = 1;
                } else
                    s_prev = s_cmp;
            }
        }
        for (s_cmp = ret->end; s_cmp; s_cmp = s_cmp->end_next) {
            num_seg++;
            if (s_cmp == s)
                continue;
            if (s_cmp->data.flags & AF_ONEWAYREV)
                continue;
            if (s_cmp->start->seg != s_cmp)
                continue;
            if (item_is_equal_id(s_cmp->data.item, s->data.item)) {
                s_prev = s_cmp;
                id_match = 1;
            } else if ((s_cmp->data.item.type == s->data.item.type) && !id_match && !is_ambiguous) {
                if (s_prev) {
                    s_prev = NULL;
                    is_ambiguous = 1;
                } else
                    s_prev = s_cmp;
            }
        }

        /* cancel if we are past start and ret is a junction */
        if ((ret != start) && (num_seg > 2))
            break;

        /* move s and ret one step further and update links */
        s = s_prev;
        if (s) {
            if (ret == s->start) {
                ret = s->end;
                dbg(lvl_debug, "At %p (%d -> %d)", ret, ret->value, s->start->value + s->data.len);
                ret->value = s->start->value + s->data.len;
            } else {
                ret = s->start;
                dbg(lvl_debug, "At %p (%d -> %d)", ret, ret->value, s->end->value + s->data.len);
                ret->value = s->end->value + s->data.len;
            }
            ret->seg = s;
            s_prev = NULL;
        }
    }
    dbg(lvl_debug, "return, start=%p, ret=%p", start, ret);
    return ret;
}

/**
 * @brief Returns one of the traffic location’s points.
 *
 * @param this_ The traffic location
 * @param point The point of the traffic location to retrieve (0 = from, 1 = at, 2 = to, 16 = start, 17 = end)
 *
 * @return The matched points, or NULL if the requested point does not exist
 */
static struct traffic_point * traffic_location_get_point(struct traffic_location * this_, int point) {
    /* The point from the location to match */
    struct traffic_point * trpoint = NULL;

    switch(point) {
    case 0:
        trpoint = this_->from;
        break;
    case 1:
        trpoint = this_->at;
        break;
    case 2:
        trpoint = this_->to;
        break;
    case 16:
        trpoint = this_->from ? this_->from : this_->at;
        break;
    case 17:
        trpoint = this_->to ? this_->to : this_->at;
        break;
    default:
        break;
    }

    return trpoint;
}

/**
 * @brief Compares a given point to the traffic location and returns a score.
 *
 * This method obtains all points at coordinates `c` from the map_rect used to build the route graph, compares their
 * attributes to those supplied with the location, assigns a match score from 0 (no matching attributes) to 100 (all
 * supplied attributes match) and returns the highest score obtained. If no matching point is found, 0 is returned.
 *
 * @param this_ The traffic location
 * @param p The route graph point to examine for matches
 * @param point The point of the traffic location to use for matching (0 = from, 1 = at, 2 = to, 16 = start, 17 = end)
 * @param rg The route graph
 * @param start The first point of the path
 * @param match_start True to evaluate for the start point of a route, false for the end point
 * @param ms The mapset to read the items from
 *
 * @return A score from 0 (worst) to 100 (best).
 */
static int traffic_location_get_point_match(struct traffic_location * this_, struct route_graph_point * p, int point,
        struct route_graph * rg, struct route_graph_point * start, int match_start, struct mapset * ms) {
    int ret = 0;

    /* The point from the location to match */
    struct traffic_point * trpoint = NULL;

    /* The attribute matching score for the current item */
    int score;

    trpoint = traffic_location_get_point(this_, point);

    if (!trpoint)
        return 0;

    /* First examine route graph points and connected segments */
    score = traffic_point_match_segment_attributes(trpoint, p, start, match_start);
    if (ret < score)
        ret = score;
    return ret;
}

/**
 * @brief Returns points from the route graph which match a traffic location.
 *
 * This method obtains point items from the map_rect from which the route graph was built and compares
 * their attributes to those supplied with the location. Each point is assigned a match score, from 0
 * (no matching attributes) to 100 (all supplied attributes match), and a list of all points with a
 * nonzero score is returned.
 *
 * Points which have no corresponding map item (i.e. points which have no additional attributes) are not included in
 * the result and must be analyzed separately if needed.
 *
 * @param this_ The traffic location
 * @param point The point of the traffic location to use for matching (0 = from, 1 = at, 2 = to, 16 = start, 17 = end)
 * @param rg The route graph
 * @param start The first point of the path
 * @param match_start True to evaluate for the start point of a route, false for the end point
 * @param ms The mapset to read the items from
 *
 * @return The matched points as a `GList`. The `data` member of each item points to a `struct point_data` for the point.
 */
static GList * traffic_location_get_matching_points(struct traffic_location * this_, int point,
        struct route_graph * rg, struct route_graph_point * start, int match_start, struct mapset * ms) {
    GList * ret = NULL;

    /* The point from the location to match */
    struct traffic_point * trpoint = NULL;

    /* The item being processed */
    struct item *item;

    /* Mercator coordinates of current and previous point */
    struct coord c;

    /* The corresponding point in the route graph */
    struct route_graph_point * p;

    /* The attribute matching score for the current item */
    int score;

    /* Data for the current point */
    struct point_data * data;

    trpoint = traffic_location_get_point(this_, point);

    if (!trpoint)
        return NULL;

    traffic_location_set_enclosing_rect(this_, NULL);

    rg->h = mapset_open(ms);

    while ((rg->m = mapset_next(rg->h, 2))) {
        if (!traffic_location_open_map_rect(this_, rg))
            continue;
        while ((item = map_rect_get_item(rg->mr))) {
            /* exclude non-point items */
            if ((item->type < type_town_label) || (item->type >= type_line))
                continue;

            /* exclude items from which we can't obtain a coordinate pair */
            if (!item_coord_get(item, &c, 1))
                continue;

            /* exclude items not in the route graph (points with turn restrictions are ignored) */
            p = route_graph_get_point(rg, &c);
            while (p && (p->flags & RP_TURN_RESTRICTION))
                p = route_graph_get_point_next(rg, &c, p);
            if (!p)
                continue;

            /* determine score */
            score = traffic_point_match_attributes(trpoint, item);

            /* exclude items with a zero score */
            if (!score)
                continue;

            dbg(lvl_debug, "adding item, score: %d", score);

            do {
                if (!(p->flags & RP_TURN_RESTRICTION)) {
                    data = g_new0(struct point_data, 1);
                    data->score = score;
                    data->p = p;

                    ret = g_list_append(ret, data);
                }
            } while ((p = route_graph_get_point_next(rg, &c, p)));
        }
        map_selection_destroy(rg->sel);
        rg->sel = NULL;
        map_rect_destroy(rg->mr);
        rg->mr = NULL;
    }
    route_graph_build_done(rg, 1);

    return ret;
}

/**
 * @brief Whether the contents of a location are valid.
 *
 * This identifies any malformed locations in which mandatory members are not set.
 *
 * @return true if the locations is valid, false if it is malformed
 */
static int traffic_location_is_valid(struct traffic_location * this_) {
    if (!this_->at && !(this_->from && this_->to))
        return 0;
    return 1;
}

/**
 * @brief Whether the current point is a candidate for low-res endpoint matching.
 *
 * @param this_ The point to examine
 * @param s_prev The route segment leading to `this_` (NULL for the start point)
 */
static int route_graph_point_is_endpoint_candidate(struct route_graph_point *this_,
        struct route_graph_segment *s_prev) {
    int ret;

    /* Whether we are at a junction of 3 or more segments */
    int is_junction;

    /* Segment used for comparison */
    struct route_graph_segment *s_cmp;

    /* Current segment */
    struct route_graph_segment *s = this_->seg;

    if (!s_prev || !s)
        /* the first and last points are always candidates */
        ret = 1;
    else
        /* detect tunnel portals */
        ret = ((s->data.flags & AF_UNDERGROUND) != (s_prev->data.flags & AF_UNDERGROUND));
    if (!ret) {
        /* detect junctions */
        is_junction = (s && s_prev) ? 0 : -1;
        for (s_cmp = this_->start; s_cmp; s_cmp = s_cmp->start_next) {
            if ((s_cmp != s) && (s_cmp != s_prev))
                is_junction += 1;
        }
        for (s_cmp = this_->end; s_cmp; s_cmp = s_cmp->end_next) {
            if ((s_cmp != s) && (s_cmp != s_prev))
                is_junction += 1;
        }
        ret = (is_junction > 0);
    }
    return ret;
}

/**
 * @brief Generates segments affected by a traffic message.
 *
 * This translates the approximate coordinates in the `from`, `at`, `to`, `via` and `not_via` members of
 * the location to one or more map segments, using both the raw coordinates and the auxiliary information
 * contained in the location. Each segment is stored in the map, if not already present, and a link is
 * stored with the message.
 *
 * @param this_ The traffic message
 * @param ms The mapset to use for matching
 * @param data Data for the segments added to the map
 * @param map The traffic map
 * @param route The route affected by the changes
 *
 * @return `true` if the locations were matched successfully, `false` if there was a failure.
 */
static int traffic_message_add_segments(struct traffic_message * this_, struct mapset * ms, struct seg_data * data,
                                        struct map *map, struct route * route) {
    int i;

    struct coord_geo * coords[] = {NULL, NULL, NULL};
    struct coord * pcoords[] = {NULL, NULL, NULL};

    /* How many point pairs coords contains (number of members minus one) */
    int point_pairs = -1;

    /* Which members of coords are the end points */
    int endpoints = 0;

    /* The direction (positive or negative) */
    int dir = 1;

    /* Start point for the route path */
    struct route_graph_point * p_start = NULL;

    /* Current and previous segment */
    struct route_graph_segment *s = NULL;
    struct route_graph_segment *s_prev;

    /* Iterator for the route path */
    struct route_graph_point *p_iter;

    /* route graph for simplified routing */
    struct route_graph *rg;

    /* Coordinate count for matched segment */
    int ccnt;

    /* Coordinates of matched segment and pointer into it, order as read from map */
    struct coord *c, ca[2048];

    /* Coordinates of matched segment, sorted */
    struct coord *cd, *cs;

    /* Speed calculated in various ways */
    int maxspeed, speed, penalized_speed, factor_speed;

    /* Delay for the current segment */
    int delay;

    /* Number of new segments and existing segments */
    int count = 0, prev_count;

    /* Length of location */
    int len;

    /* The message's previous list of items */
    struct item ** prev_items;

    /* The next item in the message's list of items */
    struct item ** next_item;

    /* Flags for the next item to add */
    int flags;

    /* The last item added */
    struct item * item;

    /* Projected coordinates of start and end points of the actual location
     * (if at is set, both point to the same coordinates) */
    struct coord * c_from, * c_to;

    /* Matched points */
    GList * points;
    GList * points_iter;

    /* The corresponding point data */
    struct point_data * pd;

    /* The match score of the current point */
    int score;

    /* Current and minimum cost to reference point */
    int val, minval;

    /* Start of extended route */
    struct route_graph_point * start_new;

    /* Last segment of the route (before extension) */
    struct route_graph_segment * s_last = NULL;

    /* Aligned points */
    struct route_graph_point * p_from;
    struct route_graph_point * p_to;

    dbg(lvl_debug, "*****checkpoint ADD-1");
    if (!data) {
        dbg(lvl_error, "no data for segments, aborting");
        return 0;
    }

    if (this_->location->ramps != location_ramps_none)
        /* TODO Ramps, not supported yet */
        return 0;

    /* Main carriageway */

    dbg(lvl_debug, "*****checkpoint ADD-2");
    /* get point triple and enclosing rectangle */
    endpoints = traffic_location_get_point_triple(this_->location, &coords[0]);
    if (!endpoints) {
        dbg(lvl_error, "invalid location (mandatory points missing)");
        return 0;
    }
    traffic_location_set_enclosing_rect(this_->location, &coords[0]);
    for (i = 0; i < 3; i++)
        if (coords[i]) {
            pcoords[i] = g_new0(struct coord, 1);
            transform_from_geo(projection_mg, coords[i], pcoords[i]);
            point_pairs++;
        }

    if (this_->location->at && !(this_->location->from || this_->location->to))
        /* TODO Point location with no auxiliary points, not supported yet */
        return 0;

    dbg(lvl_debug, "*****checkpoint ADD-3");
    rg = traffic_location_get_route_graph(this_->location, ms);

    /* transform coordinates */
    c_from = (endpoints & 4) ? pcoords[0] : pcoords[1];
    c_to = (endpoints & 1) ? pcoords[2] : pcoords[1];

    /* determine segments */
    dbg(lvl_debug, "*****checkpoint ADD-4 (loop start)");
    while (1) { /* once for each direction (loop logic at the end) */
        dbg(lvl_debug, "*****checkpoint ADD-4.1");
        if (point_pairs == 1) {
            if (dir > 0)
                p_start = traffic_route_flood_graph(rg, data,
                                                    pcoords[0] ? pcoords[0] : pcoords[1],
                                                    pcoords[2] ? pcoords[2] : pcoords[1], NULL);
            else
                p_start = traffic_route_flood_graph(rg, data,
                                                    pcoords[2] ? pcoords[2] : pcoords[1],
                                                    pcoords[0] ? pcoords[0] : pcoords[1], NULL);
            dbg(lvl_debug, "*****checkpoint ADD-4.1.1");
        } else if (point_pairs == 2) {
            /*
             * If we have more than two points, create the route in two stages (from the first to the second point,
             * then from the second to the third point) and concatenate them. This could easily be extended to any
             * number of points, provided they are spaced sufficiently far apart to calculate a route between each pair
             * of subsequent points.
             * This will create a kind of “Frankenstein route” in which the cost of points does not decrease
             * continuously but has an upward leap as we pass the middle point. This is not an issue as long as we do
             * not do any further processing based on point cost (which we currently don’t).
             * If the route needs to be extended beyond the start point, this has to be done after the first stage,
             * as doing so relies on the route graph for that stage.
             */
            /* TODO handle cases in which the route goes through the "third" point
             * (this should not happen; if it does, we need to detect and fix it) */
            if (dir > 0)
                p_start = traffic_route_flood_graph(rg, data, pcoords[0], pcoords[1], NULL);
            else
                p_start = traffic_route_flood_graph(rg, data, pcoords[2], pcoords[1], NULL);
            if ((this_->location->fuzziness == location_fuzziness_low_res)
                    || this_->location->at || this_->location->not_via) {
                /* extend start to next junction */
                start_new = traffic_route_prepend(rg, p_start);
                if (start_new)
                    p_start = start_new;
            }
            if (dir > 0) {
                if (!p_start) {
                    /* fallback if calculating the first piece of the route failed */
                    p_start = traffic_route_flood_graph(rg, data, pcoords[1], pcoords[2], NULL);
                    start_new = traffic_route_prepend(rg, p_start);
                } else
                    traffic_route_flood_graph(rg, data, pcoords[1], pcoords[2], p_start);
            } else {
                if (!p_start) {
                    /* fallback if calculating the first piece of the route failed */
                    p_start = traffic_route_flood_graph(rg, data, pcoords[1], pcoords[0], NULL);
                    start_new = traffic_route_prepend(rg, p_start);
                } else
                    traffic_route_flood_graph(rg, data, pcoords[1], pcoords[0], p_start);
            }
            dbg(lvl_debug, "*****checkpoint ADD-4.1.2");
        }

        dbg(lvl_debug, "*****checkpoint ADD-4.2");
        /* tweak ends (find the point where the ramp touches the main road) */
        if ((this_->location->fuzziness == location_fuzziness_low_res)
                || this_->location->at || this_->location->not_via) {
            dbg(lvl_debug, "*****checkpoint ADD-4.2.1");
            /* tweak end point */
            if (this_->location->at)
                points = traffic_location_get_matching_points(this_->location, 1, rg, p_start, 0, ms);
            else if (dir > 0)
                points = traffic_location_get_matching_points(this_->location, 2, rg, p_start, 0, ms);
            else
                points = traffic_location_get_matching_points(this_->location, 0, rg, p_start, 0, ms);
            if (!p_start) {
                dbg(lvl_error, "end point not found on map");
                for (points_iter = points; points_iter; points_iter = g_list_next(points_iter))
                    g_free(points_iter->data);
                g_list_free(points);
                route_graph_free_points(rg);
                route_graph_free_segments(rg);
                g_free(rg);
                for (i = 0; i < 3; i++)
                    g_free(pcoords[i]);
                return 0;
            }
            s = p_start ? p_start->seg : NULL;
            p_iter = p_start;

            dbg(lvl_debug, "*****checkpoint ADD-4.2.2");
            /* extend end to next junction */
            for (s = p_start ? p_start->seg : NULL; s; s = p_iter->seg) {
                dbg(lvl_debug, "*****checkpoint ADD-4.2.2.1, s=%p, p_iter=%p (%d)", s, p_iter, p_iter ? p_iter->value : INT_MAX);
                s_last = s;
                if (s->start == p_iter)
                    p_iter = s->end;
                else
                    p_iter = s->start;
            }
            s = traffic_route_append(rg, s_last, p_iter);
            p_iter->seg = s;

            s = p_start ? p_start->seg : NULL;
            s_prev = NULL;
            p_iter = p_start;
            minval = INT_MAX;
            p_to = NULL;

            dbg(lvl_debug, "*****checkpoint ADD-4.2.3");
            struct coord_geo wgs;
            while (p_iter) {
                transform_to_geo(projection_mg, &(p_iter->c), &wgs);
                dbg(lvl_debug, "*****checkpoint ADD-4.2.3, p_iter=%p (value=%d)\nhttps://www.openstreetmap.org?mlat=%f&mlon=%f/#map=13",
                    p_iter, p_iter->value, wgs.lat, wgs.lng);
                if (route_graph_point_is_endpoint_candidate(p_iter, s_prev)) {
                    score = traffic_location_get_point_match(this_->location, p_iter,
                            this_->location->at ? 1 : (dir > 0) ? 2 : 0,
                            rg, p_start, 0, ms);
                    pd = NULL;
                    for (points_iter = points; points_iter && (score < 100); points_iter = g_list_next(points_iter)) {
                        pd = (struct point_data *) points_iter->data;
                        if ((pd->p == p_iter) && (pd->score > score))
                            score = pd->score;
                    }
                    val = transform_distance(projection_mg, &p_iter->c, (dir > 0) ? c_to : c_from);
                    val += (val * (100 - score) * (PENALTY_POINT_MATCH) / 100);
                    if (val < minval) {
                        minval = val;
                        p_to = p_iter;
                        dbg(lvl_debug, "candidate end point found, point %p, value %d (score %d)", p_iter, val, score);
                    }
                }

                if (!s)
                    p_iter = NULL;
                else  {
                    p_iter = (s->start == p_iter) ? s->end : s->start;
                    s_prev = s;
                    s = p_iter->seg;
                }
            }

            dbg(lvl_debug, "*****checkpoint ADD-4.2.4");
            for (points_iter = points; points_iter; points_iter = g_list_next(points_iter))
                g_free(points_iter->data);
            g_list_free(points);

            dbg(lvl_debug, "*****checkpoint ADD-4.2.5");
            /* tweak start point */
            if (this_->location->at)
                points = traffic_location_get_matching_points(this_->location, 1, rg, p_start, 1, ms);
            else if (dir > 0)
                points = traffic_location_get_matching_points(this_->location, 0, rg, p_start, 1, ms);
            else
                points = traffic_location_get_matching_points(this_->location, 2, rg, p_start, 1, ms);
            s_prev = NULL;
            minval = INT_MAX;
            p_from = NULL;

            transform_to_geo(projection_mg, &(p_start->c), &wgs);
            dbg(lvl_debug, "*****checkpoint ADD-4.2.6, p_start=%p\nhttps://www.openstreetmap.org?mlat=%f&mlon=%f/#map=13",
                p_start, wgs.lat, wgs.lng);
            if (point_pairs == 1) {
                /* extend start to next junction (if we have more than two points, this has already been done) */
                start_new = traffic_route_prepend(rg, p_start);
                if (start_new)
                    p_start = start_new;
            }

            s = p_start ? p_start->seg : NULL;
            p_iter = p_start;
            dbg(lvl_debug, "*****checkpoint ADD-4.2.7");
            while (p_iter) {
                transform_to_geo(projection_mg, &(p_iter->c), &wgs);
                dbg(lvl_debug, "*****checkpoint ADD-4.2.7, p_iter=%p (value=%d)\nhttps://www.openstreetmap.org?mlat=%f&mlon=%f/#map=13",
                    p_iter, p_iter->value, wgs.lat, wgs.lng);
                if (route_graph_point_is_endpoint_candidate(p_iter, s_prev)) {
                    score = traffic_location_get_point_match(this_->location, p_iter,
                            this_->location->at ? 1 : (dir > 0) ? 0 : 2,
                            rg, p_start, 1, ms);
                    pd = NULL;
                    for (points_iter = points; points_iter && (score < 100); points_iter = g_list_next(points_iter)) {
                        pd = (struct point_data *) points_iter->data;
                        if ((pd->p == p_iter) && (pd->score > score))
                            score = pd->score;
                    }
                    val = transform_distance(projection_mg, &p_iter->c, (dir > 0) ? c_from : c_to);
                    /* TODO does attribute matching make sense for the start segment? */
                    val += (val * (100 - score) * (PENALTY_POINT_MATCH) / 100);
                    if (val < minval) {
                        minval = val;
                        p_from = p_iter;
                        dbg(lvl_debug, "candidate start point found, point %p, value %d (score %d)",
                            p_iter, val, score);
                    }
                }

                if (!s)
                    p_iter = NULL;
                else {
                    p_iter = (s->start == p_iter) ? s->end : s->start;
                    s_prev = s;
                    s = p_iter->seg;
                }
            }

            dbg(lvl_debug, "*****checkpoint ADD-4.2.8");
            for (points_iter = points; points_iter; points_iter = g_list_next(points_iter))
                g_free(points_iter->data);
            g_list_free(points);

            if (!p_from)
                p_from = p_start;

            dbg(lvl_debug, "*****checkpoint ADD-4.2.9");
            /* ensure we have at least one segment */
            if ((p_from == p_to) || !p_from->seg) {
                dbg(lvl_debug, "*****checkpoint ADD-4.2.9.1");
                p_iter = p_start;
                dbg(lvl_debug, "*****checkpoint ADD-4.2.9.2");
                while (p_iter->seg) {
                    dbg(lvl_debug, "*****checkpoint ADD-4.2.9.2.1, p_iter=%p, p_iter->seg=%p", p_iter, p_iter ? p_iter->seg : NULL);
                    if (p_iter == p_iter->seg->start) {
                        dbg(lvl_debug, "*****checkpoint ADD-4.2.9.2.2 (p_iter == p_iter->seg->start)");
                        /* compare to the last point: because p_to may be NULL here, we're comparing to
                         * p_from instead, which at this point is guaranteed to be non-NULL and either
                         * equal to p_to or without a successor, making it the designated end point. */
                        if (p_iter->seg->end == p_from)
                            break;
                        dbg(lvl_debug, "*****checkpoint ADD-4.2.9.2.3");
                        p_iter = p_iter->seg->end;
                        dbg(lvl_debug, "*****checkpoint ADD-4.2.9.2.4");
                    } else {
                        dbg(lvl_debug, "*****checkpoint ADD-4.2.9.2.2 (p_iter != p_iter->seg->start)");
                        if (p_iter->seg->start == p_from)
                            break;
                        dbg(lvl_debug, "*****checkpoint ADD-4.2.9.2.3");
                        p_iter = p_iter->seg->start;
                        dbg(lvl_debug, "*****checkpoint ADD-4.2.9.2.4");
                    }
                }
                if (p_from->seg) {
                    dbg(lvl_debug, "*****checkpoint ADD-4.2.9.3, p_from->seg is non-NULL");
                    /* decide between predecessor and successor of the point, based on proximity */
                    p_to = (p_from == p_from->seg->end) ? p_from->seg->start : p_from->seg->end;
                    if (transform_distance(projection_mg, &p_to->c, pcoords[1] ? pcoords[1] : pcoords[2])
                            > transform_distance(projection_mg, &p_iter->c, pcoords[1] ? pcoords[1] : pcoords[2])) {
                        p_to = p_from;
                        p_from = p_iter;
                    }
                } else {
                    dbg(lvl_debug, "*****checkpoint ADD-4.2.9.3, p_from->seg is NULL");
                    /* p_from has no successor, the segment goes from its predecessor to p_from */
                    p_to = p_from;
                    p_from = p_iter;
                }
            }

            dbg(lvl_debug, "*****checkpoint ADD-4.2.10");
            /* if we have identified a last point, drop everything after it from the path */
            if (p_to)
                p_to->seg = NULL;

            /* set first point to be the start point */
            if (p_from != p_start) {
                dbg(lvl_debug, "changing p_start from %p to %p", p_start, p_from);
            }
            p_start = p_from;
        }

        dbg(lvl_debug, "*****checkpoint ADD-4.3");
        /* calculate route */
        s = p_start ? p_start->seg : NULL;
        p_iter = p_start;

        if (!s)
            dbg(lvl_error, "no segments");

        /* count segments and calculate length */
        prev_count = count;
        count = 0;
        len = 0;
        dbg(lvl_debug, "*****checkpoint ADD-4.4");
        while (s) {
            dbg(lvl_debug, "*****checkpoint ADD-4.4.1 (#%d, p_iter=%p, s=%p, next %p)",
                count, p_iter, s, (s->start == p_iter) ? s->end : s->start);
            count++;
            len += s->data.len;
            if (s->start == p_iter)
                p_iter = s->end;
            else
                p_iter = s->start;
            s = p_iter->seg;
        }
        dbg(lvl_debug, "*****checkpoint ADD-4.5");

        /* add segments */

        s = p_start ? p_start->seg : NULL;
        p_iter = p_start;

        if (this_->priv->items) {
            prev_items = this_->priv->items;
            this_->priv->items = g_new0(struct item *, count + prev_count + 1);
            memcpy(this_->priv->items, prev_items, sizeof(struct item *) * prev_count);
            next_item = this_->priv->items + prev_count;
            g_free(prev_items);
        } else {
            this_->priv->items = g_new0(struct item *, count + 1);
            next_item = this_->priv->items;
        }

        dbg(lvl_debug, "*****checkpoint ADD-4.6 (loop start)");
        while (s) {
            ccnt = item_coord_get_within_range(&s->data.item, ca, 2047, &s->start->c, &s->end->c);
            c = ca;
            cs = g_new0(struct coord, ccnt);
            cd = cs;

            speed = data->speed;
            if ((data->speed != INT_MAX) || data->speed_penalty || (data->speed_factor != 100)) {
                if (s->data.flags & AF_SPEED_LIMIT) {
                    maxspeed = RSD_MAXSPEED(&s->data);
                } else {
                    switch (s->data.item.type) {
                    case type_highway_land:
                    case type_street_n_lanes:
                        maxspeed = 100;
                        break;
                    case type_highway_city:
                    case type_street_4_land:
                        maxspeed = 80;
                        break;
                    case type_street_3_land:
                        maxspeed = 70;
                        break;
                    case type_street_2_land:
                        maxspeed = 65;
                        break;
                    case type_street_1_land:
                        maxspeed = 60;
                        break;
                    case type_street_4_city:
                        maxspeed = 50;
                        break;
                    case type_ramp:
                    case type_street_3_city:
                    case type_street_unkn:
                        maxspeed = 40;
                        break;
                    case type_street_2_city:
                    case type_track_paved:
                        maxspeed = 30;
                        break;
                    case type_track:
                    case type_cycleway:
                        maxspeed = 20;
                        break;
                    case type_roundabout:
                    case type_street_1_city:
                    case type_street_0:
                    case type_living_street:
                    case type_street_service:
                    case type_street_parking_lane:
                    case type_path:
                    case type_track_ground:
                    case type_track_gravelled:
                    case type_track_unpaved:
                    case type_track_grass:
                    case type_bridleway:
                        maxspeed = 10;
                        break;
                    case type_street_pedestrian:
                    case type_footway:
                    case type_steps:
                        maxspeed = 5;
                        break;
                    default:
                        maxspeed = 50;
                    }
                }
                penalized_speed = maxspeed - data->speed_penalty;
                if (penalized_speed < 5)
                    penalized_speed = 5;
                factor_speed = maxspeed * data->speed_factor / 100;
                if (speed > penalized_speed)
                    speed = penalized_speed;
                if (speed > factor_speed)
                    speed = factor_speed;
            }

            if (data->delay)
                delay = data->delay * s->data.len / len;
            else
                delay = data->delay;

            for (i = 0; i < ccnt; i++) {
                *cd++ = *c++;
            }

            if (s->start == p_iter) {
                /* forward direction */
                p_iter = s->end;
                flags = data->flags | (s->data.flags & AF_ONEWAYMASK)
                        | (data->dir == location_dir_one ? AF_ONEWAY : 0);
            } else {
                /* backward direction */
                p_iter = s->start;
                flags = data->flags | (s->data.flags & AF_ONEWAYMASK)
                        | (data->dir == location_dir_one ? AF_ONEWAYREV : 0);
            }


            item = tm_add_item(map, type_traffic_distortion, s->data.item.id_hi, s->data.item.id_lo, flags, data->attrs, cs, ccnt,
                               this_->id);

            tm_item_add_message_data(item, this_->id, speed, delay, data->attrs, route);

            g_free(cs);

            *next_item = tm_item_ref(item);
            next_item++;

            s = p_iter->seg;
        }

        dbg(lvl_debug, "*****checkpoint ADD-4.7");
        if ((this_->location->directionality == location_dir_one) || (dir < 0))
            break;

        dir = -1;
    }

    dbg(lvl_debug, "*****checkpoint ADD-5");
    route_graph_free_points(rg);
    route_graph_free_segments(rg);
    g_free(rg);

    for (i = 0; i < 3; i++)
        g_free(pcoords[i]);

    dbg(lvl_debug, "*****checkpoint ADD-6");
    return 1;
}

/**
 * @brief Prints a dump of a message to debug output.
 *
 * @param this_ The message to dump
 */
static void traffic_message_dump_to_stderr(struct traffic_message * this_) {
    int i, j;
    char * point_names[5] = {"From", "At", "Via", "Not via", "To"};
    struct traffic_point * points[5];
    char * timestamp = NULL;

    if (!this_) {
        dbg(lvl_debug, "(null)");
        return;
    }

    if (this_->location) {
        points[0] = this_->location->from;
        points[1] = this_->location->at;
        points[2] = this_->location->via;
        points[3] = this_->location->not_via;
        points[4] = this_->location->to;
    } else
        memset(&points, 0, sizeof(struct traffic_point *) * 5);

    dbg(lvl_debug, "id='%s', is_cancellation=%d, is_forecast=%d",
        this_->id, this_->is_cancellation, this_->is_forecast);
    if (this_->receive_time) {
        timestamp = time_to_iso8601(this_->receive_time);
        dbg(lvl_debug, "  First received: %s (%ld)", timestamp, this_->receive_time);
        g_free(timestamp);
    }
    if (this_->update_time) {
        timestamp = time_to_iso8601(this_->update_time);
        dbg(lvl_debug, "  Last updated:   %s (%ld)", timestamp, this_->update_time);
        g_free(timestamp);
    }
    if (this_->start_time) {
        timestamp = time_to_iso8601(this_->start_time);
        dbg(lvl_debug, "  Start time:     %s (%ld)", timestamp, this_->start_time);
        g_free(timestamp);
    }
    if (this_->end_time) {
        timestamp = time_to_iso8601(this_->end_time);
        dbg(lvl_debug, "  End time:       %s (%ld)", timestamp, this_->end_time);
        g_free(timestamp);
    }
    if (this_->expiration_time) {
        timestamp = time_to_iso8601(this_->expiration_time);
        dbg(lvl_debug, "  Expires:        %s (%ld)", timestamp, this_->expiration_time);
        g_free(timestamp);
    }

    /* dump replaced message IDs */
    dbg(lvl_debug, "  replaced_count=%d",
        this_->replaced_count);
    for (i = 0; i < this_->replaced_count; i++) {
        dbg(lvl_debug, "  Replaces: '%s'", this_->replaces[i]);
    }

    /* dump location */
    if (this_->location) {
        dbg(lvl_debug, "  Location: road_type='%s', road_ref='%s', road_name='%s'",
            item_to_name(this_->location->road_type), this_->location->road_ref,
            this_->location->road_name);
        dbg(lvl_debug, "    directionality=%d, destination='%s', direction='%s'",
            this_->location->directionality, this_->location->destination, this_->location->direction);
        dbg(lvl_debug, "    fuzziness=%s, ramps=%s, tmc_table='%s', tmc_direction=%+d",
            location_fuzziness_to_string(this_->location->fuzziness),
            location_ramps_to_string(this_->location->ramps), this_->location->tmc_table,
            this_->location->tmc_direction);
        for (i = 0; i < 5; i++) {
            if (points[i]) {
                dbg(lvl_debug, "    %s: lat=%.5f, lng=%.5f",
                    point_names[i], points[i]->coord.lat, points[i]->coord.lng);
                dbg(lvl_debug, "      junction_name='%s', junction_ref='%s', tmc_id='%s'",
                    points[i]->junction_name, points[i]->junction_ref, points[i]->tmc_id);
            } else {
                dbg(lvl_debug, "    %s: (null)",
                    point_names[i]);
            }
        }
    } else {
        dbg(lvl_debug, "  Location: null");
    }

    /* dump events */
    dbg(lvl_debug, "  event_count=%d",
        this_->event_count);
    for (i = 0; i < this_->event_count; i++) {
        dbg(lvl_debug, "  Event: event_class=%s, type=%s, length=%d m, speed=%d km/h",
            event_class_to_string(this_->events[i]->event_class),
            event_type_to_string(this_->events[i]->type),
            this_->events[i]->length, this_->events[i]->speed);
        /* TODO quantifier */

        /* dump supplementary information */
        dbg(lvl_debug, "    si_count=%d",
            this_->events[i]->si_count);
        for (j = 0; j < this_->events[i]->si_count; j++) {
            dbg(lvl_debug, "    Supplementary Information: si_class=%s, type=%s",
                si_class_to_string(this_->events[i]->si[j]->si_class),
                si_type_to_string(this_->events[i]->si[j]->type));
            /* TODO quantifier */
        }
    }
}

/**
 * @brief Whether the contents of a message are valid.
 *
 * This identifies any malformed messages in which mandatory members are not set.
 *
 * @return true if the message is valid, false if it is malformed
 */
static int traffic_message_is_valid(struct traffic_message * this_) {
    int i;
    int has_valid_events = 0;

    if (!this_->id || !this_->id[0]) {
        dbg(lvl_debug, "ID is NULL or empty");
        return 0;
    }
    if (!this_->receive_time || !this_->update_time) {
        dbg(lvl_debug, "receive_time or update_time not supplied");
        return 0;
    }
    if (!this_->is_cancellation) {
        if (!this_->expiration_time && !this_->end_time) {
            dbg(lvl_debug, "not a cancellation, but neither expiration_time nor end_time supplied");
            return 0;
        }
        if (!this_->location) {
            dbg(lvl_debug, "not a cancellation, but no location supplied");
            return 0;
        }
        if (!traffic_location_is_valid(this_->location)) {
            dbg(lvl_debug, "not a cancellation, but location is invalid");
            return 0;
        }
        if (!this_->event_count || !this_->events) {
            dbg(lvl_debug, "not a cancellation, but no events supplied");
            return 0;
        }
        for (i = 0; i < this_->event_count; i++)
            if (this_->events[i])
                has_valid_events |= traffic_event_is_valid(this_->events[i]);
        if (!has_valid_events) {
            dbg(lvl_debug, "not a cancellation, but all events (%d in total) are invalid", this_->event_count);
            return 0;
        }
    }
    return 1;
}

/**
 * @brief Parses the events of a traffic message.
 *
 * @param message The message to parse
 *
 * @return A `struct seg_data`, or `NULL` if the message contains no usable information
 */
static struct seg_data * traffic_message_parse_events(struct traffic_message * this_) {
    struct seg_data * ret = NULL;

    int i, j;
    int has_flags = 0;
    int flags = 0;

    /* Default assumptions, used only if no explicit values are given */
    int speed = INT_MAX;
    int speed_penalty = 0;
    int speed_factor = 100;
    int delay = 0;

    for (i = 0; i < this_->event_count; i++) {
        if (this_->events[i]->speed != INT_MAX) {
            if (!ret)
                ret = seg_data_new();
            if (ret->speed > this_->events[i]->speed)
                ret->speed = this_->events[i]->speed;
        }
        if (this_->events[i]->event_class == event_class_congestion) {
            switch (this_->events[i]->type) {
            case event_congestion_heavy_traffic:
            case event_congestion_traffic_building_up:
            case event_congestion_traffic_heavier_than_normal:
            case event_congestion_traffic_much_heavier_than_normal:
                /* Heavy traffic: assume 10 km/h below the posted limit, unless explicitly specified */
                if ((this_->events[i]->speed == INT_MAX) && (speed_penalty < 10))
                    speed_penalty = 10;
                break;
            case event_congestion_slow_traffic:
            case event_congestion_traffic_congestion:
            case event_congestion_traffic_problem:
                /* Slow traffic or unspecified congestion: assume half the posted limit, unless explicitly specified */
                if ((this_->events[i]->speed == INT_MAX) && (speed_factor > 50))
                    speed_factor = 50;
                break;
            case event_congestion_queue:
                /* Queuing traffic: assume 20 km/h, unless explicitly specified */
                if ((this_->events[i]->speed == INT_MAX) && (speed > 20))
                    speed = 20;
                break;
            case event_congestion_stationary_traffic:
            case event_congestion_long_queue:
                /* Stationary traffic or long queues: assume 5 km/h, unless explicitly specified */
                if ((this_->events[i]->speed == INT_MAX) && (speed > 5))
                    speed = 5;
                break;
            default:
                break;
            }
        } else if (this_->events[i]->event_class == event_class_delay) {
            switch (this_->events[i]->type) {
            case event_delay_delay:
            case event_delay_long_delay:
                /* Delay or long delay: assume 30 minutes, unless explicitly specified */
                if (this_->events[i]->quantifier) {
                    if (!ret)
                        ret = seg_data_new();
                    if (ret->delay < this_->events[i]->quantifier->u.q_duration)
                        ret->delay = this_->events[i]->quantifier->u.q_duration;
                } else if (delay < 18000)
                    delay = 18000;
                break;
            case event_delay_very_long_delay:
                /* Very long delay: assume 1 hour, unless explicitly specified */
                if (this_->events[i]->quantifier) {
                    if (!ret)
                        ret = seg_data_new();
                    if (ret->delay < this_->events[i]->quantifier->u.q_duration)
                        ret->delay = this_->events[i]->quantifier->u.q_duration;
                } else if (delay < 36000)
                    delay = 36000;
                break;
            case event_delay_several_hours:
            case event_delay_uncertain_duration:
                /* Delay of several hours or uncertain duration: assume 3 hours */
                if (delay < 108000)
                    delay = 108000;
                break;
            default:
                break;
            }
        } else if (this_->events[i]->event_class == event_class_restriction) {
            switch (this_->events[i]->type) {
            case event_restriction_blocked:
            case event_restriction_blocked_ahead:
            case event_restriction_carriageway_blocked:
            case event_restriction_carriageway_closed:
            case event_restriction_closed:
            case event_restriction_closed_ahead:
                if (!ret)
                    ret = seg_data_new();
                ret->speed = 0;
                break;
            case event_restriction_intermittent_closures:
            case event_restriction_batch_service:
            case event_restriction_single_alternate_line_traffic:
                /* Assume 30% of the posted limit for all of these cases */
                if (speed_factor > 30)
                    speed_factor = 30;
                break;
            case event_restriction_lane_blocked:
            case event_restriction_lane_closed:
            case event_restriction_reduced_lanes:
                /* Assume speed is reduced proportionally to number of lanes, and never higher than 80 */
                speed = 80;
                /* TODO determine actual numbers of lanes */
                speed_factor = 67;
                break;
            case event_restriction_contraflow:
                /* Contraflow: assume 80, unless explicitly specified */
                speed = 80;
                break;
            /* restriction_speed_limit is not in the list: either it comes with a maxspeed attribute, which gets
             * evaluated regardless of the event it comes with, and if it doesn’t come with one, it carries no
             * useful information. */
            default:
                break;
            }
        }

        for (j = 0; j < this_->events[i]->si_count; j++) {
            switch (this_->events[i]->si[j]->type) {
            case si_vehicle_all:
                /* For all vehicles */
                flags |= AF_ALL;
                has_flags = 1;
                break;
            case si_vehicle_bus:
                /* For buses only */
                /* TODO what about other (e.g. chartered) buses? */
                flags |= AF_PUBLIC_BUS;
                has_flags = 1;
                break;
            case si_vehicle_car:
                /* For cars only */
                flags |= AF_CAR;
                has_flags = 1;
                break;
            case si_vehicle_car_with_caravan:
                /* For cars with caravans only */
                /* TODO no matching flag */
                has_flags = 1;
                break;
            case si_vehicle_car_with_trailer:
                /* For cars with trailers only */
                /* TODO no matching flag */
                has_flags = 1;
                break;
            case si_vehicle_hazmat:
                /* For hazardous loads only */
                flags |= AF_DANGEROUS_GOODS;
                has_flags = 1;
                break;
            case si_vehicle_hgv:
                /* For heavy trucks only */
                flags |= AF_TRANSPORT_TRUCK | AF_DELIVERY_TRUCK;
                has_flags = 1;
                break;
            case si_vehicle_motor:
                /* For all motor vehicles */
                flags |= AF_MOTORIZED_FAST | AF_MOPED;
                has_flags = 1;
                break;
            case si_vehicle_with_trailer:
                /* For vehicles with trailers only */
                /* TODO no matching flag */
                has_flags = 1;
                break;
            default:
                break;
            }
        }
    }

    /* if no vehicle type is specified in supplementary information, assume all */
    if (!has_flags) {
        if (this_->location->road_type == type_line_unspecified)
            flags = AF_ALL;
        else
            flags = AF_MOTORIZED_FAST | AF_MOPED;
    }

    if (!ret)
        ret = seg_data_new();

    /* use implicit values if no explicit ones are given */
    if ((speed != INT_MAX) || speed_penalty || (speed_factor != 100) || delay) {
        if (ret->speed == INT_MAX) {
            ret->speed = speed;
            ret->speed_penalty = speed_penalty;
            ret->speed_factor = speed_factor;
        }
        if (!ret->delay)
            ret->delay = delay;
    }

    ret->dir = this_->location->directionality;
    ret->flags = flags;

    return ret;
}

/**
 * @brief Removes message data from the items associated with a message.
 *
 * Removing message data also triggers an update of the affected items’ attributes.
 *
 * It is possible to skip items associated with a particular message from being removed by passing that
 * message as the `new` argument. This is used for message updates, as this function is called after the
 * items associated with both the old and the new message have already been updated. Skipping items
 * referenced by `new` ensures that message data is only stripped from items which are no longer being
 * referenced by the updated message.
 *
 * If the IDs of `old` and `new` differ, `new` is ignored.
 *
 * @param old The message whose data it so be removed from its associated items
 * @param new If non-NULL, items referenced by this message will be skipped, see description
 * @param route The route affected by the changes
 */
static void traffic_message_remove_item_data(struct traffic_message * old, struct traffic_message * new,
        struct route * route) {
    int i, j;
    int skip;
    struct item_priv * ip;
    GList * msglist;
    struct item_msg_priv * msgdata;

    if (new && strcmp(old->id, new->id))
        new = NULL;

    for (i = 0; old->priv->items && old->priv->items[i]; i++) {
        skip = 0;
        if (new)
            for (j = 0; new->priv->items && new->priv->items[j] && !skip; j++)
                skip |= (old->priv->items[i] == new->priv->items[j]);
        if (!skip) {
            ip = (struct item_priv *) old->priv->items[i]->priv_data;
            for (msglist = ip->message_data; msglist; ) {
                msgdata = (struct item_msg_priv *) msglist->data;
                msglist = g_list_next(msglist);
                if (!strcmp(msgdata->message_id, old->id)) {
                    ip->message_data = g_list_remove(ip->message_data, msgdata);
                    g_free(msgdata->message_id);
                    g_free(msgdata);
                }
            }
            tm_item_update_attrs(old->priv->items[i], route);
        }
    }
}

/**
 * @brief Ensures the traffic instance points to valid shared data.
 *
 * This method first examines all registered traffic instances to see if one of them has the `shared`
 * member set. If that is the case, the current instance copies the `shared` pointer of the other
 * instance. Otherwise a new `struct traffic_shared_priv` is created and its address stored in `shared`.
 *
 * Calling this method on a traffic instance with a non-NULL `shared` member has no effect.
 *
 * @param this_ The traffic instance
 */
static void traffic_set_shared(struct traffic *this_) {
    struct attr_iter *iter;
    struct attr attr;
    struct traffic * traffic;

    dbg(lvl_debug, "enter");

    if (!this_->shared) {
        iter = navit_attr_iter_new();
        while (navit_get_attr(this_->navit, attr_traffic, &attr, iter)) {
            traffic = (struct traffic *) attr.u.navit_object;
            if (traffic->shared)
                this_->shared = traffic->shared;
        }
        navit_attr_iter_destroy(iter);
    }

    if (!this_->shared) {
        this_->shared = g_new0(struct traffic_shared_priv, 1);
    }
}

/**
 * @brief Dumps all currently active traffic messages to an XML file.
 */
static void traffic_dump_messages_to_xml(struct traffic * this_) {
    /* add the configuration directory to the name of the file to use */
    char *traffic_filename = g_strjoin(NULL, navit_get_user_data_directory(TRUE),
                                       "/traffic.xml", NULL);
    GList * msgiter;
    struct traffic_message * message;
    char * strval;
    char * point_names[5] = {"from", "at", "via", "not_via", "to"};
    struct traffic_point * points[5];
    int i, j;

    if (traffic_filename) {
        FILE *f = fopen(traffic_filename,"w");
        if (f) {
            fprintf(f, "<navit_messages>\n");
            for (msgiter = this_->shared->messages; msgiter; msgiter = g_list_next(msgiter)) {
                message = (struct traffic_message *) msgiter->data;
                points[0] = message->location->from;
                points[1] = message->location->at;
                points[2] = message->location->via;
                points[3] = message->location->not_via;
                points[4] = message->location->to;

                strval = time_to_iso8601(message->receive_time);
                fprintf(f, "  <message id=\"%s\" receive_time=\"%s\"", message->id, strval);
                g_free(strval);
                strval = time_to_iso8601(message->update_time);
                fprintf(f, " update_time=\"%s\"", strval);
                g_free(strval);
                if (message->start_time) {
                    strval = time_to_iso8601(message->start_time);
                    fprintf(f, " start_time=\"%s\"", strval);
                    g_free(strval);
                }
                if (message->end_time) {
                    strval = time_to_iso8601(message->end_time);
                    fprintf(f, " end_time=\"%s\"", strval);
                    g_free(strval);
                }
                if (message->expiration_time) {
                    strval = time_to_iso8601(message->expiration_time);
                    fprintf(f, " expiration_time=\"%s\"", strval);
                    g_free(strval);
                }
                if (message->is_forecast)
                    fprintf(f, " forecast=\"%d\"", message->is_forecast);
                fprintf(f, ">\n");

                fprintf(f, "    <location directionality=\"%s\"",
                        message->location->directionality == location_dir_one ? "ONE_DIRECTION" : "BOTH_DIRECTIONS");
                if (message->location->fuzziness)
                    fprintf(f, " fuzziness=\"%s\"", location_fuzziness_to_string(message->location->fuzziness));
                if (message->location->ramps)
                    fprintf(f, " ramps=\"%s\"", location_ramps_to_string(message->location->ramps));
                if (message->location->road_type != type_line_unspecified)
                    fprintf(f, " road_class=\"%s\"", item_to_name(message->location->road_type));
                if (message->location->road_ref)
                    fprintf(f, " road_ref=\"%s\"", message->location->road_ref);
                if (message->location->road_name)
                    fprintf(f, " road_name=\"%s\"", message->location->road_name);
                if (message->location->destination)
                    fprintf(f, " destination=\"%s\"", message->location->destination);
                if (message->location->direction)
                    fprintf(f, " direction=\"%s\"", message->location->direction);
                if ((message->location->directionality == location_dir_one)
                        && message->location->tmc_direction)
                    fprintf(f, " tmc_direction=\"%+d\"", message->location->tmc_direction);
                if (message->location->tmc_table)
                    fprintf(f, " tmc_table=\"%s\"", message->location->tmc_table);
                fprintf(f, ">\n");

                for (i = 0; i < 5; i++)
                    if (points[i]) {
                        fprintf(f, "      <%s", point_names[i]);
                        if (points[i]->junction_name)
                            fprintf(f, " junction_name=\"%s\"", points[i]->junction_name);
                        if (points[i]->junction_ref)
                            fprintf(f, " junction_ref=\"%s\"", points[i]->junction_ref);
                        if (points[i]->tmc_id)
                            fprintf(f, " tmc_id=\"%s\"", points[i]->tmc_id);
                        fprintf(f, ">");
                        fprintf(f, "%+f %+f", points[i]->coord.lat, points[i]->coord.lng);
                        fprintf(f, "</%s>\n", point_names[i]);
                    }

                fprintf(f, "    </location>\n");

                fprintf(f, "    <events>\n");
                for (i = 0; i < message->event_count; i++) {
                    fprintf(f, "      <event class=\"%s\" type=\"%s\"",
                            event_class_to_string(message->events[i]->event_class),
                            event_type_to_string(message->events[i]->type));
                    if (message->events[i]->length >= 0)
                        fprintf(f, " length=\"%d\"", message->events[i]->length);
                    if (message->events[i]->speed != INT_MAX)
                        fprintf(f, " speed=\"%d\"", message->events[i]->speed);
                    /* TODO message->events[i]->quantifier */
                    fprintf(f, ">\n");

                    for (j = 0; j < message->events[i]->si_count; j++) {
                        fprintf(f, "        <supplementary_info class=\"%s\" type=\"%s\"",
                                si_class_to_string(message->events[i]->si[j]->si_class),
                                si_type_to_string(message->events[i]->si[j]->type));
                        /* TODO message->events[i]->si[j]->quantifier */
                        fprintf(f, "/>\n");
                    }

                    fprintf(f, "      </event>\n");
                }
                fprintf(f, "    </events>\n");
                fprintf(f, "  </message>\n");
            }
            fprintf(f, "</navit_messages>\n");
            fclose(f);
        } else {
            dbg(lvl_error,"could not open file for traffic messages");

        } /* else - if (f) */
        g_free(traffic_filename);			/* free the file name */
    } /* if (traffic_filename) */
}

/**
 * @brief Processes new traffic messages.
 *
 * This is the internal backend for `traffic_process_messages()`. It is also used internally.
 *
 * The behavior of this function can be controlled via flags.
 *
 * `PROCESS_MESSAGES_PURGE_EXPIRED` causes expired messages to be purged from the message store after
 * new messages have been processed. It is intended to be used with timer-triggered calls.
 *
 * `PROCESS_MESSAGES_NO_DUMP_STORE` prevents saving of the message store to disk, intended to be used
 * when reading stored message data on startup.
 *
 * Traffic messages are always read from `this->shared->message_queue`. It can be empty, which makes sense e.g. when
 * the `PROCESS_MESSAGES_PURGE_EXPIRED` flag is used, to just purge expired messages.
 *
 * @param this_ The traffic instance
 * @param flags Flags, see description
 *
 * @return A combination of flags, `MESSAGE_UPDATE_MESSAGES` indicating that new messages were processed
 * and `MESSAGE_UPDATE_SEGMENTS` that segments were changed
 */
/* TODO what if the update for a still-valid message expires in the past? */
static int traffic_process_messages_int(struct traffic * this_, int flags) {
    /* Start and current time */
    struct timeval start, now;

    /* Current message */
    struct traffic_message * message;

    /* Return value */
    int ret = 0;

    /* Number of messages processed so far */
    int i = 0;

    /* Iterator over messages */
    GList * msg_iter;

    /* Stored message being compared */
    struct traffic_message * stored_msg;

    /* Messages to remove */
    GList * msgs_to_remove = NULL;

    /* Pointer into messages[i]->replaces */
    char ** replaces;

    /* Attributes for traffic distortions generated from the current traffic message */
    struct seg_data * data;

    /* Message replaced by the current one whose segments can be reused */
    struct traffic_message * swap_candidate;

    /* Temporary store for swapping locations and items */
    struct traffic_location * swap_location;
    struct item ** swap_items;

    /* Time elapsed since start */
    double msec = 0;

    if (this_->shared->message_queue)
        dbg(lvl_debug, "*****enter, %d messages in queue", g_list_length(this_->shared->message_queue));

    gettimeofday(&start, NULL);
    for (; this_->shared->message_queue && (msec < TIME_SLICE);
            this_->shared->message_queue = g_list_remove(this_->shared->message_queue, message)) {
        message = (struct traffic_message *) this_->shared->message_queue->data;
        i++;
        if (message->expiration_time < time(NULL)) {
            dbg(lvl_debug, "message is no longer valid, ignoring");
            traffic_message_destroy(message);
        } else {
            dbg(lvl_debug, "*****checkpoint PROCESS-1, id='%s'", message->id);
            ret |= MESSAGE_UPDATE_MESSAGES;

            for (msg_iter = this_->shared->messages; msg_iter; msg_iter = g_list_next(msg_iter)) {
                stored_msg = (struct traffic_message *) msg_iter->data;
                if (!strcmp(stored_msg->id, message->id))
                    msgs_to_remove = g_list_append(msgs_to_remove, stored_msg);
                else
                    for (replaces = ((struct traffic_message *) this_->shared->message_queue->data)->replaces; replaces; replaces++)
                        if (!strcmp(stored_msg->id, *replaces) && !g_list_find(msgs_to_remove, message))
                            msgs_to_remove = g_list_append(msgs_to_remove, stored_msg);
            }

            if (!message->is_cancellation) {
                dbg(lvl_debug, "*****checkpoint PROCESS-2");
                /* if the message is not just a cancellation, store it and match it to the map */
                data = traffic_message_parse_events(message);
                swap_candidate = NULL;

                dbg(lvl_debug, "*****checkpoint PROCESS-3");
                /* check if any of the replaced messages has the same location and segment data */
                for (msg_iter = msgs_to_remove; msg_iter && !swap_candidate; msg_iter = g_list_next(msg_iter)) {
                    stored_msg = (struct traffic_message *) msg_iter->data;
                    if (seg_data_equals(data, traffic_message_parse_events(stored_msg))
                            && traffic_location_equals(message->location, stored_msg->location))
                        swap_candidate = stored_msg;
                }

                if (swap_candidate) {
                    dbg(lvl_debug, "*****checkpoint PROCESS-4, swap candidate found");
                    /* reuse location and segments if we are replacing a matching message */
                    swap_location = message->location;
                    swap_items = message->priv->items;
                    message->location = swap_candidate->location;
                    message->priv->items = swap_candidate->priv->items;
                    swap_candidate->location = swap_location;
                    swap_candidate->priv->items = swap_items;
                } else {
                    dbg(lvl_debug, "*****checkpoint PROCESS-4, need to find matching segments");
                    /* else find matching segments from scratch */
                    traffic_message_add_segments(message, this_->ms, data, this_->map, this_->rt);
                    ret |= MESSAGE_UPDATE_SEGMENTS;
                }

                g_free(data);

                /* store message */
                this_->shared->messages = g_list_append(this_->shared->messages, message);
                dbg(lvl_debug, "*****checkpoint PROCESS-5");
            }

            /* delete replaced messages */
            if (msgs_to_remove) {
                dbg(lvl_debug, "*****checkpoint PROCESS (messages to remove, start)");
                for (msg_iter = msgs_to_remove; msg_iter; msg_iter = g_list_next(msg_iter)) {
                    stored_msg = (struct traffic_message *) msg_iter->data;
                    if (stored_msg->priv->items)
                        ret |= MESSAGE_UPDATE_SEGMENTS;
                    this_->shared->messages = g_list_remove_all(this_->shared->messages, stored_msg);
                    traffic_message_remove_item_data(stored_msg, message, this_->rt);
                    traffic_message_destroy(stored_msg);
                }

                g_list_free(msgs_to_remove);
                msgs_to_remove = NULL;
                dbg(lvl_debug, "*****checkpoint PROCESS (messages to remove, end)");
            }

            traffic_message_dump_to_stderr(message);

            if (message->is_cancellation)
                traffic_message_destroy(message);

            dbg(lvl_debug, "*****checkpoint PROCESS-6");
        }
        gettimeofday(&now, NULL);
        msec = (now.tv_usec - start.tv_usec) / ((double)1000) + (now.tv_sec - start.tv_sec) * 1000;
    }

    if (i)
        dbg(lvl_debug, "processed %d message(s), %d still in queue", i, g_list_length(this_->shared->message_queue));

    if (this_->shared->message_queue) {
        /* if we're in the middle of the queue, trigger a redraw (if needed) and exit */
        if ((ret & MESSAGE_UPDATE_SEGMENTS) && (navit_get_ready(this_->navit) == 3))
            navit_draw_async(this_->navit, 1);
        return ret;
    } else {
        /* last pass, remove our idle event and callback */
        if (this_->idle_ev)
            event_remove_idle(this_->idle_ev);
        if (this_->idle_cb)
            callback_destroy(this_->idle_cb);
        this_->idle_ev = NULL;
        this_->idle_cb = NULL;
    }

    if (flags & PROCESS_MESSAGES_PURGE_EXPIRED) {
        /* find and remove expired messages */
        for (msg_iter = this_->shared->messages; msg_iter; msg_iter = g_list_next(msg_iter)) {
            stored_msg = (struct traffic_message *) msg_iter->data;
            if (stored_msg->expiration_time < time(NULL))
                msgs_to_remove = g_list_append(msgs_to_remove, stored_msg);
        }

        if (msgs_to_remove) {
            for (msg_iter = msgs_to_remove; msg_iter; msg_iter = g_list_next(msg_iter)) {
                stored_msg = (struct traffic_message *) msg_iter->data;
                if (stored_msg->priv->items)
                    ret |= MESSAGE_UPDATE_SEGMENTS;
                this_->shared->messages = g_list_remove_all(this_->shared->messages, stored_msg);
                traffic_message_remove_item_data(stored_msg, NULL, this_->rt);
                traffic_message_destroy(stored_msg);
            }

            dbg(lvl_debug, "%d message(s) expired", g_list_length(msgs_to_remove));

            g_list_free(msgs_to_remove);
        }
    }

    if (ret && !(flags & PROCESS_MESSAGES_NO_DUMP_STORE)) {
#ifdef TRAFFIC_DEBUG
        /* dump map if messages have been added, deleted or expired */
        tm_dump_to_textfile(this_->map);
#endif

        /* dump message store if new messages have been received */
        traffic_dump_messages_to_xml(this_);
    }

    /* TODO see comment on route_recalculate_partial about thread-safety */
    route_recalculate_partial(this_->rt);

    /* trigger redraw if segments have changed */
    if ((ret & MESSAGE_UPDATE_SEGMENTS) && (navit_get_ready(this_->navit) == 3))
        navit_draw_async(this_->navit, 1);

    return ret;
}

/**
 * @brief The loop function for the traffic module.
 *
 * This function polls backends for new messages and processes them by inserting, removing or modifying
 * traffic distortions and triggering route recalculations as needed.
 */
static void traffic_loop(struct traffic * this_) {
    struct traffic_message ** messages;
    struct traffic_message ** cur_msg;

    messages = this_->meth.get_messages(this_->priv);
    for (cur_msg = messages; cur_msg && *cur_msg; cur_msg++)
        this_->shared->message_queue = g_list_append(this_->shared->message_queue, *cur_msg);
    g_free(messages);

    /* make sure traffic_process_messages_int runs at least once to ensure purging of expired messages */
    if (this_->shared->message_queue) {
        if (this_->idle_ev)
            event_remove_idle(this_->idle_ev);
        if (this_->idle_cb)
            callback_destroy(this_->idle_cb);
        this_->idle_cb = callback_new_2(callback_cast(traffic_process_messages_int),
                                        this_, PROCESS_MESSAGES_PURGE_EXPIRED);
        this_->idle_ev = event_add_idle(50, this_->idle_cb);
    } else
        traffic_process_messages_int(this_, PROCESS_MESSAGES_PURGE_EXPIRED);
}

/**
 * @brief Instantiates the traffic plugin
 *
 * At a minimum, `attrs` must contain a `type` attribute matching one of the available traffic plugins.
 *
 * @param parent The parent, usually the Navit instance
 * @param attrs The attributes for the plugin
 *
 * @return A `traffic` instance.
 */
static struct traffic * traffic_new(struct attr *parent, struct attr **attrs) {
    struct traffic *this_;
    struct traffic_priv *(*traffic_new)(struct navit *nav, struct traffic_methods *meth,
                                        struct attr **attrs, struct callback_list *cbl);
    struct attr *attr;

    attr = attr_search(attrs, NULL, attr_type);
    if (!attr) {
        dbg(lvl_error, "type missing");
        return NULL;
    }
    dbg(lvl_debug, "type='%s'", attr->u.str);
    traffic_new = plugin_get_category_traffic(attr->u.str);
    dbg(lvl_debug, "new=%p", traffic_new);
    if (!traffic_new) {
        dbg(lvl_error, "wrong type '%s'", attr->u.str);
        return NULL;
    }
    this_ = (struct traffic *) navit_object_new(attrs, &traffic_func, sizeof(struct traffic));
    if (parent->type == attr_navit)
        this_->navit = parent->u.navit;
    else {
        dbg(lvl_error, "wrong parent type '%s', only navit is permitted", attr_to_name(parent->type));
        navit_object_destroy((struct navit_object *) this_);
        return NULL;
    }

    this_->priv = traffic_new(parent->u.navit, &this_->meth, this_->attrs, NULL);
    dbg(lvl_debug, "get_messages=%p", this_->meth.get_messages);
    dbg(lvl_debug, "priv=%p", this_->priv);
    if (!this_->priv) {
        dbg(lvl_error, "plugin initialization failed");
        navit_object_destroy((struct navit_object *) this_);
        return NULL;
    }
    navit_object_ref((struct navit_object *) this_);
    dbg(lvl_debug,"return %p", this_);

    // TODO do this once and cycle through all plugins
    this_->callback = callback_new_1(callback_cast(traffic_loop), this_);
    this_->timeout = event_add_timeout(1000, 1, this_->callback); // TODO make interval configurable

    this_->map = NULL;

    if (!this_->shared)
        traffic_set_shared(this_);

    return this_;
}

/**
 * @brief Creates a new XML element structure.
 *
 * Note that the structure of `names` and `values` may differ between XML libraries. Behavior is indicated by the
 * `XML_ATTR_DISTANCE` constant.
 *
 * If `XML_ATTR_DISTANCE == 1`, `names` and `values` are two separate arrays, and `values[n]` is the value that
 * corresponds to `names[n]`.
 *
 * If `XML_ATTR_DISTANCE == 2`, attribute names and values are kept in a single array in which names and values
 * alternate, names first. In this case, `names` points to the array while `values` points to its second element, i.e.
 * the first value. In this case, `value` is invalid for an empty array, and dereferencing it may segfault.
 *
 * @param tag_name The tag name
 * @param names Attribute names
 * @param values Attribute values
 */
static struct xml_element * traffic_xml_element_new(const char *tag_name, const char **names,
        const char **values) {
    struct xml_element * ret = g_new0(struct xml_element, 1);
    const char ** in;
    char ** out;

    ret->tag_name = g_strdup(tag_name);
    if (names) {
        ret->names = g_new0(char *, g_strv_length((gchar **) names) / XML_ATTR_DISTANCE + 1);
        in = names;
        out = ret->names;
        while (*in) {
            *out++ = g_strdup(*in);
            in += XML_ATTR_DISTANCE;
        }
    }
    /* extra check for mixed name-value array */
    if (names && *names && values) {
#if XML_ATTR_DISTANCE == 1
        ret->values = g_new0(char *, g_strv_length((gchar **) values) + 1);
#else
        ret->values = g_new0(char *, g_strv_length((gchar **) values) / XML_ATTR_DISTANCE + 2);
#endif
        in = values;
        out = ret->values;
        while (*in) {
            *out++ = g_strdup(*in++);
#if XML_ATTR_DISTANCE > 1
            if (*in)
                in++;
#endif
        }
    }
    return ret;
}

/**
 * @brief Frees up an XML element structure.
 *
 * This will free up the memory used by the struct and all its members.
 */
static void traffic_xml_element_destroy(struct xml_element * this_) {
    void ** iter;

    g_free(this_->tag_name);
    if (this_->names) {
        for (iter = (void **) this_->names; *iter; iter++)
            g_free(*iter);
        g_free(this_->names);
    }
    if (this_->values) {
        for (iter = (void **) this_->values; *iter; iter++)
            g_free(*iter);
        g_free(this_->values);
    }
    g_free(this_->text);
    g_free(this_);
}

/**
 * @brief Retrieves the value of an XML attribute.
 *
 * @param name The name of the attribute to retrieve
 * @param names All attribute names
 * @param values Attribute values (indices correspond to `names`)
 *
 * @return If `names` contains `name`, the corresponding value is returned, else NULL
 */
static char * traffic_xml_get_attr(const char * attr, char ** names, char ** values) {
    int i;
    for (i = 0; names[i] && values[i]; i++) {
        if (!g_ascii_strcasecmp(attr, names[i]))
            return values[i];
    }
    return NULL;
}

/**
 * @brief Whether the tag stack represents a hierarchy of elements which is recognized.
 *
 * @param state The XML parser state
 *
 * @return True if the stack is valid, false if invalid. An empty stack is considered invalid.
 */
static int traffic_xml_is_tagstack_valid(struct xml_state * state) {
    int ret = 0;
    GList * tagiter;
    struct xml_element * el, * el_parent;

    for (tagiter = g_list_last(state->tagstack); tagiter; tagiter = g_list_previous(tagiter)) {
        el = (struct xml_element *) tagiter->data;
        el_parent = tagiter->next ? tagiter->next->data : NULL;

        if (!g_ascii_strcasecmp(el->tag_name, "navit_messages")
                || !g_ascii_strcasecmp(el->tag_name, "feed"))
            ret = !tagiter->next;
        else if (!g_ascii_strcasecmp((char *) el->tag_name, "message"))
            ret = (!el_parent
                   || !g_ascii_strcasecmp(el_parent->tag_name, "navit_messages")
                   || !g_ascii_strcasecmp(el_parent->tag_name, "feed"));
        else if (!g_ascii_strcasecmp(el->tag_name, "events")
                 || !g_ascii_strcasecmp(el->tag_name, "location")
                 || !g_ascii_strcasecmp(el->tag_name, "merge"))
            ret = (el_parent && !g_ascii_strcasecmp(el_parent->tag_name, "message"));
        else if (!g_ascii_strcasecmp(el->tag_name, "event"))
            ret = (el_parent && !g_ascii_strcasecmp(el_parent->tag_name, "events"));
        else if (!g_ascii_strcasecmp(el->tag_name, "from")
                 || !g_ascii_strcasecmp(el->tag_name, "to")
                 || !g_ascii_strcasecmp(el->tag_name, "at")
                 || !g_ascii_strcasecmp(el->tag_name, "via")
                 || !g_ascii_strcasecmp(el->tag_name, "not_via"))
            ret = (el_parent && !g_ascii_strcasecmp(el_parent->tag_name, "location"));
        else if (!g_ascii_strcasecmp(el->tag_name, "supplementary_info"))
            ret = (el_parent && !g_ascii_strcasecmp(el_parent->tag_name, "event"));
        else if (!g_ascii_strcasecmp(el->tag_name, "replaces"))
            ret = (el_parent && !g_ascii_strcasecmp(el_parent->tag_name, "merge"));
        else
            ret = 0;

        if (!ret)
            break;
    }

    return ret;
}

/**
 * @brief Callback function which gets called when an opening tag is encountered.
 *
 * @param tag_name The tag name
 * @param names Attribute names
 * @param values Attribute values (indices correspond to `names`)
 * @param data Points to a `struct xml_state` holding parser state
 */
static void traffic_xml_start(xml_context *dummy, const char *tag_name, const char **names,
                              const char **values, void *data, GError **error) {
    struct xml_state * state = (struct xml_state *) data;
    struct xml_element * el;

    el = traffic_xml_element_new(tag_name, names, values);
    state->tagstack = g_list_prepend(state->tagstack, el);
    state->is_opened = 1;
    state->is_valid = traffic_xml_is_tagstack_valid(state);
    if (!state->is_valid)
        return;

    dbg(lvl_debug, "OPEN: %s", tag_name);

    if (!g_ascii_strcasecmp((char *) tag_name, "supplementary_info")) {
        state->si = g_list_append(state->si, traffic_suppl_info_new(
                                      si_class_new(traffic_xml_get_attr("class", el->names, el->values)),
                                      si_type_new(traffic_xml_get_attr("type", el->names, el->values)),
                                      /* TODO quantifier */
                                      NULL));
    } else if (!g_ascii_strcasecmp((char *) tag_name, "replaces")) {
        /* TODO */
    }

    /*
     * No handling necessary for:
     *
     * navit_messages: No attributes, everything handled in children's callbacks
     * feed: No attributes, everything handled in children's callbacks
     * message: Everything handled in end callback
     * events: No attributes, everything handled in children's callbacks
     * location: Everything handled in end callback
     * event: Everything handled in end callback
     * merge: No attributes, everything handled in children's callbacks
     * from, to, at, via, not_via: Everything handled in end callback
     */
}

/**
 * @brief Callback function which gets called when a closing tag is encountered.
 *
 * @param tag_name The tag name
 * @param data Points to a `struct xml_state` holding parser state
 */
static void traffic_xml_end(xml_context *dummy, const char *tag_name, void *data, GError **error) {
    struct xml_state * state = (struct xml_state *) data;
    struct xml_element * el = state->tagstack ? (struct xml_element *) state->tagstack->data : NULL;
    struct traffic_message * message;
    struct traffic_point ** point = NULL;

    /* Iterator and child element count */
    int i, count;

    /* Child elements */
    void ** children = NULL;

    /* Iterator for children in GList */
    GList * iter;

    /* Some elements we need to check for null */
    char * tmc_direction;
    char * length;
    char * speed;

    /* New traffic event */
    struct traffic_event * event = NULL;

    float lat, lon;

    if (state->is_valid) {
        dbg(lvl_debug, "  END:  %s", tag_name);

        if (!g_ascii_strcasecmp((char *) tag_name, "message")) {
            count = g_list_length(state->events);
            if (count) {
                children = (void **) g_new0(struct traffic_event *, count);
                iter = state->events;
                for (i = 0; iter && (i < count); i++) {
                    children[i] = iter->data;
                    iter = g_list_next(iter);
                }
            }
            message = traffic_message_new(traffic_xml_get_attr("id", el->names, el->values),
                                          time_new(traffic_xml_get_attr("receive_time", el->names, el->values)),
                                          time_new(traffic_xml_get_attr("update_time", el->names, el->values)),
                                          time_new(traffic_xml_get_attr("expiration_time", el->names, el->values)),
                                          time_new(traffic_xml_get_attr("start_time", el->names, el->values)),
                                          time_new(traffic_xml_get_attr("end_time", el->names, el->values)),
                                          boolean_new(traffic_xml_get_attr("cancellation", el->names, el->values), 0),
                                          boolean_new(traffic_xml_get_attr("forecast", el->names, el->values), 0),
                                          /* TODO replaces */
                                          0, NULL,
                                          state->location,
                                          count,
                                          (struct traffic_event **) children);
            if (!traffic_message_is_valid(message)) {
                dbg(lvl_error, "malformed message detected, skipping");
                traffic_message_destroy(message);
            } else
                state->messages = g_list_append(state->messages, message);
            g_free(children);
            state->location = NULL;
            g_list_free(state->events);
            state->events = NULL;
            /* TODO replaces */
        } else if (!g_ascii_strcasecmp((char *) tag_name, "location")) {
            tmc_direction = traffic_xml_get_attr("tmc_direction", el->names, el->values);
            state->location = traffic_location_new(state->at, state->from,
                                                   state->to, state->via, state->not_via,
                                                   traffic_xml_get_attr("destination", el->names, el->values),
                                                   traffic_xml_get_attr("direction", el->names, el->values),
                                                   location_dir_new(traffic_xml_get_attr("directionality", el->names, el->values)),
                                                   location_fuzziness_new(traffic_xml_get_attr("fuzziness", el->names, el->values)),
                                                   location_ramps_new(traffic_xml_get_attr("ramps", el->names, el->values)),
                                                   item_type_from_road_type(traffic_xml_get_attr("road_class", el->names, el->values),
                                                           /* TODO revisit default for road_is_urban */
                                                           boolean_new(traffic_xml_get_attr("road_is_urban", el->names, el->values), 0)),
                                                   traffic_xml_get_attr("road_name", el->names, el->values),
                                                   traffic_xml_get_attr("road_ref", el->names, el->values),
                                                   traffic_xml_get_attr("tmc_table", el->names, el->values),
                                                   tmc_direction ? atoi(tmc_direction) : 0);
            state->from = NULL;
            state->to = NULL;
            state->at = NULL;
            state->via = NULL;
            state->not_via = NULL;
        } else if (!g_ascii_strcasecmp((char *) tag_name, "event")) {
            count = g_list_length(state->si);
            if (count) {
                children = (void **) g_new0(struct traffic_suppl_info *, count);
                iter = state->si;
                for (i = 0; iter && (i < count); i++) {
                    children[i] = iter->data;
                    iter = g_list_next(iter);
                }
            }
            length = traffic_xml_get_attr("length", el->names, el->values);
            speed = traffic_xml_get_attr("speed", el->names, el->values);
            event = traffic_event_new(event_class_new(traffic_xml_get_attr("class", el->names, el->values)),
                                      event_type_new(traffic_xml_get_attr("type", el->names, el->values)),
                                      length ? atoi(length) : -1,
                                      speed ? atoi(speed) : INT_MAX,
                                      /* TODO quantifier */
                                      NULL,
                                      count,
                                      (struct traffic_suppl_info **) children);
            g_free(children);
            g_list_free(state->si);
            state->si = NULL;
            /* TODO preserve unknown (and thus invalid) events if they have maxspeed set */
            if (!traffic_event_is_valid(event)) {
                dbg(lvl_debug, "invalid or unknown event detected, skipping");
                traffic_event_destroy(event);
            } else
                state->events = g_list_append(state->events, event);
        } else if (!g_ascii_strcasecmp((char *) tag_name, "from")) {
            point = &state->from;
        } else if (!g_ascii_strcasecmp((char *) tag_name, "to")) {
            point = &state->to;
        } else if (!g_ascii_strcasecmp((char *) tag_name, "at")) {
            point = &state->at;
        } else if (!g_ascii_strcasecmp((char *) tag_name, "via")) {
            point = &state->via;
        } else if (!g_ascii_strcasecmp((char *) tag_name, "not_via")) {
            point = &state->not_via;
        }

        /*
         * No handling necessary for:
         *
         * navit_messages: No attributes, everything handled in children's callbacks
         * feed: No attributes, everything handled in children's callbacks
         * events: No attributes, everything handled in children's callbacks
         * merge: No attributes, everything handled in children's callbacks
         * replaces: Leaf node, handled in start callback
         * supplementary_info: Leaf node, handled in start callback
         */

        if (point) {
            /* we have a location point (from, at, to, via or not_via) to process */
            if (sscanf(el->text, "%f %f", &lat, &lon) == 2) {
                *point = traffic_point_new(lon, lat,
                                           traffic_xml_get_attr("junction_name", el->names, el->values),
                                           traffic_xml_get_attr("junction_ref", el->names, el->values),
                                           traffic_xml_get_attr("tmc_id", el->names, el->values));
            } else {
                dbg(lvl_error, "%s has no valid lat/lon pair, skipping", tag_name);
            }
        }
    }

    if (el && !g_ascii_strcasecmp(tag_name, el->tag_name)) {
        traffic_xml_element_destroy(el);
        state->tagstack = g_list_remove(state->tagstack, state->tagstack->data);
    }
    state->is_opened = 0;
}

/**
 * @brief Callback function which gets called when character data is encountered.
 *
 * @param text The character data (note that the data is not NULL-terminated!)
 * @param len The number of characters in `text`
 * @param data Points to a `struct xml_state` holding parser state
 */
static void traffic_xml_text(xml_context *dummy, const char *text, gsize len, void *data, GError **error) {
    struct xml_state * state = (struct xml_state *) data;
    char * text_sz = g_strndup(text, len);
    struct xml_element * el = state->tagstack ? (struct xml_element *) state->tagstack->data : NULL;

    dbg(lvl_debug, " TEXT: '%s'", text_sz);
    if (state->is_valid && state->is_opened) {
        /* this will work only for leaf nodes, which is not an issue at the moment as the only nodes
         * with actual text data are leaf nodes */
        el->text = g_strndup(text, len);
    }
    g_free(text_sz);
}

enum event_class event_class_new(char * string) {
    if (string) {
        if (!g_ascii_strcasecmp(string, "CONGESTION"))
            return event_class_congestion;
        if (!g_ascii_strcasecmp(string, "DELAY"))
            return event_class_delay;
        if (!g_ascii_strcasecmp(string, "RESTRICTION"))
            return event_class_restriction;
    }
    return event_class_invalid;
}

const char * event_class_to_string(enum event_class this_) {
    switch (this_) {
    case event_class_congestion:
        return "CONGESTION";
    case event_class_delay:
        return "DELAY";
    case event_class_restriction:
        return "RESTRICTION";
    default:
        return "INVALID";
    }
}

enum event_type event_type_new(char * string) {
    if (string) {
        if (!g_ascii_strcasecmp(string, "CONGESTION_CLEARED"))
            return event_congestion_cleared;
        if (!g_ascii_strcasecmp(string, "CONGESTION_FORECAST_WITHDRAWN"))
            return event_congestion_forecast_withdrawn;
        if (!g_ascii_strcasecmp(string, "CONGESTION_HEAVY_TRAFFIC"))
            return event_congestion_heavy_traffic;
        if (!g_ascii_strcasecmp(string, "CONGESTION_LONG_QUEUE"))
            return event_congestion_long_queue;
        if (!g_ascii_strcasecmp(string, "CONGESTION_NONE"))
            return event_congestion_none;
        if (!g_ascii_strcasecmp(string, "CONGESTION_NORMAL_TRAFFIC"))
            return event_congestion_normal_traffic;
        if (!g_ascii_strcasecmp(string, "CONGESTION_QUEUE"))
            return event_congestion_queue;
        if (!g_ascii_strcasecmp(string, "CONGESTION_QUEKE_LIKELY"))
            return event_congestion_queue_likely;
        if (!g_ascii_strcasecmp(string, "CONGESTION_SLOW_TRAFFIC"))
            return event_congestion_slow_traffic;
        if (!g_ascii_strcasecmp(string, "CONGESTION_STATIONARY_TRAFFIC"))
            return event_congestion_stationary_traffic;
        if (!g_ascii_strcasecmp(string, "CONGESTION_STATIONARY_TRAFFIC_LIKELY"))
            return event_congestion_stationary_traffic_likely;
        if (!g_ascii_strcasecmp(string, "CONGESTION_TRAFFIC_BUILDING_UP"))
            return event_congestion_traffic_building_up;
        if (!g_ascii_strcasecmp(string, "CONGESTION_TRAFFIC_CONGESTION"))
            return event_congestion_traffic_congestion;
        if (!g_ascii_strcasecmp(string, "CONGESTION_TRAFFIC_EASING"))
            return event_congestion_traffic_easing;
        if (!g_ascii_strcasecmp(string, "CONGESTION_TRAFFIC_FLOWING_FREELY"))
            return event_congestion_traffic_flowing_freely;
        if (!g_ascii_strcasecmp(string, "CONGESTION_TRAFFIC_HEAVIER_THAN_NORMAL"))
            return event_congestion_traffic_heavier_than_normal;
        if (!g_ascii_strcasecmp(string, "CONGESTION_TRAFFIC_LIGHTER_THAN_NORMAL"))
            return event_congestion_traffic_lighter_than_normal;
        if (!g_ascii_strcasecmp(string, "CONGESTION_TRAFFIC_MUCH_HEAVIER_THAN_NORMAL"))
            return event_congestion_traffic_much_heavier_than_normal;
        if (!g_ascii_strcasecmp(string, "CONGESTION_TRAFFIC_PROBLEM"))
            return event_congestion_traffic_problem;
        if (!g_ascii_strcasecmp(string, "DELAY_CLEARANCE"))
            return event_delay_clearance;
        if (!g_ascii_strcasecmp(string, "DELAY_DELAY"))
            return event_delay_delay;
        if (!g_ascii_strcasecmp(string, "DELAY_DELAY_POSSIBLE"))
            return event_delay_delay_possible;
        if (!g_ascii_strcasecmp(string, "DELAY_FORECAST_WITHDRAWN"))
            return event_delay_forecast_withdrawn;
        if (!g_ascii_strcasecmp(string, "DELAY_LONG_DELAY"))
            return event_delay_long_delay;
        if (!g_ascii_strcasecmp(string, "DELAY_SEVERAL_HOURS"))
            return event_delay_several_hours;
        if (!g_ascii_strcasecmp(string, "DELAY_UNCERTAIN_DURATION"))
            return event_delay_uncertain_duration;
        if (!g_ascii_strcasecmp(string, "DELAY_VERY_LONG_DELAY"))
            return event_delay_very_long_delay;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_ACCESS_RESTRICTIONS_LIFTED"))
            return event_restriction_access_restrictions_lifted;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_ALL_CARRIAGEWAYS_CLEARED"))
            return event_restriction_all_carriageways_cleared;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_ALL_CARRIAGEWAYS_REOPENED"))
            return event_restriction_all_carriageways_reopened;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_BATCH_SERVICE"))
            return event_restriction_batch_service;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_BLOCKED"))
            return event_restriction_blocked;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_BLOCKED_AHEAD"))
            return event_restriction_blocked_ahead;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_CARRIAGEWAY_BLOCKED"))
            return event_restriction_carriageway_blocked;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_CARRIAGEWAY_CLOSED"))
            return event_restriction_carriageway_closed;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_CONTRAFLOW"))
            return event_restriction_contraflow;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_CLOSED"))
            return event_restriction_closed;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_CLOSED_AHEAD"))
            return event_restriction_closed_ahead;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_ENTRY_BLOCKED"))
            return event_restriction_entry_blocked;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_ENTRY_REOPENED"))
            return event_restriction_entry_reopened;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_INTERMITTENT_CLOSURES"))
            return event_restriction_intermittent_closures;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_LANE_BLOCKED"))
            return event_restriction_lane_blocked;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_LANE_CLOSED"))
            return event_restriction_lane_closed;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_OPEN"))
            return event_restriction_open;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_RAMP_BLOCKED"))
            return event_restriction_ramp_blocked;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_RAMP_CLOSED"))
            return event_restriction_ramp_closed;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_RAMP_REOPENED"))
            return event_restriction_ramp_reopened;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_REDUCED_LANES"))
            return event_restriction_reduced_lanes;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_REOPENED"))
            return event_restriction_reopened;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_ROAD_CLEARED"))
            return event_restriction_road_cleared;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_SINGLE_ALTERNATE_LINE_TRAFFIC"))
            return event_restriction_single_alternate_line_traffic;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_SPEED_LIMIT"))
            return event_restriction_speed_limit;
        if (!g_ascii_strcasecmp(string, "RESTRICTION_SPEED_LIMIT_LIFTED"))
            return event_restriction_speed_limit_lifted;
    }
    return event_invalid;
}

const char * event_type_to_string(enum event_type this_) {
    switch (this_) {
    case event_congestion_cleared:
        return "CONGESTION_CLEARED";
    case event_congestion_forecast_withdrawn:
        return "CONGESTION_FORECAST_WITHDRAWN";
    case event_congestion_heavy_traffic:
        return "CONGESTION_HEAVY_TRAFFIC";
    case event_congestion_long_queue:
        return "CONGESTION_LONG_QUEUE";
    case event_congestion_none:
        return "CONGESTION_NONE";
    case event_congestion_normal_traffic:
        return "CONGESTION_NORMAL_TRAFFIC";
    case event_congestion_queue:
        return "CONGESTION_QUEUE";
    case event_congestion_queue_likely:
        return "CONGESTION_QUEUE_LIKELY";
    case event_congestion_slow_traffic:
        return "CONGESTION_SLOW_TRAFFIC";
    case event_congestion_stationary_traffic:
        return "CONGESTION_STATIONARY_TRAFFIC";
    case event_congestion_stationary_traffic_likely:
        return "CONGESTION_STATIONARY_TRAFFIC_LIKELY";
    case event_congestion_traffic_building_up:
        return "CONGESTION_TRAFFIC_BUILDING_UP";
    case event_congestion_traffic_congestion:
        return "CONGESTION_TRAFFIC_CONGESTION";
    case event_congestion_traffic_easing:
        return "CONGESTION_TRAFFIC_EASING";
    case event_congestion_traffic_flowing_freely:
        return "CONGESTION_TRAFFIC_FLOWING_FREELY";
    case event_congestion_traffic_heavier_than_normal:
        return "CONGESTION_TRAFFIC_HEAVIER_THAN_NORMAL";
    case event_congestion_traffic_lighter_than_normal:
        return "CONGESTION_TRAFFIC_LIGHTER_THAN_NORMAL";
    case event_congestion_traffic_much_heavier_than_normal:
        return "CONGESTION_TRAFFIC_MUCH_HEAVIER_THAN_NORMAL";
    case event_congestion_traffic_problem:
        return "CONGESTION_TRAFFIC_PROBLEM";
    case event_delay_clearance:
        return "DELAY_CLEARANCE";
    case event_delay_delay:
        return "DELAY_DELAY";
    case event_delay_delay_possible:
        return "DELAY_DELAY_POSSIBLE";
    case event_delay_forecast_withdrawn:
        return "DELAY_FORECAST_WITHDRAWN";
    case event_delay_long_delay:
        return "DELAY_LONG_DELAY";
    case event_delay_several_hours:
        return "DELAY_SEVERAL_HOURS";
    case event_delay_uncertain_duration:
        return "DELAY_UNCERTAIN_DURATION";
    case event_delay_very_long_delay:
        return "DELAY_VERY_LONG_DELAY";
    case event_restriction_access_restrictions_lifted:
        return "RESTRICTION_ACCESS_RESTRICTIONS_LIFTED";
    case event_restriction_all_carriageways_cleared:
        return "RESTRICTION_ALL_CARRIAGEWAYS_CLEARED";
    case event_restriction_all_carriageways_reopened:
        return "RESTRICTION_ALL_CARRIAGEWAYS_REOPENED";
    case event_restriction_batch_service:
        return "RESTRICTION_BATCH_SERVICE";
    case event_restriction_blocked:
        return "RESTRICTION_BLOCKED";
    case event_restriction_blocked_ahead:
        return "RESTRICTION_BLOCKED_AHEAD";
    case event_restriction_carriageway_blocked:
        return "RESTRICTION_CARRIAGEWAY_BLOCKED";
    case event_restriction_carriageway_closed:
        return "RESTRICTION_CARRIAGEWAY_CLOSED";
    case event_restriction_closed:
        return "RESTRICTION_CLOSED";
    case event_restriction_closed_ahead:
        return "RESTRICTION_CLOSED_AHEAD";
    case event_restriction_contraflow:
        return "RESTRICTION_CONTRAFLOW";
    case event_restriction_entry_blocked:
        return "RESTRICTION_ENTRY_BLOCKED";
    case event_restriction_entry_reopened:
        return "RESTRICTION_ENTRY_REOPENED";
    case event_restriction_exit_blocked:
        return "RESTRICTION_EXIT_BLOCKED";
    case event_restriction_exit_reopened:
        return "RESTRICTION_EXIT_REOPENED";
    case event_restriction_intermittent_closures:
        return "RESTRICTION_INTERMITTENT_CLOSURES";
    case event_restriction_lane_blocked:
        return "RESTRICTION_LANE_BLOCKED";
    case event_restriction_lane_closed:
        return "RESTRICTION_LANE_CLOSED";
    case event_restriction_open:
        return "RESTRICTION_OPEN";
    case event_restriction_ramp_blocked:
        return "RESTRICTION_RAMP_BLOCKED";
    case event_restriction_ramp_closed:
        return "RESTRICTION_RAMP_CLOSED";
    case event_restriction_ramp_reopened:
        return "RESTRICTION_RAMP_REOPENED";
    case event_restriction_reduced_lanes:
        return "RESTRICTION_REDUCED_LANES";
    case event_restriction_reopened:
        return "RESTRICTION_REOPENED";
    case event_restriction_road_cleared:
        return "RESTRICTION_ROAD_CLEARED";
    case event_restriction_single_alternate_line_traffic:
        return "RESTRICTION_SINGLE_ALTERNATE_LINE_TRAFFIC";
    case event_restriction_speed_limit:
        return "RESTRICTION_SPEED_LIMIT";
    case event_restriction_speed_limit_lifted:
        return "RESTRICTION_SPEED_LIMIT_LIFTED";
    default:
        return "INVALID";
    }
}

enum item_type item_type_from_road_type(char * string, int is_urban) {
    enum item_type ret = type_line_unspecified;

    if (string) {
        if (!g_ascii_strcasecmp(string, "MOTORWAY"))
            return is_urban ? type_highway_city : type_highway_land;
        if (!g_ascii_strcasecmp(string, "TRUNK"))
            return type_street_n_lanes;
        if (!g_ascii_strcasecmp(string, "PRIMARY"))
            return is_urban ? type_street_4_city : type_street_4_land;
        if (!g_ascii_strcasecmp(string, "SECONDARY"))
            return is_urban ? type_street_3_city : type_street_3_land;
        if (!g_ascii_strcasecmp(string, "TERTIARY"))
            return is_urban ? type_street_2_city : type_street_2_land;

        ret = item_from_name(string);
    }
    if ((ret < route_item_first) || (ret > route_item_last))
        return type_line_unspecified;
    return ret;
}

enum location_dir location_dir_new(char * string) {
    if (string && !g_ascii_strcasecmp(string, "ONE_DIRECTION"))
        return location_dir_one;
    return location_dir_both;
}

enum location_fuzziness location_fuzziness_new(char * string) {
    if (string) {
        if (!g_ascii_strcasecmp(string, "LOW_RES"))
            return location_fuzziness_low_res;
        if (!g_ascii_strcasecmp(string, "END_UNKNOWN"))
            return location_fuzziness_end_unknown;
        if (!g_ascii_strcasecmp(string, "START_UNKNOWN"))
            return location_fuzziness_start_unknown;
        if (!g_ascii_strcasecmp(string, "EXTENT_UNKNOWN"))
            return location_fuzziness_extent_unknown;
    }
    return location_fuzziness_none;
}

const char * location_fuzziness_to_string(enum location_fuzziness this_) {
    switch (this_) {
    case location_fuzziness_low_res:
        return "LOW_RES";
    case location_fuzziness_end_unknown:
        return "END_UNKNOWN";
    case location_fuzziness_start_unknown:
        return "START_UNKNOWN";
    case location_fuzziness_extent_unknown:
        return "EXTENT_UNKNOWN";
    default:
        return NULL;
    }
}

enum location_ramps location_ramps_new(char * string) {
    if (string) {
        if (!g_ascii_strcasecmp(string, "ALL_RAMPS"))
            return location_ramps_all;
        if (!g_ascii_strcasecmp(string, "ENTRY_RAMP"))
            return location_ramps_entry;
        if (!g_ascii_strcasecmp(string, "EXIT_RAMP"))
            return location_ramps_exit;
    }
    return location_ramps_none;
}

const char * location_ramps_to_string(enum location_ramps this_) {
    switch (this_) {
    case location_ramps_none:
        return "NONE";
    case location_ramps_all:
        return "ALL_RAMPS";
    case location_ramps_entry:
        return "ENTRY_RAMP";
    case location_ramps_exit:
        return "EXIT_RAMP";
    default:
        return NULL;
    }
}

enum si_class si_class_new(char * string) {
    if (string) {
        if (!g_ascii_strcasecmp(string, "PLACE"))
            return si_class_place;
        if (!g_ascii_strcasecmp(string, "TENDENCY"))
            return si_class_tendency;
        if (!g_ascii_strcasecmp(string, "VEHICLE"))
            return si_class_vehicle;
    }
    return si_class_invalid;
}

const char * si_class_to_string(enum si_class this_) {
    switch (this_) {
    case si_class_place:
        return "PLACE";
    case si_class_tendency:
        return "TENDENCY";
    case si_class_vehicle:
        return "VEHICLE";
    default:
        return "INVALID";
    }
}

enum si_type si_type_new(char * string) {
    if (string) {
        if (!g_ascii_strcasecmp(string, "S_PLACE_BRIDGE"))
            return si_place_bridge;
        if (!g_ascii_strcasecmp(string, "S_PLACE_RAMP"))
            return si_place_ramp;
        if (!g_ascii_strcasecmp(string, "S_PLACE_ROADWORKS"))
            return si_place_roadworks;
        if (!g_ascii_strcasecmp(string, "S_PLACE_TUNNEL"))
            return si_place_tunnel;
        if (!g_ascii_strcasecmp(string, "S_TENDENCY_QUEUE_DECREASING"))
            return si_tendency_queue_decreasing;
        if (!g_ascii_strcasecmp(string, "S_TENDENCY_QUEUE_INCREASING"))
            return si_tendency_queue_increasing;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_ALL"))
            return si_vehicle_all;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_BUS"))
            return si_vehicle_bus;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_CAR"))
            return si_vehicle_car;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_CAR_WITH_CARAVAN"))
            return si_vehicle_car_with_caravan;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_CAR_WITH_TRAILER"))
            return si_vehicle_car_with_trailer;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_HAZMAT"))
            return si_vehicle_hazmat;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_HGV"))
            return si_vehicle_hgv;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_MOTOR"))
            return si_vehicle_motor;
        if (!g_ascii_strcasecmp(string, "S_VEHICLE_WITH_TRAILER"))
            return si_vehicle_with_trailer;
    }
    return si_invalid;
}

const char * si_type_to_string(enum si_type this_) {
    switch (this_) {
    case si_place_bridge:
        return "S_PLACE_BRIDGE";
    case si_place_ramp:
        return "S_PLACE_RAMP";
    case si_place_roadworks:
        return "S_PLACE_ROADWORKS";
    case si_place_tunnel:
        return "S_PLACE_TUNNEL";
    case si_tendency_queue_decreasing:
        return "S_TENDENCY_QUEUE_DECREASING";
    case si_tendency_queue_increasing:
        return "S_TENDENCY_QUEUE_INCREASING";
    case si_vehicle_all:
        return "S_VEHICLE_ALL";
    case si_vehicle_bus:
        return "S_VEHICLE_BUS";
    case si_vehicle_car:
        return "S_VEHICLE_CAR";
    case si_vehicle_car_with_caravan:
        return "S_VEHICLE_CAR_WITH_CARAVAN";
    case si_vehicle_car_with_trailer:
        return "S_VEHICLE_CAR_WITH_TRAILER";
    case si_vehicle_hazmat:
        return "S_VEHICLE_HAZMAT";
    case si_vehicle_hgv:
        return "S_VEHICLE_HGV";
    case si_vehicle_motor:
        return "S_VEHICLE_MOTOR";
    case si_vehicle_with_trailer:
        return "S_VEHICLE_WITH_TRAILER";
    default:
        return "INVALID";
    }
}

struct traffic_point * traffic_point_new(float lon, float lat, char * junction_name, char * junction_ref,
        char * tmc_id) {
    struct traffic_point * ret;

    ret = g_new0(struct traffic_point, 1);
    ret->coord.lat = lat;
    ret->coord.lng = lon;
    ret->junction_name = junction_name ? g_strdup(junction_name) : NULL;
    ret->junction_ref = junction_ref ? g_strdup(junction_ref) : NULL;
    ret->tmc_id = tmc_id ? g_strdup(tmc_id) : NULL;
    return ret;
}

struct traffic_point * traffic_point_new_short(float lon, float lat) {
    return traffic_point_new(lon, lat, NULL, NULL, NULL);
}

void traffic_point_destroy(struct traffic_point * this_) {
    if (this_->junction_name)
        g_free(this_->junction_name);
    if (this_->junction_ref)
        g_free(this_->junction_ref);
    if (this_->tmc_id)
        g_free(this_->tmc_id);
    g_free(this_);
}

// TODO split CID/LTN?
struct traffic_location * traffic_location_new(struct traffic_point * at, struct traffic_point * from,
        struct traffic_point * to, struct traffic_point * via, struct traffic_point * not_via,
        char * destination, char * direction, enum location_dir directionality,
        enum location_fuzziness fuzziness, enum location_ramps ramps, enum item_type road_type,
        char * road_name, char * road_ref, char * tmc_table, int tmc_direction) {
    struct traffic_location * ret;

    ret = g_new0(struct traffic_location, 1);
    ret->at = at;
    ret->from = from;
    ret->to = to;
    ret->via = via;
    ret->not_via = not_via;
    ret->destination = destination ? g_strdup(destination) : NULL;
    ret->direction = direction ? g_strdup(direction) : NULL;
    ret->directionality = directionality;
    ret->fuzziness = fuzziness;
    ret->ramps = ramps;
    ret->road_type = road_type;
    ret->road_name = road_name ? g_strdup(road_name) : NULL;
    ret->road_ref = road_ref ? g_strdup(road_ref) : NULL;
    ret->tmc_table = tmc_table ? g_strdup(tmc_table) : NULL;
    ret->tmc_direction = tmc_direction;
    ret->priv = g_new0(struct traffic_location_priv, 1);
    ret->priv->sw = NULL;
    ret->priv->ne = NULL;
    return ret;
}

struct traffic_location * traffic_location_new_short(struct traffic_point * at, struct traffic_point * from,
        struct traffic_point * to, struct traffic_point * via, struct traffic_point * not_via,
        enum location_dir directionality, enum location_fuzziness fuzziness) {
    return traffic_location_new(at, from, to, via, not_via, NULL, NULL, directionality, fuzziness,
                                location_ramps_none, type_line_unspecified, NULL, NULL, NULL, 0);
}

void traffic_location_destroy(struct traffic_location * this_) {
    if (this_->at)
        traffic_point_destroy(this_->at);
    if (this_->from)
        traffic_point_destroy(this_->from);
    if (this_->to)
        traffic_point_destroy(this_->to);
    if (this_->via)
        traffic_point_destroy(this_->via);
    if (this_->not_via)
        traffic_point_destroy(this_->not_via);
    if (this_->destination)
        g_free(this_->destination);
    if (this_->direction)
        g_free(this_->direction);
    if (this_->road_name)
        g_free(this_->road_name);
    if (this_->road_ref)
        g_free(this_->road_ref);
    if (this_->tmc_table)
        g_free(this_->tmc_table);
    if (this_->priv->sw)
        g_free(this_->priv->sw);
    if (this_->priv->ne)
        g_free(this_->priv->ne);
    g_free(this_->priv);
    g_free(this_);
}

struct traffic_suppl_info * traffic_suppl_info_new(enum si_class si_class, enum si_type type,
        struct quantifier * quantifier) {
    struct traffic_suppl_info * ret;
    ret = g_new0(struct traffic_suppl_info, 1);
    ret->si_class = si_class;
    ret->type = type;
    ret->quantifier = quantifier ? g_memdup(quantifier, sizeof(struct quantifier)) : NULL;
    return ret;
}

void traffic_suppl_info_destroy(struct traffic_suppl_info * this_) {
    if (this_->quantifier)
        g_free(this_->quantifier);
    g_free(this_);
}

struct traffic_event * traffic_event_new(enum event_class event_class, enum event_type type,
        int length, int speed, struct quantifier * quantifier, int si_count, struct traffic_suppl_info ** si) {
    struct traffic_event * ret;

    ret = g_new0(struct traffic_event, 1);
    ret->event_class = event_class;
    ret->type = type;
    ret->length = length;
    ret->speed = speed;
    ret->quantifier = quantifier ? g_memdup(quantifier, sizeof(struct quantifier)) : NULL;
    if (si_count && si) {
        ret->si_count = si_count;
        ret->si = g_memdup(si, sizeof(struct traffic_suppl_info *) * si_count);
    } else {
        ret->si_count = 0;
        ret->si = NULL;
    }
    return ret;
}

struct traffic_event * traffic_event_new_short(enum event_class event_class, enum event_type type) {
    return traffic_event_new(event_class, type, -1, INT_MAX, NULL, 0, NULL);
}

void traffic_event_destroy(struct traffic_event * this_) {
    int i;

    if (this_->quantifier)
        g_free(this_->quantifier);
    if (this_->si && this_->si_count) {
        for (i = 0; i < this_->si_count; i++)
            traffic_suppl_info_destroy(this_->si[i]);
        g_free(this_->si);
    }
    g_free(this_);
}

void traffic_event_add_suppl_info(struct traffic_event * this_, struct traffic_suppl_info * si) {
    struct traffic_suppl_info ** si_new;

    if (this_->si_count && this_->si) {
        si_new = g_new0(struct traffic_suppl_info *, this_->si_count + 1);
        memcpy(si_new, this_->si, sizeof(struct traffic_suppl_info *) * this_->si_count);
        si_new[this_->si_count] = si;
        g_free(this_->si);
        this_->si = si_new;
        this_->si_count++;
    } else {
        this_->si = g_new0(struct traffic_suppl_info *, 1);
        this_->si[0] = si;
        this_->si_count = 1;
    }
}

struct traffic_suppl_info * traffic_event_get_suppl_info(struct traffic_event * this_, int index) {
    if (this_->si && (index < this_->si_count))
        return this_->si[index];
    else
        return NULL;
}

struct traffic_message * traffic_message_new(char * id, time_t receive_time, time_t update_time,
        time_t expiration_time, time_t start_time, time_t end_time, int is_cancellation, int is_forecast,
        int replaced_count, char ** replaces, struct traffic_location * location, int event_count,
        struct traffic_event ** events) {
    struct traffic_message * ret;

    ret = g_new0(struct traffic_message, 1);
    ret->id = g_strdup(id);
    ret->receive_time = receive_time;
    ret->update_time = update_time;
    ret->expiration_time = expiration_time;
    ret->start_time = start_time;
    ret->end_time = end_time;
    ret->is_cancellation = is_cancellation;
    ret->is_forecast = is_forecast;
    if (replaced_count && replaces) {
        ret->replaced_count = replaced_count;
        ret->replaces = g_memdup(replaces, sizeof(char *) * replaced_count);
    } else {
        ret->replaced_count = 0;
        ret->replaces = NULL;
    }
    ret->location = location;
    if (event_count && events) {
        ret->event_count = event_count;
        ret->events = g_memdup(events, sizeof(struct traffic_event *) * event_count);
    }
    ret->priv = g_new0(struct traffic_message_priv, 1);
    ret->priv->items = NULL;
    return ret;
}

struct traffic_message * traffic_message_new_short(char * id, time_t receive_time, time_t update_time,
        time_t expiration_time, int is_forecast, struct traffic_location * location,
        int event_count, struct traffic_event ** events) {
    return traffic_message_new(id, receive_time, update_time, expiration_time, 0, 0, 0,
                               is_forecast, 0, NULL, location, event_count, events);
}

struct traffic_message * traffic_message_new_single_event(char * id, time_t receive_time, time_t update_time,
        time_t expiration_time, int is_forecast, struct traffic_location * location,
        enum event_class event_class, enum event_type type) {
    struct traffic_event * event;
    struct traffic_event ** events;

    event = traffic_event_new_short(event_class, type);
    events = g_new0(struct traffic_event *, 1);
    events[0] = event;
    return traffic_message_new_short(id, receive_time, update_time, expiration_time, is_forecast,
                                     location, 1, events);
    g_free(events);
}

struct traffic_message * traffic_message_new_cancellation(char * id, time_t receive_time, time_t update_time,
        time_t expiration_time, struct traffic_location * location) {
    return traffic_message_new(id, receive_time, update_time, expiration_time, 0, 0, 1,
                               0, 0, NULL, location, 0, NULL);
}

void traffic_message_destroy(struct traffic_message * this_) {
    int i;
    struct item ** items;

    g_free(this_->id);
    if (this_->replaces) {
        for (i = 0; i < this_->replaced_count; i++)
            g_free(this_->replaces[i]);
        g_free(this_->replaces);
    }
    if (this_->location)
        traffic_location_destroy(this_->location);
    if (this_->events && this_->event_count) {
        for (i = 0; i < this_->event_count; i++)
            traffic_event_destroy(this_->events[i]);
        g_free(this_->events);
    }
    if (this_->priv->items) {
        for (items = this_->priv->items; *items; items++)
            *items = tm_item_unref(*items);
        g_free(this_->priv->items);
    }
    g_free(this_->priv);
    g_free(this_);
}

void traffic_message_add_event(struct traffic_message * this_, struct traffic_event * event) {
    struct traffic_event ** events_new;

    events_new = g_new0(struct traffic_event *, this_->event_count + 1);
    memcpy(events_new, this_->events, sizeof(struct traffic_event *) * this_->event_count);
    events_new[this_->event_count] = event;
    g_free(this_->events);
    this_->events = events_new;
    this_->event_count++;
}

struct traffic_event * traffic_message_get_event(struct traffic_message * this_, int index) {
    if (this_->events && (index < this_->event_count))
        return this_->events[index];
    else
        return NULL;
}

struct item ** traffic_message_get_items(struct traffic_message * this_) {
    struct item ** ret;
    struct item ** in;
    int i;
    if (!this_->priv->items) {
        ret = g_new0(struct item *, 1);
        return ret;
    }
    in = this_->priv->items;
    for (i = 1; *in; i++)
        in++;
    ret = g_new0(struct item *, i);
    memcpy(ret, this_->priv->items, sizeof(struct item *) * i);
    return ret;
}

/**
 * @brief Registers a new traffic map plugin
 *
 * @param meth Receives the map methods
 * @param attrs The attributes for the map
 * @param cbl
 *
 * @return A pointer to a `map_priv` structure for the map
 */
static struct map_priv * traffic_map_new(struct map_methods *meth, struct attr **attrs, struct callback_list *cbl) {
    struct map_priv *ret;

    ret = g_new0(struct map_priv, 1);
    *meth = traffic_map_meth;

    return ret;
}

void traffic_init(void) {
    dbg(lvl_debug, "enter");
    plugin_register_category_map("traffic", traffic_map_new);
}

struct map * traffic_get_map(struct traffic *this_) {
    struct attr_iter *iter;
    struct attr *attr;
    struct traffic * traffic;
    char * filename;
    struct traffic_message ** messages;
    struct traffic_message ** cur_msg;

    if (!this_->map) {
        /* see if any of the other instances has already created a map */
        attr = g_new0(struct attr, 1);
        iter = navit_attr_iter_new();
        while (navit_get_attr(this_->navit, attr_traffic, attr, iter)) {
            traffic = (struct traffic *) attr->u.navit_object;
            if (traffic->map)
                this_->map = traffic->map;
        }
        navit_attr_iter_destroy(iter);
        g_free(attr);
    }

    if (!this_->map) {
        /* no map yet, create a new one */
        struct attr *attrs[4];
        struct attr a_type,data,a_description;
        a_type.type = attr_type;
        a_type.u.str = "traffic";
        data.type = attr_data;
        data.u.str = "";
        a_description.type = attr_description;
        a_description.u.str = "Traffic";

        attrs[0] = &a_type;
        attrs[1] = &data;
        attrs[2] = &a_description;
        attrs[3] = NULL;

        this_->map = map_new(NULL, attrs);
        navit_object_ref((struct navit_object *) this_->map);

        /* populate map with previously stored messages */
        filename = g_strjoin(NULL, navit_get_user_data_directory(TRUE), "/traffic.xml", NULL);
        messages = traffic_get_messages_from_xml_file(this_, filename);
        g_free(filename);

        if (messages) {
            for (cur_msg = messages; *cur_msg; cur_msg++)
                this_->shared->message_queue = g_list_append(this_->shared->message_queue, *cur_msg);
            g_free(messages);
            if (this_->shared->message_queue) {
                if (!this_->idle_cb)
                    this_->idle_cb = callback_new_2(callback_cast(traffic_process_messages_int),
                                                    this_, PROCESS_MESSAGES_NO_DUMP_STORE);
                if (!this_->idle_ev)
                    this_->idle_ev = event_add_idle(50, this_->idle_cb);
            }
        }
    }

    return this_->map;
}

/**
 * @brief Reads previously stored traffic messages from parsed XML data.
 *
 * @param state The XML parser state after parsing the XML data
 *
 * @return A `NULL`-terminated pointer array. Each element points to one `struct traffic_message`.
 * `NULL` is returned (rather than an empty pointer array) if there are no messages to report.
 */
static struct traffic_message ** traffic_get_messages_from_parsed_xml(struct xml_state * state) {
    struct traffic_message ** ret = NULL;
    int i, count;
    GList * msg_iter;

    count = g_list_length(state->messages);
    if (count)
        ret = g_new0(struct traffic_message *, count + 1);
    msg_iter = state->messages;
    for (i = 0; i < count; i++) {
        ret[i] = (struct traffic_message *) msg_iter->data;
        msg_iter = g_list_next(msg_iter);
    }
    g_list_free(state->messages);
    return ret;
}

struct traffic_message ** traffic_get_messages_from_xml_file(struct traffic * this_, char * filename) {
    struct traffic_message ** ret = NULL;
    struct xml_state state;
    int read_success = 0;

    if (filename) {
        memset(&state, 0, sizeof(struct xml_state));
        read_success = xml_parse_file(filename, &state, traffic_xml_start, traffic_xml_end, traffic_xml_text);
        if (read_success) {
            ret = traffic_get_messages_from_parsed_xml(&state);
        } else {
            dbg(lvl_error,"could not retrieve stored traffic messages");
        }
    } /* if (traffic_filename) */
    return ret;
}

struct traffic_message ** traffic_get_messages_from_xml_string(struct traffic * this_, char * xml) {
    struct traffic_message ** ret = NULL;
    struct xml_state state;
    int read_success = 0;

    if (xml) {
        memset(&state, 0, sizeof(struct xml_state));
        read_success = xml_parse_text(xml, &state, traffic_xml_start, traffic_xml_end, traffic_xml_text);
        if (read_success) {
            ret = traffic_get_messages_from_parsed_xml(&state);
        } else {
            dbg(lvl_error,"no data supplied");
        }
    } /* if (xml) */
    return ret;
}

struct traffic_message ** traffic_get_stored_messages(struct traffic *this_) {
    struct traffic_message ** ret = g_new0(struct traffic_message *, g_list_length(this_->shared->messages) + 1);
    struct traffic_message ** out = ret;
    GList * in = this_->shared->messages;

    while (in) {
        *out = (struct traffic_message *) in->data;
        in = g_list_next(in);
        out++;
    }

    return ret;
}

void traffic_process_messages(struct traffic * this_, struct traffic_message ** messages) {
    struct traffic_message ** cur_msg;

    for (cur_msg = messages; cur_msg && *cur_msg; cur_msg++)
        this_->shared->message_queue = g_list_append(this_->shared->message_queue, *cur_msg);
    if (this_->shared->message_queue) {
        if (this_->idle_ev)
            event_remove_idle(this_->idle_ev);
        if (this_->idle_cb)
            callback_destroy(this_->idle_cb);
        this_->idle_cb = callback_new_2(callback_cast(traffic_process_messages_int), this_, 0);
        this_->idle_ev = event_add_idle(50, this_->idle_cb);
    }
}

void traffic_set_mapset(struct traffic *this_, struct mapset *ms) {
    this_->ms = ms;
}

void traffic_set_route(struct traffic *this_, struct route *rt) {
    this_->rt = rt;
}

struct object_func traffic_func = {
    attr_traffic,
    (object_func_new)traffic_new,
    (object_func_get_attr)navit_object_get_attr,
    (object_func_iter_new)navit_object_attr_iter_new,
    (object_func_iter_destroy)navit_object_attr_iter_destroy,
    (object_func_set_attr)navit_object_set_attr,
    (object_func_add_attr)navit_object_add_attr,
    (object_func_remove_attr)navit_object_remove_attr,
    (object_func_init)NULL,
    (object_func_destroy)navit_object_destroy,
    (object_func_dup)NULL,
    (object_func_ref)navit_object_ref,
    (object_func_unref)navit_object_unref,
};