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

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

2 

3# run tests from Pycharms locally 

4from radix_config import my_logger 

5# run tests from external Testpy as distributed package 

6#from radix_tree.radix_config import my_logger 

7 

8class Container(object): 

9 """ 

10 Container populated with data linked to a radic node 

11 """ 

12 

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

14 self._data = data 

15 self._tag = tag 

16 self._previous = None 

17 self._next = None 

18 

19 def __str__(self): 

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

21 

22 

23class Node(object): 

24 """ 

25 A radix node 

26 """ 

27 

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

29 self._next = {} 

30 self._key = key 

31 self._key_size = key_size 

32 self._data = cont 

33 

34 def __str__(self): 

35 p = hex(id(self)) 

36 if self._data: 

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

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

39 else: 

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

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

42 

43class RadixTree(object): 

44 """ 

45 A radix tree 

46 """ 

47 

48 # max_key_len = 0 

49 

50 def __init__(self): 

51 self._tree = None 

52 

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

54 """ 

55 Insert a node in radix tree with a string key 

56 :param key: string or int key 

57 :param val: data linked to the node 

58 :return: new node created 

59 """ 

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

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

62 

63 if type(key) != str: 

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

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

66 

67 if start_node == None: 

68 current = self._tree 

69 else: 

70 current = start_node 

71 

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

73 

74 if not current: 

75 """ the radix tree is empty """ 

76 my_logger.debug("Radix tree empty") 

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

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

79 self._tree = node 

80 my_logger.debug(node) 

81 return cont 

82 

83 tested = 0 

84 while tested < current._key_size: 

85 if tested > len(key) - 1: 

86 # Example 

87 # key to insert AB 

88 # tested = 2 

89 # ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

90 # ┃ current ┃->┃ next node ┃ 

91 # ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

92 # ┃ len=4 ┃ ┃ len=5 ┃ 

93 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

94 # Result : 

95 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

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

97 # ┃ key=AB ┃ ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

98 # ┃ len=2 ┃ ┃ len=4 ┃ ┃ len=5 ┃ 

99 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

100 

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

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

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

104 node1._data = current._data 

105 

106 current._key_size = len(key) 

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

108 current._key = key 

109 current._data = cont 

110 

111 my_logger.debug(current) 

112 my_logger.debug(node1) 

113 

114 return cont 

115 

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

117 """ 

118 Creation of two new nodes and one container for data 

119 """ 

120 # Example 

121 # key to insert AC 

122 # tested = 1 

123 # ┏━━━━━━━━━━━━┓ ┏━━━━━━━━━━━━┓ 

124 # ┃ current ┃->┃ next node ┃ 

125 # ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

126 # ┃ len=4 ┃ ┃ len=5 ┃ 

127 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

128 # Result : 

129 # ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ ┏━━━━━━━━━━━━┓ 

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

131 # ┃ key=A ┃ ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

132 # ┃ len=1 ┃ ┃ len=4 ┃ ┃ len=5 ┃ 

133 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

134 # │ C ┏━━━━━━━━━━━━┓ 

135 # +-------->┃ node2 ┃ 

136 # ┃ key=AC ┃ 

137 # ┃ len=2 ┃ 

138 # ┗━━━━━━━━━━━━┛ 

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

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

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

142 node1._data = current._data 

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

144 

145 current._key_size = tested 

146 # for k in current._next: 

147 # del current._next[k] 

148 current._next = {} 

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

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

151 current._key = key[0:tested] 

152 current._data = None 

153 

154 my_logger.debug(current) 

155 my_logger.debug(node1) 

156 my_logger.debug(node2) 

157 

158 return cont 

159 tested += 1 

160 

161 if tested == current._key_size: 

162 if tested < len(key): 

163 """Go to the next node""" 

164 if key[tested] in current._next: 

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

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

167 self.insert_node(key, val, current) 

168 else: 

169 """Create the new node""" 

170 # Example 

171 # key to insert ABABA 

172 # tested = 4 

173 # ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

174 # ┃ current ┃->┃ ┃ 

