SOLVED:Custom Data Structure

[zeid]

This data structure I've been working on, while not perfect is intended for batch rendering purposes. However at the moment I am having an issue with deleting individual nodes based on their m_id. So I was hoping someone could lend a hand and help me solve this problem. My logic seems inevitably flawed everytime I attempt to delete a node by m_id.

Let me explain the data structure a bit to help make things more understandable; The render system is going to consist of an array of this 'list' type, with each index representing a different layer (background towards forground so that I can use blending effects, etc). This 'list' structure does the following:
When you add a node (a node consists of m_key, which represents the sprite being used for the entity, and a m_id which represents the entities unique id.) it cycles through to see if any entities of that m_key exist. If they do then it is attatched as a 'junction' to that node. If not it is added as a child to the last child node added.
I can currently add nodes for entities without any issues, however I am having trouble traversing this structure in order to delete a specific node that has a specific m_id. You can see my attempt bellow:

Code: Select all

/*
 *  List.h
 *  Core
 *
 *  Created by Samuel Zeid on 24/01/10.
 *  Copyright 2010 Sam Zeid. All rights reserved.
 *
 */
#define NULL 0
#ifndef _LIST_H
#define _LIST_H

struct Node
{
	int m_key, m_id;
	Node *m_child, *m_junction;
};

class List
{
public:
	List()
	{
		m_root=NULL;
	}
	
	void addNode(int p_key, int m_id)
	{
		_insert(m_root, p_key, m_id);
	}
	
	void deleteKey(int p_key)
	{
		if(m_root!=NULL)
		{
			if(m_root->m_key==p_key)
			{
				Node *temp=m_root;
				m_root=m_root->m_child;
				_clear(temp->m_junction);
				delete temp;
			}
			else
				_deleteKey(m_root, p_key);
		}
	}

	void deleteNode(int p_id)
	{
		_deleteNode(m_root,p_id);
	}

	void empty()
	{
		_clear(m_root);
	}

	void release()
	{
		_clear(m_root);
		delete this;
	}

private:
	Node *m_root;
	
	void _insert(Node *&n, int p_key, int p_id)
	{
		if(n==NULL)
		{
			n=new Node;
			n->m_key=p_key;
			n->m_id=p_id;
			n->m_child=NULL;
			n->m_junction=NULL;
		}
		else
		{
			if(n->m_key==p_key||n->m_key==0)
			{
				_insert(n->m_junction,p_key,p_id);
				return;
			}
			_insert(n->m_child,p_key,p_id);
		}
	}
	
	void _deleteKey(Node *&n, int p_key)
	{
		if(n->m_child==NULL)
			return;
		if (n->m_child->m_key==p_key)
		{
			Node *temp=n;
			n->m_child=n;
			_clear(temp->m_junction);
			delete temp;
		}
		else
		{
			_deleteKey(n->m_child, p_key);
		}
	}

	void _deleteNode(Node *&n, int p_id)
	{
		if(n==NULL)
			return;

		if(n->m_id==p_id)
		{
			if(n->m_junction!=NULL)
			{
				Node *temp=n->m_junction;
				n->m_id=n->m_junction->m_id;
				n->m_junction=n->m_junction->m_junction;
				delete temp;
				return;
			}
			if(n->m_child!=NULL)
			{
				Node *temp=n;
				n=n->m_child;
				delete temp;
				return;
			}
		}
		_deleteNode(n->m_junction,p_id);
		_deleteNode(n->m_child,p_id);
	}

	void _clear(Node *&n)
	{
		if(n!=NULL)
		{
			_clear(n->m_child);
			_clear(n->m_junction);
			delete n;
		}
	}
};

#endif

The m_id deleting methods on their own:

Code: Select all

	void deleteNode(int p_id)
	{
		_deleteNode(m_root,p_id);
	}

	void _deleteNode(Node *&n, int p_id)
	{
		if(n==NULL)
			return;

		if(n->m_id==p_id)
		{
			if(n->m_junction!=NULL)
			{
				Node *temp=n->m_junction;
				n->m_id=n->m_junction->m_id;
				n->m_junction=n->m_junction->m_junction;
				delete temp;
				return;
			}
			if(n->m_child!=NULL)
			{
				Node *temp=n;
				n=n->m_child;
				delete temp;
				return;
			}
		}
		_deleteNode(n->m_junction,p_id);
		_deleteNode(n->m_child,p_id);
	}

