sorting the input

[arnuld]

1st I think of creating an array of pointers of size 100 as this is the
maximum input I intend to take. I can create a fixed size array but in the
end I want my array to expand at run-time to fit the size of input. I am
not able to come up with anyting all all and doing:

char* arr_of_pointers[100];

seems like a completely wrong idea as this is a static array. I want to
take the input and then decide how much memory I need and then malloc the
array of that size. I came up with K&R2 idea:


1.) read and save the input lines till the user hits the EOF
2.) sort them
3.) print them

I am pretty much confused on what to start with. Can I have your ideas in
solving this problem ? All I can think of is:


use sort algorithm from the standard library to sort the lines.
print the lines using %s as argument in printf().



--

http://lispmachine.wordpress.com/

my email ID is at the above address

[arnuld]

Re: sorting the input

On Tue, 22 Apr 2008 23:59:49 +0500, arnuld wrote:

1st I think of creating an array of pointers of size 100 as this is the
maximum input I intend to take. I can create a fixed size array but in the
end I want my array to expand at run-time to fit the size of input. I am
not able to come up with anyting all all and doing:
>
char* arr_of_pointers[100];

...[SNIP]....

I came up with the Static Version of this function with 1 error and I
can't seem to find a way either to remove that error or to convert it to a
dynamic version of the program:


/* write a program to read a set of lines from input and sort them
* and then print them.
*
* version 1.0
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum MAXLINES { ARRSIZE = 100 };

char* arr_of_ptr[ARRSIZE];
char arr_of_lines[ARRSIZE];

int readlines( char**, char*, const int max );
void printlines( char** );


/* main() will simply call the other functions to do the job */

int main( void )
{
if( readlines( arr_of_ptr, arr_of_lines, ARRSIZE ) 0 )
{
qsort( arr_of_ptr, ARRSIZE, sizeof( char* ) ); /* Line 26 */
printlines( arr_of_ptr );
}
else
{
fprintf( stderr, "error: out of memory\n" );
}

return 0;
}


/* 1) read lines till we get the NULL,
* 2) store those lines into an array of characters <arr_of_lines >,
* 3) pointer of arry of pointers <arr_of_ptrwi ll point to the
* individual elements of array of characters <arr_of_lines >,
*
*/

int readlines( char* arr_of_ptr[], char arr_of_lines[], int max )
{
int num_lines;

char temp_arr[ARRSIZE];

num_lines = 0;

while( fgets(temp_arr, max, stdin) )
{
strcpy( arr_of_lines, temp_arr );
*arr_of_ptr++ = arr_of_lines++;
++num_lines;
}

return num_lines;
}


/* it will simply print the lines pointed to by the elements of
* arrays of pointers <arr_of_ptr>.
*
*/
void printlines( char* arr_of_ptr[] )
{
while( *arr_of_ptr != '\0' )
{
puts( *arr_of_ptr++ );
}
}
=============== = OUTPUT =============== =====
[arnuld@raj C]$ gcc -ansi -pedantic -Wall -Wextra 5-7.c
5-7.c: In function `main':
5-7.c:27: error: too few arguments to function `qsort'
[arnuld@raj C]$



I know that qsort needs a compare function and I found this in FAQ:

http://www.c-faq.com/lib/qsort1.html

but a statement like: *(char * const *)p1

is totally beyond my capability.




--

http://lispmachine.wordpress.com/

my email ID is at the above address

[Nick Keighley]

Re: sorting the input

please include the subject in the body of your email:

"sorting the input"

On 22 Apr, 19:59, arnuld <GoogleGroupsis Full0fS...@gmai l.comwrote:

1st I think of creating an array of pointers of size 100 as this is the
maximum input I intend to take. I can create a fixed size array but in the
end I want my array to expand at run-time to fit the size of input. I am
not able to come up with anyting all all and doing:

take a look at realloc(). Initally malloc() a block of pointers
and when it fills up call realloc().

   char* arr_of_pointers[100];
>
seems like a completely wrong idea as this is a static array. I want to
take the input and then decide how much memory I need and then malloc the
array of that size. I came up with K&R2 idea:
>
   1.)   read and save the input lines till the user hits the EOF
   2.)   sort them
   3.)   print them
