Find the first substring in C++

Years ago, I interviewed for a summer internship, and I got a coding question along the lines of: "Implement a function that finds a substring within a string. If that substring is found, return the index of the found substring."

I fumbled through the question. Eventually I got a working solution, but it was a clumsy process getting there. Why was such a simple question so difficult to implement on the spot?

In hindsight, I think this is a good interview question for a few reasons. The problem is deceivingly simple; just about anybody is capable of doing this correctly, but it's difficult to do it well and efficiently, especially on the spot. Because the problem is so simple, the focus of evaluation lies in your style and thought process. Do you clutter your code with unnecessary variables? Is your code verbose or terse? How many functions do you compose, and why? Is your style sloppy or bug-prone? I didn't get that particular internship, because my code was definitely sloppy and bug-prone.

I think there's one more aspect of this question that causes applicants to freeze: strings. In C++ and Java, people tend to use the std::string/String classes, which have lots of utility functions built in. In day-to-day programming, you would rarely iterate over a string manually, and you might also avoid using pointers of type char*.

In this particular example, I think it's actually easier to use pointers than integer indices; this way you have fewer local variables to keep track of. To some extent, having fewer variables means fewer opportunities to introduce a bug.

In my version, I like splitting it up into two functions. The primary function simply iterates over the outer string, and searches each substring for the sought string. Heres' the code:

bool matched(char* sought, char* sent){
    //utility function
    while (*sought!='\0'){
        if (*sent=='\0') //sought is longer than sent
            return false;
        if (*sent!=*sought) //The characters don't match
            return false;
        sent++; sought++; //Check next character
    }
    return true;
}

int substring(char* sought, char* sentence){
    //primary function
    char* iter=sentence; //iterate over string
    while (*iter!='\0'){        
        if (matched(sought, iter)){
                return iter-sentence;
        }        
        iter++;
    }
    return -1;
}

As you can see, the pointers can reduce clutter in the code, because they already are indices in an array of characters.

Matplotlib Animations Using Data queried from a SQL Table

In prior examples, I've provided a couple of snippets for writing videos using Matplotlib. In this example, instead of plotting data stored in files, I'm using data stored in a SQL table. In this particular instance, I'm using MySQL for convenience.

These days, your choice of database is about as controversial as discussing politics and religion; it's the third rail of...data? You can choose the best database, and table structure to suit your particular needs. MySQL serves just fine as an example. In any case, SQL syntax is mostly standard across databases. and the Python database interfaces are also quite standard; they mainly consist of instantiating a connection and cursor, and executing SQL commands.

Ok, so now to the code. In prior examples, we needed to know the number of frames to plot, when we initiate the matplotlib animation. In my case, I've structured the data so a given row in the table corresponds to one data frame, and to one plotted frame in the Matplotlib animation. So, I have a couple of utility functions, one to get the number of frames we'll plot, and the other to query a particular table entry, given the desired row [frame] and column.

 import sys  
 import os  
 import time  
 import MySQLdb as mdb  
 from TableDef import columns #Custom definition of the table structure  
   
 def count(table, serverIP, dbUser, password, database):  
   try:  
     con = mdb.connect(serverIP, dbUser, password,database)        
     with con:  
       cur = con.cursor()  
       com="SET sql_mode=\'ANSI_QUOTES\'"  
       cur.execute(com)  
       row_exists=0  
       com="SELECT COUNT(*) FROM \"%s\""%table  
       cur.execute(com)  
       rows=cur.fetchall()  
       count=rows[0][0]        
         
   except mdb.Error, e:   
       print "Error %d: %s" % (e.args[0],e.args[1])  
       sys.exit(1)    
   finally:      
       if con:    
         con.close()   
   return count  
   
 def getdataframe(table,column,frame,serverIP, user, password, database):      
     
   if column not in columns:  
     return  
   if frame>count(table):  
     return  
   try:  
     con = mdb.connect(serverIP, dbUser, password,database);        
     with con:  
       cur = con.cursor()  
       com="SET sql_mode=\'ANSI_QUOTES\'"  
       cur.execute(com)  
       row_exists=0  
       com="SELECT %s "%column  
       com=com+"FROM \"%s\" "%table  
       com=com+"WHERE Frame=%s"%str(frame)        
       cur.execute(com)  
       rows=cur.fetchall()  
       data=rows[0][0]        
         
   except mdb.Error, e:   
       print "Error %d: %s" % (e.args[0],e.args[1])  
       sys.exit(1)    
   finally:      
       if con:    
         con.close()   
           
   return data    

