CODEWITHSUNDEEP
c#data-structuresrecursion
noloman
noloman

Reputation: 11975

C#: recursive search in two different data structures

I need to perform a search in two different data structures in C#, and here's the deal: I have one name (which is a string) and I want to perform a search. I have a function called Exists which will return a bool indicating whether it exists or not.

In case it exists, I increase the name (simply adding a 1 at the end of the string), and then I need to perform the search again (via method exists) to see if an object with the new name exists.

This would go on until there's an unused name, which I could use, BUT, in case it doesn't exist, now I should perform a search another data structure which contains the objects that were deleted, and if the string is found there, then I'd have to increase the name again, and start searching since the beginning. This would all end in case there's no object with such name neither using Exists method nor in the data structure where all the deleted objects are.

How could I approach this problem?

I hope I expressed myself clearly :-)

Thanks a lot in advance!

Upvotes: 0

Views: 200

Answers (6)

AryanVadera
AryanVadera

Reputation: 1

To address this issue, run a series of checks and updates until you locate a unique name that does not appear in either the main collection or the deleted items collection. Here's an organised way to accomplish this in C#:

  1. Use the Exists method to determine whether the name exists in the main collection.
  2. If it exists, change the name by adding a '1' and check again.
  3. If the updated name still remains, continue the procedure until you locate a name that does not appear in the main collection.
  4. When you come across a name that does not appear in the main collection, see whether it is in the deleted items collection.
  5. If it still persists in the deleted items collection, change the name and restart the verification process.
  6. Continue until you locate a name that does not appear in both collections.

example:

public string GetUniqueName(string baseName) { string currentName = baseName;

    while (true)
    {
        // Check if the current name exists in the main collection
        if (_exists(currentName))
        {
            // Modify the name by appending '1'
            currentName = IncrementName(currentName);
        }
        else
        {
            // Check if the current name exists in the deleted objects collection
            if (_deletedObjects.Contains(currentName))
            {
                // Modify the name by appending '1'
                currentName = IncrementName(currentName);
            }
            else
            {
                // Name is unique in both collections
                return currentName;
            }
        }
    }
}

private string IncrementName(string name)
{
    return name + "1";
}

Upvotes: -1

Serge Wautier
Serge Wautier

Reputation: 21888

string BuildNextName(string originalName)
{
  string name = originalName;
  while( Exists(name) || deletedNames.Contains(name))
  {
    name = Increment(name);
  }

  return name;
}

Or did I miss something?

Using a for loop:

string BuildNextName(string originalName)
{
  for (string name=originalName; 
       Exists(name) || deletedNames.Contains(name);
       name = Increment(name));

  return name;
}

BTW, I guess your name incrementation algorithm is more complex than simply adding 1: name, name1, name2,... Basically, if the name doesn't end in a number, you append "1". If it does, you increment that number. right?

Upvotes: 3

Renatas M.
Renatas M.

Reputation: 11820

if you create Exists methods for both data structures, you can search with recursion like this: pseudo code:

string resultName;
void Search(string name)
{
  if(ExistsInFirstStructure(name)) //name is in first data structure
    Search(name + "1"); //add 1 and try again
  else
    if(ExistsInSecondStructure(name)) //name exists in second data structure
      Search(name + "1"); //perform search again
    else
      resultName = name; //current name wasn't found in first and second data structures - we have result
}

Upvotes: 0

Oliver
Oliver

Reputation: 45109

How about this one:

var listOfExistingNames = new List<string> { "MyName", "MyName1", "MyName3" };
var listOfDeletedNames = new List<string> { "MyName2", "MyName5" };

int counter = 0;
string baseToFindFreePlace = "MyName";
string newName = baseToFindFreePlace;

var allNames = listOfExistingNames.Concat(listOfDeletedNames);

while (allNames.Contains(newName))
{
    counter++;
    newName = baseToFindFreePlace + counter;
}

listOfExistingNames.Add(newName);

Upvotes: 0

Haris Hasan
Haris Hasan

Reputation: 30097

a non recursive and simple solution could be something like this ( I don't see any need of recursion in this case)

   //pseudocode

    String name;
    bool condition = true;

    while(condition)
    {
        if(ExistInFirstDataStructure(name))
        {
           //increment name
        }
        else
        {
           if(ExistInDeletedDataStructure(String name))
           {
               //increment name
           }
           else
           {
               condition = false;
           }

        }
    }


    bool ExistInFirstDataStructure(String name)
    {

    }

    bool ExistInDeletedDataStructure(String name)
    {

    }

Upvotes: 0

George Duckett
George Duckett

Reputation: 32438

Why use a loop at all?? (I know LINQ will under the hood)

var LastUsedObjectName =
    MyObjects.Select(mo => mo.Name)
             .Union( MyDeletedObjects.Select(mo => mo.Name))
             .OrderByDescending(name => /*Function to order by integer part of name*/).First();

// Now add 1 to LastUseObjectName and use that.

Upvotes: 0

Related Questions