How To

There should be a collection of ProgrammerHowTos. A programmer can write one if he wants to share his programming knowledge. Then other programmers who want to learn will have another place to turn to besides the bookstore and the university. These HowTos? could even be placed on a Wiki, although not necessarily this one.

Well, somebody has to start it, so it might as well be me (whoever 'me' happens to be).

Anyone for filling in the blanks?

---

• HowToWiki (you mean how to WalkingTheWiki? sorry about mixing infinitive and gerund)
• HowToWriteaLinkedList? (in what language? varies all over the place depending on that)
• HowToSortaList? (merge sort, probably)
• HowToSearchaSortedList? (if it's a linked list, sequential is your only option)

• HowToMakeThreadsInJava
• HowToSynchronizeThreadsInJava?
• HowToWriteaUnitTest?

---

I just know (or at least I think I know) that somebody will comment on how HowToWriteaUnitTest? should've been listed first... :)

---

I wonder about the page names. At first they jarred me because I'm used to the Linux Documentation Project's convention (http://www.tldp.org/), which is to put the HOWTO last.

On a Wiki it might be more appropriate to omit it entirely, creating page names such as ThreadSynchronizationInJava?. But on this Wiki, some hapless Wikizen might mistake the page as a discussion about thread synchronization rather than a tutorial or reference on it. So how about ThreadSynchronizationInJavaHowTo??

---

All right, here's how to sort a linked list. You need a stack of (linked list, length) pairs, initially empty. You also need a linked list for input. Then you repeat the following:

 done = false;
 repeat until returning something
 { if (the input is empty)
   { if (the stack is empty)
     { return the empty list;
     }
     else if (the stack has one item)
     { pop the stack into x, return x.list
     }
     else /* the stack has more than one item */
     { merge top two lists on stack;
     }
   } else /* the input is not empty */
   { if (the stack has more than one item
         and the top two items on the stack have the same length)
     { merge top two lists on stack;
     }
     else /* either the stack is empty or has one item or the top two items are different lengths */
     { remove the first item from the input, put it in x
       push the list containing only x onto the stack, length 1
     }
   }
 }

Here's how to "merge two lists," call them A and B. They are sorted.

 pop stack into a;
 pop stack into b;
 c.list = merge(a.list,b.list); // pay attention to order of params!
 c.length = a.length + b.length;
 push c onto stack;

The merge function is defined as follows:

 create a new empty list c.
 repeat until returning something
 { if (lists a and b are empty)
   { return c;
   }
   else if (list a is empty)
   { pop first item from b and add to end of c;
   }
   else if (list b is empty)
   { pop first item from a and add to end of c;
   }
   else if (list a's first item is less than list b's first item)
   { pop first item from a and add to end of c;
   }
   else if (list b's first item is less than list a's first item)
   { pop first item from b and add to end of c;
   }
   else /* first items are equal */
   { pop first item from b and add to end of c;
     /* note that this is NOT arbitrary. It has to be b, not a, in
        order to guarantee a stable sort. */
   }
 }

Presto, your list is sorted in O(n log n) time, optimal to within a multiplicative constant.