Thanks in advance, I hope that you could understand what I'm attempting to do. Any suggestions for improving this logically as well as solving my issue would be greatly appreciated.

[Arce]

Aighty, I took a look at the code. I began by adding this method (to aid in debugging):

Code: Select all

   void showList() {
		std::cout << "Current List: \n";
		Node *current=m_root;
		Node *junction=current;
		while(current != NULL) {
			std::cout << current->m_key << "(" << current->m_id << ")  " ;
			junction=current->m_junction;
			while(junction!=NULL) {
				std::cout << junction->m_key << "(" << junction->m_id << ")  " ;
				junction=junction->m_junction;
			}
			current=current->m_child;
			std::cout << "\n";
		}
	}

Then making a sample driver (something like this:)

Code: Select all

#include <iostream>
#include <stdlib.h>
#include "list.h"
int main() {
	List list;
	list.addNode(17,1);
	list.addNode(17,2);
	//list.addNode(17,3);
	list.addNode(17,43);
	list.addNode(7,433);
	list.addNode(7,453);
	list.addNode(7,443);
	list.addNode(5,433);
	list.addNode(9,433);
	list.addNode(9,433);
	list.addNode(9,433);
	list.showList();
	list.deleteKey(7);
	list.showList();
	list.deleteKey(9);
	list.showList();
	list.deleteKey(7);
	list.showList();
	list.deleteKey(5);
	list.showList();
	system("pause");
	
	return 0;
}

Which made it apparent that things were fucked. I got an infinite loop of zeros being printed somewhere when I deleted shit, so obviously a node's child pointer was aiming back at itself or something. So, to check that theory, I modified my code to read:

Code: Select all

   void showList() {
		std::cout << "Current List: \n";
		Node *current=m_root;
		Node *junction=current;
		while(current != NULL && current->m_child!=current ) {
			std::cout << current->m_key << "(" << current->m_id << ")  " ;
			junction=current->m_junction;
			while(junction!=NULL && junction->m_junction!=junction ) {
				std::cout << junction->m_key << "(" << junction->m_id << ")  " ;
				junction=junction->m_junction;
			}
			current=current->m_child;
			std::cout << "\n";
		}
	}

Which resulted in a seg fault somewhere, so something fucked with the pointers.

A quick tweak from my driver revealed that the problem only occurred when you try to remove a key from something below the root node (ae, base case involving root was fine).

Eh, it's late, I'm tired, so I guess long(ish) story short, the problem was some (severely) screwed logic in your "deleteKey" method. Change it to this and it should work okay:

Code: Select all

 void _deleteKey(Node *&n, int p_key)
   {
      if(n->m_child==NULL)
         return;
      if (n->m_child->m_key==p_key)
      {	
        Node *temp=n->m_child;
        n->m_child=n->m_child->m_child;
         _clear(temp->m_junction);
         delete temp;
      }
      else
      {
         _deleteKey(n->m_child, p_key);
      }
   }

Any suggestions for improving this logically as well as solving my issue would be greatly appreciated.

Hmm...I admit the code is somewhat elegant, but why so much recursion? It would be a considerable optimization to use iteration (loops), especially in the case of using this data structure for rendering (each frame shitloads of calls). Popping shit off the stack every frame isn't quite as cheap as you'd expect...Or, atleast not cheap enough to make an entire separate function just to handle one case:

Code: Select all

   void deleteKey(int p_key)
   {
      if(m_root!=NULL)
      {
         if(m_root->m_key==p_key)
         {
            Node *temp=m_root;
            m_root=m_root->m_child;
            _clear(temp->m_junction);
            delete temp;
         }
         else
            _deleteKey(m_root, p_key);
      }
   }

I will say that your idea for this structure and the use is pretty cool, though.

Also, I haven't tried or messed with removing nodes by ID yet, so I've got no idea if there's something wrong there. If so, please lemme know if you need help and I can take a look. Hope it helped!

Lemme know if MY logic is fucked somewhere--I didn't quite do all the testing I should have. Good luck!

[avansc]

hey its pretty later here so im not gonna look to much into it now, but will tomorrow.(i love data structures!!)
but making node a class that can have a destructor will make deletion way easier.

also does deletion mean that all the sub nodes gets deleted?
if so it should be cake.

edit: also, why do you have _clear(Node *&n).. the *&n.. especially when you are passing it pointers as it is. you can make that *n and it will be find.