>
I am pretty much confused on what to start with. Can I have your ideas in
solving this problem ? All I can think of is:
>
  use sort algorithm from the standard library to sort the lines.
  print the lines using %s as argument in printf().

or fputs()

sounds fine to me. Which bit are you stuck on?


--
Nick Keighley

[Ben Bacarisse]

Re: sorting the input

arnuld <GoogleGroupsis Full0fSpam@gmai l.comwrites:

>On Tue, 22 Apr 2008 23:59:49 +0500, arnuld wrote:

>

>1st I think of creating an array of pointers of size 100 as this is the
>maximum input I intend to take. I can create a fixed size array but in the
>end I want my array to expand at run-time to fit the size of input. I am
>not able to come up with anyting all all and doing:
>>
> char* arr_of_pointers[100];

>

>...[SNIP]....

>
>
I came up with the Static Version of this function with 1 error and I
can't seem to find a way either to remove that error or to convert it to a
dynamic version of the program:
>
>
/* write a program to read a set of lines from input and sort them
* and then print them.
*
* version 1.0
*/
>
>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
>
enum MAXLINES { ARRSIZE = 100 };
>
char* arr_of_ptr[ARRSIZE];
char arr_of_lines[ARRSIZE];

I would not link these two sizes. You need two enum constants.

int readlines( char**, char*, const int max );
void printlines( char** );
>
>
/* main() will simply call the other functions to do the job */
>
int main( void )
{
if( readlines( arr_of_ptr, arr_of_lines, ARRSIZE ) 0 )
{
qsort( arr_of_ptr, ARRSIZE, sizeof( char* ) ); /* Line 26 */

OK, I see you ask about this later.

printlines( arr_of_ptr );
}
else
{
fprintf( stderr, "error: out of memory\n" );
}
>
return 0;
}
>
>
/* 1) read lines till we get the NULL,
* 2) store those lines into an array of characters <arr_of_lines >,
* 3) pointer of arry of pointers <arr_of_ptrwi ll point to the
* individual elements of array of characters <arr_of_lines >,
*
*/
>
int readlines( char* arr_of_ptr[], char arr_of_lines[], int max )

The second parameter has a bad name. At best it is one line.

{
int num_lines;
>
char temp_arr[ARRSIZE];
>
num_lines = 0;
>
while( fgets(temp_arr, max, stdin) )
{
strcpy( arr_of_lines, temp_arr );
*arr_of_ptr++ = arr_of_lines++;

This can't work. You must malloc space for the line you have just
read. There is nowhere else to put the line that will survive both
the next execution of the loop and the return from this function.

++num_lines;
}
>
return num_lines;
}
>
>
/* it will simply print the lines pointed to by the elements of
* arrays of pointers <arr_of_ptr>.
*
*/
void printlines( char* arr_of_ptr[] )
{
while( *arr_of_ptr != '\0' )

Correct, but confusing. '\0' is a char constant equal to zero so it
works, but I'd expect plain 0 or, better, NULL here.

{
puts( *arr_of_ptr++ );

You will get extra newlines. puts adds one and fgets retains the
newline from the input.

}
}
=============== = OUTPUT =============== =====
[arnuld@raj C]$ gcc -ansi -pedantic -Wall -Wextra 5-7.c
5-7.c: In function `main':
5-7.c:27: error: too few arguments to function `qsort'
[arnuld@raj C]$
>
>
>
I know that qsort needs a compare function and I found this in FAQ:
>

http://www.c-faq.com/lib/qsort1.html

>
>
but a statement like: *(char * const *)p1
>
is totally beyond my capability.

I'd stick with reading the lines in first. Deal with sorting later.

--
Ben.

[arnuld]

Re: sorting the input

On Tue, 22 Apr 2008 13:05:13 +0100, Ben Bacarisse wrote:

...[SNIP]...

This can't work. You must malloc space for the line you have just
read. There is nowhere else to put the line that will survive both
the next execution of the loop and the return from this function.

I did not get what exactly you mean. That array is created already with
reserved space, then I am copying its contents to another place then I
don't care what fgets() puts into it on next call, because I will copy
that away too. It exists for temporary saving of input for single call to
while().

