Category Archives: Personal Computers

Ha! I now have a trivial python program the works interactively! momdad.py:


“””
“””

import os

print “os.listdir(os.getcwd())”
print os.listdir(os.getcwd())

for fname in os.listdir(os.getcwd()):
print fname
text=open(fname).read()
print “text.count( hi mom )”
print text.count(‘hi mom’)

Link

A philosophic reason to sets pointers to NULL after free’ing them.


A philosophic reason to sets pointers to NULL after free’ing them.

On reflection, I think I got this one right, and I kinda like it! I have experienced other people’s double-free errors, surprisingly, but the value of crashing-on-access-via-null is persuasive to me. Making double-free happen silently and without error is a small cost for positively crashing on a rogue access through a freed pointer.

Trending up: Windows7, Agile Methodologies, Scrum, Python. Everything else? Down!


Linked-in are now listing ala-carte qualifications which one can endorse one’s acquaintances on, or be endorsed by them. No surprise, 20 people say I’m good at “hardware”, which is my highest endorsement. What I want to draw your attention to here is that if you hover your pointer over each of the possible qualifications, Linked-in will show you a working definition and the year-to-year trend on people who say they do-have-know-practice-are-qualified-in the specific item.

Not so surprising, people saying they know ‘hardware’ are down year on year… also C, C++, software engineering, Perforce, customer support, regression test, unit test, and so forth. VMware is 0% – neither up nor down over last year.

Agile Methodologies are up, Windows 7 is way-up, Python is up, Scrum is up. The other 44 categories, on my list, not including VMware at 0 and Windows 8 which doesn’t have a year on year trend, are down.

So, among people who list qualifications similar to mine, the majority and growth area are Python users, on Windows 7, employing Scrum and Agile project management methods.

Your choice whether that’s:

a) what everyone wants;

b) what people looking for work think they need;

c) some cross section of professionals on Linked-in.

I think its worth noting in passing, but not worth a lot of study. But it is a curiosity.

An example that pleased me: The difference between an abstract class and an interface, in Java:


Here’s the punch line:

In Java, Prussia can extend (“be a”) one of the super-classes, Holy, Roman or  Empire, but only one. Prussia can implement the other two as interfaces, but only with methods and fields uniquely its own. If Prussia is to be Holy, be Roman and be an Empire, the strictly hierarchical relationship of those three super-classes has to be worked out separately and in detail, in advance. I can only imagine Herr von Bismark would approve.

 

And the whole magilla:
1) What is the difference between an interface and an abstract class?

An abstract class defines data (fields) and member functions but may not, itself, be instantiated. Usually, some of the methods of an abstract class are abstract and expected to be supplied by a sub-class, but some of the methods are defined.  Unless they are final, they can be overridden, and they can always be overloaded. Private parts of an abstract super class, for example, data, are not available to a subclass, so access methods (public or protected) must be used by the subclass. An abstract superclass is “extended” by a subclass. A given subclass may only extend one super-class, but a super-class may extend another super-class, in a hierarchy. (This avoids the complexities/difficulties of multiple inheritance in C++)

An interface is a proper subset of an abstract class, but has a different scope and use. An interface has ONLY abstract member functions and static, final, fields, aka constants. Any subclass has to provide all the variable fields and code which implements an interface. The implementing class cannot override the interface’s member signatures – the signatures are what the interface *is*. It is possible to overload an interface’s signatures, adding or subtracting variables, changing return or variable types, but the overloads do not satisfy the requirements of the interface. The implementing class(s) must contain actual member functions to satisfy all of the signatures in the interface, because there is no default, no code in the interface.  As used above, a given class ‘implements’ an interface, it does not ‘extend’ it. These limitations to an interface allow a given class to implement more than one, which retains most of the utility of multiple inheritance without, as it were, opening Plethora’s bag. (grin)

For example: In Java, Prussia can extend (“be a”) one of the super-classes, Holy, Roman or  Empire, but only one. Prussia can implement the other two as interfaces with methods and fields uniquely its own. If Prussia is to be Holy, be Roman and be an Empire, the strictly hierarchical relationship of those three super-classes has to be worked out separately and in detail, in advance. I can only imagine Herr von Bismark would approve.

