Archive for the ‘computers’ Category

Custom foreach behaviour in Java using inner classes

Thursday, September 28th, 2006

One of the most widely-anticipated and useful language updates in Java 5 was the introduction of a “foreach” construct, to reduce the amount of boilerplate code which needs to be written when a programmer wants to iterate over all the elements in a collection. Languages such as C# and PHP have had the feature for a long time, and Java programmers were clamouring for it too.

The syntax looks like:

for (element foo : collection) {
    ...
}

To allow your own classes to be iterated over with the foreach construct they must implement the new Iterable interface and thus provide an “iterator()” method to return the appropriate Iterator object.

However, there is a limitation in the current implementation. In some code I was writing I found I had a class which looked like:

public class Foo {
    private List<Integer> intList = new ArrayList<Integer>();
    private List<Float> floatList = new ArrayList<Float>();
}

I wanted the user of Foo to be able to choose to iterate over either the intList or floatList. My first attempt was:

public class Foo implements Iterable<Integer>, Iterable<Float> {
    private List<Integer> intList = new ArrayList<Integer>();
    private List<Float> floatList = new ArrayList<Float>();

    public Iterator<Integer> iterator() {
        return intList.iterator();
    }

    public Iterator<Float> iterator() {
        return floatList.iterator();
    }
}

But it won’t compile! The problem is that you are not permitted to implement the same interface more than once, even if you use a different generic type each time.

I’m not sure why this is, but I guess it has something to do with the requirement to support legacy code without modification. It meant that being able to write:

Foo foo;
for (Integer i : foo) {
    ...
}
for (Float f : foo) {
    ...
}

was impossible.

I thought about this for a day or two until a solution popped into my head (after a few beers, as often happens!). It is possible if we use Java’s support for inner classes. The code isn’t quite as simple, but it’s the best we can do - and the difference to the user is so small that I think it’s a neat solution. The code follows:

public class Foo {
    private List<Integer> intList = new ArrayList<Integer>();
    private List<Float> floatList = new ArrayList<Float>();

    public class Integers implements Iterable<Integer> {
        public Iterator<Integer> iterator() {
            return intList.iterator();
        }
    }

    public class Floats implements Iterable<Float> {
        public Iterator<Float> iterator() {
            return floatList.iterator();
        }
    }
}

The user code looks like:

Foo foo;
for (Integer i : foo.new Integers()) {
    ...
}
for (Float f : foo.new Floats()) {
    ...
}

I’m quite pleased with this solution. I wouldn’t go as far as to call it a design pattern, but it certainly allows us to work around one of the limitations of Java generics.

Pointer Hurdles

Wednesday, March 16th, 2005

At Joel On Software there’s a great article about how to interview for programming jobs, which includes getting the candidate to write some code, on paper, in the interview.

For programming questions, I ask candidates to write a small function in C. Here are some typical problems I would ask:

  1. Reverse a string in place
  2. Reverse a linked list
  3. Count all the bits that are on in a byte
  4. Binary search
  5. Find the longest run in a string
  6. atoi
  7. itoa (great, because they have to use a stack or strrev)

And here are some of the things he suggests looking out for:

  • Is their function fast? Look at how many times they call strlen. I’ve seen O(n^2) algorithms for strrev when it should be O(n), because they are calling strlen again and again in a loop.
  • Do they use pointer arithmetic? This is a good sign. Many “C programmers” just don’t know how to make pointer arithmetic work. Now, ordinarily, I wouldn’t reject a candidate just because he lacked a particular skill. However, I’ve discovered that understanding pointers in C is not a skill, it’s an aptitude. In Freshman year CompSci, there are always about 200 kids at the beginning of the semester, all of whom wrote complex adventure games in BASIC for their Atari 800s when they were 4 years old. They are having a good ol’; time learning Pascal in college, until one day their professor introduces pointers, and suddenly, they don’t get it. They just don’t understand anything any more. 90% of the class goes off and becomes PoliSci majors, then they tell their friends that there weren’t enough good looking members of the appropriate sex in their CompSci classes, that’s why they switched. For some reason most people seem to be born without the part of the brain that understands pointers. This is an aptitude thing, not a skill thing – it requires a complex form of doubly-indirected thinking that some people just can’t do.

