Generating the next available unique name in C#

Question

If you were to have a naming system in your app where the app contains say 100 actions, which creates new objects, like:

Blur
Sharpen
Contrast
Darken
Matte
...

and each time you use one of these, a new instance is created with a unique editable name, like Blur01, Blur02, Blur03, Sharpen01, Matte01, etc. How would you generate the next available unique name, so that it's an O(1) operation or near constant time. Bear in mind that the user can also change the name to custom names, like RemoveFaceDetails, etc.

It's acceptable to have some constraints, like restricting the number of characters to 100, using letters, numbers, underscores, etc...

EDIT: You can also suggest solutions without "filling the gaps" that is without reusing the already used, but deleted names, except the custom ones of course.

Answer 1

I would create a static integer in action class that gets incremented and assigned as part of each new instance of the class. For instance:

class Blur
{
    private static int count = 0;

    private string _name;
    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }

    public Blur()
    {
        _name = "Blur" + count++.ToString();
    }
}

Since count is static, each time you create a new class, it will be incremented and appended to the default name. O(1) time.

EDIT

If you need to fill in the holes when you delete, I would suggest the following. It would automatically queue up numbers when items are renamed, but it would be more costly overall:

class Blur
    {
        private static int count = 0;
        private static Queue<int> deletions = new Queue<int>();

        private string _name;
        public string Name
        {
            get { return _name; }
            set
            {
                _name = value;
                Delete();
            }
        }

        private int assigned;

        public Blur()
        {
            if (deletions.Count > 0)
            {
                assigned = deletions.Dequeue();
            }
            else
            {
                assigned = count++;
            }
            _name = "Blur" + assigned.ToString();
        }

        public void Delete()
        {
            if (assigned >= 0)
            {
                deletions.Enqueue(assigned);
                assigned = -1;
            }
        }
    }

Also, when you delete an object, you'll need to call .Delete() on the object.

CounterClass Dictionary version

class CounterClass
{
   private int count;
   private Queue<int> deletions;

   public CounterClass()
   {
      count = 0;
      deletions = new Queue<int>();
   }

   public string GetNumber()
   {
      if (deletions.Count > 0)
      {
          return deletions.Dequeue().ToString();
      }
      return count++.ToString();
   }

   public void Delete(int num)
   {
      deletions.Enqueue(num);
   }
}

you can create a Dictionary to look up counters for each string. Just make sure you parse out the index and call .Delete(int) whenever you rename or delete a value.

Answer 2

I refer you to Michael A. Jackson's Two Rules of Program Optimization:

1. Don't do it.
2. For experts only: Don't do it yet.

Simple, maintainable code is far more important than optimizing for a speed problem that you think you might have later.

I would start simple: build a candidate name (e.g. "Sharpen01"), then loop through the existing filters to see if that name exists. If it does, increment and try again. This is O(N²), but until you get thousands of filters, that will be good enough.

If, sometime later, the O(N²) does become a problem, then I'd start by building a HashSet of existing names. Then you can check each candidate name against the HashSet, rather than iterating. Rebuild the HashSet each time you need a unique name, then throw it away; you don't need the complexity of maintaining it in the face of changes. This would leave your code easy to maintain, while only being O(N).

O(N) will be good enough. You do not need O(1). The user is not going to click "Sharpen" enough times for there to be any difference.