Wednesday, November 24, 2010

Boost multi-index container quirks

I recently had the need to use a container that supports both fast search access and sequential (insert-order) access. The boost::multi_index_container was just that. It is an amazing piece of code. To use the container itself, however, is a bit quirky. First, let's see how we can use it.

Suppose your requirement is to define a map (for fast search) with an int KEY and some satellite data struct DATA, and you still want to access the whole list of (KEY, DATA) pairs in the same order as you inserted them. The way to define a multi_index_container for this is as follows:

#include "boost/multi_index_container.hpp"
#include "boost/multi_index/indexed_by.hpp"
#include "boost/multi_index/seqeunced_index.hpp"
#include "boost/multi_index/ordered_index.hpp"
#include "boost/multi_index/identity.hpp"
#include "boost/multi_index/member.hpp"

typedef std::pair<int,DATA> DataPair;

typedef boost::multi_index_container<datapair,
boost::multi_index::indexed_by <
boost::multi_index::sequenced<>,
boost::multi_index::ordered_unique <
boost::multi_index::member<DataPair,>
>
>
> DataContainer;

enum IndexType {
     kIndexSequential, // = zero (the first index is the sequenced index)
     kIndexSearchable // = one (the second index is the ordered index on the first member of the pair)
};

typedef DataContainer::nth_index<kIndexSequential> SequentialAccessIndex;
typedef DataContainer::nth_index<kIndexSearchable> SearchableAccessIndex;


// To declare a container
DataContainer myContainer;

....

// to insert content
myContainer.push_back(std::make_pair(12, someDATAInstance));
myContainer.push_back(std::make_pair(13, someOtherDATAInstance));
....


// to search for the content
SearchableAccessIndex& srchIdx = myContainer.get<kIndexSearchable>();
SearchableAccessIndex::iterator idx = srchIndex.find(12);
if (idx != srchIdx.end()) {
// ... use it..
}

// to sequentially access (e.g. iterate over the content, or add it to a list)
std::list sequentialDataList;
SequentialAccessIndex& seqIdx = myContainer.get<kIndexSequential>();
std::transform (seqIdx.begin(), seqIdx.end(), std::back_inserter(sequentialDataList),
std::tr1::bind(&DataPair::second, std::tr1::placeholders::_1));


So where are the quirks? Some hint in the last operation we did.. the sequentialDataList had to be declared as a list of const Data. This is the key issue. The multi_index_container does NOT allow changing the data in-place (that's not entirely true).

The container is not (and probably cannot be) programmed to be smart enough to know that only a part of the data is to be modified in-situ, while the indexes will remain intact. So, how does it allow updates? There are two distinct ways:

i) Using replace( ) which is an exception-safe way to do it. It takes the iterator to the element to be replaced, and a new object (which implicitly means your object needs to be copy-constructible).
// replace
SearchableAccessIndex& srchIdx = myContainer.get();
SearchableAccessIndex::iterator idx = srchIndex.find(12);
if (idx != srchIdx.end()) {
DataPair pair = *idx; // copy constructed
pair.second = someNewDATAInstance;
srchIdx.replace (idx, pair);
}

ii) The second, more sophisticated, way is to use modify which takes as its second parameter, a functor. This functor is passed a reference to the object being modified, and is responsible for modifying it as required. So,

// using modify()

struct ModificationFunctor {
ModificationFunctor(const DATA& someDataRef):m_Data(someDataRef)
{
}
void operator()(DataPair& dataPair)
{
dataPair.DATA = m_Data;
}

private:
const DATA& m_Data;
};


...
// actual modify
SearchableAccessIndex& srchIdx = myContainer.get();
SearchableAccessIndex::iterator idx = srchIndex.find(12);
if (idx != srchIdx.end()) {
srchIdx.modify(idx, ModificationFunctor(someNewDataInstance));
}

But if you are the old school, novice programmer that I am, you'd like direct access to the struct DATA, which after all is the only thing you wish to modify. Why can't you just let me have it? Why not?? :(

The answer is to use a const_cast. This is not necessarily the best way to do things, but it works, provided that the DATA you inserted into the pair is never really a constant. The way to do that is as follows:

SearchableAccessIndex& srchIdx = myContainer.get<kIndexSearchable>();
SearchableAccessIndex::iterator idx = srchIndex.find(12);
DATA& data = *(const_cast<DATA*>(&(idx.second)));

and then modify data as usual

data.whatever = whatever;





Monday, October 11, 2010

std::tr1::bind the hard way

I'll probably move this to a tech blog when I start one..

Usually, I'd just go up to my colleague (Mr. Skarpio, a.k.a. DirkGently) when in trouble with the STL. This time he's on leave, and I had to figure it out on my own. The thing in question is tr1::bind, a function template available in C++ for binding values to parameters in functions, and functors. It is supposed to be easier to use than the older std::bind1st and std::bind2nd. But, I'm new to STL, and of course to the "functional" way of life. So, I had a real hard time to get this right. So how do you use it...

Here's how :


Example 1: Using it with regular functions

void foo(int bar1, int bar2)
{
std::cout << bar1 << bar2 << std::endl;
}

And then some where in your code, if you use..

std::tr1::bind(foo, 10, std::tr1::placeholders::_1)(20)

What this does is of course useless (mostly). The list of arguments after "foo" above has one of the following two things (actually, it can have more, but for now two will suffice):

1. a value
2. a placeholder

So the expression above is equivalent to calling foo(10, 20);

If you do it the other way around, i.e.
std::tr1::bind(foo, std::tr1::placeholders::_1, 10)(20);
then that's equivalent to calling foo(20, 10);.

If you specify placeholders for both, i.e.
std::tr1::bind(foo, std::tr1::placeholders::_1, std::tr1::placeholders::_1)(20); ,
then both parameters are taken from the actual list of parameters, i.e. it is equivalent to calling foo(20,20);.

Example 2: Using it with function objects (functors). This is where I got stuck and then read the documentation here carefully to discover this
In the general case, the return type of the generated function object's operator() has to be specified explicitly (without a typeof operator the return type cannot be inferred):
So, for example, here is a simple rendition of the same function "foo" as a functor:

struct foo_object {
void operator()(int x, int y) {
std::cout << x << "," << y << std::endl;
}
};

Now, using std::tr1::bind(foo_object(), 10, std::tr1::placeholders::_1)(20); does not work. So, basically, the struct has to be modified to add a new result_type typedef. That is,

struct foo_object {
typedef void result_type;
void operator()(int x, int y) {
std::cout << x << "," << y << std::endl;
}
};

Now we can use this, std::tr1::bind(foo_object(), 10, std::tr1::placeholders::_1)(20); , and it is indeed equivalent to calling foo_object()(10, 20).


Now for the actual utility of it... of Mr. tr1::bind :

Binding is used for clever "functional"-type programming in C++. For example,
  • suppose you have a std::vector<std::string> strings;
  • and a function std::string get_suffix(const std::string& str, long suffix_len); which gives you a suffix of the string that is suffix_len in length,
  • and now you want to extract out all suffixes of length 2 and length 4 from the list of strings and store them into distinct vectors std::vector<std::string> suffix_2, and suffix_4.
The regular way to do this is to use a for-loop that looks like this:
std::vector<std::string>::const_iterator iter = strings.begin(), iterEnd = strings.end();
for (; iter != iterEnd; ++iter) {
suffix_2.push_back(get_suffix(*iter, 2));
suffix_4.push_back(get_suffix(*iter, 4));
}
But, the STL way to do this is:
std::transform(strings.begin(), strings.end(), std::back_inserter(suffix_2),
std::tr1::bind(get_suffix, std::tr1::placeholders::_1, 2));
std::transform(strings.begin(), strings.end(), std::back_inserter(suffix_4),
std::tr1::bind(get_suffix, std::tr1::placeholders::_1, 4));

Of course, if Mr. Skarpio ever saw this, I'd be in for some rebuke, because he'd probably use some compositional stuff and do it in a single expression.






Sunday, July 18, 2010

Programs I love - Today's program - jQuery

Just so that I don't forget, I've decided to blog about programs that I really use and love. It's not important if anybody reads it ('cause this is basically my web "log" :D)

