Developer forums (C::B DEVELOPMENT STRICTLY!) > CodeCompletion redesign
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"));
--- End code ---
results in:
--- Code: ---- "" (0)
\- "p" (4)
+- "hysi" (2)
| +- "cs" (1)
| \- "ology" (3)
\- "sychic" (5)
--- End code ---
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)
---
--- End code ---
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:
--- Quote from: rickg22 on December 20, 2005, 08:41:46 am ---Good news people! It seems I have fixed all bugs in the tree's adding of nodes.
--- End quote ---
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).
--- Quote from: rickg22 on December 20, 2005, 08:41:46 am ---
--- 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)
--- End code ---
--- End quote ---
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 :P )
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 :)
Navigation
[0] Message Index
[#] Next page
Go to full version