INI File Parser ( C++ )

INI File Yesterday I was just browsing Stackoverflow, One question took my attention on INI File parsing. So I was just thinking why it is so difficult to parse ini file. I decided to write a parser for the same. On one hand India Vs England IIIrd test was causing panic and other side this parser activity was getting more and more interesting, It took me only 2 hrs to finish the parser.

This is very simple parser written in C++ using STL. Parser will validate the correctness of the configuration file and allows you to query for the keys using template functions. You just need to include the header and .cpp file for using this.
Typical Usage is as follows

    #include "IniParser.h"
    #include <assert.h>
    int main( int argc, char ** argv){
        IniParser myparser;
        int intValue;
        try {
            myparser.Load(argv[1]);
            myparser.QueryKeyValue<int>("Section4","KeyInt",intValue);
        } catch ( IniParseException &e) {
            std::cout << e.what();
            exit (1);
        }
        return 0;
    }
void IniParser::Load( const std::string &filename)

takes file name and parse the file, if found any error then it will throws

IniParseException

exception
Querying Key value
Following API will need to use for querying key.

    void QueryKeyValue(const std::string &section,
                            const std::string &key,
                            ValueType &defaultValue = ValueType())
                            const throw (IniParseException)

Usage of the API is as follows
If you know the type of the value is int then call this function as follows

myparser.QueryKeyValue<int>("Section4","KeyInt",intValue);

If this call does not throw any exception then intValue will have required value.
Will add writing/editing capabilities soon of course when India is again loosing next Test Match.

Advertisements

Facebook puzzle Breathalyzer

To safeguard against the dreaded phenomenon of wall posting while drunk, Facebook is implementing a feature that detects when post content is too garbled to have been done while sober and informs the user that they breathalyzer-puzzleneed to take an online breathalyzer test before being allowed to post.

My Solution:
Your are given input sentence and dictionary.
Your program must print out the minimum number of changes necessary to turn all words in the input wall post into accepted words as defined by the word list file. Words may not be joined together, or separated into multiple words. A change in a word is defined as one of the following:
Replacing any single letter with another letter.
Adding a single letter in any position.
Removing any single letter.
All the 3 rules above shouts for Levenshtein distance, which is a metric for measuring the amount of difference between the two sequences.

After doing lot of search for the data structure to solve this problem I came across with the interesting datastructure. A BK-tree is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller [1] specifically adapted to discrete metric spaces. For simplicity, let us consider integer discrete metric d(x,y). Then, BK-tree is defined in the following way. An arbitrary element a is selected as root node. The root node may have zero or more subtrees. The k-th subtree is recursively built of all elements b such that d(a,b) = k. BK-trees can be used for approximate string matching in a dictionary [2].

BK-Trees were first proposed by Burkhard and Keller in 1973, in their paper “Some approaches to best match file searching”. The only copy of this online seems to be in the ACM archive, which is subscription only. Further details, however, are provided in the excellent paper “Fast Approximate String Matching in a Dictionary”. Good Explanation about the BK-Tree can be found at Damn Cool Algorithms, Part 1: BK-Trees

Here is how I coded the solution.

Interface declaration for BK-Tree is as follows:

class BkTree {
    public:
        BkTree();
        ~BkTree();
        void insert(std::string m_item);
        int  getWithinDistance(std::string center, size_t k);
        std::vector<std::string> wordVector;
        void solve();
        int BuildDictionary();
        int ReadInputFile(const char *inpFileName);
    private:
        size_t EditDistance( const std::string &s, const std::string &t );
        struct Node {
            std::string m_item;
            size_t m_distToParent;
            Node *m_firstChild;
            Node *m_nextSibling;
            Node(std::string x, size_t dist);         
            ~Node();
        };
        Node *m_root;
    protected:
};

EditDistance is implemented below using dynamic programming approach.

size_t BkTree::EditDistance( const std::string &left, const std::string &right ) {
    size_t asize = left.size();
    size_t bsize = right.size();
    std::vector<size_t> prevrow(bsize + 1);
    std::vector<size_t> thisrow(bsize + 1);
    for(size_t i = 0; i <= bsize; i++)
        prevrow[i] = i;
    for(size_t i = 1; i <= asize; i++) {
        thisrow[0] = i;
        for(size_t j = 1; j <= bsize; j++) {
            thisrow[j] = std::min(prevrow[ j - 1] + size_t(left[ i - 1] != right[ j - 1]), 
                    1 + std::min(prevrow[j],thisrow[ j - 1]) );
        }
        std::swap(thisrow,prevrow);
    }
    return prevrow[bsize];
}

Build the dictionary using BK-Tree.

int BkTree::BuildDictionary) {
    std::ifstream dictFile("/var/tmp/twl06.txt");
    if ( dictFile.peek() == EOF ) {
        return -1;
    } 
    std::string line; 
    if (dictFile.is_open()) {
        while (! dictFile.eof() ) {  
            std::getline (dictFile,line);
            trim(line);
            std::transform(line.begin(), line.end(), line.begin(), ::tolower);
            insert(line);
        }
        dictFile.close();
    } else {
        return EXIT_FAILURE;
    }
    return 0;
}