Note that I have a custom Python class called TableDef, where I've declared various parameters relevant to the table and database. This part depends on your particular application, how you structure your data, etc. I could have wrapped these table functions in a class if I wanted a more OO feel.

Now, when I go my Matplotlib animation, I can use these utility functions to get the total number of frames, and to query individual data frames.

 import sys  
 import os  
 import json  
 import numpy as np  
 import matplotlib  
 import matplotlib.pyplot as plt  
 import matplotlib.animation as animation  
 from file_utils import * #table from folder is defined here  
 import table_read as Table  
 from TableDef import columns #Custom definition of the table structure  
 from TableDef import DatabaseCredentials as DB #Custom definition of the table structure  
   
 def init():  
   plotline.set_data([], [])  
   dplotline.set_data([],[])  
   return plotline,dplotline,  
   
 def animate(i):          
   global buffersize    
   if (i%100==0):  
     print i        
   line= Table.getdataframe(table,columns[1],i,DB.serverIP, DB.user, DB.password, DB.name)    
   
   try:  
     jsondata=json.loads(line)    
   except ValueError:  
     print "Invalid JSON"  
     print line  
     f.close()  
     os.system("pause")      
     
   pos=jsondata["Position"]       
   vel=jsondata["Velocity"]  
   
   pos_buf.append(pos)  
   vel_buf.append(vel)  
     
   while len(pos_buf)>buffersize:  
     pos_buf.pop(0)  
   while len(vel_buf)>buffersize:  
     vel_buf.pop(0)  
     
   x=np.linspace(-len(pos_buf)/framerate,0,len(pos_buf))  
   dx=np.linspace(-len(vel_buf)/framerate,0,len(vel_buf))        
     
   plotline.set_data(x,headpose_buf)  
   dplotline.set_data(dx,headvel_buf)    
   return plotline, dplotline,  
   
 table=""   
 framerate=20.0  
 buffersize=5*20  
 vel_buf=[]  
 pos_buf=[]  
   
 fig, ax = plt.subplots()  
 ax.set_xlim(-5.0,2.0)  
 ax.set_ylim(-180,180)  
 my_dpi=96  
 fig.set_size_inches(640/my_dpi, 360/my_dpi)    
 plotline, =ax.plot([],[],lw=2,color='b')  
 dplotline, =ax.plot([],[], lw=2, color='r')  
   
 if __name__=='__main__':  
   if len(sys.argv)<2:  
     print "Usage:\nplot_pos_vel.py folder"  
     exit()  
     
   folder= sys.argv[1]       
   outfile=folder+"/pos_vel.avi"  
   if (os.path.isfile(outfile)):  
     exit()   
   table=table_from_folder(folder)  #Custom function that maps folders to their table representation, user defined  
   line_count=Table.count(table)    
     
   Writer = animation.writers['ffmpeg']  
   writer = Writer(fps=25, metadata=dict(artist='Sayanan'), extra_args=['-vcodec','libx264'])      
   anim = animation.FuncAnimation(fig, animate,init_func=init, frames=line_count-1,blit=True, interval=1, repeat=False)      
   anim.save(outfile,writer=writer)  
     
   #plt.show()  
     

Within the entries in the table, I've further structured my data as json for position and velocity. Again, this is really a design choice, and depending on your database, json encoding might be native.

Other than that, this is the same Matplotlib example as before, but using a database for the data.

Pallindromes in C++

Sometimes you come across puzzles or interview questions along the lines of "Find the longest palindrome in a string." To be honest, I've never looked for palindromes in my work, but I think it's a good exercise nonetheless. For one thing, the "best practices" strategies can be applied to other problems. For another, the search for symmetric subsets in datasets of all types definitely does come up.

So, we might start this exercise by first writing a function to classify a string as a palindrome or not. A nice way to do this is to start with a pointer at either end of the string, and iterate them inwards, checking the lower and upper characters against each other at each stage.  For example, if the first and last characters are equal, we iterate inwards. If not, we can return "false" immmediately. The following snippet shows this function.

 bool is_pallindrome(string input){  
      int lower=0;  
      int upper=input.length()-1;  
      while (upper>lower){  
           if (input[upper]!=input[lower]) //If we find differing characters, not a pallindrome  
                return false;  
           upper--;  
           lower++;  
      }  
      return true;  
 }  

