Deleting a Node from Singly Linked List

Deleting a Node from Singly Linked List is rather straight forward.

• You have to know the head first of all

• Start by checking the head if that’s the one you are looking for

• Keep moving forward and checking - always check for null pointers everywhere

Before we talk about the code, let’s see how Linked List is setup.

Now, below is the code for it….

Code

As usual the code is available here:

https://github.com/abhi1010/Algorithms

Usage of typename

What is wrong with the following code?

The issue is very simple but hard to notice. If you try to compile this, you will get the following errors:

    main.cpp:24:5: error: need 'typename' before 'OuterStruct<T2>::InnerStruct' because 'OuterStruct<T2>' is a dependent scope
    OuterStruct<T2>::InnerStruct mUsingInner;
    ^
    main.cpp: In function 'int main(int, char**)':
    main.cpp:34:13: error: 'struct InnerStruct_Wrapper<int>' has no member named 'mUsingInner'
    wrapper.mUsingInner = innerStrct;

The Issue

At least it straight away tells you something is wrong with InnerStruct_Wrapper. Here’s what is happening:

• The compiler does not know that mUsingInner in that line is actually a variable of type “OuterStruct::InnerStruct”

• InnerStruct will only be known later when it is being instantiated

• Compiler cannot figure out what InnerStruct means here. It could be a type or a member variable

The Fix

The only way here is to help the compiler by telling it beforehand that is going to be a class or struct type. The way to tell the compiler that something like this is supposed to be a type name is to throw in the keyword “typename”. The “typename” keyword has to be used everytime you want to tell the compiler that it should expect a Type in its place.

One place where this is used quite a lot is when templates have to implement iterators.

Full Code

The full sample code, along with the fix is provided on Stacked-Crooked.

Setting up your VIM... Your style

Writing code using VIM can be a bit overwhelming but it helps creating a few shortcuts there to make your life easier. Here I will discuss a few.

• First of all, it is always a good idea to set up your tabs and spaces
• Set up shortcuts for:
  • Toggling of Auto-Indent while pasting source text; very useful in code (F2 in my provided script)
  • Toggling of Auto-Scroll of Split windows (F3 in my provided script)
  • Macro for Folding functions within the source code (@q in my provided script)
  • Smart case search - based on whether the input is in caps or not
  • Toggling of Mouse Usage in VIM window - to allow quick selection of text (F12 in my provided script)

Please see the provided script below to have a look.

Getting a group of lines from a file

I’ve had this need quite a few times to pull out a section of logs that would begin with a particular line and end with another. grep is not exactly useful there because it only prints out sections based on line counters (using -A/B/C) lines based on a single search pattern.

I came up with a script that can run at almost same speeds using grep/cat/awk. awk is used to decide whether the end of the section has been reached or not. Some features of the script are:

• Since awk script only toggles one variable it works seamlessly without delaying the actual work

• Works on gzip files as well

• If you do not want to depend on grep or are unsure how many lines may be between begin and end keyword then replace gunzip with zcat and grep with cat.

• Usage: group filename printBeginKeyword printUntilKeyword NumOfLines

Let’s have a look at the script….

32 bit vs 64 bit

When to use 64-bit?

If your application needs more than 2-4gb of data

• If your application intensively uses 64-bit arithmetic
• * 32-bit x86 compiled applications are restricted to x86 instruction set, even when run on on a 64-bit machine
• x64 supports 16 registers compared to just 8 in x86. If your code is computation intensive this may help a great deal

When to use 32-bit?

After reading so many great things about 32 bit, why would anybody still want to code against 32-bit? Simple reason - code compiled in 32-bit takes lesser memory. For example, a pointer in 64-bit machine is 8 bytes compared to 4 bytes with 32-bit. Now imagine how many pointers do you have going around in your code?

When to not use 64-bit?

Sometimes if your code is running on a machine that does not have too much of space then it is a never a great idea to use 64-bit compilation because the same task can probably be done much better using 32-bit version. L2 and L3 caches will be utilized a lot more in 64-bit code (and a lot earlier as well) compared to 32-bit; on such systems.

Summary

Always benchmark your code and ensure that the application actually needs more than 2-4Gb of space.

Tokenize a String using C++

Here’s a short snippet to split a string into multiple tokens; into a vector. As you will see that, if you run the code, boost version performs better because you can choose a number of delimiters to split your string instead of the vanilla version using the normal C++ code. Of course, you may also write your own code to do something like this but I was looking to do some short snippets.

I have posted my code on Stacked-Crooked which you can view along with the output as well. It shows C++ doesn’t perform so well.

Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort

I had written about sorting algorithms (Tag: Sorting) with details about what to look out for along with their code snippets but I wanted a do a quick comparison of all the algos together to see how do they perform when the same set of input is provided to them. Hence I started working on a simple implementation for each one of them. I have now put together all of them in a single project on GitHub. I ensured that they all have the same set of procedures during their run. Some of the items I wanted to ensure was:

• Same input array

• Same number of iterations. Each iteration having the same input

• Each algo being timed the exact same way as another

Some of the algorithms being tested were:

• Heap Sort

• Merge Sort

• Insertion Sort

• Radix Sort

• Counting Sort

• Quick Sort

How did we ensure Equality?

• Created a simple base class for all algorithms: AlgoStopwatch

• • Responsible for benchmarking everything

  • Provide a function called doSort() that would allow derived classes to implement their algorithm

  • Ensures that every algorithm has a name and description - to help us distinguish

• Another class to help manage the testing of all the algorithms: AlgoDemo

• • All instances are created here for the algorithms

  • The input array is provided by this class to all algorithms

Code

As usual the code for the project is available here:

https://github.com/abhi1010/Algorithms

It can be run using Visual Studio without any changes.

Numbers

Looking at the numbers below, it may be hard to compare the actual values. Hence I decided to normalize them by calculating how much time will be required to sort 100 numbers using the same rate as the actual numbers. They are provided for all algorithms on the right-most column.

Global Search in VIM

You must be knowing about regular VIM search

%s/SEARCH/REPLACE/CMD

However, sometimes you do not want to replace something but just see all instances of the a word or phrase. In such cases, global search is really useful when on vim. The syntax is simpler than normal search-replace:

:[range]g[lobal]/{pattern}/[cmd]

This will show all instances of the “SEARCH” term within the VIM window. There’s another version of the same command which is as follows:

:[range]g[lobal]!/{pattern}/[cmd]

This is similar to the previous command but the only difference is that this command contains “!” which signifies that the command will be executed on all lines NOT matching the pattern.

One example here would be to delete all lines in a file containing a particular word:

:g/deleteMe/d

There could be lot more actions (regular vim stuff) that you could do like yanking or indenting.

Reading Excel in C#

Recently had to work on an Excel and update its content when some events were triggered on a Bloomberg terminal. I couldn’t find any code for reading the excel file using C# so thought of putting that up.

There were a few things to learn:

• Excel support is not available by default so make sure to add Microsoft.Office.Interop.Excel as a reference

• Sometime indexing to reference the Workbooks or Worksheets may not work so try out other values

• • I remember this was not a problem with Visual Studio 2010 but something must have happened in Visual Studio 2012
    

• It is also possible to try Workbook names to try and retrieve them

Please follow the shortened code to read an Excel file after the break.

Ideas for Shared Memory in Linux

I have been doing extensive research today regarding shared memory in linux before I embark on a new project in which shaving time off process communication latency is extremely important. I found some very interesting links as well. Let’s break them down: