CODEWITHSUNDEEP
algorithm
user816318
user816318

Reputation: 55

Adding sequential integers make strings unique?

dynamic list means elements of the list can be added deleted or changed.

The question is similar to how duplicate file names are handled in windows. For example:

file
file (1)
file (2)
file (3)

If file (2) is deleted and then another file with name file is added, file (2) will be the generated file name. (don't think that happens in windows though)

Is there an elegant way to do this without searching through the whole list on every insert?

Upvotes: 1

Views: 120

Answers (3)

Jim Mischel
Jim Mischel

Reputation: 134015

Use a min heap to store the items that get deleted. If the heap is empty, then there are no free items. Otherwise, take the first one.

A simple min heap implementation is available at http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=789

To use it:

BinaryHeap<int> MyHeap = new BinaryHeap<int>();

When you remove an item from your list, add the number to the heap:

MyHeap.Insert(number);

To get the next number:

if (MyHeap.Count > 0)
    nextNumber = MyHeap.RemoveRoot();
else
    nextNumber = List.Count;

This guarantees that you'll always get the smallest available number.

Upvotes: 1

s3rius
s3rius

Reputation: 1452

You can use a queue to store the integers which were freed and a counter to keep in mind which was the last one:

Queue s;
int lastUsedInt; //Initialize to 0

void delete( int fileNumber ){
    s.push(fileNumber);
}

int getIntForNewFile(){
    if( s.empty() ){ //If our queue is empty then there are no unused spaces
        return lastUsedInt++; //Return lastUsedInt and increment it by 1
    }
    else{
        int i = s.top(); //Get current top of the queue
        s.pop(); //Delete current top of the queue
        return i; //Return the retrieved number
    }
}

Some Cpp pseudo code here :)

This will "fill" the empty spots in the order they were deleted. So if you have files 1 through 10, then delete 5 and 2: 5 will be filled first, then 2.

If you want them to be filled in order, you can use a sorted container. In C++ that would be a priority_queue.

Upvotes: 1

Nemo
Nemo

Reputation: 71535

I would use a self-balancing binary tree as a set representation (e.g., the C++ standard std::set<int> container).

The set would consist of all "unallocated" numbers up to and including one greater than the largest allocated number.

Initialize the set to contain 0 (or 1, whatever your preference is).

To allocate a new number, grab the smallest element in the set and remove it. Call that number n. If the set is now empty, put n+1 into the set.

To de-allocate a number, add it to the set. Then perform the following cleanup algorithm:

Step 1: If the set has one element, stop.

Step 2: If the largest element in the set minus the second-largest element is greater than 1, stop.

Step 3: Remove the largest element.

Step 4: Goto step 2.

With this data structure and algorithm, any sequence of k allocate/deallocate operations requires O(k log k) time. (Even though the "cleanup" operation is O(k log k) time all by itself, you can only remove an element after you have inserted it, so the total time does not exceed O(k log k).)

Put another way, each allocate/deallocate takes logarithmic amortized time.

Upvotes: 0

Related Questions