I totally agree with this: pointers and pointer arithmetic represent a specific level of skill that allow you to say confidently either “this person has no hope as a programmer” or “this person gets it“.

However, I think you can extend this idea further. I’ve found that there’s a second hurdle, beyond which lie the really good programmers. That hurdle is function pointers.

There’s something about function pointers that many otherwise-good programmers just don’t get. Ask them to define and initialise an array of function pointers to factory methods, and index into the array to instantiate an instance of the appropriate type, and they’ll be totally lost. They just won’t get it. They’ll write reams of bug-free procedural code when a simple function pointer would have saved them hours, and made their code vastly more maintainable and extensible.

SCO vs IBM Summary

Wednesday, March 16th, 2005

Right on cue, just as I was starting to lose track of where we’re up to, Groklaw produces a lovely Summary of SCO vs IBM.

(It’s still causing much amusement in the office).

Object Oriented C

Tuesday, March 15th, 2005

An excellent article about how to use encapsulation and polymorphism in C programs.

Note that these techniques are basically what the first C++ compilers used (they were purely preprocessors which generated C code). Similar techniques are also used in parts of Linux (such as the filesystems subsystem).

Crazy crazy stuff

Thursday, December 23rd, 2004

This is the (true) story of how Graphing Calculator 1.0 made it into MacOS.

Automounting SMB filesystems using autofs

Wednesday, December 22nd, 2004

Because I just know I’m going to need this again in the future:

In /etc/auto.master:

/misc /etc/auto.misc –timeout=60

In /etc/auto.misc:

drive -fstype=smbfs,credentials=/etc/auto.smbcredentials ://host/share

In /etc/auto.smbcredentials:

username=username
password=xxxxxxxxx

Then…

# service autofs restart

and cding to /misc/drive should automount \host\share.

iMac G5

Tuesday, August 31st, 2004

I’ve never been a big Mac fan (they don’t really appeal to the hacker instinct in me), but this is quite, quite sexy.

What I Want

Thursday, August 12th, 2004

Quite often, when I’m browsing the web, I’ll stay at the same site for quite a long time, clicking “next” successively to get to the next page of some online article. An example of this is at Peter Norvig’s Design Patterns site, where he has the slides from a talk he has given online. I was reading this site earlier.

There are 76 slides in this talk.

When I got to the end, I wanted to return to the site I was at previously, which had linked me to Peter’s site in the first place. What were my options? Clicking my “back” button 76 times? Even with mouse gestures that didn’t appeal. Luckily Firefox has a drop-down menu that allows me to skip back in chunks of ten, but even so, it took me 8 clicks to return to where I was before.

I want a “super-back” feature. This shouldn’t be too difficult. Basically, when I hold down Shift (or whatever) and click “back”, it should jump to the last page I was viewing outside the current domain. So, since Peter’s site is at norvig.com, my “super-back” would jump back 76 pages to the first page in my history not hosted at norvig.com.

I think this is very simple, and a good idea.

Will someone write me a Firefox extension that does this?

Scaremongering

Thursday, August 12th, 2004

*sigh* Stories like this are really, really, counterproductive.