They say, a programmer can only be known by his work. So is the case with John Resig (http://ejohn.org/). His program - jQuery (http://jquery.com/), the write less and do more library that he wrote is a beautiful Javascript program. Beautiful, because it really works and is really small. So what is it?

jQuery's a Javascript program library that allows you to write your own Javascript code in a compact fashion. One common task in Javascript programs is to access specific elements on a page (for example, a div with an id="something"). jQuery provides easy (and new) ways to access them using what are called Selectors. These selectors are the same that are used in CSS for styling. So for example, if you styled a div by giving its class="someClass" attribute, jQuery allows you to access this element using jQuery(".someClass") . But that's not all - the object returned by jQuery(".someClass") is actually a wrapper over the page DOM object, and exposes a number of functions of its own. For example, it provides a click( ) function which takes in as argument, a handler function (basically, the functional programming approach) which gets called whenever the element is clicked.

Another important thing that jQuery does to compact the code is to use chaining of objects. So, if you've written jQuery(".someClass").click(function() {...}) , and you would like to do some more things to the same object, then you basically add a dot and continue jQuery(".someClass).click(function() {...}).hide( ) for example.

jQuery also provides a number of plug-ins that make a programmer's life easy. CSS is often used to style elements on a web page. jQuery provides easy ways to create good looking UI elements. For example, the Accordion navigator which is very useful for showing many categories of links in a compact manner, can be very easily built on a web page using jQuery(...).accordion( ). It only requires that the content be laid out as a hierarchical list (<ul>) tags. The good thing about it is that if for any reason (like if the browser doesn't support Javascript), jQuery doesn't work, the page still looks okay, because, it is still just an unordered list on the page.

All these things make jQuery a very handy program for creating web pages. The best thing, however, about jQuery is that it is cross-browser. This is very very important for web applications and pages that need to render on different browser, the likes of IE6, and Safari, and Opera, etc. jQuery just works.

Behind the scenes, when jQuery uses another library called the sizzleJS library which provides the basic selector functionality.

Oh! and one doesn't really have to write jQuery(...) everywhere.. One can simply use $(...) everywhere instead.

Friday, June 25, 2010

Proving the Cone volume formula without Calculus

High school students would probably do it in a jiffy. I've been baffled for a long time now about proving the cone volume formula of PI*R^2*H/3 .. Just haven't figured it out till date (i.e. a good solution). It's amazing that the volume formula has existed for such a long time and was invented before calculus came into being. My last attempt was basically cheating on the idea of a limiting value to determine the radius of an infinitesimal height disc that constitutes a cone.

Yesterday, however, I thought I found a better answer - not nearly close to an elegant solution - because it still uses the volume of a cylinder (which is slightly easier to explain), but a calculus-free solution nevertheless. The idea came ironically from a book on calculus (one I purchased recently). The second theorem of Pappus which states that the volume of revolution of a planar lamina about an external axis is equal to the surface area of the lamina times the distance travelled by the center of gravity of the lamina, plays the central statement in the solution. ("Central" sounds like there're too many things about it, but really there's just a little more).

So, now imagine a cylinder (volume = PI*R^2*H) with radius R and height H. Also imagine a right triangular lamina with its back (the perpendicular) resting on the cylinder. The lamina's dimensions height=h=H, base width = r. If you rotate this triangle about the cylinder's central axis you'd get a section of the cone. If you reduce the radius of the internal cylinder to zero, you'd get a perfect right-circular cone.

The volume of the cone can therefore determined as the volume of the rotation volume of this circular lamina.

Incidentially :) the position of the centroid is at (r/3, h/3) from the right vertex. Thus, the distance travelled by the center of gravity is (2*PI*r/3).

And the area of the right triangle is (r * h)/2 = (r * H/2)

Therefore, the volume of rotation (or the volume of the cone) is 2*PI*r/3 * (r * H/2) = (PI * r^2 * H) /3 which is what we set out to prove... It was so simple ..

Please don't ask me to prove Pappus's theorem without calculus..

Monday, November 23, 2009

iBOS - the Internet Browsing Operating System

Oh well! Sometimes, when some smart people come up with an idea that you've already had, and sort of done something... It's a nice feeling. That's what I felt when I first read about the Chrome OS. It was practically the same idea that we (Anuj, Amit and me) had back in college. We wanted to do an operating system that's a web browser - for low-end machines - the likes of kiosks in a library, etc. We did it.. sort of.. We started out writing a new kernel... and ended up (mostly feeling stupid) writing a text-based web browser (that's right, we only had about 3 months and we didn't even know how to write Makefiles :D). But yes, we wrote a browser that read some HTML, filtered out the rest (and the Javascript), and we made it the default shell of a stripped-down RedHat 8 distribution. It was extremely basic (meaning crude, I even remember putting in a SIGSEGV handler towards the end of the term) with a vim-like dual mode (edit and browse) interface. But it was fast. Coupled with a filtering proxy which we mostly used to filter out unwanted (spelled unhandled) HTML markup and JS code, and to make the actual HTTP calls to the servers, we had a couple of systems running as kiosks in our lab. And guess which page we used to demo.. that's right www.google.com :D Oh! and the search worked, because we added support for GET/POST form submission in the last month of our term.