So now, to find the longest palindrome in a string, we could just iterate over the string, looking at all substrings, and calling is_pallindrome() [notice my typo in the function name]. That sounds pretty straight-forward, but searching all substrings becomes O(N^2), kind of cumbersome.

A nice way to use the is_pallindrome() function is to think about strings that are centered at index i. So, we have a pointer that searches left from i, and a pointer that searches right from i, and we stop iterating when input[lower]!=input[upper]. This is very similar to the is_pallindrome() function.

There's another approach that's more efficient than the above. Sometimes a good way to think about such a problem is to find the desired subset that ends at index i. If I'm searching for a palindrome that ends at index i, I can store the longest palindrome that ended at index i-1. Then I simply have to look at the first index of that palindrome, and the character that precedes it in the input string.

The storage/caching can be implemented with a hashmap, so we store the longest palindrome that ends at each index, and then we can look it up at the next step. This means, each additional step only features two more comparisons. The following snippet implements this approach:

 string longest_pallindrome_map(string input){  
      map<int, string> pal; //hashmap from index to longest pallindrome that *ends* at index  
      int max_length=0; int max_index=0;  
      for (int i=0; i<input.size(); i++){  
           int prev_index=i-pal[i-1].length()-1;            
           if (pal[i-1][0]==input[i]) //Looking for consecutive duplicate letters  
                pal[i]=pal[i-1]+input[i];            
           else if (input[i]==input[prev_index])  
                pal[i]=input[prev_index]+pal[i-1]+input[i]; //Looking at the character prior to previous pallindrome  
           else  
                pal[i]=string(input.begin()+i, input.begin()+i+1); //Longest pallindrome is current character  
   
           if (pal[i].length()>max_length){  
                max_index=i;  
                max_length=pal[i].length();            
           }            
      }  
      return pal[max_index];  
 }  

This is actually quite a bit more efficient in the searching, more like pseudo-linear instead of quadratic search. [Again notice my mispelling of palindrome.]  The only thing is, we are storing a bunch of strings in this hashmap. We don't actually need to do this.

Instead, we can just store the indices or pointers that begin the palindromes that ends at each index in the input string. The following function does this.

 string longest_pallindrome(string input){       
      map<int, int> pal; //hashmap from current index, to the begin-index of the longest pallindrome that *ends* here  
      int max_length=0;  
      int max_ind=0;  
      for (int i=0; i<input.size(); i++){                           
           int prev_index=pal[i-1];                                
           if (input[i]==input[prev_index]){ //Looking for consecutive duplicate characters  
                pal[i]=prev_index;  
           }  
           else if (input[i]==input[prev_index-1]) //Looking at the index prior to the last pallindrome  
                pal[i]=prev_index-1;  
           else  
                pal[i]=i; //Longest pallindrome is simply the current character  
           if ((i-pal[i])>max_length){ //Finding the longest one along the way  
                max_ind=i;  
                max_length=i-pal[i];  
           }                           
      }            
      return string(input.begin()+pal[max_ind], input.begin()+max_ind+1);  
 }  

So now we have, via dynamic programming, a pseudo-linear search, in that we basically have a linear search over the input string, but we have to store O(N) indices.

Did I really need the hashmap? Not necessarily; I could have used a regular old array, and had some code to check_bounds. On the other hand, the hashmap approach is generalizable to other problems, where the key values might not be simple ordinal numbers.

Matplotlib Animations, Using Stored Data, Writing Video

There are some good matplotlib animations examples floating around the internet, including here and here. These were useful and I gained a great deal from them, but my particular problem was not directly addressed.

The scenario we're looking at today is the following. We have some stored data on disk, that we would like to plot using a Matplotlib animation, and save this animation as a video file. This is a reasonably common occurrence for researchers, but I had trouble finding tutorials online for this problem. Many of the tutorials generated their data via simulations on the fly, which didn't directly map to the case of recorded data.

There were two stumbling blocks I ran into, that had non-obvious solutions. First, Matplotlib's animation takes a function pointer to a user-defined function, for example def animate(i), but the animate function is then controlled by the iterator i. The second major stumbling block I hit, is that your animation function def animate(i): should return the data structures that need to be updated.

