relocatable address

The address generated by the compiler are relocatable addresses.
See : Introduction to computer-based imaging systems By Divyendu Sinha, Edward R. Dougherty , page.213 :

Assuming the page size as 64 KB (2¹⁶):
The compiler generated relocatable addresses as if the entire program were to be loaded at once. The page number and offset can be easily computed from the relocatable address. Since the offset must be a nonnegative number smaller than the page size, the offset is the least significant 16 bits of the relocatable address. The remaining 25-16 = 9 bits specify the page number. Consider the relocatable address 145678. Since

145678 (decimal) = 0 00000010 00111001 00001110 (binary),
we have the page number as 2 (or 000000010 in binary) and the offset as 14,606( or 0011100100001110 in binary).

If the page size is changed later on to 32KB, programs need not be recompiled to run on the system. Computation of page number and offset is done by the memory manager

Basic introduction to probability

Surprisingly the basic introduction to probability was found in a biology book!
Here is the summary:
Product Rule:
When two or more events are independent, the probability that they will occur in succession is calculated using the product rule--their individual probabilities are multiplied. Ex : probability of getting two heads in succession is 1/2 x 1/2 = 1/4

Sum Rule:
Sum Rule is applied when there are two or more different ways of obtaining the same outcome; that is, the probability tat either event A or event B will occur equals P(A) + P(B)

Source: Billogy: Te dynamic science by Peter Russell p.240

reversing a linked list

Few of the most elegant solutions for reversing a linked list:
1. Stanford : Linked list problems
2. Algorithms : 4th Edition : Stacks and Queues
The code is reproduced here and is very elegant:

public Node reverse(Node first) {
    if (first == null || first.next == null) return first;
    Node second = first.next;
    Node rest = reverse(second);
    second.next = first;
    first.next  = null;
    return rest;
}

Implementing stack using queues and vice versa

To implement stack using queues, with two cases : constant insertion time, linear removal time and vice-a-versa, see this stack overflow discussion

To implement a queue using two stacks,

// Basic solution
class Queue
{
    Stack s1; // used as main stack
    Stack s2; // used as stack for temp storage
    
    enqueue(T& t)
    {
        if ( !s1.empty() ) s1.push(t);
        else  s2.push(t);
    }

    T dequeue()
    {
        T t;
        if ( s1.isEmpty() && s2.isEmpty() ) throw Exception();
        return __dequeue(s1,s2);
    }
    T __dequeue(Stack& from, Stack& to) 
    {
        size_t n = from.count();
        if (!n) return __dequeue(to, from);
        move(from, to, n-1);
        t = from.pop();
        move(to, from, n-1);
        return t;
    }
}

// optimized solution : by saving the last operation
class Queue
{
    Stack s1; // used as main stack
    Stack s2; // used as stack for temp storage
    
    enqueue(T& t)
    {
        if ( last_operation == Dequeue ) 
            move( s2,s1);
        s1.push(t);
        last_operation = Enqueue;
    }

    T dequeue()
    {
        if ( s1.isEmpty() && s2.isEmpty() ) throw Exception();
        // if the last operation was dequeue, the required element
        // is already on the temp usage stack s2
        if ( last_operation == Dequeue )
            return s2.pop();

        T t= __dequeue(s1,s2);
        last_operation = Dequeue;
    }
    T __dequeue(Stack& from, Stack& to) 
    {
        size_t n = from.count();
        if (!n) return __dequeue(to, from);
        move(from, to, n-1);
        t = from.pop();
        move(to, from, n-1);
        return t;
    }
}

Also there is a interesting solution in Algorithms and Programming: Problems and Solutions - Page 90

We maintain the following invariant relation: stacks whose bottoms are
put together, form the queue. (In other words, listing all elements of one stack from
top to bottom and then of the other stack from bottom to top, we list all the queue
elements in the proper order.) To add an element to the queue, it is enough to add it to
one of the stacks. To check if the queue is empty, we must check that both stacks are
empty. When taking the first element from the queue, we should distinguish between
two cases. If the stack that contains the first element is not empty, there is no problem.
If that stack is empty, the required element is buried under all the elements of the
second stack. In this case, we move all the elements one-by-one onto the first stack
(their ordering is reversed) and return to the first case.
The number of operations for this step is not limited by any constant. However,
the requirement posed in the problem is still met. Indeed, any element of the queue
can participate in such a process at most once during its presence in the queue.

