Simplest Codings

Harnessing Sentiment Analysis with Java: A Step-by-Step Guide using NLP

noreply@blogger.com (Varun) — Sat, 03 Feb 2024 18:33:00 +0000

Sentiment analysis, a powerful application of Natural Language Processing (NLP), allows developers to gain insights into the emotions expressed in textual data. In this article, we'll explore how to perform sentiment analysis in Java using the Stanford NLP library. We'll guide you through setting up a Maven project, compiling the code, and running it with practical examples.

Prerequisites

Get IntelliJ Idea from https://www.jetbrains.com/idea/download.

You can skip this and use any other IDE as well. The steps for setting up a maven project will be different for each IDE.

Step 1: Create a New Project

Open IntelliJ IDEA and click on "Create New Project."
Choose "Maven" as the project type and click "Next."
Set the "GroupId" to com.simplestcodings and "ArtifactId" to SentimentAnalysis.
Click "Next" and then "Finish."

Step 2: Add Dependencies

Open the pom.xml file in the editor and replace the content with this section:


<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.simplestcodings</groupId>
    <artifactId>nlp</artifactId>
    <version>1.0-SNAPSHOT</version>

    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    </properties>

    <dependencies>
        <dependency>
            <groupId>edu.stanford.nlp</groupId>
            <artifactId>stanford-corenlp</artifactId>
            <version>4.5.6</version>
        </dependency>
        <dependency>
            <groupId>edu.stanford.nlp</groupId>
            <artifactId>stanford-corenlp</artifactId>
            <version>4.5.6</version>
            <classifier>models</classifier>
        </dependency>
        <dependency>
            <groupId>org.slf4j</groupId>
            <artifactId>slf4j-simple</artifactId>
            <version>1.7.32</version>
        </dependency>
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>1.18.30</version>
            <scope>provided</scope>
        </dependency>
    </dependencies>

</project>

Step 3: Create Project Structure

Right-click on the src directory in your project and choose "New" -> "Package."
Name it com.simplestcodings.
Inside the com.simplestcodings package, create a new Java class named SentimentAnalysis.

Step 4: Configure Properties

Right-click on the src directory and create a new directory named resources. Inside the resources directory, create a file named application.properties with the following content:

tokenize.whitespace=true
ssplit.eolonly=true
annotators = tokenize, ssplit, parse, sentiment

Step 5: Write Code

Replace the contents of SentimentAnalysis.java with the code provided below


package com.simplestcodings;

import edu.stanford.nlp.ling.CoreAnnotations;
import edu.stanford.nlp.pipeline.Annotation;
import edu.stanford.nlp.pipeline.StanfordCoreNLP;
import edu.stanford.nlp.sentiment.SentimentCoreAnnotations;
import edu.stanford.nlp.util.CoreMap;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class SentimentAnalysis {

    public static void main(String[] args) {
        // Initialize the Stanford NLP pipeline
        StanfordCoreNLP pipeline = new StanfordCoreNLP("application.properties");

        // Sample text for sentiment analysis
        String text = "Simplest codings is the best place to learn and grow. I am glad to be here.";

        // Perform sentiment analysis
        String sentiment = getSentiment(text, pipeline);

        // Display the result
        log.info("Text: {}, Sentiment: {}",text, sentiment);

        // Another Sample text for sentiment analysis
        text = "I hate this place. I am not coming back here again. I am very disappointed.";

        // Perform sentiment analysis
        sentiment = getSentiment(text, pipeline);

        // Display the result
        log.info("Text: {}, Sentiment: {}",text, sentiment);
    }

    private static String getSentiment(String text, StanfordCoreNLP pipeline) {
        // Create an Annotation object with the input text
        Annotation annotation = new Annotation(text);

        // Run all the NLP annotators on the text
        pipeline.annotate(annotation);

        // Extract the sentiment from the annotation
        CoreMap sentence = annotation.get(CoreAnnotations.SentencesAnnotation.class).get(0);
        String sentiment = sentence.get(SentimentCoreAnnotations.SentimentClass.class);

        return sentiment;
    }
}

Step 6: Run the Code

Right-click on the SentimentAnalysis class and select "Run SentimentAnalysis.main()". Observe the output in the Run console, which should display the sentiment of the provided text.

You have successfully set up and run a sentiment analysis Java project using the Stanford NLP library in IntelliJ IDEA. Feel free to explore more examples and experiment with different texts to gain insights into the sentiment analysis capabilities of Java and NLP. Happy coding!

Cracking the Piggy Bank Puzzle: A Java Adventure in Dynamic Programming

noreply@blogger.com (Varun) — Wed, 20 Dec 2023 19:57:00 +0000

Hey there, intrepid coders! Today, we're diving into a piggy bank heist… of the intellectual kind, of course! We'll be using a powerful technique called Dynamic Programming (DP) to crack the code of a mischievous piggy bank and unlock its hidden treasures. Buckle up, because this adventure requires both logic and a dash of mathematical magic.

Imagine a piggy bank with compartments numbered 1 to N. Each compartment holds a certain amount of coins. Your mission is to maximise the total coins you can collect by following these two rules:

You can only start at compartment 1 and move rightward, collecting all the coins in a compartment before proceeding.
You can either skip a compartment (earning you 0 coins) or rob a compartment, but robbing two consecutive compartments is forbidden.

This might seem tricky, but DP comes to the rescue! It breaks down the problem into smaller, overlapping subproblems and cleverly stores the solutions, saving you from redundant calculations. Think of it like mapping a treasure hunt – each solution to a subproblem guides you towards the bigger prize.


class PiggyBankBreaker {

    private final int[] coins; // Array storing coins in each compartment (1-indexed)
    private final int[] maxCoins; // DP array to store max achievable coins at each position (0-indexed)

    public PiggyBankBreaker(int[] coins) {
        this.coins = coins; // Copy original coin values
        this.maxCoins = new int[coins.length + 1]; // Allocate DP array with space for starting point (index 0)
    }

    public int crackPiggyBank() {
        // Base case: No coins at starting point
        maxCoins[0] = 0;

        // Loop through each compartment from index 1 (inclusive)
        for (int i = 1; i <= coins.length; i++) {
            // Option 1: Rob current compartment + max from 2 positions back (non-consecutive)
            int robCurrent;

            // Check if robbing current is even possible (avoid accessing coins[-1])
            if (i >= 3) {
                robCurrent = coins[i - 1] + maxCoins[i - 3];
            } else {
                // Default to skipping for initial positions where robbing isn't valid
                robCurrent = 0;
            }

            // Option 2: Skip current compartment and take max from previous position (consecutive)
            int skipCurrent = maxCoins[i - 1];

            // Choose the option that yields more coins
            maxCoins[i] = Math.max(robCurrent, skipCurrent);
        }

        // Return the maximum achievable coins from the last compartment
        return maxCoins[coins.length];
    }

    public static void main(String[] args) {
        // Example piggy bank with coins
        int[] coins = {2, 3, 1, 4, 5, 7, 10};

        PiggyBankBreaker breaker = new PiggyBankBreaker(coins);
        int maxLoot = breaker.crackPiggyBank();
        System.out.println("Maximum amount you can collect: " + maxLoot);
    }
}

This Java code solves the piggy bank problem, where you maximise the coins collected while adhering to two rules:

Start at compartment 1 and move rightward, collecting all coins in each compartment.
You can either skip or rob a compartment, but not two consecutive compartments.

The code utilises Dynamic Programming (DP) to efficiently solve this problem by breaking it down into smaller, overlapping subproblems. Here's a breakdown of the key aspects:

The method calculates the maximum coins achievable from any starting point.
Base case: maxCoins[0] = 0 since no coins are earned before starting.
Loop: Iterates through each compartment (index 1 to length).
Rob current option:
- Calculates robCurrent by adding the current coin value (coins[i - 1]) to the maximum coins achievable two positions back (maxCoins[i - 3]).
- Fix: A conditional statement (i >= 3) ensures this calculation only happens for valid positions (avoiding coins[-1] access).
- Otherwise, robCurrent is set to 0, mimicking skipping the compartment for initial positions.
Skip current option: Simply takes the maximum coins from the previous position (maxCoins[i - 1]).
Comparison: Chooses the maximum value between robCurrent and skipCurrent and stores it in maxCoins[i]. This ensures the optimal decision is recorded for future subproblems.
Final result: The last element maxCoins[coins.length] represents the maximum achievable coins from the starting point (compartment 1).

Longest common subsequence in Java

noreply@blogger.com (Varun) — Wed, 20 Dec 2023 15:17:00 +0000

Longest Common Subsequence (LCS)

It's the longest sequence of characters that is present in the same relative order within two or more strings.
It doesn't have to be a contiguous substring; the characters can appear in different positions within the original strings.

Understanding the Problem

Imagine two strings, written vertically on separate columns.
The goal is to find the longest sequence of characters that appears in the same order within both strings, even if they're not consecutive.

Character Grid

Create a grid where each row represents a character from the first string, and each column represents a character from the second string.
Fill each cell with a color indicating whether the corresponding characters match (e.g., green) or not (e.g., white).

Tracing Paths

Start at the top-left corner of the grid.
Move diagonally down-right only when characters match (green cells).
If characters don't match, move either down or right to continue searching for matches.
The path you take represents the LCS.

Visualize the LCS

Highlight the cells along the longest path with a bolder color or border.
The characters in those cells, read in order, form the LCS.

Example:

Consider strings "AGGTAB" and "GXTXAYB":



LCS: "GTAB" (highlighted cells)

Algorithm

Dynamic Programming Table:
- Create a 2D table dp with dimensions (m+1) x (n+1), where m and n are the lengths of the two strings.
- Fill the first row and column with 0s, indicating no LCS for empty strings.
Filling the Table:
- Iterate through the table, starting from dp[1][1].
- For each cell dp[i][j]:
  - If the characters at indices i-1 and j-1 in the strings match:
    - Set dp[i][j] = dp[i-1][j-1] + 1 (add 1 to the LCS length of the previous substrings).
  - Else:
    - Set dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the maximum LCS length from the previous options).
Reconstructing the LCS:
- Start from the bottom-right corner of the table (dp[m][n]).
- Backtrack:
  - If the characters at indices i-1 and j-1 match, add the character to the LCS and move diagonally up (i--, j--).
  - Else, move to the cell with the maximum value (either i-- or j--).
- Reverse the constructed LCS string to get the correct order.



public class LCS {

    public static String lcs(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        int[][] dp = new int[m + 1][n + 1];

        // Build the table in a bottom-up manner
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Reconstruct the LCS
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs.append(str1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // Reverse the LCS string
        return lcs.reverse().toString();
    }

    // Example usage for testing
    public static void main(String[] args) {
        System.out.println(lcs("ABCDEFG", "BCDGK"));
        System.out.println(lcs("AGGTAB", "GXTXAYB"));
        System.out.println(lcs("ABCDE", "A"));
        System.out.println(lcs("A", "BCDEF"));
    }
}

Explanation for code

1. lcs() Method:

Takes two strings as input.
Uses dynamic programming to find the longest common subsequence (LCS).
Returns the LCS string.

Steps

Create a DP Table: Stores the lengths of LCSs for substrings of different lengths.
Fill the DP Table:
- Iterates through characters of both strings.
- For each cell, calculates the length of the LCS based on previous calculations:
  - If characters match, add 1 to the LCS length of the previous substrings.
  - If not, take the maximum LCS length from the previous options.
Reconstruct the LCS: Backtracks through the DP table to find the characters in the LCS.
Reverse the LCS: Since it's built backward, reverse it before returning.

Take away points

Bottom-up approach: Builds the solution from smaller subproblems to the final LCS.
Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
Time complexity: O(mn), where m and n are string lengths.
Space complexity: O(mn), due to the DP table.

Knapsack Problem implementation in Java

noreply@blogger.com (Varun) — Wed, 20 Dec 2023 14:59:00 +0000

Imagine a hiker's backpack (the knapsack) with limited space (capacity).

They have a collection of items, each with a value (usefulness) and a weight (space it occupies).

The goal is to fill the backpack with the most valuable combination of items, without exceeding its weight capacity.

Visualizing the Items

Item 1:  (value 60, weight 10)
Item 2:  (value 100, weight 20)
Item 3:  (value 120, weight 30)

The Knapsack

Decision-Making

Can't fit all items directly (total weight 60).
Optimal choice would be to put these items in the bag

Item: {value: 120, weight: 30}
Item: {value: 100, weight: 20}

Optimal Solution

KNAPSACK  (capacity 50)
     (value 120, weight 30)

Key Points

Knapsack represents a resource constraint (limited capacity).
Items represent choices with associated values and constraints (weight).
Goal is to maximize value within the constraint.
Often involves trade-offs and strategic decision-making.

In formal language, given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, find the subset of items that maximizes the total value while fitting within the weight capacity.

Dynamic Programming Approach

Create a table dp:
- Dimensions: (n + 1) x (W + 1), where n is the number of items and W is the knapsack capacity.
- dp[i][w] stores the maximum value achievable using items up to the i-th item and with a maximum weight of w.
Fill the table:
- Base cases:
  - dp[0][w] = 0 for all w (no items, value is 0).
  - dp[i][0] = 0 for all i (zero weight capacity, value is 0).
- Recursive formula:
  - dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w (Choose between including or excluding the i-th item)
  - dp[i][w] = dp[i-1][w] otherwise (Item cannot be included due to weight constraint)
Solution:

The maximum value is dp[n][W] (using all items with the knapsack capacity).
Backtrack to find the selected items.


import java.util.ArrayList;
import java.util.List;

public class Knapsack {

