OO DIGITAL TREE - Object Oriented

[code34 248]

Object Oriented DIGITAL TREE
Lastest version: 0.4 by Code34

 

Like to Donate ? Donate with paypal
 

---

Github: https://github.com/code34/oo_digitaltree.Altis
Reference: http://forums.bistudio.com/showthread.php?167980-Object-Oriented-SQF-Scripting-and-Compiling
Wikipedia: http://en.wikipedia.org/wiki/Trie

 

 

---

Description
OO DIGITAL TREE is a class (object oriented) digital tree that permits to stock value like string, scalar, object, etc... in a digital tree. This object will permits to stock objects in digital tree, and give linear time access to them. Time access to record depends of the key size.

Features:

 

 

 

• Put, remove, search value
• Retrieve keyset, and entryset

 

 

Licence:
Under Gpl, you can share, modify, distribute this script but don't remove the licence and the name of the original author

 

Warning: The script uses sleep for scheduled environment.

Documentation:

 

/*
Author: code34 nicolas_boiteux@yahoo.fr
Copyright (C) 2013 Nicolas BOITEUX

CLASS OO_TREE OO_NODE

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/

/*
Function: = ["get", key] call OO_TREE;
Retrieve the value associated to a key

Parameters:
key - string

*/

/*
Function: = ["put", [key, value]] call OO_TREE;
Put/update a value associated to a key

Parameters:
key - string
value - any kind of value

*/


/*
Function: = ["remove", key] call OO_TREE;
Remove the value associated to key

Parameters:
key - string


*/

/*
Function: = "entrySet" call OO_TREE;
Return all the value in the digital tree

Parameters:
none
*/

/*
Function: = "keySet" call OO_TREE;
Return all the keys in the digital tree

Parameters:
none
*/

/*
Function: = "size" call OO_TREE;
Return the number of values in the digital tree

Parameters:
none
*/

Readme:

 

