Measuring the size of a type without sizeof
November 25th, 2009 § 1 Comment
Suppose you wanted to check the size (in bytes) of a certain type, WITHOUT using the sizeof() operator. How would you do that?
And what is the size of an empty struct (or class), anyway?
ScopeLogger
November 18th, 2009 § 13 Comments
The RAII design pattern can be utilized to create simple and intuitive logging facilities, like the one we will present now. Through the useful macro LOG_FUNC, the proposed ScopeLogger will easily create function call graphs at run time, to allow easy debugging and tracking of program execution.
Enumerating permutations
November 14th, 2009 § 5 Comments
There are exactly n! different permutations of n numbers. This challenge was about writing a function which is able to enumerate all these permutations, i.e. function permute(n, idx) which is able to return permutation with index idx of n numbers. The requirement is of course that all these permutations must be unique – this is in order to go over all possible permutations.
Using the state design pattern to implement FSMs
November 13th, 2009 § 1 Comment
The State design pattern is a very useful design pattern. In this article we will exploit it to provide a very slick and elegant implementation of a Finite State Machine (FSM).
First of all, a FSM consists of a finite number of states and a predefined set of rules defining the transitions between all these states. Each state can either ACCEPT or REJECT the input - the FSM accepts the input IFF it ends up on an accepting state at the end of execution. In our design, each state will be modeled by a distinct class derived from an abstract base State class. Each state class will also contain all of its relevant transition logic. This architecture will enable us to provide a very flexible, powerful, yet intuitive and simple, implementation of any FSM.
Reset an array in constant time
November 5th, 2009 § 12 Comments
Ever wondered how to reset an entire array of N elements in a constant slice of time? This post will introduce the algorithm along with an implementation.
Let me lay out the problem. There’s an array of N integers. We would like to be able to reset that array (set all elements to zero), in a set amount of time – regardless of the value of N. The reset operation should take the same amount of time whether it operates on 100 elements or 10,000 of them.