RadixTree.h Source File (original) (raw)

71template <typename KeyType, typename T> class RadixTree {

72public:

75 using value_type = std::pair<const KeyType, mapped_type>;

77private:

78 using KeyConstIteratorType =

79 decltype(adl_begin(std::declval<const key_type &>()));

81 using KeyValueType =

83 using ContainerType = std::list<value_type>;

86 struct Node {

87 KeyConstIteratorRangeType Key{KeyConstIteratorType{},

88 KeyConstIteratorType{}};

89 std::vector Children;

96 std::optional Value;

99 KeyValueType KeyFront;

100

101 Node() = default;

102 Node(const KeyConstIteratorRangeType &Key)

103 : Key(Key), KeyFront(*Key.begin()) {

105 }

106

107 Node(Node &&) = default;

108 Node &operator=(Node &&) = default;

109

110 Node(const Node &) = delete;

111 Node &operator=(const Node &) = delete;

112

113 const Node *findChild(const KeyConstIteratorRangeType &Key) const {

114 if (Key.empty())

115 return nullptr;

116 for (const Node &Child : Children) {

117 assert(!Child.Key.empty());

118 if (Child.KeyFront == *Key.begin())

119 return &Child;

120 }

121 return nullptr;

122 }

123

124 Node *findChild(const KeyConstIteratorRangeType &Query) {

125 const Node *This = this;

126 return const_cast<Node *>(This->findChild(Query));

127 }

128

130 size_t R = 1;

131 for (const Node &C : Children)

132 R += C.countNodes();

133 return R;

134 }

135

136

137

138

139

140

141

142

143

144

145

146 void split(KeyConstIteratorType SplitPoint) {

149

150 Children.swap(Child.Children);

152

153 Children.emplace_back(std::move(Child));

154 }

155 };

156

157

158

160 ContainerType KeyValuePairs;

161

162

163 Node &findOrCreate(KeyConstIteratorRangeType Key) {

164 Node *Curr = &Root;

165 if (Key.empty())

166 return *Curr;

167

168 for (;;) {

171

172 if (I2 != Curr->Key.end()) {

173

174

175

176 Curr->split(I2);

177

178

179 break;

180 }

181

182 Node *Child = Curr->findChild(Key);

183 if (!Child)

184 break;

185

186

187 Curr = Child;

188 }

189

190 if (Key.empty()) {

191

192 return *Curr;

193 }

194

195

196

197

198 return Curr->Children.emplace_back(Key);

199 }

200

201

202

203

204

205

206

207

208

209

210 template

211 class IteratorImpl

212 : public iterator_facade_base<IteratorImpl,

213 std::forward_iterator_tag, MappedType> {

214 const Node *Curr = nullptr;

215 KeyConstIteratorRangeType Query{KeyConstIteratorType{},

216 KeyConstIteratorType{}};

217

218 void findNextValid() {

219 while (Curr && !Curr->Value.has_value())

220 advance();

221 }

222

223 void advance() {

225 if (Query.empty()) {

226 Curr = nullptr;

227 return;

228 }

229

230 Curr = Curr->findChild(Query);

231 if (!Curr) {

232 Curr = nullptr;

233 return;

234 }

235

237 if (I2 != Curr->Key.end()) {

238 Curr = nullptr;

239 return;

240 }

242 }

243

244 friend class RadixTree;

245 IteratorImpl(const Node *C, const KeyConstIteratorRangeType &Q)

246 : Curr(C), Query(Q) {

247 findNextValid();

248 }

249

250 public:

251 IteratorImpl() = default;

252

253 MappedType &operator*() const { return **Curr->Value; }

254

256 advance();

257 findNextValid();

258 return *this;

259 }

260

262 return Curr == Other.Curr;

263 }

264 };

265

266public:

270

273

274 using iterator = typename ContainerType::iterator;

276

277

278 bool empty() const { return KeyValuePairs.empty(); }

279

280

281 size_t size() const { return KeyValuePairs.size(); }

282

283

284

285

286

287 size_t countNodes() const { return Root.countNodes(); }

288

289

292

293

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310 template <typename... Ts>

312

313

314

315

316 const value_type &NewValue = KeyValuePairs.emplace_front(

317 std::move(Key), T(std::forward(Args)...));

318 Node &Node = findOrCreate(NewValue.first);

319 bool HasValue = Node.Value.has_value();

321 Node.Value = KeyValuePairs.begin();

322 else

323 KeyValuePairs.pop_front();

324 return {*Node.Value, HasValue };

325 }

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

347};