Though as you advised, I changed it to malloc but the "why the malloc" is
not clear to me.

..[SNIP].....
I'd stick with reading the lines in first. Deal with sorting later.

ok, I removed the sorting routines and any calls to it. This program now
compiles and runs with strange output:


/* write a program to read a set of lines from input and sort them
* and then print them.
*
* version 1.0
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum MAXLINES { ARR_SIZE = 100, STR_SIZE = 1000 };

char* arr_of_ptr[ARR_SIZE];
char arr_of_char[STR_SIZE];

int readlines( char**, char*, const int max );
void printlines( char** );


/* main() will simply call the other functions to do the job */

int main( void )
{
if( readlines( arr_of_ptr, arr_of_char, STR_SIZE ) 0 )
{
/* qsort( arr_of_ptr, ARR_SIZE, sizeof( char* )); */
printlines( arr_of_ptr );
}
else
{
fprintf( stderr, "error: out of memory\n" );
}

return 0;
}


/* 1) read lines till we get the NULL,
* 2) store those lines into an array of characters <arr_of_lines >,
* 3) pointer of arry of pointers <arr_of_ptrwi ll point to the
* individual elements of array of characters <arr_of_lines >,
*
*/

int readlines( char* arr_of_ptr[], char arr_of_char[], int max )
{
int num_lines;
char *p;

p = malloc( max * sizeof( char* ));

num_lines = 0;

while( fgets(p, max, stdin) )
{
strcpy( arr_of_char, p );
*arr_of_ptr++ = arr_of_char++;
++num_lines;
}

return num_lines;
}




/* it will simply print the lines pointed to by the elements of
* arrays of pointers <arr_of_ptr>.
*
*/
void printlines( char* arr_of_ptr[] )
{
printf("\n-------------------------\n");
while( *arr_of_ptr )
{
printf("%s", *arr_of_ptr++ );
}
}


=========== OUTPUT ==============
[arnuld@raj C]$ gcc -ansi -pedantic -Wall -Wextra 5-7.c
[arnuld@raj C]$ ./a.out
and
oye
....love

-------------------------
ao...love
o...love
....love
[arnuld@raj C]$




--

http://lispmachine.wordpress.com/

my email ID is at the above address

[Ben Bacarisse]

Re: sorting the input

arnuld <GoogleGroupsis Full0fSpam@gmai l.comwrites:

>On Tue, 22 Apr 2008 13:05:13 +0100, Ben Bacarisse wrote:

>
>
>

>...[SNIP]...

>

>This can't work. You must malloc space for the line you have just
>read. There is nowhere else to put the line that will survive both
>the next execution of the loop and the return from this function.

>
>
I did not get what exactly you mean. That array is created already with
reserved space, then I am copying its contents to another place then I
don't care what fgets() puts into it on next call, because I will copy
that away too. It exists for temporary saving of input for single call to
while().

In total your program had an array of 100 char pointers. One array of
100 characters (the "global" one) and a local array of 100 characters.
That just can't be enough "in general". Where are the characters of
the second line stored?

Did you intend that the whole file should fit into one 100 character
array, with the each start of line pointer to by one of the 100
character pointers? If that was your plan, then the error was one of
detail -- you were not doing that, but your code could be corrected to
do that. The trouble is that such fixed-size solutions are almost
never worth getting right -- you need allocated storage when you don't
know the data size in advance.

Though as you advised, I changed it to malloc but the "why the malloc" is
not clear to me.
>
>
>
>

>..[SNIP].....
>I'd stick with reading the lines in first. Deal with sorting later.

