Calculating SHA-1 sums in Java

Java has functionality for calculating SHA-1 and MD5 checksums but not for displaying them as the 40-char hex strings I’m used to. I want to update my photo reorganizer so it doesn’t create duplicate files so I figured this would be a handy thing to write. I wrote one for MD5 a while ago (the only code you really need to write is the byte-array-to-hex-string converter) but I guess I lost it. Anyway, here it is.

Edit: Rather than paste a huge useless block of code here, I put it on github: https://github.com/evandhoffman/Java-SHA-1-Hasher.

Output appears to match that of the command-line utility:

[evan@EvanMBP bin]$ java -jar SHA1.jar ~/text.txt
3bbed58697cc1775e8fadcf1324e26d4d092e7c2        /Users/evan/text.txt
[evan@EvanMBP bin]$ shasum ~/text.txt
3bbed58697cc1775e8fadcf1324e26d4d092e7c2  /Users/evan/text.txt

It’s not as fast as shasum (as I expected) but that may partially be due to reading data in 1k chunks.

Integrating Amazon Simple Email Service with postfix for SMTP smarthost relaying.

So, we’ve outgrown the 500 outbound messages/day limit imposed by Google Apps’s Standard tier. A wise friend suggested SendGrid, but I figured it was worth looking into what options Amazon provides. I found SES and am in the process of setting it up. Hopefully I can set it up as a drop-in replacement, obviating the need for code changes to use it. SES is attractive for us because:

Free Tier
If you are an Amazon EC2 user, you can get started with Amazon SES for free. You can send 2,000 messages for free each day when you call Amazon SES from an Amazon EC2 instance directly or through AWS Elastic Beanstalk. Many applications are able to operate entirely within this free tier limit.

Note: Data transfer fees still apply. For new AWS customers eligible for the AWS free usage tier, you receive 15 GB of data transfer in and 15 GB of data transfer out aggregated across all AWS services, which should cover your Amazon SES data transfer costs. In addition, all AWS customers receive 1GB of free data transfer per month.

Free to try? Sounds good.

After signing up, the first thing I did was download the Perl scripts. Create a credentials file with your AWS access key ID and Secret Key (credentials can be found here when logged in). The credentials file (aws-credentials) should look like this:

AWSAccessKeyId=022QF06E7MXBSH9DHM02
AWSSecretKey=kWcrlUX5JEDGM/LtmEENI/aVmYvHNif5zB+d9+ct

Make sure to chmod 0600 aws-credentials. To ensure it’s working, run:

$ ./ses-get-stats.pl -k aws-credentials -s

If it doesn’t return anything it should be working correctly.

Next, you need to add at least one verified email address:

$ ./ses-verify-email-address.pl -k aws-credentials --verbose -v support@example.com

Amazon will send a verification message to support@example.com with a link you need to click to verify the address. Once you click, it’s verified. It’s important to note that initially your account will only be able to send email to verified addresses. According to this thread, you need to submit a production access request to send to unverified To: addresses. I did this and got my “approval” email about 30 minutes later.

To send a test email:

$ ./ses-send-email.pl --verbose -k aws-credentials -s "Test from SES" -f support@example.com evan@example.com
This is a test message from SES.

(Press ctrl-D to send.)

The next step is integrating the script with sendmail/postfix. The first thing I did was move my scripts to /opt/ (out of /root/) and attempt to run them with absolute pathnames (rather than ./ses-send-email.pl) and I got perl @INC errors:

