Coverage for src/radix_tree/radix_tree.py: 100%

1# -*- coding: utf-8 -*- 

2 

3# run tests from Pycharms locally 

4#from radix_config import my_logger 

5 

6# run tests from external Testpy as distributed package 

7from radix_tree.radix_config import my_logger 

8 

9class Container(object): 

10 """ 

11 Container populated with data linked to a radic node 

12 """ 

13 

14 def __init__(self, data, tag=None): 

15 self._data = data 

16 self._tag = tag 

17 self._previous = None 

18 self._next = None 

19 

20 def __str__(self): 

21 return ("Container -> data: %s tag: %s" % (self._data, self._tag)) 

22 

23 

24class Node(object): 

25 """ 

26 A radix node 

27 """ 

28 

29 def __init__(self, key, key_size, cont=None): 

30 self._next = {} 

31 self._key = key 

32 self._key_size = key_size 

33 self._data = cont 

34 

35 def __str__(self): 

36 p = hex(id(self)) 

37 if self._data: 

38 return ("Node %s -> key: %s (%s) key_size: %d _next: %s _data %s" % ( 

39 p, self._key[0:self._key_size], self._key[self._key_size + 1:], self._key_size, self._next, self._data)) 

40 else: 

41 return ("Node %s -> key: %s (%s) key_size: %d _next: %s" % ( 

42 p, self._key[0:self._key_size], self._key[self._key_size + 1:], self._key_size, self._next)) 

43 

44class RadixTree(object): 

45 """ 

46 A radix tree 

47 """ 

48 

49 # max_key_len = 0 

50 

51 def __init__(self): 

52 self._tree = None 

53 

54 def insert_node(self, key, val, start_node=None): 

55 """ 

56 Insert a node in radix tree with a string key 

57 :param key: string or int key 

58 :param val: data linked to the node 

59 :return: new node created 

60 """ 

61 my_logger.debug(" RadixTree.insert_node() ".center(60, '-')) 

62 my_logger.debug(" key: %s " % key) 

63 

64 if type(key) != str: 

65 key = bin(key).replace('0b', '') 

66 my_logger.debug("Key converted in string key: %s " % key) 

67 

68 if start_node == None: 

69 current = self._tree 

70 else: 

71 current = start_node 

72 

73 my_logger.info("Current node: %s " % current) 

74 

75 if not current: 

76 """ the radix tree is empty """ 

77 my_logger.debug("Radix tree empty") 

78 cont = Container(data=val, tag=0) 

79 node = Node(key, len(key), cont) 

80 self._tree = node 

81 my_logger.debug(node) 

82 return cont 

83 

84 tested = 0 

85 while tested < current._key_size: 

86 if tested > len(key) - 1: 

87 # Example 

88 # key to insert AB 

89 # tested = 2 

90 # ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

91 # ┃ current ┃->┃ next node ┃ 

92 # ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

93 # ┃ len=4 ┃ ┃ len=5 ┃ 

94 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

95 # Result : 

96 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

97 # ┃ current ┃->┃ node1 ┃->┃ next node ┃ 

98 # ┃ key=AB ┃ ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

99 # ┃ len=2 ┃ ┃ len=4 ┃ ┃ len=5 ┃ 

100 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

101 

102 cont = Container(data=val, tag=0) 

103 node1 = Node(current._key, current._key_size, None) 

104 node1._next = current._next.copy() 

105 node1._data = current._data 

106 

107 current._key_size = len(key) 

108 current._next[current._key[tested]] = node1 

109 current._key = key 

110 current._data = cont 

111 

112 my_logger.debug(current) 

113 my_logger.debug(node1) 

114 

115 return cont 

116 

117 elif current._key[tested] != key[tested]: 

118 """ 

119 Creation of two new nodes and one container for data 

120 """ 

121 # Example 

122 # key to insert AC 

123 # tested = 1 

124 # ┏━━━━━━━━━━━━┓ ┏━━━━━━━━━━━━┓ 

125 # ┃ current ┃->┃ next node ┃ 

126 # ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

127 # ┃ len=4 ┃ ┃ len=5 ┃ 

128 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

129 # Result : 

130 # ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ ┏━━━━━━━━━━━━┓ 

131 # ┃ current ┃->┃ node1 ┃->┃ next node ┃ 

132 # ┃ key=A ┃ ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

133 # ┃ len=1 ┃ ┃ len=4 ┃ ┃ len=5 ┃ 

134 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

135 # │ C ┏━━━━━━━━━━━━┓ 