I guess, it does take a bunch of really smart people to do it on a really usable scale. But it does feel nice to boast about these things once in a while - that you were once nearly right there amongst the smart ones. Now I'd have wanted to put a link to the documentation and source code, but alas... Yahoo shut down their geocities (philanthropy) where we'd put it. So, all that remains of it now is on my machine, and a thick volume of documentation that my friend Anuj made me write (I still curse him for it).

I hope someday we all get together again as a team and maybe write something to compete with Chrome OS (Day dreaming... well it's night time around here anyway.)

Tuesday, July 7, 2009

एक और बजट पर्यावरण के लिए

यदि ऐसा अधिनियम किसी दिन हमारे संसद में प्रस्तुत हो तो कैसा रहेगा?
वाहनों के विषय में: -
१ किसी भी व्यक्ति के पास यदि एक से अधिक ईंधन-चलित वाहन हो तो उससे अतिरिक्त कर लिया जाए।
२ यदि कोई भी ५० वर्ष से कम आयु का व्यक्ति किसी ४-पहिया वाहन में अकेला दीख पडे तो उससे कर लिया जाए।
यदि किसी को कोई साथी न मिले अपनी गाड़ी के लिए तो वह सार्वजनिक वाहनों का उपयोग करे।
३ यदि कोई ५० वर्ष से कम आयु का व्यक्ति किसी वाहन चालक को अपनी सेवा में रखे तो उससे अतिरिक्त कर लिया जाए।
४ सरकार इस वर्ष से हर मार्ग पर कम से कम २० विद्युत-चलित बसें चलाएगी।

विद्युत संरक्षण हेतु: -
१ किसी भी घर में एक से अधिक वातानुकूलन यन्त्र न हो। यदि किसी के घर में वृद्ध लोग हों जिन्हें उनकी आवश्यकता हो तो वे अपने किसी एक कमरे में ऐसे यन्त्र का प्रयोग कर सकते हैं।
२ रात में १२ बजे के बाद सब विद्युत उपकरण (पंखे एवं ऐसी को छोड़ कर) बंद कर दें।
३ घर में एक से अधिक फ्रीज या वाशिंग मशीन होने पर अतिरिक्त शुल्क लगेगा।
४ प्रातः ८ बजे से सांय ५ बजे तक कोई भी प्रकाश देने वाले उपकरण उपयोग करने पर अतिरिक्त विद्युत शुल्क लगेगा

जल संरक्षण हेतु: -
१ प्रति व्यक्ति हर घर में पानी की व्यवस्था कुछ इस प्रकार होगी -
नहाने के लिए ३ लीटर
पीने के लिए ५ लीटर
शौच के लिए ३ लीटर
अर्थात प्रति व्यक्ति, एक दिन में ११ लीटर से अधिक पानी नही उपयोग कर सकेगा।
२ किसी भी घर में टुल्लू अथवा पम्प का प्रयोग निषेध होगा।
३ वर्षा ऋतू में वर्षा का पानी एकत्रित कर अपने ११ लीटर के कोटे से कम पानी प्रयोग करने वाले सभी नागरिकों को पुरस्कृत किया जाएगा।

अभी बस इतना ही। शेष वचन फ़िर कभी।

Thursday, February 12, 2009

Kolkata: A Weekend

The city, like every other Indian city reflects images of the past, and of the future. Here are a few shots from my phone (hence the low resolution) of a day in Kolkata - the city of joy (Mukherjee?)
The order is completely random (well not really!)



The new symbol of the city (the second bridge over the Hooghly river).
The massive engineering feat reflects progress in the state. Or does it?














A republic day celebration at a locality
What does a republic day mean to a rickshaw puller?
























The city has loads of glimpses of the British empire. Many have been preserved to date for their beauty. Or have we still not gotten over our rulers?









Morning Breakfast. National integration at this level - Puri Bhaji (a typical northern dish) is savored by many in Kolkata.






The many modes of transport in the city.



Followers

Blog Archive

About me

A soul possessed forever...