175 # ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

176 # ┃ len=4 ┃ ┃ len=5 ┃ 

177 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

178 # Result : 

179 # ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

180 # ┃ current ┃->┃ ┃ 

181 # ┃ key=ABAB ┃ ┃ key=ABABB ┃ 

182 # ┃ len=4 ┃ ┃ len=5 ┃ 

183 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

184 # │ A ┏━━━━━━━━━━━━┓ 

185 # +-------->┃ node ┃ 

186 # ┃ key=ABABA ┃ 

187 # ┃ len=5 ┃ 

188 # ┗━━━━━━━━━━━━┛ 

189 

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

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

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

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

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

195 return cont 

196 else: 

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

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

199 current._key = key 

200 current._key_size = len(key) 

201 cont = current._data 

202 if cont: 

203 """Update container""" 

204 cont._data = val 

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

206 else: 

207 """Create container""" 

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

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

210 current._data = cont 

211 return cont 

212 

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

214 """ 

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

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

217 :param key: key to search 

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

219 """ 

220 

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

222 

223 if type(key) != str: 

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

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

226 

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

228 

229 if start_node == None: 

230 node = self._tree 

231 else: 

232 node = start_node 

233 

234 if node: 

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

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

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

238 return node._data 

239 else: 

240 tested = 0 

241 while tested < node._key_size: 

242 if tested > len(key) - 1: 

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

244 return None 

245 else: 

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