>
ok, I removed the sorting routines and any calls to it. This program now
compiles and runs with strange output:
>
>
/* write a program to read a set of lines from input and sort them
* and then print them.
*
* version 1.0
*/
>
>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
>
enum MAXLINES { ARR_SIZE = 100, STR_SIZE = 1000 };
>
char* arr_of_ptr[ARR_SIZE];
char arr_of_char[STR_SIZE];
>
int readlines( char**, char*, const int max );
void printlines( char** );
>
>
/* main() will simply call the other functions to do the job */
>
int main( void )
{
if( readlines( arr_of_ptr, arr_of_char, STR_SIZE ) 0 )
{
/* qsort( arr_of_ptr, ARR_SIZE, sizeof( char* )); */
printlines( arr_of_ptr );
}
else
{
fprintf( stderr, "error: out of memory\n" );
}
>
return 0;
}
>
>
/* 1) read lines till we get the NULL,
* 2) store those lines into an array of characters <arr_of_lines >,
* 3) pointer of arry of pointers <arr_of_ptrwi ll point to the
* individual elements of array of characters <arr_of_lines >,
*
*/
>
int readlines( char* arr_of_ptr[], char arr_of_char[], int max )
{
int num_lines;
char *p;
>
p = malloc( max * sizeof( char* ));

Not what I intended. I assumed you continue to use a local array for
the line:

char one_line[SOME_SIZE];

num_lines = 0;
>
while( fgets(p, max, stdin) )

and read into that:

while( fgets(one_line, sizeof one_line, stdin) )

{

and do the malloc here, to save the line. At this point we know how
long it is (if we use strlen(one_line )) and we call allocate a copy
the line.

strcpy( arr_of_char, p );
*arr_of_ptr++ = arr_of_char++;

and we'd store the pointer in arr_or_ptr[num_lines] (I prefer that
style to your *arr_of_ptr++ = ... one).

++num_lines;
}
>
return num_lines;
}

--
Ben.

[arnuld]

Re: sorting the input

On Tue, 22 Apr 2008 14:18:26 +0100, Ben Bacarisse wrote:

In total your program had an array of 100 char pointers. One array of
100 characters (the "global" one) and a local array of 100 characters.
That just can't be enough "in general". Where are the characters of
the second line stored?

:-O

and read into that:
>
while( fgets(one_line, sizeof one_line, stdin) )

and do the malloc here, to save the line. At this point we know how
long it is (if we use strlen(one_line )) and we call allocate a copy
the line.

you meant this ?


int readlines( char* arr_of_ptr[], const int max )
{
int num_lines, size_arr;
char *p;
char temp_arr[STR_SIZE];

num_lines = 0;

while( fgets(temp_arr, max, stdin) && num_lines < max )
{
size_arr = strlen( temp_arr );
if( (p = malloc( size_arr * sizeof( char* ))) )
{
strcpy( p, temp_arr );
*arr_of_ptr++ = p;
++num_lines;
}

}

return num_lines;
}

and we'd store the pointer in arr_or_ptr[num_lines] (I prefer that
style to your *arr_of_ptr++ = ... one).

That's the style I want to use but I don't use it as that lies to me
about the very basic fact of C. At some point I will also stop using []
notation in function arguments as it fakes the array, it lies that it is
not a pointer, that it is a box of characters we call array and we are
using it directly but we are not, in fact, it is a pointer that is
manipulating the array and hence this distinction is the source of most
troubles I have and this trouble is intensively painful than the troubles
I get by not using array indexing.





--

http://lispmachine.wordpress.com/

my email ID is at the above address

[Nick Keighley]

Re: sorting the input

On 23 Apr, 06:25, arnuld <GoogleGroupsis Full0fS...@gmai l.comwrote:

On Tue, 22 Apr 2008 13:05:13 +0100, Ben Bacarisse wrote:

This can't work.  You must malloc space for the line you have just
read.  There is nowhere else to put the line that will survive both
the next execution of the loop and the return from this function.

>
I did not get what exactly you mean.

so I see! Say you have 10 lines you need 10 lumps
of memory to store the lines.

That array is created already with
reserved space, then I am copying its contents to another place

you read into the malloc()ed memory. Good. *Then* you copy it to
static memory and ignore the malloc()ed memory!

then I
don't care what fgets() puts into it on next call, because I will copy
that away too. It exists for temporary saving of input for single call to
while().

re-read your code it isn't doing what you think it is.

Though as you advised, I changed it to malloc but the "why the malloc" is
not clear to me.

I don't understand