    public static List knapsack(List items, int capacity) {
        int[][] dp = new int[items.size() + 1][capacity + 1];

        // Build table dp[][] in a bottom-up manner
        for (int i = 0; i <= items.size(); i++) {
            for (int w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (items.get(i - 1).weight <= w) {
                    dp[i][w] = Math.max(items.get(i - 1).value + dp[i - 1][w - items.get(i - 1).weight], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // Reconstruct the solution
        List selectedItems = new ArrayList<>();
        int i = items.size(), w = capacity;
        while (i > 0 && w > 0) {
            if (dp[i][w] != dp[i - 1][w]) {
                selectedItems.add(items.get(i - 1));
                w -= items.get(i - 1).weight;
            }
            i--;
        }

        return selectedItems;
    }

    public static void main(String[] args) {
        List items = new ArrayList<>();
        items.add(new Item(60, 10));
        items.add(new Item(100, 20));
        items.add(new Item(120, 30));
        int capacity = 50;

        List selected = knapsack(items, capacity);
        System.out.println("Selected items: " + selected);
    }

    public static class Item {
        int value;
        int weight;

        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Item: {value: " + value + ", weight: " + weight + "}";
        }
    }
}

Explanation of code

1. Item Class:

Represents an item with its value and weight.

2. knapsack() Method:

Takes a list of items and a knapsack capacity as input.
Uses dynamic programming to solve the 0-1 Knapsack Problem.
Returns a list of selected items that maximize the total value without exceeding the capacity.

Steps

Create a 2D DP array: Stores intermediate results for subproblems.
Fill the DP array:
- Iterate through items and capacities.
- For each cell, calculate the maximum value achievable considering the current item and remaining capacity.
Reconstruct the solution: Backtrack through the DP array to find the selected items.

Take away points

Bottom-up approach: Builds the solution from smaller subproblems to the final solution.
Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
Time complexity: O(nW), where n is the number of items and W is the capacity.
Space complexity: O(nW), due to the DP array.

Dijkstra algorithm implementation in Java

noreply@blogger.com (Varun) — Wed, 20 Dec 2023 14:40:00 +0000

Purpose

Finds the shortest paths from a single source vertex to all other vertices in a weighted graph.
Commonly used in GPS navigation, network routing, and logistics planning.

Key Concepts

Weighted Graph: A set of vertices (nodes) connected by edges with associated weights (distances, costs, etc.).
Source Vertex: The starting point for finding shortest paths.
Shortest Path: The path with the minimum total weight between two vertices.

Algorithm Steps

Initialization:
- Create a set S to store visited vertices (initially empty).
- Initialize an array distances with infinite values for all vertices except the source, which is set to 0.
- Create a priority queue Q to store vertices, prioritized by their tentative distances.
- Add the source vertex to Q.
Exploration Loop:
- While Q is not empty:
  - Extract the vertex u with the minimum distance from Q.
  - Add u to the set S (mark as visited).
  - For each neighbor vertex v of u:
    - If v is not visited and the distance to v through u is shorter than its current distance:
      - Update the distance to v in the distances array.
      - Add v to the priority queue Q (or update its priority if already present).
Result:
- The distances array now contains the shortest distances from the source vertex to all other vertices.
- To reconstruct the actual shortest paths, keep track of the predecessor of each vertex during the exploration.



import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;

public class Dijkstra {

    public static List dijkstra(Graph graph, int source) {
        int[] distances = new int[graph.numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(i -> distances[i]));
        pq.offer(source);

        boolean[] visited = new boolean[graph.numVertices];
        while (!pq.isEmpty()) {
            int u = pq.poll();
            visited[u] = true;
            for (Edge edge : graph.adjacencyList.get(u)) {
                int v = edge.to;
                int weight = edge.weight;
                if (!visited[v] && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                    pq.offer(v);
                }
            }
        }

        return Arrays.stream(distances).boxed().collect(Collectors.toList());
    }

    public static Graph createRandomGraph(int numVertices) {
        Graph graph = new Graph(numVertices);
        Random random = new Random();
        // Add edges with random weights
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                // Decide whether to create an edge with 50% probability
                if (random.nextBoolean()) {
                    int weight = random.nextInt(10) + 1; // Random weight between 1 and 10
                    graph.addEdge(i, j, weight);
                    graph.addEdge(j, i, weight); // Add reverse edge for undirected graph (if needed)
                }
            }
        }
        return graph;
    }

    public static void main(String[] args) {
        // Create a sample graph
        Graph graph = createRandomGraph(9);
        graph.visualize();
        int source = 0;
        List distances = dijkstra(graph, source);
        System.out.println("Shortest distances from " + source + ": " + distances);
    }

    public static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static class Graph {
        int numVertices;
        List> adjacencyList;

        Graph(int numVertices) {
            this.numVertices = numVertices;
            adjacencyList = new ArrayList<>();
            for (int i = 0; i < numVertices; i++) {
                adjacencyList.add(new ArrayList<>());
            }
        }

        void addEdge(int from, int to, int weight) {
            adjacencyList.get(from).add(new Edge(to, weight));
        }

        void visualize() {
            System.out.println("Graph Visualization:\n");
            for (int vertex = 0; vertex < numVertices; vertex++) {
                System.out.print(vertex + " -> ");
                for (Edge edge : adjacencyList.get(vertex)) {
                    System.out.print(edge.to + "(" + edge.weight + ") ");
                }
                System.out.println();
            }
        }
    }
}

Explanation of code

Graph Representation
- The Graph class models a graph using an adjacency list, where each vertex stores a list of its connected edges and their weights.
- The Edge class encapsulates the destination vertex and weight of an edge.
Dijkstra's Algorithm Implementation
- The dijkstra(Graph, source) method implements the algorithm's logic:
  - It maintains a priority queue to explore vertices in order of their tentative distances.
  - It iteratively relaxes edges to update distances and explore reachable vertices.
  - It ultimately returns a list of the shortest distances from the source vertex to all other vertices.
Random Graph Generation
- The createRandomGraph(numVertices) method generates a graph with a specified number of vertices and randomly assigns edges with weights between 1 and 10.

Ternary Search Tree Implementation in C++

noreply@blogger.com (Varun) — Wed, 12 Oct 2016 17:11:00 +0000

A Ternary Search Tree is a trie which leverages concepts of Binary Search Tree as well. A Ternary Search Tree is as memory efficient as Binary Search Trees and time efficient as a Trie.

It is an efficient data structure to store and search large number of strings.

A node in a Ternary Search Tree comprises of these fields :

Left pointer - Points to Ternary Search Tree containing all strings alphabetically lesser than current node's data
Right pointer - Points to Ternary Search Tree containing all strings alphabetically greater than current node's data
Equal pointer - Points to Ternary Search Tree containing all strings alphabetically equal to current node's data
End of string flag - Flag indicating the end of string
Data - Actual data in the form of single character

Ternary Search Tree Node

For example, consider adding these strings in the same order into a Ternary Search Tree :

"Lead"
"Leader"
"Leads"
"Late"
"State"

Let's build a visualization of ternary search tree out of above data :

"Lead"
"Leader"
"Leads"
"Late"
"State"



//TST.h
#ifndef TST_H
#define TST_H
//#define DEBUG_PROGRAM_MEMORY

//Node of a Ternary Search Tree
typedef struct TSTNode{
 char data; //Actual data stored in form of character
 bool bEOS; //flag marking end of string
 struct TSTNode* left;   //All character data less than this node
 struct TSTNode* eq;  //All character data equal to this node
 struct TSTNode* right; //All character data greater than this node
}TSTNode;

//Inserts a string in the TST
TSTNode* Insert(TSTNode* root, char* str); 

//Prints all strings in the TST
void PrintAllStringsInTST(TSTNode* root);

//Gets the length of maximum length string in TST
int MaxLenStringLen(TSTNode *root);

//Deleted the complete TST
void DeleteTST(TSTNode *root);

//Search a pattern in TST
bool SearchTST(TSTNode *root, char* pattern);

//Prints 
#ifdef DEBUG_PROGRAM_MEMORY
#include <map>

static std::map<TSTNode*, char> mem_addrs;
void CheckTSTMem();
#endif

#endif



//TST.cpp
#include <iostream>
#define DEBUG_PROGRAM_MEMORY

#include "TST.h"
#include <cstdlib>
#include <utility>

#define MAX_LEN 1024

#define MAX( a, b, c ) ((a)>(b) ? ((a)>(c) ? (a):(c)) : ( (b)>(c) ? (b):(c) ))


TSTNode* Insert(TSTNode* root, char* str)
{
 if(root == NULL)
 {
  root = (TSTNode*)malloc(sizeof(TSTNode));
  if(root == NULL)
  {
   std::cout<<"Memory allocation failed"<<std::endl;
   return NULL;
  }

  //Insert first character of string in the root node
  root->data = *str;
#ifdef DEBUG_PROGRAM_MEMORY
  mem_addrs.insert(std::make_pair(root, root->data));
#endif
  root->bEOS = false;
  root->left = root->eq = root->right = NULL;
 }
 
 if(*str  < root->data)
  root->left = Insert(root->left, str);
 else if (*str == root->data)
 {
  if(*(str + 1))
   root->eq = Insert(root->eq, str + 1);
  else
   root->bEOS = true;
 }
 else
  root->right = Insert(root->right, str);
 
 return root; 
}

//Helper to print the strings in TST
static void PrintHelper(TSTNode* root, char* buffer, int depth)
{
 if (root)
 {
  // Traverse the left subtree
  PrintHelper(root->left, buffer, depth);

  buffer[depth] = root->data;
  //Once end of string flag is encountered, print the string
  if (root->bEOS)
  {
   buffer[depth + 1] = '\0';
   std::cout<< buffer << std::endl;
  }

  // Traverse the middle subtree
  PrintHelper(root->eq, buffer, depth + 1);

  // Traverse the right subtree
  PrintHelper(root->right, buffer, depth);
 }
}

// Function to print TST's strings
void PrintAllStringsInTST(TSTNode* root)
{
 char buffer[MAX_LEN];
 PrintHelper(root, buffer, 0);
}

bool SearchTST(TSTNode *root, char* pattern)
{
 while (root != NULL)
 {
  if (*pattern < root->data)
   root = root->left;
  else if (*pattern == root->data)
  {
   //If end of string flag is found and the pattern length is also exhausted, 
   //we can safely say that the pattern is present in the TST
   if (root->bEOS && *(pattern + 1) == '\0')
    return true;
   pattern++;
   root = root->eq;
  }
  else
   root = root->right;
 }

 return false;
}

//Function to determine largest 
int MaxLenStringLen(TSTNode *root)
{
 if (root == NULL)
  return 0;

 int leftLen = MaxLenStringLen(root->left);
 int middleLen = MaxLenStringLen(root->eq) + 1;
 int rightLen = MaxLenStringLen(root->right);

 return MAX( leftLen, middleLen, rightLen);
}

void DeleteTST(TSTNode *root)
{
 TSTNode *tmp = root;
 if (tmp)
 {
  DeleteTST(tmp->left);
  DeleteTST(tmp->eq);
  DeleteTST(tmp->right);

#ifdef DEBUG_PROGRAM_MEMORY
  mem_addrs.erase(tmp);
#endif
  delete tmp;
 }
}

#ifdef DEBUG_PROGRAM_MEMORY
void CheckTSTMem()
{
 std::map<TSTNode*, char>::iterator itr = mem_addrs.begin();

 if (mem_addrs.size() == 0)
 {
  std::cout << "No memory leaks";
  return;
 }

 while (itr != mem_addrs.end()) 
 {
  std::cout << "Memory address " << itr->first<< " for \"" << itr->second << "\" has not been deallocated" << std::endl;
  ++itr;
 }
}
#endif



//Main.cpp
#include <iostream>
#include "TST.h"

int main(int argc, char** argv) {
 
 TSTNode *root = NULL;
 root = Insert(root, "boats");
 root = Insert(root, "boat");
 root = Insert(root, "bat");
 root = Insert(root, "bats");
 root = Insert(root, "stages");

 PrintAllStringsInTST(root);
 std::cout << "Maximum length string in this TST is of size "<< MaxLenStringLen(root) << std::endl;

 char *str = "hello";
 char *str1 = "bat";

 if (SearchTST(root, str) == false)
  std::cout << "\""<<str<<"\" not found in TST" << std::endl;
 else
  std::cout << "\"" << str << "\" is present in TST" << std::endl;

 if (SearchTST(root, str1) == false)
  std::cout << "\"" << str << "\" not found in TST" << std::endl;
 else
  std::cout << "\"" << str1 << "\" is present in TST" << std::endl;

 DeleteTST(root);

#ifdef DEBUG_PROGRAM_MEMORY
 CheckTSTMem();
#endif
 
 return 0;
}

String matching using KMP algorithm : C++ Implementation

noreply@blogger.com (Varun) — Sat, 24 Sep 2016 15:01:00 +0000

KMP Algorithm is one the well-known string matching algorithms. It finds a pattern in a string. The pattern can exist multiple times in the string. This implementation in C++ gives indexes of all such matches in the string to be searched.

e.g.

String to be searched : "ABCDBCAAB ABCDABCDABDE ABCDABD"
Pattern : "ABCD"

The result will be 4 index locations 0, 10, 14 and 23

However, there is a limitation of KMP algorithm where the pattern overlaps.

Consider this scenario :

String to be searched: "ABCABCABCA"
Pattern: "ABCA"
The result from KMP algorithm will be 0 and 6 locations. It cannot identify the overlapping matches like this:
ABCABCABCA
ABCABCABCA
ABCABCABCA



#include <iostream>
#include <cstdlib>

using namespace std;
#define MAX_MATCHES 100

//Array to store matched indexes
int FOUND[MAX_MATCHES];
//variable to store last index in FOUND array
static int l = 0;

//Partial match table
void kmp_table(string W, int *T )
{
 int pos = 2;
 int cnd = 0;
 int length = W.length();
 
 T[0] = -1;
 T[1] = 0;
 
 while( pos < length)
 {
  if(W[pos-1] == W[cnd])
  {
   T[pos] = cnd + 1;
   cnd++;
   pos++;
  }
  else if( cnd > 0)
   cnd = T[cnd];
  else
  {
   T[pos] = 0;
   pos++;
  }
 }
}

//Search function
void kmp_search(string S, string W)
{
 
 int m = 0; 
 int i = 0;
 int sizeS = S.length();
 int sizeW = W.length();
 
 int *T = new int[sizeof(int) * sizeW];
 
 kmp_table(W, T);
 
 while( (m + i) < sizeS)
 {
  if (W[i] == S[m + i]) 
  {
            if (i == (sizeW - 1))
            {
             //Add the start index of match in the FOUND table
             FOUND[l++] = m;
   }
    
            i++;
        }
        else
        {
            if (T[i] > -1)
            {
                m = m + i - T[i];
    i = T[i];
            }
            else
            {
                m = m + 1;
    i = 0;
            }
        }
 }
 
 delete(T);
}

int main()
{
 string S = "ABCDBCAAB ABCDABCDABDE ABCDABD";
 string W = "ABCD";
 
 kmp_search(S,W);
  
 for (int i = 0 ; i < l; i++)
  cout<<"Pattern found at "<< FOUND[i] <<endl; 
}

Component Object Model(COM) - Implementation in C++ -- Usage in C++, C#

noreply@blogger.com (Varun) — Tue, 24 Feb 2015 12:22:00 +0000

As per Microsoft "Component Object Model or COM is a platform-independent, distributed, object-oriented system for creating binary software components that can interact".
COM defines a standard (Object Model) and the implementation part is left to the developer. These objects can communicate within a process or across the processes, on the same or different machine with different programming languages.

Language requirement for COM :

1. Ability to create structures of pointers

2. Ability to call functions using pointers

Object-oriented languages such as C++ and Smalltalk provide programming mechanisms that simplify the implementation of COM objects, but languages such as C, Java, and VBScript can be used create and use COM objects.

Object's data is accessed using interfaces. The functions of this interface are called methods. The pointers to these interfaces enables to call the methods.

More information on COM is available at the MSDN .

In a nutshell , COM provides interfaces which can be implemented in different languages and can be used over distributed platforms.

To provide portability across platforms and programming languages, COM uses interface definition in platform-independent language, IDL(Interface Definition Language).

Steps involved to create COM interface:

Define the interface/s in .idl file.
Compile the .idl file using IDL compiler(platform and language specific) to generate language and platform specific code.
Implement these interface/s in the specific language.
Use it.

In our example, we are using MIDL compiler to generate the C++ specific code and DLL.
We will use ATL to make the implementation easier. ATL is the Active Template Library, a set of template-based C++ classes with which you can easily create small, fast Component Object Model (COM) objects. It has special support for key COM features including: stock implementations of IUnknown, IClassFactory, IClassFactory2, and IDispatch; dual interfaces; standard COM enumerator interfaces; connection points; tear-off interfaces; and ActiveX controls.

We are using Visual Studio 2005 for our example. Visual Studio provides ATL project wizard which will help a lot and make the process easy.

Steps to generate COM DLL:

Create a new project in Visual Studio File->New->Project->Visual C++ -> ATL => ATL Project.
Give the project name as Calculator as we will be implementing a calculator interface using COM.
Choose DLL(Dynamic-link library) in the Application Settings -> Finish.
This structure will be visible once the project is created.
Now add a class following the image as below. Right click on the project Add->Class.
We will now add a COM Object using ATL Simple Object.
Give the name of class as CalculatorImpl (This defines the implentation of the interface). You can see under the panel C++ these four areas are updated -> Short Name, .h file, Class, .cpp file to be as CalculatorImpl, CalculatorImpl.h , CCalculatorImpl and CalculatorImpl.cpp respectively . Also in the panel COM below, these four areas are also updated - CoClass, Type, Interface and ProgID. Change these according to the image below.
Choose the Options for the COM Object as below, then click on Finish.
After these changes, the Calculator.idl file will look like this:

Here, the declaration for interface ICalculator is added. ICalculator implements IDispatch interface. IDispatch is the interface that exposes the OLE Automation protocol. It is one of the standard interfaces exposed by COM. The IDispatch interface inherits from the IUnknown interface. More information on IDispatch can be found here. You can also see the declaration of the Type Library CalculatorLib which declares a coclass Calculator as well. This CoClass creates a COM object, which can implement a COM interface. The Type library information helps in creating .tlb file which is a binary file that stores information about a COM or DCOM object's properties and methods in a form that is accessible to other applications at runtime. Using a type library, an application or browser can determine which interfaces an object supports, and invoke an object's interface methods. This can occur even if the object and client applications were written in different programming languages. The COM/DCOM run-time environment can also use a type library to provide automatic cross-apartment, cross-process, and cross-machine marshaling for interfaces described in type libraries.
Now our interface is ready to have some methods. Switch to Class View beside Solution Explorer as shown in image below. Right click on ICalculator interface and add a method. Add->Add Method.
Give the method name as Add , check parameter attributes as 'in', parameter type DOUBLE, parameter name as Input1. Click on Add. You should see the parameter being added to the list box. Similarly add one more input parameter named Input2. Now add an output parameter with parameter type DOUBLE*, parameter name as pOutput, check parameter attributes as 'out' and 'retval'. Click on Add. Click on Next->Finish.

Similarly add three more methods Subtract, Multiply and Divide.
After adding the methods , you should see the functions' skeleton created in Calculator.idl and CalculatorImpl.cpp like this :
We will add the implementation in the skeleton.
Now compile the solution. It will generate Calculator.dll in the project output directory (e.g. for 64 bit Release configuration it is %PROJECT_HOME%\Calculator\Calculator\x64\Release by default)

Now we have our COM DLL. To use it , we need some code.

Steps to create sample C++ code to test COM DLL:

Create an Empty Win32 Console Project in Visual Studio
Create an Empty cpp file in the project (TestCalc.cpp)
Add the path to Calculator.h in Additional Include Directories in the project properties. Right click project -> Properties -> Configuration Properties -> C/C++ -> General.
Add Calculator_i.c in the Project Source.
Populate TestCalc.cpp with the contents given later in the blog post.
Run the executable(F5).

Note: One advantage using the Visual Studio to build our COM dll was that it registers the COM DLL by default. So we do not need to do it manually. This is the reason why we are able to run the test code even without the DLL being present in the System Path or adding it's path to PATH environment variable .

Now as we have been saying that the COM is interoperable between the languages/platform etc. Let's see some code in action.
We are going to use the COM DLL generated in C# application.

Before we go on using DLLs directly , let's be SMART and create .NET wrappers over COM DLL. Now you would ask what's that ??

The COM components has unmanaged code while .NET framework has managed code. Data types, method signatures, and error-handling mechanisms vary between managed and unmanaged object models
Code that executes under the control of the runtime is called managed code and the code that runs outside the runtime is called unmanaged code.

To simplify this, .NET wrappers are generated over existing COM components which allows unmanaged model to be converted to managed.
More information in this link.

Steps to create .NET wrapper from COM DLL:

Run this command from the output directory:

     tlbimp /machine: x64 Calculator.dll /out: Calculator_Wrapper.dll

It will generate Calculator_Wrapper.dll which is nothing but our .NET wrapper over COM.

Steps to create C# application to test COM DLL :

Create a Windows Application TestCalcCCharp from Visual Studio
Add a reference to the wrapper Calculator_Wrapper.dll
Create a simple form as per the code in the blog post.
Populate the functions to call the methods from COM.



// CalculatorImpl.cpp : Implementation of CCalculatorImpl

#include "stdafx.h"
#include "CalculatorImpl.h"

// CCalculatorImpl

STDMETHODIMP CCalculatorImpl::Add(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 + Input2;

 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Subtract(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 - Input2;
 
 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Multiply(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 * Input2;

 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Divide(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 / Input2;

 return S_OK;
}



//TestCalc.cpp
#include "Calculator.h"
#include <iostream>
#include <stdexcept>
using std::runtime_error; 

int main()
{
 HRESULT hr ;
 ICalculator      *calc = NULL;

 hr = CoInitialize(0);

 if(SUCCEEDED(hr))
    {
  hr = CoCreateInstance( CLSID_Calculator, NULL, 
            CLSCTX_INPROC_SERVER,
   IID_ICalculator, (void**) &calc);

        // If we succeeded then call the Add 
        // method, if it failed
        // then display an appropriate message to the user.
        if(SUCCEEDED(hr))
        {
            double ReturnValue;
   double a = 4;
   double b = 0;
   calc->Add(a, b, &ReturnValue);
            std::cout << "The answer for "<<a<<" + "<<b<<" is: " 
                << ReturnValue << std::endl;
            calc->Release(); 
        }
        else
        {
            std::cout << "CoCreateInstance Failed." << std::endl;
        }
    }
    // Uninitialize COM
    CoUninitialize();

}


//Form1.Designer.cs
namespace TestCalcCSharp
{
    partial class Form1
    {
        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.calcPanel = new System.Windows.Forms.GroupBox();
            this.groupBox1 = new System.Windows.Forms.GroupBox();
            this.logTextBox = new System.Windows.Forms.RichTextBox();
            this.label5 = new System.Windows.Forms.Label();
            this.label4 = new System.Windows.Forms.Label();
            this.label1 = new System.Windows.Forms.Label();
            this.divBtn = new System.Windows.Forms.Button();
            this.subBtn = new System.Windows.Forms.Button();
            this.addBtn = new System.Windows.Forms.Button();
            this.mulBtn = new System.Windows.Forms.Button();
            this.textBox3 = new System.Windows.Forms.TextBox();
            this.textBox2 = new System.Windows.Forms.TextBox();
            this.label3 = new System.Windows.Forms.Label();
            this.label2 = new System.Windows.Forms.Label();
            this.textBox1 = new System.Windows.Forms.TextBox();
            this.calcPanel.SuspendLayout();
            this.groupBox1.SuspendLayout();
            this.SuspendLayout();
            // 
            // calcPanel
            // 
            this.calcPanel.Controls.Add(this.groupBox1);
            this.calcPanel.Controls.Add(this.label5);
            this.calcPanel.Controls.Add(this.label4);
            this.calcPanel.Controls.Add(this.label1);
            this.calcPanel.Controls.Add(this.divBtn);
            this.calcPanel.Controls.Add(this.subBtn);
            this.calcPanel.Controls.Add(this.addBtn);
            this.calcPanel.Controls.Add(this.mulBtn);
            this.calcPanel.Controls.Add(this.textBox3);
            this.calcPanel.Controls.Add(this.textBox2);
            this.calcPanel.Controls.Add(this.label3);
            this.calcPanel.Controls.Add(this.label2);
            this.calcPanel.Controls.Add(this.textBox1);
            this.calcPanel.Location = new System.Drawing.Point(13, 13);
            this.calcPanel.Name = "calcPanel";
            this.calcPanel.Size = new System.Drawing.Size(450, 344);
            this.calcPanel.TabIndex = 0;
            this.calcPanel.TabStop = false;
            this.calcPanel.Text = "Calculator";
            // 
            // groupBox1
            // 
            this.groupBox1.Controls.Add(this.logTextBox);
            this.groupBox1.Location = new System.Drawing.Point(6, 238);
            this.groupBox1.Name = "groupBox1";
            this.groupBox1.Size = new System.Drawing.Size(438, 100);
            this.groupBox1.TabIndex = 34;
            this.groupBox1.TabStop = false;
            this.groupBox1.Text = "Logs";
            // 
            // logTextBox
            // 
            this.logTextBox.Location = new System.Drawing.Point(6, 19);
            this.logTextBox.Name = "logTextBox";
            this.logTextBox.Size = new System.Drawing.Size(432, 81);
            this.logTextBox.TabIndex = 33;
            this.logTextBox.Text = "";
            // 
            // label5
            // 
            this.label5.AutoSize = true;
            this.label5.Location = new System.Drawing.Point(254, 22);
            this.label5.Name = "label5";
            this.label5.Size = new System.Drawing.Size(37, 13);
            this.label5.TabIndex = 32;
            this.label5.Text = "Result";
            // 
            // label4
            // 
            this.label4.AutoSize = true;
            this.label4.Location = new System.Drawing.Point(163, 22);
            this.label4.Name = "label4";
            this.label4.Size = new System.Drawing.Size(37, 13);
            this.label4.TabIndex = 31;
            this.label4.Text = "Input2";
            // 
            // label1
            // 
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(83, 22);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(37, 13);
            this.label1.TabIndex = 30;
            this.label1.Text = "Input1";
            // 
            // divBtn
            // 
            this.divBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.divBtn.Location = new System.Drawing.Point(352, 134);
            this.divBtn.Name = "divBtn";
            this.divBtn.Size = new System.Drawing.Size(75, 36);
            this.divBtn.TabIndex = 29;
            this.divBtn.Text = "Divide";
            this.divBtn.UseVisualStyleBackColor = true;
            this.divBtn.Click += new System.EventHandler(this.divBtn_Click);
            // 
            // subBtn
            // 
            this.subBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.subBtn.Location = new System.Drawing.Point(125, 134);
            this.subBtn.Name = "subBtn";
            this.subBtn.Size = new System.Drawing.Size(75, 36);
            this.subBtn.TabIndex = 28;
            this.subBtn.Text = "Subtract";
            this.subBtn.UseVisualStyleBackColor = true;
            this.subBtn.Click += new System.EventHandler(this.subBtn_Click);
            // 
            // addBtn
            // 
            this.addBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.addBtn.Location = new System.Drawing.Point(14, 134);
            this.addBtn.Name = "addBtn";
            this.addBtn.Size = new System.Drawing.Size(75, 36);
            this.addBtn.TabIndex = 27;
            this.addBtn.Text = "Add";
            this.addBtn.UseVisualStyleBackColor = true;
            this.addBtn.Click += new System.EventHandler(this.addBtn_Click);
            // 
            // mulBtn
            // 
            this.mulBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.mulBtn.Location = new System.Drawing.Point(239, 134);
            this.mulBtn.Name = "mulBtn";
            this.mulBtn.Size = new System.Drawing.Size(75, 36);
            this.mulBtn.TabIndex = 26;
            this.mulBtn.Text = "Multiply";
            this.mulBtn.UseVisualStyleBackColor = true;
            this.mulBtn.Click += new System.EventHandler(this.mulBtn_Click);
            // 
            // textBox3
            // 
            this.textBox3.Enabled = false;
            this.textBox3.Location = new System.Drawing.Point(257, 41);
            this.textBox3.Name = "textBox3";
            this.textBox3.Size = new System.Drawing.Size(170, 20);
            this.textBox3.TabIndex = 7;
            // 
            // textBox2
            // 
            this.textBox2.Location = new System.Drawing.Point(166, 41);
            this.textBox2.Name = "textBox2";
            this.textBox2.Size = new System.Drawing.Size(57, 20);
            this.textBox2.TabIndex = 6;
            // 
            // label3
            // 
            this.label3.AutoSize = true;
            this.label3.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.label3.Location = new System.Drawing.Point(228, 44);
            this.label3.Name = "label3";
            this.label3.Size = new System.Drawing.Size(16, 17);
            this.label3.TabIndex = 4;
            this.label3.Text = "=";
            // 
            // label2
            // 
            this.label2.AutoSize = true;
            this.label2.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.label2.Location = new System.Drawing.Point(146, 44);
            this.label2.Name = "label2";
            this.label2.Size = new System.Drawing.Size(16, 17);
            this.label2.TabIndex = 3;
            this.label2.Text = "+";
            // 
            // textBox1
            // 
            this.textBox1.Location = new System.Drawing.Point(83, 41);
            this.textBox1.Name = "textBox1";
            this.textBox1.Size = new System.Drawing.Size(57, 20);
            this.textBox1.TabIndex = 1;
            // 
            // Form1
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(475, 369);
            this.Controls.Add(this.calcPanel);
            this.Name = "Form1";
            this.Text = "Calculator";
            this.calcPanel.ResumeLayout(false);
            this.calcPanel.PerformLayout();
            this.groupBox1.ResumeLayout(false);
            this.ResumeLayout(false);

        }

        #endregion

        private System.Windows.Forms.GroupBox calcPanel;
        private System.Windows.Forms.TextBox textBox1;
        private System.Windows.Forms.TextBox textBox3;
        private System.Windows.Forms.TextBox textBox2;
        private System.Windows.Forms.Label label3;
        private System.Windows.Forms.Label label2;
        private System.Windows.Forms.Button mulBtn;
        private System.Windows.Forms.Button divBtn;
        private System.Windows.Forms.Button subBtn;
        private System.Windows.Forms.Button addBtn;
        private System.Windows.Forms.Label label5;
        private System.Windows.Forms.Label label4;
        private System.Windows.Forms.Label label1;
        private System.Windows.Forms.RichTextBox logTextBox;
        private System.Windows.Forms.GroupBox groupBox1;

    }
}


//Form1.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using Calculator_Wrapper;
using System.Runtime.InteropServices;

namespace TestCalcCSharp
{
    public partial class Form1 : Form
    {
        Calculator_Wrapper.Calculator calc = null;

        public Form1()
        {
            InitializeComponent();
            calc = new Calculator();
        }

        private void addBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);


                double output = calc.Add(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void subBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);


                double output = calc.Subtract(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void mulBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);

                double output = calc.Multiply(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void divBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);

                if (inp2 == 0) throw new DivideByZeroException();
                double output = calc.Divide(inp1, inp2);
                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message + "\n";
            }
        }
    }
}

Facade design pattern implementation in C++

noreply@blogger.com (Varun) — Sun, 26 Oct 2014 16:33:00 +0000

Facade means the exterior of any object in general. Facade Design Pattern provides similar functionality as well. It provides a simple interface to a complex system. Just as we can not tell from the exterior of a building what lies inside it, Facade design pattern provides an interface which hides the internal complexity of a system. It only exposes the desired interfaces which have to be used by a client. It can be only a small subsystem of the complex system as the client may not need all the functionality of the complex system. Also it could modify the interfaces as well to provide the complete functionality of the system.

Facade Design Pattern

For our implementation of the Facade Design Pattern, we have chosen example of Online Shopping model. The following diagram represents the relationships and flow between the classes.

Class Diagram for below example

The example works like this. OnlineShoppingFacade is the interface which is exposed to the customers (us). It's just like any portal like Flipkart, Amazon or eBay. Now we do not know what the heck is going behind those websites. All we know is that we have just placed an order and we will get a delivery after a certain period of time. Of course there is a status tracker something like this

But still the intricacies behind the process is hidden away from us. This is the Facade for the Online Shopping Portal.

Below is a simplistic implementation just to demo how Facade Design Pattern works using a C++ example.

Facade Design Pattern Implementation(C++)

Update(5th Nov 2014): The code is updated to work on linux platform as well.



#include <iostream>
#include <string>
#ifdef _WIN32
#include <windows.h>
#elif defined __linux__
#include <unistd.h>
#endif

/* Uncomment below line to enable debug logs */
/* #define DEBUG */
 
std::string _stateToStrCourier[]   = { "Received", "VerifyReachbility", "AssignPerson", 
                                       "DispatchPackage", "GetDeliveryConfirmation", "Complete"};
std::string _stateToStrVendor[]    = { "Received", "VerifyInventory", "GetItemFromWareHouse", 
                                       "PackItem", "ContactCourier", "Complete"};
std::string _stateToStrOrderTeam[] = { "Received", "VerifyPayment", "ContactVendor", "Complete"};

void mySleep(unsigned int millisecs)
{
#ifdef _WIN32
 Sleep(millisecs);
#elif defined __linux__
 usleep(1000 * millisecs);
#endif
}

class Courier
{
public:
 void submitRequestToCourier()
 {
  _state = 0;
 }
 bool checkStatus()
 {
#ifdef DEBUG
  std::cout<<"Courier: Current State: "<<_stateToStrCourier[_state]<< std::endl;
#endif
  mySleep(500); /* Do some useful work here */

  _state++;
  if (_state == Complete)
   return 1;
  return 0;
 }
private:
 enum States
 {
  Received, VerifyReachbility, AssignPerson, DispatchPackage, GetDeliveryConfirmation, Complete
 };
 int _state;
};
 
class Vendor
{
public:
 void submitRequestToVendor()
 {
  _state = 0;
 }
 bool checkStatus()
 {
#ifdef DEBUG
  std::cout<<"Vendor: Current State: "<<_stateToStrVendor[_state]<< std::endl;
#endif
  mySleep(500); /* Do some useful work here */

  _state++;
  if (_state == Complete)
   return 1;
  return 0;
 }
private:
 enum States
 {
  Received, VerifyInventory, GetItemFromWareHouse, PackItem, ContactCourier, Complete
 };
 int _state;
 
};
 
class OrderingTeam
{
public:
 void submitRequestToOrderTeam()
 {
  _state = 0;
 }
 bool checkStatus()
 {
#ifdef DEBUG
  std::cout<<"OrderingTeam: Current State: "<<_stateToStrOrderTeam[_state]<< std::endl;
#endif
  mySleep(500); /* Do some useful work here */ 
  _state++;
  if (_state == Complete)
   return 1;
  return 0;
 }
private:
 enum States
 {
  Received, VerifyPayment, ContactVendor, Complete
 };
 int _state;
};
 
class OnlineShoppingFacade
{
public:
 OnlineShoppingFacade()
 {
  _count = 0;
 }
 void submitRequest()
 {
  _state = 0;
 }
 bool checkStatus()
 {
  /* Item request has just been received */
  switch(_state)
  {
  case Received:
   _state++;
   /* Forward the job request to the ordering team */
   _order.submitRequestToOrderTeam();
   std::cout << "submitted to Order Team - " << _count <<
    " followups till now" << std::endl;
   break;
  case SubmittedToOrderTeam:
   /* If order team has completed verification, 
   place the request with vendor */
   if (_order.checkStatus())
   {
    _state++;
    _vendor.submitRequestToVendor();
    std::cout << "submitted to Vendor - " << _count <<
     " followups till now" << std::endl;
   }
   break;
  case SubmittedToVendor:
   /* If vendor has packed the item, forward it to courier */
   if (_vendor.checkStatus())
   {
    _state++;
    _courier.submitRequestToCourier();
    std::cout << "submitted to Courier - " << _count <<
     " followups till now" << std::endl;
   }
   break;
  case SubmittedToCourier:
   /* If package is delivered, order is complete */
   if (_courier.checkStatus())
    return 1;
  default:
   break;
  }
 
  _count++;
 
  /* The order is not complete */
  return 0;
 }
 int numFUPs()
 