Escape (‘\’) your “\” (backslash) characters when Python writes paths for Windows…


When using Python to prepare strings For Windows, always escape ‘\’ your “\” (backslash) characters in a path name. So ‘\\’ everywhere. It looks like a double ‘\’ but the first one is really “escape” and the second character is interpreted as a literal, not, in this case, as ‘escape’…

What am I talking about??

If your Python program will create file path names for Windows computers, you need to be extra thoughtful as you enter string constants for them.

For example, consider the string "blather\pather\gather"
Give that to the Python Interpreter, and it will show you how it is understood by Python:

>>>
>>> "blather\pather\gather"
'blather\\pather\\gather'
>>>

See what happedened to “blather\pather\gather”?
Python put an escape back slash before each of the (presumably) literal back slashes. Its easy to see if you line them up:

"blather\pather\gather"
'blather\\pather\\gather'

The string delimiters have changed too- python gives ‘ and ” the same meaning, defaults to ‘ and requires them to be used in pairs. ” is an empty string, “” is an empty string, ‘” opens a quoted string inside a quoted string. Better not close it backwards: “”” is an empty string. “‘”‘ is missing a close “.

So far, so good. You might think Python will understand back slashes in things you identify as strings and respect them. That’s nice.

Change the string to
"blather\rather\ather"
>>>"blather\rather\x07ther"

What’s that?? Turns out that Python recognizes “\r” as (carriage return), “\n” a newline and “\t” as a tab. And \a as (control)a, with is slightly startling. But not \G or \g as “bell”…

So they’re compound characters, and they get issued without escapes being added. Why? I don’t know. But I do know that putting an excape backslash before the delimiter backslash results in the text being left alone, and written out exactly the same. And when it goes to Windows, Windows strips off the first backslash and correctly interprets the second one.

Here’s an advantage for Python, as my friend James points out. You can just look at what it does and how it sees things. The realization I’m reporting started wth a Python script trying to call a Windows .bat script… it worked well for some .bat scripts and didn’t work for others. ?!?!?!

Searching for apples and oranges, using grep.


Not using grep? Its a step up from sorting and cutting and pasting in spreadsheets. You will feel, briefly, omniscient, when you use it to solve some problem that’s been bugging you. Here’s my latest:

You care about two keywords in a file- apples and oranges, and you also care about about their relative positions, for whatever reason. So grepping for each, separately, is nice, but you’d really like to grep for one OR the other.

Did I mention this was grep?

grep -i ‘apple\|orange’ *filename.ext*

The -i makes it case-insensitive, just like you’d want on a first pass. The “|” vertical bar is a familiar OR operator, and the only tricky parts are to a) put the whole thing in a single set of single quotes- the two words and the operator are a single syntactic unit, and b) use a back-slash to mark the vertical bar as an operator and not just a literal vertical bar.

I used apple and orange in the title because they are canonically “unrelated” things, but where this technique is really useful is when the unrelated things are in orthagonal kinds: fruits and deserts. If you’ve got your recipes filed or a cookbook on line, grep -i ‘pie\|apple’ will produce all the refernces to either. Pies involving apples will be found where ‘apple’ has ‘pie’ both above and below… As a human, you have a right to do that last bit in your head, the sorting out that we gatherer-hunters are bred for.

There’s always something more to learn… or remember!


Some Mac OS-X tidbits I picked up or recalled. I realize this seems somewhat dim of me…

1) Closing the window is NOT the same as quitting the application. For one thing, the application is still running, as you can see from the Mac’s menu bar. Also see the Activity Monitor, or ps -ef in a terminal window.

This small detail saw me fumbling through the latest iTunes update- I’ve got a dialog box asking me to exit the app and i’m thinking, “Gee, I closed the window, what does it want?” Well, of course, what it wants is for me to select “iTunes” in the menu bar, once I get the menu into iTunes mode, and slide the pointer down to select “Quit iTunes”… how is it I forgot that? Well, I remember again!