f(f(n)) = -n

Originally from stackoverflow
While working on this puzzle, became confused, but this can be simplified if we first write the state diagram and then the code. The state diagram should consider odd/even and +ve/-ve numbers.
A simple control flow can be as follows:
A: 1 → 2
B: 2 → -1
C: -1 → -2
D: -2 → 1
E: 1 → 2

Notice that E and A are same.
Once we have this,

if n is +ve:
   if n is odd : return n+1
   if n is even : return -1* (n-1)
else if n is -ve:
   if n is odd : return n-1
   if n is even : return -1 * (n+1)

We get the highest rated solution on stackoverflow.

Sorting and array of 0 and 1's in single pass

Question from Princeton.edu's sorting and searching :

Partitioning. Write a static method that sorts a Comparable array that is known to have at most two different values.

Hint: Maintain two pointers, one starting at the left end and moving right, the other starting at the right end and moving left. Maintain the invariant that all elements to the left of the left pointer are equal to the smaller of the two values and all elements to the right of the right pointer are equal to the larger of the two values.

Solution in python:

"""
Sort an array of 0's and 1's

Loop invariant
[0 0 0 0 0 0 |----unknown-----| 1 1 1 1 1 1]
             i                j
All elements < i are 0
All element > j are 1
elements between i and j are unknown.
"""

a1 = [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1]
a2 = [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
a3 = [ 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ]

def sort_01(a):
    i=0
    j=len(a)-1
    while i < j:
        while i < j and (a[i] < a[j] or a[i]==0): i += 1
        while i < j and a[i] <= a[j]: j -= 1
        if i < j: a[i],a[j] = 0,1
    print(a)

sort_01(a1)
sort_01(a2)
sort_01(a3)

importance of vector::reserve

Not using reserve results in quite some extra work.

struct Foo
{
 static int i ;
 int f;
 Foo():f(i++){ cout << "in ctor:" << i << endl; }
 Foo(const Foo&):f(i++){ cout << "in copy ctor:" << i << endl; }
};
int Foo::i = 1;

void tst_vec()
{
 vector v;
 v.reserve(10);
 Foo f ;
 v.push_back(f);
 v.push_back(Foo());
 v.push_back(Foo());
 cout << "---" << endl;
 Foo& temp = v[0];
}

---

with reserve:
in ctor:2
in copy ctor:3
in ctor:4
in copy ctor:5
in ctor:6
in copy ctor:7
---

without reserve:
in ctor:2
in copy ctor:3
in ctor:4
in copy ctor:5
in copy ctor:6
in ctor:7
in copy ctor:8
in copy ctor:9
in copy ctor:10

virtual destructors and valgrind

Was curious to know the effects of missing a virtual destructor, and ran the program on valgrind:

Valgrind reported a memory leak.

user@ubuntu:~/devel/effective_cpp$ g++ virt_dtor.cpp -ggdb
user@ubuntu:~/devel/effective_cpp$ cat virt_dtor.cpp 
#include 
using namespace std;

class Base{
    public:
    ~Base() { cout << "~Base()" << endl; }
};

class Der: public Base{
    public:
        int* array;
     Der(){ array = new int[10]; }
    ~Der() { cout << "~Der()" << endl; delete[] array; }
};

int main()
{
    Base* b  = new Der;
    delete b;
}
user@ubuntu:~/devel/effective_cpp$ valgrind --leak-check=full ./a.out 
==2791== Memcheck, a memory error detector
==2791== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==2791== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==2791== Command: ./a.out
==2791== 
~Base()
==2791== 
==2791== HEAP SUMMARY:
==2791==     in use at exit: 40 bytes in 1 blocks
==2791==   total heap usage: 2 allocs, 1 frees, 44 bytes allocated
==2791== 
==2791== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==2791==    at 0x4025FE5: operator new[](unsigned int) (vg_replace_malloc.c:299)
==2791==    by 0x80488C8: Der::Der() (virt_dtor.cpp:12)
==2791==    by 0x80487A7: main (virt_dtor.cpp:18)
==2791== 
==2791== LEAK SUMMARY:
==2791==    definitely lost: 40 bytes in 1 blocks
==2791==    indirectly lost: 0 bytes in 0 blocks
==2791==      possibly lost: 0 bytes in 0 blocks
==2791==    still reachable: 0 bytes in 0 blocks
==2791==         suppressed: 0 bytes in 0 blocks
==2791== 
==2791== For counts of detected and suppressed errors, rerun with: -v
==2791== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 19 from 8)

