Setting up a search node.

ID:1875187
 
Jun 15 2015, 4:13 pm
Problem description:
I was reading a C++ book and I ran across something that is an alternative to looping through lists.
I was wondering what the DM equivalent would be and how to set one up - nodes.

Which is basically an item that then has sub items to the left and right.
The theory is that each level of a node that you do "down" eliminates up to half the items you have to look through.

so A leads to B and C, while B leads do D and E, and C leads to F and G, and so on.

I was curious how this could be applied to other things like atoms. It seems pretty useful. Any ideas?
Jun 15 2015, 5:56 pm (Edited on Jun 15 2015, 6:01 pm)
Hi buddy, how are you?

I personaly don't like to work with C++ so please forgive me if I make any mistakes. A node in c# looks like this (I guess that a node in C++ is similar, at least it does the same thing):
    public class Node { //Setting up the node class

        public object information;
        public Node nextNode;

        public Node(object data) {
            this.information = data;
            this.nextNode = null;
        }
    }
Then you would create a node in c# (smilar to C++)by doing this 
            Node newNode = new Node(1);
            newNode.nextNode = new Node(2);
            newNode.nextNode.nextNode = new Node(3);



I wrote a code in DM that does pretty much the same thing (it is the equivalente to the C++ and C# node system):
//@Misticone00

Node        //This is the node class
    parent_type = /datum
    var/Data    //This is where you store your data
    var/Node/Next   //This is the a possible future subNode

    New(object) //This is the Node builder
        Data = object   //It sets the Node class Data variable to a value
        Next = null //It sets the next Node to null


    proc/Print(N, /var/Node) //This is simply to show you that this Node Class works
        world<<N:Data //Shows the current Node Data value
        if(N:Next <> null)  //If the next node is NOT null then
            Print(N:Next) //Let's call the print function again using the next Node

mob/verb/CreateNode()
    var/Node/myNode = new /Node (1) //Let's give life to our first node
    myNode.Next = new /Node(2)   //The next subnode
    myNode.Next.Next = new /Node(3) // the next subnode
    myNode.Print(myNode) //Now let's display all the nodes values to show you that this works
Use the node Class that I wrote in DreamMaker and you shouldn't have any problems.

Thanks for the challenge :D

Hug,
,MistY
Jun 15 2015, 6:02 pm
 
node
    var data, node/next

    New(Data, Next)
        data = Data
        next = Next

    proc/Print()
        world << data
        if(next) next.Print()

mob/verb/test_nodes()
    var node/my_node = new (1, new (2, new (3)))
    my_node.Print()

ftfy
Jun 15 2015, 7:50 pm
Nodes of what sort of data structure? A linked list? Double-linked list? Ring? Dequeue? Tree? Heap? BYOND can do all of those with datums.

It sounds like you're describing a binary search tree. Making your own trees can be useful. Although, BYOND already uses binary trees for associative lists, so wherever feasible you're better off relying on the internal behavior which is faster.
Jun 17 2015, 4:25 am
This is all insightful but I think the closest answer was the one Lummox Jr gave with associative lists, could you show a small example of that?

I'm more interested in using it for things like finding players in a list or finding certain items in a list.
Jun 17 2015, 5:15 am
Do you mean like Dictionaries ?
        public Dictionary<string, int> Dic = new Dictionary<string, int>(); //Sets the dictionary
        public int TestDIC(){
            Dic.Add("A", 1); //Adds The key A and the correspondent value 1 to the dictionary
            Dic.Add("B", 2); //Adds the key B and the correspondent value 2 to the dictionary

            return Dic["A"]; //This will return 1
        
        
        }



You said that you read something in your C++ book ("I was reading a C++ book and I ran across something that is an alternative to looping through lists"). I guess that the book as an exemple of what it looks like. Could you post it for me please (so I can help you better)? I am much more familiar with C# than C++ but I'll give it a try.
Jun 17 2015, 5:18 am
You might make a player dictionary that associates a player's key to the player's mob:
var key2mob[0]

mob/Login()
    ..()
    key2mob[key] = src

Then, given a key, you can instantly get the mob with that key with key2mob[that_key], instead of looping through and checking the key of every client.

Something like that?