<snip>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
>
enum MAXLINES { ARR_SIZE = 100, STR_SIZE = 1000 };
>
char*  arr_of_ptr[ARR_SIZE];
char   arr_of_char[STR_SIZE];
>
int readlines(  char**, char*,  const int max );
void printlines( char** );

you could avoid these by putting main() at the end

int main( void )
{
  if( readlines( arr_of_ptr, arr_of_char, STR_SIZE ) 0 )
    {
      /*      qsort( arr_of_ptr, ARR_SIZE, sizeof( char* ));  */
      printlines( arr_of_ptr );      
    }
  else
    {
      fprintf( stderr, "error: out of memory\n" );

well no. It might be an empty file

    }
>
  return 0;
>
}
>
/* 1) read lines till we get the NULL,
 * 2) store those lines into an array of characters <arr_of_lines >,
 * 3) pointer of arry of pointers <arr_of_ptrwi ll point to the
 *    individual elements of array of characters <arr_of_lines >,
 *
 */
>
int readlines( char* arr_of_ptr[], char arr_of_char[], int max )
{
  int num_lines;
  char *p;
>
  p = malloc( max * sizeof( char* ));

don't you mean sizeof(char)? Or since sizeof(char)
is 1 just omit it. You don't check the return
value of malloc(). Your malloc() should be in the loop.

  num_lines = 0;
>
  while( fgets(p, max, stdin) )

you read it into the malloced buffer

    {
      strcpy( arr_of_char, p );

then you copy to a static buffer. Why?

      *arr_of_ptr++ = arr_of_char++;

what does this do? When the loop ends

aop[0] = aoc[0]
aop[1] = aoc[1]
aop[2] = aoc[2]

suppose aoc contains "ao...love"
then your print routine will print

ao...love
o...love
...love

      ++num_lines;
    }
>
  return num_lines;
>
}
>
/* it will simply print the lines pointed to by the elements of
 * arrays of pointers <arr_of_ptr>.
 *
 */
void printlines( char* arr_of_ptr[] )
{
  printf("\n-------------------------\n");
  while( *arr_of_ptr )
    {
      printf("%s", *arr_of_ptr++ );
    }
>
}
>
=========== OUTPUT ==============
[arnuld@raj C]$ gcc -ansi -pedantic -Wall -Wextra 5-7.c
[arnuld@raj C]$ ./a.out
and
oye
...love
>
-------------------------
ao...love
o...love
...love

--
Nick Keighley

[Ben Bacarisse]

Re: sorting the input

arnuld <GoogleGroupsis Full0fSpam@gmai l.comwrites:

<snip>

you meant this ?
>
>
int readlines( char* arr_of_ptr[], const int max )
{
int num_lines, size_arr;
char *p;
char temp_arr[STR_SIZE];
>
num_lines = 0;
>
while( fgets(temp_arr, max, stdin) && num_lines < max )
{
size_arr = strlen( temp_arr );
if( (p = malloc( size_arr * sizeof( char* ))) )

You need size_arr + 1. You are storing chars, not char *s.

{
strcpy( p, temp_arr );
*arr_of_ptr++ = p;
++num_lines;
}
>
}
>
return num_lines;
}
>
>

>and we'd store the pointer in arr_or_ptr[num_lines] (I prefer that
>style to your *arr_of_ptr++ = ... one).

>
>
That's the style I want to use but I don't use it as that lies to me
about the very basic fact of C. At some point I will also stop using []
notation in function arguments as it fakes the array, it lies that it is
not a pointer, that it is a box of characters we call array and we are
using it directly but we are not, in fact, it is a pointer that is
manipulating the array and hence this distinction is the source of most
troubles I have and this trouble is intensively painful than the troubles
I get by not using array indexing.

Sorry, I can't follow that. It was a matter of style not correctness,
so I am not sure it is worth pursuing.

--
Ben.

[arnuld]

Re: sorting the input

On Tue, 22 Apr 2008 15:50:11 +0100, Ben Bacarisse wrote:

>arnuld <GoogleGroupsis Full0fSpam@gmai l.comwrites:
> while( fgets(temp_arr, max, stdin) && num_lines < max )
> {
> size_arr = strlen( temp_arr );
> if( (p = malloc( size_arr * sizeof( char* ))) )

You need size_arr + 1. You are storing chars, not char *s.

and what I am supposed to do with last element ?

I think NULL should be the last element but I can't find a way
to add it.

Sorry, I can't follow that. It was a matter of style not correctness,
so I am not sure it is worth pursuing.

okay :)


--

http://lispmachine.wordpress.com/

my email ID is at the above address

[Joachim Schmitz]

Re: sorting the input

arnuld wrote:

>On Tue, 22 Apr 2008 15:50:11 +0100, Ben Bacarisse wrote:

>

>>arnuld <GoogleGroupsis Full0fSpam@gmai l.comwrites:
>> while( fgets(temp_arr, max, stdin) && num_lines < max )
>> {
>> size_arr = strlen( temp_arr );
>> if( (p = malloc( size_arr * sizeof( char* ))) )

>

>You need size_arr + 1. You are storing chars, not char *s.

>
>
and what I am supposed to do with last element ?

You need It for the string terminating \0.
strlen gives the lengh without the terminating \0, so you need to add it to
the size you malloc

I think NULL should be the last element but I can't find a way
to add it.

\0, not NULL and the "strcpy( p, temp_arr );" in your next line whill do
that for you.

Bye, Jojo

[Ben Bacarisse]

Re: sorting the input

arnuld <GoogleGroupsis Full0fSpam@gmai l.comwrites:

>On Tue, 22 Apr 2008 15:50:11 +0100, Ben Bacarisse wrote:

>

>>arnuld <GoogleGroupsis Full0fSpam@gmai l.comwrites:
>> while( fgets(temp_arr, max, stdin) && num_lines < max )
>> {
>> size_arr = strlen( temp_arr );
>> if( (p = malloc( size_arr * sizeof( char* ))) )

>

>You need size_arr + 1. You are storing chars, not char *s.

>
and what I am supposed to do with last element ?
>
I think NULL should be the last element but I can't find a way
to add it.

the strcpy (now snipped from the quote) copies the string including
the final '\0' bytes. That is what the +1 is for.

--
Ben.

[arnuld]

Re: sorting the input

On Tue, 22 Apr 2008 13:05:13 +0100, Ben Bacarisse wrote:

I would not link these two sizes. You need two enum constants.

it is done.

The second parameter has a bad name. At best it is one line.

sorry, my mistake

I'd stick with reading the lines in first. Deal with sorting later.

okay, I am done with reading and printing lines now. It is working now, I
need to understand the sorting part now:


/* write a program to read a set of lines from input and sort them
* and then print them.
*
* version 1.0
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum MAXLINES { ARR_SIZE = 100, STR_SIZE = 1000 };

char* arr_of_ptr[ARR_SIZE];
char arr_of_char[STR_SIZE];

int readlines( char**, const int );
void printlines( char** );


/* main() will simply call the other functions to do the job */

int main( void )
{
if( readlines( arr_of_ptr, ARR_SIZE ) 0 )
{
/* qsort( arr_of_ptr, ARR_SIZE, sizeof( char* )); */
printlines( arr_of_ptr );
}
else
{
fprintf( stderr, "error: out of memory\n" );
}

return 0;
}


/* 1) read lines till we get the NULL,
* 2) store those lines into an array of characters <arr_of_lines >,
* 3) pointer of arry of pointers <arr_of_ptrwi ll point to the
* individual elements of array of characters <arr_of_lines >,
*
*/

int readlines( char* arr_of_ptr[], const int max )
{
char *p, **p_arrptr;
int num_lines, size_arr;
char temp_arr[STR_SIZE];

num_lines = 0;
p_arrptr = arr_of_ptr;

while( fgets(temp_arr, max, stdin) && num_lines < max )
{
size_arr = strlen( temp_arr ) + 1;
if( (p = malloc( size_arr * sizeof( char ))) )
{
strcpy( p, temp_arr );
*p_arrptr++ = p;
++num_lines;
}

}

return num_lines;
}




/* it will simply print the lines pointed to by the elements of
* arrays of pointers <arr_of_ptr>.
*
*/
void printlines( char* arr_of_ptr[] )
{
printf("\n-------------------------\n");
while( *arr_of_ptr )
{
printf("%s", *arr_of_ptr++ );
}
}

============= OUTPUT =============== ====
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra 5-7.c
/home/arnuld/programs/C $ ./a.out
Ben & Richard
both are helping
C newbie.... arnuld

-------------------------
Ben & Richard
both are helping
C newbie.... arnuld
/home/arnuld/programs/C $







--

http://lispmachine.wordpress.com/

my email ID is at the above address

[Ben Bacarisse]

Re: sorting the input

arnuld <GoogleGroupsis Full0fSpam@gmai l.comwrites:

On Tue, 22 Apr 2008 13:05:13 +0100, Ben Bacarisse wrote:

>I'd stick with reading the lines in first. Deal with sorting later.

>
okay, I am done with reading and printing lines now. It is working
now,

Sorry, not quite.

I need to understand the sorting part now:

I think you need to show your best attempt at the sort call and people
will help you get the details right.

/* write a program to read a set of lines from input and sort them
* and then print them.
*
* version 1.0
*/

enum MAXLINES { ARR_SIZE = 100, STR_SIZE = 1000 };
>
char* arr_of_ptr[ARR_SIZE];
char arr_of_char[STR_SIZE];

This second array seem not to be used now (that is as I would expect)
so you should get rid of it.

if( readlines( arr_of_ptr, ARR_SIZE ) 0 )

int readlines( char* arr_of_ptr[], const int max )
{
char *p, **p_arrptr;
int num_lines, size_arr;
char temp_arr[STR_SIZE];
>
num_lines = 0;
p_arrptr = arr_of_ptr;
>
while( fgets(temp_arr, max, stdin) && num_lines < max )

^^^?

Safe (because max happens to be less that STR_SIZE) but not correct.

{
size_arr = strlen( temp_arr ) + 1;
if( (p = malloc( size_arr * sizeof( char ))) )

You can omit sizeof(char). It is 1 by definition. I can see why some
people might want a size there, but if you are one of them then you
should use the c.l.c-approved idiom:

if( (p = malloc(size_arr * sizeof *p)) )

{
strcpy( p, temp_arr );
*p_arrptr++ = p;
++num_lines;
}
>
}
>
return num_lines;
}

--
Ben.

[pete]

Re: sorting the input

arnuld wrote:

1st I think of creating an array of pointers of size 100 as this is the
maximum input I intend to take. I can create a fixed size array but in the
end I want my array to expand at run-time to fit the size of input. I am
not able to come up with anyting all all and doing:
>
char* arr_of_pointers[100];
>
seems like a completely wrong idea as this is a static array. I want to
take the input and then decide how much memory I need and then malloc the
array of that size. I came up with K&R2 idea:
>
>
1.) read and save the input lines till the user hits the EOF
2.) sort them
3.) print them
>
I am pretty much confused on what to start with. Can I have your ideas in
solving this problem ?

That is my idea of a linked list problem.

/* BEGIN sort_input.c */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

typedef struct list_node {
struct list_node *next;
void *data;
} list_type;

int lencomp(const list_type *a, const list_type *b);
int str_cmp(const list_type *a, const list_type *b);
int get_line(char **lineptr, size_t *n, FILE *stream);
int list_fputs(cons t list_type *node, FILE *stream);
list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size);
void list_free(list_ type *node, void (*free_data)(vo id *));
list_type *list_sort(list _type *head,
int (*compar)(const list_type *, const list_type *));
list_type *sort_node(list _type *head,
int (*compar)(const list_type *, const list_type *));
list_type *split_list(lis t_type *head);
list_type *merge_lists(li st_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));

int main(void)
{
int rc;
list_type *head = NULL;
list_type *tail = NULL;
char *buff = NULL;
size_t size = 0;
long unsigned line_count = 0;

puts("/* BEGIN sort_input.c output */\n");
puts("This program makes and prints a list of all the lines\n"
"of text entered from standard input.\n"
"Just hit the Enter key to end,\n"
"or enter any line of characters to continue.");
while ((rc = get_line(&buff, &size, stdin)) 1) {
++line_count;
tail = list_append(&he ad, tail, buff, rc);
if (tail == NULL) {
break;
}
puts("\nJust hit the Enter key to end,\n"
"or enter any line of characters to continue");
}
free(buff);
printf("%lu lines of text were entered.\n", line_count);
puts("They are:");
list_fputs(head , stdout);
puts("\nStable sorted by length, the lines are:");
head = list_sort(head, lencomp);
list_fputs(head , stdout);
puts("\nSorted by strcmp, they are:");
head = list_sort(head, str_cmp);
list_fputs(head , stdout);
list_free(head, free);
puts("\n/* END sort_input.c output */");
return 0;
}