Different types of mutexes

Some of the different types of Mutex:
-- Fair / Unfair Mutex : A mutex which allows access in the order of locking
-- Reentrant : which allows recursive locking, helpful when there are recursive calls in the code. See also man page description of PTHREAD_MUTEX_RECURSIVE
-- Scalable Mutex
-- Sleep or spin : spin is optimal for short waits and sleep for long waits. And also while spining, there is no need for context switch.

Reference : Intel threading building blocks: outfitting C++ for multi-core processor ... By James Reinders, p.114

reversing a string in C++

C++ string does not have reverse member function,
this is how we can do it:

string s("abcdef");
reverse(s.begin(), s.end());

Binary Search of a string

Interesting problem : How can we apply binary search to search a string in a big word file?

We use a suffix array and sort this array. Once sorted, we apply binary search on this array. See Bentley Programming Pearls p.172. See also : Large-scale genome sequence processing By Masahiro Kasahara, Shinichi Morishita, p.56

We can optimize this even further by storing the radix representation of strings (see:Cormen's section in Hashing) and the problem will be reduced to binary search of numbers.

C++ : non-local static object initialization problem

If one global object is directly dependent on another global object, the order of their construction is undefined. The best solution for it, suggested by Scott Meyers is to use singletons : ( see : Scott Meyers "Item 47: Ensure that non-local static objects are initialized before they're used." Effective C++ )

The basis of this approach is the observation that although C++ says next to nothing about when a nonlocal static object is initialized, it specifies quite precisely when a static object inside a function (i.e. a local static object) is initialized: it's when the object's definition is first encountered during a call to that function. So if you replace direct accesses to non-local static objects with calls to functions that return references to local static objects inside them, you're guaranteed that the references you get back from the functions will refer to initialized objects. As a bonus, if you never call a function emulating a nonlocal
static object, you never incur the cost of constructing and destructing the object, something that can't be said for true non-local static objects

Multiple Inheritance : Overriding same named functions in derived.

Technique for overriding same named functions in Base classes in a multiple inheritance: ( See : Item 43 in Effective C++ , see also, Exceptional C++ )

#include < iostream >
using namespace std;

class Base1{
    public:
    virtual int func(){ cout << "base1::func" << endl; }
};

class Base2{
    public:
    virtual int func(){ cout << "base2::func" << endl; }
};

class Der : public Base1, public Base2
{
    public:
    // overrides both Base1, and Base func
    virtual int func() { cout << "der::func" << endl; }
};

/** Using auxillary classes  */
class AuxBase1: public Base1{
    public:
        virtual int base1_func() = 0;
        virtual int func() {return base1_func(); }
};
class AuxBase2: public Base2{
    public:
        virtual int base2_func() = 0;
        virtual int func() {return base2_func(); }
};

class Der2 : public AuxBase1, public AuxBase2
{
    int base1_func() { cout << __func__ << endl; }
    int base2_func() { cout << __func__ << endl; }
    
};

int main()
{
    Der *pd = new Der();
    Base1 *p1 = pd;
    Base2 *p2 = pd;
    p1->func();
    p2->func();
    pd->func();

    Der2 *pd2 = new Der2();
    p1 = pd2;
    p2 = pd2;
    p1->func();
    p2->func();
}

Output :

der::func
der::func
der::func
base1_func
base2_func