136 # +-------->┃ node2 ┃ 

137 # ┃ key=AC ┃ 

138 # ┃ len=2 ┃ 

139 # ┗━━━━━━━━━━━━┛ 

140 cont = Container(data=val, tag=0) 

141 node1 = Node(current._key, current._key_size, None) 

142 node1._next = current._next.copy() 

143 node1._data = current._data 

144 node2 = Node(key, len(key), cont) 

145 

146 current._key_size = tested 

147 # for k in current._next: 

148 # del current._next[k] 

149 current._next = {} 

150 current._next[current._key[tested]] = node1 

151 current._next[key[tested]] = node2 

152 current._key = key[0:tested] 

153 current._data = None 

154 

155 my_logger.debug(current) 

156 my_logger.debug(node1) 

157 my_logger.debug(node2) 

158 

159 return cont 

160 tested += 1 

161 

162 if tested == current._key_size: 

163 if tested < len(key): 

164 """Go to the next node""" 

165 if key[tested] in current._next: 

166 current = current._next[key[tested]] 

167 my_logger.debug("Go to the next node: %s" % current) 

168 self.insert_node(key, val, current) 

169 else: 

170 """Create the new node""" 

171 # Example 

172 # key to insert ABABA 

173 # tested = 4 

174 # ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

175 # ┃ current ┃->┃ ┃ 

176 # ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

177 # ┃ len=4 ┃ ┃ len=5 ┃ 

178 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

179 # Result : 

180 # ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

181 # ┃ current ┃->┃ ┃ 

182 # ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

183 # ┃ len=4 ┃ ┃ len=5 ┃ 

184 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

185 # │ A ┏━━━━━━━━━━━━┓ 

186 # +-------->┃ node ┃ 

187 # ┃ key=ABABA ┃ 

188 # ┃ len=5 ┃ 

189 # ┗━━━━━━━━━━━━┛ 

190 

191 cont = Container(data=val, tag=0) 

192 node = Node(key, len(key), cont) 

193 current._next[key[tested]] = node 

194 my_logger.debug("Create the next node: %s" % node) 

195 my_logger.debug("Modify the current node: %s" % current) 

196 return cont 

197 else: 

198 """The leaf already exists, we have to update container""" 

199 my_logger.debug("The leaf already exists, we have to update container node: %s" % current) 

200 current._key = key 

201 current._key_size = len(key) 

202 cont = current._data 

203 if cont: 

204 """Update container""" 

205 cont._data = val 

206 my_logger.debug("Node already exist. Update container: %s" % current) 

207 else: 

208 """Create container""" 

209 my_logger.debug("Node already exist. Create container: %s" % current) 

210 cont = Container(data=val, tag=0) 

211 current._data = cont 

212 return cont 

213 

214 def get_node(self, key, start_node=None): 

215 """ 

216 Get node in the radix tree beginning to <start_node> indexed by <key> 

217 :param start_node: first node of the radix tree to explore 

218 :param key: key to search 

219 :return: data linked to the node, if any. None otherwise 

220 """ 

221 

222 my_logger.debug(" RadixTree.get_node() ".center(60, '-')) 

223 

224 if type(key) != str: 

225 key = bin(key).replace('0b', '') 

226 my_logger.debug("Key converted in string key: %s " % key) 

227 

228 my_logger.debug("key: %s" % key) 

229 

230 if start_node == None: 

231 node = self._tree 

232 else: 

233 node = start_node 

234 

235 if node: 

236 my_logger.info("Current node: %s" % node) 

237 if node._key == key and node._key_size == len(node._key): 

238 my_logger.info("Node found -> key: %s key_size: %d data: %s" % (node._key, node._key_size, node._data)) 

239 return node._data 

240 else: 

241 tested = 0 

242 while tested < node._key_size: 

243 if tested > len(key) - 1: 

244 my_logger.warning("Node not found -> key: %s" % key) 

245 return None 

246 else: 

247 my_logger.debug("Searching node... current node: %s " % node) 

248 my_logger.debug( 

249 "Searching node... index: %d tested: %s - %s" % (tested, node._key[tested], key[tested])) 

250 if node._key[tested] != key[tested]: 

251 my_logger.warning("Node not found -> key: %s" % key) 

252 return None 

253 else: 

254 tested += 1 

255 

256 if tested == node._key_size: 

257 if key[tested] in node._next: 

258 node = node._next[key[tested]] 

259 my_logger.info("2 Go to the next node -> next: %s node: %s" % (node._key[tested], node)) 

260 return self.get_node(key, node) 