Try getting a new word from a dictionary using a BK-Tree based dictionary. Start with Edit Distance equals to 0, if found no changes are required and keep incrementing Edit Distance till you find some word in the dictionary.

int BkTree::getWithinDistance(std::string center, size_t k) {
    if( !m_root ) return 0;
    int found = 0;
    std::queue< Node* > nodeQueue;
    nodeQueue.push( m_root );
    while( !nodeQueue.empty() ) {
        Node *t = nodeQueue.front(); 
        nodeQueue.pop();
        size_t d = EditDistance( t->m_item, center );
        if( d <= k ) { 
            found++; 
            break;
        }
        Node *pChild = t->m_firstChild;
        while( pChild ) {
            if( d - k <= pChild->m_distToParent && pChild->m_distToParent <= d + k )
                nodeQueue.push(pChild);
            pChild = pChild->m_nextSibling;
        }
    }
    return found;
}

Complete code with tested cases are uploaded on my .

Programming Challenge-II Adding spaces to a sentence

Let’s say you have a phrase without any spaces – eg. “thisisawesome”. Given a dictionary, how would you add spaces in this string?
Here is my simpler version

Build a set of all the words ( from a dictionary )
Have one pointer left, which points to start of the string
have another pointer right which pointers to the end of the string
try finding the word ( left .. right ) in the set
If found you got the word
if not, reduce right pointer by 1
goto step 4
if you find the word, move left equal to left + size of the word found
continue this till left is not equal to right.

#include <set>
#include <fstream>
#include <string>
#include <iostream>
std::set<std::string> pDict;
int BuildDictionary(const char *filename) {
    std::ifstream dictFile(filename);
    if ( dictFile.peek() == EOF ) {
        return -1;
    } 
    std::string line; 
    if (dictFile.is_open()) {
        while (! dictFile.eof() ) {  
            std::getline (dictFile,line);
            pDict.insert(line);
        }
        dictFile.close();
    } else {
        return EXIT_FAILURE;
    }
    return 0;
}

int main ( int argc, char **argv) {
    BuildDictionary(argv[1]);
    /*pDict.insert("i");
    pDict.insert("this");
    pDict.insert("saw");
    pDict.insert("is");
    pDict.insert("a");
    pDict.insert("some");
    pDict.insert("awesome");*/
    std::string word(argv[1]);
    std::string::iterator left = word.begin();
    std::string::iterator right = word.end();
    std::string::iterator rightMoving = left + 1;
    while ( left != right ) {        
        std::string tempWord(left, right);
        if ( pDict.find(tempWord) != pDict.end()) {
            std::cout << tempWord << " ";
            left = left + tempWord.size();
            right = word.end();
            continue;
        } else  {
            right--;
        }        
    }
    return 0;
}

Experiments with inotify.

inotify_diagram2-150x150 inotify is a Linux kernel subsystem that acts to extend filesystems to notice changes to the filesystem, and report those changes to applications. It replaces an earlier facility, dnotify, which had similar goals.

One major use is in desktop search utilities like Beagle, where its functionality permits reindexing of changed files without scanning the filesystem for changes every few minutes, which would be very inefficient. By being told that a file has changed directly by the kernel, rather than actively looking, Beagle and such utilities can achieve change-to-reindexing times of only about a second.

Code can be downloaded from : File System Watcher

Note: Windows do have similar API FindFirstChangeNotification , have not tried but details can be found at FindFirstChangeNotification

IntelliSense in VIM for C++ developers.

IntelliSense is Microsoft‘s implementation of autocompletion, best known for its use in the Microsoft Visual Studio integrated development environment. In addition to completing the symbol names the programmer is typing, IntelliSense serves as documentation and disambiguation for variable names, functions and methods using reflection.

Vim is very powerful tool and can have autompletion  with help of couple of configurations and Omni completion.

Here is my .vimrc file. See Omni completion for details installation instruction.

set enc=utf-8
set fenc=utf-8
set termencoding=utf-8
set nocompatible
set autoindent
set smartindent
set tabstop=4 
set shiftwidth=4
set expandtab
set textwidth=120
syntax on
set number
set showmatch
set comments=sl:/*,mb:\ *,elx:\ */
set tags+=~/.vim/tags/cpp
au BufNewFile,BufRead,BufEnter *.cpp,*.hpp set omnifunc=omni#cpp#complete#Main
let OmniCpp_NamespaceSearch = 1
let OmniCpp_GlobalScopeSearch = 1
let OmniCpp_ShowAccess = 1
let OmniCpp_ShowPrototypeInAbbr = 1 
let OmniCpp_MayCompleteDot = 1
let OmniCpp_MayCompleteArrow = 1 
let OmniCpp_MayCompleteScope = 1
let OmniCpp_DefaultNamespaces = ["std", "_GLIBCXX_STD"]
au CursorMovedI,InsertLeave * if pumvisible() == 0|silent! pclose|endif
set completeopt=menuone,menu,longest,preview
filetype on
filetype plugin on
set nocp
autocmd FileType c set omnifunc=ccomplete#CompleteCpp

Here is how it works in VIM:

Screenshot-1

Screenshot1