[root@web2 ~]$ mv amazon-email/ /opt/
[root@web2 ~]$ /opt/ses-get-stats.pl -k aws-credentials -s
-bash: /opt/ses-get-stats.pl: No such file or directory
[root@web2 ~]$ /opt/amazon-email/ses-get-stats.pl -k aws-credentials -s
Can't locate SES.pm in @INC (@INC contains: /usr/lib64/perl5/site_perl/5.8.8/x86_64-linux-thread-multi /usr/lib64/perl5/site_perl/5.8.7/x86_64-linux-thread-multi /usr/lib64/perl5/site_perl/5.8.6/x86_64-linux-thread-multi /usr/lib64/perl5/site_perl/5.8.5/x86_64-linux-thread-multi /usr/lib/perl5/site_perl/5.8.8 /usr/lib/perl5/site_perl/5.8.7 /usr/lib/perl5/site_perl/5.8.6 /usr/lib/perl5/site_perl/5.8.5 /usr/lib/perl5/site_perl /usr/lib64/perl5/vendor_perl/5.8.8/x86_64-linux-thread-multi /usr/lib64/perl5/vendor_perl/5.8.7/x86_64-linux-thread-multi /usr/lib64/perl5/vendor_perl/5.8.6/x86_64-linux-thread-multi /usr/lib64/perl5/vendor_perl/5.8.5/x86_64-linux-thread-multi /usr/lib/perl5/vendor_perl/5.8.8 /usr/lib/perl5/vendor_perl/5.8.7 /usr/lib/perl5/vendor_perl/5.8.6 /usr/lib/perl5/vendor_perl/5.8.5 /usr/lib/perl5/vendor_perl /usr/lib64/perl5/5.8.8/x86_64-linux-thread-multi /usr/lib/perl5/5.8.8 .) at /opt/amazon-email/ses-get-stats.pl line 23.
BEGIN failed--compilation aborted at /opt/amazon-email/ses-get-stats.pl line 23.

The problem is that SES.pm isn’t in perl’s include path. To solve this, I tried adding the directory to the PERL5LIB environment var:

[root@web2 amazon-email]$ PERL5LIB=/opt/amazon-email/
[root@web2 amazon-email]$ echo $PERL5LIB
/opt/amazon-email/
[root@web2 amazon-email]$ cd
[root@web2 ~]$ export PERL5LIB
[root@web2 ~]$ /opt/amazon-email/ses-get-stats.pl -k aws-credentials -s
Cannot open credentials file . at /opt/amazon-email//SES.pm line 54.
[root@web2 ~]$ /opt/amazon-email/ses-get-stats.pl -k /opt/amazon-email/aws-credentials -s
Timestamp               DeliveryAttempts        Rejects Bounces Complaints
2011-04-27T20:27:00Z    1                       0       0       0
[root@web2 ~]$

This worked for setting all users’ PERL5LIB … but didn’t allow postfix to send the message. After a couple more attempts at doing this “the right way,” I just ended up dropping a symlink to SES.pm in /usr/lib/perl5/site_perl and the @INC error went away.

After following Amazon’s instructions for editing main.cf and master.cf, I still was unable to send mail through Postfix, even though I could send directly through the perl scripts. I kept getting this error:

Apr 28 11:26:32 web2 postfix/pipe[27226]: A2AD33C9A6: to=, relay=aws-email, delay=0.35, delays=0.01/0/0/0.34, dsn=5.3.0, status=bounced (Command died with status 1: "/opt/amazon-email/ses-send-email.pl". Command output: Missing final '@domain' )

Google led me to this blog post which led me to this other blog post which illuminated the problem: apparently the Postfix pipe macro ${sender} uses the user@hostname of the mail sender. Since the hostname of an EC2 machine is usually something crazy like dom11-22-33-44.internal, this is not likely a validated sending email address. So the solution proposed by Ben Simon was to create a regex to map user@internal to user@realdomain.com and have postfix map everything. This didn’t work for me or the bashbang.com guys, who changed it to map from user@internal to validuser@realdomain.com. I found that you can eliminate the need for the mapping entirely by changing the master.cf entry to this:

  flags=R user=mailuser argv=/opt/amazon-email/ses-send-email.pl -r -k /opt/amazon-email/aws-credentials -e https://email.us-east-1.amazonaws.com -f support@example.com ${recipient}

The only difference between the above line and Amazon’s suggestion is that this replaces “-f ${sender}” with “support@example.com” which is a validated email address.

After this I was able to relay email successfully through SES. Whew!

Update 5/26/2011: We’ve been relaying through SES without issues for a few weeks now. I recently ran ses-get-stats.pl to see how many messages we’re actually sending and it’s a lot lower than expected. I’m still glad we moved to SES though, since it has no hard cap like Google Apps does:

$ /opt/amazon-email/ses-get-stats.pl -k /opt/amazon-email/aws-credentials -q
SentLast24Hours Max24HourSend   MaxSendRate
317             10000           5

ldapsearch example on Active Directory

Just putting this here for safekeeping since I couldn’t remember the exact syntax.

[evan@ehoffman 10:35:50 ~]$ ldapsearch -x -LLL -D "ldapuser@example.com" -w password -b "OU=Users,DC=example,DC=com" -s sub -H ldaps://activedirectory.example.com "(sn=hoffman)" cn mail displayName samaccountname
dn: CN=Evan Hoffman,OU=Tech,OU=Users,DC=example,DC=com
cn: Evan Hoffman
displayName: Evan D. Hoffman
sAMAccountName: ehoffman
mail: Evan.Hoffman@example.com

Explanation: Connect to activedirectory.example.com using ldaps (SSL) with simple authentication, binding as ldapuser@example.com with password password; search for (sn=hoffman) within the OU=Users,DC=example,DC=com search base (branch), and search the subtree. Return the cn, displayName, and samaccountname fields.

Refer to the ldapsearch man page for more options.

Java Code: searching a Binary Search Tree for the largest value strictly less than X

Someone recently asked me how to do this, so I figured I’d write it up in Java since it’s still the language I’m most comfortable with:

Node.java

package com.evanhoffman.bst;

import org.apache.log4j.Logger;

/**
 * Node in a binary search tree in which values = are in the right branch.
 * @author evan
 *
 * @param 
 */
public class Node<v extends Comparable> {
	private static Logger logger = Logger.getLogger(Node.class);

	private Node left = null;
	private Node right = null;
	private V value = null;

	public Node(V t) {
		this.value = t;
	}

	public V getValue() {
		return value;
	}
	public boolean isLeaf() {
		return (left == null && right == null);
	}


	public void addNode(Node node) {
		if (node.getValue().compareTo(value) < 0) {
			if (left == null) {
				left = node;
				logger.debug("Assigning "+node.getValue()+" "+
						"to left child of node "+value);
			} else {
				left.addNode(node);
			}
		} else {
			if (right == null) {
				right = node;
				logger.debug("Assigning "+node.getValue()+" "+
						"to right child of node "+value);
			} else {
				right.addNode(node);
			}
		}

	}

	public V findMaxStrictlyLessThan(V t) {
		return findMaxStrictlyLessThan(t, null);
	}

	/**
	 * Returns the greatest value in the tree strictly
	 * less than (as defined by {@link Comparable#compareTo(Object)} the given value.
	 * @param t
	 * @return
	 */
	private V findMaxStrictlyLessThan(V t, V currentMax) {
		if (t.compareTo(value) = current node "+value+", checking right (if exists)");
			currentMax = value;
			return right == null ? currentMax : right.findMaxStrictlyLessThan(t, currentMax);
		}

	}

	@Override
	public String toString() {
		if (isLeaf()) {
			return "{value="+value+"}";
		} else {
			return "{value="+value+", left="+left+", right="+right+"}";
		}
	}

}

IntBstBuilder.java:

package com.evanhoffman.bst;

import java.util.Random;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

public class IntBstBuilder {

	private static int min = 0;
	private static int max = 200;
	private static int size = 10;

	private static Random rng = new Random();
	private static Logger logger = Logger.getLogger(IntBstBuilder.class);

	public static void main(String args[]) {
		BasicConfigurator.configure();

		Node root = new Node((max - min)/2);
		for (int i = 0; i < size; i++) {
			int num = (Math.abs(rng.nextInt()) % (max - min)) + min;
			Node newNode = new Node(num);
			root.addNode(newNode);
		}

		logger.info(root);

		logger.info(root.findMaxStrictlyLessThan(50));
		logger.info(root.findMaxStrictlyLessThan(90));
		logger.info(root.findMaxStrictlyLessThan(130));
		logger.info(root.findMaxStrictlyLessThan(220));
		logger.info(root.findMaxStrictlyLessThan(-100));

	}
}

Output:

0 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 192 to right child of node 100
1 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 140 to left child of node 192
1 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 162 to right child of node 140
1 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 54 to left child of node 100
1 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 155 to left child of node 162
1 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 118 to left child of node 140
2 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 52 to left child of node 54
2 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 184 to right child of node 162
2 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 41 to left child of node 52
2 [main] DEBUG com.evanhoffman.bst.Node  - Assigning 161 to right child of node 155
2 [main] INFO com.evanhoffman.bst.IntBstBuilder  - {value=100, left={value=54, left={value=52, left={value=41}, right=null}, right=null}, right={value=192, left={value=140, left={value=118}, right={value=162, left={value=155, left=null, right={value=161}}, right={value=184}}}, right=null}}
2 [main] DEBUG com.evanhoffman.bst.Node  - 50 is less than current node 100, checking left (if it exists)
2 [main] DEBUG com.evanhoffman.bst.Node  - 50 is less than current node 54, checking left (if it exists)
2 [main] DEBUG com.evanhoffman.bst.Node  - 50 is less than current node 52, checking left (if it exists)
2 [main] DEBUG com.evanhoffman.bst.Node  - 50 is >= current node 41, checking right (if exists)
2 [main] INFO com.evanhoffman.bst.IntBstBuilder  - 41
2 [main] DEBUG com.evanhoffman.bst.Node  - 90 is less than current node 100, checking left (if it exists)
2 [main] DEBUG com.evanhoffman.bst.Node  - 90 is >= current node 54, checking right (if exists)
2 [main] INFO com.evanhoffman.bst.IntBstBuilder  - 54
2 [main] DEBUG com.evanhoffman.bst.Node  - 130 is >= current node 100, checking right (if exists)
2 [main] DEBUG com.evanhoffman.bst.Node  - 130 is less than current node 192, checking left (if it exists)
3 [main] DEBUG com.evanhoffman.bst.Node  - 130 is less than current node 140, checking left (if it exists)
3 [main] DEBUG com.evanhoffman.bst.Node  - 130 is >= current node 118, checking right (if exists)
3 [main] INFO com.evanhoffman.bst.IntBstBuilder  - 118
3 [main] DEBUG com.evanhoffman.bst.Node  - 220 is >= current node 100, checking right (if exists)
3 [main] DEBUG com.evanhoffman.bst.Node  - 220 is >= current node 192, checking right (if exists)
3 [main] INFO com.evanhoffman.bst.IntBstBuilder  - 192
3 [main] DEBUG com.evanhoffman.bst.Node  - -100 is less than current node 100, checking left (if it exists)
3 [main] DEBUG com.evanhoffman.bst.Node  - -100 is less than current node 54, checking left (if it exists)
3 [main] DEBUG com.evanhoffman.bst.Node  - -100 is less than current node 52, checking left (if it exists)
3 [main] DEBUG com.evanhoffman.bst.Node  - -100 is less than current node 41, checking left (if it exists)
3 [main] INFO com.evanhoffman.bst.IntBstBuilder  -

StringBstBuilder.java:

package com.evanhoffman.bst;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

public class StringBstBuilder {

	private static int size = 100;

	private static Random rng = new Random();
	private static Logger logger = Logger.getLogger(StringBstBuilder.class);

	private ArrayList words = new ArrayList();

	public ArrayList getWords() {
		return words;
	}



	StringBstBuilder(File f, int maxLines) {

		logger.debug("Creating "+this.getClass()+" with word list file: "+f+" up to "+maxLines+" lines");

		int i = 0;
		try {
			BufferedReader br = new BufferedReader(new FileReader(f));
			String line = null;
			while ((i < maxLines) && (line = br.readLine()) != null) {
				words.add(line);
				i++;
			}
			logger.debug("Added "+words.size()+" words to list");

		} catch (FileNotFoundException fe) {
			logger.error("File not found: "+f,fe);
			throw new RuntimeException(fe);
		} catch (IOException ie) {
			logger.error("IO Exception: "+ie.getMessage(),ie);
			throw new RuntimeException(ie);
		}
	}



	public static void main(String args[]) {
		BasicConfigurator.configure();

		StringBstBuilder sbt = new StringBstBuilder(new File(args[0]), Integer.parseInt(args[1]));

		ArrayList words = sbt.getWords();

		int wordListSize = words.size();

		// Random number between 1/4 and 3/4 through the list.
		int seedWordIndex = (Math.abs(rng.nextInt()) % (wordListSize/2)) + (wordListSize / 4);

		Node root = new Node(words.get(seedWordIndex));
		logger.debug("Root word: "+root.getValue());

		for (int i = 0; i < size; i++) {
			int index = (Math.abs(rng.nextInt()) % (words.size()));
			Node newNode = new Node(words.get(index));
			root.addNode(newNode);
		}

		logger.info("Entire tree: "+root);

		String[] searches = {"andy", "joker", "kale", "moonshine", "zebra"};
		for (String str : searches) {
			logger.info("Search for "+str+": ");
			String s = root.findMaxStrictlyLessThan(str);
			logger.info("max word: "+s);
		}

	}
}

