Get a number between two numbers question

HarryBoy · 02-01-2010, 10:51 AM

I need help with some c.

I have some code that opens a directory and reads in the names of files which are e.g. 0001, 0002, 0003 up to 9999.

I need to get all these numbers and then generate a new number that is not one of these numbers already.

here is my code to check the files in the directory

DIR *d;
struct dirent *dir;
int i = 0;

d = opendir( "//mydir//" );
if( d )
{

printf("Directory stream is now open\n");

while ((dir = readdir(d)) != NULL)
{

int num = atoi(dir->d_name);
printf("Filename=%s number=%d\n", dir->d_name, num);

if( num > 0 && num < 9999)//
{
//I need to add all my numbers to an array or list
// and then get a new number which is between 0 and 9999 //that does not include any of my added numbers
//Preferably the next logical number e.g. if i have 0,1,2,3 then i should get 4 as my next number

}

}

Can someone help me??

thanks

Alien_Hominid · 02-01-2010, 11:38 AM

Create an int array n[10000] and set the value to 1 if the name is used, otherwise 0.

as in your example:

Code:

n[0] = 1;
n[1] = 1;
n[2] = 1;
n[3] = 1;
n[4] = 0;

and loop through searching for 0.

Another better and more difficult solution would be creating a singly linked list of unused names, which you could manage (add/remove members) dynamically.

Code:

struct slist
{
  int value;
  struct slist *bigger;
}

carbonfiber · 02-01-2010, 12:31 PM

HarryBoy: Are the names of the files represented by consecutive numbers? (is it possible to have only the following file names: 0001, 0002, 0004)

Alien_Hominid: why would the 'linked list' solution be better in this particular case?

HarryBoy · 02-01-2010, 12:44 PM

Thanks guys, the names can be any numer e.g. 0001, 0002, 0099, 1234, 4567, 9999.

here is an attempt by me, please could you guys 'code review' it for me if possible?

Code:

const char* getstreamFileNo( void )
{
   char filename[4]; //holds the new file name
   DIR           *d;
   struct dirent *dir;
   int count = 0;
   int filenumbers[10000];
   int newfilenumber = 0;

   d = opendir( "//mydir//" );
   if( d )
   {

	 while ((dir = readdir(d)) != NULL)
	 {
	   int num = atoi(dir->d_name);

	   if( num > 0 && num < 9999)//Add number to
	   {
		filenumbers[count] = num;
		count++;
	   }

	 }

	 int i,j = 0 ;
	 bool bfound = false;
	 for( i=1; i<10000; i++ )//go through all numbers from 1-9999
	 {
	   bfound = false;
	   for( j=0; j<count; j++ )//go through all numbers in our array
	   {
		 if(i == filenumbers[j])
		 {
			 bfound = true;
			 break;
		 }
	   }
	   if( !bfound )
	   {
		 newfilenumber = i;
		 break;
	   }
	 }

	sprintf(filename,"%04d\n",newfilenumber);

     closedir(d);
   }

  return filename;
}

PTrenholme · 02-01-2010, 12:51 PM

Actually, a double-linked list:

Code:

struct dlist {
  dirent * entry;
  struct dlist * prior;
  struct dlist * post;
}

might be a more general solution. Then a tree search could be used to find the "next" gap which (for a large set of directory entries) would be more efficient than a sequential search. By using a dirent structure pointer (properly allocated, of course) in the list, the solution would be easily generalized to non-numeric file names.

PTrenholme · 02-01-2010, 01:07 PM

Re your code:

You will read the whole directory every time the function is called.
Your error condition is to return "0000" as the file name. It might make the calling program more efficient if you set an error flag that could be checked.
If, instead, you followed the suggestion of Alien_hominid, you would initialize filenumbers to all zeros, and then, when a number is found, set filenumber[num]=1 Then your check would be for (j=num;j<10000 && filenum[j];++j) rather than a nested loop.

carbonfiber · 02-01-2010, 01:13 PM

We are talking about finding a "missing number" between 1 and 9999. I'd take the easy array solution without thinking twice about it. I also consider it the superior approach because of the specifics of the task.

HarryBoy: Keep working on it, reread Alien_Hominid's initial suggestion.

aspire1 · 02-01-2010, 01:32 PM

You could try using scandir as well, code not really tested so usual disclaimers apply:

Code:

int main(){
	
	int currentFreeNum = 1;

	
	struct dirent **namelist;
	int index = 0;
	
	int foundNumber = 0;

	int numOfDirs = scandir( ".", &namelist, 0, alphasort );


	if( numOfDirs> 0 )
	{

               while ( index < numOfDirs && ! foundNumber )
               {

                  int num = atoi( namelist[ index ]->d_name );

		  if( num > 0 && num < 9999){
			  
			  if( currentFreeNum < num ){
			  
				  foundNumber = 1;
			  }
			  else
			  {
				  currentFreeNum++;  
			  }
			  
			   printf("Filename %s number=%d\n", namelist[index]->d_name, num);
			   free( namelist[ index ] );
		  }
		  
              index++;
         }
	 
	 free( namelist );
	}
	
	if( foundNumber ){
		
		printf( "You can use number = %d\n", currentFreeNum );
	}
	else
	{
		printf( "No free numbers found.");
	}
}

Alien_Hominid · 02-02-2010, 10:16 AM

Singly linked list is enough because:

OP needs a new number that is not one of already available numbers.
We select smallest number and remove it from the list - we do not need to loop through, we just take the first element.

carbonfiber · 02-02-2010, 10:29 AM

That seems to imply creating the complete list first, also, assume you read number N, how do you remove the associated element from the list? A better question would be: what is the representation of the singly-linked list?

Alien_Hominid · 02-02-2010, 11:04 AM

http://en.wikipedia.org/wiki/Linked_...y-linked_lists

No, you read through directory listing. Assume 4 is missing, you add it to the list, then you find that 9 is missing, you add it to the list, etc, etc...
You get 4 -> 9 -> ...

While doubly linked list would be:

4 <-> 9 <->, which is unecessary because you always take lowest number first.

carbonfiber · 02-02-2010, 11:46 AM

Ah. I got it, you were saying that a singly linked list would suffice given the choice between singly linked and doubly linked. Quite.