In this example, I have saved some data to a file in JSON format; each entry has a position and a velocity parameter. I read this file in line-by-line, and create a scrolling plot of the time series. I save this animated scrolling plot as a video file to disk, using ffmpeg and x264 for video encoding.

 import sys  
 import os  
 import json  
 import numpy as np  
 import matplotlib  
 import matplotlib.pyplot as plt  
 import matplotlib.animation as animation  
 from time import time  
 import itertools  
   
 from matplotlib.path import Path  
 import matplotlib.patches as patches  
 import threading  
   
   
   
 def init():  
   plotline.set_data([], [])  
   dplotline.set_data([],[])  
   return plotline,dplotline,  
   
 def animate(i):        
   #ax.clear()  
     
   global frame_num, buffersize  
     
   if (frame_num%100==0):  
             print frame_num    
   line=f.readline()  
   jsondata=json.loads(line)  
   frame_num+=1  
     
   if "Position" in jsondata:  
     pos= jsondata["Position"]  
       
   if "Velocity" in jsondata:  
             vel=jsondata["Velocity"]  
   
   pos_buf.append(pos)  
   vel_buf.append(vel)  
     
   while len(pos_buf)>buffersize:  
     pos_buf.pop(0)  
   while len(vel_buf)>buffersize:  
     vel_buf.pop(0)  
     
   x=np.linspace(-len(pos_buf)/framerate,0,len(pos_buf))  
   dx=np.linspace(-len(vel_buf)/framerate,0,len(vel_buf))        
     
   plotline.set_data(x,headpose_buf)  
   dplotline.set_data(dx,headvel_buf)    
   return plotline, dplotline,  
   
 def folder_from_path(file):  
   split_path=file.split("/")  
   folder=split_path[0]  
   for i in range(1,len(split_path)-1):  
     folder+="/"+split_path[i]  
   return folder  
   
 #Setting up globals  
 file=""    
 frame_num=0    
   
 framerate=20.0  
 buffersize=5*20  
 vel_buf=[]  
 pos_buf=[]  
   
 fig, ax = plt.subplots()  
 ax.set_xlim(-5.0,2.0)  
 ax.set_ylim(-180,180)  
 my_dpi=96  
 fig.set_size_inches(640/my_dpi, 360/my_dpi)    
 plotline, =ax.plot([],[],lw=2,color='b')  
 dplotline, =ax.plot([],[], lw=2, color='r')  
   
 if __name__=='__main__':  
   if len(sys.argv)<2:  
     print "Usage:\nplot_data.py file"  
     exit()  
   #Parsing command-line arguments, checking the input file exists.  
   file= sys.argv[1]  
   print file  
   if (os.path.isfile(file)==False):  
       print "Problem with file"  
       exit()   
   folder=folder_from_path(file)  
   #Writing video to same folder  
   outfile=folder+"/data.avi"  
   print folder  
   #Getting number of data points from file. A little hackey, but I couldn't control animate() with the file open()            
   line_count=0  
   with open(file, 'r') as f:  
     for read_data in f:      
       line_count=line_count+1  
   print line_count  
   f=open(file,'r')  
   Writer = animation.writers['ffmpeg']  
   writer = Writer(fps=25, metadata=dict(artist='Sayanan'), extra_args=['-vcodec','libx264'])      
   anim = animation.FuncAnimation(fig, animate,init_func=init, frames=line_count-1,blit=True, interval=1, repeat=False)      
   anim.save(outfile,writer=writer)  
   f.close()  
   #plt.show()  
     

So there you go. A basic program that plots animation, and saves the resulting video to disk, using recorded data, stored in JSON on disk.

