Problems with an Algorithm

Question

I have the following 5 lines of string:

A.B.C.D.E
A.B
A.B.C
A
A.B.C.D

This are hierarchical relationships. The second row for example means that B is a child of A.

Now I want to parse these lines into a Class Structure. So that each letter is represented by an instance of a class and points to its parent (or null if top level (A)). However, every letter should only be addded once.

I started the following:

    String[] hierarchical = Name.Split('.');

        if (hierarchical.Count() > 1)
        {
            Console.WriteLine("Package '" + Name + "' is not top level and has to be parsed");

            Console.WriteLine("Find parent for '" + hierarchical[hierarchical.Count() - 1] + "'");

            findParent(Name);

        }
        else
        {
            Console.WriteLine("Package '" + Name + "' is top level and is added to the manager");
            if (!manager.isAlreadyAdded(Name))
            {
                Package p = new Package(null, hierarchical[0], Name);
                manager.add(p);
            }
        }

    }

This means if it is a top level name (A in the example above) then add it to the manager if it is not already there. The problem lies in the findParent() method where I try to find the parent of a subpackage:

private void findParent(String path)
        {
            String originalPath = path;
            bool found = false;

            while (!found)
            {
                int position = path.LastIndexOf(".");

                if (position == -1)
                {
                    Console.WriteLine("Top level reached: " + path);
                    if (!manager.isAlreadyAdded(path))
                    {
                        Package p = new Package(null, path, path);
                        manager.add(p);
                    }
                    found = true;
                }
                else
                {
                    path = path.Substring(0, position);
                    Console.WriteLine("Path: " + path);

                    if (!manager.isAlreadyAdded(path))
                    {
                        Package p = new Package(null,getName(path), path);
                        manager.add(p);
                    }

                }

            }

        }

        private string getName(string path)
        {
            int position = path.LastIndexOf(".");
            if (position == -1)
            {
                return path;
            }
            else
            {
                return path.Substring(position+1, path.Length - position - 1);
            }
        }

As expected this works not as I wanted, since it adds all packages as top levels. How can I correct this?

Your sample only describes 1 structure with 5 members. Or do you mean a (independent) structure per line? — Henk Holterman
– Henk Holterman, Commented Dec 2, 2010 at 21:05
Sorry I shiuld have clarified that. One line is one structure. — anon
– anon, Commented Dec 2, 2010 at 21:06
So basically your structure is always a tree with one branch only ? Then why don't add elements to the structure from left to right ? — digEmAll
– digEmAll, Commented Dec 2, 2010 at 21:10

SpeksETC · Accepted Answer · 2010-12-02 21:13:05Z

2

Is the first argument of the Package constructor by any chance the parent? If so, you are always passing null there which could be your issue.

Btw, I think you may be able to simplify your algorithm.

Can't something like this work:

String[] hierarchical = Name.Split('.');
foreach (String node in hierarchical){
 if(!manager.Contains(node)){
      manager.AddToEnd(node); //adds node who's parent is the last node added

  }

}

Since each line is guaranteed to be "sorted" you know if you get a package that hasn't been added yet, its parent is the last node already added.

edited Dec 2, 2010 at 21:13

answered Dec 2, 2010 at 21:07

SpeksETC

1,0132 gold badges7 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Grinn · Accepted Answer · 2010-12-02 21:20:44Z

0

I'm a little unclear on what you're trying to do, but this will set parent to the second to last entry (node) in your list:

        string[] nodes = path.Split(".".ToCharArray());
        string parent = nodes[nodes.Length - 2];

answered Dec 2, 2010 at 21:20

Grinn

5,56340 silver badges52 bronze badges

Collectives™ on Stack Overflow

Problems with an Algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related