VB UDT's and C++ (whoa nelly)

Background

I have a file of VB a UDT's called Patient, which has the following definition...
VB Code:
LName As String * 16        
    FName As String * 12        
    MName As String * 1             
    BDate As String * 10        
    NDate As String * 10        
    Upi As Integer  'unique identifier
Each UDT is 100 bytes long...and is not in any discerning order in the file.

My application sorts these UDT's (500 records takes almost 1 second on a AMD 850mhz) when a new record is added.

My application does not sort the records in the file, but writes another file that just contains the UPI of each UDT in the order it should appear based on alphabetic order of LastName, FirstName, etc....

Problem
This works fine, but if I have 5000 records, I imagine it will take ten times longer. My idea was to implement a C++ dll to do the actual alphabetizing.

My half-ass ideas

Two solutions came to mind:
1) write C++ code to take an array of the UDT's and sort them (in memory). The problem is, I'm not quite certain how I should pass these UDT's to my C++ dll.

2) Read the file made by my VB app, take the values from that, and sort them, all within the C++ dll. The problem here is, even records of fixed-length UDT's seem to vary in size from record to record. I'm not sure how I can read these strings values into C++ since I actually have to examine each byte.

I would like to hear if anyone has encountered the same idea, or problem, and any suggestions as how I should approach this.

Whether it takes 10 times longer or not depends on how you perform the sort. Sorting algorithms like quicksort can be as good as O(log N), which is pretty good. You will probably find that you will get a much better performance boost for your effort by using a more efficient sorting algorithm in VB, rather than writing essentially the same thing in C++.

If you don't want to read everything into memory before you start sorting, consider a merge sort.

If i have a file of UDT's (say, the UDT consists of ID and Name)

Code:

1232 John 3292 Andy 2312 Philip 2123 Berry 2322 Timmy

I just created an index file (much like a database would do), so as you move through the records in the index file, you simply open the record with the ID that is stored.

Code:

rec# Index 1 3292 -points to Andy 2 2123 -points to Berry 3 1232 ... 4 2313 5 2322

It was difficult enough to implement this as a bubble sort, I had tried doing this with a divide and concquer sort, but EACH element does have to be compared to every other element.

They don't really need to be compared against every other element. For instance, you could add all the records to an ordered binary tree, and just do an inorder traversal of that tree to get every element, in order. You just have to compare each element to a proportion of the elements you've already sorted to know where it should go.

If you take some kind of recursive divide and conquer sort strategy like a merge sort or a quicksort, you shouldn't have to check against every other element, just a few.

Bubble sort is hideously slow as N grows large. If you are concerned with performance, a bubble sort is just about the worst kind of sort you can do. They're dead easy to write when you're in a rush, or just prototyping of course.

HarryW, thanks for the input. I agree with your view, but it appears alot easier when your working with just sorting numbers... I guess I should bite the bullet tho...

I really have no clue what you mean about binary trees... but I will google search it...

I'm sure there are some decent optimised sort functions written in VB out there somewhere. Many people will have them in their personal code libraries, to be used over and over. They might even already have a DLL for it.

Ask about it over in the General VB section and I am pretty sure someone will give you some sorting code you can adapt to your needs. It's gotta be easier and more efficient than writing a C DLL to do your bubble sort :)

Quote:

It's gotta be easier and more efficient than writing a C DLL to do your bubble sort

Actually, i got that about 60% done...

Well I have never written a DLL for VB so I was thinking the VB compatibility bit would be the tough part. Probably won't win you much in performance though. In the end, better algorithms will win out over faster execution.

Well, Harry, I finished implementing a Shell Short... and its races ...

Thanks...

Nice one :cool:

I have been doing some work in passing stuff from VB to C++ and stuff like that. I am not sure what version u use, as VB6 is a little bit easier since it supports pointers -- but i never test it myself.

as for VB .NET, passing it forward should be no problem -- but I've never figured out how to return a sorted array -- maybe i am wrong, but i think C++ can only pass back pointers to arrays, not arrays themselves right? anywayz passing array byVal is no problems, and personally i've never succeeded in passing byRef. in C++ just do a typedef struct patient {...} and you should be fine. if you want speed (as c++ does things faster) you can do this and use the dll to write the records to file directly and start from there. notice that if you want to pass arrays in C++ u usually can declare a typedef struct as mentioned above but in VB, if you declare a Structure/End Structure it will not let you define the size of array inside the structure so it won't pass back.

Well, I'm still having difficulties figuring out how I can read this in, the problem is trying to read the Upc of patient Struct.

Code:

#include<iostream> #include<fstream> using namespace std; struct patient { char Lname[16]; char Fname[12]; char Mname; char Bdate[10]; char Ndate[10]; int Upc; }; void main() { int i; patient p[400]; ofstream fout("c:\\patientlog.txt"); fstream File("c:\\patientpsa0.ps1",ios::out | ios::in | ios::binary); int Upi = 0; while (File.eof()==false) { File.read(p[Upi].Lname,16); File.read(p[Upi].Fname,12); File.get(p[Upi].Mname); File.read(p[Upi].Bdate,10); File.read(p[Upi].Ndate,10); File.read(p[Upi].Upc,sizeof(p[Upi].Upc)); Upi++; }

Gives me the following error at line bolded above

Quote:

Error C2664: 'read' : cannot convert parameter 1 from 'int' to 'char *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast

Looks like you're reading from the file into an integer variable, but you need to read the data into a char * variable. I guess you need to read into a string buffer, then convert that to an integer using atoi() or something similar.

quicksort is not that big a deal in C - use qsort.
This sorts 50000 random patient structs in 1200 ms on a 500MHz
PIII. (just the sort) Writing takes another second.

[code]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/stat.h>
#define zout(y) memset(&y,0x00,sizeof(y))
typedef struct patient
{
char Lname[16];
char Fname[12];
char Mname;
char Bdate[10];
char Ndate[10];
int Upc;
}p;

Code:

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <sys/stat.h> #define zout(y) memset(&y,0x00,sizeof(y)) typedef struct patient { char Lname[16]; char Fname[12]; char Mname; char Bdate[10]; char Ndate[10]; int Upc; }p; int cmp(const void*,const void *); int main(){ struct patient *first,*a,*b; FILE *in,*out; int nelem; struct stat statbuf; struct stat *s; s=&statbuf; in = fopen("patient.dat","rb"); stat("patient.dat",s); first = (p*) malloc( s->st_size ); fread(first,s->st_size,1,in); nelem = (int)(s->st_size / (long)sizeof(p) ); qsort(first,nelem,sizeof(p),cmp ); out=fopen("patient_sorted.dat","wb"); fwrite(first,sizeof(p),nelem,out); fclose(in); fclose(out); free(first); return 0; } int cmp(const void *a, const void *b){ //custom compare routine char tmp[40],tmp1[40]; struct patient *s; zout(tmp); zout(tmp1); s = (struct patient*)a; sprintf(tmp,"%10s%10s",s->Lname,s->Fname); // justify names into fields s=(struct patient*)b; sprintf(tmp1,"%10s%10s",s->Lname,s->Fname); return strcmp(tmp,tmp1); }

Mcnamara,

The code you supplied didn't work unless I commented out the
qsort call.... once I did, it sucessfully wrote the patient data using
C++ (which makes me happy), although, its not sorted of course..

An unhandled exception of some kind...

A few things perhaps you can explain:
1.<sys/stat.h> What library this is and what it accomplishes pertaining to the code supplied.

2. qsort(first,nelem,sizeof(p),cmp );

Is qsort being defined in <sys/stat.h>?

I have been working with C++ for only a year... so code like
#define zout(y) memset(&y,0x00,sizeof(y))
kinda loses me fast...

Thanks for your input and time on this... It is really fascinating to see code like this acheive so much..

Btw, the exception is occuring in the Cmp function...

Also, I should inform of you some things, not sure if the first one makes a difference:
1) The patient file is written using VB random access.. (doesn't appear to make a difference, but who knows)
2) The sort order should go like this

compare last names, if same
compare first names, if same
compare birthdates, if same
compare UPI's (the Upi's are all unique, so this is fail-safe)

I looked at the Qsort function on a webpage returned from Google , it appears to compare byte values... which would mean an uppercase F would come before a lowercase f, correct? Because that's not to be considered.

3) My program actually reads a seperate file, called psaindex, which is filled from start to finish with the a sorted listed of the patient UPI's.

So it would like this:
11,5,3,2,10

Given patients with last names and upi's of:

Code:

: Tutts 10 Franklin 5 Meyer 2 Adams 11

Its not that I need to rewrite the patient data back to the patient file in sorted order, I just need to rewrite the psaindex file that points to the upi of the next alphabetized patient.
Guppin 3

I haven't seen qsort() before so I'll let Jim explain that stuff.

I can help on the #define though :)

Code:

#define zout(y) memset(&y,0x00,sizeof(y))

If you don't know, this is what a macro is, and if you've been using C/C++ for a year you will almost certainly have heard macros mentioned.

A macro is a shorthand way of writing something. In effect, it's a lot like an inline function. If you write this code:

Code:

struct somekindofstructure aStructureVariable; zout(aStructureVariable);

Then your compiler will see that you have a 'zout' macro and will replace that code with this before compiling:

Code:

struct somekindofstructure aStructureVariable; memset(&aStructureVariable,0x00,sizeof(aStructureVariable));

Which will basically 'zero out' (I am guessing that's what the name is short for) that block of memory, making all the integers in your structure 0 and all the pointers NULL. This is often useful, and it's something that is done quite a lot, hence Jim has written a macro for it rather than write out the memset() call every time.

'#define' is also used to set constants that you can use in your code (although it's often better to use actual const variables as these will have addresses if you need them) and to set compiler environment variables.

The #define line create a macro - the compiler substitutes a variable for trhe letter 'y'

zout(p) becomes memset(p,0x00,sizeof(p))

I compiled and ran the code with ansi C. Which means it works in VC++. Check the visual studio docset for _qsort as well as qsort. MS sometimes does stuff like that.

qsort is part of the standard C library, and is defined as part of the ANSI standard for C and C++. If you're getting an exception, you may just copied and pasted my code. Make TOTALLY sure that the struct I used matches what you used.

You are likely running afoul of BSTR strings. That's what VB writes out to disk.
Everything you wrote to disk as a string is this in C++:
long, followed by char *.

Try this:
typedef struct patient
{
long blah;
char Lname[16];
long blah1;
char Fname[12];
char Mname;
long blah2;
char Bdate[10];
long blah3;
char Ndate[10];
int Upc;
}p;

Or change it to use BSTR

typedef struct patient
{
BSTR Lname;
BSTR Fname;
char Mname;
BSTR Bdate;
BSTR Ndate;
int Upc;
}p;

Plus, you will have to use different string operators in the compare function.

This latter choice is better for C++.

Well, I tried BSTR... got about 19 errors before I found is MSDN, i needed to include

Code:

#include <comdef.h>

So now, no errors...
But I could really use your help on how I am going to manipulate this with qsort and this cmp function...

All you need to do is read the Visual Studio help on qsort. It gives you an example.

The qsort arguments are:
address of the buffer that holds the items
size of 1 item
number of items to sort
function pointer to you own special compare function

qsort will sort anything because YOU supply the code that does the comparision and put it in a function I called mine cmp().
You can call it farkle() if you want. Doesn't matter.

use VectorFRomBSTR() -- Add oleaut.lib as a link library
You need to add as many fields to tmp & tmp1 as are need to make only ONE comparison, ie. dates, etc.

Code:

int cmp(const void *a, const void *b){ //custom compare routine char tmp[40],tmp1[40]; char *working,*working2; struct patient *s; zout(tmp); zout(tmp1); s = (struct patient*)a; HRESULT i = VectorFromBSTR(s->Lname,working); i= VectorFromBSTR(s->Fname,working1); sprintf(tmp,"%10s%10s",working,working1); // justify names into fields s=(struct patient*)b; i = VectorFromBSTR(s->Lname,working); i= VectorFromBSTR(s->Fname,working1); sprintf(tmp1,"%10s%10s",working,working1); return strcmp(tmp,tmp1); }

Or something like that. you need to mess around with it.
The rest of the code doesn't care about BSTR, except the struct declaration.

To make it case-independent use stricmp instead of strcmp.

Alright, this is gettin hard... and i am still nowhere closer to completion...
It seems the code Mcnamara wrote, will compare patient1's lastname and firstname vs patient2's lastname and firstname...

I do need to do these seperately, so... I should modify the sprintf() , or can I ditch it since I don't need Lname and Fname as part of tmp.. can I not just somehow pass the VectorFromBstr result..?

Already I'm lost...

Code:

int cmp(const void *a, const void *b){ //custom compare routine int j; char tmp[40],tmp1[40]; char *working,*working1; struct patient *s; struct patient *t; zout(tmp); zout(tmp1); s = (struct patient*)a; //the below code converts bstr into a vector passing it //to safearray working? But then how do I strcomp then? HRESULT i = VectorFromBSTR(s->Lname,working); //below code does the same as above code for 2nd patient t=(struct patient*)b; i = VectorFromBSTR(s->Lname,working1); j =strcmp( ? ); //compare last names if j < 0 || j > 0 'if last names are not equal return j; if j == 0 { //compare first names if j < 0 || j > 0 'if first names are not equal return j; if j == 0 { //compare middle initials if j < 0 || j > 0 'if middle init's are not equal return j; if j == 0 { //compare birthdates **the dates are stored as strings remember //ie. 11/20/2000 or 02/31/1995 if j < 0 || j > 0 'if birthdates's are not equal return j; if j == 0 { //compare UPI (unique patient identifier, which is an integer) //no two UPI's are the same, so one will //always be greater or lesser than another return j; }//end UPI comparison }//end birthdate comparison } // end middle initial comparison }//end firstname comparison } //end lastname compare }//end custom compare function