Edit: Just a quick addendum. I also had some trouble plotting animations of a grid of custom polygons, which could be useful for mapping, occupancy grids, or similar data. Here's a quick demo for how to generate animations of this sort:

 "Demo of a grid of PathPatch objects."  
 import numpy as np  
 import matplotlib  
 import matplotlib.pyplot as plt  
 import matplotlib.animation as animation  
 from time import time  
 import itertools  
   
 from matplotlib.path import Path  
 import matplotlib.patches as patches  
   
 def animate(i):       
   prob=np.random.rand(np.size(yr)*np.size(xl))  
   ax.clear()  
   cells=[]  
   for i in range(0,len(P1)):    
     verts=[P1[i], P2[i], P3[i], P4[i], P1[i] ]  
     path = Path(verts, codes)  
     patch = patches.PathPatch(path, color=[1-prob[i],prob[i],0], lw=2)  
     cells.append(ax.add_patch(patch))  
   return cells  
     
   
 fig, ax = plt.subplots()  
 fig.set_size_inches(5,20)  
   
 width=3.5  
 height=5.0  
   
 xl=np.arange(-8.75,8.75,width)  
 yr=np.arange(-50.0,50.0,height)  
 ax.set_xlim(xl[0],xl[np.size(xl)-1]+width)  
 ax.set_ylim(yr[0],yr[np.size(yr)-1]+height)  
 cells=[]  
 print yr[10]  
 print np.size(yr)  
 print np.size(xl)  
 P1=list(itertools.product(xl,yr+height))  
 P2=list(itertools.product(xl+width, yr+height))  
 P3=list(itertools.product(xl+width, yr))  
 P4=list(itertools.product(xl,yr))  
 prob=np.random.rand(np.size(yr)*np.size(xl))  
 codes = [Path.MOVETO,  
      Path.LINETO,  
      Path.LINETO,  
      Path.LINETO,  
      Path.CLOSEPOLY,  
      ]  
 for i in range(0,len(P1)):  
   verts=[P1[i], P2[i], P3[i], P4[i], P1[i] ]  
   path = Path(verts, codes)  
   patch = patches.PathPatch(path, color=[1-prob[i],prob[i],0], lw=2)  
   cells.append(ax.add_patch(patch))  
 anim = animation.FuncAnimation(fig, animate, blit=True, save_count=0,interval=10)  
 plt.show()  
   

Matplotlib Animation Save with FFmpeg Freezes After N Frames

Matplotlib is a go-to plotting tool in Python, which has a lot of useful features, like compatibility with the Scipy/Numpy stack. Sometimes it's useful to visualize time-series data temporally.

One very useful feature that Matplotlib has is the animations module, which allows you to animate plots with changing data [over time, for example], and save the data as a video file using FFmpeg. There's a great tutorial for Matplotlib animations here.

My only complaint about the Matplotlib animations, is that the documentation and examples are not super-comprehensive. I might create a follow-up post with some sample programs, to add to the documented examples floating around the interwebs.

In any case, once I got the animations working, I wanted to save them as a video for later on-demand viewing. I set up an animation writer with ffmpeg, x264, and let it run. Each time I ran the script, and the video saving would freeze after 820 frames.

It took a fair amount of online searching to find the answer here. It turns out that the stock Ubuntu/Debian FFmpeg and LibAV have branched apart at some point. You can obtain the "real" FFmpeg here. Once you install this, the Matplotlib animations save videos just fine.

USB Serial COM Ports and Python

I was working with a simple device that provides data via USB Serial COM. For whatever reason, the C++ library I was using to read from the device was not working consistently on different machines.

USB Serial COM is akin to socket programming. The routines are somewhat platform-dependent, and today's developer doesn't usually care about the details. Just give me an abstraction that lets me communicate!

Then I realized that Python has PySerial. Using this library, I was easily able to communicate with the device, and send it via localhost socket to my C++ program. Done and done.

Check out the super simple source code:

 import serial  
 import socket  
   
 IP="127.0.0.1"  
 PORT=3001  
 sock=socket.socket(socket.AF_INET,socket.SOCK_DGRAM) #Sending data to localhost via UDP  
   
 ser= serial.Serial(2,timeout=2) #COM3 is port number 2.  
 print ser.name  
 line=''  
 while (True):  
      line=ser.readline()  
      print line  
      sock.sendto(line,(IP,PORT))  

Python for the win.

Winsock TCP Client in C++

Recently I've been looking at a server-client software architecture for machine learning.  A lot of really great machine learning and mathematical modeling toolboxes are now written in Python. However, if you're working directly with a sensor-based system, your sensor capture code is often written in C/C++.

Yes, you could write a wrapper for that code, but it can be a slow and redundant process.

Instead, you can set up a Python TCP server like so , even on the localhost on the same machine, send a JSON structure with your feature vector, do your heavy number-crunching in Python, and send the result back to the C++ client.

There's a lot of documentation out there for TCP servers and clients on *nix in C and C++, but the documentation for Windows is less available, written in pure C, or cryptic to understand. I wanted a class that would abstract away most of the nuts and bolts.

Using the Windows Winsock documentation example, I've written a simple Winsock TCP client class in C++. This code will build with any semi-recent version of Visual Studio Express or Professional. It's really simple stuff, just easier to read.

Here's the header file, which I called TCPClient.h