Here is the list of security issues fixed in SP2. These are real issues, many with exploits in the wild:

  • MS04-025 (867801) - Cumulative Security Update for Internet Explorer
  • MS04-024 (839645) - Vulnerability in Windows Shell Could Allow Remote Code Execution
  • MS04-023 (840315) - Vulnerability in HTML Help Could Allow Code Execution
  • MS04-022 (841873) - Vulnerability in Task Scheduler Could Allow Code Execution
  • MS04-018 (823353) - Cumulative Security Update for Outlook Express
  • MS04-016 (839643) - Vulnerability in DirectPlay Could Allow Denial of Service
  • MS04-015 (840374) - Vulnerability in Help and Support Center Could Allow Remote Code Execution
  • MS04-014 (837001) - Vulnerability in the Microsoft Jet Database Engine Could Allow Code Execution
  • MS04-013 (837009) - Cumulative Security Update for Outlook Express
  • MS04-012 (828741) - Cumulative Update for Microsoft RPC/DCOM
  • MS04-011 (835732) - Security Update for Microsoft Windows
  • MS04-007 (828028) - ASN.1 Vulnerability Could Allow Code Execution
  • MS04-004 (832894) - Cumulative Security Update for Internet Explorer
  • MS04-003 (832483) - Buffer Overrun in MDAC Function Could Allow Code Execution
  • MS03-049 (828749) - Buffer Overrun in the Workstation Service Could Allow Code Execution
  • MS03-048 (824145) - Cumulative Security Update for Internet Explorer
  • MS03-045 (824141) - Buffer Overrun in the ListBox and in the ComboBox Control Could Allow Code Execution
  • MS03-044 (825119) - Buffer Overrun in Windows Help and Support Center Could Lead to System Compromise
  • MS03-043 (828035) - Buffer Overrun in Messenger Service Could Allow Code Execution
  • MS03-041 (823182) - Vulnerability in Authenticode Verification Could Allow Remote Code Execution
  • MS03-040 (828750) - Cumulative Patch for Internet Explorer
  • MS03-039 (824146) - Buffer Overrun in RPCSS Service Could Allow Code Execution
  • MS03-034 (824105) - Flaw in NetBIOS Could Lead to Information Disclosure
  • MS03-032 (822925) - Cumulative Patch for Internet Explorer
  • MS03-030 (819696) - Unchecked Buffer in DirectX Could Enable System Compromise
  • MS03-027 (821557) - Unchecked Buffer in Windows Shell Could Enable System Compromise
  • MS03-026 (823980) - Buffer Overrun in RPC Interface Could Allow Code Execution
  • MS03-024 (817606) - Buffer Overrun in Windows Could Lead to Data Corruption
  • MS03-023 (823559) - Buffer Overrun in HTML Converter Could Allow Code Execution
  • MS03-021 (819639) - Flaw in Windows Media Player May Allow Media Library Access
  • MS03-020 (818529) - Cumulative Patch for Internet Explorer
  • MS03-018 (811114) - Cumulative Patch for Internet Information Service
  • MS03-015 (813489) - Cumulative Patch for Internet Explorer
  • MS03-014 (330994) - Cumulative Patch for Outlook Express
  • MS03-013 (811493) - Buffer Overrun in Windows Kernel Message Handling Could Lead to Elevated Privileges
  • MS03-010 (331953) - Flaw in RPC Endpoint Mapper Could Allow Denial of Service Attacks
  • MS03-008 (814078) - Flaw in Windows Script Engine Could Allow Code Execution
  • MS03-007 (815021) - Unchecked Buffer in Windows Component Could Cause Server Compromise
  • MS03-005 (810577) - Microsoft Security Bulletin MS03-005
  • MS03-004 (810847) - Cumulative Patch for Internet Explorer
  • MS03-001 (810833) - Unchecked Buffer in Locator Service Could Lead to Code Execution
  • MS02-072 (329390) - Unchecked Buffer in Windows Shell Could Enable System Compromise
  • MS02-071 (328310) - Flaw in Windows WM_TIMER Message Handling Could Enable Privilege Elevation
  • MS02-070 (329170) - Flaw in SMB Signing Could Enable Group Policy to be Modified
  • MS02-068 (324929) - Cumulative Patch for Internet Explorer
  • MS02-066 (328970) - Cumulative Patch for Internet Explorer
  • MS02-063 (329834) - Unchecked Buffer in PPTP Implementation Could Enable Denial of Service Attacks
  • MS02-062 (327696) - Cumulative Patch for Internet Information Service
  • MS02-055 (323255) - Unchecked Buffer in Windows Help Facility Could Enable Code Execution

People should apply this NOW. Stories spreading FUD about it are irresponsible.

Paul Graham

Monday, August 2nd, 2004

Paul Graham is a very clever person. He was the person who first suggested using Bayesian techniques to filter spam, and consequently I love him, as he keeps my spam box nice and full.

He’s also an excellent writer, and he has a new article up about defining what makes a great hacker.