2) Force your Mac to boot from the cd/dvd? Hold down “C” while (re)booting. Similar to forcing a system to disgorge the cd/dvd by holding down the mouse. Of course, you can also set the boot disk via System Preferences, Startup Disk, to the Super Drive.

Recursion III, using Java


Here’s a Java example of the classic recursion/tree/web traversal. Note that this uses an array of other nodes, not just Left and Right, so you can make n-link webs as well as proper trees using this example.

The method interMed() is used to avoid having to make the data structures static- there is much I have yet to learn about Java! But I can manage this, and that feels pretty good!

/*
recurse.java

Recursive tree/web traversal, in Java. No explicit pointers, so I state that
the array of pointers to nodes is an array of nodes, and treat it as such.
Is it really pointers if I believe it is but can't see them? Its like String
Theory...

Original 11:58am 4/21 Bill4

*/

import java.util.ArrayList;

public class recurse {

public class node { String name; ArrayList kids; };
public class leveledName { String name; int level; };

ArrayList nLs = new ArrayList ();

public void recur ( node n, int level ) {

// System.out.println( "recur " + n + " level " + level );
leveledName lN = new leveledName();
lN.name = n.name;
lN.level= level;
nLs.add( lN );

for ( int i = 0; i < n.kids.size(); i++ ) { // better way to do this?

recur( n.kids.get(i), level + 1 );

} // for int i...

} // recur function

public void interMed() {

node Q = new node(); Q.name = "Q";
Q.kids = new ArrayList ();
// System.out.println( Q );

node S = new node(); S.name = "S";
S.kids = new ArrayList ();
// System.out.println( S );

node T = new node(); T.name = "T";
T.kids = new ArrayList ();
// System.out.println( T );

node N = new node(); N.name = "N";
N.kids = new ArrayList (); N.kids.add(Q);
// System.out.println( N );

node P = new node(); P.name = "P";
P.kids = new ArrayList (); P.kids.add(S); P.kids.add(T);
// System.out.println( P );

node M = new node(); M.name="M";
M.kids = new ArrayList (); M.kids.add(N); M.kids.add(P);
// System.out.println( M );

recur( M, 0 );

int maxLevel = 0;
for ( int i = 0; i maxLevel) {
maxLevel = ((nLs.get(i)).level );
} // if ...
} // for ...

for (int j = maxLevel; j > -1; j-- ) {
// System.out.println( "j " + j );
for ( int i = 0; i < nLs.size(); i++ ) {
// System.out.println( "j " + j + " i " + i );
if ( j == (nLs.get(i)).level ) {
System.out.printf( "%s %d \n", (nLs.get(i)).name,
(nLs.get(i)).level );
}
} // for i...
} // for j...

} // fn interMed

public static void main ( String args[] ) {

recurse r = new recurse();
r.interMed();

} // main

} // class recurse

Recursion II, K&R C, worked out in advance


Earlier I posted the C++ solution to a tree/web traversal programming problem. Here’s the C solution, including a vector-like array for pointers to children, so one doesn’t have to hard code left, right, etc. In this case Max Children is 5 but it can be any number.  A sample output is included below

/* recursion.C */
/* Follow-up to _ recursion problem, web prowling question at _  */

/* input:
(M)
|   \
(N)  (P)
|  \    \
(Q) (S)  (T)

(3 level b tree, M has two kids, N and P, and N has two kids, Q and S.  P has one child – T.)

output:
Q, S, T, N, P, M

*/

#include <stdio.h>
#include <stdlib.h>

#define MAX_NAME_N_LEVEL 1000
#define MAX_KIDS  5

/* Structure in which the input data arrives: */

struct node {
char name;  struct node *(kids[MAX_KIDS]);
};

/* Structure the result vector (array) is built from: */
struct nameNLevel  {
char name;   int level;
};

/* Global scope variables for putting struct node + name data, as discovered in recursive part. */

struct nameNLevel* nsNLs[ MAX_NAME_N_LEVEL ];
int nmLvlCount = 0;

