tag:blogger.com,1999:blog-255597992024-03-08T02:23:08.293+00:00Knanshon CoderMostly code related musings from the mind and fingers of Knanshon Coder.
<p>
Are you linked in? <a href="http://www.linkedin.com/in/knanshon">http://www.linkedin.com/in/knanshon</a>
</p>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.comBlogger28125tag:blogger.com,1999:blog-25559799.post-70304331649138812542008-11-16T21:14:00.004+00:002008-11-16T21:22:12.035+00:00C++: Anonymous namespacesThe C++ standard now says that the use of the <span style="font-family:courier new;">static</span> keyword to declare a file-scope varible as non-externally linkable is deprecated in favour of declaring it inside an anonymous namespace, that is, a namespace with no name. Such variables are guaranteed to be local to that file and can be named concisely without fear of clashes or polluting the global namespace.<br /><br />That is until you want to start doing unity builds. Unity building is the pre-build process of taking all the .cpp files in a C++ project and <span style="font-family:courier new;">#include</span>ing them into a single .cpp file, and then only compiling that single file. Apparently (and surprisingly) this compiles many, many times faster than using seperate files (perhaps because of reduced disc accesses?) at least it does within Visual Studio 2005.<br /><br />The main point is that you should always to endeavour to make all your variable names unique as you never know when that scope could change.Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-21050547511065232582008-11-16T21:11:00.000+00:002008-11-16T21:12:11.380+00:00ReclaimedI've just reclaimed this blog. It's been ages since I've posted and so much has happened. It is, this very day, my thirty-second birthday, which means I'm only twenty in hexadecimal.Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1155159198976349172006-08-09T22:23:00.000+01:002006-08-09T22:40:55.416+01:00Ruby : Cryptography - Substitution CypherHere's a Ruby class that can perform an encryption based on a alphabetical subsititution cypher and decrypt the resulting cyphertext using the same key. The key is provided as any alphabetical phrase. Symbols and case in the phrase are ignored and the order of each unique letter in the phrase is used to construct a new alphabet. Any remaining letters not in the phrase are added to the end of the new alphabet in ascending order.<br><br /><br><br />Once the key is set the encryption algorithm simply subsitutes the letters in the input string for the ones in the new alphabet. Decryption is the reverse operation. There are so many permutations of the 26 letter Roman alphabet that the cyphertext is hard to crack using brute force techniques. It is easier to crack using letter and word frequency analysis methods but that's beyond the scope of this blog.<br><br /><br><br />Check out the <a href="http://www.purplegoose.com/code/tutorial.htm">link</a> that inspired this work.<br><br /><br><br /><blockquote><pre><tt><br />class SubstitutionCypher<br /><br /> attr_reader :key, :cypherbet<br /> <br /> def initialize<br /><br /> # most common 2, 3 and 4 letter words could be used to <br />verify english<br /> # plain text on a brute force attack<br /><br /> @@common_english_words =<br />["of","to","in","it","is","be","as","at","so","we","he","by","o<br />r","on","do","if","me","my","up","an","go","no","us","am","the"<br />,"and","for","are","but","not","you","all","any","can","had","h<br />er","was","one","our","out","day","get","has","him","his","how"<br />,"man","new","now","old","see","two","way","who","boy","did","i<br />ts","let","put","say","she","too","use","that","with","have","t<br />his","will","your","from","they","know","want","been","good","m<br />uch","some","time","very","when","come","here","just","like","l<br />ong","make","many","more","only","over","such","take","than","t<br />hem","well","were"];<br /><br /> @key = ""<br /> @@alphabet = <br />"abcdefghijklmnopqrstuvwxyz".splitStripUniqDown<br /> @cypherbet = @@alphabet<br /> @cypherhash = makehash(@cypherbet, @@alphabet)<br /> @plainhash = makehash(@@alphabet, @cypherbet)<br /><br /> end<br /><br /> def key=(key)<br /><br /> @key = key<br /> @cypherbet = key.splitStripUniqDown<br /> @cypherbet.delete_if { |c| not @@alphabet.include?(c) <br />}<br /> @@alphabet.each { |c| @cypherbet.push(c) unless <br />@cypherbet.include?(c) }<br /> @cypherhash = makehash(@cypherbet, @@alphabet)<br /> @plainhash = makehash(@@alphabet, @cypherbet)<br /> <br /> end<br /><br /> def decode(cyphertext)<br /> <br /> substitute(cyphertext, @cypherbet, @cypherhash)<br /><br /> end<br /><br /> def encode(plaintext)<br /><br /> substitute(plaintext, @@alphabet, @plainhash)<br /> <br /> end<br /> <br /><br /> def crack(cyphertext)<br /><br /> i = 0<br /> <br /> @@alphabet.each_permutation do |alphabet|<br /><br /> @cypherbet = alphabet<br /> @cypherhash = makehash(@cypherbet, @@alphabet)<br /> @plainhash = makehash(@@alphabet, @cypherbet)<br /> plaintext = decode(cyphertext)<br /> check(plaintext)<br /> i = i + 1<br /> puts i.to_s+" : "+plaintext if i % 1000 == 0<br /> <br /> end<br /><br /> i<br /><br /> end<br /> <br /> def check(plaintext)<br /><br /> wordcount = 0<br /> <br /> plaintext.each(" ") do |word|<br /><br /> if @@common_english_words.include?(word.strip)<br /><br /> wordcount = wordcount + 1<br /><br /> end<br /><br /> end<br /> <br /> if wordcount > 1<br /> <br /> puts "Found "+wordcount.to_s+" English Words in : <br />"+plaintext<br /> <br /> end<br /> <br /> end<br /><br />private<br /><br /> def substitute(fromtext, frombet, tohash)<br /><br /> totext = ""<br /> <br /> lfromtext = fromtext.downcase<br /> <br /> lfromtext.unpack("a" * lfromtext.length).each do |c|<br /><br /> cc = c<br /> cc = tohash[c] if frombet.include?(c)<br /> totext = totext + cc<br /> <br /> end<br /><br /> totext<br /> <br /> end<br /><br /> def makehash(alphabet0, alphabet1)<br /><br /> hash = {}<br /> i = 0<br /> alphabet0.each do |c|<br /> hash[c] = alphabet1[i] <br /> i = i + 1<br /> end<br /> hash<br /><br /> end<br /><br />end<br /></pre></tt></blockquote><br /><br><br />This class uses the following String extension:<br><br /><br><br /><blockquote><pre><tt><br />class String<br /><br /> def splitStripUniqDown<br /> lkey = self.downcase<br /> lkey.unpack("a" * lkey.length).uniq.delete_if { |c| <br />c==" " }<br /> end<br /><br />end<br /></pre></tt></blockquote><br /><br><br />Here's a usage example<br><br /><br><br /><blockquote><pre><tt><br />cypher = SubstitutionCypher.new<br /><br />cypher.key = "Barry John Northern"<br />puts cypher.key<br />puts cypher.cypherbet.join<br /><br />cypher.key = "The Quick Brown Fox Jumped Over The Lazy Dogs"<br />puts cypher.key<br />puts cypher.cypherbet.join<br /><br />cypher.key = "attack"<br />puts cypher.key<br />puts cypher.cypherbet.join<br />s = cypher.encode("this is the plain text")<br />puts s<br />p = cypher.decode(s)<br />puts p<br />cypher.check(p)<br /><br />#cypher.crack(s)<br /></pre></tt></blockquote><br /><br><br />As you can see, the final call to "crack" is commented out. It will usually take a very long time to find something and then only if the rearranged letters are few and limited to the start of the alphabet.<br><br /><br>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1155155803003640752006-08-09T21:36:00.000+01:002006-08-09T21:36:43.016+01:00Ruby : PermutationsI've been interested in the field of cryptography recently after reading all of Dan Brown's excellent books, he wrote 3 crackers before the Da Vinci Code and I highly recommend them, especially Angels & Demons and Deception Point. Anyway, a brute force attack on a code simply iterates through every possible permutation of a key and decyphers the ciphertext until the resulting plaintext is intelligible. The two downsides of a brute force attack are firstly it can take many, many iterations before the correct key is found (which requires a lot of processing power) and secondly that matching the plaintext against an english dictionary every time round the loop is quite expensive. This makes for a slow algorithm. So, I guess Ruby wouldn't be the language of choice to implement something like this. However, Ruby is nice and expressive and good for learning the basic without getting bogged down with low level optimisations.<br /><br />To this end I've developed an extension to the standard Array class which simply allows you to iterate through every unique permutation of an array. It is based on a Python algorithm I googled for but it's nice to see it more elegantly expressed in Ruby...<br /><br /><pre><tt><blockquote><br />class Array<br /><br /> def each_permutation(&blockproc)<br /><br /> a = []<br /> self.each do |c|<br /> a.push(c)<br /> end<br /> n = a.length<br /> p = Array.new(n+1,0)<br /> i = 1<br /><br /> blockproc.call(a) <br /> <br /> while i < n do<br /><br /> if p[i] < i<br /><br /> j = 0<br /> j = p[i] if (i % 2) == 1<br /> t = a[j]<br /> a[j] = a[i]<br /> a[i] = t<br /><br /> p[i] = p[i] + 1<br /> i = 1<br /> <br /> blockproc.call(a) <br /><br /> else<br /><br /> p[i] = 0<br /> i = i + 1<br /> <br /> end<br /> <br /> end<br /> <br /> end<br /><br />end<br /></blockquote></pre></tt><br /><br><br /><pre><tt><blockquote><br /> ["a","b","c"].each_permutation { |arr| puts arr.join }<br /><br /> abc<br /> bac<br /> cab<br /> acb<br /> bca<br /> cba<br /><br /></blockquote></pre></tt><br /><br />Ruby's String class has a built in "crypt" method which applies a one-way cryptographic hash but I think it's nice to develop something new. I'll post more about the simple transposition encryption/decryption and crack algorithms that I developed soon.Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1154588856098103222006-08-03T08:03:00.000+01:002006-08-03T08:07:36.106+01:00Ruby : Tetris Screenshot<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://photos1.blogger.com/blogger/1386/2673/1600/Clip_5.gif"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;" src="http://photos1.blogger.com/blogger/1386/2673/320/Clip_5.png" border="0" alt="" /></a><br /><br />My lastest version of Tetris and information about it can be found <a href="http://shatteredforum.hastilymade.com/viewtopic.php?p=292#292">here</a>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1153834650227437132006-07-25T14:30:00.000+01:002006-07-25T14:37:30.306+01:00Ruby : TetrisIf you've heard what Ruby on Rails has done for Web Development you may be interested in Shattered. It's like Ruby on Rails for games development. It's only at version 0.3.2 at the moment, early days but it looks promising already. I'm investigating it with a view of using it as a rapid prototyping tool for more avant-garde game designs.<br /><br />Everything you need to know can be found on the <a href="http://weblog.shatteredruby.com/">Shattered Weblog</a> which has some very useful links in the top right hand corner.<br /><br />I've written a simple tetris game using it to limber up :) I'm currently in the process of writing a little tutorial on the Shattered Wiki to help people out. I found it quite hard to get going at first due to the lack of examples and documentation. Saying that though, if you're prepared to look through the Shattered sources and reference documentation it's not too hard to find out what's going on and it shows some very nice likke Ruby tricks as well.<br /><br /><a href="http://wiki.shatteredruby.com/index.php?title=Tetris">Check it out</a>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1152105988798465132006-07-05T14:25:00.000+01:002006-07-05T14:30:31.806+01:00Ruby : Pretty CodeI've been through many beginners tutorials for Ruby and I must say I really like this language. I think it's going to be very useful. The Pragmatic Programmers - Dave Thomas and Andy Hunt - give some good advice to learning a new language ... they say you must ask the question, "How will I know when I'm done?". I decided that my first "bout" of learning would be concluded when I had written my own program to prettify the text files I write for this blog! Usually I have to search and replace certain characters, manually add html tags for line breaks and code snippets, ensure that any preformatted line doesn't exceed 62 characters ... in short, a bit of a chore.<br><br /><br><br />So here's the Ruby blog prettifier ... and of course, this blog post is the first to have been run through it! :)<br><br /><br><br /><blockquote><pre><tt><br />class String<br /><br />def subAfter str, ext<br /> self[0..self.index(str)-1]+"."+ext<br />end<br /><br />end<br /><br />$column = 62<br />filename = ARGV[0].to_s<br /><br />puts "Processing "+filename+"...\n"<br /><br />File.open(filename, "r") do |file|<br /><br /> outFile = File.new(filename.subAfter(".","htm"), "w")<br /><br /> code = false;<br /> <br /> file.each_line do |line|<br /> <br /> if line.chomp == "@@@"<br /><br /> if code<br /> outFile.puts "</pre></tt></blockquote>"<br /> else<br /> outFile.puts "<blockquote><pre><tt>" <br /> end<br /><br /> code = !code;<br /> <br /> else<br /> <br /> if code<br /> <br /> long = line<br /> line = ""<br /><br /> while long.length > $column<br /><br /> space = long[0..$column].rindex(" ")<br /> <br /> if space == nil<br /> space = $column<br /> end<br /> <br /> line += long[0..space]+"\n"<br /> long = long[space+1..-1]<br /> <br /> end<br /><br /> line += long<br /> <br /> <br /> line.gsub!(/</,"<")<br /> line.gsub!(/>/,">")<br /> else<br /> line.gsub!(/\n\r|\n|\r/, "<br>") <br /> end<br /><br /> outFile.puts line<br /> <br /> end<br /> <br /> end<br /> <br /> outFile.close()<br /><br /># This is a really long comment which I've added to show you <br />how the code prettifier neatly looks for the last space before <br />col 80 and splits the line :) <br />#_This_is_another_really_long_comment_which_I've_added_to_show_<br />you_how_the_code_prettifier_simply_cuts_the_line_if_there_are_n<br />o_spaces!<br /><br />end<br /></pre></tt></blockquote>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1152014305432875192006-07-04T12:54:00.000+01:002006-07-04T14:21:59.400+01:00Ruby : to_eng Integer class extensionHere's the "English Number" method implemented in a more useful form; as an extension to the Integer class. It now works with negative numbers to. The usage is simple.<br /><br><br /><blockquote><br /><pre><tt><br />puts 0.to_eng(0) # arg is 0 for British, 1 for American<br />puts 12.to_eng(1)<br />puts -54.to_eng(1)<br />puts (10**600).to_eng(0)<br /></pre></tt><br /></blockquote><br /><br><br /><blockquote><br /><pre><tt><br /># extend the Integer class with a "to english" method<br /><br />class Integer<br /><br />def to_eng scale<br /><br /> number = self.abs<br /><br /> if number == 0<br /> return 'zero'<br /> end<br /><br /> # ... code removed see previous post<br /><br /> if write > 0<br /> <br /> exps = write.to_eng(scale)<br /><br /> # ...<br /> <br /> end<br /># ...<br /><br /> if self<0<br /> numString = "Minus " + numString<br /> end<br /><br /> # Now we just return "numString"...<br /> numString<br /><br />end<br /><br />end<br /></pre></tt><br /></blockquote>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1152007935732739002006-07-04T10:56:00.000+01:002006-07-04T11:24:54.276+01:00Ruby : English NumbersWell, it's been almost a month since my last post and what a busy month it's been! I started to write an article about a wrapper I had written for C++ iostreams that automatically closes them on scope exit until I found out that they do that anyway!! Talk about redundant levels of abstraction! <br><br />I've also found myself over-using templates recently, I mean they're fun to use but they tend to obfusticate code and generate hard-to-read compiler errors. I had this realisation after discovering Ruby - one of the easiest, most concise and powerful "scripting" languages I've ever had the pleasure to use. Check it out <a href="http://www.rubycentral.com/">www.rubycentral.com</a>. I've been following a great article called <a href="http://pine.fm/LearnToProgram/">Learn To Program</a> (Ruby), a precursor to the <a href="http://www.pragmaticprogrammer.com/titles/fr_ltp/">book</a> by the same name.<br /><br />On <a href = "http://pine.fm/LearnToProgram/?Chapter=08">Chapter 8</a> there's a nifty <b>English Number Program</b> example that takes any positive integer and returns the english name of that number. It's quite limited and only works properly between 0-999. The author sets an exersize to make it work for thousands and millions and asks, how high can you go? My answer? Is that British Scale or American Scale? Either? Ok, well, in either case I can go as high as 10^600, which is the largest number-word below <i>googolplex</i> which is too large to include anyway :)<br><br /><br />Here's my first Ruby program (based on the original example), enjoy ... for an example of conciseness see the code I wrote to sort the array of name/exponent pairs by exponent ...<br><br /><br /><pre><tt><blockquote><br />def englishNumber number, scale<br /> if number < 0 # No negative numbers.<br /> return 'Please enter a number that isn\'t negative.'<br /> end<br /> if number == 0<br /> return 'zero'<br /> end<br /><br /> # check scale:<br /> <br /> if scale<0 or scale>1<br /> return 'scale out of range'<br /> end <br /> <br /> # valid scales: <br /> # 0) British (long scale) <br /> # 1) American (short scale)<br /> <br /> numString = '' # This is the string we will return.<br /> <br /> onesPlace = ['one', 'two', 'three', 'four', <br /> 'five', 'six', 'seven', 'eight', 'nine']<br /> tensPlace = ['ten', 'twenty', 'thirty', 'forty', 'fifty',<br /> 'sixty', 'seventy', 'eighty', 'ninety']<br /> teenagers = ['eleven', 'twelve', 'thirteen', 'fourteen', <br /> 'fifteen', 'sixteen', 'seventeen', 'eighteen', <br /> 'nineteen']<br /> <br /> # short scale words<br /> <br /> expTens = [['b'],['tr'],['quadr'],['quint'],['sext'],<br /> ['sept'],['oct'],['non'],['dec'],['undec'],<br /> ['duodec'],['tredec'],['quattuordec'],['quindec'],<br /> ['sexdec'],['septendec'],<br /> ['octodec'],['novemdec'],['vigint']]<br /> <br /> # add short scale exponents and append "illion"'s!<br /><br /> exp = 9<br /> <br /> expTens.each do |expTen|<br /> <br /> expTen[0] = expTen[0] + 'illion';<br /> expTen.push(exp)<br /> exp = exp + 3<br /> <br /> end<br /> <br /> if scale == 0 # British (long scale) <br /> # not using uncommon "milliard" (10**9)<br /> <br /> # convert exponents to long scale<br /> <br /> expTens.each do |expTen|<br /><br /> expTen[1] = (expTen[1] - 3) * 2 <br /> <br /> end<br /> <br /> end<br /> <br /> # add words and exponents common to both scales<br /> <br /> expTens = [ ['hundred', 2], ['thousand', 3], ['million', 6] ] <br /> + expTens<br /> expTens = expTens + [ ['googol', 100], ['centillion', 600] ]<br /><br /> # rational.rb says googolplex i.e. 10**(10**100) => Infinity<br /> <br /> # unfortunatly now after the possible conversion to British <br /> # long scale the expTens array is not in order. A googol's <br /> # exponent is 100 which means it should be between <br /> # sexdecillion and septendecillion.<br /><br /> # let's simply sort the array every time in case other such <br /> # ordering errors occur<br /><br /> expTens.sort! { |x, y| x[1]<=>y[1] } # how easy was that! :)<br /> <br /> left = number<br /><br /> # handle hundreds and above<br /><br /> expTens.reverse.each do |expTen|<br /><br /> value = 10**expTen[1]<br /> write = left/value<br /> left = left - write*value<br /> <br /> if write > 0<br /> <br /> exps = englishNumber(write, scale)<br /> numString = numString + exps + ' ' + expTen[0]<br /><br /> if left > 0<br /><br /> if left < 100<br /> numString = numString + ' and '<br /> elsif<br /> numString = numString + ', '<br /> end<br /> <br /> end<br /> <br /> end<br /> <br /> end<br /><br /> # handle teens<br /> <br /> write = left/10 # How many tens left to write out?<br /> left = left - write*10 # Subtract off those tens.<br /> <br /> if write > 0<br /> if ((write == 1) and (left > 0))<br /> # Since we can't write "tenty-two" instead of "twelve",<br /> # we have to make a special exception for these.<br /> numString = numString + teenagers[left-1]<br /> # The "-1" is because teenagers[3] is 'fourteen', <br /> # not 'thirteen'.<br /> <br /> # Since we took care of the digit in the ones place<br /> # already, we have nothing left to write.<br /> left = 0<br /> else<br /> numString = numString + tensPlace[write-1]<br /> # The "-1" is because tensPlace[3] is 'forty', <br /> # not 'thirty'.<br /> end<br /> <br /> if left > 0<br /> # So we don't write 'sixtyfour'...<br /> numString = numString + '-'<br /> end<br /> end<br /> <br /> # handle ones<br /> <br /> write = left # How many ones left to write out?<br /> left = 0 # Subtract off those ones.<br /> <br /> if write > 0<br /> numString = numString + onesPlace[write-1]<br /> # The "-1" is because onesPlace[3] is 'four', not 'three'.<br /> end<br /> <br /> # Now we just return "numString"...<br /> numString<br />end<br /><br />def formatEnglishNumber value, scale<br /> value.to_s+" = "+englishNumber( value, scale)<br />end<br /><br />def formatEnglishNumberExp exp, scale<br /> "10**"+exp.to_s+" = "+englishNumber(10**exp, scale)<br />end<br /><br />scale = -1;<br />while scale<0 or scale>1<br /> puts "Use 0) British Long Scale 1) American Short Scale?"<br /> scale = gets.chomp.to_i<br />end<br /><br />puts "Some Numbers:"<br />puts<br />puts formatEnglishNumber( 0, scale)<br />puts formatEnglishNumber( 9, scale)<br />puts formatEnglishNumber( 10, scale)<br />puts formatEnglishNumber( 11, scale)<br />puts formatEnglishNumber( 17, scale)<br />puts formatEnglishNumber( 32, scale)<br />puts formatEnglishNumber( 88, scale)<br />puts formatEnglishNumber( 99, scale)<br />puts formatEnglishNumber(100, scale)<br />puts formatEnglishNumber(101, scale)<br />puts formatEnglishNumber(234, scale)<br />puts formatEnglishNumber(1000, scale)<br />puts formatEnglishNumber(3211, scale)<br />puts formatEnglishNumber(10000, scale)<br />puts formatEnglishNumber(100000, scale)<br />puts formatEnglishNumber(999999, scale)<br /><br />puts<br />puts "Let's test the scale: "<br />puts<br /><br />scalemax = 64;<br />if scale == 0<br /> scalemax = 121<br />end<br /><br />scalemax.times do |exp|<br /> puts formatEnglishNumberExp(exp, scale)<br />end<br /><br />puts<br />puts "Some bigger numbers!"<br />puts<br />puts formatEnglishNumber(100098765432134, scale)<br />puts formatEnglishNumber(2348723948732948723, scale)<br />puts formatEnglishNumber(2342342324100098765432134, scale)<br />puts formatEnglishNumber(124523598054213453230980329480, scale)<br />puts formatEnglishNumberExp(100, scale)<br />puts formatEnglishNumberExp(600, scale)<br /># googolplex is too big!!<br />#puts formatEnglishNumberExp(10**100, scale) <br /><br />puts<br />puts "Press Enter To Quit"<br />gets<br /></blockquote></pre></tt>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com1tag:blogger.com,1999:blog-25559799.post-1149580930400616082006-06-06T08:45:00.000+01:002006-06-06T09:02:11.026+01:00C# : Localization and Web ServicesI've recently moved house, what hard work that is! We're pretty much back to normal now so hopefully I will be blogging about some more coding topics that I've found interesting. I've recently been developing a small WinForms application in C#. It needed to be localized for a number of languages and I was pleasantly surprised at how easy this was. <br><br />If you set the "Localizable" property of your main form or custom control to true you can then set the language. Any changes made for each selected language (the pull-down contains all that are available through the OS) are writting to a seperate .resx file for that language, so for example, Form1.resx is the default language UI and Form1.fr.resx is the French version. Subsequent language resx's only contain the changes from the default file. The beauty of the entire UI resource file being customizable and not just a string table is that you can change the layout of controls to accomodate longer strings etc. <br><br />One annoying thing I did encounter was that if you edit the .resx file by hand in the VS .NET editor (you'll have to Show All Files in the Solution Explorer first) then any additions you make (i.e. for Dialog Messages etc.) will be overwritten by the IDE if you make changes in that.<br /><br><br />It's also very, very easy to consume a Web Service in VS .NET. It's simply a matter of adding a "Web Reference" to the project in the Solution Explorer, you enter the URL and it is automatically wrapped in a namespace/class for the language you are developing in. It can then be simply instantiated and used. I actually wrote a COM object in pure C++ that uses a web service and is in turn used by a C# application and through script!<br /><br><br />Cross-language development is fun when things are decoupled like this but I find that developing software using Managed C++ with a combination of pure C++ APIs and Managed Types can be a bit of a headache. The Garbage Collector obviously doesn't let managed types own un-managed ones etc. so you have to do your own memory management on them. When all's said and done, if I'm using .NET I'd rather program in C# .. a language specifically designed and fit for purpose rather than Managed C++ which has been (very ingeniously) hacked to work for the .NET runtime.Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com1tag:blogger.com,1999:blog-25559799.post-1147265351292697782006-05-10T13:48:00.000+01:002006-05-10T19:35:36.113+01:00C++ : Meta Programming : Fibonacci and PhiIn this blog I explore the relationship between the Fibonacci sequence and the Golden Ratio <i>Phi</i>. I write a meta program to calculate the Fibonacci sequence at compile time and use the last two elements in the sequence to calculate Phi.<br /><br><br />Fibonacci Sequence:<br /><pre><tt><blockquote><br /> 1 1 2 3 5 8 13 21 34 ...<br /><br /> N N + N<br /> i = i-1 i-2<br /> <br /></blockquote></pre></tt><br />The following expression tends towards Phi as <b>i</b> increases:<br /><pre><tt><blockquote><br /> N / N<br /> i i-1<br /><br /></blockquote></pre></tt><br />Another definition of Phi:<br /><pre><tt><blockquote><br />Phi * Phi = Phi + 1<br /><br /></blockquote></pre></tt><br />Which rearranged proves that Phi is 1 + it's reciprocal, hinting at a much simpler algorithm to calculate it than the one we have here based on this equation:<br /><pre><tt><blockquote><br />Phi = 1 + 1/Phi<br /><br /></blockquote></pre></tt><br />This could be expressed as a recursive function and we can start with any number, except 0 or -1, to tend towards Phi, 1 will do though.<br><br />The following link explores the interesting mathematical properties of Phi<br /><br><br /><a href="http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/phi.html#simpledef">http://www.mcs.surrey.ac.uk/Personal/R.Knott/<br>Fibonacci/phi.html#simpledef</a><br /><br><br />Now time for some code, here's a runtime recursive function that calculates the last two numbers in the Fibonacci sequence for any given index in the sequence <b>i</b>:<br /><pre><tt><blockquote><br />#define DO_OUTPUT<br /><br />typedef unsigned long long ulong;<br />typedef std::pair<ulong, ulong> tuple;<br /><br />// Fibonacci<br />// Run-time Recursive Function<br />void GetFibonacciTupleImpl(unsigned int i, tuple &result)<br />{<br /> if(i>0)<br /> { <br /> result.second += result.first;<br /> result.first = result.second - result.first;<br />#ifdef DO_OUTPUT<br /> std::cerr << result.second << " ";<br />#endif <br /> if(result.second>result.first) // wrapping guard<br /> GetFibonacciTupleImpl(i-1, result);<br /> else // store recursive level<br /> result.first = result.second = i;<br /> <br /> }<br />}<br /><br />void GetFibonacciTuple(unsigned int i, tuple &result)<br />{<br /> result.first = 1;<br /> result.second = 1;<br />#ifdef DO_OUTPUT<br /> std::cerr << "1 1 ";<br />#endif<br /> GetFibonacciTupleImpl(i, result);<br />#ifdef DO_OUTPUT<br /> if(result.first==result.second && result.second>1)<br /> std::cerr << "\nwrapping occured at i=" <br /> << (i-result.first+2) << "\n";<br />#endif<br />}<br /><br /></blockquote></pre></tt><br />Here's a meta-programming solution for the exact same thing, only all calculated at compile-time!<br /><pre><tt><blockquote><br />template<int I><br />struct Fibonacci<br />{<br /> enum { value = Fibonacci<I-1>::value +<br /> Fibonacci<I-2>::value };<br />};<br /><br />template<><br />struct Fibonacci<1><br />{<br /> enum { value = 1 };<br />};<br /><br /><br />template<><br />struct Fibonacci<0><br />{<br /> enum { value = 1 };<br />};<br /><br />template<int I, typename T><br />struct FibonacciTuple<br />{<br /> enum {<br /> first = Fibonacci<I-1>::value,<br /> second= Fibonacci<I>::value<br /> };<br /> <br /> // run time part as not integral ...<br /> static const T getRatio()<br /> {<br /> return (T)second / (T)first;<br /> }<br />};<br /><br /></blockquote></pre></tt><br />Now this only works up to a point. If you try to compile <tt>Golden::FibonacciTuple<47,double>::getRatio()</tt> under g++ 3.4.4 you get a compiler error: <b>Integer Overflow in Expression</b>. Also the results are only correct up to <tt>Golden::FibonacciTuple<45,double>::getRatio()</tt>. Initially I surmised this was due to some compiler recursion-stack related problem but after I'd actaully read the compiler output! I realised the error occured on the line where the enum value is evaluated (using the + operator). If it were a compiler stack-depth problem then something like this migth have alleviated the problem:<br /><pre><tt><blockquote><br />template<ulong I><br />struct Fibonacci<br />{<br /> ...<br />};<br /><br /></blockquote></pre></tt><br />but the error lies with the face that it looks like the compiler uses a signed integer to store enum values. Why signed? Well the runtime version uses an unsigned int to store the Fibonacci sequence value and it breaks down after 90 recursions! (i.e. twice as many).<br><br />Of course this is only a bit of fun and isn't the most efficient way of calculating Phi. Initially I thought perhaps I could write a way of statically storing the value of Phi in a program without defining it as a literal value, i.e. <br /><pre><tt><blockquote><br />static const float Phi = 1.618....;<br /><br /></blockquote></pre></tt><br />However, firstly there's the enum problem and secondly (and this is a related problem) we can only use integral values at compile-time. This is illustrated by the following meta program:<br /><pre><tt><blockquote><br />// Cannot get Phi using the reciprocal method<br />// since only integral numbers are used in enums!<br /><br />template<int I><br />struct Phi<br />{<br /> enum { value = 1 + 1/Phi<I-1>::value };<br />};<br /><br />template<><br />struct Phi<0><br />{<br /> enum { value = 1 };<br />};<br /><br /></blockquote></pre></tt><br />This is a flawed implementation of the reciprocal method of calculating Phi as mentioned above. This obviously requires less work than the Fibonacci method but isn't quite as interesting from a mathematical point of view.<br><br />In conclusion then, as well as exploring the fascinating relationship between the Fibonacci Sequence and Phi, we've found out about some limitations of what we can and can't do a compile-time and managed to deduce the g++ 3.4.4 uses an int to store an enum values!<br /><br>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com1tag:blogger.com,1999:blog-25559799.post-1147124513017292382006-05-08T22:02:00.000+01:002006-05-08T22:52:00.593+01:00C++ : Exploring Sorting Part IVLet's start with the full code for the promised generic quicksort implementation that is my attempt at an "exercise for the reader" from an Alexandrescu article mentioned previously<br /><pre><tt><blockquote><br />template<class Iter><br />void sort(Iter left, Iter right)<br />{<br /> // make larger to invoke insertion sort sooner<br /> enum { threshold = 56 }; <br /> while(right-left>1)<br /> {<br /> // do insertion sort on range<br /> if(right-left<=threshold) <br /> {<br /> Bannister::insertionSort(left, right);<br /> return; // done sorting range<br /> }<br /> else // do quicksort on range<br /> {<br /> const std::pair<Iter,Iter> pivot = <br /> Bannister::partition(<br /> left, right, <br /> *Bannister::selectRandomPivot(<br /> left, right));<br /> if (left < pivot.first)<br /> Bannister::sort(left, pivot.first);<br /> if (right > pivot.second)<br /> left = pivot.second;<br /> else<br /> break;<br /> }<br /> }<br />}<br /><br /></blockquote></pre></tt><br />Quite different from the original C code I posted in my last blog! I'm sure you could have made that function generic using the same method as shown with the bubblesort, it's not worth going into detail again. The above algorithm uses a quicksort for arrays over 56 elements long, otherwise it uses an <b><a href="http://linux.wku.edu/~lamonml/algor/sort/insertion.html">insertion sort</b></a> which is another fast method. It's a matter of testing to get the best speed benefits, something I have as yet to write a test framework for. Now to explain the quicksort part of the algorithm. The selecting of a pivot value and partitioning of the array passed to the <tt>sort</tt> function is deferred to two functions for clarity and to make it easier to tinker with the algorithm. The sort function itself has been partially converted to an iterative solution to try and alleviate the speed costs of recursion.<br><br />The pivot value is chosen randomly to help prevent the "worst-case scenario" of always choosing the lowest number around which to partition the array, which is always the case when sorting an array which is already ordered using the first value as the pivot. Another speed increase is achieved by uses Alexandrescus "fit pivot" technique which is based on the more well-known "fat-pivot". The "fat pivot" algorithm partitions the array into 3, not 2, sub arrays. The 3rd contains all occurences of the pivot value and places this in the middle of the other two (which contain values lower and values higher than the pivot respectively). This reduces the number of partitioning steps needed when there are long runs of equal numbers. However there is an overhead cost in doing the partitioning. The "fit pivot" algorithm will simply apply the normal "two partition" algorithm to an array but carry on moving the right pointer to the left and vice versa until numbers are found which are not equal to the pivot value. This way, if there is a run of pivot-equal numbers in the middle of the array, it will be kept there, not passed to the quicksort again and the resulting two partitions will be smaller, increasing the speed in those situations at no extra cost. Here are the two functions (including a more standard selectFirstPivot).<br /><pre><tt><blockquote><br />template<class Iter><br />Iter selectFirstPivot(Iter left, Iter right)<br />{<br /> return left;<br />}<br /><br />template<class Iter><br />Iter selectRandomPivot(Iter left, Iter right)<br />{<br /> long int index = Bannister::rand(0, right-left);<br /> return left + index;<br />}<br /><br />template<class I0, class I1, class T><br />std::pair<I1,I0> partition(<br /> I0 left, I1 right, T pivot)<br />{<br /> --right;<br /> while (left < right)<br /> {<br /> while ((*right >= pivot) && (left < right))<br /> --right;<br /> if (left != right)<br /> {<br /> *left = *right;<br /> ++left;<br /> }<br /> while ((*left <= pivot) && (left < right))<br /> ++left;<br /> if (left != right)<br /> {<br /> *right = *left;<br /> --right;<br /> }<br /> }<br /> *left = pivot;<br /> // all numbers in-between will be equal<br /> return std::make_pair(right, left+1); <br />}<br /><br /></blockquote></pre></tt><br />Note, I've put my functions in a namespace called "Bannister" (rubbish name I know, it's named after Roger Bannister, the first man to run the 4 minute mile). Here's the insertion sort algorithm.<br /><pre><tt><blockquote><br />template<class Iter, class T><br />void insertionSort(Iter left, Iter right, T) <br />// T unused, only type is needed<br />{<br /> Iter i, j;<br /> T index;<br /><br /> for (i=left+1; i != right; ++i)<br /> {<br /> index = *i;<br /> j = i;<br /> while ((j > left) && (*(j-1) > index))<br /> {<br /> *j = *(j-1);<br /> --j;<br /> }<br /> *j = index;<br /> }<br />}<br /><br />template<class Iter><br />void insertionSort(Iter left, Iter right)<br />{<br /> // dereference left to deduce type of iterator<br /> Bannister::insertionSort(left, right, *left); <br />}<br /><br /></blockquote></pre></tt><br />And finally I'll include the fast pseudo-random function I found to calculate the random pivot.<br /><pre><tt><blockquote><br />// Park-Miller "minimal standard" 31 bit <br />// pseudo-random number generator<br />// implemented with David G. Carta's <br />// optimisation: with 32 bit math and<br />// without division..<br /><br />long unsigned int rand31()<br />{<br /> static long unsigned int seed = 16807;<br /> long unsigned int hi, lo;<br /><br /> lo = 16807 * (seed & 0xFFFF);<br /> hi = 16807 * (seed >> 16);<br /><br /> lo += (hi & 0x7FFF) << 16;<br /> lo += hi >> 15;<br /><br /> if(lo>0x7FFFFFFF) lo -= 0x7FFFFFFF;<br /><br /> return (seed=(long)lo);<br />}<br /><br />long int rand(long int lo, long int hi)<br />{<br /> return (long int)(rand31() % (hi-lo)) + lo; <br />}<br /><br /></blockquote></pre></tt><br />I should include some examples of using these functions as well ... (I really am letting the code speak for itself in this blog)... <i>disclaimer: really bad test harness with no error-checking!!</i><br /><pre><tt><blockquote><br />#include <iostream><br />#include <cstdlib><br />#include <ctime><br />#include <limits><br />#include <vector><br />// previous code goes in here...<br />#include "sort.h"<br /><br />template<class Iter><br />void output(Iter left, Iter right)<br />{<br /> for(Iter it=left; it!=right; ++it)<br /> std::cerr << *it << " ";<br /> std::cerr << std::endl;<br />}<br /><br />template<class Iter><br />Iter find_unsorted(Iter left, Iter right)<br />{<br /> for(Iter it=left+1; it!=right; ++it)<br /> {<br /> if(*it<*(it-1))<br /> {<br /> return it;<br /> }<br /> }<br /> return right;<br />}<br /><br />int unit(void)<br />{<br /> const int size = 12;<br /> int arr[] = {4, 0, 5, 7, 2, 2, 2, 2, 2, 1, 78, 4};<br /> float arf[] = {4.2f, 0.1f, 5.3f, 7.8f, 8.02f, <br /> 2.3f, 45.9f, 2.1f, 2.1f, 1.2f, <br /> 78.0f, 4.2f};<br /> int arr[] = {0, 7, 1, 8, 2, 9, <br /> 3, 10, 4, 11, 5, 6};<br /> typedef std::vector<char> char_array_t;<br /> char_array_t arc;<br /> arc.push_back('k');<br /> arc.push_back('c');<br /> arc.push_back('e');<br /> arc.push_back('f');<br /> arc.push_back('b');<br /> arc.push_back('g');<br /> arc.push_back('i');<br /> arc.push_back('h');<br /> arc.push_back('l');<br /> arc.push_back('d');<br /> arc.push_back('j');<br /> arc.push_back('a');<br /> <br /> output(arr, arr+size);<br /> bubbleSortT<int*>(arr, size);<br /> Bannister::sort(arr, arr+size);<br /> output(arr, arr+size);<br /> <br /> output(arf, arf+size);<br /> Bannister::insertionSort(arf, arf+size);<br /> Bannister::sort(arf, arf+size);<br /> output(arf, arf+size);<br /><br /> output(arc.begin(), arc.end());<br /> Bannister::sort(arc.begin(), arc.end());<br /> Bannister::insertionSort(arc.begin(), arc.end());<br /> output(arc.begin(), arc.end());<br /><br /> return 1;<br />}<br /><br />int main(int argc, char **argv)<br />{<br /> if(argc==1)<br /> {<br /> return unit();<br /> }<br /> <br /> typedef std::vector<char> char_array_t;<br /> char_array_t arc;<br /><br /> // Kilobytes of characters to sort<br /> const int mem_size_bytes = 1024 * atoi(argv[1]); <br /> for(int i=0; i<mem_size_bytes; ++i)<br /> {<br /> arc.push_back(Bannister::rand('A', 'Z'));<br /> }<br /> <br /> switch(argv[2][0])<br /> {<br /> case 'b':<br /> std::cerr << "bubble sorting array...\n";<br /> bubbleSort(arc.begin(), arc.end());<br /> break;<br /> case 'q':<br /> std::cerr << "Bannister::sorting array... "<br /> "(hybrid quicksort/insertion sort "<br /> "with random fit pivot)\n";<br /> Bannister::sort(arc.begin(), arc.end());<br /> break;<br /> case 'i':<br /> std::cerr << "insertion sorting array...\n";<br /> Bannister::insertionSort(<br /> arc.begin(), arc.end());<br /> break;<br /> case 's':<br /> std::cerr << "std::sorting array...\n";<br /> std::sort(arc.begin(), arc.end());<br /> break;<br /> default:<br /> break;<br /> }<br /> <br /> char_array_t::iterator it = <br /> find_unsorted(<br /> arc.begin(), arc.end());<br /> if(it!=arc.end())<br /> {<br /> std::cerr << "Unsorted! Error!\n" << std::endl;<br /> output(it-10, it+10);<br /> //output(arc.begin(), arc.end());<br /> }<br /><br /> return 1;<br />}<br /><br /></blockquote></pre></tt><br />Now I propose an exercise for the reader... write some proper test code to automatically time and compare the results using different sorting methods.<br><br />Some simple timing tests I've done (using <b>>time ./sort.exe</b> on the bash command line under Cygwin) show that the <tt>Banniser::sort</tt> is many times quicker than a bubble sort or even an insertion sort with large arrays. It doesn't hold a candle to <tt>std::sort</tt> though. I suspect the <tt>std::sort</tt> implementation uses some really good platform-specific tricks, maybe implementing some inner loops in assembly. Anyone who could attempt modifying this code to go even faster is more than welcome!<br>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1146747179724678812006-05-04T13:50:00.000+01:002006-05-04T14:09:06.246+01:00Haskell : Getting StartedHere are a couple of links for anyone who wants to get started using Haskell. These are both interpreter implementations of the language but are good for getting started.<br /><br /><a href="http://haskell.org/hugs/">http://haskell.org/hugs/</a><br /><br /><i>Hugs 98 is a functional programming system based on Haskell 98, the de facto standard for non-strict functional programming languages. Hugs 98 provides an almost complete implementation of Haskell 98.</i><br /><br /><a href="http://www-users.cs.york.ac.uk/~ndm/projects/winhugs.php">http://www-users.cs.york.ac.uk/~ndm/projects/winhugs.php</a><br /><br /><i>WinHugs is the Windows user interface to Hugs. In addition to all of the Hugs features, it includes type browsers and heirarchical constraint views. WinHugs should run on any version of Windows since 95, i.e. 95/98/ME/NT/2K/XP.</i>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1146686390087628302006-05-03T20:53:00.000+01:002006-05-04T07:54:29.276+01:00Haskell : QuickSort in 2 LinesAs an aside to the series of blogs on sorting and in an effort to ensure you that this is not a C++ only blog here's how you can express the quick sort algorithm in <a href="http://www.haskell.org/haskellwiki/Haskell">haskell</a><br /><pre><tt><blockquote><br />qsort [] = []<br />qsort (x:xs) = qsort (filter (< x) xs) ++ [x]<br /> ++ qsort (filter (>= x) xs)<br /><br /></blockquote></pre></tt><br />Compare this to the C example below! Haskell is a high-level, functional programming language. It is definitely worth a closer look, even if you don't use it to develop anything it will offer a different mindset that may help you approach and solve problems from a different angle.Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1146685867796665302006-05-03T20:47:00.000+01:002006-05-03T20:52:44.626+01:00Programming Quote of the Month"The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds castles in the air, from air, creating by exertion of the imagination. Few media of creation are so flexible, so easy to polish and rework, so readily capable of realizing grand conceptual structures."<br><br><i>- <a href="http://www.softwarequotes.com/ShowQuotes.asp?ID=556&Name=Brooks,_Fred&Type=Q">Frederick P. Brooks</a>, "The Mythical Man-Month: Essays on Software Engineering, Anniversary Edition (2nd Edition)" by Frederick P. Brooks , ISBN: 0201835959,<br />page: 7-8</i><br><br><i><b><a href="http://www.softwarequotes.com/">www.softwarequotes.com</a></b></i>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1146326157875307662006-04-29T16:27:00.000+01:002006-04-29T17:00:58.233+01:00C++ : Exploring Sorting part IIII promised to talk about faster sorting algorithms and one of the fastest is the appropriately named <b>quicksort</b>. The algorithm was devised by British computer scientist in 1962! (I told you sorting was an age-old problem). His name is <a href="http://en.wikipedia.org/wiki/C._A._R._Hoare">Charles Antony Richard Hoare</a> his original paper is entitled <b>C. A. R. Hoare. "Quicksort," Computer Journal, 1962, 5, p.p. 10-15.</b> and is apparently still the most cited paper on the subject.<br><br>Anyway, I read an interesting <a href="http://www.ddj.com/dept/cpp/184403848">article</a> on searching (of which sorting is part of the solution) by Alexandrescu and the subject of this and the next blog is basically the good old "exercise for the reader" which I've done. I'm not going to claim that mine is the best or fastest implementation. In fact it performs alot slower the <tt>std::sort</tt> but there's always room for improvement and it's a good learning exercise. I have yet to completely finish tinkering with it so any suggestions would be welcome. I'd like to remove all recursion and make as many other speed improvements as possible. I also need to write a better testing framework with some proper profiling of the function. But anyway... here's the original quicksort algorithm expressed as a simple, non-generic function in C taken from <a href="http://linux.wku.edu/~lamonml/index.html">Michael Lamont</a> whose knowledge base pages have <a href="http://linux.wku.edu/~lamonml/algor/sort/">lots of nicely expressed C implementations of sorting algorithms with explanations and metrics</a><br /><pre><tt><br /><blockquote><br />void quickSort(int numbers[], int array_size)<br />{<br /> q_sort(numbers, 0, array_size - 1);<br />}<br /><br /><br />void q_sort(int numbers[], int left, int right)<br />{<br /> int pivot, l_hold, r_hold;<br /><br /> l_hold = left;<br /> r_hold = right;<br /> pivot = numbers[left];<br /> while (left < right)<br /> {<br /> while ((numbers[right] >= pivot) && (left < right))<br /> right--;<br /> if (left != right)<br /> {<br /> numbers[left] = numbers[right];<br /> left++;<br /> }<br /> while ((numbers[left] <= pivot) && (left < right))<br /> left++;<br /> if (left != right)<br /> {<br /> numbers[right] = numbers[left];<br /> right--;<br /> }<br /> }<br /> numbers[left] = pivot;<br /> pivot = left;<br /> left = l_hold;<br /> right = r_hold;<br /> if (left < pivot)<br /> q_sort(numbers, left, pivot-1);<br /> if (right > pivot)<br /> q_sort(numbers, pivot+1, right);<br />}<br /><br /></blockquote><br /></pre></tt><br />In part III we'll take this, make it generic as we did with the bubbleSort in Part II and use the ideas put forward by Alexandrescu to improve it's speed even further.<br><br>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1146257101706152592006-04-28T20:47:00.000+01:002006-05-08T08:32:13.996+01:00C++ : Exploring Sorting part IIIn order to make our bubble sort function more generic (an thereby more useful) we could give it a function signature something along these lines:<br /><pre><tt><br /><blockquote><br />template<class T><br />void bubbleSort(T numbers[], size_t size);<br /><br /></blockquote><br /></pre></tt><br />This would mean we could call the function with an array of any type and the compiler would deduct the type to instantiate the function using the first parameter i.e. <br /><pre><tt><br /><blockquote><br />float f[4] = {1.1f,0.2f,-2.3f,0.3f};<br />int i[4] = {6,3,1,5};<br />char *s = "zyxw"; // nicer syntax than...<br />//char s[4] = {'z','y','x','w'};<br /><br />bubbleSort(f,4); // uses <b>float</b><br />bubbleSort(i,4); // uses <b>int</b><br />bubbleSort(s,4); // uses <b>char</b> <br /><br /></pre></tt><br /></blockquote><br />With the wonders of (take a deep breath) <i>explicit template function argument specification</i> we can do this now too...<br /><pre><tt><br /><blockquote><br />bubbleSort<double*>(f,4); uses <b>double</b><br /><br /></pre></tt><br /></blockquote><br />Even though we're using a float array the function is explicitly instantiated using the type <tt>double</tt>. This would compile fine but obviously yield a runtime error in this specific case because we'd be performing pointer arithmetic (i.e using the array) with a <tt>double</tt> type which is twice as big as the <tt>float</tt> parameter. But hang on a second... why does it even compile? You may have noticed something amiss here... we've used <tt>double*</tt> here explictly but when we don't specify the type i.e. <tt>bubbleSort(f,4)</tt> shouldn't the type of <tt>f</tt> be <tt>float</tt> and not <tt>float*</tt>? If this were true then our function would be written by the compiler thus:<br /><pre><tt><br /><blockquote><br />// not what we get<br />void bubbleSort(float *numbers[], size_t size);<br />// this IS what we get!<br />void bubbleSort(float numbers[], size_t size); <br /><br /></pre></tt><br /></blockquote><br />The reason for this, and the reason why all the above code examples work is because when the compiler does type deduction it performs a number of type conversions on the actual type passed. If you want more details on this here's an excellent article by Angelika Langer on <a href="http://www.angelikalanger.com/Articles/Cuj/02.FctTemplArgs/FunctionTemplateArguments.html">Function Template Arguments</a>. I learnt alot reading this article. Jump to the section entitled "Implicit Type Conversions Involved in Template Argument Deduction" if you are just interested in what we've been talking about here, but I heartily recommend you read the whole thing. Anyway, I've got off the beaten track again, it's time to finish making our poor old, slow bubbleSort generic... aren't we done? No. It may work in it's current state for all POD (Plain Old Data) types but try this:<br /><pre><tt><br /><blockquote><br />std::vector<int> array;<br />array.push_back(6);<br />array.push_back(3);<br />array.push_back(1);<br />array.push_back(5);<br /><br />bubbleSort(array, array.size());<br /><br /></pre></tt><br /></blockquote><br />...and you'll quickly see it doesn't work for STL containers. You could always compile it and see why but put simply it's because we are asking the compiler to instantiate something along these lines:<br /><pre><tt><br /><blockquote><br />void bubbleSort(std::vector<int> numbers[], size_t size);<br /><br /></pre></tt><br /></blockquote><br />Which is obviously ludicrous! Anyway, when we want to iterate though an STL container we don't pass the containers to algorithms but the containers <i>iterator</i>. I.e. <tt> std::swap(array.begin(), array.end());</tt>.<br><br>The iterator is an abstract concept, by that I mean that anything that behaves like an iterator <i>is</i> an iterator, including simple arrays. The reason why simple arrays are iterators too is because iterators are implemented using operator overloading of ++, --, [] among others (and depending on the type of iterator) to use the same syntax as pointer arithmetic. This gives us a clue as to how we can write our fully generic <tt>bubbleSort</tt> function. If we pass "pointers" to the start and end we can use pointer arithmetic inside the function body and it should work with both simple arrays and STL containers. One thing to note is that STL ranges are defined with a closed start and an open end. This means the <tt>begin()</tt> of an iterator points to the first element whilst the <tt>end()</tt> actually points to the element directly <i>after</i> the last element. This is something we need to be aware of when writing the function, luckily for us it is a really good design decision and greatly simplifies a lot of things for us! Anyway, I don't want to stray from the path of this blog anymore so perhaps we'll discuss STL ranges later, here's the final implementation of <tt>bubbleSort</tt>...<br /><pre><tt><br /><blockquote><br />template<class Iter, class T><br />void bubbleSort(Iter left, Iter right, T)<br />{<br /> bool swap = true;<br /> while(swap)<br /> {<br /> swap = false;<br /> for(Iter it = left + 1; it!=right; ++it)<br /> {<br /> if(*it<*(it-1))<br /> {<br /> T tmp = *it;<br /> *it = *(it-1);<br /> *(it-1) = tmp;<br /> swap = true;<br /> }<br /> }<br /> }<br />}<br /><br /></blockquote><br /></pre></tt><br />However we can't use this function in exactly the same way as we use <tt>std::sort</tt>, it has 3 arguments! The first two specify the range we want to sort and the 3rd passes the type used in the container of the iterator! We need this to store our temporary variable <tt>T tmp = *it</tt>. Notice that there is no parameter variable specified as we only need to use the type. This makes the usage of this function pretty ugly:<br /><pre><tt><br /><blockquote><br />//dereference first element to pass type of container<br />bubbleSort(array.begin(),array.end(),*array.begin());<br /><br /></blockquote><br /></pre></tt><br />No worries we can use explicit function template argument specification! (I hear you cry ... erm), well no we can't. We'd have to specify all the template arguments which would make the function quite tedious to use. A better solution is to write a simple function overload to call the above for us:<br /><pre><tt><br /><blockquote><br />template<class Iter><br />void bubbleSort(Iter left, Iter right)<br />{<br /> bubbleSort(left, right, *left);<br />}<br /><br /></blockquote><br /></pre></tt><br />This is a neat trick we can use to quite clearly derive the container type of an iterator in a lot of situations.<br><br>To conclude this part we now have a more useful generic version of our algorithm which can by used for simple arrays and STL containers. The point of this blog has been to demonstrate how it's possible to convert an algorithm into a more useful, generic form. We'll look at some faster sorting algorithms in part III...<br><br>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1146238547491242562006-04-28T16:27:00.000+01:002006-04-28T16:36:08.946+01:00C++ : Exploring Sorting part ISorting is a fundamental requirement in many programs and libraries. As such it has been throughly explored by many people since the dawn of computers and there are many efficient algorithms and implementations available. This doesn't stop us pulling them apart, finding out all about them and seeing if we can't do better though! This is the first in a series of blogs on the subject where I want to go from looking at sorting algorithms to developing our own generic (of course!) sorting function.<br><br><br />I'll leave you with the good, old (and very, very slow) bubble sort ... we'll make it generic in part II...<br /><pre><tt><br /><blockquote><br />void bubbleSort(int numbers[], size_t size)<br />{<br /> bool swap = true;<br /> while(swap)<br /> {<br /> swap = false;<br /> for(int i = 1; i<size; ++i)<br /> {<br /> if(numbers[i]<numbers[i-1])<br /> {<br /> int tmp = numbers[i];<br /> numbers[i] = numbers[i-1];<br /> numbers[i-1] = tmp;<br /> swap = true;<br /> }<br /> }<br /> }<br />}<br /></blockquote><br /></pre></tt>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1145950899720189472006-04-25T08:38:00.000+01:002006-04-25T08:43:00.210+01:00Retro Gaming : What's Knanshon?<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://photos1.blogger.com/blogger/1386/2673/1600/knanshon.jpg"><img style="float:left; margin:0 10px 10px 0;cursor:pointer; cursor:hand;" src="http://photos1.blogger.com/blogger/1386/2673/320/knanshon.jpg" border="0" alt="" /></a>Remember Xenon II : Megablast? At the start of every level you bought power ups and upgrades from this guy. One of them was called "Super Knanshon Power" which gave you every power-up and upgrade for the first 10 seconds. Not sure if it was spelt like this but it makes an excellent unique username for sure! :)Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1145651434143301172006-04-21T21:25:00.000+01:002006-04-21T21:47:41.486+01:00C++ : A response to functorsI received an interesting and detailed response to my posts on the uses of <tt>std::for_each</tt> from my friend Jun. Before we dive in I'd like to point out that I find it interesting that there seems to be an infinite number of ways of solving the same problem in C++! If you've ever used C# you'll know that the <tt>for(<i>object</i> in <i>IEnumerable</i>)</tt> syntax is part of the language. However this is a very different language despite the syntatical similarities and it doesn't do to pit one language against another ... they all have their uses.</p><p>Soapbox time over, let's get on with it!<br><br><i>Jun writes...</i><br><br>The thing I don't like about functors (function objects) is that they can clutter the code and they obscure the flow of the logic. Originally it is clear what you want - I only have to look at what you say is the ugly code (<tt>void B::Update()</tt>).<br><br>But I don't agree that the code has become easier to read or understand (i.e. maintain) toward the end of your article.<br><br>At the start it is clear that B has a container which is used to steer its controls.<br><br><br />In the end this simple piece of code is stretched out over a <tt>class A_UpdateHandler</tt> (it's <tt>Update</tt> function), <tt>B::Init()</tt> function and of course the <tt>B::Update()</tt> function. Undoubtfully the <tt>Init()</tt>, <tt>Update()</tt> and the <tt>A_UpdateHandler</tt> will end up apart from each other in the source file and it will become quite tricky for others (including yourself in a couple of months time) to piece out the flow of the code.<br><br>What happens when elements are added to or removed from <tt>m_APCollection</tt> after <tt>Init()</tt> has been called?<br><br><br />The design in the end is a workaround for the fact that C++ doesn't support Lambda calculus. If you look at it - the original <tt>Update()</tt> function is clear, but to be able to use <tt>std::for_each</tt> you had to create a functor and use a <tt>std::bind2nd</tt> with a <tt>std::mem_fun_ref</tt> which makes the end result more complex than what you originally started with.<br><br>I can imagine that if someone else would have to make a change to this code and allow for changes to be made to <tt>m_APCollection</tt> at runtime - (s)he could be in for a bind.<br><br><br />Everything in C++ is solvable by introducing an extra layer of indirection. But by doing so, simple things can be lost in the translation.<br><br>If you would use pseudo code to describe your algorithm it would be something like:<br /><pre><tt><blockquote><br />for a in m_APCollection do<br /> control = GetControlByName ( a.GetName( ) )<br /> if ( control ) then<br /> graphic.doSomething( control.GetCurrentValue( ) <br /> > a.GetThreshhold( ) )<br /> end<br />end<br /></blockquote></pre></tt><br />Now wouldn't it be nice to be able to stick as close to this as possible?<br><br />You definitely have to read <a href="http://www.artima.com/cppsource/foreach.html">FOREACH Redux by Niebler!</a><br />check this out:<br /><pre><tt><blockquote><br />BOOST_FOREACH ( char c, "Hello World" )<br />{<br /> std::cout << ch;<br />}<br /></blockquote></pre></tt><br />or even<br /><pre><tt><blockquote><br />BOOST_FOREACH ( A *a, m_APCollection )<br />{<br /> std::string const &name=a->GetName( );<br /> Control *control = GetControlByName( name ); <br /> // can return NULL<br /> if ( control )<br /> {<br /> bool value = control->GetCurrentValue( ) <br /> > a->GetThreshold( );<br /> graphic.doSomething( value );<br /> }<br />}<br /></blockquote></pre></tt><br />Sticks pretty close to what you originally intended? Then in turn it<br />is not that different from what you considered to be ugly code<br><br><br />Now I am curious if there is a way to force <tt>std::for_each</tt> in without having to write a wrapper and having to use "bind" and "mem_fun_ref".<br><br><br />How about this sneaky way to get access to that private function(compiles with the .NET C++ compiler - I haven't checked with GNU or others). No need to make changes to the interface and this is the update function:<br /><pre><tt><blockquote><br />void B::Update( )<br />{<br /> Graphic const &graphic = GetGraphic( );<br /> DoSomethingWithA functor(graphic, *this, <br /> &B::GetControlByName);<br /> std::for_each(mAPCollection.begin( ), <br /> mAPCollection.end( ), functor);<br />}<br /></blockquote></pre></tt><br /><i>(*disclaimer - I am not promoting this and any loss or<br />damage resulting from this code is your own responsibility!</i><br><br><br />Jun<br><br><br />So I agree with all of what is said here and have taken it on board. My main mistake in this case was the desire to use a tool that was unsuited to the task in hand. Having said that I learnt a lot so it is always recommended to try these things out! I actually managed to use a more straight forward functor without the pointer to a private member function hack to solve a similar problem after this and I think it made for much better code. Of the two solutions offered the <tt>BOOST_FOREACH</tt> is the most robust and readable. The Niebler article is well worth a read. Many good generic tricks are introduced in an interesting context and I learnt a lot. Especially the <b>ScopeGuard</b> trick from Alexandrescu ... but that's a topic for another post. The full code for Jun's own solution is shown below and I think you'll agree too that it is more readable and hence easier to maintain. The intention is clear and as it says in <b>The Pragmatic Programmer</b> <i>"Program close to the Problem Domain"</i>.<br /><pre><tt><blockquote><br />#ifndef __B__H<br />#define __B__H<br /><br />#include <string><br />#include <vector><br /><br />class A<br />{<br />public:<br /> std::string const& GetName() const;<br /> int GetThreshold() const;<br />};<br /><br />struct Control { int GetCurrentValue() const { return 11; } };<br />struct Graphic { void DoSomething(bool) const {} };<br /><br />class B<br />{<br />public:<br /> void Update();<br />private:<br /> Control const* GetControlByName(<br /> std::string const &name) const;<br /> Graphic const& GetGraphic() const;<br /><br /> std::vector<A*> mAPCollection;<br />};<br /><br />#endif // __B__H<br /></blockquote></pre></tt><br /><pre><tt><blockquote><br />// b.cpp<br />#include "b.h"<br />#include <algorithm><br /><br />using namespace std;<br /><br />string const& A::GetName() const<br />{<br /> static string const name("Knanshon");<br /> return name;<br />}<br /><br />int A::GetThreshold() const { return 42; }<br /><br />//--------------------------------------<br /><br />namespace<br />{<br /><br /> class DoSomethingWithA<br /> {<br /> Graphic const &mGraphic;<br /> B &mB;<br /> typedef Control const* (B::*GetCtrl)<br /> (std::string const&) const;<br /> GetCtrl mFoo;<br /> public:<br /> DoSomethingWithA(Graphic const &graphic, B &b, <br /> GetCtrl foo)<br /> : mGraphic(graphic)<br /> , mB(b)<br /> , mFoo(foo)<br /> {<br /> }<br /><br /> void operator()(A *a)<br /> {<br /> string const &name=a->GetName();<br /> Control const *ctrl=(mB.*mFoo)(name); <br /> // can return NULL<br /> if ( ctrl )<br /> {<br /> bool value = ctrl->GetCurrentValue() > <br /> a->GetThreshold();<br /> mGraphic.DoSomething(value);<br /> }<br /> }<br /> };<br /><br />} // anonymous namespace<br /> <br />//---------------------------------------------------<br /><br />Control const* B::GetControlByName(<br /> string const &name) const<br />{<br /> return 0;<br />}<br /><br />Graphic const& B::GetGraphic() const<br />{<br /> static Graphic const g;<br /> return g;<br />}<br /><br />void B::Update()<br />{<br /> Graphic const &graphic=GetGraphic();<br /> DoSomethingWithA functor(graphic, *this, <br /> &B::GetControlByName);<br /> std::for_each(mAPCollection.begin(), <br /> mAPCollection.end(), functor);<br />}<br /><br />// eof<br /></blockquote></pre></tt>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1145526231507526412006-04-20T10:29:00.000+01:002006-04-20T10:45:42.170+01:00C++ : Once false always falseI've recently written a useful little class that can be treated like a plain old <tt>bool</tt> type but has a couple of behavioural differences. It defaults to true on construction and once it is set to false, it can never be set to true. Here it is<br><br /><pre><tt><br /><blockquote><br />class OnceFalseAlwaysFalse<br />{<br />public:<br /> OnceFalseAlwaysFalse() : m_Value(true) {}<br /> operator bool() { return m_Value; }<br /> const bool operator ==(const OnceFalseAlwaysFalse &rhs) <br /> { return m_Value==rhs.m_Value; } <br /> const bool operator !=(const OnceFalseAlwaysFalse &rhs) <br /> { return m_Value!=rhs.m_Value; }<br /> const bool operator !(void) <br /> { return !m_Value; }<br /> const OnceFalseAlwaysFalse &operator =(const bool & value)<br /> { if(m_Value) m_Value=value; return *this; }<br />private:<br /> bool m_Value;<br />};<br /></blockquote><br /></pre></tt><br />What the hell use is that? I hear you cry. Well, consider the following, fictitious example.<br><br /><pre><tt><br /><blockquote><br />// Function to save as many pages as it can, <br />// returns false if any failed to print.<br />bool PrintDocument(void)<br />{<br /> bool success = true;<br /><br /> if(!PrintPage(1))<br /> success = false;<br /> if(!PrintPage(2))<br /> success = false;<br /> if(!PrintPage(3))<br /> success = false;<br /><br /> return success;<br />}<br /></blockquote><br /></pre></tt><br />And this is the function using the <tt>OnceFalseAlwaysFalse</tt> class instead of a plain old <tt>bool</tt>...<br><br /><pre><tt><br /><blockquote><br />bool PrintDocument(void)<br />{<br /> OnceFalseAlwaysFalse success;<br /> success = PrintPage(1);<br /> success = PrintPage(2);<br /> success = PrintPage(3);<br /> return success;<br />}<br /></blockquote><br /></pre></tt><br />A lot neater I think you'll agree. It takes out the multiple <tt>if</tt> tests needed to ensure that the overall success of the function is stored rather than simply the storing the success of the last operation. The class also illustrates one of Bjarne Stroustrups major intentions for the C++ language, i.e. that custom data types can be treated in exactly the same way as built-in types. This is achieved via the medium of operator overloading. For this class I have overloaded the =, !=, == and bool (implicit conversion to bool) operators. The last one is useful as it allows an instance of <tt>OnceFalseOnlyFalse</tt> to be returned by a function which is defined to return a <tt>bool</tt>, as many are.<br><br><br />Hope this can help you write some easier-to-read code!<br><br>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com1tag:blogger.com,1999:blog-25559799.post-1144932354207029192006-04-13T13:41:00.000+01:002006-04-13T13:48:02.573+01:00C++ : C++0x<a href="http://www.artima.com/cppsource/cpp0x.html">http://www.artima.com/cppsource/cpp0x.html</a><br /><br><br><br />Bjarne Stroustrup (the creator of C++) offers a sneak peek at the next version of standard C++ ("C++0x") which should be complete by 2009, and will then become C++09. <br><br>The current standard version is C++98, it takes along time to ratify these changes!<br><br>See my links on the sidebar for Bjarne Stroustrup's Homepage<br><br>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1144532798774559272006-04-08T22:26:00.000+01:002006-04-10T22:03:18.433+01:00HTML : <pre><tt>y codeWell, in my first ever post to this blog I mentioned that I was trying to get the formatting to look good for my code examples. One of the easiest ways I found to do this in HTML was by using the <tt><pre></tt> tag. Any text between the <tt><pre></tt> and <tt></pre></tt> tags will not be formatted, i.e. wrapped or have whitespace stripped which your browser usually does. This is very handy for indented code.<br><br>One caveat is that you have to be careful to ensure the lines aren't too long. In this blog I ensure that a code line never exceeds column 67.<br><br />Ok, that takes care of the formatting, but how do I get a nice fixed width font for the code examples. <i>Style-sheets!</i> I hear you cry, and indeed they do come in very useful for exactly this kind of thing but there is a simpler way to achieve this common task in HTML, the <tt><tt></tt> tag. This stands for <b>teletype</b>. An easy-to-use tag it is much more suitable for writing code snippets in amongst the normal text. The alternative would be something like this: <tt><div class="code"></tt> and then you'd have to specify the styling, i.e. font etc. in a stylesheet - which, by the way, is the only place you should put style information - remember this simple rule:<br><br /><b>HTML/XML = Content<br><br />CSS/XSL = Style</b><br><br />The two should always be seperate in any good system. Imagine having to go through every single one of your postings and changing them to conform to a style rather than simply changing the template and republishing!<br><br><br />Obviously you can still add additional styling for the <tt><tt></tt> tag if you wish. Indeed on this blog I have changed the font color slightly just to make the in place code snippets stand out a bit more.<br><br><br />I also enclose my large code examples in <tt><blockquote></tt>'s, which in my stylesheet/template is defined as having a darker background since this is how you'll find it done in most books written about code. Be careful to put the <tt><blockquote></tt> inside the <tt><pre></tt> and <tt><tt></tt> tags otherwise the darker blocks will extend to the top and bottom of the containing paragraphs and look ugly.<br><br><br />Anyway, if you have a blog of your own I hope this can help you have <tt><pre></tt><tt><tt></tt>ier text!<br /><br><br />For a look at what a good stylesheet can do visit <a href="http://www.csszengarden.com/">http://www.csszengarden.com/</a><br>Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com1tag:blogger.com,1999:blog-25559799.post-1144526999541201752006-04-08T21:09:00.000+01:002006-04-08T21:47:22.506+01:00C++ : In a bind with function objects part IVJust to recap let’s look at the relevant parts of <code>class B</code> again in it’s entireity…<br /><pre><tt><br /><blockquote><br />class B<br />{<br />public:<br /> void Update()<br /> { <br /> Graphic &graphic = GetGraphic();<br /><br /> std::for_each(<br /> m_A_UpdateHandlers.begin(),<br /> m_A_UpdateHandlers.end(),<br /> std::bind2nd(<br /> std::mem_fun_ref(&A_UpdateHandler::Update), <br /> &graphic)<br /> );<br /> }<br /><br />private:<br /> void Init()<br /> {<br /> Control *control;<br /><br /> for(APtrContainer::iterator it = m_APCollection.begin();<br /> it!= m_APCollection.end(); ++it)<br /> {<br /> A &a = *it;<br /> std::string &name = a.GetName();<br /> control = GetControlByName(name);<br /> if(control)<br /> {<br /> const int threshold = a.GetThreshold();<br /> m_A_UpdateHandlers.push_back(<br /> A_UpdateHandler(*control, threshold));<br /> }<br /> }<br /> }<br /> <br /> <br /> Control *GetControlByName(std::string);<br /> Graphic &GetGraphic() const;<br />...<br />private:<br /> APtrContainer m_APCollection;<br /> A_UpdateHandlerContainer m_A_UpdateHandlers; <br />}; <br /></blockquote><br /></pre></tt><br />The first thing we notice is that design constraints imposed by the standard during the refactor have forced me to separate the processing of <tt>class A</tt> objects into an initialisation phase and an update phase. The potentially expensive call to <tt>GetControlByName</tt> is only done once per object in the initialisation phase as is the check to see if it returns a NULL value. Additionally, if the control indeed is NULL nothing gets added to the handler container. In the worst case, if no controls are found the update function will do nothing! Finally the update function in the handler that does the actual work is succinct and to the point, only expressing the minimum it needs to in order to get the job done. Everything required prior to this call has been handled already and is either passed in or cached where appropriate<br /><pre><tt><br /><blockquote><br />void A_UpdateHandler::Update(Graphic *graphic) const<br />{<br /> bool value = m_Control.GetCurrentValue() > m_Threshold;<br /> graphic->doSomething(value);<br />}<br /></blockquote><br /></pre></tt><br />All of these things have improved the code in terms of legibility, ease of maintenance and run-time efficiency, what more do you want!?<br /><br><br />A couple of finer points are worth noting here before we end the last part in this series. <tt>std::bind2nd</tt> is obviously a templated function. The compiler implicitly deducts what types to use to instantiate the function using the types of the parameters. However, <tt>std::bind2nd</tt> defines the type of the second parameter as a reference type to this type. For this reason we must pass in a pointer to the <tt>Graphic</tt> object since references to references are illegal in C++ and your local friendly compiler will tell you as much if you attempt it! Also, when using <tt>std::mem_fun_ref</tt> in combination with <tt>std::bind2nd</tt> like this the member function must be <tt>const</tt> as <tt>std::bind2nd</tt> (and <tt>std::bind1st</tt> for that matter) don’t allow the use of non-<tt>const</tt> adaptors as parameters. In our case of using a wrapper class, which acts as a kind of functor with a constant state that we don’t need to change, this is not an issue, then again, there’s always that lovely keyword <tt>mutable</tt>.Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0tag:blogger.com,1999:blog-25559799.post-1144420968894616762006-04-07T15:42:00.000+01:002006-04-08T21:58:16.523+01:00C++ : In a bind with function objects part IIIGiven this constraint I needed to write a new member function for <tt>class A</tt> that did the work, at the time (luckily for me as it turned out) this wasn’t an option so I thought that this sounded like a job for a wrapper class!<br /><pre><tt><br /><blockquote><br />class A_UpdateHandler<br />{<br />public:<br /> A_UpdateHandler(Control &control, const int threshold)<br /> : m_Control(control)<br /> , m_Threshold(threshold)<br /> {<br /> }<br /><br /> void Update(Graphic *graphic) const <br /> // want to pass this in as it doesn’t make <br /> // sense for all the handler objects to <br /> // store the same pointer<br /> {<br /> bool value = m_Control.GetCurrentValue() > m_Threshold;<br /> graphic->doSomething(value);<br /> }<br /><br />private:<br /> Control &m_Control;<br /> const int m_Threshold;<br />};<br /><br />typedef std::vector<A_UpdateHandler> <br /> A_UpdateHandlerContainer;<br /></blockquote><br /></pre></tt> <br />Next I needed to create a collection of these handlers and initialise them. So a couple of (private) additions to <tt>class B</tt> did the trick.<br /><pre><tt><br /><blockquote><br />class B<br />{<br /> …<br /> private:<br /> …<br /> void Init()<br /> {<br /> // Note: using a for-loop here to illustrate the current <br /> // point more clearly, I’ll leave refactoring to a pref-<br /> // erable implementation using for_each as an exercise <br /> // for the reader! Clue: try using std::transform with <br /> // a back_inserter.<br /> // When I first came across this problem an Init member <br /> // already existed in the real version of “class B” <br /> // that iterated through the collection anyway,<br /> // perhaps I should go back and refactor that too…<br /><br /> Control *control;<br /><br /> for(APtrContainer::iterator it = m_APCollection.begin();<br /> it!= m_APCollection.end(); ++it)<br /> {<br /> A &a = **it;<br /> std::string &name = a.GetName();<br /> control = GetControlByName(name);<br /> if(control)<br /> {<br /> const int threshold = a.GetThreshold();<br /> m_A_UpdateHandlers.push_back(<br /> A_UpdateHandler(*control, threshold));<br /> }<br /> }<br /> }<br /> …<br /> private:<br /> A_UpdateHandlerContainer m_A_UpdateHandlers;<br />};<br /></blockquote><br /></pre></tt> <br />Now <tt>class B</tt>’s update function can now be written using a call to <tt>std::for_each</tt>…<br /><pre><tt><br /><blockquote><br />void B::Update()<br />{<br /> std::for_each(<br /> m_A_UpdateHandlers.begin(),<br /> m_A_UpdateHandlers.end(),<br /> std::mem_fun_ref(&A_UpdateHandler::Update)); <br /> // we have a problem!<br />}<br /></blockquote><br /></pre></tt><br />Another problem!! Oh no, but before we explore what it is an how I overcame it to get to the end of this refactor (finally!!) I’d like to point out the use of <tt>std::mem_fun_ref</tt> above. It does the same as <tt>std::mem_fun</tt> but works with a collection of references instead of pointers.<br /><pre><tt><br /><blockquote><br />template<class Result, class Type><br /> std::<b>mem_fun_ref_t</b><Result, Type> <br /> std::<b>mem_fun_ref</b>(Result (Type::*pm)());<br /></blockquote><br /></pre></tt> <br />So, the problem with calling <tt>A_UpdateHandler::Update</tt> in this way is that there’s no way of passing the <tt>Graphic *</tt> parameter that we need - or is there? Enter that old favourite, <tt>std::bind2nd</tt> and the final update function looks like this:<br /><pre><tt><br /><blockquote><br />void B::Update()<br />{<br /> Graphic &graphic = GetGraphic();<br /><br /> std::for_each(<br /> m_A_UpdateHandlers.begin(),<br /> m_A_UpdateHandlers.end(),<br /> <b>std::bind2nd</b>(<br /> std::mem_fun_ref(&A_UpdateHandler::Update), <br /> <b>&graphic</b>)<br /> );<br />}<br /></blockquote><br /></pre></tt><br />Which in terms of sheer aethestetics looks a lot prettier than our original for-loop! This isn’t mere triviality, in my experience elegant <i>looking</i> code usually indicates a more elegantly designed solution under the hood. There are several reasons why this is the case here.<br /><br><br />... and I'll go through it with you in Part IV :)Barry J. Northernhttp://www.blogger.com/profile/12078136594892291058noreply@blogger.com0