Developer forums (C::B DEVELOPMENT STRICTLY!) > CodeCompletion redesign
Question about the code completion revamping done around 2010...
ollydbg:
@rick22 and all
If I'm right, I found that the searchTree template or basic searchTree has a drawback.
Why it can not remove/delete a string item?
I mean, the tree can only add items, but it can't remove items???
Correct me if I'm wrong.
rickg22:
Deleting nodes involves a more complicated algorithm, as we'd have to take care that a node isn't used anymore, and that means checking all the labels, the items used by that node, etc.
However, we could manage to just remove the item stored in that node. It's just not implemented yet.
ollydbg:
Ok, I see.
Can you take a look at the gcc's std c++ library, it has some Patricia tree class implemented.
like:
Trie-Based Containers
rickg22:
Well, what do you know, that's exactly the same algorithm that I use! My tree is an implementation of a patricia trie, but with some customizations (for example, label reuse and linear-space). And I just finished a modification to make it a word sufix tree. Unfortunately, I haven't managed to get the suffix links to work and construct the tree in linear time. Currently the construction time is N*wordlength, and that's only needed once per file. I still need to finish implementing the file reading and do a few tests to see how much it helps.
EDIT: Here's a dump of the tree constructed with the above paragraph. Each node can be expressed with 4 integers: a parent node, a label id, and the label start and length. The labels are shown separately.
--- Code: ---- "" (0)
+- "!" (51)
+- "'" (199)
| +- "s" (23)
| \- "t" (200)
+- "(for" (110)
+- ")." (145)
+- "*wordlength," (252)
+- "," (6)
+- "-space)." (137)
+- "." (146)
+- "And" (147)
+- "Currently" (239)
+- "I" (47)
+- "My" (52)
+- "N*wordlength," (251)
+- "Unfortunately," (179)
+- "Well," (1)
+- "a" (28)
| +- "bel" (124)
| +- "c" (141)
| | +- "e)." (142)
| | \- "tly" (29)
| +- "ding" (298)
| +- "ged" (207)
| +- "ke" (167)
| +- "lgorithm" (39)
| +- "m" (115)
| | +- "e" (37)
| | \- "ple," (116)
| +- "n" (203)
| | +- "aged" (204)
| | \- "d" (59)
| +- "r-space)." (135)
| +- "t" (70)
| | +- "'s" (9)
| | +- "ely," (186)
| | +- "ions" (71)
| | \- "ricia" (79)
| \- "ven't" (194)
+- "b" (125)
| +- "el" (126)
| \- "ut" (93)
+- "c" (85)
| +- "ation" (165)
| +- "e)." (143)
| +- "h" (314)
| +- "ia" (86)
| +- "onstruction" (227)
| +- "t" (249)
| | +- "ion" (250)
| | \- "ly" (30)
| \- "ustomizations" (99)
+- "d" (158)
| +- "ed" (267)
| +- "i" (299)
| | +- "fication" (159)
| | \- "ng" (300)
| +- "length," (253)
| \- "o" (11)
+- "e" (25)
| +- "!" (50)
| +- ")." (144)
| +- "," (92)
| +- "." (178)
| +- "a" (296)
| | +- "ding" (297)
| | \- "r-space)." (134)
| +- "ded" (155)
| +- "e" (265)
| | +- "." (56)
| | \- "ded" (266)
| +- "l" (188)
| | +- "l," (2)
| | +- "ps." (317)
| | \- "y," (189)
| +- "ment" (287)
| | +- "ation" (65)
| | \- "ing" (288)
| +- "n" (196)
| | +- "'t" (197)
| | +- "gth," (255)
| | \- "t" (243)
| | +- "ation" (66)
| | +- "ing" (291)
| | \- "ly" (244)
| +- "r" (271)
| +- "sts" (305)
| +- "t" (212)
| +- "use" (129)
| +- "w" (302)
| \- "xa" (111)
| +- "ctly" (26)
| \- "mple," (112)
+- "f" (149)
| +- "ew" (301)
| +- "fix" (217)
| +- "i" (161)
| | +- "cation" (162)
| | +- "le." (272)
| | +- "nished" (150)
| | \- "x" (176)
| \- "ortunately," (76)
+- "g" (208)
| +- "e" (210)
| | +- "d" (209)
| | \- "t" (211)
| +- "orithm" (41)
| \- "th," (257)
+- "h" (35)
| +- "," (259)
| +- "a" (192)
| | +- "t's" (8)
| | \- "ven't" (193)
| +- "e" (315)
| | +- "d" (36)
| | \- "lps." (316)
| +- "m" (46)
| \- "ow" (310)
+- "i" (57)
| +- "a" (87)
| +- "c" (163)
| | +- "ation" (164)
| | \- "ia" (84)
| +- "e," (91)
| +- "fication" (160)
| +- "l" (277)
| | +- "e." (273)
| | \- "l" (278)
| +- "m" (235)
| | +- "e." (236)
| | \- "plement" (279)
| | +- "ation" (60)
| | \- "ing" (280)
| +- "n" (151)
| | +- "ear-space)." (132)
| | +- "g" (294)
| | +- "ished" (152)
| | \- "ks" (220)
| +- "ons" (73)
| +- "shed" (58)
| +- "thm" (44)
| +- "x" (177)
| \- "zations" (107)
+- "just" (148)
+- "k" (168)
| +- "e" (169)
| +- "now," (15)
| \- "s" (222)
+- "l" (4)
| +- "," (5)
| +- "abel" (123)
| +- "e" (121)
| | +- "," (122)
| | +- "." (274)
| | +- "ment" (285)
| | | +- "ation" (64)
| | | \- "ing" (286)
| | \- "ngth," (254)
| +- "gorithm" (40)
| +- "in" (218)
| | +- "ear-space)." (131)
| | \- "ks" (219)
| +- "l," (3)
| +- "ps." (318)
| \- "y," (32)
+- "m" (61)
| +- "a" (201)
| | +- "ke" (166)
| | \- "naged" (202)
| +- "e" (237)
| | +- "." (238)
| | \- "nt" (289)
| | +- "ation" (38)
| | \- "ing" (290)
| +- "izations" (106)
| +- "odification" (156)
| +- "ple" (117)
| | +- "," (118)
| | \- "ment" (281)
| | +- "ation" (62)
| | \- "ing" (282)
| \- "uch" (311)
+- "n" (67)
| +- "'t" (198)
| +- "a" (205)
| | +- "ged" (206)
| | \- "tely," (185)
| +- "ce" (269)
| +- "d" (130)
| +- "e" (263)
| | +- "ar-space)." (133)
| | \- "eded" (264)
| +- "fortunately," (180)
| +- "gth," (256)
| +- "ished" (153)
| +- "ks" (221)
| +- "ly" (262)
| +- "ow," (16)
| +- "st" (247)
| | +- "omiz" (109)
| | \- "ruction" (248)
| \- "t" (245)
| +- "ation" (68)
| +- "ing" (292)
| \- "ly" (246)
+- "o" (17)
| +- "dification" (157)
| +- "f" (75)
| +- "m" (104)
| | +- "e" (98)
| | \- "izations" (105)
| +- "n" (260)
| | +- "ce" (268)
| | +- "ly" (261)
| | \- "struction" (74)
| +- "r" (171)
| | +- "dlength," (172)
| | +- "ithm" (42)
| | +- "k" (225)
| | \- "tunately," (181)
| +- "u" (12)
| \- "w," (18)
+- "p" (77)
| +- "a" (139)
| | +- "ce)." (140)
| | \- "tricia" (78)
| +- "er" (270)
| +- "le" (119)
| | +- "," (120)
| | \- "ment" (283)
| | +- "ation" (63)
| | \- "ing" (284)
| \- "s." (319)
+- "r" (54)
| +- "-space)." (136)
| +- "dlength," (173)
| +- "e" (127)
| | +- "ading" (295)
| | +- "e." (55)
| | +- "ntly" (242)
| | \- "use" (128)
| +- "i" (82)
| | +- "cia" (83)
| | +- "e," (90)
| | \- "thm" (43)
| +- "k" (226)
| +- "rently" (241)
| +- "tunately," (182)
| \- "uction" (231)
+- "s" (48)
| +- "." (320)
| +- "ame" (24)
| +- "e" (308)
| | +- "!" (49)
| | \- "e" (309)
| +- "hed" (154)
| +- "ome" (97)
| +- "pace)." (138)
| +- "t" (228)
| | +- "ill" (275)
| | +- "omizations" (102)
| | +- "ruction" (229)
| | \- "s" (306)
| \- "uf" (213)
| +- "fix" (214)
| \- "ix" (174)
+- "t" (21)
| +- "'s" (22)
| +- "ation" (69)
| +- "e" (303)
| | +- "ly," (187)
| | \- "sts" (304)
| +- "h" (33)
| | +- "," (258)
| | +- "at's" (10)
| | +- "e" (34)
| | \- "m" (45)
| +- "i" (233)
| | +- "ll" (276)
| | +- "me." (234)
| | +- "ng" (293)
| | \- "ons" (72)
| +- "ly" (31)
| +- "omizations" (103)
| +- "r" (80)
| | +- "ee." (53)
| | +- "i" (88)
| | | +- "cia" (81)
| | | \- "e," (89)
| | \- "uction" (230)
| +- "s" (307)
| \- "unately," (183)
+- "u" (94)
| +- "c" (312)
| | +- "h" (313)
| | \- "tion" (232)
| +- "f" (215)
| | +- "fix" (216)
| | \- "ix" (175)
| +- "nately," (184)
| +- "rrently" (240)
| +- "s" (100)
| | +- "e!" (14)
| | \- "tomizations" (101)
| \- "t" (95)
+- "ven't" (195)
+- "w" (19)
| +- "," (20)
| +- "hat" (7)
| +- "ith" (96)
| \- "or" (223)
| +- "dlength," (170)
| \- "k" (224)
+- "xa" (113)
| +- "ctly" (27)
| \- "mple," (114)
+- "y" (190)
| +- "," (191)
| \- "ou" (13)
\- "zations" (108)
<labels>
<label id="0" data="Well," />
<label id="1" data="whathat'samentation" />
<label id="2" data="dou" />
<label id="3" data="youse!" />
<label id="4" data="know," />
<label id="5" data="xactly," />
<label id="6" data="ed" />
<label id="7" data="lgorithm" />
<label id="8" data="I" />
<label id="9" data="My" />
<label id="10" data="ree." />
<label id="11" data="shed" />
<label id="12" data="nd" />
<label id="13" data="mplementationstruction" />
<label id="14" data="fortunately," />
<label id="15" data="atricia" />
<label id="16" data="e," />
<label id="17" data="but" />
<label id="18" data="ith" />
<label id="19" data="ome" />
<label id="20" data="ustomizationstruct" />
<label id="21" data="(for" />
<label id="22" data="mple," />
<label id="23" data="abel" />
<label id="24" data="use" />
<label id="25" data="inear-space)." />
<label id="26" data="And" />
<label id="27" data="just" />
<label id="28" data="inisheded" />
<label id="29" data="odification" />
<label id="30" data="ake" />
<label id="31" data="ordlength," />
<label id="32" data="ufix" />
<label id="33" data="Unfortunately," />
<label id="34" data="ven't" />
<label id="35" data="naged" />
<label id="36" data="t" />
<label id="37" data="fix" />
<label id="38" data="ks" />
<label id="39" data="k" />
<label id="40" data="onstruction" />
<label id="41" data="me." />
<label id="42" data="Currently" />
<label id="43" data="N*wordlength," />
<label id="44" data="ly" />
<label id="45" data="eded" />
<label id="46" data="ce" />
<label id="47" data="er" />
<label id="48" data="le." />
<label id="49" data="ill" />
<label id="50" data="ing" />
<label id="51" data="ading" />
<label id="52" data="ew" />
<label id="53" data="sts" />
<label id="54" data="e" />
<label id="55" data="ow" />
<label id="56" data="uch" />
<label id="57" data="lps." />
</labels>
--- End code ---
ollydbg:
Ok, I'm looking forward to see the "file in files" feature.
In-fact, I carefully read and debugged the searchtree.cpp code before, so I understand mostly of them :D.
About the wxString or std::string, I think using std::string is enough. Non-anis (code point value > 128) code should only be appeared in comments.
About the lexer, I still think Quex - A Fast Universal Lexical Analyzer Generator is much faster than flex or other hand-made lexer.
Edit: Looking at your plotted tree, I guess that you lex has some problems, looks like:
--- Code: --- +- "e" (25)
| +- "!" (50)
| +- ")." (144)
--- End code ---
We don't need the "e)."
Also:
--- Code: --- +- "d" (158)
| +- "ed" (267)
| +- "i" (299)
| | +- "fication" (159)
| | \- "ng" (300)
| +- "length," (253)
| \- "o" (11)
--- End code ---
We don't have a word "ded"? or "dlength,"?
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version