Output:

0 [main] DEBUG com.evanhoffman.bst.StringBstBuilder  - Creating class com.evanhoffman.bst.StringBstBuilder with word list file: /Users/evan/Downloads/scowl-7.1/final/english-words.20 up to 10000 lines
47 [main] DEBUG com.evanhoffman.bst.StringBstBuilder  - Added 7951 words to list
48 [main] DEBUG com.evanhoffman.bst.StringBstBuilder  - Root word: patient's
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning scroll's to right child of node patient's
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning dual to left child of node patient's
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning bat to left child of node dual
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning moderate to right child of node dual
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning abort to left child of node bat
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning migrates to left child of node moderate
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning terrifying to right child of node scroll's
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning equilibrium to left child of node migrates
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning polynomial to left child of node scroll's
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning tomatoes to right child of node terrifying
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning unusable to right child of node tomatoes
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning nailing to right child of node moderate
48 [main] DEBUG com.evanhoffman.bst.Node  - Assigning supporter to left child of node terrifying
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning prosecution to right child of node polynomial
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning management to right child of node equilibrium
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning disabled to right child of node bat
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning planted to left child of node polynomial
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning midday to right child of node management
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning cloth to left child of node disabled
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning hip to left child of node management
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning tune's to left child of node unusable
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning mortal to left child of node nailing
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning dangers to right child of node cloth
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning concentrate to left child of node dangers
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning intimate to right child of node hip
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning stairs to left child of node supporter
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning attorney to right child of node abort
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning globally to left child of node hip
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning vertical to right child of node unusable
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning close's to left child of node cloth
49 [main] DEBUG com.evanhoffman.bst.Node  - Assigning debatable to right child of node dangers
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning guarding to right child of node globally
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning aided to left child of node attorney
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning contend to right child of node concentrate
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning shined to left child of node stairs
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning journals to right child of node intimate
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning warmed to right child of node vertical
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning blaming to left child of node close's
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning ingredient to left child of node intimate
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning gleaning to left child of node globally
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning boys to right child of node blaming
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning stream's to right child of node stairs
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning tragedy to left child of node tune's
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning brands to right child of node boys
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning revenge to right child of node prosecution
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning knight to right child of node journals
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning discard to right child of node disabled
50 [main] DEBUG com.evanhoffman.bst.Node  - Assigning successor to right child of node stream's
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning synonymous to right child of node supporter
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning bow to left child of node boys
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning satisfaction to right child of node revenge
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning mutters to right child of node mortal
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning tray to right child of node tragedy
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning linkage to right child of node knight
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning face's to left child of node gleaning
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning decreasing to right child of node debatable
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning spoiling to right child of node shined
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning slave's to left child of node spoiling
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning clarified to right child of node brands
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning inspection to right child of node ingredient
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning technically to right child of node synonymous
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning supervises to right child of node successor
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning disconnect to right child of node discard
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning whence to right child of node warmed
51 [main] DEBUG com.evanhoffman.bst.Node  - Assigning creator to right child of node contend
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning oppress to right child of node nailing
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning magnificent to right child of node linkage
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning launch to left child of node linkage
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning compensation to left child of node concentrate
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning cave to left child of node clarified
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning unbearable to right child of node tune's
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning verifies to left child of node vertical
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning compact to left child of node compensation
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning immense to left child of node ingredient
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning empire to left child of node equilibrium
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning foreseeable to right child of node face's
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning joking to left child of node journals
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning opts to right child of node oppress
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning convicting to left child of node creator
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning divisions to right child of node disconnect
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning fascinate to left child of node foreseeable
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning reactions to left child of node revenge
52 [main] DEBUG com.evanhoffman.bst.Node  - Assigning discriminated to left child of node divisions
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning unrealistic to right child of node unbearable
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning crowds to right child of node creator
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning marketed to left child of node midday
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning broad to left child of node cave
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning socket to right child of node slave's
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning verbal to left child of node verifies
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning register's to right child of node reactions
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning attributes to right child of node attorney
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning clarity to right child of node clarified
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning engage to right child of node empire
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning succeeded to left child of node successor
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning resembled to right child of node register's
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning kernel to left child of node knight
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning dot to right child of node divisions
53 [main] DEBUG com.evanhoffman.bst.Node  - Assigning wrecked to right child of node whence
54 [main] DEBUG com.evanhoffman.bst.Node  - Assigning gratuitously to left child of node guarding
54 [main] DEBUG com.evanhoffman.bst.Node  - Assigning syndicate to left child of node synonymous
54 [main] INFO com.evanhoffman.bst.StringBstBuilder  - Entire tree: {value=patient's, left={value=dual, left={value=bat, left={value=abort, left=null, right={value=attorney, left={value=aided}, right={value=attributes}}}, right={value=disabled, left={value=cloth, left={value=close's, left={value=blaming, left=null, right={value=boys, left={value=bow}, right={value=brands, left=null, right={value=clarified, left={value=cave, left={value=broad}, right=null}, right={value=clarity}}}}}, right=null}, right={value=dangers, left={value=concentrate, left={value=compensation, left={value=compact}, right=null}, right={value=contend, left=null, right={value=creator, left={value=convicting}, right={value=crowds}}}}, right={value=debatable, left=null, right={value=decreasing}}}}, right={value=discard, left=null, right={value=disconnect, left=null, right={value=divisions, left={value=discriminated}, right={value=dot}}}}}}, right={value=moderate, left={value=migrates, left={value=equilibrium, left={value=empire, left=null, right={value=engage}}, right={value=management, left={value=hip, left={value=globally, left={value=gleaning, left={value=face's, left=null, right={value=foreseeable, left={value=fascinate}, right=null}}, right=null}, right={value=guarding, left={value=gratuitously}, right=null}}, right={value=intimate, left={value=ingredient, left={value=immense}, right={value=inspection}}, right={value=journals, left={value=joking}, right={value=knight, left={value=kernel}, right={value=linkage, left={value=launch}, right={value=magnificent}}}}}}, right={value=midday, left={value=marketed}, right=null}}}, right=null}, right={value=nailing, left={value=mortal, left=null, right={value=mutters}}, right={value=oppress, left=null, right={value=opts}}}}}, right={value=scroll's, left={value=polynomial, left={value=planted}, right={value=prosecution, left=null, right={value=revenge, left={value=reactions, left=null, right={value=register's, left=null, right={value=resembled}}}, right={value=satisfaction}}}}, right={value=terrifying, left={value=supporter, left={value=stairs, left={value=shined, left=null, right={value=spoiling, left={value=slave's, left=null, right={value=socket}}, right=null}}, right={value=stream's, left=null, right={value=successor, left={value=succeeded}, right={value=supervises}}}}, right={value=synonymous, left={value=syndicate}, right={value=technically}}}, right={value=tomatoes, left=null, right={value=unusable, left={value=tune's, left={value=tragedy, left=null, right={value=tray}}, right={value=unbearable, left=null, right={value=unrealistic}}}, right={value=vertical, left={value=verifies, left={value=verbal}, right=null}, right={value=warmed, left=null, right={value=whence, left=null, right={value=wrecked}}}}}}}}}
55 [main] INFO com.evanhoffman.bst.StringBstBuilder  - Search for andy:
55 [main] DEBUG com.evanhoffman.bst.Node  - andy is less than current node patient's, checking left (if it exists)
55 [main] DEBUG com.evanhoffman.bst.Node  - andy is less than current node dual, checking left (if it exists)
55 [main] DEBUG com.evanhoffman.bst.Node  - andy is less than current node bat, checking left (if it exists)
55 [main] DEBUG com.evanhoffman.bst.Node  - andy is >= current node abort, checking right (if exists)
55 [main] DEBUG com.evanhoffman.bst.Node  - andy is less than current node attorney, checking left (if it exists)
55 [main] DEBUG com.evanhoffman.bst.Node  - andy is >= current node aided, checking right (if exists)
55 [main] INFO com.evanhoffman.bst.StringBstBuilder  - max word: aided
56 [main] INFO com.evanhoffman.bst.StringBstBuilder  - Search for joker:
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is less than current node patient's, checking left (if it exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is >= current node dual, checking right (if exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is less than current node moderate, checking left (if it exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is less than current node migrates, checking left (if it exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is >= current node equilibrium, checking right (if exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is less than current node management, checking left (if it exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is >= current node hip, checking right (if exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is >= current node intimate, checking right (if exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is less than current node journals, checking left (if it exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - joker is less than current node joking, checking left (if it exists)
56 [main] INFO com.evanhoffman.bst.StringBstBuilder  - max word: intimate
56 [main] INFO com.evanhoffman.bst.StringBstBuilder  - Search for kale:
56 [main] DEBUG com.evanhoffman.bst.Node  - kale is less than current node patient's, checking left (if it exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - kale is >= current node dual, checking right (if exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - kale is less than current node moderate, checking left (if it exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - kale is less than current node migrates, checking left (if it exists)
56 [main] DEBUG com.evanhoffman.bst.Node  - kale is >= current node equilibrium, checking right (if exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - kale is less than current node management, checking left (if it exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - kale is >= current node hip, checking right (if exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - kale is >= current node intimate, checking right (if exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - kale is >= current node journals, checking right (if exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - kale is less than current node knight, checking left (if it exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - kale is less than current node kernel, checking left (if it exists)
57 [main] INFO com.evanhoffman.bst.StringBstBuilder  - max word: journals
57 [main] INFO com.evanhoffman.bst.StringBstBuilder  - Search for moonshine:
57 [main] DEBUG com.evanhoffman.bst.Node  - moonshine is less than current node patient's, checking left (if it exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - moonshine is >= current node dual, checking right (if exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - moonshine is >= current node moderate, checking right (if exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - moonshine is less than current node nailing, checking left (if it exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - moonshine is less than current node mortal, checking left (if it exists)
57 [main] INFO com.evanhoffman.bst.StringBstBuilder  - max word: moderate
57 [main] INFO com.evanhoffman.bst.StringBstBuilder  - Search for zebra:
57 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node patient's, checking right (if exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node scroll's, checking right (if exists)
57 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node terrifying, checking right (if exists)
58 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node tomatoes, checking right (if exists)
58 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node unusable, checking right (if exists)
58 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node vertical, checking right (if exists)
58 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node warmed, checking right (if exists)
58 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node whence, checking right (if exists)
58 [main] DEBUG com.evanhoffman.bst.Node  - zebra is >= current node wrecked, checking right (if exists)
58 [main] INFO com.evanhoffman.bst.StringBstBuilder  - max word: wrecked

Code to flatten a list in Java, with and without recursion

Recently had someone ask me to solve this problem: assume you have a list of objects, some of which may be lists of arbitrary depths. Write a function to return the list “flattened,” so sublists are all in the “main” list. I solved it recursively pretty easily, but it took some thought to do it without recursion. My solutions are below.

package com.evanhoffman.listflattener;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

public class ListFlattener {

        private static Logger logger = Logger.getLogger(ListFlattener.class);

        public static List flattenList(List inList) {
                List newList = new LinkedList();

                for (Object i : inList) {
                        // If it's not a list, just add it to the return list.
                        if (!(i instanceof List)) {
                                newList.add(i);
                        } else {
                                // It's a list, so add each item to the return list.
                                newList.addAll(flattenList((List)i));
                        }
                }

                return newList;
        }

        public static List flattenListNoRecursion(List inList) {
                List tempList = null;

                // Clone the input list to newList
                List newList = new LinkedList();
                newList.addAll(inList);

                ListIterator iterator = newList.listIterator();


                int currentPosition = 0;

                while (iterator.hasNext()) {
                        Object i = iterator.next();
                        if (!(i instanceof List)) {
                                // If it's not a list, advance the position.  Don't advance position if this IS a list.
                                currentPosition++;
                        } else {
                                // If the current item is a list, save it to a temp var.
                                tempList = (List) i;

                                // Delete the list from the list
                                iterator.remove();

                                // Add each item from the temp list to the master list at the same position the sublist was removed.
                                for (Object obj : tempList) {
                                        iterator.add(obj);
                                }

                                // reset the iterator to re-walk the list that was just inserted (within the master) to check for more lists.
                                iterator = newList.listIterator(currentPosition);
                        }
                }
                return newList;
        }

        public static void printList(List list) {
                int i = 0;
                for (Object item : list) {
                        logger.debug("List item #"+i +": "+item);
                        i++;
                }
        }

        public static void main(String[] args) {

                BasicConfigurator.configure();

                // List of strings
                LinkedList stringList = new LinkedList();
                for (Integer i = 0; i < 10; i++) {
                        stringList.add("String #" +i.toString());
                }

                // List of integers
                LinkedList intList = new LinkedList();
                for (Integer i = 10; i < 20; i++) {
                        intList.add(i);
                }

                // Nested Lists
                LinkedList nestedList1 = new LinkedList();
                LinkedList nestedList2 = new LinkedList();
                LinkedList nestedList3 = new LinkedList();

                nestedList3.add("Nested String 1");
                nestedList3.add("Nested String 2");
                nestedList2.add(nestedList3);
                nestedList1.add(nestedList2);

                LinkedList bigList = new LinkedList();

                bigList.add("First item");
                bigList.add(stringList);
                bigList.add("Third Item");
                bigList.add(intList);
                bigList.add("Fifth Item");
                bigList.add(nestedList1);
                bigList.add("Seventh Item");

//              List flattenedList = flattenList(bigList);
                List flattenedListRecursion = flattenList(bigList);
                List flattenedList = flattenListNoRecursion(bigList);

                logger.debug("Original list:                 "+bigList.toString());
//              printList(bigList);
                logger.debug("Flattened list (w/ recursion): "+flattenedListRecursion.toString());
                logger.debug("Flattened list (no recursion): "+flattenedList.toString());
//              printList(flattenedList);

        }
}

Java compound interest calculator

I wrote a thing to calculate compound interest and print out how much you’ve accrued after each period. It’s pretty basic but I was bored and didn’t want to do it via calculator. The code is in InterestCalculator.java, sample output is below:

Initial principal: 5000.00
Interest rate:     0.05 (4.93%)
# of ann. periods: 4
Total years:       5
Annual Addition:   500.0
Starting year 1 with $5000.00
Year 1, period 1, accrued $61.62, value is now: $5061.62
Year 1, period 2, accrued $62.38, value is now: $5124.01
Year 1, period 3, accrued $63.15, value is now: $5187.16
Year 1, period 4, accrued $63.93, value is now: $5251.09
Added $500.00 for the end of year 1, total is now: 5751.09
Starting year 2 with $5751.09
Year 2, period 1, accrued $70.88, value is now: $5821.98
Year 2, period 2, accrued $71.76, value is now: $5893.73
Year 2, period 3, accrued $72.64, value is now: $5966.37
Year 2, period 4, accrued $73.54, value is now: $6039.91
Added $500.00 for the end of year 2, total is now: 6539.91
Starting year 3 with $6539.91
Year 3, period 1, accrued $80.60, value is now: $6620.51
Year 3, period 2, accrued $81.60, value is now: $6702.11
Year 3, period 3, accrued $82.60, value is now: $6784.71
Year 3, period 4, accrued $83.62, value is now: $6868.34
Added $500.00 for the end of year 3, total is now: 7368.34
Starting year 4 with $7368.34
Year 4, period 1, accrued $90.81, value is now: $7459.15
Year 4, period 2, accrued $91.93, value is now: $7551.08
Year 4, period 3, accrued $93.07, value is now: $7644.15
Year 4, period 4, accrued $94.21, value is now: $7738.37
Added $500.00 for the end of year 4, total is now: 8238.37
Starting year 5 with $8238.37
Year 5, period 1, accrued $101.54, value is now: $8339.90
Year 5, period 2, accrued $102.79, value is now: $8442.69
Year 5, period 3, accrued $104.06, value is now: $8546.75
Year 5, period 4, accrued $105.34, value is now: $8652.09
Added $500.00 for the end of year 5, total is now: 9152.09
Final value: $9152.09