#ifndef TCP_CLIENT_H
#define TCP_CLIENT_H
#define WIN32_LEAN_AND_MEAN

#include <windows.h>
#include <winsock2.h>
#include <ws2tcpip.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <iostream>
#include <sstream>

#pragma comment (lib, "Ws2_32.lib")
#pragma comment (lib, "Mswsock.lib")
#pragma comment (lib, "AdvApi32.lib")


class TCPClient{
public:
    TCPClient(); //Default constructor
    TCPClient(const char* host, const char* port); //Constructor with host-ipaddress, port number
    TCPClient(std::string host, std::string port); //Constructor with host-ipaddress, port number
    TCPClient(const char* host, const char* port, const int buffer_size); //Constructor with host-ipaddress, port number, buffersize [rarely used]
    TCPClient(std::string host, std::string port, const int buffer_size); //Constructor with host-ipaddress, port number, buffersize [rarely used]
    int init(); //initialization, called by constructors
    ~TCPClient(); //clean up winsock environment
    bool open(); //open connection
    bool open(const char* host, const char* port); //open connection with host-ipaddress, port number
    bool open(std::string host, std::string port); //open connection with host-ipaddress, port number
    int send_buf(const char* sendbuf);    //send a message. Returns the number of bytes successfully sent. Returns -1 if failed.
    int send_buf(std::string sendbuffer); //send a message. Returns the number of bytes successfully sent. Returns -1 if failed.
    int receive(std::string& recvbuffer); //receive a message. Returns the number of bytes received.
    bool shutdown_send(); //shutdown the outgoing connection
    bool close(); //close the socket    
private:
    int resolve(); //used internally, resolving host. Returns -1 if failed.
    int connect_to(); //used internally, actually connect. Returns -1 if failed.

    int _buffer_size;    //buffer size in bytes
    int iResult;        //errorcodes from Winsock

    WSADATA wsaData;   //Winsock stuff
    SOCKET ConnectSocket; //Socket
    struct addrinfo *result, *ptr, hints; //Winsock stuff

    std::string host; //host ipaddress
    std::string port; //port number
    bool _connection_open; // Is the connection open?
    bool _ipset; //Did we initialize with host and port number?
    bool _shutdown_sent; //Have we sent a shutdown message to the host?
};

#endif

Here's the class implementation. Again, really simple stuff.

#include "TCPClient.h"

int TCPClient::init(){
    ConnectSocket = INVALID_SOCKET;
    result=NULL;
    ptr=NULL;

    iResult = WSAStartup(MAKEWORD(2,2), &wsaData);
    if (iResult != 0) {
        std::cerr<<"WSAStartup failed with error: "<<iResult<<"\n";
        return -1;
    }
    ZeroMemory( &hints, sizeof(hints) );
    hints.ai_family = AF_UNSPEC;
    hints.ai_socktype = SOCK_STREAM;
    hints.ai_protocol = IPPROTO_TCP;
    this->_buffer_size=4096;
    this->_shutdown_sent=false;
    return 0;
}
TCPClient::TCPClient(){
    this->_ipset=false;
    if (init()<0){
        std::cerr<<"Error initializing WinSock\n";
        exit(1);
    }
}
TCPClient::TCPClient(const char* host, const char* port){
    this->host=host;
    this->port=port;
    this->_ipset=true;
    if (init()<0){
        std::cerr<<"Error initializing WinSock\n";
        exit(1);
    }
}
TCPClient::TCPClient(std::string host, std::string port){
    this->host=host;
    this->port=port;
    this->_ipset=true;
    if (init()<0){
        std::cerr<<"Error initializing WinSock\n";
        exit(1);
    }
}
TCPClient::TCPClient(const char* host, const char* port, const int buffer_size){
    this->host=host;
    this->port=port;
    this->_ipset=true;
    this->_buffer_size=buffer_size;
    if (init()<0){
        std::cerr<<"Error initializing WinSock\n";
        exit(1);
    }
}
TCPClient::TCPClient(std::string host, std::string port, const int buffer_size){
    this->host=host;
    this->port=port;
    this->_ipset=true;
    this->_buffer_size=buffer_size;
    if (init()<0){
        std::cerr<<"Error initializing WinSock\n";
        exit(1);
    }
}
TCPClient::~TCPClient(){
    WSACleanup();
}