/*
* Synopsis:  void recur( int level, struct node* n ) {
* args:
*    int level
*    struct node* n
* returns: void, BUT puts a record into nsNLs[] and increments nmLvlCount.
* The record contins a node name and the level it was found at.
* Apr 5, 2011  Bill Abbott
*/

void recur( int level, struct node* n ) {
/* first make the new record in the list of names and levels */

struct nameNLevel* thisNmNLvl = (struct nameNLevel*) malloc( sizeof( struct nameNLevel));    /* allocate name string & level num struct */
if (0 == thisNmNLvl ) { /* allocation failed! */
printf(“Memory allocation failed at level %d, struct node %s, go ahead and crash!\n”, level, n->name );
}

thisNmNLvl->level = level;            /* fill in level, */
if ( n != 0 ) thisNmNLvl->name = n->name;             /* 1 char name… */
nsNLs[ nmLvlCount++ ] = thisNmNLvl;

printf(“\n”);
printf(“recur level: %d    n: 0x%x   name: %c\n”, level,  n, n->name );
/*
printf(“(long)*(n > kids)  :  0X%x \n”, (long)*(n->kids) );
printf(“(long)(n > kids[0]):  0X%x \n”, (long)(n->kids[0]) );
*/
/* those two should be the same… */

if ( 0 != n->kids ) {  /* this pointer should always have an array where it points, but just in case… */

int j;
for (j=0; j<3; j++ ) {
printf(” (n > kids[%d]) = 0x%x  “, j, (n->kids[j]) );
if ( n->kids[j] ) { printf(”   >name = %c\n”, (n->kids[j])->name ); }
else { printf( “\n” ); }
}   /* ha! This was the hardest part… */
}

int i;
/* now look for any child nodes an call recursivly for them… */
for ( i = 0; n->kids[i] != 0; i++ ) {
recur(level+1,  n->kids[i]);
} /* for int it… */

} /* recur */

/*
* Synopsis: void passThrough( struct node* n )
* args:
* returns:
* no return value. creates and outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

void passThrough( struct node* n ) {

int i;
for( i = 0; i< MAX_NAME_N_LEVEL; i++ ) { /* not strictly required…*/
nsNLs[ i ] = 0;  // set ’em all to null to start with.
} /* for i… */

int level = 0;
nmLvlCount = 0;

recur( level, n );

int maxLevel = 0;
for (i = 0; i < nmLvlCount; i++ ) {
if ( nsNLs[ i ]->level > maxLevel ) {
maxLevel = nsNLs[ i ]->level;
} /* if…*/
} /* for int i… */

/*    printf(“\nlevel  %d    nmLvlCount  %d     maxLevel %d \n”, level, nmLvlCount, maxLevel ); */

int lvl;
printf(“\n”);
for ( lvl = maxLevel; lvl >= 0; lvl– ) {  // this is serious, collect and print, all done.
for ( i = 0; i < nmLvlCount; i++ ) {
if (nsNLs[i]->level == lvl ) {
printf( “%c, “,  nsNLs[i]->name );
}
}
} /* for int i… */
printf(“\n”);

for ( lvl = maxLevel; lvl >= 0; lvl– ) {  // this is serious, collect and print, all done.
for ( i = 0; i < nmLvlCount; i++ ) {
if (nsNLs[i]->level == lvl ) {
printf( “%d, “, nsNLs[i]->level );
}
}
} /* for int i… */
printf(“\n”);

} /* passThrough */

/*
* Synopsis: int main( int argc, char* argv[] )
* args:
* int        argc    count of command line arguments
* char*    argv[]    vector of zero-terminated arrays of char containing command line args
* returns:
* no return value. creates a tree of nodes, outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Apr 7, 2011  Bill Abbott
*/