 {
  return _count;
 }
private:
 enum States
 {
  Received, SubmittedToOrderTeam, SubmittedToVendor, SubmittedToCourier
 };
 
 int _state;
 int _count;
 
 OrderingTeam _order;
 Vendor _vendor;
 Courier _courier;
};
 
int main()
{
 OnlineShoppingFacade onlinereq;
 
 onlinereq.submitRequest();
 
 /* Keep checking until order is complete */
 while (!onlinereq.checkStatus());
 
 std::cout << "Order completed after " << onlinereq.numFUPs() << 
  " followups" << std::endl;
}

Create a SOAP web service client in C++

noreply@blogger.com (Varun) — Sat, 18 Oct 2014 17:07:00 +0000

What is SOAP?

SOAP(Simple Object Access Protocol) is a great way to exchange information over the network. Normally it is used with application protocols like HTTP, SMTP etc. The envelope containing the information is XML based.

It provides the basic messaging infrastructure for web services.

An example SOAP request looks like :

 
<?xml version="1.0" encoding="UTF-8"?>
<soapenv:Envelope
        xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/"
        xmlns:xsd="http://www.w3.org/2001/XMLSchema"
        xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
  <soapenv:Header>
    <ns1:RequestHeader
         soapenv:actor="http://schemas.xmlsoap.org/soap/actor/next"
         soapenv:mustUnderstand="0"
         xmlns:ns1="https://www.google.com/apis/ads/publisher/v201403">
      <ns1:networkCode>123456</ns1:networkCode>
      <ns1:applicationName>DfpApi-Java-2.1.0-dfp_test</ns1:applicationName>
    </ns1:RequestHeader>
  </soapenv:Header>
  <soapenv:Body>
    <getAdUnitsByStatement xmlns="https://www.google.com/apis/ads/publisher/v201403">
      <filterStatement>
        <query>WHERE parentId IS NULL LIMIT 500</query>
      </filterStatement>
    </getAdUnitsByStatement>
  </soapenv:Body>
</soapenv:Envelope>

The corresponding response would look like :

 
<soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
  <soap:Header>
    <ResponseHeader xmlns="https://www.google.com/apis/ads/publisher/v201403">
      <requestId>xxxxxxxxxxxxxxxxxxxx</requestId>
      <responseTime>1063</responseTime>
    </ResponseHeader>
  </soap:Header>
  <soap:Body>
    <getAdUnitsByStatementResponse xmlns="https://www.google.com/apis/ads/publisher/v201403">
      <rval>
        <totalResultSetSize>1</totalResultSetSize>
        <startIndex>0</startIndex>
        <results>
          <id>2372</id>
          <name>RootAdUnit</name>
          <description></description>
          <targetWindow>TOP</targetWindow>
          <status>ACTIVE</status>
          <adUnitCode>1002372</adUnitCode>
          <inheritedAdSenseSettings>
            <value>
              <adSenseEnabled>true</adSenseEnabled>
              <borderColor>FFFFFF</borderColor>
              <titleColor>0000FF</titleColor>
              <backgroundColor>FFFFFF</backgroundColor>
              <textColor>000000</textColor>
              <urlColor>008000</urlColor>
              <adType>TEXT_AND_IMAGE</adType>
              <borderStyle>DEFAULT</borderStyle>
              <fontFamily>DEFAULT</fontFamily>
              <fontSize>DEFAULT</fontSize>
            </value>
          </inheritedAdSenseSettings>
        </results>
      </rval>
    </getAdUnitsByStatementResponse>
  </soap:Body>
</soap:Envelope>

Courtesy : https://developers.google.com/doubleclick-publishers/docs/soap_xml

The above is an example of Google's web service which provides Ad Units to the requester based on some filters.

Web Services provide an easy platform independent way to exchange information over the network.
The following picture shows the basic flow on how the Service Provider caters the request of the consumer.

Source: http://www.service-architecture.com

Following is an implementation of a SOAP client in C++ which calls the Web Service to get the stock quotes based on a symbol(company ticker).

The example uses gSoap library for SOAP encoding/decoding and Xerces library to extract the data from the SOAP response (XML).

I have used the web service URL http://www.webservicex.net/stockquote.asmx?WSDL

Resources:

gSOAP library (2.8.18) http://sourceforge.net/projects/gsoap2/files/
Xerces library (3.1.1) http://xerces.apache.org/mirrors.cgi#binary

Setup for Visual Studio 2005:

Unzip gSOAP library at any location (Lets say C:\tools , so the location will be C:\gsoap-2.8)
Download only the binary distribution of xerces xerces-c-3.1.1-x86-windows-vc-8.0.zip
Unzip the zip file at C:\ so that location becomes C:\xerces-c-3.1.1-x86-windows-vc-8.0
Create an empty Win32 Console Application project.
Add theses paths to the Additional Include Directories :
"C:\xerces-c-3.1.1-x86-windows-vc-8.0\include";"C:\gsoap-2.8\gsoap\";"C:\gsoap-2.8\gsoap\import"
Add these paths to Additional Library Directories :
"C:\xerces-c-3.1.1-x86-windows-vc-8.0\lib"
Add these libs to the dependency list:

Notice that since we are using a Debug configuration here, we added xerces-c_3D.lib. For Release configuration, use xerces-c_3.lib
Add this location to your environment Path variable C:\xerces-c-3.1.1-x86-windows-vc-8.0\bin or copy the xerces dlls (xerces-c_3_1.dll and xerces-c_3_1D.dll) into the output path of the project(i.e. same path where the exe of the project will be created). These will be present at the location C:\xerces-c-3.1.1-x86-windows-vc-8.0\bin
Open a command prompt and go to gSOAP win32 bin directory and run following commands :

wsdl2h.exe -o quote.h http://www.webservicex.net/stockquote.asmx?WSDL

This will generate quote.h which contains class definitions for the web service.
soapcpp2.exe /IC:\tools\gsoap_2.8.18\gsoap-2.8\gsoap\import quote.h
This generates following files :

StockQuoteSoap.GetQuote.req.xml
StockQuoteSoap.GetQuote.res.xml
StockQuoteSoap.nsmap
soapC.cpp
soapClient.cpp
soapClientLib.cpp
soapH.h
soapServer.cpp
soapServerLib.cpp
soapStub.h
Now add these generated files to the Visual Studio project created earlier :
soapH.h , soapC.cpp, soapClient.cpp, soapStub.h, quote.h

Also these add two additional files from C:\tools\gsoap_2.8.18\gsoap-2.8\gsoap to your project:
stdsoap2.cpp, stdsoap2.h
Now its time to create some files on our own :). Create these files in the project and copy the contents from the code below :

quote.cpp, parser.hpp, stock.hpp

SOAP Web Service client implementation(c++)


//quote.cpp
#include "soapH.h"    // include the generated proxy
#include <xercesc/sax/HandlerBase.hpp>
#include <xercesc/util/XMLString.hpp>
#include <xercesc/framework/MemBufInputSource.hpp>
#include <xercesc/util/OutOfMemoryException.hpp>
#include <xercesc/dom/DOM.hpp>
#include <xercesc/dom/DOMDocument.hpp>
#include <xercesc/dom/DOMDocumentType.hpp>
#include <xercesc/dom/DOMElement.hpp>
#include <xercesc/dom/DOMImplementation.hpp>
#include <xercesc/dom/DOMImplementationLS.hpp>
#include <xercesc/dom/DOMNodeIterator.hpp>
#include <xercesc/dom/DOMNodeList.hpp>
#include <xercesc/dom/DOMText.hpp>
#include <xercesc/parsers/XercesDOMParser.hpp>
#include <xercesc/util/XMLUni.hpp>
#include "parser.hpp"

XERCES_CPP_NAMESPACE_USE

GetXml::GetXml()
{
 try
 {
  XMLPlatformUtils::Initialize();  // Initialize Xerces infrastructure
 }
 catch( XMLException& e )
 {
  char* message = XMLString::transcode( e.getMessage() );
  std::cout << "XML toolkit initialization error: " << message << std::endl;
  XMLString::release( &message );
 }

 // Tags and attributes used in XML file.
 // Can't call transcode till after Xerces Initialize()
 TAG_root  = XMLString::transcode("StockQuotes");
 TAG_Stock = XMLString::transcode("Stock");
 TAG_Symbol = XMLString::transcode("Symbol");
 TAG_Last = XMLString::transcode("Last");
 TAG_Date = XMLString::transcode("Date");
 TAG_Time = XMLString::transcode("Time");
 TAG_Change = XMLString::transcode("Change");
 TAG_Open = XMLString::transcode("Open");
 TAG_High = XMLString::transcode("High");
 TAG_Low = XMLString::transcode("Low");
 TAG_Volume = XMLString::transcode("Volume");
 TAG_MktCap = XMLString::transcode("MktCap");
 TAG_PrevClose = XMLString::transcode("PreviousClose");
 TAG_PercentChange = XMLString::transcode("PercentageChange");
 TAG_AnnRange = XMLString::transcode("AnnRange");
 TAG_Earns = XMLString::transcode("Earns");
 TAG_PE = XMLString::transcode("P-E");
 TAG_Name = XMLString::transcode("Name");
 
 m_XmlParser = new XercesDOMParser;
 m_Stock = new Stock;
}

GetXml::~GetXml()
{
 // Free memory
 delete m_XmlParser;
 delete m_Stock;

 try
 {
  XMLString::release( &TAG_root );
 }
 catch( ... )
 {
  std::cout << "Unknown exception encountered in Destructor" << std::endl;
 }

 // Terminate Xerces
 try
 {
  XMLPlatformUtils::Terminate();  // Terminate after release of memory
 }
 catch( xercesc::XMLException& e )
 {
  char* message = xercesc::XMLString::transcode( e.getMessage() );

  std::cout << "XML toolkit teardown error: " << message << std::endl;
  XMLString::release( &message );
 }
}

void GetXml::readXml(std::string& xmlStr)
throw( std::runtime_error )
{
 // Configure DOM parser.
 m_XmlParser->setValidationScheme( XercesDOMParser::Val_Never );
 m_XmlParser->setDoNamespaces( false );
 m_XmlParser->setDoSchema( false );
 m_XmlParser->setLoadExternalDTD( false );

 try
 {
  xercesc_3_1::MemBufInputSource xmlBuf((const XMLByte*)xmlStr.c_str(), xmlStr.size(),
   "xmlBuf (in memory)");
  m_XmlParser->parse( xmlBuf );

  xercesc_3_1::DOMDocument* xmlDoc = m_XmlParser->getDocument();

  DOMElement* elementRoot = xmlDoc->getDocumentElement();
  if( !elementRoot ) throw(std::runtime_error( "Empty XML document" ));

  DOMNodeList*      children = elementRoot->getChildNodes();
  const  XMLSize_t nodeCount = children->getLength();

  // For all nodes, children of "StockQuotes" in the XML tree.

  for( XMLSize_t xx = 0; xx < nodeCount; ++xx )
  {
   DOMNode* currentNode = children->item(xx);
   if( currentNode->getNodeType() &&  // true is not NULL
    currentNode->getNodeType() == DOMNode::ELEMENT_NODE ) // is element 
   {
    // Found node which is an Element. Re-cast node as element
    DOMElement* currentElement
     = dynamic_cast< xercesc::DOMElement* >( currentNode );
    if( XMLString::equals(currentElement->getTagName(), TAG_Stock))
    {
     DOMNodeList*      children1 = currentElement->getChildNodes();
     const  XMLSize_t nodeCount1 = children1->getLength();
     for( XMLSize_t yy = 0; yy < nodeCount1; ++yy )
     {
      DOMNode* currentNode1 = children1->item(yy);
      if( currentNode1->getNodeType() &&  // true is not NULL
       currentNode1->getNodeType() == DOMNode::ELEMENT_NODE ) // is element 
      {
       // Found node which is an Element. Re-cast node as element
       DOMElement* currentElement1
        = dynamic_cast< xercesc::DOMElement* >( currentNode1 );
       std::cout<<XMLString::transcode(currentElement1->getTagName())<<": "
        <<XMLString::transcode(currentElement1->getTextContent())<<std::endl;

       std::string sym(XMLString::transcode(currentElement1->getTextContent()));

       if(XMLString::equals(currentElement1->getTagName(), TAG_Symbol))
       {
        m_Stock->SetSymbol(sym);
       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Last))
       {
        m_Stock->SetLast(sym);
       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Date))
       {
        m_Stock->SetDate(sym);
       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Time))
       {
        m_Stock->SetTime(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Change))
       {
        m_Stock->SetChange(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Open))
       {
        m_Stock->SetOpen(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_High))
       {
        m_Stock->SetHigh(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Low))
       {
        m_Stock->SetLow(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Volume))
       {
        m_Stock->SetVolume(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_MktCap))
       {
        m_Stock->SetMktCap(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_PrevClose))
       {
        m_Stock->SetPrevClose(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_PercentChange))
       {
        m_Stock->SetPercentChange(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_AnnRange))
       {
        m_Stock->SetAnnRange(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Earns))
       {
        m_Stock->SetEarns(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_PE))
       {
        m_Stock->SetPE(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Name))
       {
        m_Stock->SetName(sym);
       }
      }
     }
    }
   }
  }

  std::cout<<m_Stock->ToString();
 }
 catch( xercesc::XMLException& e )
 {
  char* message = xercesc::XMLString::transcode( e.getMessage() );
  std::ostringstream errBuf;
  errBuf << "Error parsing file: " << message << std::flush;
  XMLString::release( &message );
 }
}

int main(int argc, char** argv){
 struct soap *soap = soap_new(); 
 struct _ns1__GetQuote sym;
 struct _ns1__GetQuoteResponse quote;
 GetXml xml;
 std::string response="";
 std::string str(argv[1]);
 sym.symbol = &str;

 soap_init(soap);

 //Call the web service
 if (soap_call___ns1__GetQuote(soap, NULL, NULL, &sym, quote) == SOAP_OK) {
  //std::cout<<"Symbol: "<<*(sym.symbol)<<std::endl<<" Quote: "<<*(quote.GetQuoteResult)<<std::endl;
  response = *(quote.GetQuoteResult);
  free (quote.GetQuoteResult);
 }
 else {
  std::cout<<"Error in execution of GetQuote:: "<<soap->buf<<std::endl;
  return(0);
 }

 //Parse the SOAP response 
 xml.readXml(response);
 return 0;
}

// Copied from StockQuoteSoap.nsmap file
SOAP_NMAC struct Namespace namespaces[] =
{
 {"SOAP-ENV", "http://www.w3.org/2003/05/soap-envelope", "http://schemas.xmlsoap.org/soap/envelope/", NULL},
 {"SOAP-ENC", "http://www.w3.org/2003/05/soap-encoding", "http://schemas.xmlsoap.org/soap/encoding/", NULL},
 {"xsi", "http://www.w3.org/2001/XMLSchema-instance", "http://www.w3.org/*/XMLSchema-instance", NULL},
 {"xsd", "http://www.w3.org/2001/XMLSchema", "http://www.w3.org/*/XMLSchema", NULL},
 {"ns1", "http://www.webserviceX.NET/", NULL, NULL},
 {NULL, NULL, NULL, NULL}
};


//stock.hpp
#include <sstream>
class Stock
{
 std::string symbol_;
 std::string last_;
 std::string date_;
 std::string time_;
 std::string change_;
 std::string open_;
 std::string high_;
 std::string low_;
 std::string volume_;
 std::string mktcap_;
 std::string previousclose_;
 std::string percentagechange_;
 std::string annrange_;
 std::string earns_;
 std::string p_e_;
 std::string name_;

public:
 Stock() {}
 Stock(std::string symbol) {symbol_ = symbol;}

 void SetSymbol(std::string symbol) {symbol_ = symbol;}
 void SetLast(std::string last) {last_ = last;}
 void SetDate(std::string date) {date_ = date;}
 void SetTime(std::string time) {time_ = time;}
 void SetChange(std::string change) {change_ = change;}
 void SetOpen(std::string open) {open_ = open;}
 void SetHigh(std::string high) {high_ = high;}
 void SetLow(std::string low) {low_ = low;}
 void SetVolume(std::string volume) {volume_ = volume;}
 void SetMktCap(std::string mktcap) {mktcap_ = mktcap;}
 void SetPrevClose(std::string previousclose) {previousclose_ = previousclose;}
 void SetPercentChange(std::string percentagechange) {percentagechange_ = percentagechange;}
 void SetAnnRange(std::string annrange) {annrange_ = annrange;}
 void SetEarns(std::string earns) {earns_ = earns;}
 void SetPE(std::string p_e) {p_e_ = p_e;}
 void SetName(std::string name) {name_ = name;}

 //ToString function overridden to display in short format  
 std::string ToString() const
 {
  std::stringstream sstr;
  sstr << "\'" << symbol_ << "\' Open: " << open_
   << ", Last: " << last_;
  return sstr.str();
 }
};


//parser.hpp
#include "stock.hpp"
class GetXml
{
public:
 GetXml();
 ~GetXml();

 //Function to read the XML string
 void readXml(std::string&) throw(std::runtime_error);


private:
 xercesc_3_1::XercesDOMParser *m_XmlParser; //DOM Parser pointer
 Stock *m_Stock;        //To save the returned data

 XMLCh* TAG_root;
 XMLCh* TAG_Stock;
 XMLCh* TAG_Symbol;
 XMLCh* TAG_Last;
 XMLCh* TAG_Date;
 XMLCh* TAG_Time;
 XMLCh* TAG_Change;
 XMLCh* TAG_Open;
 XMLCh* TAG_High;
 XMLCh* TAG_Low;
 XMLCh* TAG_Volume;
 XMLCh* TAG_MktCap;
 XMLCh* TAG_PrevClose;
 XMLCh* TAG_PercentChange;
 XMLCh* TAG_AnnRange;
 XMLCh* TAG_Earns;
 XMLCh* TAG_PE;
 XMLCh* TAG_Name;
};

Now the project is ready to compile. Use F7 to compile the solution.
After the binary is generated, run it like this :
<binary-name>.exe<space><Ticker-Name>

e.g. If project name was soap
soap.exe GOOG
This program is specific to the Stock Quote web service provided by http://www.webservicex.net/ . This program can be modified to use any web service. Depending upon the expected SOAP response, the result can be parsed accordingly. Then following files will be modified :

stock.hpp - Class which stores the data from SOAP response
parser.hpp - Class which parses the XML result from SOAP response

Builder Design Pattern Implementation in C++

noreply@blogger.com (Varun) — Tue, 01 Apr 2014 20:21:00 +0000

Sometimes an application gets too complicated and developing it becomes a pain. These applications contain complex objects which are made up from other objects from different classes. Now these objects may vary. So there has to be a process of building the complex objects so that there is scope of building different products using the same process.

That is when a creational design pattern called Builder comes into picture. It separates the details of construction process from its representation.

Now what in the world that line means actually ?

It means that the construction process is made so generic, that multiple products can be produced using the same process. e.g. construction workers. Different type of buildings can be built using the same workers and same common set of process.

Here is a class diagram of the design pattern.

Builder Design Pattern

There are 4 major components:

Director: It constructs an object using the Builder interface.
Builder : It specifies an abstract interface to build parts of a product.
Concrete Classes : Implements builder interface.
Product : The complex object which is created at the end.

Director object is created and Builder interface is used. It notifies the Builder to create each part of the product. Upon the request from Director, Builder adds parts to the product. Finally the product is returned by the Builder.

We have to take care of when to use the Builder Design Pattern. Few points come into mind :

When the object to be created is complex enough and can have multiple representations.
When the construction process can be broken down into multiple steps
When the process of creation of an object can be independent of the parts to be used.
When different products can have a common abstract class.

Now lets create a builder design pattern using an example.

Builder Example

In this example we create house as product. Now the house created may be different as per requirement of different people. It can be a lavish house with lots of amenities and expensive stuff. On the other hand, it could be a normal house with normal stuff.

The HouseBuilder class is the builder class which provides interface for creating the parts of the house.
The House class is the final product that we want to build
LavishHouse and NormalHouse are the concrete classes which implement the HouseBuilder interface.
Contractor is the director which constructs the house using the HouseBuilder interface.

Builder Design Pattern Implementation(C++)

 #include <iostream>

using namespace std;

/* Interface that will be returned as the product from builder */
class HousePlan{
public:
 virtual void setWindow(string window)=0;
 virtual void setDoor(string door)=0;
 virtual void setBathroom(string bathroom)=0;
 virtual void setKitchen(string kitchen)=0;
 virtual void setFloor(string floor)=0;
};

/* Concrete class for the HousePlan interface */
class House:public HousePlan{
private :
 string window, door, kitchen, bathroom, floor;

public:
 void setWindow(string window)
 {
  this->window = window;
 }

 void setDoor(string door)
 {
  this->door = door;
 }

 void setBathroom(string bathroom)
 {
  this->bathroom = bathroom;
 }

 void setKitchen(string kitchen)
 {
  this->kitchen = kitchen;
 }

 void setFloor(string floor)
 {
  this->floor = floor;
 }
};

/* Builder Class */
class HouseBuilder
{
public:
 /* Abstract functions to build parts */
 virtual void buildWindow()=0;
 virtual void buildDoor()=0;
 virtual void buildKitchen()=0;
 virtual void buildBathroom()=0;
 virtual void buildFloor()=0;
 /* The product is returned by this function */
 virtual House* getHouse()=0;
};

/* Concrete class for the builder interface */
class LavishHouse:public HouseBuilder{
private:
 House *house;
public:
 LavishHouse()
 {
  house = new House();
 }

 void buildWindow()
 {
  house->setWindow("French Window");
 }

 void buildDoor()
 {
  house->setDoor("Wooden Door");
 }

 void buildBathroom()
 {
  house->setBathroom("Modern Bathroom");
 }

 void buildKitchen()
 {
  house->setKitchen("Modular Kitchen");
 }

 void buildFloor()
 {
  house->setFloor("Wooden Floor");
 }

 House* getHouse()
 {
  return this->house;
 }
};

/* Another Concrete class for the builder interface */
class NormalHouse:public HouseBuilder{
private:
 House *house;
public:
 NormalHouse()
 {
  house = new House();
 }

 void buildWindow()
 {
  house->setWindow("Normal Window");
 }

 void buildDoor()
 {
  house->setDoor("Metal Door");
 }

 void buildBathroom()
 {
  house->setBathroom("Regular Bathroom");
 }

 void buildKitchen()
 {
  house->setKitchen("Regular Kitchen");
 }

 void buildFloor()
 {
  house->setFloor("Mosaic Floor");
 }

 House* getHouse()
 {
  return this->house;
 }
};

/* The Director. Constructs the house */
class Contractor
{
private:
 HouseBuilder *houseBuilder;

public:
 Contractor(HouseBuilder *houseBuilder)
 {
  this->houseBuilder = houseBuilder;
 }

 House *getHouse()
 {
  return houseBuilder->getHouse();
 }

 void buildHouse()
 {
  houseBuilder->buildWindow();
  houseBuilder->buildDoor();
  houseBuilder->buildBathroom();
  houseBuilder->buildKitchen();
  houseBuilder->buildFloor();
 }
};

/* Example on how to use the Builder design pattern */
int main()
{
 HouseBuilder *lavishHouseBldr = new LavishHouse();
 HouseBuilder *normalHouseBldr = new NormalHouse();

 Contractor *ctr1 = new Contractor(lavishHouseBldr);
 Contractor *ctr2 = new Contractor(normalHouseBldr);

 ctr1->buildHouse();
 House *house1 = ctr1->getHouse();
 cout<<"Constructed: "<<house1;

 ctr2->buildHouse();
 House *house2 = ctr2->getHouse();
 cout<<"Constructed: "<<house2;
}

Decorator Design Pattern Implementation in C++

noreply@blogger.com (Varun) — Sun, 29 Dec 2013 14:46:00 +0000

Do you need to extend the capabilities of your existing class instance at run-time? If the answer is yes then Decorator design pattern just provides the functionality you need.

When we have to change the capabilities of only a particular instance and not all the instances which will get created for a particular class, we have to use decorator design pattern.

This is achieved by creating a decorator class, which wraps the original class. The original class is sub-classed into two parts. One is the concrete class which is essentially the original class with only basic features. The other one is the Decorator base class. This decorator base class implements the same interface as the original class. In addition it wraps the original base class.

We can extend this Decorator base class to create multiple concrete decorator classes. Each of these concrete decorator classes implement their own methods and will call the base class's instance's method.

Now this looks complete babbling. Let's see what I mean actually.

Decorator Design Pattern

I know the above diagram looks overwhelming. So let's explain it in more simple language with much simpler example.

Lets prepare a subway burger. Shall we ;)
Now we all know that when we visit a Subway store, we have a variety of options to customize our Sub.
Assuming that we have chosen a foot-long already for the base bread, we start making our sandwich.

We can add cheese to the sandwich.
We can add vegetables to our Sub.
We can add mayonnaise,mustard, sweet onion etc .

Depending on our choices, the sandwich is prepared. And we are ready to eat it .. Aren't we :)

Now consider the bread(foot-long) as the Base Component Class. Over this component, we can place a Decorator Base Class SubDecorator and now the Concrete Decorators can be derived from this class.

CheeseDecorator, VegDecorator, SauceDecorator are concrete decorators which implement their own functions and have their own members in addition to the base class functions cost() and description().

And here comes the code:

Decorator Design Pattern Implementation (C++)

 #include <iostream>
#include <string>

//Uncomment the next line to enable debug logs
//#define DEBUG

std::string c(const std::string cls) {
    return "\n" + cls + " Constructor";
}
std::string d(const std::string cls) {
    return "\n" +cls + " Destructor";
}

/*Base component class*/
class Sandwich
{
public:
    virtual ~Sandwich() { }
    virtual double getCost()=0;
    virtual std::string getDesc()=0;
};

/*Concrete component class*/
class WheatBread:public Sandwich
{
public:
    WheatBread() {
#ifdef DEBUG
        std::cout<<c("WheatBread");
#endif
    }
    ~WheatBread() {
#ifdef DEBUG
        std::cout<<d("WheatBread");
#endif
    }
    std::string getDesc()
    {
        return "Wheat Bread";
    }

    double getCost()
    {
        return 2.0;
    }
};

/*Concrete component class*/
class WholeGrainBread:public Sandwich
{
public:
    WholeGrainBread() {
#ifdef DEBUG
        std::cout<<c("WholeGrainBread");
#endif
    }
    ~WholeGrainBread() {
#ifdef DEBUG
        std::cout<<d("WholeGrainBread");
#endif
    }
    std::string getDesc()
    {
        return "WholeGrain Bread";
    }

    double getCost()
    {
        return 3.0;
    }
};

/*Concrete component class*/
class ItalianBread:public Sandwich
{
public:
    ItalianBread() {
#ifdef DEBUG
        std::cout<<c("ItalianBread");
#endif
    }
    ~ItalianBread() {
#ifdef DEBUG
        std::cout<<d("ItalianBread");
#endif
    }
    std::string getDesc()
    {
        return "Italian Bread";
    }

    double getCost()
    {
        return 2.5;
    }
};

/*Decorator Base class*/
class SubDecorator: public Sandwich
{
    Sandwich *sandwich;
public:
    SubDecorator(Sandwich *sandwichRef)
    {
#ifdef DEBUG
        std::cout<<c("SubDecorator");
#endif
        sandwich = sandwichRef;
    }

    ~SubDecorator() {
#ifdef DEBUG
        std::cout<<d("SubDecorator");
#endif
        delete sandwich;
    }
    double getCost()
    {
        return sandwich->getCost();
    }
    std::string getDesc()
    {
        return sandwich->getDesc();
    }
};

/*Decorator concrete class*/
class CheeseDecorator:public SubDecorator
{
private:
    std::string cheese_desc()
    {
        return " + Cheese";
    }

    double cheese_cost;

public:
    CheeseDecorator(Sandwich *sandwich):SubDecorator(sandwich)
    {
#ifdef DEBUG
        std::cout<<c("CheeseDecorator");
#endif
        cheese_cost = 3.0;
    }

    ~CheeseDecorator() {
#ifdef DEBUG
        std::cout<<d("CheeseDecorator");
#endif
    }
    std::string getDesc()
    {
        return SubDecorator::getDesc().append(cheese_desc());
    }

    double getCost()
    {
        return SubDecorator::getCost() + cheese_cost;
    }
};

/*Decorator concrete class*/
class VegDecorator:public SubDecorator
{
private:
    std::string veg_desc()
    {
        return " + Veg";
    }

    double veg_cost;

public:
    VegDecorator(Sandwich *sandwich):SubDecorator(sandwich)
    {
#ifdef DEBUG
        std::cout<<c("VegDecorator");
#endif
        veg_cost = 2.0;
    }

    ~VegDecorator() {
#ifdef DEBUG
        std::cout<<d("VegDecorator");
#endif
    }
    std::string getDesc()
    {
        return SubDecorator::getDesc().append(veg_desc());
    }

    double getCost()
    {
        return SubDecorator::getCost() + veg_cost;
    }
};

/*Decorator concrete class*/
class SauceDecorator:public SubDecorator
{
private:
    std::string sauce_desc()
    {
        return " + Sauce";
    }

    double sauce_cost;

public:
    SauceDecorator(Sandwich *sandwich):SubDecorator(sandwich)
    {
#ifdef DEBUG
        std::cout<<c("SauceDecorator");
#endif
        sauce_cost = .5;
    }

    ~SauceDecorator() {
#ifdef DEBUG
        std::cout<<d("SauceDecorator");
#endif
    }
    std::string getDesc()
    {
        return SubDecorator::getDesc().append(sauce_desc());
    }

    double getCost()
    {
        return SubDecorator::getCost() + sauce_cost;
    }
};

int main()
{
    Sandwich *sandwich = new CheeseDecorator(new WheatBread());
    sandwich = new VegDecorator(sandwich);
    sandwich = new SauceDecorator(new SubDecorator(sandwich));
    std::cout<<"\nYour sandwich is "<<sandwich->getDesc()<<" and costs $"<<sandwich->getCost();
    delete sandwich;
}

Factory Method Design Pattern implementation in C++

noreply@blogger.com (Varun) — Sun, 29 Dec 2013 11:08:00 +0000

What does a factory mean ? It is something which creates/manufactures some products.

Same is the job of factory design pattern. It is responsible for instantiation/creation of objects. But wait, isn't that something what constructors do ? Yes call to constructor indeed creates the object and that's exactly what a factory method does but with an additional feature of option of choosing between different constructors based on some logic.

Factory methods decide logically what constructor to call. So, instead of directly calling the constructor for a class, we call a factory method to get the object. There can be multiple derived classes from a base class. The factory method instantiates the appropriate sub-class based on the arguments passed to it and returns the base class type. This base class object can be used to access the derived class members/methods.

Blah, blah, blah... Let's get down to business and understand what it actually is and what it does.

A basic structure:

Basic structure of factory design pattern

Now let's explain it with a simple example:

Assume that we are an online Music Store . We every kind of music be it Rock, Classical, Jazz, Reggae, Techno and what not. Of course, to organize these we need categories based on different genres. Lets design this model using factory design pattern. Our base class is what we do. We provide music, so say "Music" is our base class.

Now Music can be classified into multiple categories . We for the time being assume only three.

Rock
Pop
Reggae

The class structure would be something like this:

Class Structure

Here Rock, Pop and Reggae are the derived classes from base class Music.

We create a factory pattern for this class structure in which we provide a factory method getMusic(genre_e genre) to the user. Using this method, one can instantiate the object of any subclass by choosing the genre.

Here genre is the logic based on which any particular subclass is instantiated. Advantage of this pattern is that outer world need not instantiate specific objects using the different sub-class constructors. It is being masked in the implementation of factory method.

Factory pattern for the class Music

Moreover if any new genre needs to be added, that can be done easily just by adding a new case in Factory method.

And now the code :

Factory Method Design Pattern implementation (C++)

 #include <iostream>
using namespace std;

enum genre_e{ROCK,POP, REGGAE, INVALID};

/*Base Class*/
class Music {
public:
 virtual void song() = 0;
};

/*Derived class Rock from Music*/
class Rock: public Music
{
public:
 void song()
 {
  cout<<"Nirvana: Smells like a teen spirit\n";
 }
};

/*Derived class Pop from Music*/
class Pop: public Music
{
public:
 void song()
 {
  cout<<"Michael Jackson: Billie Jean\n";
 }
};

/*Derived class Reggae from Music*/
class Reggae: public Music
{
public:
 void song()
 {
  cout<<"Bob Marley: No woman, No cry\n";
 }
};

/*Factory Class*/
class MusicFactory
{
public:
 /*Factory Method*/
 Music *getMusic(genre_e genre)
 {
  Music *music = NULL;

  /*Logic based on Genre*/
  switch(genre)
  {
  case ROCK:
   music = new Rock();
   break;
  case POP:
   music = new Pop();
   break;
  case REGGAE:
   music = new Reggae();
   break;
  default:
   music = NULL;
   break;
  }
  return music;
 }
};

int main()
{
 /*Create factory*/
 MusicFactory *musicFactory = new MusicFactory();

 /*Factory instantiating an object of type ROCK*/
 Music *music = musicFactory->getMusic(ROCK);

 cout<<"Song: ";
 if(music)
  music->song();
 else
  cout<<"Wrong selection dude/dudette !!";
}

Graph Implementation in C

noreply@blogger.com (Varun) — Sun, 29 Sep 2013 12:01:00 +0000

A graph is a collection of nodes and edges. These nodes are connected by links(edges).
These edges may be directed or undirected. Moreover these edges can have weights associated with them

So edges can be categorized as :

Directed, weighted edges
Directed, unweighted edges
Undirected, weighted edges
Undirected, unweighted edges

Uses of graphs

Graphs are extremely useful. Look everywhere and one can easily find use of graphs. Listed below are a few of the vast set of practical uses of graphs.

Delhi Metro Rail Map

Each station is a vertex, the distance in between is a weighted edge.

A Maze

Each corner is a vertex, Line between two corners is and edge.

A tournament fixture
Courtesy: http://www.squadtd.com/

Each team is a vertex, match between the teams is an edge.

Kind of graphs

There are numerous classifications and types of graphs available. I have collected a few of those types from various sources and organized a list of types of graphs:

Undirected Graphs

Undirected Graph

Characteristics:

Order of vertices doesn't matter
1-2 is same as 2-1

Directed Graphs

Directed Graph

Characteristics:

Order of vertices does matter
1-2 is not same as 2-1

Vertex labeled Graphs.

Vertex Labeled Graph

Characteristics:

Each vertex contains additional information. e.g {2,orange}, {4,green}

Cyclic Graphs.

Cyclic Graph

Characteristics:

Graph contains at least one cycle.

Edge labeled Graphs.

Edge Labeled Graph

Characteristics:

Edge has labels e.g an edge in the above graph will be represented as {orange,green,{blue,cyan}}

Weighted Graphs.

Weighted Graph

Characteristics:

Each edge has some weight associated with it.

Directed Acyclic Graphs.

Direct Acyclic Graph(DAG)

Characteristics:

Graph has no cycles.

Disconnected Graphs

Disconnected Graph

Characteristics:

Vertices are disconnected

Mixed graph

Mixed Graph

Characteristics:

Some edges may be directed and some may be undirected

Multigraph

Characteristics:

Multiple edges (and sometimes loops) are allowed

Quiver

Characteristics:

Directed graph which may have more than one arrow from a given source to a given target. A quiver may also have directed loops in it.

Representation of graphs:

Fig. 1: An undirected graph

Fig 2: A directed graph

In order to use Graphs programatically , they need to be somehow represented in code. Following are the most widely used methods of representing a graph.

Adjacency Matrix :

For N vertices an adjacency matrix is an NxN array A such that
A[i][j] = 1 if there is an edge E(i,j)
= 0 otherwise

For an undirected graph, A[i][j] = A[j][i]

For weighted graphs,
A[i][j] = weight of the edge, if there is an edge E(i,j)
= a constant representing no edge (e.g a very large or very small value)

For Fig 1, the adjacency matrix would be

The adjacency matrix for directed graph in Fig 2 would be:

Adjacency List :

Adjacency matrix representation consume a lot of memory (O[N²]). If the graph is complete or almost complete(i.e. contains most of the edges between the vertices), then this representation is good to use. But if there are very few edges as compared to number of vertices, it will unnecessarily consume extra space. Adjacency list can handle this situation very optimally.

Every vertex has a linked list of the vertices it is connected with.

Adjacency list for Fig 1 would be:

Adjacency list for Fig 2 would be:

Following is code snippet to implement graphs in C using adjacency list.

/*graph.h*/
#ifndef _GRAPH_H_
#define _GRAPH_H_

typedef enum {UNDIRECTED=0,DIRECTED} graph_type_e;

/* Adjacency list node*/
typedef struct adjlist_node
{
    int vertex;                /*Index to adjacency list array*/
    struct adjlist_node *next; /*Pointer to the next node*/
}adjlist_node_t, *adjlist_node_p;

/* Adjacency list */
typedef struct adjlist
{
    int num_members;           /*number of members in the list (for future use)*/
    adjlist_node_t *head;      /*head of the adjacency linked list*/
}adjlist_t, *adjlist_p;

/* Graph structure. A graph is an array of adjacency lists.
   Size of array will be number of vertices in graph*/
typedef struct graph
{
    graph_type_e type;        /*Directed or undirected graph */
    int num_vertices;         /*Number of vertices*/
    adjlist_p adjListArr;     /*Adjacency lists' array*/
}graph_t, *graph_p;

/* Exit function to handle fatal errors*/
__inline void err_exit(char* msg)
{
    printf("[Fatal Error]: %s \nExiting...\n", msg);
    exit(1);
}

#endif

/*graph.c*/
#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

/* Function to create an adjacency list node*/
adjlist_node_p createNode(int v)
{
    adjlist_node_p newNode = (adjlist_node_p)malloc(sizeof(adjlist_node_t));
    if(!newNode)
        err_exit("Unable to allocate memory for new node");

    newNode->vertex = v;
    newNode->next = NULL;

    return newNode;
}

/* Function to create a graph with n vertices; Creates both directed and undirected graphs*/
graph_p createGraph(int n, graph_type_e type)
{
    int i;
    graph_p graph = (graph_p)malloc(sizeof(graph_t));
    if(!graph)
        err_exit("Unable to allocate memory for graph");
    graph->num_vertices = n;
    graph->type = type;

    /* Create an array of adjacency lists*/
    graph->adjListArr = (adjlist_p)malloc(n * sizeof(adjlist_t));
    if(!graph->adjListArr)
        err_exit("Unable to allocate memory for adjacency list array");

    for(i = 0; i < n; i++)
    {
        graph->adjListArr[i].head = NULL;
        graph->adjListArr[i].num_members = 0;
    }

    return graph;
}

/*Destroys the graph*/
void destroyGraph(graph_p graph)
{
    if(graph)
    {
        if(graph->adjListArr)
        {
            int v;
            /*Free up the nodes*/
            for (v = 0; v < graph->num_vertices; v++)
            {
                adjlist_node_p adjListPtr = graph->adjListArr[v].head;
                while (adjListPtr)
                {
                    adjlist_node_p tmp = adjListPtr;
                    adjListPtr = adjListPtr->next;
                    free(tmp);
                }
            }
            /*Free the adjacency list array*/
            free(graph->adjListArr);
        }
        /*Free the graph*/
        free(graph);
    }
}

/* Adds an edge to a graph*/
void addEdge(graph_t *graph, int src, int dest)
{
    /* Add an edge from src to dst in the adjacency list*/
    adjlist_node_p newNode = createNode(dest);
    newNode->next = graph->adjListArr[src].head;
    graph->adjListArr[src].head = newNode;
    graph->adjListArr[src].num_members++;

    if(graph->type == UNDIRECTED)
    {
        /* Add an edge from dest to src also*/
        newNode = createNode(src);
        newNode->next = graph->adjListArr[dest].head;
        graph->adjListArr[dest].head = newNode;
        graph->adjListArr[dest].num_members++;
    }
}

/* Function to print the adjacency list of graph*/
void displayGraph(graph_p graph)
{
    int i;
    for (i = 0; i < graph->num_vertices; i++)
    {
        adjlist_node_p adjListPtr = graph->adjListArr[i].head;
        printf("\n%d: ", i);
        while (adjListPtr)
        {
            printf("%d->", adjListPtr->vertex);
            adjListPtr = adjListPtr->next;
        }
        printf("NULL\n");
    }
}

int main()
{
    graph_p undir_graph = createGraph(5, UNDIRECTED);
    graph_p dir_graph = createGraph(5, DIRECTED);
    addEdge(undir_graph, 0, 1);
    addEdge(undir_graph, 0, 4);
    addEdge(undir_graph, 1, 2);
    addEdge(undir_graph, 1, 3);
    addEdge(undir_graph, 1, 4);
    addEdge(undir_graph, 2, 3);
    addEdge(undir_graph, 3, 4);

    addEdge(dir_graph, 0, 1);
    addEdge(dir_graph, 0, 4);
    addEdge(dir_graph, 1, 2);
    addEdge(dir_graph, 1, 3);
    addEdge(dir_graph, 1, 4);
    addEdge(dir_graph, 2, 3);
    addEdge(dir_graph, 3, 4);

    printf("\nUNDIRECTED GRAPH");
    displayGraph(undir_graph);
    destroyGraph(undir_graph);

    printf("\nDIRECTED GRAPH");
    displayGraph(dir_graph);
    destroyGraph(dir_graph);

    return 0;
}

Sources:
http://en.wikipedia.org/wiki/Graph_(mathematics)
http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html
http://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx

Trie implementation in C

noreply@blogger.com (Anonymous) — Thu, 08 Nov 2012 14:01:00 +0000

To implement the kind of storage which stores strings as the search keys , there is a need to have special data structures which can store the strings efficiently and the searching of data based on the string keys is easier, efficient and faster. One such data structure is a tree based implementation called Trie.

Trie is a data structure which can be used to implement a dictionary kind of application. It provides all the functionality to insert a string, search a string and delete a string from the dictionary. The insertion and deletion operation takes O(n) time where n is the length of the string to be deleted or inserted.

Some of the application of tries involve web based search engines, URL completion in autocomplete feature, Spell checker etc.

Structure of Trie(Specific to this implementation):

The trie implemented here consists of nodes. Each node has these fields:

Key - Part of the string to be serached,inserted or deleted.
Value - The value associated with a string (e.g In a dictionary it could be the meaning of the word which we are searching)
Neighbour node address - It consists of the address of the neighbouring node at the same level.
Previous neighbour address - It consists of the address of the previous node at the same level.
Children node address - It consists of the address of the child nodes of the current node.
Parent node address - It consists of the address of the parent node of the current node.

The additional nodes like Parent and Previous nodes are added to this implementation for making the search, and deletions easier.

Here is a diagrammatical view of a trie nodes I have used in this implementation. The field key is not represented in the diagram due to symmetry purposes.

Let us consider an example to understand tries in detail.

Suppose we have to implement a database for the HR department of an organisation in which we have to store an employee's name and their ages. There is an assumption for this example that there each employee's name is unique.So there is a strange policy in this organisation that any new employee which has a name that already exists in the organisation, it would not hire that new employee.

Let's use this hypothetical example just to understand how tries work.

Consider we have a new employee named Andrew with age 36. Lets populate our trie for "andrew".

Now add "tina".

Add "argo".

Add "tim".

Add "t".

Add "amy".

Add "aramis".

This is the complete Trie with all the entries. Now let us try deleting the names. I am not capturing the trivial cases.

Lets try deleting Argo.

Delete Tina

Delete Andrew

There is also a video from IIT Delhi which explains the tries. Tries Explained.
The implementation for this Trie is given below. Please provide your suggestions to further improve the implementation.

/*trie.h*/
typedef int trieVal_t;

typedef struct trieNode {
    char key;
    trieVal_t value;
    struct trieNode *next;
    struct trieNode *prev;
    struct trieNode *children;
    struct trieNode *parent;
} trieNode_t;

void TrieCreate(trieNode_t **root);
trieNode_t* TrieSearch(trieNode_t *root, const char *key);
void TrieAdd(trieNode_t **root, char *key, int data);
void TrieRemove(trieNode_t **root, char *key);
void TrieDestroy( trieNode_t* root );

/*trie.c*/
#include <stdio.h>
#include "trie.h"
#include <stdlib.h>

trieNode_t *TrieCreateNode(char key, int data);

void TrieCreate(trieNode_t **root)
{
 *root = TrieCreateNode('\0', 0xffffffff);
}

trieNode_t *TrieCreateNode(char key, int data)
{
 trieNode_t *node = NULL;
 node = (trieNode_t *)malloc(sizeof(trieNode_t));

 if(NULL == node)
 {
  printf("Malloc failed\n");
  return node;
 }

 node->key = key;
 node->next = NULL;
 node->children = NULL;
 node->value = data;
 node->parent= NULL;
 node->prev= NULL;
 return node;
}

void TrieAdd(trieNode_t **root, char *key, int data)
{
 trieNode_t *pTrav = NULL;

 if(NULL == *root)
 {
  printf("NULL tree\n");
  return;
 }
#ifdef DEBUG
 printf("\nInserting key %s: \n",key);
#endif
 pTrav = (*root)->children;



 if(pTrav == NULL)
 {
  /*First Node*/
  for(pTrav = *root; *key; pTrav = pTrav->children)
  {
   pTrav->children = TrieCreateNode(*key, 0xffffffff);
   pTrav->children->parent = pTrav;
#ifdef DEBUG
   printf("Inserting: [%c]\n",pTrav->children->key);
#endif
   key++;
  }

  pTrav->children = TrieCreateNode('\0', data);
  pTrav->children->parent = pTrav;
#ifdef DEBUG
  printf("Inserting: [%c]\n",pTrav->children->key);
#endif
  return;
 }

 if(TrieSearch(pTrav, key))
 {
  printf("Duplicate!\n");
  return;
 }

 while(*key != '\0')
 {
  if(*key == pTrav->key)
  {
   key++;
#ifdef DEBUG
   printf("Traversing child: [%c]\n",pTrav->children->key);
#endif
   pTrav = pTrav->children;
  }
  else
   break;
 }

 while(pTrav->next)
 {
  if(*key == pTrav->next->key)
  {
   key++;
   TrieAdd(&(pTrav->next), key, data);
   return;
  }
  pTrav = pTrav->next;
 }

 if(*key)
 {
  pTrav->next = TrieCreateNode(*key, 0xffffffff);
 }
 else
 {
  pTrav->next = TrieCreateNode(*key, data);
 }

 pTrav->next->parent = pTrav->parent;
 pTrav->next->prev = pTrav;

#ifdef DEBUG
 printf("Inserting [%c] as neighbour of [%c] \n",pTrav->next->key, pTrav->key);
#endif

 if(!(*key))
  return;

 key++;

 for(pTrav = pTrav->next; *key; pTrav = pTrav->children)
 {
  pTrav->children = TrieCreateNode(*key, 0xffffffff);
  pTrav->children->parent = pTrav;
#ifdef DEBUG
  printf("Inserting: [%c]\n",pTrav->children->key);
#endif
  key++;
 }

 pTrav->children = TrieCreateNode('\0', data);
 pTrav->children->parent = pTrav;
#ifdef DEBUG
 printf("Inserting: [%c]\n",pTrav->children->key);
#endif
 return;
}

trieNode_t* TrieSearch(trieNode_t *root, const char *key)
{
 trieNode_t *level = root;
 trieNode_t *pPtr = NULL;

 int lvl=0;
 while(1)
 {
  trieNode_t *found = NULL;
  trieNode_t *curr;

  for (curr = level; curr != NULL; curr = curr->next)
  {
   if (curr->key == *key)
   {
    found = curr;
    lvl++;
    break;
   }
  }

  if (found == NULL)
   return NULL;

  if (*key == '\0')
  {
   pPtr = curr;
   return pPtr;
  }

  level = found->children;
  key++;
 }
}

void TrieRemove(trieNode_t **root, char *key)
{
 trieNode_t *tPtr = NULL;
 trieNode_t *tmp = NULL;

 if(NULL == *root || NULL == key)
  return;

 tPtr = TrieSearch((*root)->children, key);

 if(NULL == tPtr)
 {
  printf("Key [%s] not found in trie\n", key);
  return;
 }

#ifdef DEBUG
 printf("Deleting key [%s] from trie\n", key);
#endif

 while(1)
 {
  if( tPtr->prev && tPtr->next)
  {
   tmp = tPtr;
   tPtr->next->prev = tPtr->prev;
   tPtr->prev->next = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else if(tPtr->prev && !(tPtr->next))
  {
   tmp = tPtr;
   tPtr->prev->next = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else if(!(tPtr->prev) && tPtr->next)
  {
   tmp = tPtr;
   tPtr->parent->children = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else
  {
   tmp = tPtr;
   tPtr = tPtr->parent;
   tPtr->children = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
 }

#ifdef DEBUG
 printf("Deleted key [%s] from trie\n", key);
#endif
}


void TrieDestroy( trieNode_t* root )
{
 trieNode_t *tPtr = root;
 trieNode_t *tmp = root;

    while(tPtr)
 {
  while(tPtr->children)
   tPtr = tPtr->children;

  if( tPtr->prev && tPtr->next)
  {
   tmp = tPtr;
   tPtr->next->prev = tPtr->prev;
   tPtr->prev->next = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else if(tPtr->prev && !(tPtr->next))
  {
   tmp = tPtr;
   tPtr->prev->next = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else if(!(tPtr->prev) && tPtr->next)
  {
   tmp = tPtr;
   tPtr->parent->children = tPtr->next;
   tPtr->next->prev = NULL;
   tPtr = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else
  {
   tmp = tPtr;
   if(tPtr->parent == NULL)
   {
    /*Root*/
    free(tmp);
    return;
   }
   tPtr = tPtr->parent;
   tPtr->children = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
 }

}

/*triedriver.c*/
/*
 * To Compile : gcc -o trie trie.c triedriver.c
 * To run: ./trie
 */
#include <stdio.h>
#include <stdlib.h>
#include "trie.h"

int main()
{
    trieNode_t *root;
    printf("Trie Example\n");
    
    /*Create a trie*/
    TrieCreate(&root);
    
    TrieAdd(&root, "andrew", 1);
    TrieAdd(&root, "tina", 2);
    TrieAdd(&root, "argo", 3);
    TrieAdd(&root, "timor", 5);
    TrieRemove(&root, "tim");
    TrieAdd(&root, "tim", 6);
    TrieRemove(&root, "tim");
    TrieAdd(&root, "ti", 6);
    TrieAdd(&root, "amy", 7);
    TrieAdd(&root, "aramis", 8);

    /*Destroy the trie*/
    TrieDestroy(root);
}

In order to print the debug messages, use -DDEBUG while compiling with gcc:

gcc -o trie trie.c triedriver.c -DDEBUG

Abstract Binary Search Tree Implementation in C

noreply@blogger.com (Varun) — Wed, 31 Oct 2012 14:16:00 +0000

There are several ways to store data using different data structures like Array, Linked Lists , Trees, Graphs, Hashmaps etc. The choice of the data structure depends on the application which extracts that data. On searching the web , one can easily find out which data structure is required for their application. Binary Search Tree is one such data structure which is generally used for storing data.

A binary search tree consists of members called as nodes which have the data embedded in them. Generally, a BST node contains address fields and data field. The structure of a BST is something like this :

Each node can have a left subtree and right subtree which may or may not have any nodes.

Binary Search tree has some properties which identifies it :

The left subtree members have a value which is always less than the value at the root node
The right subtree members have a value which is always greater than the value at the root node
Both the subtrees must be also a BST.

The implementation provided in this post uses an abstract data type (void). To use this implementation as it is, one must implement these two functions

Comparison Function - This function compares the data between two nodes. This function must return -1, 0 or 1 only. The signature for this function is int <function-name> (void * data1, void * data2).

Function should return 1 when data1 is greater than data2.
Function should return -1 when data1 is lesser than data2.
Function should return 0 when data1 is equal to data2.

Display Function - This function is used for display purposes only. It displays the node data.

A sample implementation of these two functions is presented in the driver example(bstdriver.c) for the BST. This sample implementation uses int type as data.

 
/*bst.h*/
typedef struct bstNode
{
    struct bstNode *left;       /*Left Child*/
    struct bstNode *right;      /*Right Child*/
    struct bstNode *parent;     /*Parent Child*/
    void *data;                 /*Data*/
}BSTNode;

void BSTDestroy(BSTNode *root);
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *));
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *));

 
/*bst.c*/
#include <stdio.h>
#include <stdlib.h>

#include "bst.h"

/* @brief Function to determine if a child is a left child or right child in a BST
 * @param data Pointer to the data to be used
 * @return LEFT - if left child
 *         RIGHT - if right child
 */
static inline const char* BSTFindChildLoc(BSTNode *parent, BSTNode *child)
{
    return (((parent->left)==(child))?"LEFT":"RIGHT");
}

/* @brief Function to swap data between two nodes in a BST
 * @param data Pointer to the data to be used
 * @return void
 */
static inline void BSTSwapNodeData(BSTNode **node1, BSTNode **node2 )
{
    void *tmp;
    tmp = (*node1)->data;
    (*node1)->data = (*node2)->data;
    (*node2)->data = tmp;
}

/* @brief Function to create a node in a BST
 * @param data Pointer to the data to be used
 * @return Address of the node created
 */
BSTNode* BSTCreateNode(void *data)
{
    /*Allocate memory*/
    BSTNode* node= (BSTNode*)malloc(sizeof(BSTNode));

    if(NULL == node)
    {
        printf("Error: Memory Allocation could not be completed\n");
        return NULL;
    }

    /*Initialize links*/
    node->left = NULL;
    node->right= NULL;
    node->parent= NULL;
    node->data = data;

    printf("Allocated Node with address %p\n", node);
    return node;
}

/* @brief Function to destroy all nodes in a BST
 * @param root Pointer to the root of the BST
 * @return void
 */
void BSTDestroy(BSTNode *root)
{
    if(root)
    {
        /*Traverse down the left subtree*/
        if(root->left)
            BSTDestroy(root->left);
        /*Traverse down the right subtree*/
        if(root->right)
            BSTDestroy(root->right);
        /*Free the memory*/
        free(root);
        printf("DeAllocated Node with address %p\n", root);
    }
}

/* @brief Function to insert a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be inserted
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *tmp = NULL;
    BSTNode *ptr = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }


    if(!(*root))
    {
        /*Create a node*/
        tmp = BSTCreateNode(data);

        if(NULL == tmp)
        {
            printf("Error: Node insertion failed\n");
            return;
        }

        /*Root Node*/
        *root = tmp;
        return;
    }

    ptr = *root;

    /*If data is greater than the current node's data*/
    if(cmp_fn(data,ptr->data) == 1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->right == NULL)
        {
            /*Create a node*/
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->right = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->right), data, cmp_fn);
        }
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data,ptr->data) == -1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->left == NULL)
        {
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->left = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->left), data, cmp_fn);
        }
    }
    /*If data is equal to the current node's data*/
    else
        printf("Error: Duplicate\n");
}

/* @brief Function to find the minimum valued node in the left subtree of a node
 * @param node Pointer to the node whose min valued child in left subtree has to be found
 * @return Address of the minimum valued node in the left subtree
 */
static BSTNode* BSTMinVal(BSTNode* node)
{
    BSTNode* current = node;

  /*Go to the leftmost member of the tree */
  while (current->left != NULL)
  {
    current = current->left;
  }
  return current;
}

/* @brief Function to find the Inorder successor of a node in a BST
 * @param node Pointer to the node whose inorder successor has to be found
 * @return Address of the Inorder successor
 */
static BSTNode* BSTInorderSuccessor(BSTNode* node)
{
    BSTNode *inOrdSucc = NULL;
    if(NULL == node)
        return NULL;

    /*Traverse the right subtree and find the minimum value */
    if( node->right != NULL )
        return BSTMinVal(node->right);

    inOrdSucc = node->parent;

    while(inOrdSucc != NULL && node == inOrdSucc->right)
    {
        node = inOrdSucc;
        inOrdSucc = inOrdSucc->parent;
    }
    return inOrdSucc;

}

/* @brief Helper Function to update the parent node links in a BST
 * @param node Pointer to pointer to the node whose parent will be updated
 * @param ptr Target Link
 * @return void
 */
static inline void updateParent(BSTNode **node, BSTNode *ptr)
{
    /*If the child is a left child*/
    if(BSTFindChildLoc((*node)->parent, *node) == "LEFT")
    {
        (*node)->parent->left = ptr;
    }
    /*If the child is a right child*/
    else
    {
        (*node)->parent->right = ptr;
    }
}

/* @brief Function to delete a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;
    BSTNode *tmp = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }

    /*Search if the node exists in the BST*/
    ptr = BSTSearch(*root, data, cmp_fn);

    if(NULL == ptr)
    {
        printf("Error: Node not found\n");
        return;
    }

    /*If the node has no children*/
    if(ptr->left == NULL && ptr->right == NULL)
    {
        /*No children*/
         tmp = ptr;

         /*Non-Root Node*/
         if(ptr->parent)
            updateParent(&ptr, NULL);   /*Update the parent's link*/
         /*Root Node*/
         else
             *root = NULL;

         ptr = NULL;
         free(tmp);
         printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has single child*/
    else if((ptr->left != NULL && ptr->right == NULL) || (ptr->left == NULL && ptr->right != NULL))
    {
        tmp = ptr;

        /*Single Child*/
        if((ptr->left != NULL) && (ptr->right == NULL))
        {
            ptr->left->parent = ptr->parent;

            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->left);   /*Update the parent's link*/
            /*Root Node*/
            else
                *root = ptr->left;
        }
        else
        {
            ptr->right->parent = ptr->parent;   /*Update the parent's link*/
            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->right);
            /*Root Node*/
            else
                *root = ptr->right;
        }

        free(tmp);
        printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has two children*/
    else if((ptr->left != NULL) && (ptr->right != NULL))
    {
        /*Find the inorder successor of the node*/
        BSTNode *inOrdSucc = BSTInorderSuccessor(ptr);

        /*Swap the node's data with inorder successor's data*/
        BSTSwapNodeData(&ptr, &inOrdSucc);

        /*Delete the inorder successor node*/
        BSTDelete(&inOrdSucc, data, cmp_fn);
    }
}

/* @brief Function to search a data in a BST
 * @param root Pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return Address of the node found
 *         NULL if node not found
 */
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;

    if(NULL == root)
        return NULL;

    ptr = root;

    /*If the data is found*/
    if(cmp_fn(data, ptr->data) == 0)
    {
        return ptr;
    }
    /*If data is greater than the current node's data*/
    else if(cmp_fn(data, ptr->data) == 1)
    {
        return BSTSearch(ptr->right, data, cmp_fn);
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data, ptr->data) == -1)
    {
        return BSTSearch(ptr->left, data, cmp_fn);
    }

    return NULL;
}

/* @brief Function to traverse all nodes in a BST in InOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTInOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTInOrder(root->left, display_fn);

    printf("[%p]",root->data);
    display_fn(root);

    if(root->right)
        BSTInOrder(root->right, display_fn);

}

/* @brief Function to traverse all nodes in a BST in PostOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPostOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTPostOrder(root->left, display_fn);

    if(root->right)
        BSTPostOrder(root->right, display_fn);

    printf("[%p]",root->data);
    display_fn(root);
}

/* @brief Function to traverse all nodes in a BST in PreOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPreOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    printf("[%p]",root->data);
    display_fn(root);

    if(root->left)
        BSTPreOrder(root->left, display_fn);

    if(root->right)
        BSTPreOrder(root->right, display_fn);

}

/* @brief Function to display all nodes in a BST
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *))
{
    printf("InOrder ->",root->data);
    BSTInOrder(root,display_fn);
    printf("\n",root->data);

    printf("PreOrder ->",root->data);
    BSTPreOrder(root,display_fn);
    printf("\n",root->data);

    printf("PostOrder ->",root->data);
    BSTPostOrder(root,display_fn);
    printf("\n",root->data);
}

 
/*bstdriver.c*/
/*
 * Compile: gcc -o test bst.c bstdriver.c
 * Run: ./test
 */
#include <stdio.h>
#include "bst.h"

int data[]={9,1,6,3,8,4,2,5,7};

/*Comparison function*/
int cmp_fn(void *data1, void *data2)
{
    if(*((int*)data1) > *((int*)data2))
        return 1;
    else if(*((int*)data1) < *((int*)data2))
        return -1;
    else
        return 0;
}

/*Display Function*/
static void displayNode(BSTNode *node)
{
    if(node)
        printf("%d ",*((int*)node->data));
}

int main()
{
    BSTNode *root = NULL;

    int i,sVal=-1;
    int size = sizeof(data)/sizeof(data[0]);

    for(i=0; i < size; i++)
        BSTInsert(&root, &data[i], cmp_fn);

    BSTDisplay(root, displayNode);

    printf("Search Value : ");
    scanf("%d", &sVal);

    if(NULL == BSTSearch(root, &sVal, cmp_fn))
        printf("Not Found\n");
    else
        printf("Found\n");

    printf("Delete Value : ");
    scanf("%d", &sVal);
    BSTDelete(&root, &sVal, cmp_fn);
    BSTDisplay(root, displayNode);

    BSTDestroy(root);
}

FTP implementation in C

noreply@blogger.com (Varun) — Sun, 23 Sep 2012 18:31:00 +0000

Most of the beginners would wonder how the known services work. Well this post will give an overview of one of the well-written services in C , the FTP application. I thought that there is no need to re-invent the wheel and use this code as is from Apple's open source initiative.The code is written in C.

I am providing the code only for the main file which contains FTP specific functions. The rest of the supporting files including the Makefile can be downloaded from here.

Disclaimer : This code is taken from Apple Opensource . I don't want Apple to sue me ;)

 /*ftp.c*/

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * "Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  This file contains Original Code and/or Modifications of
 * Original Code as defined in and that are subject to the Apple Public
 * Source License Version 1.0 (the 'License').  You may not use this file
 * except in compliance with the License.  Please obtain a copy of the
 * License at http://www.apple.com/publicsource and read it before using
 * this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License."
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 * Copyright (c) 1985, 1989, 1993, 1994
 * The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 * This product includes software developed by the University of
 * California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */


#include <sys/param.h>
#include <sys/stat.h>
#include <sys/ioctl.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/file.h>

#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>
#include <arpa/inet.h>
#include <arpa/ftp.h>
#include <arpa/telnet.h>

#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <netdb.h>
#include <pwd.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdarg.h>

#include "ftp_var.h"

extern int h_errno;

struct sockaddr_in hisctladdr;
struct sockaddr_in data_addr;
int data = -1;
int abrtflag = 0;
jmp_buf ptabort;
int ptabflg;
int ptflag = 0;
struct sockaddr_in myctladdr;
off_t restart_point = 0;

FILE *cin, *cout;

