Sunday, October 26, 2014

Facade design pattern implementation in C++



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
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;
}


Saturday, October 18, 2014

Create a SOAP web service client in C++

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:

  1. gSOAP library (2.8.18) http://sourceforge.net/projects/gsoap2/files/
  2. Xerces library (3.1.1) http://xerces.apache.org/mirrors.cgi#binary
Setup for Visual Studio 2005:
  1. Unzip gSOAP library at any location (Lets say C:\tools , so the location will be C:\gsoap-2.8)
  2. Download only the binary distribution of xerces xerces-c-3.1.1-x86-windows-vc-8.0.zip
  3. Unzip the zip file at C:\  so that location becomes C:\xerces-c-3.1.1-x86-windows-vc-8.0
  4. Create an empty Win32 Console Application project.
  5. 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"

  6. Add these paths to Additional Library Directories :
    "C:\xerces-c-3.1.1-x86-windows-vc-8.0\lib"

  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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;
    };
    
    


  13. Now the project is ready to compile. Use F7 to compile the solution.
  14. 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
  15. 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

Wednesday, April 2, 2014

Builder Design Pattern Implementation in C++


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
Builder Design Pattern
There are 4 major components:

  1. Director: It constructs an object using the Builder interface.
  2. Builder : It specifies an abstract interface to build parts of a product.
  3. Concrete Classes : Implements builder interface.
  4. 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 Design Pattern
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;
}

Sunday, December 29, 2013

Decorator Design Pattern Implementation in C++

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++

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 !!";
}

Sunday, September 29, 2013

Graph Implementation in C

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 :
  1. Directed, weighted edges
  2. Directed, unweighted edges
  3. Undirected, weighted edges
  4. 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:
  1. Order of vertices doesn't matter
  2. 1-2 is same as 2-1

  • Directed Graphs

Directed Graph
     Characteristics:
  1. Order of vertices does matter
  2. 1-2 is not same as 2-1

  • Vertex labeled Graphs.

Vertex Labeled Graph
     Characteristics:
  1. Each vertex contains additional information. e.g {2,orange}, {4,green}

  • Cyclic Graphs.

Cyclic Graph
     Characteristics:
  1. Graph contains at least one cycle.

  • Edge labeled Graphs.

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

  • Weighted Graphs.

Weighted Graph
     Characteristics:
  1. Each edge has some weight associated with it.

  • Directed Acyclic Graphs.

Direct Acyclic Graph(DAG)
     Characteristics:
  1. Graph has no cycles.

  • Disconnected Graphs

Disconnected Graph
     Characteristics:
  1. Vertices are disconnected 

  • Mixed graph

Mixed Graph
     Characteristics:
  1. Some edges may be directed and some may be undirected 

  • Multigraph

Multigraph
     Characteristics:
  1. Multiple edges (and sometimes loops) are allowed

  • Quiver

          

     Characteristics:
  1. 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[N2]). 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

Thursday, November 8, 2012

Trie implementation in C

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:
  1. Key - Part of the string to be serached,inserted or deleted.
  2. Value -  The value associated with a string (e.g In a dictionary it could be the meaning of the word which we are searching)
  3. Neighbour node address - It consists of the address of the neighbouring node at the same level.
  4. Previous neighbour address - It consists of the address of the previous node at the same level.
  5. Children node address - It consists of the address of the child nodes of the current node.
  6. 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