int TCPClient::resolve(){
    // Resolve the server address and port
    iResult = getaddrinfo(host.c_str(), port.c_str(), &hints, &result);
    if ( iResult != 0 ) {
        std::cerr<<"getaddrinfo failed with error: "<<iResult<<"\n";
        WSACleanup();
        return -1;
    }
    return 0;
}
int TCPClient::connect_to(){
    // Attempt to connect to an address until one succeeds
    for(ptr=result; ptr != NULL ;ptr=ptr->ai_next) {
        // Create a SOCKET for connecting to server
        ConnectSocket = socket(ptr->ai_family, ptr->ai_socktype, 
            ptr->ai_protocol);
        if (ConnectSocket == INVALID_SOCKET) {           
            std::cerr<<"socket failed with error: "<<WSAGetLastError()<<"\n";
            WSACleanup();
            return -1;
        }
        // Connect to server.
        iResult = connect( ConnectSocket, ptr->ai_addr, (int)ptr->ai_addrlen);
        if (iResult == SOCKET_ERROR) {
            closesocket(ConnectSocket);
            ConnectSocket = INVALID_SOCKET;
            continue;
        }
        break;
    }
    freeaddrinfo(result);
    if (ConnectSocket == INVALID_SOCKET) {
        std::cerr<<"Unable to connect to server!\n";
        WSACleanup();
        return -1;
    }
    return 0;
}

bool TCPClient::open(){
    if (this->_ipset==false)
        return false;
    if (resolve()<0)
        return false;
    if (connect_to()<0)
        return false;
    return true;
}
bool TCPClient::open(const char* host, const char* port){
    this->host=host;
    this->port=port;
    this->_ipset=true;
    this->_connection_open=this->open();
    return _connection_open;
}
bool TCPClient::open(std::string host, std::string port){
    this->host=host;
    this->port=port;
    this->_ipset=true;
    this->_connection_open=this->open();
    return _connection_open;
}
int TCPClient::send_buf(const char* sendbuf){
    if (_connection_open==false)
        return -1;
    // Send an initial buffer

    iResult = send( ConnectSocket, sendbuf, (int)strlen(sendbuf), 0 );
    if (iResult == SOCKET_ERROR) {
        std::cerr<<"socket failed with error: "<<WSAGetLastError()<<"\n";    
        WSACleanup();
        return -1;
    }   
    return iResult;
}
int TCPClient::send_buf(std::string sendbuffer){
    
    int length=sendbuffer.length();
    if (_connection_open==false)
        return -1;
    // Send an initial buffer
    iResult = send( ConnectSocket, sendbuffer.c_str(), length, 0 );

    if (iResult == SOCKET_ERROR) {
        std::cerr<<"socket failed with error: "<<WSAGetLastError()<<"\n";
        this->close();
        WSACleanup();
        return -1;
    }   
    return iResult;
}
int TCPClient::receive(std::string& recvbuffer){
    // Receive up to _buffer_size bytes
    recvbuffer.clear();
    int total=0;
    char* recvbuf=new char[this->_buffer_size];    
    iResult = recv(ConnectSocket, recvbuf, _buffer_size, 0);
        if ( iResult > 0 ){            
            std::string received_str=recvbuf;
            received_str.resize(iResult);
            recvbuffer+=received_str;
            total+=iResult;            
        }
        else if ( iResult == 0 ){
            std::cout<<"\nConnection closed\n";            
        }
        else            
            std::cerr<<"recv failed with error: "<<WSAGetLastError()<<"\n";
   
    delete [] recvbuf;
    return total;
}
bool TCPClient::shutdown_send(){
     // shutdown the connection since no more data will be sent
    iResult = shutdown(ConnectSocket, SD_SEND);    
    if (iResult == SOCKET_ERROR) {
       std::cerr<<"shutdown failed with error: "<<WSAGetLastError()<<"\n";       
        this->close();
        WSACleanup();
        return false;
    }
    this->_shutdown_sent=true;
    return true;
}
bool TCPClient::close(){
    if (!_shutdown_sent)
        shutdown_send();        
     // cleanup
    closesocket(ConnectSocket);
    return true;
}

And finally, this is the main function, which shows how to invoke the class. I had a very simple TCP server written in Python, running on a different machine on the same local network.

The main program simple gets your keyboard input and sends it to the server. If you input the string "exit", the program exits cleanly.