int main( int argc, char* argv[] ) {

/* 3 level b tree:
* M has two kids, N and P, and
*    N has two kids, Q and S.
*        Q has no kids
*        S has no kids
*    P has one child – T.
*        T has no kids
*/

char nameIt[] =”malloc “;
char theRest[] = ” failed. Out of memory\n”;

struct node* T = malloc( sizeof(struct node));
if ( 0 == T ) { printf(“%s T %s”, nameIt, theRest ); return( 0 ); }
T->name = ‘T’;
T->kids[MAX_KIDS] = (struct node*) malloc(sizeof(struct node*) * MAX_KIDS);
if ( 0 == T->kids ) { printf(“%s T->kids %s”, nameIt, theRest); return( 0 ); }
T->kids[0] = (void*) 0;
T->kids[1] = (void*) 0;
T->kids[2] = (void*) 0;

/*
printf(“\n”);
printf(“(long)(T > kids) = 0X%x   \n”,  (long)*(T->kids) );
if ( (T->kids[0]))  printf(“*(T > kids[0]) = %c\n”,   *(T->kids[0]) );
if ( (T->kids[0]))  printf(“( (T > kids[0]) >name = 0x%x  %c\n”,   (T->kids[0])->name, (T->kids[0])->name );
if ( (T->kids[1]))  printf(“( (T > kids[1]) >name = 0x%x  %c\n”,   (T->kids[1])->name, (T->kids[1])->name );
if ( (T->kids[2]))  printf(“( (T > kids[2]) = 0x%x\n”,   (T->kids[2]) );
*/

struct node* S = malloc( sizeof(struct node));
if ( 0 == S ) { printf(“%s S %s”, nameIt, theRest ); return( 0 ); }
S->name = ‘S’;
S->kids[MAX_KIDS] = malloc( sizeof( struct node*) * MAX_KIDS);
if ( 0 == S->kids ) { printf(“%s S->kids %s”, nameIt, theRest); return( 0 ); }
S->kids[0] = (void*) 0;
S->kids[1] = (void*) 0;
S->kids[2] = (void*) 0;

struct node* Q = malloc( sizeof(struct node));
if ( 0 == Q ) { printf(“%s Q %s”, nameIt, theRest ); return( 0 ); }
Q->name = ‘Q’;
*(Q->kids) = malloc(sizeof(struct node*) * MAX_KIDS);
if ( 0 == Q->kids ) { printf(“%s Q->kids %s”, nameIt, theRest); return( 0 ); }
Q->kids[0] = (void*) 0;
Q->kids[1] = (void*) 0;
Q->kids[2] = (void*) 0;

struct node* P = malloc( sizeof(struct node));
if ( 0 == P ) { printf(“%s P %s”, nameIt, theRest ); return( 0 ); }
P->name = ‘P’;
P->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == P->kids ) { printf(“%s P->kids %s”, nameIt, theRest); return( 0 ); }
P->kids[0] = T;
P->kids[1] = (void*) 0;
P->kids[2] = (void*) 0;

struct node* N = malloc( sizeof(struct node));
if ( 0 == N ) { printf(“%s N %s”, nameIt, theRest ); return( 0 ); }
N->name = ‘N’;
N->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == N->kids ) { printf(“%s N->kids %s”, nameIt, theRest); return( 0 ); }
N->kids[0] = Q;
N->kids[1] = S;
N->kids[2] = (void*) 0;

struct node* M  = malloc( sizeof(struct node));
if ( 0 == N ) { printf(“%s N %s”, nameIt, theRest ); return( 0 ); }
M->name = ‘M’;
M->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == M->kids ) { printf(“%s M->kids %s”, nameIt, theRest); return( 0 ); }
M->kids[0] = N;
M->kids[1] = P;
M->kids[2] = (void*) 0;

/*  printf(“\n”);
printf(“(long)(M > kids) = 0X%x   \n”,  (long)*(M->kids) );
printf(“*(M > kids[0]) = %c\n”,   *(M->kids[0]) );
printf(“( (M > kids[0]) >name = 0x%x\n”,   (M->kids[0])->name );
printf(“( (M > kids[1]) >name = 0x%x\n”,   (M->kids[1])->name );
printf(“( (M > kids[2]) = 0x%x\n”,   (M->kids[2]) );
*/

passThrough( M );

