1 /*
2 * Copyright 2014 Google Inc. All rights reserved.
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
17 #ifndef SEMISTATIC_GRAPH_DEFN_H
18 #define SEMISTATIC_GRAPH_DEFN_H
19
20 #include <fruit/impl/data_structures/semistatic_graph.h>
21
22 namespace fruit {
23 namespace impl {
24
25 inline bool SemistaticGraphInternalNodeId::operator==(const SemistaticGraphInternalNodeId& x) const {
26 return id == x.id;
27 }
28
29 inline bool SemistaticGraphInternalNodeId::operator<(const SemistaticGraphInternalNodeId& x) const {
30 return id < x.id;
31 }
32
33 template <typename NodeId, typename Node>
node_iterator(NodeData * itr)34 inline SemistaticGraph<NodeId, Node>::node_iterator::node_iterator(NodeData* itr) : itr(itr) {}
35
36 template <typename NodeId, typename Node>
getNode()37 inline Node& SemistaticGraph<NodeId, Node>::node_iterator::getNode() {
38 FruitAssert(itr->edges_begin != 1);
39 return itr->node;
40 }
41
42 template <typename NodeId, typename Node>
isTerminal()43 inline bool SemistaticGraph<NodeId, Node>::node_iterator::isTerminal() {
44 FruitAssert(itr->edges_begin != 1);
45 return itr->edges_begin == 0;
46 }
47
48 template <typename NodeId, typename Node>
setTerminal()49 inline void SemistaticGraph<NodeId, Node>::node_iterator::setTerminal() {
50 FruitAssert(itr->edges_begin != 1);
51 itr->edges_begin = 0;
52 }
53
54 template <typename NodeId, typename Node>
55 inline bool SemistaticGraph<NodeId, Node>::node_iterator::operator==(const node_iterator& other) const {
56 return itr == other.itr;
57 }
58
59 template <typename NodeId, typename Node>
const_node_iterator(const NodeData * itr)60 inline SemistaticGraph<NodeId, Node>::const_node_iterator::const_node_iterator(const NodeData* itr) : itr(itr) {}
61
62 template<typename NodeId, typename Node>
const_node_iterator(node_iterator itr)63 inline SemistaticGraph<NodeId, Node>::const_node_iterator::const_node_iterator(node_iterator itr) : itr(itr.itr) {}
64
65 template <typename NodeId, typename Node>
getNode()66 inline const Node& SemistaticGraph<NodeId, Node>::const_node_iterator::getNode() {
67 FruitAssert(itr->edges_begin != 1);
68 return itr->node;
69 }
70
71 template <typename NodeId, typename Node>
isTerminal()72 inline bool SemistaticGraph<NodeId, Node>::const_node_iterator::isTerminal() {
73 FruitAssert(itr->edges_begin != 1);
74 return itr->edges_begin == 0;
75 }
76
77 template <typename NodeId, typename Node>
78 inline bool SemistaticGraph<NodeId, Node>::const_node_iterator::operator==(const const_node_iterator& other) const {
79 return itr == other.itr;
80 }
81
82 template <typename NodeId, typename Node>
83 inline typename SemistaticGraph<NodeId, Node>::edge_iterator
neighborsBegin()84 SemistaticGraph<NodeId, Node>::node_iterator::neighborsBegin() {
85 FruitAssert(itr->edges_begin != 0);
86 FruitAssert(itr->edges_begin != 1);
87 return edge_iterator{reinterpret_cast<InternalNodeId*>(itr->edges_begin)};
88 }
89
90 template <typename NodeId, typename Node>
edge_iterator(InternalNodeId * itr)91 inline SemistaticGraph<NodeId, Node>::edge_iterator::edge_iterator(InternalNodeId* itr) : itr(itr) {}
92
93 template <typename NodeId, typename Node>
94 inline typename SemistaticGraph<NodeId, Node>::node_iterator
getNodeIterator(node_iterator nodes_begin)95 SemistaticGraph<NodeId, Node>::edge_iterator::getNodeIterator(node_iterator nodes_begin) {
96 return node_iterator{nodeAtId(nodes_begin.itr, *itr)};
97 }
98
99 template <typename NodeId, typename Node>
100 inline void SemistaticGraph<NodeId, Node>::edge_iterator::operator++() {
101 ++itr;
102 }
103
104 template <typename NodeId, typename Node>
105 inline typename SemistaticGraph<NodeId, Node>::node_iterator
getNodeIterator(std::size_t i,node_iterator nodes_begin)106 SemistaticGraph<NodeId, Node>::edge_iterator::getNodeIterator(std::size_t i, node_iterator nodes_begin) {
107 itr += i;
108 return getNodeIterator(nodes_begin);
109 }
110
111 template <typename NodeId, typename Node>
begin()112 inline typename SemistaticGraph<NodeId, Node>::node_iterator SemistaticGraph<NodeId, Node>::begin() {
113 return node_iterator{nodes.begin()};
114 }
115
116 template <typename NodeId, typename Node>
end()117 inline typename SemistaticGraph<NodeId, Node>::node_iterator SemistaticGraph<NodeId, Node>::end() {
118 return node_iterator{nodes.end()};
119 }
120
121 template <typename NodeId, typename Node>
end()122 inline typename SemistaticGraph<NodeId, Node>::const_node_iterator SemistaticGraph<NodeId, Node>::end() const {
123 return const_node_iterator{nodes.end()};
124 }
125
126 template <typename NodeId, typename Node>
at(NodeId nodeId)127 inline typename SemistaticGraph<NodeId, Node>::node_iterator SemistaticGraph<NodeId, Node>::at(NodeId nodeId) {
128 InternalNodeId internalNodeId = node_index_map.at(nodeId);
129 return node_iterator{nodeAtId(internalNodeId)};
130 }
131
132 template <typename NodeId, typename Node>
133 inline typename SemistaticGraph<NodeId, Node>::const_node_iterator
find(NodeId nodeId)134 SemistaticGraph<NodeId, Node>::find(NodeId nodeId) const {
135 const InternalNodeId* internalNodeIdPtr = node_index_map.find(nodeId);
136 if (internalNodeIdPtr == nullptr) {
137 return const_node_iterator{nodes.end()};
138 } else {
139 const NodeData* p = nodeAtId(*internalNodeIdPtr);
140 if (p->edges_begin == 1) {
141 return const_node_iterator{nodes.end()};
142 }
143 return const_node_iterator{p};
144 }
145 }
146
147 template <typename NodeId, typename Node>
find(NodeId nodeId)148 inline typename SemistaticGraph<NodeId, Node>::node_iterator SemistaticGraph<NodeId, Node>::find(NodeId nodeId) {
149 const InternalNodeId* internalNodeIdPtr = node_index_map.find(nodeId);
150 if (internalNodeIdPtr == nullptr) {
151 return node_iterator{nodes.end()};
152 } else {
153 NodeData* p = nodeAtId(*internalNodeIdPtr);
154 if (p->edges_begin == 1) {
155 return node_iterator{nodes.end()};
156 }
157 return node_iterator{p};
158 }
159 }
160
161 template <typename NodeId, typename Node>
162 inline typename SemistaticGraph<NodeId, Node>::NodeData*
nodeAtId(InternalNodeId internalNodeId)163 SemistaticGraph<NodeId, Node>::nodeAtId(InternalNodeId internalNodeId) {
164 return nodeAtId(nodes.data(), internalNodeId);
165 }
166
167 template <typename NodeId, typename Node>
168 inline const typename SemistaticGraph<NodeId, Node>::NodeData*
nodeAtId(InternalNodeId internalNodeId)169 SemistaticGraph<NodeId, Node>::nodeAtId(InternalNodeId internalNodeId) const {
170 return nodeAtId(nodes.data(), internalNodeId);
171 }
172
173 template <typename NodeId, typename Node>
174 inline typename SemistaticGraph<NodeId, Node>::NodeData*
nodeAtId(NodeData * nodes_begin,InternalNodeId internalNodeId)175 SemistaticGraph<NodeId, Node>::nodeAtId(NodeData* nodes_begin, InternalNodeId internalNodeId) {
176 FruitAssert(internalNodeId.id % sizeof(NodeData) == 0);
177 NodeData* p = reinterpret_cast<NodeData*>(reinterpret_cast<char*>(nodes_begin) + internalNodeId.id);
178 // The code above is faster (the compiler doesn't have to worry about internalNodeId.id%sizeof(NodeData), that we know
179 // to be 0).
180 FruitAssert(p == nodes_begin + internalNodeId.id / sizeof(NodeData));
181 return p;
182 }
183
184 template <typename NodeId, typename Node>
185 inline const typename SemistaticGraph<NodeId, Node>::NodeData*
nodeAtId(const NodeData * nodes_begin,InternalNodeId internalNodeId)186 SemistaticGraph<NodeId, Node>::nodeAtId(const NodeData* nodes_begin, InternalNodeId internalNodeId) {
187 FruitAssert(internalNodeId.id % sizeof(NodeData) == 0);
188 const NodeData* p = reinterpret_cast<const NodeData*>(reinterpret_cast<const char*>(nodes_begin) + internalNodeId.id);
189 // The code above is faster (the compiler doesn't have to worry about internalNodeId.id%sizeof(NodeData), that we know
190 // to be 0).
191 FruitAssert(p == nodes_begin + internalNodeId.id / sizeof(NodeData));
192 return p;
193 }
194
195 } // namespace impl
196 } // namespace fruit
197
198 #endif // SEMISTATIC_GRAPH_INLINES_H
199