261 else: 

262 my_logger.warning("Node not found -> key: %s" % key) 

263 return None 

264 else: 

265 my_logger.info("Radix tree empty") 

266 return None 

267 

268 def delete_node(self, key, start_node=None, prev_node=None): 

269 """ 

270 Delete node in radix tree 

271 :param key: key of the node to delete 

272 :param start_node: first node of the radix tree or None to start from the beginning of radix tree 

273 :param prev_node: previous node 

274 :return: True if deleted. False otherwise. 

275 """ 

276 

277 my_logger.debug(" RadixTree.delete_node() ".center(60, '-')) 

278 

279 if type(key) != str: 

280 key = bin(key).replace('0b', '') 

281 my_logger.debug("Key converted in string key: %s " % key) 

282 

283 my_logger.debug(" Key : %s" % key) 

284 

285 if start_node == None: 

286 node = self._tree 

287 else: 

288 node = start_node 

289 

290 my_logger.info("Current node -> %s" % node) 

291 

292 if node: 

293 if node._key == key: 

294 # Node to delete found 

295 my_logger.debug("Node to delete found -> %s" % node) 

296 if len(node._next) == 0: 

297 if prev_node == None: 

298 my_logger.debug("First node of tree deleted -> Radix tree empty") 

299 del self._tree 

300 self._tree = None 

301 return True 

302 else: 

303 # Example 

304 # Delete 'ABA' 

305 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━┓ 

306 # ┃ prev_node ┃->┃ node ┃ 

307 # ┃ key=AB ┃ ┃ key=ABA ┃ 

308 # ┃ len=2 ┃ ┃ len=3 ┃ 

309 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━┛ 

310 # Result : 

311 # ┏━━━━━━━━━━━━┓ 

312 # ┃ prev_node ┃ 

313 # ┃ key=AB ┃ 

314 # ┃ len=2 ┃ 

315 # ┗━━━━━━━━━━━━┛ 

316 

317 my_logger.debug("Node deleted %s " % node) 

318 my_logger.debug("Previous link deleted %s " % prev_node) 

319 del prev_node._next[node._key[prev_node._key_size]] 

320 my_logger.debug("1. Previous node updated %s " % prev_node) 

321 

322 if len(prev_node._next) == 1 and prev_node._data == None: 

323 # Example 

324 # Delete 'ABB' 

325 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━┓ 

326 # ┃ prev_node ┃->┃ node ┃ 

327 # ┃ key=AB ┃ ┃ key=ABA ┃ 

328 # ┃ len=2 ┃ ┃ len=3 ┃ 

329 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━┛ 

330 # │ B ┏━━━━━━━━━━━━┓ 

331 # +-------->┃ other node ┃ 

332 # ┃ key=ABB ┃ 

333 # ┃ len=3 ┃ 

334 # ┗━━━━━━━━━━━━┛ 

335 # Result : 

336 # ┏━━━━━━━━━━━━┓ 

337 # ┃ prev_node ┃ 

338 # ┃ key=ABA ┃ 

339 # ┃ len=3 ┃ 

340 # ┗━━━━━━━━━━━━┛ 

341 for k in prev_node._next: 

342 prev_node._key = prev_node._next[k]._key 

343 prev_node._key_size = prev_node._next[k]._key_size 

344 prev_node._data = prev_node._next[k]._data 

345 prev_node._next = prev_node._next[k]._next 

346 my_logger.debug("2. Previous node updated %s " % prev_node) 

347 

348 del node._data 

349 del node 

350 return True 

351 else: 

352 if len(node._next) == 1: 

353 # Example 

354 # Delete 'ABA' 

355 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

356 # ┃ prev_node ┃->┃ node ┃->┃ next_node ┃ 

357 # ┃ key=AB ┃ ┃ key=ABA ┃ ┃ key=ABAB ┃ 

358 # ┃ len=2 ┃ ┃ len=3 ┃ ┃ len=4 ┃ 

359 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

360 # Result : 

361 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓ 

362 # ┃ prev_node ┃->┃ node ┃ 

363 # ┃ key=AB ┃ ┃ key=ABAB ┃ 

364 # ┃ len=2 ┃ ┃ len=4 ┃ 

365 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

366 for ke in node._next: 

367 next_node = node._next[ke] 

368 my_logger.info("Node to update %s " % node) 

369 node._key = next_node._key 

370 node._key_size = next_node._key_size 

371 node._data = next_node._data 

372 node._next = next_node._next.copy() 

373 my_logger.info("Node updated %s " % node) 

