473,836 Members | 1,422 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

matching callback parameters in generic algorithm

I'm useless at templates, but, inspired by this post:

<hi************ *************** @syrcnyrdrs-01-ge0.nyroc.rr.co m>,

I'm trying to write an algorithm

template <class BidirectionalIt erator, class Function, class Size>
Function for_each_combin ation(Bidirecti onalIterator first,
BidirectionalIt erator last,
Size k,
Function fn);

which does the obvious thing.

The post references some code (from Feb 05 CUJ) which implements
for_each_permut ation. That implementation uses a nice algorithm from
Knuth to generate the permutations which

(i) cycles the elements of [first, last[ in situ, so that the callback can
be called simply as fn(first, last).

(ii) leaves the elements of [first, last[ in their original order.

I can't find such a nice algorithm for combinations. I have a simple
enough algorithm which generates all combinations of the integers 1, ...
(k-1). When it comes to calling the callback fn for each combination, I
copy the corresponding k elements from [first, last[ into a

vector<typename iterator_traits <BidirectionalI terator>::value _type>

but I can't make the call to fn. The caller supplies a callback taking
two parameters of the type BidirectionalIt erator, which isn't matched.

My questions:

Is there a way that I can convert iterators from my vector into the type
of the template parameter BidirectionalIt erator?

Alternatively, and off-topic, can anyone point me to an algorithm for
enumerating combinations which has the properties (i) and (ii) above?

Thanks.


Sep 10 '05 #1
3 1706
On Sat, 10 Sep 2005 12:24:48 +0000, spakka wrote:
Alternatively, and off-topic, can anyone point me to an algorithm for
enumerating combinations which has the properties (i) and (ii) above?


Ok - sorted now.

Sep 11 '05 #2
spakka wrote:
On Sat, 10 Sep 2005 12:24:48 +0000, spakka wrote:

Alternatively , and off-topic, can anyone point me to an algorithm for
enumerating combinations which has the properties (i) and (ii) above?

Ok - sorted now.


How? It was an interesting problem.

john
Sep 11 '05 #3
On Sun, 11 Sep 2005 13:29:49 +0000, John Harrison wrote:
spakka wrote:
On Sat, 10 Sep 2005 12:24:48 +0000, spakka wrote:

Alternativel y, and off-topic, can anyone point me to an algorithm for
enumeratin g combinations which has the properties (i) and (ii) above?

Ok - sorted now.


How? It was an interesting problem.

john


I cheated. I just copy into the storage that was passed to me, then
restore the original contents at the end:
// not for users
template<class ForwardIterator , class RandomAccessIte rator,
class Size, class Function>
Function _combine(Forwar dIterator first, ForwardIterator lastk,
ForwardIterator current, Size n, Size k, Size base, Size level,
Function f, RandomAccessIte rator vals)
{
for (Size i = base; i < n - k + 1 + level; ++i) {
*current = vals[i];
if (level == k - 1) {
f(first, lastk);
}
else {
f = _combine(first, lastk, current + 1, n, k, i + 1, level + 1,
f, vals);
}
}
return f;
}

template<class ForwardIterator , class Function, class Size>
Function for_each_combin ation(ForwardIt erator first,
ForwardIterator last, Size k, Function fn)
{
Size n = distance(first, last);
ForwardIterator lastk = first;
advance(lastk, k);

// save the original sequence
vector<typename iterator_traits <ForwardIterato r>::value_type > sav;
sav.reserve(n);
copy(first, last, back_inserter(s av));

fn = _combine(first, lastk, first, n, k, 0, 0, fn, sav.begin());

// restore the original sequence
copy(sav.begin( ), sav.end(), first);

return fn;
}

Sep 11 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
2477
by: ajay.sonawane | last post by:
Hello ther I read somewhere that callback function should be global or static member function. 1: I could use static member functions but how could I access members of class which ar not static. 2: I could use global function but want to access members of class. Let me know the possible solutions. Regards, Ajay Sonawane
10
4988
by: bpontius | last post by:
The GES Algorithm A Surprisingly Simple Algorithm for Parallel Pattern Matching "Partially because the best algorithms presented in the literature are difficult to understand and to implement, knowledge of fast and practical algorithms is not commonplace." Hume and Sunday, "Fast String Searching", Software - Practice and Experience, Vol. 21 # 11, pp 1221-48
8
572
by: kurtcobain1978 | last post by:
-------------------------------------------------------------------------------- I need to do the exactly same thing in VB.NET. Load a unmanaged C DLL dynamically and then call a function in which I pass the callback function as an argument. My C function being called callback as type _cdecl. Does anybody have any ideas?
10
9574
by: javuchi | last post by:
I'm searching for a library which makes aproximative string matching, for example, searching in a dictionary the word "motorcycle", but returns similar strings like "motorcicle". Is there such a library?
12
9902
by: Larry Bates | last post by:
I'm trying to get the results of binascii.crc32 to match the results of another utility that produces 32 bit unsigned CRCs. binascii.crc32 returns results in the range of -2**31-1 and 2**21-1. Has anyone ever worked out any "bit twiddling" code to get a proper unsigned 32 bit result from binascii.crc32? Output snip from test on three files: binascii.crc32=-1412119273, oldcrc32= 2221277246
2
1876
by: Marcus Kwok | last post by:
I have processing code (I'll call it the "model") written in native unmanaged pure C++, and I have put a GUI on top of it written using Windows Forms (.NET 1.1). The GUI is used to set the parameters for the model, and once all parameters are set and checked to be valid, I run the model. The model takes a long time to run, so I decided to run it in a background thread, and have it notify the GUI when it is complete. The GUI will then...
0
1681
by: RoninZA | last post by:
Hi all, My problem is this... I need to somehow communicate the completion of a workflow back to the calling application. The scenario is as follows: I have a "generic" workflow engine, utilising Windows Workflow Foundation. This part works fine, no hassles. The idea of the workflow engine is that we can integrate a workflow authorisation process easily into any application with minimal work. The problem lies in the "generic" part...
6
6432
by: Daniel Fetchinson | last post by:
Hi all, There are a number of free tools for image matching but it's not very easy to decipher the actual algorithm from the code that includes db management, GUI, etc, etc. I have my own image database and GUI so all I need is the actual algorithm preferably in pseudo code and not in the form of a research paper (from which I also found a lot but since I'm not that much interested in the actual science of image recognition this seems...
40
2372
by: Angus | last post by:
Hello I am writing a library which will write data to a user defined callback function. The function the user of my library will supply is: int (*callbackfunction)(const char*); In my libary do I create a function where user passes this callback function? How would I define the function?
0
9825
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, weíll explore What is ONU, What Is Router, ONU & Routerís main usage, and What is the difference between ONU and Router. Letís take a closer look ! Part I. Meaning of...
0
9671
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10854
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10558
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10600
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
1
7794
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Duprť who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
6981
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5651
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5829
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.