[Arce]

edit: also, why do you have _clear(Node *&n).. the *&n.. especially when you are passing it pointers as it is. you can make that *n and it will be find.

I thought the same thing, and changed it in my build...To find that it was somehow fucked up.

I really didn't have the time to investigate as to why, so if you find out please let me know. It was actually the thing that bothered me most. ;p

[zeid]

Actually deleting by key was working fine for me. The thing I wanted to be able to do was delete by an individual node using the deleteNode function, but there was a logic error there. The issue comes from the need to do a number of things, of which I could conceptualise but couldn't put into code for some reason, the steps are as followed;
*Check the root node...
*If it's m_id = the p_id exchange it with it's junction node and change the junction nodes child to the deleted nodes child.
*Reccur/itterate through all junction nodes of that m_key (as all nodes of the same key are placed as junctions of the first one added), if any have an m_id = to the p_id replace them with their junction node.
*Perform this check for all the succesive child nodes of the root node.

I am taking a different approach to this issue, and have made a flexible LinkedList data structure instead, then will wrap around that as it will be both more efficient and more modular. Your help was greatly appreciated, and I am taking on board some of your suggestions;
*I'm going to try and see if I can swap some reccursion out for itteration, as it is generally faster/better practice like Arce said.
*I've moved the Node type to a seperate class, this plus making it a template will make it incredibly more modular. (I will no doubt use it in other data structures)
*Changed _clear(Node *&n) to _clear(Node *n) as it is unnecassary in that case, I overlooked that somehow.

GAME JAM! so probably will be off the grid for a few days. I might post up the LinkedList in code snippets later it's pretty much done, just needs some comments for convenience.

[avansc]

you know i was looking and thinking about this for a while, and for what you want to do you are doing things a little to complicated.
dont get me wrong its a good practice. but i think this might be a better solution to your problem.

ps: i might not have understood the problem correctly, if so im sorry.

cList.h

Code: Select all

/*
 *  cList.h
 *  zeid
 *
 *  Created by Andre van-Schalkwyk on 1/28/10.
 *  Copyright 2010 Andre van-Schalkwyk. All rights reserved.
 *
 */

#ifndef _cList_h
#define _cList_h

#include <map>
#include <list>

using namespace std;

class cList;

class cList
{
public:
	cList();
	~cList();
	
	void add(int m_key, int m_id);
	void delete_key(int m_key);
	void delete_id_from_key(int m_key, int m_id);
	void delete_id_from_all_keys(int m_id);
	list<int> *get_Key(int m_key);
	
private:
	map<int, list<int>* > *m_list;
};

#endif

cList.cpp

Code: Select all

/*
 *  cList.cpp
 *  zeid
 *
 *  Created by Andre van-Schalkwyk on 1/28/10.
 *  Copyright 2010 Andre van-Schalkwyk. All rights reserved.
 *
 */

#include <stdio.h>
#include <stdlib.h>

#include "cList.h"

	// constructor and destructor

cList::cList()
{
	this->m_list = new map<int, list<int>* >();
}

cList::~cList()
{
}

void cList::add(int m_key, int m_id)
{
	for(map<int, list<int>* >::iterator ii = this->m_list->begin(); ii != this->m_list->end(); ++ii)
	{
		if((*ii).first == m_key)
		{
			(*ii).second->push_back(m_id);
			return;
		}
	}
	this->m_list->insert(map<int, list<int>* >::value_type(m_key, new list<int>()));
	this->get_Key(m_key)->push_back(m_id);
	
}

void cList::delete_key(int m_key)
{
	map<int, list<int>* >::iterator ii = this->m_list->find(m_key);
	this->m_list->erase(ii);
}

void cList::delete_id_from_key(int m_key, int m_id)
{
	if(this->get_Key(m_key) == NULL)
		return;
	this->get_Key(m_key)->remove(m_id);
	
}

list<int> *cList::get_Key(int m_key)
{
	for(map<int, list<int>* >::iterator ii = this->m_list->begin(); ii != this->m_list->end(); ++ii)
	{
		if((*ii).first == m_key)
			return (*ii).second;
	}
	
	return NULL;
}

ps: i know im gonna get shit for doing it all oo like a mofo.

[avansc]

hey, you can also get rig of the m_list var if you really wanna be a wackadoo OO person.

class cList : public map<int, list<int>* >

then just convert all the this->m_list-> to just this->