374 my_logger.info("Node deleted %s " % next_node) 

375 del next_node._data 

376 del next_node 

377 return True 

378 else: 

379 # Example 

380 # Delete 'ABA' 

381 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

382 # ┃ prev_node ┃->┃ node ┃->┃ next_node1 ┃ 

383 # ┃ key=AB ┃ ┃ key=ABA ┃ ┃ key=ABAB ┃ 

384 # ┃ len=2 ┃ ┃ len=3 ┃ ┃ len=4 ┃ 

385 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

386 # │ C ┏━━━━━━━━━━━━┓ 

387 # +-------->┃ next_nodei ┃ 

388 # ┃ key=ABAC ┃ 

389 # ┃ len=4 ┃ 

390 # ┗━━━━━━━━━━━━┛ 

391 # Result : 

392 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

393 # ┃ prev_node ┃->┃ node ┃->┃ next_node1 ┃ 

394 # ┃ key=AB ┃ ┃ key=ABA ┃ ┃ key=ABAB ┃ 

395 # ┃ len=2 ┃ ┃ len=3 ┃ ┃ len=4 ┃ 

396 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

397 # │ C ┏━━━━━━━━━━━━┓ 

398 # +-------->┃ next_nodei ┃ 

399 # ┃ key=ABAC ┃ 

400 # ┃ len=4 ┃ 

401 # ┗━━━━━━━━━━━━┛ 

402 # In this case, just delete data linked to the node 

403 del node._data 

404 node._data = None 

405 my_logger.info("Just delete data linked to the node %s " % node) 

406 return True 

407 else: 

408 # Other node case 

409 tested = 0 

410 while tested < node._key_size: 

411 if tested > len(key) - 1: 

412 my_logger.warning("Node not found -> key: %s" % key) 

413 return False 

414 else: 

415 my_logger.debug("Searching node... current node: %s " % node) 

416 my_logger.debug( 

417 "Searching node... index: %d tested: %s - %s" % (tested, node._key[tested], key[tested])) 

418 if node._key[tested] != key[tested]: 

419 my_logger.warning("Node not found -> key: %s" % key) 

420 return False 

421 else: 

422 tested += 1 

423 

424 if tested == node._key_size: 

425 if key[tested] in node._next: 

426 prev_node = node 

427 node = node._next[key[tested]] 

428 my_logger.info("Go to the next node -> next: %s node: %s" % (node._key[tested], node)) 

429 ret = self.delete_node(key, node, prev_node) 

430 return ret 

431 else: 

432 my_logger.warning("Node not found -> key: %s" % key) 

433 return False 

434 else: 

435 my_logger.info("Radix tree empty") 

436 return False 

437 

438 def dump(self, node=None, st_next_line=''): 

439 """ 

440 Display a radix node 

441 :param node: first node of the radix tree. If node = None dump the entire radix tree 

442 :param st_next_line: start of next line to display 

443 :return: None 

444 """ 

445 

446 my_logger.debug(" RadixTree.dump() ".center(60, '-')) 

447 

448 if not node: 

449 """Dump the entire radix tree""" 

450 node = self._tree 

451 if not node: 

452 print("Radix tree empty") 

453 return 

454 if node._data: 

455 line = "■" 

456 else: 

457 line = "□" 

458 line += " key: %s key_len: %d next: %d" % (node._key, node._key_size, len(node._next)) 

459 if node._data: 

460 line += " data: %s" % node._data 

461 print(line) 

462 cpt = len(node._next) - 1 

463 st_next_line = "│" * cpt 

464 for item in node._next: 

465 self.dump(node._next[item], st_next_line) 

466 cpt -= 1 

467 st_next_line = st_next_line[0:cpt] 

468 else: 

469 """Intermediate node""" 

470 line = st_next_line 

471 if node._data: 

472 line += "└■" 

473 else: 

474 line += "└□" 

475 line += " key: %s key_len: %d next: %d" % (node._key, node._key_size, len(node._next)) 

476 if node._data: 

477 line += " data: %s" % node._data 

478 print(line) 

479 cpt = len(node._next) - 1 

480 if cpt > 1: 

481 st_next_line = st_next_line + " │" + "│" * (cpt - 1) 

482 if cpt == 1: 

483 my_logger.debug("node with only one son: %s" % node) 

484 st_next_line = st_next_line + " │" 

485 

486 for item in node._next: 

487 self.dump(node._next[item], st_next_line) 

488 l = len(st_next_line) - 1 

489 st_next_line = st_next_line[0:l]