asked on

C# Recursive Function problem

Hi Experts.

I have an incredible anoing problem that I have been trying to solv for a few days now but I can't get it to work.
This is the problem in brief:

I'm working on a project where I have to manage a category structure that looks something like this.

Every line looks something like:

Order.themes
Order.themes.basic
Order.themes.basic2
Order.themes.basic3
Order.Product
Order.Product.prod1
Shipment
Shipment.where
Shipment.where.east

It can be more or less data separated by a . (dot)

I have written a linked list to hold the structure, BUT my problem is that I don't now how to write the function for this, I have tryed some diffrent approached and faild time by time.
I think that a recursive function is the way to handle this but I can't come up with the function. So that's when I decided to get some serius help from you guys.

My List looks lite this.

public class MNode
      {
            private MNode m_pParent;
            private MNode m_pChild;
            private MNode m_pNext;
            private MNode m_pPrevius;

            public MNode()
            {
                  m_pParent = m_pChild = null;
                  m_pPrevius = m_pNext = this;
            }

            public MNode( MNode node )
            {
                  m_pParent = m_pChild = null;
                  m_pPrevius = m_pNext = this;
                  AttatchTo( node );
            }

            public void AttatchTo( MNode newParent )
            {
                  if( m_pParent != null )
                        Detatch();

                  m_pParent = newParent;
                  if( m_pParent.Child != null )
                  {
                        m_pPrevius = newParent.Child.Previus;
                        m_pNext = newParent.Child;
                        m_pParent.Child.Previus.Next = this;
                        m_pParent.Child.Previus = this;
                  }
                  else
                        m_pParent.Child = this;
            }

            public void Attatch( MNode newChild )
            {
                  if( newChild.HasParent )
                        newChild.Detatch();

                  newChild.Parent = this;

                  if( m_pChild != null )
                  {
                        newChild.Previus = m_pChild.Previus;
                        newChild.Next = m_pChild;
                        m_pChild.Previus.Next = newChild;
                        m_pChild.Previus = newChild;
                  }
                  else
                        m_pChild = newChild;
            }

            public void Detatch()
            {
                  if( m_pParent != null && m_pParent.Child == this )
                  {
                        if( m_pNext != this )
                              m_pParent.Child = m_pNext;
                        else
                              m_pParent.Child = null;
                  }

                  m_pPrevius.Next = m_pNext;
                  m_pNext.Previus = m_pPrevius;

                  m_pPrevius = this;
                  m_pNext = this;
            }

            public int CountNodes()
            {
                  if( m_pChild != null )
                        return m_pChild.CountNodes() + 1;
                  else
                        return 1;
            }

            public virtual string ToHTML( string strBaseUrl )
            {
                  return "";
            }

            #region Access Methods
            public bool HasParent
            {
                  get { return ( m_pParent != null ); }
            }

            public bool HasChild
            {
                  get { return ( m_pChild != null ); }
            }

            public bool IsFirstChild
            {
                  get
                  {
                        if( m_pParent != null )
                              if( m_pParent.Child == this )
                                    return true;

                        return false;
                  }
            }

            public bool IsLastChild
            {
                  get
                  {
                        if( m_pParent != null )
                              if( m_pParent.Child.Previus == this )
                                    return true;

                        return false;
                  }
            }

            public MNode Parent
            {
                  get { return m_pParent; }
                  set { m_pParent = value; }
            }

            public MNode Child
            {
                  get { return m_pChild; }
                  set { m_pChild = value; }
            }

            public MNode Next
            {
                  get { return m_pNext; }
                  set { m_pNext = value; }
            }

            public MNode Previus
            {
                  get { return m_pPrevius; }
                  set { m_pPrevius = value; }
            }

            #endregion

And I have derived it into antother class called MCat.
I woul'd like to have all the lines ordered by name in the list like this

ROOT
|- Order
|--- themes
|--|---basic
|--| Product
|--|--prod1
...

I would gratly appreciate the help that I can get in this matter, the best thing would be a finished function that maps up the nodes and returns the root node beacuse I'm in a deadline here :P

Bob Learned

In an effort to understand this requirement, what benefit do you think that this approach has? What power does this class give you that can't be done in a different way?

In effect, what is the bigger picture here?

Bob
"Big Picture Guy"

Snurre

ASKER

The benefit of making it with the MNode class is that I can make the information searchable and I am going to present it in a TreeView kind a way on the web but with our own custom controlls. That's the main thing that made me to use the MNode class.

BUT if you Bob has a better soloution i'm very mutch interested in this. As long as I can solve this problem I'm pleased and if we shall consider performance, this is'nt the most important thing for this operation.

I hope that this is enough information for ya guys.

Diego Pazos

This code loads the data you want into a structure of nested hashtables. If you tell me what you want to do with it later, maybe I can provide sample code to access it.

using System;
using System.Collections;
using System.IO;

namespace ConsoleApplication1 {
class Program {
static Hashtable Root = new Hashtable();

static void Main(string[] args) {
StreamReader R = new StreamReader(@"C:\datos.txt");

string L;
while ((L = R.ReadLine()) != null) {
ProcessLine(L);
}
Console.Read();
}

static void ProcessLine(string L) {
int N;
string P;
Hashtable H = Root;
bool Last=false;
while (true) {
N = L.IndexOf(".");
if (N == -1) {
P = L;
Last = true;
} else {
P = L.Substring(0, N);
L = L.Substring(N + 1);
}
if (!H.ContainsKey(P)) H[P] = new Hashtable();
if (Last) break;
H = (Hashtable)H[P];
}
}
}
}

Snurre

ASKER

Ok uKER. Tanks for your reply.

I Never thought of the HasTable utility :)

I Load all the data from a Database but that's not a problem, the only question I have concerning this code is, DOES THE ProcessLine function creates it like the tree I described earlier?
If so, then it's excactly what I need. I'm going to test run the posted code tomorrow morning Swedish time and then I will return with questions about it, if any.

Btw, How is the HashTable class in performance? Not that it maters, just courius, have't worked with that until know.

Tanks in advance, uKER

Snurre

ASKER

Ok uKER, I'v tried your function and sure, it does handle the dot separated strings.

But my need is not forfilled, I woul'd need a function that reades X lines with and evaluates everyone of them and checks if the values separated by a . and create a nodelist of them so I get the treeview kind a thingie I described earlier. It's a key thing to get this in a nodelist beacuse of this:

1. Need to have the values separated and child values MUST be aware of it's parent value aKa MNode.
2. By creating this Node list, I get full controll over the values, beacuse I don't have any definitions on how or how many values and child values etc. there will be

Btw, the category structure is like the files and folders structure, the only diffrence is that instead of a '/' it's a '.' separator.

I hope I have made my self clear, otherwise, just ask, beacuse it's IMPORTANT that I solv this during the day or weekend..

ASKER CERTIFIED SOLUTION

RiverPhoenix

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

RiverPhoenix

Procs 2-4 are all helper procedures; I tested this and it takes a multi-line string, delimits it, and adds each line recursively into a TreeView

Snurre

ASKER

Tanks RiverPhoenix.

That's did it for me :) excellet help. I'm really grateful.