char *
hookup(host, port)
 char *host;
 int port;
{
 struct hostent *hp = 0;
 int s, len, tos;
 static char hostnamebuf[80];

 memset((char *)&hisctladdr, 0, sizeof (hisctladdr));
 hisctladdr.sin_addr.s_addr = inet_addr(host);
 if (hisctladdr.sin_addr.s_addr != -1) {
  hisctladdr.sin_family = AF_INET;
  (void) strncpy(hostnamebuf, host, sizeof(hostnamebuf));
 } else {
  hp = gethostbyname(host);
  if (hp == NULL) {
   warnx("%s: %s", host, hstrerror(h_errno));
   code = -1;
   return ((char *) 0);
  }
  hisctladdr.sin_family = hp->h_addrtype;
  memmove((caddr_t)&hisctladdr.sin_addr,
    hp->h_addr_list[0], hp->h_length);
  (void) strncpy(hostnamebuf, hp->h_name, sizeof(hostnamebuf));
 }
 hostname = hostnamebuf;
 s = socket(hisctladdr.sin_family, SOCK_STREAM, 0);
 if (s < 0) {
  warn("socket");
  code = -1;
  return (0);
 }
 hisctladdr.sin_port = port;
 while (connect(s, (struct sockaddr *)&hisctladdr, sizeof (hisctladdr)) < 0) {
  if (hp && hp->h_addr_list[1]) {
   int oerrno = errno;
   char *ia;

   ia = inet_ntoa(hisctladdr.sin_addr);
   errno = oerrno;
   warn("connect to address %s", ia);
   hp->h_addr_list++;
   memmove((caddr_t)&hisctladdr.sin_addr,
     hp->h_addr_list[0], hp->h_length);
   fprintf(stdout, "Trying %s...\n",
    inet_ntoa(hisctladdr.sin_addr));
   (void) close(s);
   s = socket(hisctladdr.sin_family, SOCK_STREAM, 0);
   if (s < 0) {
    warn("socket");
    code = -1;
    return (0);
   }
   continue;
  }
  warn("connect");
  code = -1;
  goto bad;
 }
 len = sizeof (myctladdr);
 if (getsockname(s, (struct sockaddr *)&myctladdr, &len) < 0) {
  warn("getsockname");
  code = -1;
  goto bad;
 }
#ifdef IP_TOS
 tos = IPTOS_LOWDELAY;
 if (setsockopt(s, IPPROTO_IP, IP_TOS, (char *)&tos, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 cin = fdopen(s, "r");
 cout = fdopen(s, "w");
 if (cin == NULL || cout == NULL) {
  warnx("fdopen failed.");
  if (cin)
   (void) fclose(cin);
  if (cout)
   (void) fclose(cout);
  code = -1;
  goto bad;
 }
 if (verbose)
  printf("Connected to %s.\n", hostname);
 if (getreply(0) > 2) {  /* read startup message from server */
  if (cin)
   (void) fclose(cin);
  if (cout)
   (void) fclose(cout);
  code = -1;
  goto bad;
 }
#ifdef SO_OOBINLINE
 {
 int on = 1;

 if (setsockopt(s, SOL_SOCKET, SO_OOBINLINE, (char *)&on, sizeof(on))
  < 0 && debug) {
   warn("setsockopt");
  }
 }
#endif /* SO_OOBINLINE */

 return (hostname);
bad:
 (void) close(s);
 return ((char *)0);
}

int
login(host)
 char *host;
{
 char tmp[80];
 char *user, *pass, *acct;
 int n, aflag = 0;

 user = pass = acct = 0;
 if (ruserpass(host, &user, &pass, &acct) < 0) {
  code = -1;
  return (0);
 }
 while (user == NULL) {
  char *myname = getlogin();

  if (myname == NULL) {
   struct passwd *pp = getpwuid(getuid());

   if (pp != NULL)
    myname = pp->pw_name;
  }
  if (myname)
   printf("Name (%s:%s): ", host, myname);
  else
   printf("Name (%s): ", host);
  (void) fgets(tmp, sizeof(tmp) - 1, stdin);
  tmp[strlen(tmp) - 1] = '\0';
  if (*tmp == '\0')
   user = myname;
  else
   user = tmp;
 }
 n = command("USER %s", user);
 if (n == CONTINUE) {
  if (pass == NULL)
   pass = getpass("Password:");
  n = command("PASS %s", pass);
 }
 if (n == CONTINUE) {
  aflag++;
  acct = getpass("Account:");
  n = command("ACCT %s", acct);
 }
 if (n != COMPLETE) {
  warnx("Login failed.");
  return (0);
 }
 if (!aflag && acct != NULL)
  (void) command("ACCT %s", acct);
 if (proxy)
  return (1);
 for (n = 0; n < macnum; ++n) {
  if (!strcmp("init", macros[n].mac_name)) {
   (void) strcpy(line, "$init");
   makeargv();
   domacro(margc, margv);
   break;
  }
 }
 return (1);
}

void
cmdabort()
{

 printf("\n");
 (void) fflush(stdout);
 abrtflag++;
 if (ptflag)
  longjmp(ptabort,1);
}

int command(const char *fmt, ...)
{
 va_list ap;
 int r;
 sig_t oldintr;

 abrtflag = 0;
 if (debug) {
  printf("---> ");
  va_start(ap, fmt);
  if (strncmp("PASS ", fmt, 5) == 0)
   printf("PASS XXXX");
  else 
   vfprintf(stdout, fmt, ap);
  va_end(ap);
  printf("\n");
  (void) fflush(stdout);
 }
 if (cout == NULL) {
  warn("No control connection for command");
  code = -1;
  return (0);
 }
 oldintr = signal(SIGINT, cmdabort);
 va_start(ap, fmt);
 vfprintf(cout, fmt, ap);
 va_end(ap);
 fprintf(cout, "\r\n");
 (void) fflush(cout);
 cpend = 1;
 r = getreply(!strcmp(fmt, "QUIT"));
 if (abrtflag && oldintr != SIG_IGN)
  (*oldintr)(SIGINT);
 (void) signal(SIGINT, oldintr);
 return (r);
}

char reply_string[BUFSIZ];  /* last line of previous reply */

int
getreply(expecteof)
 int expecteof;
{
 int c, n;
 int dig;
 int originalcode = 0, continuation = 0;
 sig_t oldintr;
 int pflag = 0;
 char *cp, *pt = pasv;

 oldintr = signal(SIGINT, cmdabort);
 for (;;) {
  dig = n = code = 0;
  cp = reply_string;
  while ((c = getc(cin)) != '\n') {
   if (c == IAC) {     /* handle telnet commands */
    switch (c = getc(cin)) {
    case WILL:
    case WONT:
     c = getc(cin);
     fprintf(cout, "%c%c%c", IAC, DONT, c);
     (void) fflush(cout);
     break;
    case DO:
    case DONT:
     c = getc(cin);
     fprintf(cout, "%c%c%c", IAC, WONT, c);
     (void) fflush(cout);
     break;
    default:
     break;
    }
    continue;
   }
   dig++;
   if (c == EOF) {
    if (expecteof) {
     (void) signal(SIGINT,oldintr);
     code = 221;
     return (0);
    }
    lostpeer();
    if (verbose) {
     printf("421 Service not available, remote server has closed connection\n");
     (void) fflush(stdout);
    }
    code = 421;
    return (4);
   }
   if (c != '\r' && (verbose > 0 ||
       (verbose > -1 && n == '5' && dig > 4))) {
    if (proxflag &&
       (dig == 1 || dig == 5 && verbose == 0))
     printf("%s:",hostname);
    (void) putchar(c);
   }
   if (dig < 4 && isdigit(c))
    code = code * 10 + (c - '0');
   if (!pflag && code == 227)
    pflag = 1;
   if (dig > 4 && pflag == 1 && isdigit(c))
    pflag = 2;
   if (pflag == 2) {
    if (c != '\r' && c != ')')
     *pt++ = c;
    else {
     *pt = '\0';
     pflag = 3;
    }
   }
   if (dig == 4 && c == '-') {
    if (continuation)
     code = 0;
    continuation++;
   }
   if (n == 0)
    n = c;
   if (cp < &reply_string[sizeof(reply_string) - 1])
    *cp++ = c;
  }
  if (verbose > 0 || verbose > -1 && n == '5') {
   (void) putchar(c);
   (void) fflush (stdout);
  }
  if (continuation && code != originalcode) {
   if (originalcode == 0)
    originalcode = code;
   continue;
  }
  *cp = '\0';
  if (n != '1')
   cpend = 0;
  (void) signal(SIGINT,oldintr);
  if (code == 421 || originalcode == 421)
   lostpeer();
  if (abrtflag && oldintr != cmdabort && oldintr != SIG_IGN)
   (*oldintr)(SIGINT);
  return (n - '0');
 }
}

int
empty(mask, sec)
 struct fd_set *mask;
 int sec;
{
 struct timeval t;

 t.tv_sec = (long) sec;
 t.tv_usec = 0;
 return (select(32, mask, (struct fd_set *) 0, (struct fd_set *) 0, &t));
}

jmp_buf sendabort;

void
abortsend()
{

 mflag = 0;
 abrtflag = 0;
 printf("\nsend aborted\nwaiting for remote to finish abort\n");
 (void) fflush(stdout);
 longjmp(sendabort, 1);
}

#define HASHBYTES 1024

void
sendrequest(cmd, local, remote, printnames)
 char *cmd, *local, *remote;
 int printnames;
{
 struct stat st;
 struct timeval start, stop;
 int c, d;
 FILE *fin, *dout = 0, *popen();
 int (*closefunc) __P((FILE *));
 sig_t oldintr, oldintp;
 long bytes = 0, hashbytes = HASHBYTES;
 char *lmode, buf[BUFSIZ], *bufp;

 if (verbose && printnames) {
  if (local && *local != '-')
   printf("local: %s ", local);
  if (remote)
   printf("remote: %s\n", remote);
 }
 if (proxy) {
  proxtrans(cmd, local, remote);
  return;
 }
 if (curtype != type)
  changetype(type, 0);
 closefunc = NULL;
 oldintr = NULL;
 oldintp = NULL;
 lmode = "w";
 if (setjmp(sendabort)) {
  while (cpend) {
   (void) getreply(0);
  }
  if (data >= 0) {
   (void) close(data);
   data = -1;
  }
  if (oldintr)
   (void) signal(SIGINT,oldintr);
  if (oldintp)
   (void) signal(SIGPIPE,oldintp);
  code = -1;
  return;
 }
 oldintr = signal(SIGINT, abortsend);
 if (strcmp(local, "-") == 0)
  fin = stdin;
 else if (*local == '|') {
  oldintp = signal(SIGPIPE,SIG_IGN);
  fin = popen(local + 1, "r");
  if (fin == NULL) {
   warn("%s", local + 1);
   (void) signal(SIGINT, oldintr);
   (void) signal(SIGPIPE, oldintp);
   code = -1;
   return;
  }
  closefunc = pclose;
 } else {
  fin = fopen(local, "r");
  if (fin == NULL) {
   warn("local: %s", local);
   (void) signal(SIGINT, oldintr);
   code = -1;
   return;
  }
  closefunc = fclose;
  if (fstat(fileno(fin), &st) < 0 ||
      (st.st_mode&S_IFMT) != S_IFREG) {
   fprintf(stdout, "%s: not a plain file.\n", local);
   (void) signal(SIGINT, oldintr);
   fclose(fin);
   code = -1;
   return;
  }
 }
 if (initconn()) {
  (void) signal(SIGINT, oldintr);
  if (oldintp)
   (void) signal(SIGPIPE, oldintp);
  code = -1;
  if (closefunc != NULL)
   (*closefunc)(fin);
  return;
 }
 if (setjmp(sendabort))
  goto abort;

 if (restart_point &&
     (strcmp(cmd, "STOR") == 0 || strcmp(cmd, "APPE") == 0)) {
  int rc;

  switch (curtype) {
  case TYPE_A:
   rc = fseek(fin, (long) restart_point, SEEK_SET);
   break;
  case TYPE_I:
  case TYPE_L:
   rc = lseek(fileno(fin), restart_point, SEEK_SET);
   break;
  }
  if (rc < 0) {
   warn("local: %s", local);
   restart_point = 0;
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
  if (command("REST %ld", (long) restart_point)
   != CONTINUE) {
   restart_point = 0;
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
  restart_point = 0;
  lmode = "r+w";
 }
 if (remote) {
  if (command("%s %s", cmd, remote) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   if (oldintp)
    (void) signal(SIGPIPE, oldintp);
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
 } else
  if (command("%s", cmd) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   if (oldintp)
    (void) signal(SIGPIPE, oldintp);
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
 dout = dataconn(lmode);
 if (dout == NULL)
  goto abort;
 (void) gettimeofday(&start, (struct timezone *)0);
 oldintp = signal(SIGPIPE, SIG_IGN);
 switch (curtype) {

 case TYPE_I:
 case TYPE_L:
  errno = d = 0;
  while ((c = read(fileno(fin), buf, sizeof (buf))) > 0) {
   bytes += c;
   for (bufp = buf; c > 0; c -= d, bufp += d)
    if ((d = write(fileno(dout), bufp, c)) <= 0)
     break;
   if (hash) {
    while (bytes >= hashbytes) {
     (void) putchar('#');
     hashbytes += HASHBYTES;
    }
    (void) fflush(stdout);
   }
  }
  if (hash && bytes > 0) {
   if (bytes < HASHBYTES)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (c < 0)
   warn("local: %s", local);
  if (d < 0) {
   if (errno != EPIPE) 
    warn("netout");
   bytes = -1;
  }
  break;

 case TYPE_A:
  while ((c = getc(fin)) != EOF) {
   if (c == '\n') {
    while (hash && (bytes >= hashbytes)) {
     (void) putchar('#');
     (void) fflush(stdout);
     hashbytes += HASHBYTES;
    }
    if (ferror(dout))
     break;
    (void) putc('\r', dout);
    bytes++;
   }
   (void) putc(c, dout);
   bytes++;
 /*  if (c == '\r') {      */
 /*  (void) putc('\0', dout);  // this violates rfc */
 /*   bytes++;    */
 /*  }                             */ 
  }
  if (hash) {
   if (bytes < hashbytes)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (ferror(fin))
   warn("local: %s", local);
  if (ferror(dout)) {
   if (errno != EPIPE)
    warn("netout");
   bytes = -1;
  }
  break;
 }
 if (closefunc != NULL)
  (*closefunc)(fin);
 (void) fclose(dout);
 (void) gettimeofday(&stop, (struct timezone *)0);
 (void) getreply(0);
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 if (bytes > 0)
  ptransfer("sent", bytes, &start, &stop);
 return;
abort:
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 if (!cpend) {
  code = -1;
  return;
 }
 if (data >= 0) {
  (void) close(data);
  data = -1;
 }
 if (dout)
  (void) fclose(dout);
 (void) getreply(0);
 code = -1;
 if (closefunc != NULL && fin != NULL)
  (*closefunc)(fin);
 (void) gettimeofday(&stop, (struct timezone *)0);
 if (bytes > 0)
  ptransfer("sent", bytes, &start, &stop);
}

jmp_buf recvabort;

void
abortrecv()
{

 mflag = 0;
 abrtflag = 0;
 printf("\nreceive aborted\nwaiting for remote to finish abort\n");
 (void) fflush(stdout);
 longjmp(recvabort, 1);
}

void
recvrequest(cmd, local, remote, lmode, printnames)
 char *cmd, *local, *remote, *lmode;
 int printnames;
{
 FILE *fout, *din = 0;
 int (*closefunc) __P((FILE *));
 sig_t oldintr, oldintp;
 int c, d, is_retr, tcrflag, bare_lfs = 0;
 static int bufsize;
 static char *buf;
 long bytes = 0, hashbytes = HASHBYTES;
 struct timeval start, stop;
 struct stat st;

 is_retr = strcmp(cmd, "RETR") == 0;
 if (is_retr && verbose && printnames) {
  if (local && *local != '-')
   printf("local: %s ", local);
  if (remote)
   printf("remote: %s\n", remote);
 }
 if (proxy && is_retr) {
  proxtrans(cmd, local, remote);
  return;
 }
 closefunc = NULL;
 oldintr = NULL;
 oldintp = NULL;
 tcrflag = !crflag && is_retr;
 if (setjmp(recvabort)) {
  while (cpend) {
   (void) getreply(0);
  }
  if (data >= 0) {
   (void) close(data);
   data = -1;
  }
  if (oldintr)
   (void) signal(SIGINT, oldintr);
  code = -1;
  return;
 }
 oldintr = signal(SIGINT, abortrecv);
 if (strcmp(local, "-") && *local != '|') {
  if (access(local, 2) < 0) {
   char *dir = strrchr(local, '/');

   if (errno != ENOENT && errno != EACCES) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (dir != NULL)
    *dir = 0;
   d = access(dir ? local : ".", 2);
   if (dir != NULL)
    *dir = '/';
   if (d < 0) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (!runique && errno == EACCES &&
       chmod(local, 0600) < 0) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (runique && errno == EACCES &&
      (local = gunique(local)) == NULL) {
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
  }
  else if (runique && (local = gunique(local)) == NULL) {
   (void) signal(SIGINT, oldintr);
   code = -1;
   return;
  }
 }
 if (!is_retr) {
  if (curtype != TYPE_A)
   changetype(TYPE_A, 0);
 } else if (curtype != type)
  changetype(type, 0);
 if (initconn()) {
  (void) signal(SIGINT, oldintr);
  code = -1;
  return;
 }
 if (setjmp(recvabort))
  goto abort;
 if (is_retr && restart_point &&
     command("REST %ld", (long) restart_point) != CONTINUE)
  return;
 if (remote) {
  if (command("%s %s", cmd, remote) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   return;
  }
 } else {
  if (command("%s", cmd) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   return;
  }
 }
 din = dataconn("r");
 if (din == NULL)
  goto abort;
 if (strcmp(local, "-") == 0)
  fout = stdout;
 else if (*local == '|') {
  oldintp = signal(SIGPIPE, SIG_IGN);
  fout = popen(local + 1, "w");
  if (fout == NULL) {
   warn("%s", local+1);
   goto abort;
  }
  closefunc = pclose;
 } else {
  fout = fopen(local, lmode);
  if (fout == NULL) {
   warn("local: %s", local);
   goto abort;
  }
  closefunc = fclose;
 }
 if (fstat(fileno(fout), &st) < 0 || st.st_blksize == 0)
  st.st_blksize = BUFSIZ;
 if (st.st_blksize > bufsize) {
  if (buf)
   (void) free(buf);
  buf = malloc((unsigned)st.st_blksize);
  if (buf == NULL) {
   warn("malloc");
   bufsize = 0;
   goto abort;
  }
  bufsize = st.st_blksize;
 }
 (void) gettimeofday(&start, (struct timezone *)0);
 switch (curtype) {

 case TYPE_I:
 case TYPE_L:
  if (restart_point &&
      lseek(fileno(fout), restart_point, SEEK_SET) < 0) {
   warn("local: %s", local);
   if (closefunc != NULL)
    (*closefunc)(fout);
   return;
  }
  errno = d = 0;
  while ((c = read(fileno(din), buf, bufsize)) > 0) {
   if ((d = write(fileno(fout), buf, c)) != c)
    break;
   bytes += c;
   if (hash) {
    while (bytes >= hashbytes) {
     (void) putchar('#');
     hashbytes += HASHBYTES;
    }
    (void) fflush(stdout);
   }
  }
  if (hash && bytes > 0) {
   if (bytes < HASHBYTES)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (c < 0) {
   if (errno != EPIPE)
    warn("netin");
   bytes = -1;
  }
  if (d < c) {
   if (d < 0)
    warn("local: %s", local);
   else
    warnx("%s: short write", local);
  }
  break;

 case TYPE_A:
  if (restart_point) {
   int i, n, ch;

   if (fseek(fout, 0L, SEEK_SET) < 0)
    goto done;
   n = restart_point;
   for (i = 0; i++ < n;) {
    if ((ch = getc(fout)) == EOF)
     goto done;
    if (ch == '\n')
     i++;
   }
   if (fseek(fout, 0L, SEEK_CUR) < 0) {
done:
    warn("local: %s", local);
    if (closefunc != NULL)
     (*closefunc)(fout);
    return;
   }
  }
  while ((c = getc(din)) != EOF) {
   if (c == '\n')
    bare_lfs++;
   while (c == '\r') {
    while (hash && (bytes >= hashbytes)) {
     (void) putchar('#');
     (void) fflush(stdout);
     hashbytes += HASHBYTES;
    }
    bytes++;
    if ((c = getc(din)) != '\n' || tcrflag) {
     if (ferror(fout))
      goto break2;
     (void) putc('\r', fout);
     if (c == '\0') {
      bytes++;
      goto contin2;
     }
     if (c == EOF)
      goto contin2;
    }
   }
   (void) putc(c, fout);
   bytes++;
 contin2: ;
  }
break2:
  if (bare_lfs) {
   printf("WARNING! %d bare linefeeds received in ASCII mode\n", bare_lfs);
   printf("File may not have transferred correctly.\n");
  }
  if (hash) {
   if (bytes < hashbytes)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (ferror(din)) {
   if (errno != EPIPE)
    warn("netin");
   bytes = -1;
  }
  if (ferror(fout))
   warn("local: %s", local);
  break;
 }
 if (closefunc != NULL)
  (*closefunc)(fout);
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 (void) fclose(din);
 (void) gettimeofday(&stop, (struct timezone *)0);
 (void) getreply(0);
 if (bytes > 0 && is_retr)
  ptransfer("received", bytes, &start, &stop);
 return;
abort:

/* abort using RFC959 recommended IP,SYNC sequence  */

 if (oldintp)
  (void) signal(SIGPIPE, oldintr);
 (void) signal(SIGINT, SIG_IGN);
 if (!cpend) {
  code = -1;
  (void) signal(SIGINT, oldintr);
  return;
 }

 abort_remote(din);
 code = -1;
 if (data >= 0) {
  (void) close(data);
  data = -1;
 }
 if (closefunc != NULL && fout != NULL)
  (*closefunc)(fout);
 if (din)
  (void) fclose(din);
 (void) gettimeofday(&stop, (struct timezone *)0);
 if (bytes > 0)
  ptransfer("received", bytes, &start, &stop);
 (void) signal(SIGINT, oldintr);
}

/*
 * Need to start a listen on the data channel before we send the command,
 * otherwise the server's connect may fail.
 */
int
initconn()
{
 char *p, *a;
 int result, len, tmpno = 0;
 int on = 1;
 int a0, a1, a2, a3, p0, p1;

 if (passivemode) {
  data = socket(AF_INET, SOCK_STREAM, 0);
  if (data < 0) {
   perror("ftp: socket");
   return(1);
  }
  if ((options & SO_DEBUG) &&
      setsockopt(data, SOL_SOCKET, SO_DEBUG, (char *)&on,
          sizeof (on)) < 0)
   perror("ftp: setsockopt (ignored)");
  if (command("PASV") != COMPLETE) {
   printf("Passive mode refused.\n");
   goto bad;
  }

  /*
   * What we've got at this point is a string of comma
   * separated one-byte unsigned integer values.
   * The first four are the an IP address. The fifth is
   * the MSB of the port number, the sixth is the LSB.
   * From that we'll prepare a sockaddr_in.
   */

  if (sscanf(pasv,"%d,%d,%d,%d,%d,%d",
      &a0, &a1, &a2, &a3, &p0, &p1) != 6) {
   printf("Passive mode address scan failure. "
          "Shouldn't happen!\n");
   goto bad;
  }

  bzero(&data_addr, sizeof(data_addr));
  data_addr.sin_family = AF_INET;
  a = (char *)&data_addr.sin_addr.s_addr;
  a[0] = a0 & 0xff;
  a[1] = a1 & 0xff;
  a[2] = a2 & 0xff;
  a[3] = a3 & 0xff;
  p = (char *)&data_addr.sin_port;
  p[0] = p0 & 0xff;
  p[1] = p1 & 0xff;

  if (connect(data, (struct sockaddr *)&data_addr,
       sizeof(data_addr)) < 0) {
   perror("ftp: connect");
   goto bad;
  }
#ifdef IP_TOS
  on = IPTOS_THROUGHPUT;
  if (setsockopt(data, IPPROTO_IP, IP_TOS, (char *)&on,
          sizeof(int)) < 0)
   perror("ftp: setsockopt TOS (ignored)");
#endif
  return(0);
 }

noport:
 data_addr = myctladdr;
 if (sendport)
  data_addr.sin_port = 0; /* let system pick one */ 
 if (data != -1)
  (void) close(data);
 data = socket(AF_INET, SOCK_STREAM, 0);
 if (data < 0) {
  warn("socket");
  if (tmpno)
   sendport = 1;
  return (1);
 }
 if (!sendport)
  if (setsockopt(data, SOL_SOCKET, SO_REUSEADDR, (char *)&on, sizeof (on)) < 0) {
   warn("setsockopt (reuse address)");
   goto bad;
  }
 if (bind(data, (struct sockaddr *)&data_addr, sizeof (data_addr)) < 0) {
  warn("bind");
  goto bad;
 }
 if (options & SO_DEBUG &&
     setsockopt(data, SOL_SOCKET, SO_DEBUG, (char *)&on, sizeof (on)) < 0)
  warn("setsockopt (ignored)");
 len = sizeof (data_addr);
 if (getsockname(data, (struct sockaddr *)&data_addr, &len) < 0) {
  warn("getsockname");
  goto bad;
 }
 if (listen(data, 1) < 0)
  warn("listen");
 if (sendport) {
  a = (char *)&data_addr.sin_addr;
  p = (char *)&data_addr.sin_port;
#define UC(b) (((int)b)&0xff)
  result =
      command("PORT %d,%d,%d,%d,%d,%d",
        UC(a[0]), UC(a[1]), UC(a[2]), UC(a[3]),
        UC(p[0]), UC(p[1]));
  if (result == ERROR && sendport == -1) {
   sendport = 0;
   tmpno = 1;
   goto noport;
  }
  return (result != COMPLETE);
 }
 if (tmpno)
  sendport = 1;
#ifdef IP_TOS
 on = IPTOS_THROUGHPUT;
 if (setsockopt(data, IPPROTO_IP, IP_TOS, (char *)&on, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 return (0);
bad:
 (void) close(data), data = -1;
 if (tmpno)
  sendport = 1;
 return (1);
}

FILE *
dataconn(lmode)
 char *lmode;
{
 struct sockaddr_in from;
 int s, fromlen = sizeof (from), tos;

 if (passivemode)
  return (fdopen(data, lmode));

 s = accept(data, (struct sockaddr *) &from, &fromlen);
 if (s < 0) {
  warn("accept");
  (void) close(data), data = -1;
  return (NULL);
 }
 (void) close(data);
 data = s;
#ifdef IP_TOS
 tos = IPTOS_THROUGHPUT;
 if (setsockopt(s, IPPROTO_IP, IP_TOS, (char *)&tos, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 return (fdopen(data, lmode));
}

void
ptransfer(direction, bytes, t0, t1)
 char *direction;
 long bytes;
 struct timeval *t0, *t1;
{
 struct timeval td;
 float s;
 long bs;

 if (verbose) {
  tvsub(&td, t1, t0);
  s = td.tv_sec + (td.tv_usec / 1000000.);
#define nz(x) ((x) == 0 ? 1 : (x))
  bs = bytes / nz(s);
  printf("%ld bytes %s in %.3g seconds (%ld bytes/s)\n",
      bytes, direction, s, bs);
 }
}

/*
void
tvadd(tsum, t0)
 struct timeval *tsum, *t0;
{

 tsum->tv_sec += t0->tv_sec;
 tsum->tv_usec += t0->tv_usec;
 if (tsum->tv_usec > 1000000)
  tsum->tv_sec++, tsum->tv_usec -= 1000000;
}
*/

void
tvsub(tdiff, t1, t0)
 struct timeval *tdiff, *t1, *t0;
{

 tdiff->tv_sec = t1->tv_sec - t0->tv_sec;
 tdiff->tv_usec = t1->tv_usec - t0->tv_usec;
 if (tdiff->tv_usec < 0)
  tdiff->tv_sec--, tdiff->tv_usec += 1000000;
}

void
psabort()
{

 abrtflag++;
}

void
pswitch(flag)
 int flag;
{
 sig_t oldintr;
 static struct comvars {
  int connect;
  char name[MAXHOSTNAMELEN];
  struct sockaddr_in mctl;
  struct sockaddr_in hctl;
  FILE *in;
  FILE *out;
  int tpe;
  int curtpe;
  int cpnd;
  int sunqe;
  int runqe;
  int mcse;
  int ntflg;
  char nti[17];
  char nto[17];
  int mapflg;
  char mi[MAXPATHLEN];
  char mo[MAXPATHLEN];
 } proxstruct, tmpstruct;
 struct comvars *ip, *op;

 abrtflag = 0;
 oldintr = signal(SIGINT, psabort);
 if (flag) {
  if (proxy)
   return;
  ip = &tmpstruct;
  op = &proxstruct;
  proxy++;
 } else {
  if (!proxy)
   return;
  ip = &proxstruct;
  op = &tmpstruct;
  proxy = 0;
 }
 ip->connect = connected;
 connected = op->connect;
 if (hostname) {
  (void) strncpy(ip->name, hostname, sizeof(ip->name) - 1);
  ip->name[strlen(ip->name)] = '\0';
 } else
  ip->name[0] = 0;
 hostname = op->name;
 ip->hctl = hisctladdr;
 hisctladdr = op->hctl;
 ip->mctl = myctladdr;
 myctladdr = op->mctl;
 ip->in = cin;
 cin = op->in;
 ip->out = cout;
 cout = op->out;
 ip->tpe = type;
 type = op->tpe;
 ip->curtpe = curtype;
 curtype = op->curtpe;
 ip->cpnd = cpend;
 cpend = op->cpnd;
 ip->sunqe = sunique;
 sunique = op->sunqe;
 ip->runqe = runique;
 runique = op->runqe;
 ip->mcse = mcase;
 mcase = op->mcse;
 ip->ntflg = ntflag;
 ntflag = op->ntflg;
 (void) strncpy(ip->nti, ntin, 16);
 (ip->nti)[strlen(ip->nti)] = '\0';
 (void) strcpy(ntin, op->nti);
 (void) strncpy(ip->nto, ntout, 16);
 (ip->nto)[strlen(ip->nto)] = '\0';
 (void) strcpy(ntout, op->nto);
 ip->mapflg = mapflag;
 mapflag = op->mapflg;
 (void) strncpy(ip->mi, mapin, MAXPATHLEN - 1);
 (ip->mi)[strlen(ip->mi)] = '\0';
 (void) strcpy(mapin, op->mi);
 (void) strncpy(ip->mo, mapout, MAXPATHLEN - 1);
 (ip->mo)[strlen(ip->mo)] = '\0';
 (void) strcpy(mapout, op->mo);
 (void) signal(SIGINT, oldintr);
 if (abrtflag) {
  abrtflag = 0;
  (*oldintr)(SIGINT);
 }
}

void
abortpt()
{

 printf("\n");
 (void) fflush(stdout);
 ptabflg++;
 mflag = 0;
 abrtflag = 0;
 longjmp(ptabort, 1);
}

void
proxtrans(cmd, local, remote)
 char *cmd, *local, *remote;
{
 sig_t oldintr;
 int secndflag = 0, prox_type, nfnd;
 char *cmd2;
 struct fd_set mask;

 if (strcmp(cmd, "RETR"))
  cmd2 = "RETR";
 else
  cmd2 = runique ? "STOU" : "STOR";
 if ((prox_type = type) == 0) {
  if (unix_server && unix_proxy)
   prox_type = TYPE_I;
  else
   prox_type = TYPE_A;
 }
 if (curtype != prox_type)
  changetype(prox_type, 1);
 if (command("PASV") != COMPLETE) {
  printf("proxy server does not support third party transfers.\n");
  return;
 }
 pswitch(0);
 if (!connected) {
  printf("No primary connection\n");
  pswitch(1);
  code = -1;
  return;
 }
 if (curtype != prox_type)
  changetype(prox_type, 1);
 if (command("PORT %s", pasv) != COMPLETE) {
  pswitch(1);
  return;
 }
 if (setjmp(ptabort))
  goto abort;
 oldintr = signal(SIGINT, abortpt);
 if (command("%s %s", cmd, remote) != PRELIM) {
  (void) signal(SIGINT, oldintr);
  pswitch(1);
  return;
 }
 sleep(2);
 pswitch(1);
 secndflag++;
 if (command("%s %s", cmd2, local) != PRELIM)
  goto abort;
 ptflag++;
 (void) getreply(0);
 pswitch(0);
 (void) getreply(0);
 (void) signal(SIGINT, oldintr);
 pswitch(1);
 ptflag = 0;
 printf("local: %s remote: %s\n", local, remote);
 return;
abort:
 (void) signal(SIGINT, SIG_IGN);
 ptflag = 0;
 if (strcmp(cmd, "RETR") && !proxy)
  pswitch(1);
 else if (!strcmp(cmd, "RETR") && proxy)
  pswitch(0);
 if (!cpend && !secndflag) {  /* only here if cmd = "STOR" (proxy=1) */
  if (command("%s %s", cmd2, local) != PRELIM) {
   pswitch(0);
   if (cpend)
    abort_remote((FILE *) NULL);
  }
  pswitch(1);
  if (ptabflg)
   code = -1;
  (void) signal(SIGINT, oldintr);
  return;
 }
 if (cpend)
  abort_remote((FILE *) NULL);
 pswitch(!proxy);
 if (!cpend && !secndflag) {  /* only if cmd = "RETR" (proxy=1) */
  if (command("%s %s", cmd2, local) != PRELIM) {
   pswitch(0);
   if (cpend)
    abort_remote((FILE *) NULL);
   pswitch(1);
   if (ptabflg)
    code = -1;
   (void) signal(SIGINT, oldintr);
   return;
  }
 }
 if (cpend)
  abort_remote((FILE *) NULL);
 pswitch(!proxy);
 if (cpend) {
  FD_ZERO(&mask);
  FD_SET(fileno(cin), &mask);
  if ((nfnd = empty(&mask, 10)) <= 0) {
   if (nfnd < 0) {
    warn("abort");
   }
   if (ptabflg)
    code = -1;
   lostpeer();
  }
  (void) getreply(0);
  (void) getreply(0);
 }
 if (proxy)
  pswitch(0);
 pswitch(1);
 if (ptabflg)
  code = -1;
 (void) signal(SIGINT, oldintr);
}

void
reset(argc, argv)
 int argc;
 char *argv[];
{
 struct fd_set mask;
 int nfnd = 1;

 FD_ZERO(&mask);
 while (nfnd > 0) {
  FD_SET(fileno(cin), &mask);
  if ((nfnd = empty(&mask,0)) < 0) {
   warn("reset");
   code = -1;
   lostpeer();
  }
  else if (nfnd) {
   (void) getreply(0);
  }
 }
}

char *
gunique(local)
 char *local;
{
 static char new[MAXPATHLEN];
 char *cp = strrchr(local, '/');
 int d, count=0;
 char ext = '1';

 if (cp)
  *cp = '\0';
 d = access(cp ? local : ".", 2);
 if (cp)
  *cp = '/';
 if (d < 0) {
  warn("local: %s", local);
  return ((char *) 0);
 }
 (void) strcpy(new, local);
 cp = new + strlen(new);
 *cp++ = '.';
 while (!d) {
  if (++count == 100) {
   printf("runique: can't find unique file name.\n");
   return ((char *) 0);
  }
  *cp++ = ext;
  *cp = '\0';
  if (ext == '9')
   ext = '0';
  else
   ext++;
  if ((d = access(new, 0)) < 0)
   break;
  if (ext != '0')
   cp--;
  else if (*(cp - 2) == '.')
   *(cp - 1) = '1';
  else {
   *(cp - 2) = *(cp - 2) + 1;
   cp--;
  }
 }
 return (new);
}

void
abort_remote(din)
 FILE *din;
{
 char buf[BUFSIZ];
 int nfnd;
 struct fd_set mask;

 /*
  * send IAC in urgent mode instead of DM because 4.3BSD places oob mark
  * after urgent byte rather than before as is protocol now
  */
 sprintf(buf, "%c%c%c", IAC, IP, IAC);
 if (send(fileno(cout), buf, 3, MSG_OOB) != 3)
  warn("abort");
 fprintf(cout,"%cABOR\r\n", DM);
 (void) fflush(cout);
 FD_ZERO(&mask);
 FD_SET(fileno(cin), &mask);
 if (din) { 
  FD_SET(fileno(din), &mask);
 }
 if ((nfnd = empty(&mask, 10)) <= 0) {
  if (nfnd < 0) {
   warn("abort");
  }
  if (ptabflg)
   code = -1;
  lostpeer();
 }
 if (din && FD_ISSET(fileno(din), &mask)) {
  while (read(fileno(din), buf, BUFSIZ) > 0)
   /* LOOP */;
 }
 if (getreply(0) == ERROR && code == 552) {
  /* 552 needed for nic style abort */
  (void) getreply(0);
 }
 (void) getreply(0);
}

SSC Combined Graduate Level Examination 2012 Admit Card

noreply@blogger.com (Varun) — Thu, 28 Jun 2012 18:42:00 +0000

This would be helpful to those candidates who are having trouble finding their Admit Card for SSC Combined Graduate Level Examination 2012.

Please visit your local(state) SSC website and download the list of eligible candidates from there.
You can find your Roll No. Enlisted there and then it could be used to retrieve the Admit Card from the same site.

For Example, In Karntaka roll no. can be found using following steps:

1. Visit http://www.ssckkr.kar.nic.in/
2. On the homepage find the link
1.'"Click here to see the Roll NO. of the list of the provisionally eligible candidates for Combined Graduate Level Exam, 2012".
3. Then try to search your name in the list.
4. Then visit the link 1.Download Duplicate Admission Certificates for Combined Graduate Level EXAMINATION 2012 scheduled to be held on 01.07.2012
5. Enter your roll no. there and download your admit card.

This steps is valid for Karnataka State Candidates, It might be valid for other states too but somebody will have to check.

These are sites for various regions

SSC Northern Region Delhi (SSCNR)

SSC North Western Region Chandigarh

SSC Central Region (SSCCR) Allahabad

SSC Eastern Region Kolkata (SSCER)

SSC North Eastern Region (SSCNER) Guwahati

SSC Madhya Pradesh Region (SSCMPR)

SSC Southern Region (SSCSR) (Forenoon) || (Afternoon)

SSC Western Region (SSCWR) Maharashtra

SSC Kerala, Karnataka Region (SSCKKR)

Whereever you have filled the centre of examination , that will be you region 

libconfig to read configuration files in C/C++

noreply@blogger.com (Varun) — Thu, 23 Feb 2012 13:10:00 +0000

There are so many open-source libraries already available for parsing configuration files in c/c++ , but still we there are some which make their place up than rest of the others. One such library is libconfig . The reason being its simplicity and much lesser memory footprint. Most of the library for configuration files are XML based , but this library is text based and the structure of the configuration files is pretty simple.
e.g. In its simplest form a configuration file can look like :

port = 5000;

It can provide even more simpler configuration file for much complex data group. For example :

books = ( "inventory",
          { title  = "Treasure Island";
            author = "Robert Louis Stevenson";
            price  = 29.99;
            qty    = 5; },
          { title  = "Snow Crash";
            author = "Neal Stephenson";
            price  = 9.99;
            qty    = 8; },

{ } );

Here there is a set of data for the inventory of books with multiple fields for each book.

One of the most important feature of this library is that it supports a fully re-entrant parser which means that different configurations can be parsed in concurrent threads at the same time. Moreover the APIs are available for both C and C++ languages and there are hooks provided in the library to facilitate its use in other programming languages too.

The detailed documentation of this library can be found at Libconfig Manual. It supports multiple platforms such as Windows, Linux , Mac OS X and Solaris (POSIX compliant platforms).

To use it in a C/C++ program one just needs to add a single preprocessor directive

#include <libconfig.h>      /*For C*/

#include <libconfig.h++>    /*For C++*/

For dynamic linking -lconfig/-lconfig++ must be used for C/C++ respectively. Otherwise the libraries can be statically linked using the static linking option during the compilation.

e.g. ( -static $(LIBPTHREAD_INSTALL_DIR)/libpthread.a)

Issues as per the libconfig website:

Libconfig is fully reentrant; the functions in the library do not make use of global variables and do not maintain state between successive calls. Therefore two independent configurations may be safely manipulated concurrently by two distinct threads.
Libconfig is not thread-safe. The library is not aware of the presence of threads and knows nothing about the host system's threading model. Therefore, if an instance of a configuration is to be accessed from multiple threads, it must be suitably protected by synchronization mechanisms like read-write locks or mutexes; the standard rules for safe multithreaded access to shared data must be observed.
Libconfig is not async-safe. Calls should not be made into the library from signal handlers, because some of the C library routines that it uses may not be async-safe.
Libconfig is not guaranteed to be cancel-safe. Since it is not aware of the host system's threading model, the library does not contain any thread cancellation points. In most cases this will not be an issue for multithreaded programs. However, be aware that some of the routines in the library (namely those that read/write configurations from/to files or streams) perform I/O using C library routines which may potentially block; whether or not these C library routines are cancel-safe depends on the host system.

We will provide a simple example of how to read from a configuration file using libconfig:

 
/*config.c*/
/*
To compile : gcc -o config config.c -lconfig
To run     : ./config
*/
#include 
#include 

int main()
{
    config_t cfg;               /*Returns all parameters in this structure */
    config_setting_t *setting;
    const char *str1, *str2;
    int tmp;

    char *config_file_name = "config.txt";

    /*Initialization */
    config_init(&cfg);

    /* Read the file. If there is an error, report it and exit. */
    if (!config_read_file(&cfg, config_file_name))
    {
        printf("\n%s:%d - %s", config_error_file(&cfg), config_error_line(&cfg), config_error_text(&cfg));
        config_destroy(&cfg);
        return -1;
    }

    /* Get the configuration file name. */
    if (config_lookup_string(&cfg, "filename", &str1))
        printf("\nFile Type: %s", str1);
    else
        printf("\nNo 'filename' setting in configuration file.");

    /*Read the parameter group*/
    setting = config_lookup(&cfg, "params");
    if (setting != NULL)
    {
        /*Read the string*/
        if (config_setting_lookup_string(setting, "param1", &str2))
        {
            printf("\nParam1: %s", str2);
        }
        else
            printf("\nNo 'param1' setting in configuration file.");

        /*Read the integer*/
        if (config_setting_lookup_int(setting, "param2", &tmp))
        {
            printf("\nParam2: %d", tmp);
        }
        else
            printf("\nNo 'param2' setting in configuration file.");

        printf("\n");
    }

    config_destroy(&cfg);
}

And corresponding configuration file :

 
//config.txt
// Basic Information:
filename = "Sample Configuration File";

// Parameters
params = 
{
param1 = "Hello";

param2 = 1234;
};

Articles needed !

noreply@blogger.com (Anonymous) — Tue, 14 Feb 2012 06:10:00 +0000

Due to lack of time, I am not being able to write more posts. If anyone feels that they have some good topic to write about, please write to me and after moderation i can publish it on the blog.

Serialization using Google protobuf

noreply@blogger.com (Anonymous) — Sun, 28 Nov 2010 10:35:00 +0000

Protocol buffers (that's what protobuf means :)) are a means to serialize structured data. Now you may be wondering what this 'serialize' means.

To be brief : Serialization is a process of packing the data structures or objects into sequence of bits so that they can be stored in a file or a buffer and transmitted across the network and then can be retrieved on the same or other system environment. Examples include XML, JSON, ASN.1, YAML, ProtoBuf etc.

Advantages :
1. Persistent object creation
2. RPC enabling
3. Are simple
4. Save space on disk
5. Very fast
6. Platform and language independent

ProtoBuf is available freely from Google (http://code.google.com/p/protobuf/). Procedure of installation and compilation is present there.

Everything that needs to be serialized is put in a protocol buffer message (a .proto file). This file tells the compiler how the data is to be serialized.

For each field there are setter and getter functions fieldname() is a getter and set_fieldname() is a setter. Remember to use these functions as the exact way it is told here.
The tutorials for the different languages can be found here

I present a small simple example to use the protobuf library and there is much more than that one can do with the protobuf :)

To make and run the example (on linux) follow the steps :
1. Download the tar.gz package from here
2. Login as root
3. Untar it in your home directory (say user1)
4. Go inside the protobuf directory and run ./configure
5. Add the path /usr/local/lib to the environment variable LD_LIBRARY_PATH
6. Then run :
make
make install
7. You are now ready to use the library.
8. To use protobuf you will need following files (I am explaining for c++ only):
.cc file
.proto file
Makefile
Rest of the files are generated on the fly.

Here is an example of a Vehicle parts which contains three fields , two mandatory and one optional.
-Part ID (mandatory)
-Part Name (mandatory)
-Vendor (optional)

We write this in .proto file

//partbook.proto
package tutorial;

message Part {
  required string name = 1;
  required int32 partid = 2;        // Unique ID number for this part
  optional string vendor = 3;

}

message PartDetails {
  repeated Part part = 1;
}

Then we write a c++ program to use the library and .proto to add serialized data to the data file.

/*add_part.cc*/
#include <iostream>
#include <fstream>
#include <string>
#include "partbook.pb.h"
using namespace std;

/* This function fills in a Part message based on user input.*/
void PromptForPart(tutorial::Part* part) {
  cout << "Enter part ID number: ";
  int partid;
  cin >> partid;
  part->set_partid(partid);
  cin.ignore(256, '\n');

  cout << "Enter part name: ";
  getline(cin, *part->mutable_name());

  cout << "Enter vendor name (blank for none): ";
  string vendor;
  getline(cin, vendor);
  if (!vendor.empty()) {
    part->set_vendor(vendor);
  }

}

/* Main function:  Reads the entire part list from a file,
 * adds one part based on user input, then writes it back out to the same
 *   file.
 */
int main(int argc, char* argv[]) {
  /* Verify that the version of the library that we linked against is
   * compatible with the version of the headers we compiled against.
   */
  GOOGLE_PROTOBUF_VERIFY_VERSION;

  if (argc != 2) {
    cerr << "Usage:  " << argv[0] << " PART_BOOK_FILE" << endl;
    return -1;
  }

  tutorial::PartDetails part_book;

  {
    // Read the existing part book.
    fstream input(argv[1], ios::in | ios::binary);
    if (!input) {
      cout << argv[1] << ": File not found.  Creating a new file." << endl;
    } else if (!part_book.ParseFromIstream(&input)) {
      cerr << "Failed to parse part book." << endl;
      return -1;
    }
  }

  // Add a new part.
  PromptForPart(part_book.add_part());

  {
    // Write the new part book back to disk.
    fstream output(argv[1], ios::out | ios::trunc | ios::binary);
    if (!part_book.SerializeToOstream(&output)) {
      cerr << "Failed to write part book." << endl;
      return -1;
    }
  }

  // Optional:  Delete all global objects allocated by libprotobuf.
  google::protobuf::ShutdownProtobufLibrary();

  return 0;
}

Then we write a c++ program to use the library and .proto to serialize the data.

/*list_parts.cc*/
#include <iostream>
#include <fstream>
#include <string>
#include "partbook.pb.h"
using namespace std;

// Iterates though all parts in the PartDetails and prints info about them.
void ListParts(const tutorial::PartDetails& part_book) {
  for (int i = 0; i < part_book.part_size(); i++) {
    const tutorial::Part& part = part_book.part(i);

    cout << "Part ID: " << part.partid() << endl;
    cout << "  Name: " << part.name() << endl;
    if (part.has_vendor()) {
      cout << "  Vendor: " << part.vendor() << endl;
    }

  }
}

// Main function:  Reads the entire part book from a file and prints all
//   the information inside.
int main(int argc, char* argv[]) {
  // Verify that the version of the library that we linked against is
  // compatible with the version of the headers we compiled against.
  GOOGLE_PROTOBUF_VERIFY_VERSION;

  if (argc != 2) {
    cerr << "Usage:  " << argv[0] << " PART_BOOK_FILE" << endl;
    return -1;
  }

  tutorial::PartDetails part_book;

  {
    // Read the existing data file.
    fstream input(argv[1], ios::in | ios::binary);
    if (!part_book.ParseFromIstream(&input)) {
      cerr << "Failed to parse part book." << endl;
      return -1;
    }
  }

  ListParts(part_book);

  // Optional:  Delete all global objects allocated by libprotobuf.
  google::protobuf::ShutdownProtobufLibrary();

  return 0;
}

#Makefile
#This creates executables for python cpp and java , to create only one language use #'make cpp' or 'make python' or 'make java'

.PHONY: all cpp java python clean

all: cpp java python

cpp:    add_part_cpp    list_parts_cpp
java:   add_part_java   list_parts_java
python: add_part_python list_parts_python

clean:
 rm -f add_part_cpp list_parts_cpp add_part_java list_parts_java add_part_python list_parts_python
 rm -f javac_middleman AddPart*.class ListParts*.class com/example/tutorial/*.class
 rm -f protoc_middleman partbook.pb.cc partbook.pb.h partbook.pb2.py com/example/tutorial/PartBookProtos.java
 rm -f *.pyc
 rmdir com/example/tutorial 2>/dev/null || true
 rmdir com/example 2>/dev/null || true
 rmdir com 2>/dev/null || true

protoc_middleman: partbook.proto
 protoc --cpp_out=. --java_out=. --python_out=. partbook.proto
 @touch protoc_middleman

add_part_cpp: add_part.cc protoc_middleman
 pkg-config --cflags protobuf  # fails if protobuf is not installed
 c++ add_part.cc partbook.pb.cc -o add_part_cpp `pkg-config --cflags --libs protobuf`

list_parts_cpp: list_parts.cc protoc_middleman
 pkg-config --cflags protobuf  # fails if protobuf is not installed
 c++ list_parts.cc partbook.pb.cc -o list_parts_cpp `pkg-config --cflags --libs protobuf`

javac_middleman: AddPart.java ListParts.java protoc_middleman
 javac AddPart.java ListParts.java com/example/tutorial/PartBookProtos.java
 @touch javac_middleman

add_part_java: javac_middleman
 @echo "Writing shortcut script add_part_java..."
 @echo '#! /bin/sh' > add_part_java
 @echo 'java -classpath .:$$CLASSPATH AddPart "$$@"' >> add_part_java
 @chmod +x add_part_java

list_parts_java: javac_middleman
 @echo "Writing shortcut script list_parts_java..."
 @echo '#! /bin/sh' > list_parts_java
 @echo 'java -classpath .:$$CLASSPATH ListParts "$$@"' >> list_parts_java
 @chmod +x list_parts_java

add_part_python: add_part.py protoc_middleman
 @echo "Writing shortcut script add_part_python..."
 @echo '#! /bin/sh' > add_part_python
 @echo './add_part.py "$$@"' >> add_part_python
 @chmod +x add_part_python

list_parts_python: list_parts.py protoc_middleman
 @echo "Writing shortcut script list_parts_python..."
 @echo '#! /bin/sh' > list_parts_python
 @echo './list_parts.py "$$@"' >> list_parts_python
 @chmod +x list_parts_python

Save all these files under <proto-installation-path>/examples/ and run make

To run the example
./add_part_cpp <data-filename>
./list_parts_cpp <data-filename>

Xdotool : Fake Keyboard/Mouse Input Tool

noreply@blogger.com (Anonymous) — Wed, 24 Nov 2010 08:12:00 +0000

xdotool is a fake keyboard/mouse input tool for linux which is freely available on the internet.
So whatever you keep typing on the keyboard or kept clicking using the mouse , you can do it now with the help of a script.

One can get the tool downloaded from their website for all versions of linux:
http://www.semicomplete.com/projects/xdotool
There are too many uses you can use xdotool for. For example : If you need to open multiple tabs in a terminal you can use -
'xdotool key ctrl+shift+t' for as many times as the no. of tabs you need and to close down those tabs use 'xdotool ctrl+shift+w'

All this can be written on a script and when the script runs you can see all of that happening without even touching the keyboard or mouse.

The whole documentation is present here

Here are some examples :

Example: focus the firefox url bar

WID=`xdotool search "Mozilla Firefox" | head -1`
xdotool windowactivate --sync $WID
xdotool key --clearmodifiers ctrl+l


# As of version 2.20100623, you can do this simpler version of above:
xdotool search "Mozilla Firefox" windowactivate --sync key --clearmodifiers ctrl+l

Example: Resize all visible gnome-terminal windows
WIDS=`xdotool search --onlyvisible --name "gnome-terminal"`
for id in $WIDS; do
  xdotool windowsize $id 500 500
done

# As of version 2.20100623, you can do this simpler version of above:
xdotool search --onlyvisible --classname "gnome-terminal" windowsize %@ 500
500

Create your own packet sniffer in C

noreply@blogger.com (Anonymous) — Sat, 23 Oct 2010 10:09:00 +0000

A simple implementation of a packet sniffer in C on linux platform using the libpcap library. This packet sniffer currently sniffs IP , TCP , ICMP and UDP packets. It can be modified to any protocol as needed just by introducing the header information in it.

Certain filters can be used too like port number and specific host etc.
e.g.

Expression	Description
ip	Capture all IP packets.
tcp	Capture only TCP packets.
tcp port 80	Capture only TCP packets with a port equal to 80.
ip host 10.1.2.3	Capture all IP packets to or from host 10.1.2.3.

It is a little modified version of sniffer from tcpdump website.

Note : To run this code you require root permissions.

Here's the code:

/*sniffer.c*/
//To compile : gcc -o sniffer sniffer.c -lpcap
//To run : ./sniffer [interface-name]

#include <pcap.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

/* default snap length (maximum bytes per packet to capture) */
#define SNAP_LEN 1518

/* ethernet headers are always exactly 14 bytes [1] */
#define SIZE_ETHERNET 14

/* Ethernet addresses are 6 bytes */
#define ETHER_ADDR_LEN 6

/* Ethernet header */
struct sniff_ethernet {
        u_char  ether_dhost[ETHER_ADDR_LEN];    /* destination host address */
        u_char  ether_shost[ETHER_ADDR_LEN];    /* source host address */
        u_short ether_type;                     /* IP? ARP? RARP? etc */
};

/* IP header */
struct sniff_ip {
        u_char  ip_vhl;                 /* version << 4 | header length >> 2 */
        u_char  ip_tos;                 /* type of service */
        u_short ip_len;                 /* total length */
        u_short ip_id;                  /* identification */
        u_short ip_off;                 /* fragment offset field */
        #define IP_RF 0x8000            /* reserved fragment flag */
        #define IP_DF 0x4000            /* dont fragment flag */
        #define IP_MF 0x2000            /* more fragments flag */
        #define IP_OFFMASK 0x1fff       /* mask for fragmenting bits */
        u_char  ip_ttl;                 /* time to live */
        u_char  ip_p;                   /* protocol */
        u_short ip_sum;                 /* checksum */
        struct  in_addr ip_src,ip_dst;  /* source and dest address */
};
#define IP_HL(ip)               (((ip)->ip_vhl) & 0x0f)
#define IP_V(ip)                (((ip)->ip_vhl) >> 4)

/* TCP header */
typedef u_int tcp_seq;

struct sniff_tcp {
        u_short th_sport;               /* source port */
        u_short th_dport;               /* destination port */
        tcp_seq th_seq;                 /* sequence number */
        tcp_seq th_ack;                 /* acknowledgement number */
        u_char  th_offx2;               /* data offset, rsvd */
#define TH_OFF(th)      (((th)->th_offx2 & 0xf0) >> 4)
        u_char  th_flags;
        #define TH_FIN  0x01
        #define TH_SYN  0x02
        #define TH_RST  0x04
        #define TH_PUSH 0x08
        #define TH_ACK  0x10
        #define TH_URG  0x20
        #define TH_ECE  0x40
        #define TH_CWR  0x80
        #define TH_FLAGS        (TH_FIN|TH_SYN|TH_RST|TH_ACK|TH_URG|TH_ECE|TH_CWR)
        u_short th_win;                 /* window */
        u_short th_sum;                 /* checksum */
        u_short th_urp;                 /* urgent pointer */
};

void
got_packet(u_char *args, const struct pcap_pkthdr *header, const u_char *packet);

void
print_payload(const u_char *payload, int len);

void
print_hex_ascii_line(const u_char *payload, int len, int offset);



/*
 * print data in rows of 16 bytes: offset   hex   ascii
 *
 * 00000   47 45 54 20 2f 20 48 54  54 50 2f 31 2e 31 0d 0a   GET / HTTP/1.1..
 */
void
print_hex_ascii_line(const u_char *payload, int len, int offset)
{

 int i;
 int gap;
 const u_char *ch;

 /* offset */
 printf("%05d   ", offset);
 
 /* hex */
 ch = payload;
 for(i = 0; i < len; i++) {
  printf("%02x ", *ch);
  ch++;
  /* print extra space after 8th byte for visual aid */
  if (i == 7)
   printf(" ");
 }
 /* print space to handle line less than 8 bytes */
 if (len < 8)
  printf(" ");
 
 /* fill hex gap with spaces if not full line */
 if (len < 16) {
  gap = 16 - len;
  for (i = 0; i < gap; i++) {
   printf("   ");
  }
 }
 printf("   ");
 
 /* ascii (if printable) */
 ch = payload;
 for(i = 0; i < len; i++) {
  if (isprint(*ch))
   printf("%c", *ch);
  else
   printf(".");
  ch++;
 }

 printf("\n");

return;
}

/*
 * print packet payload data (avoid printing binary data)
 */
void
print_payload(const u_char *payload, int len)
{

 int len_rem = len;
 int line_width = 16;   /* number of bytes per line */
 int line_len;
 int offset = 0;     /* zero-based offset counter */
 const u_char *ch = payload;

 if (len <= 0)
  return;

 /* data fits on one line */
 if (len <= line_width) {
  print_hex_ascii_line(ch, len, offset);
  return;
 }

 /* data spans multiple lines */
 for ( ;; ) {
  /* compute current line length */
  line_len = line_width % len_rem;
  /* print line */
  print_hex_ascii_line(ch, line_len, offset);
  /* compute total remaining */
  len_rem = len_rem - line_len;
  /* shift pointer to remaining bytes to print */
  ch = ch + line_len;
  /* add offset */
  offset = offset + line_width;
  /* check if we have line width chars or less */
  if (len_rem <= line_width) {
   /* print last line and get out */
   print_hex_ascii_line(ch, len_rem, offset);
   break;
  }
 }

return;
}

/*
 * dissect/print packet
 */
void
got_packet(u_char *args, const struct pcap_pkthdr *header, const u_char *packet)
{

 static int count = 1;                   /* packet counter */
 
 /* declare pointers to packet headers */
 const struct sniff_ethernet *ethernet;  /* The ethernet header [1] */
 const struct sniff_ip *ip;              /* The IP header */
 const struct sniff_tcp *tcp;            /* The TCP header */
 const char *payload;                    /* Packet payload */

 int size_ip;
 int size_tcp;
 int size_payload;
 
 printf("\nPacket number %d:\n", count);
 count++;
 
 /* define ethernet header */
 ethernet = (struct sniff_ethernet*)(packet);
 
 /* define/compute ip header offset */
 ip = (struct sniff_ip*)(packet + SIZE_ETHERNET);
 size_ip = IP_HL(ip)*4;
 if (size_ip < 20) {
  printf("   * Invalid IP header length: %u bytes\n", size_ip);
  return;
 }

 /* print source and destination IP addresses */
 printf("       From: %s\n", inet_ntoa(ip->ip_src));
 printf("         To: %s\n", inet_ntoa(ip->ip_dst));
 
 /* determine protocol */ 
 switch(ip->ip_p) {
  case IPPROTO_TCP:
   printf("   Protocol: TCP\n");
   break;
  case IPPROTO_UDP:
   printf("   Protocol: UDP\n");
   return;
  case IPPROTO_ICMP:
   printf("   Protocol: ICMP\n");
   return;
  case IPPROTO_IP:
   printf("   Protocol: IP\n");
   return;
  default:
   printf("   Protocol: unknown\n");
   return;
 }
 
 /*
  *  OK, this packet is TCP.
  */
 
 /* define/compute tcp header offset */
 tcp = (struct sniff_tcp*)(packet + SIZE_ETHERNET + size_ip);
 size_tcp = TH_OFF(tcp)*4;
 if (size_tcp < 20) {
  printf("   * Invalid TCP header length: %u bytes\n", size_tcp);
  return;
 }
 
 printf("   Src port: %d\n", ntohs(tcp->th_sport));
 printf("   Dst port: %d\n", ntohs(tcp->th_dport));
 
 /* define/compute tcp payload (segment) offset */
 payload = (u_char *)(packet + SIZE_ETHERNET + size_ip + size_tcp);
 
 /* compute tcp payload (segment) size */
 size_payload = ntohs(ip->ip_len) - (size_ip + size_tcp);
 
 /*
  * Print payload data; it might be binary, so don't just
  * treat it as a string.
  */
 if (size_payload > 0) {
  printf("   Payload (%d bytes):\n", size_payload);
  print_payload(payload, size_payload);
 }

return;
}

int main(int argc, char **argv)
{

 char *dev = NULL;   /* capture device name */
 char errbuf[PCAP_ERRBUF_SIZE];  /* error buffer */
 pcap_t *handle;    /* packet capture handle */

 char filter_exp[] = "ip";  /* filter expression */
 struct bpf_program fp;   /* compiled filter program (expression) */
 bpf_u_int32 mask;   /* subnet mask */
 bpf_u_int32 net;   /* ip */
 int num_packets ;   /* number of packets to capture */

 /* check for capture device name on command-line */
 if (argc == 2) {
  dev = argv[1];
 }
 else if (argc > 3) {
  fprintf(stderr, "error: unrecognized command-line options\n\n");
 printf("Usage: %s [interface]\n", argv[0]);
 printf("\n");
 printf("Options:\n");
 printf("    interface    Listen on <interface> for packets.\n");
 printf("\n");
  exit(EXIT_FAILURE);
 }
 else {
  /* find a capture device if not specified on command-line */
  dev = pcap_lookupdev(errbuf);
  if (dev == NULL) {
   fprintf(stderr, "Couldn't find default device: %s\n",
       errbuf);
   exit(EXIT_FAILURE);
  }
 }
 printf("\nEnter no. of packets you want to capture: ");
        scanf("%d",&num_packets);
        printf("\nWhich kind of packets you want to capture : ");
        scanf("%s",filter_exp);
 /* get network number and mask associated with capture device */
 if (pcap_lookupnet(dev, &net, &mask, errbuf) == -1) {
  fprintf(stderr, "Couldn't get netmask for device %s: %s\n",
      dev, errbuf);
  net = 0;
  mask = 0;
 }

 /* print capture info */
 printf("Device: %s\n", dev);
 printf("Number of packets: %d\n", num_packets);
 printf("Filter expression: %s\n", filter_exp);

 /* open capture device */
 handle = pcap_open_live(dev, SNAP_LEN, 1, 1000, errbuf);
 if (handle == NULL) {
  fprintf(stderr, "Couldn't open device %s: %s\n", dev, errbuf);
  exit(EXIT_FAILURE);
 }

 /* make sure we're capturing on an Ethernet device [2] */
 if (pcap_datalink(handle) != DLT_EN10MB) {
  fprintf(stderr, "%s is not an Ethernet\n", dev);
  exit(EXIT_FAILURE);
 }

 /* compile the filter expression */
 if (pcap_compile(handle, &fp, filter_exp, 0, net) == -1) {
  fprintf(stderr, "Couldn't parse filter %s: %s\n",
      filter_exp, pcap_geterr(handle));
  exit(EXIT_FAILURE);
 }

 /* apply the compiled filter */
 if (pcap_setfilter(handle, &fp) == -1) {
  fprintf(stderr, "Couldn't install filter %s: %s\n",
      filter_exp, pcap_geterr(handle));
  exit(EXIT_FAILURE);
 }

 /* now we can set our callback function */
 pcap_loop(handle, num_packets, got_packet, NULL);

 /* cleanup */
 pcap_freecode(&fp);
 pcap_close(handle);

 printf("\nCapture complete.\n");

return 0;
}

Vector Write in C

noreply@blogger.com (Anonymous) — Tue, 19 Oct 2010 06:47:00 +0000

Simple implementation of vector writes in unix. This example uses writev system call to write into a file. The writev call enables you to write multiple discontiguous regions of memory to a file descriptor in a single operation.This is called a vector write.

We use iovec structure for the purpose of filling up the vector.Each
element specifies one region of memory to write; the fields iov_base and iov_len
specify the address of the start of the region and the length of the region, respectively.

This program takes command line arguments to fill up the vector.
Anything after the second argument will go to the file.

//vector-write.c
//To compile : gcc -o vwrite vector-write.c
//To run : ./vwrite file-name argument1 argument2 ..

#include <fcntl.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>
int main (int argc, char* argv[])
{
  int fd;
  struct iovec* vec;
  struct iovec* vec_next;
  int i;
  
  if(argc < 2 )
  {
    printf("\nUsage : %s <filename> [args...]\n",argv[0]);
    exit(1);
  }
  
  char newline = '\n';
  
  char* filename = argv[1];
  
  argc -= 2;
  argv += 2;
  
  /* Allocate an array of iovec elements. We.ll need two for each
   * element of the argument list, one for the text itself, and one for
   * a newline. */
  
  vec = (struct iovec*) malloc (2 * argc * sizeof (struct iovec));
  
  /* Fill the iovec entries. */
  
  vec_next = vec;
  for (i = 0; i < argc; ++i) {
    
    /* The first element is the text of the argument itself. */
    
    vec_next->iov_base = argv[i];
    vec_next->iov_len = strlen (argv[i]);
    ++vec_next;
    
    /* The second element is a single newline character. It.s okay for
     * multiple elements of the struct iovec array to point to the
     * same region of memory. */
    
    vec_next->iov_base = &newline;
    vec_next->iov_len = 1;
    ++vec_next;
  }
  
  /* Write the to a file. */
  
  fd = open (filename, O_WRONLY | O_CREAT);
  writev (fd, vec, 2 * argc);
  close (fd);
  free (vec);
  return 0;
}

IPC Memory Map implementation in C

noreply@blogger.com (Anonymous) — Wed, 13 Oct 2010 05:13:00 +0000

Using memory mapped file two processes can both open the same file and both read and write from it, thus sharing the information.It is easier to map a section of the file to memory, and get a pointer to it rather than doing fseek .

A memory mapped file is very easy to use as we can perform simple arithmetic operations to get and set data from a file.

Here is a simple example of creating and using memory mapped files.It takes a file and offset as input and tells what data is present at that offset.

//memorymap.c
//To compile : gcc -o mmap memorymap.c
//To run : ./mmap file-name offset

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>

#include <sys/stat.h>
#include <errno.h>
int main(int argc, char *argv[])
{
    int fd, offset;
    char *data;
    struct stat sbuf;
    if (argc != 3)
    {
        fprintf(stderr, "usage: %s <file-name> offset\n",argv[0]);
        exit(1);
    }
    if ((fd = open(argv[1], O_RDONLY)) == -1)
    {
        perror("open");
        exit(1);
    }
    /*argv[1] is the file name to be examined*/
    if (stat(argv[1], &sbuf) == -1)
    {
        perror("stat");
        exit(1);
    }
    offset = atoi(argv[2]);
    if (offset < 0 || offset > sbuf.st_size-1)
    {
        printf("%s: offset must be in the range 0-%d\n",argv[0],sbuf.st_size-1);
        exit(1);
    }
    data = mmap((caddr_t)0, sbuf.st_size, PROT_READ, MAP_SHARED, fd, 0);
    {
        if (data == (caddr_t)(-1))
        {
            perror("mmap");
            exit(1);
        }
        printf("Byte at offset %d is '%c'\n", offset, data[offset]);
        return 0;
    }
}

Simplest Codings

Harnessing Sentiment Analysis with Java: A Step-by-Step Guide using NLP

Prerequisites

Step 1: Create a New Project

Step 2: Add Dependencies

Step 3: Create Project Structure

Step 4: Configure Properties

Step 5: Write Code

Step 6: Run the Code

Cracking the Piggy Bank Puzzle: A Java Adventure in Dynamic Programming

Longest common subsequence in Java

Understanding the Problem

Character Grid

Tracing Paths

Visualize the LCS

Algorithm

Explanation for code

Steps

Take away points

Knapsack Problem implementation in Java

Visualizing the Items

The Knapsack

Decision-Making

Optimal Solution

Key Points

Dynamic Programming Approach

Explanation of code

Steps

Take away points

Dijkstra algorithm implementation in Java

Purpose

Key Concepts

Algorithm Steps

Explanation of code

Graph Representation

Dijkstra's Algorithm Implementation

Random Graph Generation

Ternary Search Tree Implementation in C++

String matching using KMP algorithm : C++ Implementation

Component Object Model(COM) - Implementation in C++ -- Usage in C++, C#

Steps involved to create COM interface:

Steps to generate COM DLL:

Steps to create sample C++ code to test COM DLL:

Steps to create .NET wrapper from COM DLL:

Steps to create C# application to test COM DLL :

Facade design pattern implementation in C++

Facade Design Pattern Implementation(C++)

Create a SOAP web service client in C++

What is SOAP?

SOAP Web Service client implementation(c++)

Builder Design Pattern Implementation in C++

Builder Design Pattern Implementation(C++)

Decorator Design Pattern Implementation in C++

Decorator Design Pattern Implementation (C++)

Factory Method Design Pattern implementation in C++

Factory Method Design Pattern implementation (C++)

Graph Implementation in C

Uses of graphs

Kind of graphs

Undirected Graphs

Directed Graphs

Vertex labeled Graphs.

Cyclic Graphs.

Edge labeled Graphs.

Weighted Graphs.

Directed Acyclic Graphs.

Disconnected Graphs

Mixed graph

Multigraph

Quiver

Representation of graphs:

Adjacency Matrix :

Adjacency List :

Trie implementation in C

Structure of Trie(Specific to this implementation):

Abstract Binary Search Tree Implementation in C

FTP implementation in C

SSC Combined Graduate Level Examination 2012 Admit Card

SSC Southern Region (SSCSR) (Forenoon) || (Afternoon)

libconfig to read configuration files in C/C++