/*
Author: code34 nicolas_boiteux@yahoo.fr
Copyright (C) 2013 Nicolas BOITEUX

CLASS OO_DIGITAL TREE

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/

Usage:
put the "oo_tree.sqf", "oo_node.sqf", and the "oop.h" files in your mission directory
put this code into your mission init.sqf
call compilefinal preprocessFileLineNumbers "oo_tree.sqf";
call compilefinal preprocessFileLineNumbers "oo_node.sqf";

See example mission in directory: init.sqf

Licence:
You can share, modify, distribute this script but don't remove the licence and the name of the original author

logs:
0.3 - fix parseChildKeySet
0.2 - Make Arma Not War version
0.1 - OO DIGITAL TREE - first release

---

Examples

Put string value into the digital tree.

_tree = ["new", []] call OO_TREE;
_key = name player;
_value = "my entry value";
["put", [_key, _value]] call _tree;

Retrieve the value into the digital tree

_key = name player;
_value = ["get", _key] call _tree;
hint format ["%1", _value];

Put an object into digital tree

_tree = ["new", []] call OO_TREE;
_key = name player;
_value = player;
["put", [_key, _value]] call _tree;

Retrieve the object into digital tree

_key = name player;
_value = ["get", _key] call _tree;
hint format ["%1", _value];

[code34 248]

hi :)

just release the 0.3 version

logs:

- fix parseChildKeySet

[iceman77 18]

This is all very interesting. Thanks.

[code34 248]

This is all very interesting. Thanks.

thxs friend :)

[dreadedentity 278]

I really don't understand what this does

[cuel 25]

snip misread

Edited November 9, 2014 by cuel

[code34 248]

Hi :)

In fact, i dont bench this object cause it s early version. The digital tree stills loop on some arrays.

Example with:

if you want to looking for the value associated to "TEN" key, the access is like this:

-> ROOT NODE -> loop on array, and leave at firt element, go to T node

-> T NODE -> loop on array, parse TO node, and leave at TE node

-> TE NODE -> loop on array, parse TEA node, parse TED node, leave to TEN node

if you have want to have a direct access to a value associated to a key, you can use OO_HASHMAP instead

http://forums.bistudio.com/showthread.php?181911-Object-Oriented-Hashmap&p=2752350#post2752350

at this time, i don't compare the both method to retrieve a key, with a large amount of datas, resultats are highly link to engine internal functions.

I will try to do bench tonight with thousand of random key, and randomly access :)

Edited November 10, 2014 by code34

[code34 248]

Hi,

here the results with a huge collection of 1000 keys of 64 chars writing:

"Time OO_TREE insert: 40.9241 sec"

"Time OO_HASHMAP insert: 0.322998 sec"

100 keys of 64 chars randomly reading:

"Time OO_TREE read: 1.04688 sec"

"Time OO_HASHMAP read: 0.0219727 sec"

Very slow insertion of tree map are relative to node object instanciation, and accessor methods. A way to optimize will be te create only one object that would be the tree and node with direct access to variable.

Very important note: both objects OO_HASHMAP & OO_TREE use the same interface, they can be replace each others without any code modification

Edited November 10, 2014 by code34

[code34 248]

Hi

 

I just release a new version

0.4 - improve performance with native arma array function

 

https://github.com/code34/oo_digitaltree.Altis

[Mirek 166]

Aaaand what is it good for?

 

[Dedmen 2588]

MyHashMap = createHashMap;
for "_i" from 1 to 10000 do {MyHashMap set [_i, _i];};

`MyHashMap find 125` 0.002ms
`MyHashMap find 9999` 0.0019 ms
Don't have perf on the insert right now. Should be as fast as the finds though.

 

 

 

9 minutes ago, Mirek said:

Aaaand what is it good for?

 

If you know what Tree and Hashmap containers are then you will know what this is useful for. If you don't then this is most likely not useful for you.
They are Array-like containers optimized for a certain use case. Usually way better lookup performance (Finding a specific value).

[Mirek 166]

Tree is a thing that grows outside :-) , no idea what hashmap is, and it surely be too advanced coding for me, so ill probably never use it, but iam highly curious George, and any knowledge that can help me create a better mission might come in handy. So what it does in plain language?

 

[Dedmen 2588]

11 minutes ago, Mirek said:

Tree is a thing that grows outside :-) , no idea what hashmap is, and it surely be too advanced coding for me, so ill probably never use it, but iam highly curious George, and any knowledge that can help me create a better mission might come in handy. So what it does in plain language?

 

Look at the picture in the first post.
An array would be a straight line of points and each point would have some data.
As you can see in the picture a tree looks like a tree. One root and then multiple branches from that. And branches from each other branch.
Let's say you want to find the entry with the string "ten"
If you have an array of 1000 elements and "ten" is at the end you would have to go from start to end through each of the elements in the normal array till you find your "ten" which takes a long time.
With a tree you first go to the branch named "t" then go to the "e" then go to the "n" and there you are. You found your value. That makes finding values ALOT faster.

Hope that's easy enough?
 

[Mirek 166]

Thank you. that is clear as day.

[Nichols 243]

2 hours ago, dedmen said:

Look at the picture in the first post.
An array would be a straight line of points and each point would have some data.
As you can see in the picture a tree looks like a tree. One root and then multiple branches from that. And branches from each other branch.
Let's say you want to find the entry with the string "ten"
If you have an array of 1000 elements and "ten" is at the end you would have to go from start to end through each of the elements in the normal array till you find your "ten" which takes a long time.
With a tree you first go to the branch named "t" then go to the "e" then go to the "n" and there you are. You found your value. That makes finding values ALOT faster.

Hope that's easy enough?
 

 

@dedmen Seriously thanks for the simplified description. It helped me quite a bit as well. Its amazing what can happen when someone takes a moment to actually say what it means instead of just speaking coder language and getting mad at the people who don't understand.

[Muzzleflash 111]

Why do you sleep in the implementation? If I am running this in a scheduled environment I do not need it, and if I am running it in a unscheduled environment I most certainly do not want it.

[code34 248]

6 hours ago, Muzzleflash said:

Why do you sleep in the implementation? If I am running this in a scheduled environment I do not need it, and if I am running it in a unscheduled environment I most certainly do not want it.

 

you can delete them if you dont need it :) i always use sleep in unscheduled environnement to redistribute to other thread compute time.

[Muzzleflash 111]

17 minutes ago, code34 said:

 

you can delete them if you dont need it :) i always use sleep in unscheduled environnement to redistribute to other thread compute time.

I guess you mean in the scheduled environment :)   I just let the scheduler handle the scheduling of threads, but it is fine if you want to sleep to let other scheduled scripts run. But maybe it would be prudent to add a warning that it should be run in a scheduled environment only. If you try to sleep in a unscheduled environment you will get an error and the script will be terminated.

[code34 248]

yes you are right it s for scheduled environment :) i add this warning.

 

[code34 248]

11 hours ago, dedmen said:

MyHashMap = createHashMap;
for "_i" from 1 to 10000 do {MyHashMap set [_i, _i];};

`MyHashMap find 125` 0.002ms
`MyHashMap find 9999` 0.0019 ms
Don't have perf on the insert right now. Should be as fast as the finds though.

 

 

In 2014, we did bench with very large random key of 64 char and 1000 entries. That s why it took so much times for tree and so less time for hashmap :)

[Dedmen 2588]

Did you ever benchmark your tree against 2 arrays? [[keys],[values]] ?
_value = values select (key find keys);

SQF is terribly slow by itself. The more you move into engine the faster it usually goes.
You optimal SQF implementation might thus be alot slower than a less than optimal implementation using just engine functions.

[code34 248]

Not really as it uses object nodes instead of native array, so this design is definitively slow.

 

I could rewrite it to use only one object instead n * leaf objects, but i think i will do in the case of an other project :D

 

At first version, my other oo hashmap used 2 arrays, but since setvariable/getvariable functions are avalaible, i replaced them.