int main (int argc, char* argv[]){
    TCPClient myClient("192.168.1.2","5000");    
    if (!myClient.open()){
        char a;
        std::cout<<"Enter any key to exit\n";
        std::cin>>a;
        return 0;
    }

    while (true){        
        std::string input; 
        std::cout<<"Enter something to send to the server\n";
        getline(std::cin,input);
        if (!input.compare("exit")){
            myClient.close();
            break;
        }
        if (myClient.send_buf(input)<0)    
            break;    
        std::string received;
        if    (myClient.receive(received)<0)
            break;    
        std::cout<<"Received:\n"<<received<<"\n\n";            
    }
    return 0;
}

Much easier to read and understand, than the original code on the Microsoft documentation site. Cheers!

Binary Search With Pointers, C++

Today I'm posting my version of binary search, using pointers in C++. Binary search is a fundamental algorithm, which searches for an element in a sorted array. It is considered the mother of all divide-and-conquer algorithms, and executes in log(N) time, where N is the size of the array. The log is taken with respect to base 2 [binary].

Implementing Binary Search with pointers is a nice exercise that brings together a few concepts.

1. While binary search is an important algorithm from a conceptual standpoint, it's also highly practical and has come up in my research and work. Consider captured data that is indexed by its timestamp, e.g.

                timestamp :  value 1, value 2,....value N
             
The most efficient way to search for the values at a particular timestamp is binary search. In reality, we may want the nearest timestamp to a given reference, but that's a minor adjustment to the algorithm.

2. Implementing binary search with pointers helps to reinforce understanding of pointers, a concept which tends to trip up many C++ programmers.

3. Despite the fact that binary search is a fundamental algorithm, very few job applicants are able to code it correctly on a whiteboard. In short, it's good practice.

In our example, we initialize an array with random elements, then sort it. First we demonstrate how we find an element in the array. Second, we demonstrate how the function behaves when we search for an unknown element. Now, to the code:

 #include <iostream> //For std::cout  
 #include <algorithm> //For std::sort  
 #include <stdlib.h> //For srand, rand   
 #include <time.h>  //For time   
   
 template<class T> //template class means we can accept arguments of different classes: int, float, double, etc.  
 int binarysearch(T* arr /*pointer to beginning of array*/, T* low, T* high, T searchkey /*seeking this value in array*/){  
      int index=-1; //Default value, if we don't find searchkey  
      if (*low>*high) //Double-checking that the array's actually sorted  
           return index;  
      if (low>high) //At this point, we've searched the whole array  
           return index;  
   
      T* mid=(high-low)/2+low; //The array index midway between high and low  
      if (*mid==searchkey)   //We've found the searchkey  
           return mid-arr;  
      if (searchkey<*mid)  
           return binarysearch(arr,low,mid-1,searchkey); //Recursive call to search the lower half of the array  
      else if (searchkey>*mid)  
           return binarysearch(arr,mid+1,high,searchkey); //Recursive call to search the upper half of the array  
   
      return index;  
 }  
   
 int main(int argc, char* argv[]){  
      //Using srand to initialize rand() with time()  
      srand (time(NULL));  
   
      //Size of our array will be 15  
      int size=15;   
      int* arr=new int [size]; //Note that arr is the array, and is also a pointer. It points to a memory block of 15 integers.  
      for (int i=0; i<size; i++){            
           arr[i]=rand()%100; //Randomly initialize the elements of the array, integers between 0 and 100  
           std::cout<<arr[i]<<",";  
      }  
      std::cout<<"\n";                 
      std::sort(arr,arr+size); //Sort the array  
      for (int i=0; i<size; i++)  
           std::cout<<arr[i]<<",";  
      std::cout<<"\n";  
   
      //Finding element in array.   
      int to_find=arr[rand()%size]; //Choosing an element at random from the array to search using binary search  
      int found_index=binarysearch(arr,arr,arr+size-1,to_find);  
      if (found_index>-1)  
           std::cout<<"Found "<<to_find<<" at location "<<found_index<<"\n\n";  
      else  
           std::cout<<"Couldn't find "<<to_find<<" in array\n\n";  
   
      //Finding unknown element  
      to_find=100; //We initialized the array with elements strictly smaller than 100  
      found_index=binarysearch(arr,arr,arr+size-1,to_find);  
      if (found_index>-1)  
           std::cout<<"Found "<<to_find<<" at location "<<found_index<<"\n";  
      else  
           std::cout<<"Couldn't find "<<to_find<<" in array\n";  
   
      delete [] arr; //Clean up dynamically allocated memory  
      return 0;  
 }