247 my_logger.debug( 

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

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

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

251 return None 

252 else: 

253 tested += 1 

254 

255 if tested == node._key_size: 

256 if key[tested] in node._next: 

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

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

259 return self.get_node(key, node) 

260 else: 

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

262 return None 

263 else: 

264 my_logger.info("Radix tree empty") 

265 return None 

266 

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

268 """ 

269 Delete node in radix tree 

270 :param key: key of the node to delete 

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

272 :param prev_node: previous node 

273 :return: True if deleted. False otherwise. 

274 """ 

275 

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

277 

278 if type(key) != str: 

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

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

281 

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

283 

284 if start_node == None: 

285 node = self._tree 

286 else: 

287 node = start_node 

288 

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

290 

291 if node: 

292 if node._key == key: 

293 # Node to delete found 

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

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

296 if prev_node == None: 

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

298 del self._tree 

299 self._tree = None 

300 return True 

301 else: 

302 # Example 

303 # Delete 'ABA' 

304 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━┓ 

305 # ┃ prev_node ┃->┃ node ┃ 

306 # ┃ key=AB ┃ ┃ key=ABA ┃ 

307 # ┃ len=2 ┃ ┃ len=3 ┃ 

308 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━┛ 

309 # Result : 

310 # ┏━━━━━━━━━━━━┓ 

311 # ┃ prev_node ┃ 

312 # ┃ key=AB ┃ 

313 # ┃ len=2 ┃ 

314 # ┗━━━━━━━━━━━━┛ 

315 

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

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

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

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

320 

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

322 # Example 

323 # Delete 'ABB' 

324 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━┓ 

325 # ┃ prev_node ┃->┃ node ┃ 

326 # ┃ key=AB ┃ ┃ key=ABA ┃ 

327 # ┃ len=2 ┃ ┃ len=3 ┃ 

328 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━┛ 

329 # │ B ┏━━━━━━━━━━━━┓ 

330 # +-------->┃ other node ┃ 

331 # ┃ key=ABB ┃ 

332 # ┃ len=3 ┃ 

333 # ┗━━━━━━━━━━━━┛ 

334 # Result : 

335 # ┏━━━━━━━━━━━━┓ 

336 # ┃ prev_node ┃ 

337 # ┃ key=ABA ┃ 

338 # ┃ len=3 ┃ 

339 # ┗━━━━━━━━━━━━┛ 

340 for k in prev_node._next: 

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

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

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

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

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

346 

347 del node._data 

348 del node 

349 return True 

350 else: 

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

352 # Example 

353 # Delete 'ABA' 

354 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

355 # ┃ prev_node ┃->┃ node ┃->┃ next_node ┃ 

356 # ┃ key=AB ┃ ┃ key=ABA ┃ ┃ key=ABAB ┃ 

357 # ┃ len=2 ┃ ┃ len=3 ┃ ┃ len=4 ┃ 

358 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

359 # Result : 

360 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓ 

361 # ┃ prev_node ┃->┃ node ┃ 

362 # ┃ key=AB ┃ ┃ key=ABAB ┃ 

363 # ┃ len=2 ┃ ┃ len=4 ┃ 

364 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

365 for ke in node._next: 

366 next_node = node._next[ke] 

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

368 node._key = next_node._key 

369 node._key_size = next_node._key_size 

370 node._data = next_node._data 

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

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

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

374 del next_node._data 

375 del next_node 

376 return True 

377 else: 

378 # Example 

379 # Delete 'ABA' 

380 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

381 # ┃ prev_node ┃->┃ node ┃->┃ next_node1 ┃ 

382 # ┃ key=AB ┃ ┃ key=ABA ┃ ┃ key=ABAB ┃ 

383 # ┃ len=2 ┃ ┃ len=3 ┃ ┃ len=4 ┃ 

384 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

385 # │ C ┏━━━━━━━━━━━━┓ 

386 # +-------->┃ next_nodei ┃ 

387 # ┃ key=ABAC ┃ 

388 # ┃ len=4 ┃ 

389 # ┗━━━━━━━━━━━━┛ 

390 # Result : 

391 # ┏━━━━━━━━━━━━┓A ┏━━━━━━━━━━━━┓B ┏━━━━━━━━━━━━┓ 

392 # ┃ prev_node ┃->┃ node ┃->┃ next_node1 ┃ 

393 # ┃ key=AB ┃ ┃ key=ABA ┃ ┃ key=ABAB ┃ 

394 # ┃ len=2 ┃ ┃ len=3 ┃ ┃ len=4 ┃ 

395 # ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━┛ 

396 # │ C ┏━━━━━━━━━━━━┓ 

397 # +-------->┃ next_nodei ┃ 

398 # ┃ key=ABAC ┃ 

399 # ┃ len=4 ┃ 

400 # ┗━━━━━━━━━━━━┛ 

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

402 del node._data 

403 node._data = None 

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

405 return True 

406 else: 

407 # Other node case 

408 tested = 0 

409 while tested < node._key_size: 

410 if tested > len(key) - 1: 

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

412 return False 

413 else: 

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

415 my_logger.debug( 

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

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

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

419 return False 

420 else: 

421 tested += 1 

422 

423 if tested == node._key_size: 

424 if key[tested] in node._next: 

425 prev_node = node 

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

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

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

429 return ret 

430 else: 

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

432 return False 

433 else: 

434 my_logger.info("Radix tree empty") 

435 return False 

436 

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

438 """ 

439 Display a radix node 

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

441 :param st_next_line: start of next line to display 

442 :return: None 

443 """ 

444 

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

446 

447 if not node: 

448 """Dump the entire radix tree""" 

449 node = self._tree 

450 if not node: 

451 print("Radix tree empty") 

452 return 

453 if node._data: 

454 line = "■" 

455 else: 

456 line = "□" 

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

458 if node._data: 

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

460 print(line) 

461 cpt = len(node._next) - 1 

462 st_next_line = "│" * cpt 

463 for item in node._next: 

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

465 cpt -= 1 

466 st_next_line = st_next_line[0:cpt] 

467 else: 

468 """Intermediate node""" 

469 line = st_next_line 

470 if node._data: 

471 line += "└■" 

472 else: 

473 line += "└□" 

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

475 if node._data: 

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

477 print(line) 

478 cpt = len(node._next) - 1 

479 if cpt > 1: 

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

481 if cpt == 1: 

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

483 st_next_line = st_next_line + " │" 

484 

485 for item in node._next: 

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

487 l = len(st_next_line) - 1 

488 st_next_line = st_next_line[0:l]