Progress with SearchTree class

[rickg22]

hi guys, just want to show some of my current progress.

The Tree class can already add items, and serialize its structure into XML format. It can also dump the node structure in a nice graphical way. Look!

Code

    mytree->AddItem(_T("physics"),_T("1 - uno"));
    mytree->AddItem(_T("physiology"),_T("2 - dos"));
    mytree->AddItem(_T("psychic"),_T("3 - tres"));

results in:

Code

- "" (0)
      \- "p" (4)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sychic" (5)

The numbers between parenthesis are the node id's.
Unfortunately, adding another item screws up the tree, so I'm still in the process of debugging. But at least I have something now

I also have to thank Thomas for his valuable advice on using the STL classes like vector and map. They saved a lot of work!

[rickg22]

Good news people! It seems I have fixed all bugs in the tree's adding of nodes.

Code

Adding word: physics
1 items in the tree
- "" (0)
      \- "physics" (1)
---
Adding word: physiology
2 items in the tree
- "" (0)
      \- "physi" (2)
                  +- "cs" (1)
                  \- "ology" (3)
---
Adding word: psychics
3 items in the tree
- "" (0)
      \- "p" (4)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sychics" (5)
---
Adding word: psychotic
4 items in the tree
- "" (0)
      \- "p" (4)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "ics" (5)
                         \- "otic" (7)
---
Adding word: paranormal
5 items in the tree
- "" (0)
      \- "p" (4)
              +- "aranormal" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "ics" (5)
                         \- "otic" (7)
---
Adding word: psychiatrist
6 items in the tree
- "" (0)
      \- "p" (4)
              +- "aranormal" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "i" (9)
                         |       +- "atrist" (10)
                         |       \- "cs" (5)
                         \- "otic" (7)
---
Adding word: psychiatrists
7 items in the tree
- "" (0)
      \- "p" (4)
              +- "aranormal" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "i" (9)
                         |       +- "atrists" (10)
                         |       \- "cs" (5)
                         \- "otic" (7)
---
Adding word: psychic
8 items in the tree
- "" (0)
      \- "p" (4)
              +- "aranormal" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "i" (9)
                         |       +- "atrists" (10)
                         |       \- "cs" (5)
                         \- "otic" (7)
---
Adding word: psychi
9 items in the tree
- "" (0)
      \- "p" (4)
              +- "aranormal" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "i" (9)
                         |       +- "atrists" (10)
                         |       \- "cs" (5)
                         \- "otic" (7)
---
Adding word: ghosts
10 items in the tree
- "" (0)
      +- "ghosts" (11)
      \- "p" (4)
              +- "aranormal" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "i" (9)
                         |       +- "atrists" (10)
                         |       \- "cs" (5)
                         \- "otic" (7)
---
Adding word: paranormals
11 items in the tree
- "" (0)
      +- "ghosts" (11)
      \- "p" (4)
              +- "aranormals" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "i" (9)
                         |       +- "atrists" (10)
                         |       \- "cs" (5)
                         \- "otic" (7)
---

I haven't finished testing the class, but just in case, I'm sending a backup of the tree class to the /downloads directory. Its name is searchtree.zip.

[takeshimiya]

I can guess this class is for the CodeCompletion plugin?

[Urxae]

Good news people! It seems I have fixed all bugs in the tree's adding of nodes.

Bad news, I think I found a bug just from those diagrams .

Look at the cases where a word is added that starts with another word (psychiatrist/psychiatrists, paranormal/paranormals).

Code

Adding word: psychiatrist
6 items in the tree
- "" (0)
      \- "p" (4)
              +- "aranormal" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "i" (9)
                         |       +- "atrist" (10)
                         |       \- "cs" (5)
                         \- "otic" (7)
---
Adding word: psychiatrists
7 items in the tree
- "" (0)
      \- "p" (4)
              +- "aranormal" (8)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sych" (6)
                         +- "i" (9)
                         |       +- "atrists" (10)
                         |       \- "cs" (5)
                         \- "otic" (7)

Since the node numbers don't change I presume this is an accurate representation of the internals of the data structure, so where did the node for "psychiatrist" go? Shouldn't there be an extra ending node there?

[rickg22]