return( 1 );

} // main…

Macintosh-6:interview Bill4$ cc recursion.c
Macintosh-6:interview Bill4$ a.out

recur level: 0    n: 0x100260   name: M
(n > kids[0]) = 0x100220     >name = N
(n > kids[1]) = 0x1001e0     >name = P
(n > kids[2]) = 0x0

recur level: 1    n: 0x100220   name: N
(n > kids[0]) = 0x1001a0     >name = Q
(n > kids[1]) = 0x100160     >name = S
(n > kids[2]) = 0x0

recur level: 2    n: 0x1001a0   name: Q
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0

recur level: 2    n: 0x100160   name: S
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0

recur level: 1    n: 0x1001e0   name: P
(n > kids[0]) = 0x100120     >name = T
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0

recur level: 2    n: 0x100120   name: T
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0

Q, S, T, N, P, M,
2, 2, 2, 1, 1, 0,
Macintosh-6:interview Bill4$

Recursion, working it out in advance


In a recent pair of interviews, I was asked tree data structure questions, and I flubbed the first one. Hacking at a function that received a pointer to a node and that I needed to use as the launching point for recursion, not the recursive bit itself. Not pretty. NEXT time, I managed to gather up my wits, with a bit of help from my interviewer, Jim Gill, I managed to thread the needle and there it was, a recursive operation that worked. Sho-‘nuf!  That original is at the bottom of this post- a complete, working version, follows this introduction. Its about 180 lines, with a lot of white space.

And here’s the deal. You can’t make  a sensible recursive routine by simply getting the pointer and recalling that top level routine. YES recursion needs something that takes a pointer to node, and yes,  you call it with a child of the original node. But there’s more to it. A non-recursive superstructure which supports a recursive heart.

So here’s a complete, working, version, that compiles and runs using “gcc” on Mac OS 10.5.8. It takes a bit more than what I started with. “C” and other versions will follow, as separate postings.

Macintosh-6:interview Bill4$ cat recursion_v.cpp
/* recursion_v.cpp */
/* Follow-up to ___ recursion problem with Jim Gill, web prowling question at ____ */

/* input:
(M)
|   \
(N)  (P)
|  \    \
(Q) (S)  (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S.  P has one child – T.)

output:
Q, S, T, N, P, M

*/

#include <iostream>
#include <vector>

/* Structure in which the input data arrives: */

struct node {
std::vector <node*> children;  std::string name;
};

/* Structure the result vector (array) is built from: */
struct nameNLevel  {
std::string name;   int level;
};

/*
* Synopsis: void recur( node* n, int level, std::vector* nsNLs )
* args:
* node*    n     this node, which has a name, may have children
* int        level    number of steps down the tree
* std::vector    nsNLs   pointer to the vector of node-name, level structs we’ll want to report
* returns:
* no return value. Node name and level are put into the vector of nameLevel structs.
* Mar 27, 2011  Bill Abbott
*/

