Question about the code completion revamping done around 2010...

[rickg22]

Hi all, it's been a while. I'm on a personal mission to revamp "find on files" in c::b, and I think of using the SearchTree class ( searchtree.cpp), which I originally wrote for Code Completion. I noticed many changes in that file, most by Morten.  Mind refreshing me on the changes and why were they needed?

Thanks!

[ollydbg]

I don't think there are much changes in the file "searchtree.cpp" since last two years. You can see the change logs.

I have problems to see the changes logs of this file before the merge of codecompletion branch, I'm using TortoiseSVN.

[Jenna]

I have problems to see the changes logs of this file before the merge of codecompletion branch, I'm using TortoiseSVN.

You can see the logs via websvn: http://svn.berlios.de/wsvn/codeblocks/trunk/src/plugins/codecompletion/parser/searchtree.cpp?op=log&peg=7562

[ollydbg]

You can see the logs via websvn: http://svn.berlios.de/wsvn/codeblocks/trunk/src/plugins/codecompletion/parser/searchtree.cpp?op=log&peg=7562

Thanks jens, the websvn works great! It can clear show the log before the merge.
It is much better than TortoiseSVN.

[MortenMacFly]

Mind refreshing me on the changes and why were they needed?

If I look at the diff, I see that actually there were only a few interface adjustments, naming rules (for consistency) and kind of a debug intrface for our CC test application. Basically the functionality should not have changed.

[rickg22]

Well, one of my problems was that kdesvn (I'm on linux) can't show the changes for a specific version of a specific file. I have to use the log, search the file among the 300 changed files in the scrollable list, and THEN do the diff. Yeah, it sucks.

But with websvn, it's great. Thanks, Jens!

BTW, why the explicit change from string to wxString? with the little macros I had added at the top, it should be equivalent.

[MortenMacFly]

BTW, why the explicit change from string to wxString? with the little macros I had added at the top, it should be equivalent.

IIRC this was because of an incompatibility with certain STL ANSI functions that were used in combination with Unicode. I've exchanged the ANSI methods with their (wx) Unicode equivalents and  while I were at is, I also moved the rest to wx(string).

[rickg22]

Yeah, but with the macros, all string references would be replaced to their wx equivalents. Unless I did the inclusions wrong :-/ But never mind.
The point is that I can copy (move?) SearchTree to the SDK where it can be more useful for other searching stuff (find in files, TODO items, etc). Mwahahahahaha.

[MortenMacFly]

Yeah, but with the macros, all string references would be replaced to their wx equivalents.

Yes, but what's the point of doing "macro magic" when we always compile this portion using wxWidgets? It just leads to confusion. Anyways... go ahead. ;-)

[rickg22]

Yeah, but with the macros, all string references would be replaced to their wx equivalents.

Yes, but what's the point of doing "macro magic" when we always compile this portion using wxWidgets?

For portability purposes, i.e. using that class in other projects. Anyway, thanks for the info.

[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&#39;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&#39;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>

[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 .

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)

We don't need the "e)."

Also:

Code

      +- "d" (158)
      |         +- "ed" (267)
      |         +- "i" (299)
      |         |         +- "fication" (159)
      |         |         \- "ng" (300)
      |         +- "length," (253)
      |         \- "o" (11)

We don't have a word "ded"? or "dlength,"?