Yes, it's by design. Edges (words) are only split when needed, to. Notice that there is no node with only one child. This is what allows the path compression and saves space in memory

Each node has a list of the items and their corresponding depths. In this case, "psychiatrists" has an item with depth 12 for "psychiatrist", and another with depth 13 for "psychiatrists". When a node is split, the items are recalculated so they belong to the right node (at least in theory, i haven't checked if that one works )

The next step is implementing the part that recalls the items from the tree. Eeach item has a value, so it's an associative array with strings for keys. When I implement that, my tree class will be complete, and i'll begin doing the adaptation to hold the class completion tokens

[Urxae]

Yes, it's by design. Edges (words) are only split when needed, to. Notice that there is no node with only one child. This is what allows the path compression and saves space in memory

Each node has a list of the items and their corresponding depths. In this case, "psychiatrists" has an item with depth 12 for "psychiatrist", and another with depth 13 for "psychiatrists". When a node is split, the items are recalculated so they belong to the right node (at least in theory, i haven't checked if that one works )

Ah ok then, but that wasn't shown in the tree. Maybe you could append something like "[12, 13]" to the tree output for those nodes to show that?
Well it doesn't really matter as it's debug output, but that way you could check if it works at least.

[rickg22]

I'll debug in an easier way: associating the strings with themselves. If a string doesn't match, then something is wrong.

[anonuser]

Neat searching. Have you tested searching?

[rickg22]

Adding a node implies searching for it, so yes, it's definitely tested ;-)
In fact, I realized some of the inserts weren't working right because there was a fault in the search.

[anonuser]

Very neat. This is for the code completion right?

[Game_Ender]

So this is a kind of fast, searchable Abstract Syntax Tree (AST)?  Do you have your parser generate an AST and then build a SearchTree instance in order to the code completion from?

[rickg22]

No, it's not for an abstract syntax tree ( http://en.wikipedia.org/wiki/Abstract_syntax_tree ), it will only hold the token names. Actually, I just wanted to optimize the addition of tokens :lol:

But this tree will hopefully be used in code completion, to search for all the tokens with a certain prefix.

[rickg22]

Here's the results, part deux ;-)

I added some items, and then queried the contents of the tree.

The following " => " sequences are the results of the queries.

Code

'physics' => ' 1 - uno'
'physiology' => ' 2 - dos'
'psychics' => ' 3 - tres'
'psychotic' => ' 4 - cuatro'
'paranormal' => ' 5 - cinco'
'psychiatrist' => ' 6 - seis'
'psychiatrists' => ' 7 - siete'
'psychi' => ' 8 - ocho'
'ghosts' => ' 9 - nueve'
'paranormals' => '10 - diez'
'blah' => ''
Adding item: blah => bleh
'blah' => 'bleh'
'' => 'this is the root node :P' (I did this to test if i 
could add a value to the empty string)
'psychic' => '' (Notice that here even when 'psychic' 
is contained in the tree, it doesn't have a corresponding  item)

Clearing tree...

'' => 'this is the root node :)'
(i assigned this after clearing the tree)
'physics' => ''
'physiology' => ''
'psychics' => ''
'psychotic' => ''
'paranormal' => ''
'psychiatrist' => ''
'psychiatrists' => ''
'psychi' => ''
'ghosts' => ''
'paranormals' => ''
'blah' => ''
1 items in the tree
- "" (0)
---

It seems to work, alright. I'll upload the zip now. I think I'm ready now to start working on the codecompletion improvements

[TDragon]

In case anyone's interested, the name for this type of structure is a "trie" (an odd abbreviation of "retrieval"). I had built one a few days ago for this same purpose, though without serialization functionality. Hmm...maybe I'll templatize it...

If I'm seeming to hijack all the threads in this forum, it's just your imagination.

[rickg22]

Good news everybody! I'm testing Code::Blocks with the NEW Search Tree!

In my dad's machine (I'm on vacations), parsing time (for codeblocks-newbuild) goes down from 4.75 to 1.895 seconds, that's 2.5 times faster!

So far, everything seems stable, but I'm having a little problem. Whether I use the new class or not, enabling "follow global includes" seems to shut down Codeblocks in the middle of the parsing. Has it happened to any of you? (Windows, ANSI)