void recur( node* n, int level, std::vector <nameNLevel>* nsNLs ){

/* To collect additions, nsNLs vector must be passed as a pointer! */
/* Unlike an array in C, an std::vector isn’t passed as a pointer automatically! */
nameNLevel* nNL = new nameNLevel;
nNL->name = n->name;
nNL->level = level;
nsNLs->push_back( *nNL );

int vecIdx = nsNLs->size() – 1;

//    std::cout << nsNLs->size() << ”  ” << vecIdx << ”    “;
std::cout << (*nsNLs)[ vecIdx ].level << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name.size() << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name.c_str() << ”    “;

std::cout << (nsNLs->back()).name << ”  ” << (nsNLs->back()).level << ”  ” << n->name << ”  ” << level << ”  “;
std::cout << nsNLs->size() << ”  ” ;
std::cout << n->children.size() << ”  ” << (0 != n->children.size()) << “\n”;
if ( 0 != n->children.size()) {   /* there are children */
for (int childCount =0; childCount < ( n->children.size()); childCount++ ){
recur(  n->children[childCount], level+1, nsNLs ); /* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!=  */

} /* recur *

/*
* Synopsis: void passThrough( node* n )
* args:
* node*    n     this node, which has a name, may have children
* returns:
* no return value. creates and outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

void passThrough( node* n ) {
std::vector namesNLevels;
int level = 0;

recur( n, level, &namesNLevels );

std::cout<< namesNLevels.size()  << ”  ” << “\n”;

int maxLevel = 0;
for (int i=0; i < namesNLevels.size(); i++ ) {
std::cout<< maxLevel << ”  ” << i << “\n”;
if (namesNLevels[i].level > maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */

/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */

for (level=maxLevel; level >= 0; level–){
for (int i=0; i < namesNLevels.size(); i++ ) {
if (namesNLevels[i].level == level){
std::cout << namesNLevels[i].name <<  ” “;
} /* if (namesNLevels…) */
} /* for i */
} /* for level */

printf( “\n”);

}

/*
* Synopsis: int main( int argc, char* argv[] )
* args:
* int        argc    count of command line arguments
* char*    argv[]    vector of zero-terminated arrays of char containing command line args
* returns:
* no return value. creates a tree of nodes, outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

int main( int argc, char* argv[] ) {

/* 3 level b tree:
* M has two children, N and P, and
*    N has two children, Q and S.
*        Q has no children
*        S has no children
*    P has one child – T.
*        T has no children
*/

node* T = new node;
T->children.clear();
T->name = “T”;

node* S = new node;
S->children.clear();
S->name = “S”;

node* Q = new node;
Q->children.clear();
Q->name = “Q”;

node* P = new node;
P->children.push_back(T);
P->name = “P”;

node* N = new node;
N->children.push_back(Q);
N->children.push_back(S);
N->name = “N”;

node* M = new node;
M->children.push_back(N);
M->children.push_back(P);
M->name = “M”;

passThrough( M );

return( 1 );

————- Example output, with my debug couts—————-

Macintosh-6:interview Bill4$ c++ recursion_v.cpp
Macintosh-6:interview Bill4$ a.out
0  M  1  M    M  0  M  0  1  2  1
1  N  1  N    N  1  N  1  2  2  1
2  Q  1  Q    Q  2  Q  2  3  0  0
2  S  1  S    S  2  S  2  4  0  0
1  P  1  P    P  1  P  1  5  1  1
2  T  1  T    T  2  T  2  6  0  0
6
0  0
0  1
1  2
2  3
2  4
2  5
Q S T N P M
Macintosh-6:interview Bill4$

————————– Here’s how this started:——————–

Ok- it was whiteboard code and didn’t compile. I’m working on that. Staring with std::vector blahblah  which seems like some really kewl Java/C++ library good stuff. What Kernighan and Ritchie were hoping for.

input:
(M)
|     \
(N) (P)
|     \    \
(Q) (S) (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S.  P has one child – T.

output:
Q, S, T, N, P, M

typedef struct node {
std::vector <node*> children;  std::string name;
}

typedef nameNLevel {
std::string name;   std::int level;
}

void passThrough( node* n ) {
std::Array namesNLevels;
int level = 0;

recur( n, level, namesNLevels );

int maxLevel = 0;

for (int i=0; i
if (namesNLevels[i].leve l> maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */

/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */

for (level=0; level =<maxLevel; level++){
for (i=0; i<
if (atoi(namesNLevels[i].name) == level){  printf( “%s “, namesNLevels[i].name } /* longer but more robust */
} /* for i */
} /* for level */

printf( “\n”);

}

void recur( node* n, integer level, std::Array nsNLs ){
/* its an array, gets passes as a pointer anyhow */
nsNLs.pushback( new nameNLevel( n->name, level));

if ( 0 != n->children.count()) {   /* there are children */
for (int childCount =0; childCount < ( n->children.count()); childCount++ ){
recur(  n->children[childCount], level+1, nsNLs );
/* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!=  */

}

A nice page at IBM regarding recursion:

http://www.ibm.com/developerworks/linux/library/l-recurs.html#

Good stuff!