int lencomp(const list_type *a, const list_type *b)
{
const size_t a_len = strlen(a -data);
const size_t b_len = strlen(b -data);

return b_len a_len ? -1 : b_len != a_len;
}

int str_cmp(const list_type *a, const list_type *b)
{
return strcmp(a -data, b -data);
}

int get_line(char **lineptr, size_t *n, FILE *stream)
{
int rc;
void *p;
size_t count;

count = 0;
while ((rc = getc(stream)) != EOF
|| !feof(stream) && !ferror(stream) )
{
++count;
if (count == (size_t)-2) {
if (rc != '\n') {
(*lineptr)[count] = '\0';
(*lineptr)[count - 1] = (char)rc;
} else {
(*lineptr)[count - 1] = '\0';
}
break;
}
if (count + 2 *n) {
p = realloc(*linept r, count + 2);
if (p == NULL) {
if (*n count) {
if (rc != '\n') {
(*lineptr)[count] = '\0';
(*lineptr)[count - 1] = (char)rc;
} else {
(*lineptr)[count - 1] = '\0';
}
} else {
if (*n != 0) {
**lineptr = '\0';
}
ungetc(rc, stream);
}
count = 0;
break;
}
*lineptr = p;
*n = count + 2;
}
if (rc != '\n') {
(*lineptr)[count - 1] = (char)rc;
} else {
(*lineptr)[count - 1] = '\0';
break;
}
}
if (rc != EOF || !feof(stream) && !ferror(stream) ) {
rc = INT_MAX count ? count : INT_MAX;
} else {
if (*n count) {
(*lineptr)[count] = '\0';
}
}
return rc;
}

int list_fputs(cons t list_type *node, FILE *stream)
{
int rc = 0;

while (node != NULL
&& (rc = fputs(node -data, stream)) != EOF
&& (rc = putc('\n', stream)) != EOF)
{
node = node -next;
}
return rc;
}

list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size)
{
list_type *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -next = NULL;
node -data = malloc(size);
if (node -data != NULL) {
memcpy(node -data, data, size);
if (*head != NULL) {
tail -next = node;
} else {
*head = node;
}
} else {
free(node);
node = NULL;
}
}
return node;
}

void list_free(list_ type *node, void (*free_data)(vo id *))
{
list_type *next_node;

while (node != NULL) {
next_node = node -next;
free_data(node -data);
free(node);
node = next_node;
}
}

list_type *list_sort(list _type *head,
int (*compar)(const list_type *, const list_type *))
{
return head != NULL ? sort_node(head, compar) : head;
}

list_type *sort_node(list _type *head,
int (*compar)(const list_type *, const list_type *))
{
list_type *tail;

if (head -next != NULL) {
tail = split_list(head );
tail = sort_node(tail, compar);
head = sort_node(head, compar);
head = merge_lists(hea d, tail, compar);
}
return head;
}

list_type *split_list(lis t_type *head)
{
list_type *tail;

tail = head -next;
while ((tail = tail -next) != NULL
&& (tail = tail -next) != NULL)
{
head = head -next;
}
tail = head -next;
head -next = NULL;
return tail;
}

list_type *merge_lists(li st_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
list_type *list, *sorted, **node;

node = compar(head, tail) 0 ? &tail : &head;
list = sorted = *node;
*node = sorted -next;
while (*node != NULL) {
node = compar(head, tail) 0 ? &tail : &head;
sorted -next = *node;
sorted = *node;
*node = sorted -next;
}
sorted -next = tail != NULL ? tail : head;
return list;
}

/* END get_line.c */