Use of sort algorithm of vc++. Problem I face

[vcmohan]

I am trying to sort the grey scale values along with their x and y frame coordinates. I ( my reference book C++ Primer by Stanley B.Lippman and Josee Lajoie) As I found no reference to have a primary variable on which to sort and secondary variables to be kept along with the sorted values (as available in excel) I devised a scheme whereby the grey value will be in upper 8 bits, y val in next 12 bits and the x value in the last 12 bits. My code piece is below.


if(!exist)
{
pixelsort = new int[psize];
tag = new int[psize];
dist = new int[psize];
exist=true;
}

int pitch = (rx-lx+1); // similar to frames so that height and width can be used


if(vi.IsYUY2() || vi.IsYV12() || vi.IsRGB())

{


int init=-1, mask=-2,wshed=0;
int curtag=0, curdist=0;

// prepare data for sorting
for(int h=0;h<=by-ty;h++)
for(int w=0; w<=rx-lx; w++)
{
int gval= *(fp+(h+ty)*fpitch+kb*(w+lx));

pixelsort[(h)*pitch+(w)]=(gval<<24) | (h<<12) | w ;
// initialize the tag and dist buffers
tag[(h)*pitch+(w)]=init;
dist[(h)*pitch+(w)]= 0;
}

// default sort is in ascending order. hope this is done in situ
// std::sort(&pixelsort[0], &pixelsort[psize-1]);
std::sort(pixelsort, pixelsort+psize-1);

// minimum and max grey values
int gmin= pixelsort[0] >> 24;
gmin=gmin<lt?lt:gmin; // new control added
int gmax=pixelsort[psize-1] >> 24;
gmax=gmax>ut?ut:gmax; // new control added
int gindex=0, pindex=0; // these will hopefully reduce search of pixelsort buffer for a g value
// my debug code
env->ThrowError("gmin= %d, gmax = %d", gmin, gmax);


I am getting strange values so I checked with the ThrowError code. I get some times -ve values for gmax.
I expect sort to do an inplace sort with ascending order.
VC++ however shows _Sort , Sort_0, Sort_max etc. It shows some parameters like RI BI TY* etc which I couldnt make any meaning. sort itself is not listed but it is not shown as an error while compiling. In include file The algorithm file could not be opened.
May be sort is c style 16 bit only routine?
I need help as to how to go about

[mg262]

>The algorithm file could not be opened.

Well, that's definitely the first thing to deal with. Can you open other standard STL headers like vector? What version of VC are you using?

I've included a complete, very small, filter that uses sort for you to look at... ignore distance2norm; you only really need to look at the MatchInfo class and the constructor of the FindMatch class.


#include "stdafx.h"

#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

double distance2norm(PVideoFrame from, PVideoFrame to)
{
const unsigned char *fromrow = from->GetReadPtr();
const unsigned char *torow = to->GetReadPtr();

const int frompitch = from->GetPitch();
const int topitch = to->GetPitch();
const int width = from->GetRowSize();
const int height = to->GetHeight();

double sum = 0.0;

for(int y = 0; y < height; ++y)
{
int rowsum = 0;

for(int x = 0; x < width; ++x)
{
int frompixel = fromrow[x];
int topixel = torow[x];
int difference = frompixel - topixel;

rowsum += difference*difference;
}
fromrow += frompitch;
torow += topitch;

sum += double(rowsum);
}

return sum/(width*height);
}

struct MatchInfo
{
int frame;
double match;
MatchInfo(int _frame, double _match) : frame(_frame), match(_match) {}
struct SortByMatch
{
bool operator() (MatchInfo a, MatchInfo b)
{
return a.match < b.match;
}
};
};


class FindMatch : public GenericVideoFilter
{
PClip tofind;
PClip search;
PClip display;
double displayproportion;
vector<MatchInfo> matchinfo;
public:
FindMatch(PClip _tofind, PClip _search, PClip _display, double _displayproportion, IScriptEnvironment *env);
PVideoFrame __stdcall GetFrame(int n, IScriptEnvironment *env);
};

FindMatch::FindMatch(PClip _tofind, PClip _search, PClip _display, double _displayproportion, IScriptEnvironment *env)
: GenericVideoFilter(_search), tofind(_tofind), search(_search), display(_display), displayproportion(_displayproportion)
{
VideoInfo searchinfo = search->GetVideoInfo();
if (!vi.IsYV12() || !searchinfo.IsYV12())
env->ThrowError("FindMatch requires YV12.");
if (vi.width != searchinfo.width)
env->ThrowError("Find width does not match search width.");
if (vi.height != searchinfo.height)
env->ThrowError("Find height does not match search height.");

int originalframes = vi.num_frames;
vi.num_frames = int(vi.num_frames*displayproportion + 0.5);

ofstream log("findmatch log.txt");
matchinfo.reserve(originalframes);

PVideoFrame findframe = tofind->GetFrame(0, env);
for (int n = 0; n < originalframes; ++n)
{
PVideoFrame scanframe = search->GetFrame(n, env);
double match = distance2norm(findframe, scanframe);
matchinfo.push_back(MatchInfo(n, match));
log << n << "\t" << match << "\n";
}

sort(matchinfo.begin(), matchinfo.end(), MatchInfo::SortByMatch());
}

PVideoFrame __stdcall FindMatch::GetFrame(int n, IScriptEnvironment *env)
{
int displayframe = matchinfo[n].frame;
return display->GetFrame(displayframe, env);
}


AVSValue __cdecl Create_FindMatch(AVSValue args, void* user_data, IScriptEnvironment *env)
{
return new FindMatch(args[0].AsClip(), args[1].AsClip(), args[2].AsClip(), args[3].AsFloat(1.0)*0.01, env);
}

extern "C" __declspec(dllexport) const char* __stdcall AvisynthPluginInit2(IScriptEnvironment *env)
{
env->AddFunction("FindMatch", "cccf", Create_FindMatch, 0);
return "FindMatch plugin";
}

[vcmohan]

Thanks. A second after I posted I found my mistake. I was using an signed integer array, keeping some potential -ve values in high order bits and then shifting by >>. I think the sign is being preserved in the bit shift. After correcting it my code is working fine.

Incidentally what are the other sort functions of VC++ 6 for? Sort, Sort_0, Sort_max etc;
sorry for my haste in posting. Actually I was previewing the post while I discovered my error and so I just closed the window. It appears there is no way to stop posting halfway.

[mg262]

Incidentally what are the other sort functions of VC++ 6 for? Sort, Sort_0, Sort_max etc;They are not really 'for' everything. C++ itself is a very coherent creation that makes sense internally, and its libraries tend to contain one very well implemented way of doing a given thing. But there is of course another way in the C libraries, which accounts for one more sort function. There are then any number of screwy Microsoft things packaged with VC. (Many of these predate the STL of course.) I would strongly recommend sticking with the STL unless you have very good reason to do otherwise.

Actually I was previewing the post while I discovered my error and so I just closed the window. It appears there is no way to stop posting halfway.Believe it or not that just happened to me now... occasionally the speech recognition engine picks up some noise as "submit". it can be very annoying.

[stickboy]

I am trying to sort the grey scale values along with their x and y frame coordinates. I ( my reference book C++ Primer by Stanley B.Lippman and Josee Lajoie) As I found no reference to have a primary variable on which to sort and secondary variables to be kept along with the sorted valuesYou can do it with stable sorts. You first sort on the secondary key then perform a stable sort on the primary key. When a stable sort compares two items it considers equal, it preserves the existing order.

STL provides a std::stable_sort method in <algorithm>.

[mg262]

There is also the option of doing it with one sort, with a comparison function looking like this:

if (a.primarykey < b.primarykey) return true;
if (a.primarykey > b.primarykey) return false;
//we know the primary keys are equal so compare the secondary keys
return (a.secondarykey < b.secondarykey)

... up to you which you prefer.

Edit: looking back, I'm not sure whether you just meant that you had auxiliary information as well as the stuff to be sorted... with the STL method, you can keep the extra information transparently in the objects you are sorting -- look at the frame member of MatchInfo in the example.

[vcmohan]

Edit: looking back, I'm not sure whether you just meant that you had auxiliary information as well as the stuff to be sorted... with the STL method, you can keep the extra information transparently in the objects you are sorting -- look at the frame member of MatchInfo in the example.

I have the grey value of the pixel as primary sort value and its x and y coordinates for secondary keys. I implemented by putting all these into one integer and get the result I wanted. But this could be done because the grey values are only 8 bits and the x and y coordinates unlikely to be more than 11 bits each. Since this formulation most likely will be faster than using a structure, for this particular application I will retain this method. But in general I wanted to know so that in future if a situation arises I can use a sort properly.
Thanks for the inputs

[Bidoche]

You can always create a Key class containing the key data you need and defining operator<.

Then std::sort will work as you want.