1/*
2 * Copyright 2017 Uber Technologies, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16/** @file vertexGraph.h
17 * @brief Data structure for storing a graph of vertices
18 */
19
20#ifndef VERTEX_GRAPH_H
21#define VERTEX_GRAPH_H
22
23#include <stdint.h>
24#include <stdlib.h>
25#include "geoCoord.h"
26
27/** @struct VertexNode
28 * @brief A single node in a vertex graph, part of a linked list
29 */
30typedef struct VertexNode VertexNode;
31struct VertexNode {
32 GeoCoord from;
33 GeoCoord to;
34 VertexNode* next;
35};
36
37/** @struct VertexGraph
38 * @brief A data structure to store a graph of vertices
39 */
40typedef struct {
41 VertexNode** buckets;
42 int numBuckets;
43 int size;
44 int res;
45} VertexGraph;
46
47void initVertexGraph(VertexGraph* graph, int numBuckets, int res);
48
49void destroyVertexGraph(VertexGraph* graph);
50
51VertexNode* addVertexNode(VertexGraph* graph, const GeoCoord* fromVtx,
52 const GeoCoord* toVtx);
53
54int removeVertexNode(VertexGraph* graph, VertexNode* node);
55
56VertexNode* findNodeForEdge(const VertexGraph* graph, const GeoCoord* fromVtx,
57 const GeoCoord* toVtx);
58
59VertexNode* findNodeForVertex(const VertexGraph* graph,
60 const GeoCoord* fromVtx);
61
62VertexNode* firstVertexNode(const VertexGraph* graph);
63
64// Internal functions
65uint32_t _hashVertex(const GeoCoord* vertex, int res, int numBuckets);
66void _initVertexNode(VertexNode* node, const GeoCoord* fromVtx,
67 const GeoCoord* toVtx);
68
69#endif
70