Preventing Log Forging in Liferay 6.2

28 January 2016

In the process of securing our customized deployment of Liferay 6.2 scanning revealed that we have a vulnerability to Log Forging. Log Forging is where an attacker inserts information into a log file. This information could for example say that an event happened which didn't. The most obvious avenue of attack is user input which is written to a log file. The attacker could simply put data in a form field that looks like a log entry.

The currently accepted solution is to remove any line feeds and carriage returns from text written to a log file. If you are using an HTML log view you will also want to html encode any text written to the log file. Specifically any text than comes from an external source, such as a user.

Fortunately Liferay 6.2 has a solution for this out of the box. It is tucked away inside the system.properties file. To enable it you simply need to modify your JVM startup parameters. In Tomcat you would modify the setenv.sh file to look something like the following.

bin/setenv.sh



CATALINA_OPTS="-Dlog.sanitizer.enabled=true -Dlog.sanitizer.escape.html.enabled=false -Dlog.sanitizer.replacement.character=95 -Dlog.sanitizer.whitelist.characters=9,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126 "

You enable sanitization, define a replacement character and create a white list of acceptable characters.

Running HP Fortify from the Command Line

27 January 2016

As a developer I have been tasked with making sure our application is compliant with Defense Information Systems Agency's (DISA) Security Technical Implementation Guide (STIG). DISA publishes a list of STIGs periodically which the development team needs to implement. One of the tools we use to accomplish this is HP Fortify. Fortify is a Static Code Analysis(SCA) tool.

Recently my work computer was replaced and I went from 32 Bit Fedora to a 64 Bit Fedora. The result of this is my 32 Bit Fortify installation quit working. To work around this problem I decided to learn how to run Fortify from the command line. At first running from the command line also didn't work. The solution there was to rename "HP_Fortify_3.50_SCA_and_Apps/jre" to "HP_Fortify_3.50_SCA_and_Apps/jre32". After the rename the command line started working.

You can run any of the command line tools with the "-h" or "-help" command option to get a list of available options. The results are quite verbose so we will concentrate on the sourceanalyzer's more often used options. An important build option is the "-b" option which specifies the build id. The build id is what ties all of your use of the command line tools together. The "-clean" command option will delete intermediate files and build records. "-source" is used to specify which version of Java you are using. The "-scan" command option causes sourceanalyzer to analyze your cource code. "-format" specifies in what filetype you want the scan results stored. A very handy one is "-show-build-ids" which will list the available build Ids. Finally the "-64" option tells sourceanalyzer to run in 64 bit mode.

The lifecycle of a Fortify Scan is as follows:

  • Clean
  • Build
  • Analyze
  • Report

First let us list the available build ids. This step is useful to find any already existing analysis.

Example show build ids

bash$ sourceanalyzer -show-build-ids
ExampleProject
   Created: Jan 13, 2016 1:45:47 PM
   Last Modified: Jan 13, 2016 1:45:47 PM
   Errors and Warnings: 29
   Project: []  Label: []  Version: []

Remove temporary files that might influence a new analysis.

Clean by build id

bash$  sourceanalyzer -64 -b "RecruitingOperations" -clean

Parse source code and prepare for analysis.

Build by build id

bash$  sourceanalyzer -64 -b "ExampleProject" -source "1.6" "/path/to/project/source/code/"
[warning]: The following references to java classes could not be resolved. Please make sure to supply all the required jar files that contain these classes to SCA.
	com.liferay.counter.service.CounterLocalService
	com.liferay.counter.service.CounterLocalServiceUtil
	com.liferay.portal.NoSuchModelException
	com.liferay.portal.kernel.bean.AutoEscape
	com.liferay.portal.kernel.bean.AutoEscapeBeanHandler
	com.liferay.portal.kernel.bean.BeanReference
	com.liferay.portal.kernel.bean.IdentifiableBean
	com.liferay.portal.kernel.bean.PortletBeanLocatorUtil
  ...

Analyze the prepared code.

Analyze by build id

bash$ sourceanalyzer -64 -b "ExampleProject" -format "fpr" -f "/path/to/report/ExampleProject.fpr" -scan
[warning]: Some errors or warnings were suppressed.  Check the results file for a full listing of all warnings and errors.

After analysis generated a human readable report.

Generate report from analysis

bash$  ReportGenerator -template "DeveloperWorkbook.xml" -format "pdf" -f "/path/to/report/ExampleProject.pdf" -source  "/path/to/report/ExampleProject.fpr"

This covers some basic functionality. For more help see the HP Fortify user manual.

Using ESAPI to satisfy STIG Requirements

27 January 2016

As a developer I have been tasked with making sure our application is compliant with Defense Information Systems Agency's (DISA) Security Technical Implementation Guide (STIG). DISA publishes a list of STIGs periodically which the development team needs to implement. One of the tools we use to accomplish this is the Open Web Application Security Project's (OWASP) Enterprise Security API (ESAPI). Many of the STIGs published by DISA can be implemented using the ESAPI. Both the current version, ESAPI 2.0, and the upcoming ESAPI 3.0 are hosted on Github. Do not be thrown off by ESAPI 2.0 being labeled "legacy". It is the current version. While we will be using it with Java other languages/frameworks sunch as PHP, .Net and Javascript.

ESAPI helps you by providing industry accepted solutions to security vulnerabilities in your application. Log forging, cross site scripting and LDAP injection are a few examples. In addition it also provides data validation and encryption support. This article is written in the context of using ESAPI to secure Liferay on a Tomcat application server. I am using Maven 3 as my build environment.

I found few helpful resources concerning setting up ESAPI. Documentation and configuration files seem to be scattered between Google code and the OWASP site. As I have mentioned it is now also on Github. Thus the reason for this article. The following is what I found to be the most helpful in fully installing and configuring ESAPI. The first step is to checkout the source code from Github. I recommend this because this gives you access to all the necessary configuration files and to some documentation.

checkout ESAPI 2.0 from Github



bash$ git clone https://github.com/ESAPI/esapi-java-legacy.git
Cloning into 'esapi-java-legacy'...
remote: Counting objects: 24393, done.
remote: Compressing objects: 100% (95/95), done.
remote: Total 24393 (delta 40), reused 0 (delta 0), pack-reused 24277
Receiving objects: 100% (24393/24393), 36.03 MiB | 1.67 MiB/s, done.
Resolving deltas: 100% (15356/15356), done.
Checking connectivity... done.

The configuration files will be located in the "configuration" subdirectory. Copy the "esapi" and "properties" directories to the location where you will be storing your configuration. In my case I placed them in the "<tomcat directory>/lib/ext" folder. ESAPI scans your classpath looking for an "esapi" directory to load the configuration. Unfortunately the "ant-sammy" part of it does not work unless you add a JVM startup parameter. You will want to add "-D-Dorg.owasp.esapi.resources" to your Tomcat setenv.sh script.

bin/setenv.sh



CATALINA_OPTS=" -Dorg.owasp.esapi.resources=../lib/ext/esapi"

Next you will want to add the esapi-2.1.0.jar and antisamy-1.5.3.jar to your class path. The easiest way, as shown below, to accomplish this with a maven project is to add ESAPI as a dependency to your project pom.xml. This has the advantage of Maven downloading all the necessary dependencies. I placed the jar files in the Tomcat "lib/ext" directory and modified the scope of the dependency to be "provided". The second way gives access to all applications running on the server without having to include the jar file in each seperate war file. The most reliable and easiest place to download the jar files is the Maven Central Repository.

pom.xml



    ...
   
      org.owasp.antisamy
      antisamy
      1.5.3
    
    
      org.owasp.esapi
      esapi
      2.1.0
    

    ...


The dependencies require by ESAPI are automatically downloaded by Maven. If however you decide to do it manually here are a list of dependencies.

  • antisamy-1.4.3.jar
  • xercesImple-2.8.0.jar
  • batik-ext-1.7.jar
  • batik-css-1.7.jar
  • nekohtml-1.9.12.jar

These steps provide you with default ESAPI functionality. You will want to customize the properties and configuration files to suit your needs and security considerations. Options which I will discuss in further articles.

Getting XRDP to Work on Linux

14 January 2016

My fellow programmers and I use XRDP, an open source Remote Desktop Protocol application, for remotely connecting to our workstations. Routinely during upgrades XRDP would stop working. Some time later during a routine security scan my workstation was assessed to have the CVE-2005-1794 vulnerability. This vulnerability being that for RDP to be secure either on Linux or Windows a third party certificate is needed to prevent attackers from spoofing public keys.

Having to redo the configurations a number of times, for myself and others, it seemed prudent to document the procedures. First let us look into getting XRDP to play nice with SELinux. SELinux uses extended file attributes to label files with a "Security Context". For XRDP to work with SELinux we need to change the context of files xrdp and xrdp-sesman as shown below.

Change files security context



sudo chcon --type=bin_t /usr/sbin/xrdp
sudo chcon --type=bin_t /usr/sbin/xrdp-sesman
sudo systemctl reenable xrdp.service
sudo systemctl start xrdp.service

What happened is we used the change context command to change the type of the files. SELinux then allowing the files to be run. Unfortunately the changes above will likely not last if you reinstall or upgrade XRDP. To make the changes more permanent you would want to modify SELinux configuration to remember the changes.

Add file context configuration to SELinux configuration



sudo semanage fcontext -a -t samba_share_t "/usr/sbin/xrdp"
sudo semanage fcontext -a -t samba_share_t "/usr/sbin/xrdp-sesman"
sudo systemctl reenable xrdp.service
sudo systemctl start xrdp.service

Now lets look into securing XRDP from public key spoofing. We chose to create a self-signed certificate. For our purposes this will be perfectly adequate as only our team will be connecting to the workstations and we know they are trustworthy. First lets get our certificate. You will be prompted to answer a series of questions about the location and name of the server for which it is being created.

Generate a certificate


```
bash-4.3$ cd /etc/xrdp
bash-4.3$ openssl req -x509 -newkey rsa:2048 -nodes -keyout key.pem -out cert.pem -days 3650
Generating a 2048 bit RSA private key
..........+++
.......+++
writing new private key to 'key.pem'
-----
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [XX]:US
State or Province Name (full name) []:Kentucky
Locality Name (eg, city) [Default City]:Louisville
Organization Name (eg, company) [Default Company Ltd]:Open Source
Organizational Unit Name (eg, section) []:Blog
Common Name (eg, your name or your server's hostname) []:Workstation
Email Address []:no@email.com
```

Once that is accomplished change the permissions of of the keys to protect them.

Generate a certificate



bash-4.3$ chmod 400 key.pem
bash-4.3$ chmod 444 cert.pem

Next we modify the /etc/xrdp/xrdp.ini file to enable tls by changing "security_layer=rdp" to "security_layer=tls". Finally we restart the XRDP service in order for the changes to take effect.

Restart XRDP



bash-4.3$ systemctl restart xrdp

Java Web Application Memory Leak

09 January 2016

Recently a Java Web Application on which I work ran out of memory and had to be restarted. We have monitoring tools but not ones that are helpful identifying the source of a memory leak. Working for a large organization with an established bureacracy my options were quite limited. After some research the only available option was to use the "jmap" command line utility that comes with the JDK. This discussion assumes that you have access to the computer/server on which the Java application server is running.

To follow along you will need an application server preferrably with a web application deployed to the server. You will need a current version of the JDK instlled. In my setup I am running Liferay Portal on a Tomcat 7 application server using JDK 8. These instructions should work with any Java base application server. From a high level view it is a simple process.

  • Start your application server
  • Find the pid for the application server
  • Run jmap against the pid

As a developer I have multiple versions of the JDK installed on my workstation. The first time I ran jmap I received the following error. This was due to using Oracle JDK 8 to run the server and the OpenJDK 8 being in my path. This was easily resolved by running the jmap from the Oracle JDK installation.

Terminal window in mysecurity directory



bash-4.3$ jmap -histo:live 12345
Error attaching to process: sun.jvm.hotspot.runtime.VMVersionMismatchException: Supported versions are 25.65-b01. Target VM is 25.45-b02
sun.jvm.hotspot.debugger.DebuggerException: sun.jvm.hotspot.runtime.VMVersionMismatchException: Supported versions are 25.65-b01. Target VM is 25.45-b0

Jmap can provide you with an overview of the heap which is useful for tuning garbage collection and a histogram listing objects memory usage from most to least. I will provide an example of the first but our focus will largely be on the second.

jmap -heap 22340



bash-4.3$ ./jmap -heap 22340
Attaching to process ID 22340, please wait...
Debugger attached successfully.
Server compiler detected.
JVM version is 25.45-b02

using parallel threads in the new generation.
using thread-local object allocation.
Concurrent Mark-Sweep GC

Heap Configuration:
   MinHeapFreeRatio         = 40
   MaxHeapFreeRatio         = 70
   MaxHeapSize              = 1073741824 (1024.0MB)
   NewSize                  = 134217728 (128.0MB)
   MaxNewSize               = 134217728 (128.0MB)
   OldSize                  = 939524096 (896.0MB)
   NewRatio                 = 2
   SurvivorRatio            = 8
   MetaspaceSize            = 16777216 (16.0MB)
   CompressedClassSpaceSize = 1073741824 (1024.0MB)
   MaxMetaspaceSize         = 4294963200 (4095.99609375MB)
   G1HeapRegionSize         = 0 (0.0MB)

Heap Usage:
New Generation (Eden + 1 Survivor Space):
   capacity = 120848384 (115.25MB)
   used     = 62650520 (59.748191833496094MB)
   free     = 58197864 (55.501808166503906MB)
   51.84224887938924% used
Eden Space:
   capacity = 107479040 (102.5MB)
   used     = 49281184 (46.998199462890625MB)
   free     = 58197856 (55.501800537109375MB)
   45.85190191501525% used
From Space:
   capacity = 13369344 (12.75MB)
   used     = 13369336 (12.749992370605469MB)
   free     = 8 (7.62939453125E-6MB)
   99.99994016161152% used
To Space:
   capacity = 13369344 (12.75MB)
   used     = 0 (0.0MB)
   free     = 13369344 (12.75MB)
   0.0% used
concurrent mark-sweep generation:
   capacity = 939524096 (896.0MB)
   used     = 17592173835622 MB
   free     = 12802787843112 (1.2209689944374084E7MB)
   -1362588.609863179% used

69485 interned Strings occupying 6458400 bytes.

Information such as the ratios, Eden space and New Generation space can be used to tune your JVMs garbage collection. JVM tuning is outside the scope of this article. Java Performance Tuning delves into the subject quite thoroughly.

jmap -heap 22340

```

bash-4.3$ ./jmap -histo:live 22340 | more

 num     #instances         #bytes  class name
----------------------------------------------
   1:       1540727      159689648  [C
   2:         61031       71410712  [B
   3:       2486669       59680056  java.util.HashMap$Node
   4:        147882       32565744  [Ljava.util.HashMap$Node;
   5:       1528219       24451504  java.lang.String
   6:        257708       22678304  java.lang.reflect.Method
   7:        279874        5420832  [Ljava.lang.Class;
   8:        128250        5130000  java.util.HashMap
   9:        152320        4874240  java.util.LinkedHashMap$Entry
  10:        110241        4750624  [Ljava.lang.Object;
  11:         74052        4739328  java.lang.reflect.Field
  12:         78133        4375448  java.util.LinkedHashMap
  13:        140261        3366264  java.util.Hashtable$Entry
  14:        147399        2876032  [Ljava.lang.String;
  15:         30736        2647576  [I
  16:         25009        2552912  java.lang.Class
  17:         85499        2051976  java.lang.ref.WeakReference
```

The ":live" part of the command only displays objects that are still being referenced. This will be more useful for diagnosing my memory leak. As we can see the objects taking up the most memory are "[C". What is this class? It turns out this is documented in the Java API documents under Class.getName(). A copy of which is provided below.

  
Element Type       | Encoding     |
-------------------|---------     |
boolean            | Z            |
byte               | B            |
char               | C            |
class or interface | Lclassname;  |
double             | D            |
float              | F            |
int                | I            |
long               | J            |
short              | S            |

Characters taking up most of the space is believable since the JVM stores Strings as character arrays in memory. This will be most useful if you take a snapshot when your application is running normally. Then when something goes wrong you will have a baseline for comparison.

Liferay: Setting Theme Color based on User Attributes

04 January 2016

In the Liferay portal product they provide the capability to provide multiple color schemes using one theme. Which provides flexibility for the end users to customize their experience. If you want to control that experience and choose different theme colors based on the user then you will need to write something custom.

The first challenge is how to get the user information to the Liferay Theme. One option would be to customize the User service layer. By default Liferay provides the user object to the theme. I found this objectionable as it would make database calls for every page load. This seems excessive just to identify which color scheme should be used. I decided that I would set a session variable when a user logs in and use that to set the color scheme.

First generate a Liferay hook project using "mvn archetype:generate"

Next we need to register our hook by adding the following line to the portal.properties file in the Maven resources folder.

src/main/resources/portal.properties



  login.events.post=com.codeexcursion.ColorHook

Write our ColorHook class.

src/main/java/com/codeexcursion/ColorHook.java

```

public class ColorHook extends Action {

  private static final Log _log = IkromeLogUtil.getLog(SynchronizationHook.class);

  @Override
  public void run(HttpServletRequest request, HttpServletResponse response) throws ActionException {
    /* This is where you would pull in your user object to set the color value based on a
       User attribute.  I simply set it explicitly for this example.
    */ 
    String colorValue = "defaulColor";
    request.getSession().setAttribute("color",colorValue);

  }
}
```

To use this Liferay hook we would then need to create a custom theme to use the session variable. Once again use "mvn archetype:generate" to setup a Liferay theme project. Now we need to add a custom Velocity template file to our theme. Here we are modifying the $css_class variable in the template to have the color value.

Liferay's default theme already adds a value to the variable so first we want to remove said value and add our own.

src/main/webapp/templates/init_custom.vm



  #set ($css_class = $css_class.substring($css_class.indexOf("")))
  #set ($css_class = $request.getSession().getAttribute() + " " + "${css_class}")

Scripting A Wordpress Upgrade

11 January 2015

Wordpress seems to require ftp or ftps access to automatically upgrade itself.  This bothered me as I saw it as a potential security risk and work I would have to put in to setting up a FTPS server I didn't want.  My solution was to upgrade Wordpress manually.

Following the steps in the link above Wordpress was successfully upgraded.  The process was not quick and not easy to remember if they are only used periodically.  The decision was then easy to build some scripts and directions for upgrading.

The steps need for this process is as follows


  1. Login into WordPress and disable your plugins.

  2. Login to your server using ssh.

  3. Using wget retrieve the latest copy of wordpress. "wget https://downloads.wordpress.org/release/wordpress-4.1.zip"

  4. unzip the files "unzip wordpress-4.1.zip"

  5. Backup Wordpress on the server

  6. Upgrade Wordpress on the server

  7. Go to your wordpress wp-admin page.

  8. You may be prompted to upgrade your databae.  Go ahead and do so.

  9. Enable your plugins.


For steps 4 and 5 we need some helpful scripts.  The first script dumps the mysql database and tars up the wordpress files.

wordpressbackup.sh

NOW=$(date +"%Y%m%d")

mysqldump -u root -p$1 mysite > ~/mysitebackup/mysite$NOW.sql

tar -cvzf ~/mysitebackup/mysite$NOW.tar.gz /var/www/html/mysite

The second file needs to be run in the directory containing the new Wordpress application files.  These would be the files you retrieved and extracted in steps 3 and 4.

upgradewordpress.sh

rm -rf /var/www/html/mysite/wp-includes
rm -rf /var/www/html/mysite/wp-admin

cp -rf wp-includes /var/www/html/mysite
cp -rf wp-admin /var/www/html/mysite
cp -rf wp-content /var/www/html/mysite

chown -R apache /var/www/html/mysite/wp-includes
chown -R apache /var/www/html/mysite/wp-admin
chown -R apache /var/www/html/mysite/wp-content

I placed these two files in the PATH so that I could run them from wherever.  Voila!  We now have mostly automated the manual upgrade of WordPress.

Below is a terminal capture of what the process would look like for steps 3 through 6 using the scripts.  Steps 4 and 5 will produce verbose output which i didn't capture below.
div class="terminalHolder">
Terminal window Steps 3-6


[user@server ~]# wget https://downloads.wordpress.org/release/wordpress-4.1.zip
--2015-01-11 17:33:43--  https://downloads.wordpress.org/release/wordpress-4.1.zip
Resolving downloads.wordpress.org (downloads.wordpress.org)... 66.155.40.203, 66.155.40.202
Connecting to downloads.wordpress.org (downloads.wordpress.org)|66.155.40.203|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 6718759 (6.4M) [application/zip]
Saving to: ‘wordpress-4.1.zip’

100%[========================================================================================================================================================================================>] 6,718,759   9.46MB/s   in 0.7s   

2015-01-11 17:33:44 (9.46 MB/s) - ‘wordpress-4.1.zip’ saved [6718759/6718759]
[user@server ~]# unzip wordpress-4.1.zip
[user@server ~]# cd wordpress
[user@server wordpress]# wordpressbackup.sh 
Enter password:
[user@server wordpress]# upgradewordpress.sh

Book Notes: Practical Object Oriented Design in Ruby

09 October 2014

I recently read Practical Object-Oriented Design in Ruby by Sandi Metz. A fantastic book to help bridge the gap between theory and implementation of design. I highly recommend this book even for non Rubyists. Below are bullet points to help remember key points in the book.



    • General

      • Make design decisions based on what you know now.

      • Design behavior not data.

      • Checking types or classes indicates an opportunity for inheritance or interfaces.

      • Inject dependencies.

      • Use factories to centralize design that otherwise would be spread throughout multiple classes. Such as instantiating classes to be injected.

      • Use shallow inheritance hierarchies

      • Favor composition over inheritance when in doubt.

      • When dependencies cannot be eliminated then they should be isolated from the rest of the code.

      • Dependency has a direction and should be pointed toward the code least likely to change.

      • Abstractions are less likely to change than concretions.

      • A diagram of object interaction should look like a tree not a mesh.

      • Use sequence diagrams to determine the classes you need.



    • Methods

      • Should have single responsibility

      • Large methods indicate the need to be reduced to multiple smaller methods

      • Many private methods indicate the possible need for a new class.

      • Method parameter order is a dependency.



    • Interfaces

      • The messages sent between objects are how they interface.

      • Interfaces are roles shared by otherwise unrelated objects.



    • Classes

      • Should have a single responsibility

      • Use inheritance when classes are "is a"

      • Use composition when classes "has a"

      • May have roles which translate to interfaces. These roles may be implicit rather than explicit.

      • Use dependency injection rather than explicitly using classes in other classes.

      • Use Hashes for parameters. This helps prevent dependencies on method parameter order.

      • Use template design pattern when using inheritance.

      • Template design pattern should use hooks instead of using "super". User of super creates dependency.



    • Testing

      • Test from the general to the specific.

      • Test only the public interface of a class.

      • Use modules/mixins in test to verify interfaces (modules/mixins) in the code. Then include in all classes implementing interface.

      • Use modules/mixins in test to verify super classes. These then can be included in subclasses.

      • Use a singular module/mixin to verify subclasses act correctly in relation to super class. Then include in all subclasses.



    • SOLID

      • Single Responsibility

      • Open for extension, but Closed for modification

      • Liskov Substitution:  Subclasses stand in for parent classes

      • Interface Segregation:  Clients should only know the methods they use.   (Adapter pattern?)

      • Dependency Inversion




Ruby Magick: Include and Extend

24 September 2014

While wandering lost through the strange land of Rails code I stumbled upon some many bits of code. One particular bit that crossed my path was the /railties/lib/rails/generators/migration.rb code.

migration.rb


require 'active_support/concern'
require 'rails/generators/actions/create_migration'
module Rails
  module Generators
    # Holds common methods for migrations. It assumes that migrations has the
    # [0-9]*_name format and can be used by another frameworks (like Sequel)
    # just by implementing the next migration version method.
    module Migration
      extend ActiveSupport::Concern
      attr_reader :migration_number, :migration_file_name, :migration_class_name
      module ClassMethods
        def migration_lookup_at(dirname) #:nodoc:
          Dir.glob("#{dirname}/[0-9]*_*.rb")
        end
        def migration_exists?(dirname, file_name) #:nodoc:
          migration_lookup_at(dirname).grep(/d+_#{file_name}.rb$/).first
        end
##########code omitted here#################

    end
  end
end

Having never seen "ClassMethods" module in use, I decided to investigate. It turns out that this is a design pattern prevalent in Rails. Confused I decided to investigate using code examples. First we need to understand Class and Instance methods. Class methods are methods that belong to the class and are not available to an object instantiated from the class. Instance methods are just the opposite. They are methods that belong to an instantiated object but not to the class. The following code will illustrate this point.

ruby/language/include-extend$ ruby expected.rb

language/include-extend/expected.rb


class  Expected
  #Putting self in front of the method name makes it a class method
  def self.class_method
    puts "Expected.class_method succeeded!"
  end

  def instance_method
    puts "expected.instance_method succeeded!"
  end

end

puts ""
puts "Expected Code"
puts "Begin using class"
puts "--------------------------------------"
begin
  puts Expected.class_method
  puts Expected.instance_method
rescue
  puts "Expected.instance_method failed!"
  puts ""
end

puts "Begin using instantiated object"
puts "--------------------------------------"
expected = Expected.new

begin
  puts expected.instance_method
  puts expected.class_method
rescue
  puts "expected.class_method failed!"
end

Which when run gives us the following results

run expected.rb in command line


bash-4.2$ ruby expected.rb 

Expected Code
Begin using class
--------------------------------------
Expected.class_method succeeded!

Expected.instance_method failed!

Begin using instantiated object
--------------------------------------
expected.instance_method succeeded!

expected.class_method failed!

Having the basics under our belt let us take another step and talk about include and extend. Include and extend are used to include Modules into classes and other modules. Include "includes" instance methods and extends "includes" class methods. It can actually get quite a bit more complicated than this simple explanation. We will come back to this at the end.

Using include and extend we can write the following:

language/include-extend/using-module.rb


module UsingModule
  module InstanceMethods
    def instance_method
      puts "using_class.instance_method worked!"
    end
  end

  module ClassMethods
    def class_method
      puts "UsingClass.class_method worked!"
    end
  end
end


class UsingClass
  include UsingModule::InstanceMethods
  extend UsingModule::ClassMethods

end

puts ""
puts "Using Module Code"
puts "Begin using class instance"
puts "-------------------------------"
using_class = UsingClass.new()

begin
  puts using_class.instance_method
  puts using_class.class_method
rescue
  puts "using_class.class_method failed!"
end

puts ""
puts "Begin using class"
puts "-------------------------------"

begin
  puts UsingClass.class_method
  puts UsingClass.instance_method
rescue
  puts "UsingClass.instance_method failed!"
end

Which gives us similar results as expected.rb.

run using-module.rb in command line



bash-4.2$ ruby using-module.rb 

Using Module Code
Begin using class instance
-------------------------------
using_class.instance_method worked!

using_class.class_method failed!

Begin using class
-------------------------------
UsingClass.class_method worked!

UsingClass.instance_method failed!

Using-module.rb while an interesting experiment isn't what you will likely see. You are more likely to see the use of only a ClassMethods sub module along with included class method as shown next.

language/include-extend/confusing-code.rb


module ConfusingModule
  def self.included(base)
#    This commented out code is also seen.
#    The results are the same as the line below it.
#    base.send :extend, ClassMethods
    base.extend(ClassMethods)
  end

  def instance_method
    puts "using_class.instance_method worked!"
  end

  module ClassMethods
    def class_method
      puts "ConfusingClass.class_method worked!"
    end
  end
end


class ConfusingClass
  include ConfusingModule

end

puts ""
puts "Confusing Code"
puts "Begin using class instance"
puts "-------------------------------"
confusing_class = ConfusingClass.new()

begin
  puts confusing_class.instance_method
  puts confusing_class.class_method
rescue
  puts "confusing_class.class_method failed!"
end

puts ""
puts "Begin using class"
puts "-------------------------------"

begin
  puts ConfusingClass.class_method
  puts ConfusingClass.instance_method
rescue
  puts "ConfusingClass.instance_method failed!"
end

Which once again will produce similar results.

Terminal window in mysecurity directory



bash-4.2$ ruby confusing-code.rb 

Confusing Code
Begin using class instance
-------------------------------
using_class.instance_method worked!

confusing_class.class_method failed!

Begin using class
-------------------------------
ConfusingClass.class_method worked!

ConfusingClass.instance_method failed!

Clear as mud? Good! I highly recommend playing with this code to get a more intuitive grasp of how it works. We now proceed to how Rails does all of this with hidden magic. It does this with ActiveSupport::Concern. This next code example requires you to have the ActiveSupport gem installed.

language/include-extend/concerned-code.rb


require 'active_support'

module ConcernedModule
  extend ActiveSupport::Concern

  def instance_method
    puts "concerned_class.instance_method worked!"
  end

  module ClassMethods
    def class_method
      puts "ConcernedClass.class_method worked!"
    end
  end
end


class ConcernedClass
  include ConcernedModule

end

puts ""
puts "Concerned Code"
puts "Begin concerned class instance"
puts "-------------------------------"
concerned_class = ConcernedClass.new()

begin
  puts concerned_class.instance_method
  puts concerned_class.class_method
rescue
  puts "concerned_class.class_method failed!"
end

puts ""
puts "Begin concerned class"
puts "-------------------------------"

begin
  puts ConcernedClass.class_method
  puts ConcernedClass.instance_method
rescue
  puts "ConcernedClass.instance_method failed!"
end

Code which once again produces similar results.

Terminal window in mysecurity directory



bash-4.2$ ruby concerned-code.rb 

Concerned Code
Begin concerned class instance
-------------------------------
concerned_class.instance_method worked!

concerned_class.class_method failed!

Begin concerned class
-------------------------------
ConcernedClass.class_method worked!

ConcernedClass.instance_method failed!

ActiveSupport::Concern, among other things, searches for a ClassMethods sub module and extends it. This brings us to where we can understand a bit more of Rails code and the Ruby magick it employs. Finally lets look at one last piece of code that can confuse the use of extend. What happens if we call extend on an object?

language/include-extend/extend-confusion.rbb


module MoreConfusionModule

  def instance_method
    puts "more_confusion_class.instance_method worked!"
  end

  module ClassMethods
    def class_method
      puts "MoreConfusionClass.class_method worked!"
    end
  end
end

module Diabolical
  module ClassMethods
    def confuse
      puts "Haha i am not a class method!"
    end
  end
end



class MoreConfusionClass
  include MoreConfusionModule

end

puts ""
puts "MoreConfusion Code"
puts "Begin more_confusion class instance"
puts "-------------------------------"
more_confusion_class = MoreConfusionClass.new()

more_confusion_class.extend(Diabolical::ClassMethods)


begin
  puts more_confusion_class.instance_method
  puts more_confusion_class.class_method
rescue
  puts "more_confusion_class.class_method failed!"
end

puts ""
puts "Begin more_confusion class"
puts "-------------------------------"

begin
  puts MoreConfusionClass.class_method
  puts MoreConfusionClass.instance_method
rescue
  puts "MoreConfusionClass.instance_method failed!"
end


puts "-------------------------------"
puts more_confusion_class.confuse

The results of running this class may be somewhat suprising.

Terminal window in mysecurity directory



bash-4.2$ ruby extend-confusion.rb 

MoreConfusion Code
Begin more_confusion class instance
-------------------------------
more_confusion_class.instance_method worked!

more_confusion_class.class_method failed!

Begin more_confusion class
-------------------------------
MoreConfusionClass.instance_method failed!
-------------------------------
Haha i am not a class method!

The confuse method defined in Diabolical::ClassMethods mocks us! Extend assigns the methods to the object which is calling it. You do remember that in Ruby classes are also objects? So if you call extend from an object it will assign the methods to the object not the class.

Below are links to sources the first of which I found to be a fantastic resource.

Algorithmathon Day 19: Combinations

10 September 2013

The challenge for us today is to find all the possible combinations of a set of numbers. When determining combinations the order is not important. This means that 123 is the equivalent of 321. The solution of this problem reminds me of the old adage about taking one step back for every two steps forward. Which in effect is what we do to determine the possible combinations. The solution is very similar to the Permutations of a String solution. The difference being that we start in position that is equal to the combination length desired. We work our way backwards from this position to the beginning of the array/string. Every step we make backwards we find the permutations from that location forwards. When it is all done you have your combinations.

We first prepare our RSpec tests.
algorithm_array_spec.rb



require 'spec_helper'

describe AlgorithmArray do

  describe "Class" do
    it "should have method 'combinations'" do
      AlgorithmArray.method_defined?(:combinations).should be_true
    end
  end

  describe "Instance" do
    before(:each) do
    end

    it "should return 3 when '[].combinations(2).length' is called" do
      @array = AlgorithmArray.[](1,2,3)
      @array.combinations(2).length.should == 3
    end

    it "should return 10 when '[].combinations(3).length' is called" do
      @array = AlgorithmArray.[](1,2,3,4,5)
      @array.combinations(3).length.should == 10
    end

    it "should return 20 when '[].combinations(3).length' is called" do
      @array = AlgorithmArray.[](1,2,3,4,5,6)
      @array.combinations(3).length.should == 20
    end

    it "should return 15 when '[1,2,3,4,5,6].combinations(4).length' is called" do
      @array = AlgorithmArray.[](1,2,3,4,5,6)
      @array.combinations(4).length.should == 15
    end
  end
end

Finally the code to satisfy our tests.
algorithm_array.rb



class AlgorithmArray < Array
  attr_reader :iteration_count

  #
  #  Finds the possible combinations of elements in the array.
  # * *Args*
  #   - +combination_length+ -> The length of the combinations to be found.
  # * *Returns*
  #   - An array containing all the possible combinations.
  def combinations(combination_length)
    @iteration_count=0
    @level=0
    unless combination_length.nil? || combination_length < 1
      positions = combination_length - 1
      return_array = Array.new()
      build_array = self[0..positions]
      return_array[return_array.length]= build_array.join()
      build_array.pop()
      positions.downto(0) do | position |
        combinate_by_recursion(return_array,build_array,positions,position,position+1)
        @level = @level - 1
        build_array.pop()
      end
      return_array
    end
  end


  #
  #  Using recursion finds the remaining possible combinations of elements in the array.  The first
  #  combination is found in the combinations method.  The combinations method calls this method.
  # * *Args*
  #   - +return_array+ -> An array referenced to act as a container for the combinations.
  #   - +build_array+ ->  An array acting as a stack to hold the combination currently under construction.
  #   - +positions+ -> An integer that indicates the length of the combination
  #   - +current_position+ ->  The current position in the array being changed.
  #   - +end_position+ -> The position in the array whose value is being pushed into the current position.
  # * *Returns*
  #   - An array containing all the possible combinations.
  def combinate_by_recursion(return_array,build_array,positions,current_position,end_position)
    @level = @level + 1
    if positions < current_position
      return_array[return_array.length]= build_array.join()
      return
    end

    while end_position < self.length
      @iteration_count = @iteration_count + 1
      build_array.push(self[end_position])
      combinate_by_recursion(return_array,build_array,positions,current_position + 1,end_position + 1)
      @level = @level - 1
      build_array.pop()
      end_position=end_position+1
    end
  end  
end

Algorithmathon Day 18: Longest Common Substring Revisited

09 September 2013

We previously found the Longest Common Substring (LCS) using a trie on Day 13. Today our goal is to solve this problem a different way. This solution is O(n2) because it involves a loop within a loop. We will scan through the first string and for every character we will scan every character in the second string for a match. If a match is found we will then scan the next characters in both strings for a match. This means that the worst case scenario is when neither string has a matching sub-string. The solution should work something like this.

  1. Read next character from string one.
  2. Go to the beginning of string two.
  3. Read next character from string two.
  4. If the characters match read the next characters from both strings. Otherwise go to step 1.
  5. If the characters match go to step 3. Otherwise record the substring and to to step 1.

As always we begin with our RSpec tests.

algorithm_string_spec.rb



require 'spec_helper'

describe AlgorithmString do

  describe "Class" do
    it "should have method 'longest_common_substring'" do
      AlgorithmString.method_defined?(:longest_common_substring).should be_true
    end    
  end

  describe "Instance" do
    describe "Longest common substring method tests" do
      it "should return 'bcd' when ABCD.longest_common_substring(BCDE)  is called" do
        a_string= AlgorithmString.new('ABCD')
        a_string.longest_common_substring('BCDE').should == 'BCD'
      end

      it "should return 'try' when TRY.longest_common_substring(RETRY)  is called" do
        a_string= AlgorithmString.new('TRY')
        a_string.longest_common_substring('RETRY').should == 'TRY'
      end 

       it "should return 'FGH' when ABCDFGHXYZ.longest_common_substring(TSVPFGHARS)  is called" do
        a_string= AlgorithmString.new('ABCDFGHXYZ')
        a_string.longest_common_substring('TSVPFGHARS').should == 'FGH'
      end     
    end
  end
end

Now for our solution.

algorithm_string_spec.rb



class AlgorithmString < String

  #Find the longest common substring with the 
  #string_to_compare parameter.
  # * *Args*
  #   - +string_to_compare+ -> A string which is compared to this string instance to find the longest common substring
  # * *Returns*
  #   - A string that is the first longest common substring found. 
  def longest_common_substring(string_to_compare)
    @longest_begin = -1
    @longest_length = 0    
    unless self.length < 1 || string_to_compare.nil? || string_to_compare.length < 1
      @current_outer = 0
      while (@current_outer + @longest_length) < self.length
        @current_inner = 0
        while @current_inner < string_to_compare.length
          if self[@current_outer] == string_to_compare[@current_inner]
            process_first_character_match(string_to_compare)
            break
          end
          @current_inner = @current_inner + 1
        end
        @current_outer = @current_outer + 1
      end
    end
    self.slice(@longest_begin,@longest_length)
  end


  private

    #  Called from longest_common_substring when a first character match is found.
    #  Advances to the next character in both strings to look for a match.
    #
    #   - +string_to_compare+ -> A string which is compared to this string instance to find the longest common substring
    #
    # * *Returns*
    #   - A string that is the matching characters found. 
    def process_first_character_match(string_to_compare)
      current_begin=@current_outer
      current_length=1
      @current_outer = @current_outer + 1
      @current_inner = @current_inner + 1
      while @current_outer < self.length && @current_inner < string_to_compare.length
        if self[@current_outer] == string_to_compare[@current_inner]
            current_length=current_length + 1
        else
          break
        end
        @current_outer = @current_outer + 1
        @current_inner = @current_inner + 1
      end      
      if current_length > @longest_length
         @longest_begin=current_begin
         @longest_length = current_length
      end      
    end
end

Algorithmathon Day 17: Telephone Words

26 August 2013

It is easier for most humans to remember words rather than to remember numbers. Having only 10 numbers and 26 letters the numbers would need to double or triple up with letters. The history of the telephone keypad is interesting. For example it wasn't until mobile telephones became ubiquitous that the world was even using the same letters for the same numbers. The results of this world standard makes little since to me. We will view the correlations between letters and numbers in our code.

Our challenge will be to write a small program to list out the possible combinations of letters for a telephone number. I think of this problem as being a series of wheels with letters on the circumference. If each wheel represents a number then some wheels will have no letters on it while some will have three or even four letters. The first wheel starts spinning and when it reaches the first letter it starts spinning the the second wheel which starts spinning the third wheel and so on. For a seven digit number the cost could range from 7 to 47. The first being the case for the number 111-1111 and the second being 999-9999. Most numbers will fall towards the middle of these two extremes.

A solution will involve steps similar to the below.

  1. Read the number
  2. Read the first/next letter and place it in a stack
  3. If there is another number go to step 1.
  4. Remove the last letter from the stack
  5. Go to step 2

Seems pretty straightforward let's hop right into build our RSpec tests.

telephone_words_spec.rb



require 'spec_helper'

describe TelephoneWords do

  describe "Class" do
    it "should have method 'build_words'" do
      TelephoneWords.method_defined?(:build_words).should be_true
    end
  end

  describe "Instance" do

    it "should not return nil when 'build_words([2,2,2])' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2]
      telephone_words.build_words(number_array).should_not be_nil
    end

    it "should return 27 when 'build_words([2,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end 

    it "should return 27 when 'build_words([1,2,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [1,2,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end   

    it "should return 27 when 'build_words([2,2,2,1]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2,1]
      telephone_words.build_words(number_array).length.should == 27
    end 

    it "should return 27 when 'build_words([2,1,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,1,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end  

    it "should return 2916 when 'build_words([3,5,2,2,9,6,6]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [3,5,2,2,9,6,6]
      telephone_words.build_words(number_array).length.should == 2916
    end  
  end
end

Finally our solution.

telephone_words.rb



class TelephoneWords < Array
  
  def initialize()
    @number_dictionary = { 0=> [], 1 => [], 2 => ['A','B','C'], 3 => ['D','E','F'], 4 => ['G','H','I'], 5 => ['J','K','L'], 6 => ['M','N','O'], 7 => ['P','Q','R','S'], 8 => ['T','U','V'], 9 => ['W','X','Y','Z'] }
  end


  #Find all possible letter combinations from a telephone number.
  #
  #* *Args*    :
  #  - +telephone_number+ -> The telephone number to be analyzed.
  #* *Returns* :
  #  - An array containing strings representing all the possible letter combinations.
  def build_words(telephone_number)
    if telephone_number.nil? || telephone_number.length < 1
      return
    end
    return_results = Array.new()
    build_words_by_recursion(telephone_number,Array.new(),return_results,0)
    return return_results
  end

  private
    
  #Find all possible letter combinations from a telephone number by recursing
  #through the possible letter combinations.
  #
  #* *Args*    :
  #  - +telephone_number+ -> The telephone number to be analyzed.
  #  - +current_word+ -> The combinations of letters currently being put together to build a word.
  #  - +return_results+ -> An array used to store the combinations of letters
  #  - +depth+ -> Tracks which telephone number is currently being examined.
  #* *Returns* :
  #  - An array containing strings representing all the possible letter combinations.
    def build_words_by_recursion(telephone_number,current_word,return_results,depth)
      if depth > (telephone_number.length - 1)
        return_results[return_results.length]=current_word.join()
      end
      unless telephone_number[depth].nil?
        if telephone_number[depth] == 0 || telephone_number[depth] == 1
          current_word.push(telephone_number[depth].to_s)
          build_words_by_recursion(telephone_number,current_word,return_results,depth + 1)
          current_word.pop()
        else
          @number_dictionary[telephone_number[depth]].each { | letter |
            current_word.push(letter)
            build_words_by_recursion(telephone_number, current_word, return_results, depth + 1)
            current_word.pop()
          }          
        end
      end
    end
end

Algorithmathon Day 16: Permutations of a String

16 August 2013

Day 16's goal has turned out to be surprisingly fascinating. Permutations of a string have a solution that is a factor of the length of the string. This means that a string with four characters will have 24 solutions which is the result of 4 x 3 x 2 x 1. This then can be our ideal goal and is represented by n!. We want to find the permutations of a string with the number of operations being equal or close to the multiplied factors of the string length.

This goal turned out to be difficult to achieve. In fact we will see that we do not achieve it. We will explore three solutions each of which provides a somewhat improved solution to the prior one. Even so we will not reach our goal. Searching for the solution was very interesting and I only stopped because I needed to move on to other subjects.

The number of iterations is the length of the string raised to the power of the number of factors in the string. A string of length 3 has 6 permutations. Which is the factorial of 3. 3 x 2 x 1 = 6. Research suggests an answer of n! x n x n.

We should now construct our RSpec tests. This time around we will leave one test failing because we never reach our ideal goal of n! iterations.

algorithm_string_spec.rb



require 'spec_helper'

shared_examples "a permutation" do | target_string, target_method, goal |

  describe "When #{target_method}' is called" do
    before(:each) do
      @string = AlgorithmString.new(target_string)
    end

    it "should not return nil" do
      @string.send(target_method).should_not be_nil
    end

    it "should return #{goal}" do
      @string.send(target_method).length.should == goal
    end 

    it "should return #{goal} when 'iteration_count' is called" do
      @string.send(target_method)
      @string.iteration_count.should == goal
    end 

    it "should match @verify_array" do
      verify_array = target_string.chars.to_a.permutation.map(&:join)
      local_array = @string.send(target_method)
      verify_array.each { | value |
        local_array.include?(value).should be_true
      }
    end
  end
end

describe AlgorithmString do  

  describe "Class" do
    it "should have method 'permutate'" do
      AlgorithmString.method_defined?(:permutate).should be_true
    end

    it "should have method 'permutate2'" do
      AlgorithmString.method_defined?(:permutate2).should be_true
    end

    it "should have method 'permutate3'" do
      AlgorithmString.method_defined?(:permutate3).should be_true
    end

    it "should have method 'iteration_count'" do
      AlgorithmString.method_defined?(:iteration_count).should be_true
    end    
  end

  describe "Instance" do

    describe "'ABC' permutations" do
      it_should_behave_like "a permutation", "ABC","permutate", 6 
      it_should_behave_like "a permutation", "ABC","permutate2", 6 
      it_should_behave_like "a permutation", "ABC","permutate3", 6 

    end
    describe "'ABCD' permutations" do
      it_should_behave_like "a permutation", "ABCD","permutate", 24 
      it_should_behave_like "a permutation", "ABCD","permutate2", 24 
      it_should_behave_like "a permutation", "ABCD","permutate3", 24

    end
    describe "'ABCDE' permutations" do
      it_should_behave_like "a permutation", "ABCDE","permutate", 120
      it_should_behave_like "a permutation", "ABCDE","permutate2", 120
      it_should_behave_like "a permutation", "ABCDE","permutate3", 120

    end    
  end 
end

Our code to meet these tests.

algorithm_string.rb



class AlgorithmString < String
  attr_reader :iteration_count

  #Determine all possible orderings of characters in a string
  #
  #  - returns an array with all the possible orderings.
  def permutate()
    @iteration_count=0
    return_array = Array.new()
    permutate_by_recursion(return_array,Array.new(),Array.new(),0)
    return_array
  end

  def permutate2()
    @iteration_count=0    
    return_array = Array.new()
    string_array = self.split('')
    permutate_by_recursion2(return_array,string_array,0)
    return_array
  end

  def permutate3()
    @iteration_count=0    
    return_array = Array.new()
    string_array = self.split('')
    permutate_by_recursion3(return_array,string_array,"")
    return_array
  end  

  private
  def permutate_by_recursion(return_array,build_array,tracking_array, current_position)
    final_position= self.length - 1

    if current_position > final_position
      return_array[return_array.length]=build_array.join()
      return
    end
    
    for i in 0..final_position
      @iteration_count = @iteration_count + 1
      unless tracking_array[i]
        build_array.push(self[i])
        tracking_array[i]=true
        permutate_by_recursion(return_array,build_array,tracking_array,current_position + 1)
        build_array.pop()
        tracking_array[i]=false
      end
    end
  end

  def permutate_by_recursion2(return_array, string_array, current_position)
    final_position= self.length - 1

    if current_position > final_position
      return_array[return_array.length]=string_array.join()
      return
    end
    
    for i in current_position..final_position
      @iteration_count = @iteration_count + 1
      switch_character(string_array,current_position,i)
      permutate_by_recursion2(return_array,string_array,current_position + 1)
      switch_character(string_array,current_position,i)
    end
  end  

  def switch_character(string_array,first,second)    
    value_holder=string_array[second]
    string_array[second]=string_array[first]
    string_array[first]=value_holder
  end

  def permutate_by_recursion3(return_array, string_array, string_value)
    if string_array.length == 1
      return_array[return_array.length]=string_value + string_array[0]
      return
    end
    string_array.each_with_index { | value, index |
      @iteration_count = @iteration_count + 1
      prefix = string_value + value
      temp_array = string_array.clone()
      temp_array.delete_at(index)
      permutate_by_recursion3(return_array, temp_array, prefix)
    }

  end 
  
end

As you can see the first solution permutate was not very efficient and required iterations greater than n3 and n! x n2. Our second solution permutate2 switches values around with the string and is able to do considerably better. It solves the problem somewhere between n2 and n x n2. This solutions is my favorite because it seems the least resource intensive. Finally we have permutate3 which uses the fewest iterations/recursive calls. The difference is not insignificant and the this solution could also be applied to permutate2 to reduce its number of recursive calls.

Algorithmathon Day 15: Binary Search

12 August 2013

On day 15 we will be looking into the Binary Search. It is a relatively straight forward algorithm for searching ordered data. Its a simple process where you pick an arbitrary location to start. You compare the value you are searching for with the value from the location selected. If the search value is higher you pick a value to the right for the next search. The search value might be lower in which case you would pick a value to the left. The key is to track the highest and lowest known value locations and to pick the middle location between them. This would work something like the following.

  1. The first value and the last value are the low and high locations.
  2. Pick the value in the middle of the the high and low values. Call this current value.
  3. If the high and low values are equal then return nothing.
  4. If the high location is greater than the number of values return nothing
  5. If the low location is less than the first value location return nothing
  6. If the search value is less than the current value make the current value location the high location and go to step 2.
  7. If the search value is greater than the current value make the current location the low location and go to step 2.
  8. Return the value location

As always we begin with our RSpec tests.

algorithm_array_spec.rb



require 'spec_helper'

describe AlgorithmArray do

  describe "Class" do
    it "should have method 'new_find'" do
      AlgorithmArray.method_defined?(:new_find).should be_true
    end
  end

  describe "Instance" do


    describe "Start search from default location" do
      before(:each) do
        @array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
      end

      it "should return 2 when 'new_find(7)' is called" do
        @array.new_find(7).should == 2
      end

      it "should return 0 when 'new_find(1)' is called" do
        @array.new_find(1).should == 0
      end

      it "should return 8 when 'new_find(29)' is called" do
        @array.new_find(29).should == 8
      end

      it "should return 4 when 'new_find(13)' is called" do
        @array.new_find(13).should == 4
      end 

      it "should return nil when 'new_find(443)' is called" do
        @array.new_find(443).should be_nil
      end      
    end

    describe "Start search from end location" do
      before(:each) do
        @array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
      end

      it "should return 2 when 'new_find(7,9)' is called" do
        @array.new_find(7,9).should == 2
      end

      it "should return 0 when 'new_find(1,9)' is called" do
        @array.new_find(1,9).should == 0
      end

      it "should return 8 when 'new_find(29,9)' is called" do
        @array.new_find(29,9).should == 8
      end

      it "should return 4 when 'new_find(13,9)' is called" do
        @array.new_find(13,9).should == 4
      end    
    end

    describe "Start search from first location" do
      before(:each) do
        @array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
      end

      it "should return 2 when 'new_find(7,0)' is called" do
        @array.new_find(7,0).should == 2
      end

      it "should return 0 when 'new_find(1,0)' is called" do
        @array.new_find(1,0).should == 0
      end

      it "should return 8 when 'new_find(29,0)' is called" do
        @array.new_find(29,0).should == 8
      end

      it "should return 4 when 'new_find(13,0)' is called" do
        @array.new_find(13,0).should == 4
      end    
    end    
  end

end

And the code to satisfy these tests.

algorithm_array_spec.rb



class AlgorithmArray < Array
  #Find the location of the matching element in the array.
  #
  #* *Args*    :
  #+search_object+:: The object being looked for.
  #* *Returns* :
  #  - an integer representing the location in the array the matching element is located.             
  def new_find(search_object,start_location=nil)
    if start_location.nil?
      start_location=self.length/2
    end
    new_find_by_recursion(search_object,start_location,self.length-1,0)
  end

  private

  #Find the location of the matching element in the array.
  #
  #* *Args*    :
  #+search_object+:: The object being looked for.
  #+search_location+:: The location in the array to compare values.
  #+high+:: Tracks the lowest location in the array that is know to contain a value greater than the search_object.
  #+high+:: Tracks the highest location in the array that is know to contain a value less than the search_object.
  #* *Returns* :
  #  - an integer representing the location in the array the matching element is located or nil if it is not found.               
  def new_find_by_recursion(search_object,search_location,high,low)
    if search_location >= self.length || search_location < 0 || high == low
      return
    end
    if self[search_location] < search_object
      low = search_location
      next_location = high - ((high - low)/2)
      new_find_by_recursion(search_object,next_location,high,low)
    elsif self[search_location] > search_object
      high = search_location
      next_location = low + ((high - low)/2)      
      new_find_by_recursion(search_object,next_location,high,low)
    else
      return_value = search_location
    end
  end

end

Algorithmathon Day 14: String Manipulations

02 August 2013

Today's goal will be to write algorithms for a few different types of string manipulations. Our first goal will be to remove all characters, in an array, from a string. The second will be to reverse all of the characters in a string. Third will be to convert a string to an integer. Finally we will end with converting an integer to a string. The Ruby String class already has some methods that cover this functionality. We will pretend that the do not exist and write our own.

To solve our first problem we will use a straight linear approach which will have a cost at worst of the length of the string times the length of the array. Depending on how Array#include is implemented it might be as low as just the length of the array. Though this would incur additional storage costs.

To reverse all of the characters in a string we will utilize recursion. By counting down from the outside in we will have a cost of log(n).

Our third goal can be achieved by converting each character in the string to its ordinal value. These values start with 48 for "0" on up to "9". Thus if we subtract 48 we have the numeric value represented by the character. Then we just have to multiply it by 10 raised to the power of the character position starting from the right.

The final method is the reverse of our third goal. We will use division and modulus to break apart our number. When we add 48 to it we will have the ordinal value of our characters. Then we simply need to concatenate the characters together.

Of course we must have our RSpec tests done first.

algorithm_string_spec.rb



require 'spec_helper'

describe AlgorithmString do

  describe "Class" do
    it "should have method 'new_remove'" do
      AlgorithmString.method_defined?(:new_remove).should be_true
    end
    it "should have method 'new_reverse!'" do
      AlgorithmString.method_defined?(:new_reverse!).should be_true
    end

    it "should have method 'string_to_integer'" do
      AlgorithmString.method_defined?(:string_to_integer).should be_true
    end 
    it "should have method 'integer_to_string'" do
      AlgorithmString.method_defined?(:integer_to_string).should be_true
    end   
  end

  describe "Instance" do

    before(:each) do
      @string = AlgorithmString.new('ABCABCABCABC')
    end

    it "should not be nil" do
      @string.should_not be_nil
    end

    it "should return nil when 'new_remove()' is called" do
      @string.new_remove(nil).should be_nil
    end

    it "should return 'AAAA' when 'new_remove([B,C,D])' is called" do
      @string.new_remove(['B','C','D']).should == 'AAAA'
    end

    it "should return 'CBACBACBACBA' when 'new_reverse!()' is called" do
      @string.new_reverse!().should == 'CBACBACBACBA'
    end

    it "should return 'ABCABCDABCABC' when 'new_reverse!()' is called" do
      @string = AlgorithmString.new('ABCABCDABCABC')
      @string.new_reverse!().should == 'CBACBADCBACBA'
    end

    it "should return -245 when 'string_to_integer()' is called" do
      @string = AlgorithmString.new('-245')
      @string.string_to_integer.should == -245
    end

    it "should return '-245' when 'integer_to_string(-245)' is called" do
      @string = AlgorithmString.new('test')
      @string.integer_to_string(-245).should == '-245'
    end
  end

end

The code to satisfy our tests.

algorithm_string.rb



class AlgorithmString < String


  #Remove all characters from string
  #
  #+character_array+:: An array of characters to be removed from the string.
  def new_remove(character_array)
    unless character_array.nil? || !character_array.class.name.eql?('Array')
      return_io=StringIO.new()      
      self.each_char { | char |
        unless character_array.include?(char)
          return_io.putc char
        end
      }
      return_value = return_io.string
    end
    return_value
  end

  #Reverse the order of the characters in the string
  def new_reverse!()
    unless self.length < 1    
      reverse_by_recursion(0)
    end
  end


  #this method will return the integer value of the current
  #string or throw and "Invalid integer format" exception
  def string_to_integer
    power_counter = self.length - 1
    return_value=0
    is_negative=false
    self.each_char { | character_number |
      if character_number == "-"
        is_negative=true
      else
        character_value = character_number.chr.ord
        character_value = character_value - 48
        if character_value > -1 && character_value < 10
          return_value = return_value + (character_value * (10 ** power_counter))
        else
          raise "Invalid integer format"
        end
      end
      power_counter = power_counter - 1  
    }
    if is_negative
      return_value = return_value * -1
    end
    return_value
  end


  #Converts and integer to a string
  #
  #+integer_value+:: An integer
  def integer_to_string(integer_value)
    return_value=""
    prefix = ''
    if integer_value < 0
     prefix="-"
     integer_value = integer_value * -1
    end
    while integer_value > 0
      return_value = ((integer_value % 10) + 48).chr + return_value
      integer_value = integer_value / 10
    end
    prefix + return_value
  end

  private
  
  #helper method to new_reverse!() counts the number of 
  #recursions.  Switches characters from the end to the front
  #working from the ends to the middle.
  #
  #+counter+:: Tracks the distance from the ends. 
  def reverse_by_recursion(counter)
    unless counter >= (self.length / 2)
      holder=self[counter]
      self[counter]=self[self.length - 1 - counter]
      self[self.length - (1 + counter)]=holder
      counter = counter + 1
      reverse_by_recursion(counter)
    end
    self
  end

end

If you want to earn bonus points convert the fourth method to utilize StringIO. This would lessen the overhead of string concatenation.

Algorithmathon Day 13: Trie Longest Common Substring

30 July 2013

Instead of more String manipulations, as I indicated, we will be looking into Tries and the Longest Common Substring problem. A friend mentioned the problem to me and I became very interested in Tries as a result.

A Trie is a type of Tree that proves itself useful in string manipulation. To find the Longest Common Substring (LCS) a Suffix Trie is particularly useful. You create a Suffix tree by taking all the possible suffixes of a string and adding it to the Trie. We can find the LCS by adding all of the suffixes for two strings to a Trie with a label for each string. Then finding the longest path with both string labels will give us the LCS.


  1. Label strings

  2. Find all suffixes of the Strings

  3. Add all suffixes to the trie.

  4. Find next pointer which points to a branch with both string labels

  5. Follow the branch until it no longer has both string labels.

  6. Record the resulting sequence of letters

  7. If the sequence of letters is longer than the last sequence of letters remember it.

  8. Goto step 4

The cost of adding the strings should be n(n-1). For string S1 and string S2 this would be S1(S1 - 1) + S2(S2 - 1). If S1 represents the the longer string. The searching should have a cost of S1 + (26 * S2(S2 - 1)). Where S2 is the shorter of the two strings.

Descriptions of Suffix Tries often refer to them being Compressed Trie variant. To reduce complexity I have chose not to compress the trie.

We will need several RSpec tests to verify the needed functionality for adding strings to the Trie.

trie_spec.rb



  describe "Class" do
    it "should have method 'root'" do
      Trie.method_defined?(:root).should be_true
    end 

    it "should have method 'add'" do
      Trie.method_defined?(:add).should be_true
    end 
  end

  describe "Instance" do


    describe "Add method tests" do
      before(:each) do
        @trie = Trie.new()
        @trie.add("ABCDEFG",0)
        @trie.add("DEFGHIJK",1)
      end

      it "should not return nil when 'root' is called" do
        @trie.root.should_not be_nil
      end

  
      it "should not return nil when 'root[65]' is called" do
        @trie.root[65].should_not be_nil
      end

      it "should not return nil when 'root[68]' is called" do
        @trie.root[68].should_not be_nil
      end    

      it "should not return nil when 'root[65][66]' is called" do
        @trie.root[65][66].should_not be_nil
      end        

      it "should not return nil when 'root[65][66][67][68][69][70][71]' is called" do
        @trie.root[65][66][67][68][69][70][71].should_not be_nil
      end

      it "should not return 1 when 'root[65][66][67][68][69][70][71].length' is called" do
        @trie.root[65][66][67][68][69][70][71].length.should == 2
      end 

      it "should not return 1 when 'root[65][66][67][68][69][70][71][0]' is called" do
        @trie.root[65][66][67][68][69][70][71][0].should == 1
      end

      describe "Markers indicating a specific string" do
        it "should not return nil when 'root[68][1]' is called" do
          @trie.root[68][1].should_not be_nil
        end 

        it "should return true when 'root[68][1][1]' is called" do
          @trie.root[68][1][1].should be_true
        end

        it "should return false when 'root[68][1][0]' is called" do
          @trie.root[68][1][0].should be_false
        end    
      end    
    end
  end
end

The code below satisfies these tests and provides the core functionality of our Trie. Rather than building a custom node Class we are using Arrays.

trie.rb



class Trie
  attr_reader :root

  def initialize()
    @root = Array.new(100)
  end

  def add(new_string,marker=0)
    unless new_string.nil? || new_string.length < 1
      add_by_recursion(@root,new_string,marker)
    end
  end

  private
  def add_by_recursion(current_node_array,new_string,marker)
    first_char=new_string.slice!(0)
    unless first_char.nil?
      first_char_number=first_char.chr.ord
      if current_node_array[first_char_number].nil?
        current_node_array[first_char_number] = Array.new()
      end 
      add_marker(current_node_array[first_char_number],marker)   
      add_by_recursion(current_node_array[first_char_number],new_string,marker)
    else
      current_node_array[0]=1
    end
  end

  def add_marker(current_node_array,marker)
    if current_node_array[1].nil?
      current_node_array[1]=Array.new()
    end
    current_node_array[1][marker]=true
  end

end

We now need to write a method to add all the suffixes of a string to the trie.

trie_spec.rb (excerpt)



#code omitted here
    it "should have method 'add_suffixes'" do
      Trie.method_defined?(:add_suffixes).should be_true
    end 
#code omitted here
    describe "Add_suffix method tests" do
      before(:each) do
        @trie = Trie.new()
        @trie.add_suffixes("ABCDEFG",0)
        @trie.add_suffixes("FGHIJK",1)
      end

      it "should not return nil when 'root[65]' is called" do
        @trie.root[65].should_not be_nil
      end      

      it "should not return nil when 'root[68]' is called" do
        @trie.root[68].should_not be_nil
      end

      it "should not return nil when 'root[72]' is called" do
        @trie.root[72].should_not be_nil
      end

      it "should not return nil when 'root[75]' is called" do
        @trie.root[75].should_not be_nil
      end

      it "should return false when 'root[69][1][1]' is called" do
        @trie.root[69][1][1].should be_false
      end

      it "should return true when 'root[69][1][0]' is called" do
        @trie.root[69][1][0].should be_true
      end

      it "should return true when 'root[70][1][0]' is called" do
        @trie.root[70][1][0].should be_true
      end

      it "should return true when 'root[70][1][1]' is called" do
        @trie.root[70][1][1].should be_true
      end

      it "should return true when 'root[71][1][0]' is called" do
        @trie.root[71][1][0].should be_true
      end

      it "should return true when 'root[71][1][1]' is called" do
        @trie.root[71][1][1].should be_true
      end

      it "should return false when 'root[72][1][0]' is called" do
        @trie.root[72][1][0].should be_false
      end

      it "should return true when 'root[72][1][1]' is called" do
        @trie.root[72][1][1].should be_true
      end

    end
#code omitted here

The code to satisfy these tests is quite straightforward. We add all possible suffixes of the string with a marker.

trie.rb



#code omitted here
  def add_suffixes(new_string,marker)
    unless new_string.nil? || new_string.length < 1
      string_end=new_string.length-1
      for counter in 0..string_end
        add(new_string[counter..string_end],marker)
      end
    end
  end
#code omitted here

Now all that is required is for us to find the LCS. Which we can do by searching for branches of the trie that have markers from both strings and returning the longest one.

trie_spec.rb (excerpt)



#code omitted here
    it "should have method 'longest_common_substring'" do
      Trie.method_defined?(:longest_common_substring).should be_true
    end    
#code omitted here
    describe "Longest common substring method tests" do
      it "should return 'bcd' when Trie.longest_common_substring(ABCD,BCDE)  is called" do
        trie= Trie.new()
        trie.longest_common_substring('ABCD','BCDE').should == 'BCD'
      end

      it "should return 'try' when Trie.longest_common_substring(TRY,RETRY)  is called" do
        trie= Trie.new()
        trie.longest_common_substring('TRY','RETRY').should == 'TRY'
      end 

       it "should return 'FGH' when Trie.longest_common_substring(ABCDFGHXYZ,TSVPFGHARS)  is called" do
        trie= Trie.new()
        trie.longest_common_substring('ABCDFGHXYZ','TSVPFGHARS').should == 'FGH'
      end     
    end
#code omitted here

Finally the code to satisfy the latest RSpec tests will give us our functionality.

trie.rb



#code omitted here
  def longest_common_substring(string_zero, string_one)
    add_suffixes(string_zero,0)
    add_suffixes(string_one,1)
    longest_common_substring_by_recursion()
  end
#code omitted here
  def longest_common_substring_by_recursion()
    root_end=@root.length-1
    latest_stack=Array.new()
    for counter in 65..root_end
      unless @root[counter].nil?
        if @root[counter][1][0] && @root[counter][1][1]
          tracking_stack=Array.new()
          tracking_stack.push(counter.chr)
          longest_common_substring_by_recursion_follow_branch(@root[counter],tracking_stack)
          if tracking_stack.length > latest_stack.length
            latest_stack = tracking_stack
          end
        end 
      end
    end
    latest_stack.join
  end

  def longest_common_substring_by_recursion_follow_branch(current_node_array,tracking_stack)
    array_end=current_node_array.length-1
    for counter in 65..array_end
      unless current_node_array[counter].nil?
        if current_node_array[counter][1][0] && current_node_array[counter][1][1]
          tracking_stack.push(counter.chr)
          longest_common_substring_by_recursion_follow_branch(current_node_array[counter],tracking_stack)
        end 
      end
    end
  end
#code omitted here

Algorithmathon Day12: String First Non-repeated Character

26 July 2013

This entry starts a period of string manipulation. Today's goal will be to return the first non-repeated character in a string. Ruby provides us with a String class that will be easy to subclass. If we have string "ABABCAB" we want to find the letter "C". One way to approach this is to compare every letter in the string to every other letter in the string. This however would have a n2 cost. If we shortened the string by one character on each pass we could reduce that to n * (n-1). Faster but still effectively n2. If however we use a hash to track and count the letters we can reduce this to n + 26. In this case we are assuming the use of only A through Z. Let's jump right into the initial RSpec tests.

algorithm_string_spec.rb



require 'spec_helper'

describe AlgorithmString do

  describe "Class" do
    it "should have method 'first_nonrepeated'" do
      AlgorithmString.method_defined?(:first_nonrepeated).should be_true
    end
  end

  describe "Instance" do

    before(:each) do
      @string = AlgorithmString.new()
    end

    it "should not be nil" do
      @string.should_not be_nil
    end

  end

end

A very basic class will satisfy these tests.

algorithm_string.rb




class AlgorithmString < String
  def first_nonrepeated()
    
  end
end

Now we need something with more substance so lets build some additional tests and the code to satisfy them.

algorithm_string_spec.rb (excerpt)



  #code omitted here
    it "should return nil when 'first_nonrepeated()' method is called" do
      @string.first_nonrepeated().should_not be_nil
    end

    it "should return nil when 'first_nonrepeated()' method is called" do
      @string.first_nonrepeated().should == 'C'
    end
  #code omitted here

algorithm_string.rb



class AlgorithmString < String
  def first_nonrepeated()
    string_array=self.to_s.split(//)
    character_count=Hash.new()
    return_value=nil
    string_array.each_with_index { | character_outer, index |
      if character_count[character_outer].nil?
         character_count[character_outer] = 1
      else
        character_count[character_outer] = character_count[character_outer] + 1
      end
    }
    character_count.each { | key, value |
      if value < 2
        return_value=key
      end
    }
    return_value
  end
end

We now have a working method that gives us a solution. Next time we will be adding a method which removes characters from a string.

Configuring Weblogic 10.3 to use Struts2 Convention Plugin

26 July 2013

It can be a bit of a pain to configure Weblogic Server to work with Struts2. This is to document what is needed so that I will have it recorded and it will also be available to others. Most of the heavy lifting was done by Amit in his article Getting Struts 2.1 to work in Weblogic 10.3. Several good comments as well.

There are some differences. I am using Maven 3 as my build tool and the Struts version is 2.3.8. First off you will need to have a Manifest file in your webapp/war in the META-INF folder. My Manifest file is completely empty. If you are familiar with Maven war projects it would have a path similar to the following



    project_root_folder/webapp/src/main/resources/META-INF/Manifest

You will also need to update your struts.properties file which will be located someplace similar to the below.



    project_root_folder/webapp/src/main/resources/struts.properties

The below entries will need to be added to the struts.properties file. The include jars entry basically adds the jar containing the actions back to the path. This is necessary because Weblogic Server changes several things about the EAR and WAR files that you deploy to the server.

struts.properties (excerpt)



#stuff omitted here
struts.convention.action.mapAllMatches = true
struts.convention.action.includeJars=.*?/_wl_cls_gen.*?jar(!/)?
struts.convention.action.fileProtocols=jar,zip
#stuff omitted here

Algorithmathon Day 11: Binary Search Tree Lowest Common Ancestor

25 July 2013

The Lowest Common Ancestor (LCA) is the node furthest down the tree that is an ancestor of two other nodes. In the tree depicted below the LCA of child nodes 10 and 30 would be 20 and the LCA of 20 and 90 would be 50.

Binary Tree
Binary Tree

When we first start considering the Lowest Common Ancestor (LCA) problem it is quite natural for it to seem quite difficult. One might start considering searching for each child node while keeping an ancestor list. The better solution turns out to be quite simple. Up until now we have been writing algorithms to solve problems in spite of the data structure. This time the nature of a Binary Search Tree (BST) itself will help us solve the problem. We know that the right side numbers are the larger numbers and the left side is the smaller numbers. It turns out that the LCA will be the first node that is between our two numbers.

  1. Get the root node
  2. Find the current node value
  3. If both child values are less than the current node value goto step 2 with the lesser/left child node as the target
  4. If both child values are greater than the current node value goto step 2 with the greater/right child node as the target
  5. Otherwise the current node is the LCA

Armed with this knowledge we can write our tests and follow it with our code.

binary_search_tree_spec.rb (excerpt)



#code omitted here
    it "should have method 'lowest_common_ancestor'" do
      BinarySearchTree.method_defined?(:lowest_common_ancestor).should be_true
    end
#code omitted here
      it "should not return nil with 'lowest_common_ancestor(10,30)' is called" do
        @tree.lowest_common_ancestor(10,30).should_not be_nil
      end

      it "should return 20 with 'lowest_common_ancestor(10,30)' is called" do
        @tree.lowest_common_ancestor(10,30).should == 20
      end      

      it "should return 50 with 'lowest_common_ancestor(20,90)' is called" do
        @tree.lowest_common_ancestor(20,90).should == 50
      end

      it "should return 150 with 'lowest_common_ancestor(130,180)' is called" do
        @tree.lowest_common_ancestor(130,180).should == 150
      end
#code omitted here

binary_search_tree.rb (excerpt)



#code omitted here
  def lowest_common_ancestor(first_number, second_number)
    lowest_common_ancestor_by_recursion(@root,first_number, second_number)
  end
#code omitted here
  def  lowest_common_ancestor_by_recursion(current_node,first_number, second_number)
    unless current_node.nil?
      if current_node.data > first_number && current_node.data > second_number
        lowest_common_ancestor_by_recursion(current_node.lesser,first_number, second_number)
      elsif current_node.data < first_number && current_node.data < second_number
        lowest_common_ancestor_by_recursion(current_node.greater,first_number, second_number)
      else
        current_node.data
      end
    end
  end
#code omitted here

Tomorrow we will start String manipulation.

Algorithmathon Day 10: Pre-order Traversal

24 July 2013

Today's goal is to build a Depth First Preorder Traversal. This algorithm is where a tree is searched by checking the current node, searching the children to the left and finally searching the children to the right. Following this pattern will search a tree from the outer edges left to right. Day 9's code will be our starting point and we should only need to build our tree and write the traversal method(s). The algorithm we will follow has the following steps.

  1. Get the root node
  2. Record the node value
  3. If a lesser node exists goto step 2 with lesser as the target
  4. If a greater node exists goto step 2 with greater as the target

We should start with an RSpec test to construct and verify our tree structure. A tree that should look like the diagram below.

Binary Tree
Binary Tree

binary_search_tree_spec.rb (excerpt)



#code omitted here
    describe "Verify Depth First Traversal" do
      before(:each) do
        @tree = BinarySearchTree.new()
        @tree.add(BinarySearchTreeNode.new(100))
        @tree.add(BinarySearchTreeNode.new(50))
        @tree.add(BinarySearchTreeNode.new(20))
        @tree.add(BinarySearchTreeNode.new(70))
        @tree.add(BinarySearchTreeNode.new(10))
        @tree.add(BinarySearchTreeNode.new(30))
        @tree.add(BinarySearchTreeNode.new(60))
        @tree.add(BinarySearchTreeNode.new(80))
        @tree.add(BinarySearchTreeNode.new(90))
        @tree.add(BinarySearchTreeNode.new(40))

        @tree.add(BinarySearchTreeNode.new(150))
        @tree.add(BinarySearchTreeNode.new(120))
        @tree.add(BinarySearchTreeNode.new(170))
        @tree.add(BinarySearchTreeNode.new(110))
        @tree.add(BinarySearchTreeNode.new(130))
        @tree.add(BinarySearchTreeNode.new(160))
        @tree.add(BinarySearchTreeNode.new(180))
        @tree.add(BinarySearchTreeNode.new(190))
        @tree.add(BinarySearchTreeNode.new(140))
      end

      it "should have a properly constructed tree" do
        @tree.root.should_not be_nil
        @tree.root.data.should == 100

        @tree.root.lesser.should_not be_nil
        @tree.root.lesser.data.should == 50

        @tree.root.lesser.greater.should_not be_nil
        @tree.root.lesser.greater.data.should == 70

        @tree.root.lesser.lesser.should_not be_nil
        @tree.root.lesser.lesser.data.should == 20

        @tree.root.lesser.lesser.lesser.should_not be_nil
        @tree.root.lesser.lesser.lesser.data.should == 10

        @tree.root.greater.should_not be_nil
        @tree.root.greater.data.should == 150

        @tree.root.greater.greater.should_not be_nil
        @tree.root.greater.greater.data.should == 170

        @tree.root.greater.lesser.should_not be_nil
        @tree.root.greater.lesser.data.should == 120

        @tree.root.greater.greater.greater.should_not be_nil
        @tree.root.greater.greater.greater.data.should == 180

        @tree.root.greater.greater.greater.greater.should_not be_nil
        @tree.root.greater.greater.greater.greater.data.should == 190
      end      
    end
#code omitted here

This test should and does pass without adding any additional code. We now can be confident of the tree structure we will be working with. Now we should add tests to specify what results our traversal should return.

binary_search_tree_spec.rb (excerpt)



#code omitted here
      it "should not return nil when 'depth_preorder()' is called" do
        @tree.depth_preorder().should_not be_nil
      end

      it "should not return 19 when 'depth_preorder().length' is called" do
        @tree.depth_preorder().length.should == 19
      end

      it "should return 100 when 'depth_preorder()[0]' is called" do
        @tree.depth_preorder()[0].should == 100
      end

      it "should return 30 when 'depth_preorder()[4]' is called" do
        @tree.depth_preorder()[4].should == 30
      end 

      it "should return 90 when 'depth_preorder()[9]' is called" do
        @tree.depth_preorder()[9].should == 90
      end     

      it "should return 150 when 'depth_preorder()[10]' is called" do
        @tree.depth_preorder()[10].should == 150
      end     
      it "should return 130 when 'depth_preorder()[13]' is called" do
        @tree.depth_preorder()[13].should == 130
      end     

      it "should return 170 when 'depth_preorder()[15]' is called" do
        @tree.depth_preorder()[15].should == 170
      end 
#code omitted here

All of these tests will fail and we must write a recursive method to meet these needs. Fortunately Binary Trees lend themselves very well to recursive solutions. The plan is to pass an array into the methods to record the path taken by the algorithm.

binary_search_tree.rb (excerpt)



#code omitted here
  def depth_preorder()
    return_value=Array.new()
    depth_preorder_by_recursion(@root,return_value)
    return_value
  end
#code omitted here
  def depth_preorder_by_recursion(current_node,tracker)
    unless current_node.nil?
      tracker.push(current_node.data)
      unless current_node.lesser.nil?
        depth_preorder_by_recursion(current_node.lesser,tracker)
      end
      unless current_node.greater.nil?
        depth_preorder_by_recursion(current_node.greater,tracker)
      end
    end
  end
#code omitted here

With our tests passing now we have successfully written pre-order traversal using recursion. Let's look into how we would achieve the same results using iteration. It can be very difficult to envision using iteration to solve a problem that so obviously lends itself to recursion.

Unfortunately, because recursion is so intrinsic to the definition of a preorder traversal, you may have trouble finding an entirely different iterative algorithm to use in place of the recursive algorithm. In such a case, the best course of action is to understand what is happening in the recursion and try to emulate the process iteratively Programming Interviews Exposed

This was a very helpful piece of advice and it was much easier to solve the problem while keeping it in mind. Essentially we need to use a stack and loop through nodes emulating recursion. An array will satisfy the need for a stack. The tests and code are below.

binary_search_tree_spec.rb (excerpt)



#code omitted here
      it "should not return nil when 'depth_preorder_alt()' is called" do
        @tree.depth_preorder_alt().should_not be_nil
      end

      it "should not return 19 when 'depth_preorder_alt().length' is called" do
        @tree.depth_preorder_alt().length.should == 19
      end

      it "should return 100 when 'depth_preorder_alt()[0]' is called" do
        @tree.depth_preorder_alt()[0].should == 100
      end

      it "should return 30 when 'depth_preorder_alt()[4]' is called" do
        @tree.depth_preorder_alt()[4].should == 30
      end 

      it "should return 90 when 'depth_preorder_alt()[9]' is called" do
        @tree.depth_preorder_alt()[9].should == 90
      end     

      it "should return 150 when 'depth_preorder_alt()[10]' is called" do
        @tree.depth_preorder_alt()[10].should == 150
      end     
      it "should return 130 when 'depth_preorder_alt()[13]' is called" do
        @tree.depth_preorder_alt()[13].should == 130
      end     

      it "should return 170 when 'depth_preorder_alt()[15]' is called" do
        @tree.depth_preorder_alt()[15].should == 170
      end
#code omitted here

binary_search_tree.rb (excerpt)



#code omitted here
  def depth_preorder_alt()
    return_value=Array.new()
    depth_preorder_by_iteration(@root,return_value)
    return_value
  end
#code omitted here
  def depth_preorder_by_iteration(start_node,tracker)
    current_node=start_node
    the_stack=Array.new()
    while !current_node.nil?
      tracker.push(current_node.data)
      unless current_node.greater.nil?
        the_stack.push(current_node.greater)
      end
      unless current_node.lesser.nil?
        the_stack.push(current_node.lesser)
      end
      current_node=the_stack.pop()
    end
  end
#code omitted here

On Algorithmathon Day 11 we will be looking into finding the Lowest Common Ancestor of two nodes in a tree.

Algorithmathon Day 9: Trees Base

23 July 2013

The goal for today is to setup the basics for trees. The basic object for trees is the node. A node is a collection of references/pointers to other nodes. Lets write the tests and code to satisfy this requirement. I will be concentrating on the BinarySearchTreeNode object. You will find a TreeNode and a BinaryTreeNode in the code on GitHub.

binary_search_tree_node_spec.rb



require 'spec_helper'

describe BinarySearchTreeNode do

  describe "Class" do
    it "should have method 'greater'" do
      BinarySearchTreeNode.method_defined?(:greater).should be_true
    end

    it "should have method 'lesser'" do
      BinarySearchTreeNode.method_defined?(:lesser).should be_true
    end 

     it "should have method 'data'" do
      BinarySearchTreeNode.method_defined?(:data).should be_true
    end 

    it "should have method 'less_than?'" do
      BinarySearchTreeNode.method_defined?(:less_than?).should be_true
    end     

    it "should have method 'greater_than?'" do
      BinarySearchTreeNode.method_defined?(:greater_than?).should be_true
    end     
  end

  describe "Instance" do

    before(:each) do
      @node = BinarySearchTreeNode.new(5)
    end

    it "should not be nil" do
      @node.should_not be_nil
    end

    it "should not throw an exeption because greater, lesser and parent are nil" do
      expect {parent = BinarySearchTreeNode.new(5)}.to_not raise_error
    end

    it "should throw an exeption because lesser is more than greater" do
      lesser = BinarySearchTreeNode.new(10)
      greater = BinarySearchTreeNode.new(5)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
    end

    it "should throw an exeption because lesser is not nil and greater is" do
      lesser = BinarySearchTreeNode.new(10)
      expect { parent = BinarySearchTreeNode.new(7,lesser) }.to raise_error
    end

    it "should not throw an exeption because lesser is less than greater" do
      lesser = BinarySearchTreeNode.new(5)
      greater = BinarySearchTreeNode.new(10)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to_not raise_error
    end

    it "should not throw an exeption because lesser is nil and greater is not" do
      greater = BinarySearchTreeNode.new(10)
      expect {parent = BinarySearchTreeNode.new(7,nil,greater)}.to_not raise_error
    end    

    it "should not throw an exeption because lesser and greater are nil" do
      expect {parent = BinarySearchTreeNode.new(7)}.to_not raise_error
    end    

    it "should throw an exeption because lesser and greater are equal" do
      lesser = BinarySearchTreeNode.new(10)
      greater = BinarySearchTreeNode.new(10)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
    end    

    it "should throw an exeption because lesser and parent are equal" do
      lesser = BinarySearchTreeNode.new(7)
      greater = BinarySearchTreeNode.new(10)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
    end

    it "should throw an exeption because greater and parent are equal" do
      lesser = BinarySearchTreeNode.new(3)
      greater = BinarySearchTreeNode.new(7)
      expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
    end    

    it "should return true when lesser.lesser_than?(greater) is called" do
      lesser = BinarySearchTreeNode.new(3)
      greater = BinarySearchTreeNode.new(7)
      lesser.less_than?(greater).should be_true
    end    

    it "should return false when greater.greater_than?(lesser) is called" do
      lesser = BinarySearchTreeNode.new(3)
      greater = BinarySearchTreeNode.new(7)
      greater.greater_than?(lesser).should be_true
    end
  end

end

As can be seen we have added several tests that enforce the attributes that make a Binary Search Tree. With the code below to satisfy the tests we can move on to building a Binary Search Tree.

tree_node.rb



class BinarySearchTreeNode
  attr_accessor :lesser, :greater
  attr_reader :data

  def initialize(data,lesser=nil,greater=nil)
    @data=data
    self.lesser=lesser
    self.greater=greater
    if (!self.lesser.nil? && self.greater.nil?) || (!self.lesser.nil? && (self.lesser.data > self.greater.data))
      throw "The lesser exceeds the greater"
    end
   
    if !self.lesser.nil? && !self.data.nil? && self.lesser.data == self.data
      throw "The lesser is equal to the parent"
    end
    
    if !self.greater.nil? && !self.data.nil? && self.greater.data == self.data
      throw "The greater is equal to the parent"
    end    
    
    if !self.lesser.nil? && !self.greater.nil? && self.lesser.data == self.greater.data
      throw "The lesser is equal to the parent"
    end
  end

  def less_than?(target_node)
    if target_node.nil?
      raise "The target_node is nil!"
    else
      if @data < target_node.data
        true
      else
        false
      end
    end
  end

  def greater_than?(target_node)
    if target_node.nil?
      raise "The target_node is nil!"
    else
      if @data > target_node.data
        true
      else
        false
      end
    end
  end 
end

What do we know about a binary search tree? We know that it needs a starting node know as the "root". If we are going to be able to write algorithms against a tree we need to be able to build a tree. This means we need a "root" attribute and an "add" method. We should add several tests to specify the functionality we need. These tests come quite naturally if you use the Test Driven Development methodology.

binary_search_tree_spec.rb



require 'spec_helper'

describe BinarySearchTree do

  describe "Class" do
    it "should have method 'root'" do
      BinarySearchTree.method_defined?(:root).should be_true
    end

    it "should have method 'add'" do
      BinarySearchTree.method_defined?(:add).should be_true
    end    
  end

  describe "Instance" do

    before(:each) do
      @tree = BinarySearchTree.new()
    end

    it "should have node(5) as the root when passed into constructor" do
      node = BinarySearchTreeNode.new(5)
      tree = BinarySearchTree.new(node)
      tree.root.should_not be_nil
      tree.root.data.should == 5
    end

    it "should have node(6) as the root when add(node(5)) is called" do
      node = BinarySearchTreeNode.new(5)
      tree = BinarySearchTree.new()
      tree.add(node)
      tree.root.should_not be_nil
      tree.root.data.should == 5
    end    

    it "should have add(node(5)) as the lesser of the root" do
      node = BinarySearchTreeNode.new(5)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
      tree.add(node)
      tree.root.lesser.should_not be_nil
      tree.root.lesser.data.should == 5
    end

    it "should have add(node(15)) as the greater of the root" do
      node = BinarySearchTreeNode.new(15)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
      tree.add(node)
      tree.root.greater.should_not be_nil
      tree.root.greater.data.should == 15
    end 

    it "should have add(node(10)) raise an error" do
      node = BinarySearchTreeNode.new(10)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
      expect { tree.add(node) }.to raise_error
    end   

    it "should have add(node(50)) as the lesser of the root.lesser" do
      node1 = BinarySearchTreeNode.new(75)
      node2 = BinarySearchTreeNode.new(50)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
      tree.add(node1)
      tree.add(node2)
      tree.root.lesser.should_not be_nil
      tree.root.lesser.lesser.should_not be_nil
      tree.root.lesser.lesser.data.should == 50
    end

    it "should have add(node(85)) as the greater of the root.lesser" do
      node1 = BinarySearchTreeNode.new(75)
      node2 = BinarySearchTreeNode.new(85)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
      tree.add(node1)
      tree.add(node2)
      tree.root.lesser.should_not be_nil
      tree.root.lesser.greater.should_not be_nil
      tree.root.lesser.greater.data.should == 85
    end 

     it "should have add(node(150)) as the greater of the root" do
      node1 = BinarySearchTreeNode.new(150)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
      tree.add(node1)
      tree.root.greater.should_not be_nil
      tree.root.greater.data.should == 150
    end 

     it "should return 125 when it recieves the root.greater.lesser.data call" do
      node1 = BinarySearchTreeNode.new(150)
      node2 = BinarySearchTreeNode.new(75)
      node3 = BinarySearchTreeNode.new(125)
      tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
      tree.add(node1)
      tree.add(node2)
      tree.add(node3)
      tree.root.greater.should_not be_nil
      tree.root.greater.lesser.should_not be_nil
      tree.root.greater.lesser.data.should == 125
    end

  end

end

binary_search_tree.rb



class BinarySearchTree
  attr_reader :root

  def initialize(root=nil)
    @root=root
  end

  def add(new_node)
    if new_node.nil?
      new_node
    else
      if @root.nil?
        @root = new_node
      else
        add_by_recursion(@root,new_node)
      end
    end
  end

  private

  def add_by_recursion(current_node,new_node)
    if current_node.nil?
      current_node
    else
      if current_node.greater_than?(new_node)
        if current_node.lesser.nil?
          current_node.lesser=new_node
        else
          add_by_recursion(current_node.lesser,new_node)
        end            
      elsif current_node.less_than?(new_node)
        if current_node.greater.nil?
          current_node.greater=new_node
        else
          add_by_recursion(current_node.greater,new_node)
        end
      else
        raise "Node matches existing node" + new_node.data.to_s
      end 
    end
  end

end

We now have a Binary Search Tree with enough basic functionality to make it useful. Tomorrow we will look into depth first searches.

Algorithmathon Day 8: Double Linked List Unflattening

22 July 2013

On Day 8 we will be unflattening the Double Linked List (DoLL) that we flattened on Day 7 of the Algorithmathon. As always we will be following the Rules of Algorithmathon. For your viewing pleasure the source code is also available. How do we go about achieving this unflattening? It seems likely, what we need to do is to reverse the flattening process.

We should be able to reuse our test that verified our helper methods to help us write our first test.

double_linked_list_spec.rb (excerpt)



#code omitted here
    it "should have method 'unflatten!'" do
      DoubleLinkedList.method_defined?(:element_at).should be_true
    end  
#code omitted here
    it "should have the correct non flat list when the 'unflatten!' method is called." do
      list = build_master_list()
      list.flatten!()
      list.unflatten!()
      list.length().should == 12
      list.element_at(0).child.length().should == 6
      list.element_at(0).child.last().child.length().should == 8
      list.element_at(4).child.length().should == 8
      list.element_at(4).child.element_at(2).child.length().should == 8
      list.element_at(11).child.length().should == 3
      list.element_at(11).child.element_at(0).child.length().should == 6
    end

#code omitted here

To try to grasp how we might solve this problem we can list out the rules we used for flattening the list.

  1. Starting at the head check each element for a child
  2. If the element has a child
    1. link the child elements into the top list.
    2. Return to step 1 with the child list's first element as a target.
  3. Continue to the next element. (Which will be the first element in the child list if one existed)

What needs to be done to reverse this process? Well we should probably start at the beginning much like the flattening process.

  1. Starting at the head check each element for a child
  2. If the element has a child
    1. unlink the child elements from the top list.
    2. Return to step 1 with the child list's first element as a target.
  3. Continue to the next element. (Which will be the element after the last element in the child list if one existed)

While it sounds correct this plan will prove ultimately futile. When we flattened our list we started at the bottom and worked our way up. If we reverse this process we need to start at the top and work our way down. It would look something more like this.

  1. Starting at the head check each element for a child
  2. If the element has a child goto step 1 with the child's first element as a target.
  3. Make the elements next node equal to the next node of the last element of the child list.
  4. Continue to the next element. (Which will be the element after the last element in the child list if one existed)

In this case the code seems easier to understand than the aforementioned steps.

double_linked_list.rb (excerpt)



#code omitted here
  def unflatten!()
    unflatten_by_recursion(@head)
  end
#code omitted here
  def unflatten_by_recursion(element)
    unless element.nil?
      if element.child.nil?
        unflatten_by_recursion(element.next_node)
      else
        unflatten_by_recursion(element.child.element_at(0))        
        @length = @length - element.child.length()
        element.next_node=element.child.last.next_node        
      end
    end
  end
#code omitted here

Tomorrow we will start our first foray into Trees and Graphs.

Algorithmathon Day 7: Double Linked List Flattening

19 July 2013

Today's goal is to flatten a list of lists into one long list. This means in addition to having a prev_node and next_node attribute the element will also have a child attribute which may or may not point to another list. An Illustration of this is below.

Double Linked List with children
Double Linked List with children

We will be using the Double Linked List (DoLL) base code from Day 6. Follow this link for Algorithmathon Rules. The Source Code is also available. Adding the child attribute to the element would be a good first step. We should write a test and the code to satisfy it as shown below.

double_linked_list_element_spec.rb (excerpt)



require 'spec_helper'
#code omitted here
    it "should have a 'child' method" do
      DoubleLinkedListElement.method_defined?(:child).should be_true
    end
#code omitted here

double_linked_list_element.rb



require 'spec_helper'
class DoubleLinkedListElement
  attr_accessor :next_node, :prev_node, :child, :data

  def initialize(data=nil,next_node=nil,prev_node=nil,child=nil)
    self.data=data
    self.next_node=next_node
    self.prev_node=prev_node
    self.child=child
  end
end

In order to adequately test that the list flattening is working as desired we need a list that isn't flat. Since we will need this list in multiple tests the best way to handle this is to use helper methods. Building such a list could be error prone and we should build a test to verify our list is constructed correctly.

double_linked_list_spec.rb (excerpt)



#code omitted here
    it "should build a non flat list correctly" do
      list = build_master_list()
      list.length().should == 12
      list.element_at(0).child.length().should == 6
      list.element_at(4).child.length().should == 8
      list.element_at(11).child.length().should == 16
    end         
#code omitted here

With the failing test written we can now write our helpers to construct our list.

spec_helper.rb



$LOAD_PATH.unshift File.expand_path('lib')

require 'double_linked_list'
require 'double_linked_list_element'



def add_elements(the_list)
  the_list.add(DoubleLinkedListElement.new("one"))
  the_list.add(DoubleLinkedListElement.new("two"))
  the_list.add(DoubleLinkedListElement.new("three"))
  the_list.add(DoubleLinkedListElement.new("four"))
end

def build_list(number_list)
  the_list=DoubleLinkedList.new()
  number_list.each { | the_number |
    the_list.add(DoubleLinkedListElement.new(the_number.to_s))
  }
  the_list
end

def build_master_list()
  the_list=build_list((1..12))
  the_list.element_at(0).child=build_list(13..18)
  the_list.element_at(4).child=build_list(19..26)
  the_list.element_at(11).child=build_list(27..42)
  the_list
end

The uneven list builder constructed we should move onto writing tests which give our expectations of the flatten! method.

double_linked_list_spec.rb (excerpt)



#code omitted here
    it "should have a length of 42 when it receives the 'flatten!' message" do
      list = build_master_list()
      list.flatten!()
      list.length().should == 42
    end 

    it "should return '13' when it receives the message 'element_at(12).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(1).data.should == '13'
    end 

    it "should return '18' when it receives the message 'element_at(6).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(6).data.should == '18'
    end

    it "should return '2' when it receives the message 'element_at(7).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(7).data.should == '2'
    end   
#code omitted here

The tests are all passing. It's Miller time! Kicking back with my BBC Bourbon Barrel Stout, I discuss what we have done so far. You of course are welcome to drink the beverage of your choice:) Suddenly, we realize we haven't accounted for a child who also has a child! This means we will need to go back and update our tests and the helper methods. Methods which are capable of handling a structure similar to the one illustrated below.

Double Link List with children having children
Double Link List with children having children

double_linked_list_spec.rb (excerpt)



#code omitted here
    it "should build a non flat list correctly" do
      list = build_master_list()
      list.length().should == 12
      list.element_at(0).child.length().should == 6
      list.element_at(0).child.last().child.length().should == 8
      list.element_at(4).child.length().should == 8
      list.element_at(4).child.element_at(2).child.length().should == 8
      list.element_at(11).child.length().should == 3
      list.element_at(11).child.element_at(0).child.length().should == 6
    end          
#code omitted here

spec_helper.rb (excerpt)



#code omitted here
def build_master_list()
  the_list=build_list((1..12))
  first_child_list=build_list(13..18)
  second_child_list=build_list(19..26)
  first_child_list.last().child=second_child_list
  the_list.element_at(0).child=first_child_list

  first_child_list=build_list(27..34)
  second_child_list=build_list(35..42)
  first_child_list.element_at(2).child=second_child_list
  the_list.element_at(4).child=first_child_list


  first_child_list=build_list(43..45)
  second_child_list=build_list(46..51)
  first_child_list.element_at(0).child=second_child_list  
  the_list.element_at(11).child=first_child_list
  the_list
end
#code omitted here

We now have a list that has children which in turn also have children. Unfortunately tests that are already written are now failing and new tests need to be written. Being RSpecofiles (™ pending) we hop right into some tests.

double_linked_list_spec.rb (excerpt)



#code omitted here
    it "should have a length of 51 when it receives the 'flatten!' message" do
      list = build_master_list()
      list.flatten!()
      list.length().should == 51
    end 

    it "should return '13' when it receives the message 'element_at(12).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(1).data.should == '13'
    end 

    it "should return '18' when it receives the message 'element_at(6).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(6).data.should == '18'
    end

    it "should return '19' when it receives the message 'element_at(7).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(7).data.should == '19'
    end 

    it "should return '5' when it receives the message 'element_at(18).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(18).data.should == '5'
    end

    it "should return '27' when it receives the message 'element_at(19).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(19).data.should == '27'
    end


    it "should return '51' when it receives the message 'element_at(48).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(48).data.should == '51'
    end 

    it "should return '45' when it receives the message 'element_at(50).data'" do
      list = build_master_list()
      list.flatten!()
      list.element_at(50).data.should == '45'
    end
#code omitted here

Several tests are failing and we need to update the code in our DoLL by rewriting the flatten_by_recursion method.

double_linked_list.rb (excerpt)



#code omitted here
  def flatten_by_recursion(element)
    unless element.nil?
      if element.child.nil?
        flatten_by_recursion(element.next_node)
      else
        relink(element)
        flatten_by_recursion(element.next_node)
      end
    end
  end

  def relink(element)
    tail = element.child.last()
    head = element.child.element_at(0)
    next_node = element.next_node
    element.next_node=head
    tail.next_node=next_node
    @length = @length + element.child.length()
  end
#code omitted here

All our tests are passing and this looks like a good place to stop. Tomorrow we will look into adding an unflatten! method.

Algorithmathon Day 6: Double Linked List Base

18 July 2013

Below is the code to be used as the base starting with Day 7 of the Algorithmathon. We have our RSpec tests along with our Double Linked List (DoLL) Element and the DoLL itself. This code will be used as the starting point for most of the Algorithms involving DoLL. The code for which can be found on GitHub.

We start with our tests.

double_linked_list_element_spec.rb



require 'spec_helper'

describe DoubleLinkedListElement do
  describe "Class" do
    it "should have a 'next_node' method" do
      DoubleLinkedListElement.method_defined?(:next_node).should be_true
    end
    it "should have a 'prev_node' method" do
      DoubleLinkedListElement.method_defined?(:prev_node).should be_true
    end    
    it "should have a 'data' method" do
      DoubleLinkedListElement.method_defined?(:data).should be_true
    end

  end
end

double_linked_list_spec.rb



require 'spec_helper'

describe DoubleLinkedList do

  describe "Class" do
    it "should have method 'last'" do
      DoubleLinkedList.method_defined?(:last).should be_true
    end

    it "should have method 'add'" do
      DoubleLinkedList.method_defined?(:add).should be_true
    end

    it "should have method 'length'" do
      DoubleLinkedList.method_defined?(:length).should be_true
    end 

    it "should have method 'element_at'" do
      DoubleLinkedList.method_defined?(:element_at).should be_true
    end   
  end

  describe "Instance" do

    before(:each) do
      @list = DoubleLinkedList.new()
    end

    it "should return nil when 'last()' is called" do
      @list.last().should be_nil
    end

    it "should not return nil when 'last()' is called" do
      add_elements(@list)
      @list.last().should_not be_nil
    end
    
    it "should return 'four' when 'last().data' is called" do
      add_elements(@list)
      @list.last().data.should == "four"
    end 

     it "should return 4 when 'length' is called" do
      add_elements(@list)
      @list.length().should == 4
    end 

     it "should return 'one' when 'element_at(0).data' is called" do
      add_elements(@list)
      @list.element_at(0).data.should == 'one'
      @list.element_at(1).data.should == 'two'
      @list.element_at(2).data.should == 'three'
      @list.element_at(3).data.should == 'four'
    end     

  end

end

Then we write our code to satisfy our tests.

double_linked_list_element.rb



class DoubleLinkedListElement
  attr_accessor :next_node, :prev_node, :data

  def initialize(data=nil,next_node=nil,prev_node=nil)
    self.data=data
    self.next_node=next_node
    self.prev_node=prev_node
  end
end

double_linked_list.rb



require 'double_linked_list_element'

class DoubleLinkedList
  attr_reader :head, :tail, :length

  def initialize()
    @length=0
  end

  def add(element)
    if @head.nil?
      @head = element
      @tail = element
      @length=1
    else
      @tail.next_node=element
      element.prev_node=@tail
      @tail=element
      @length = @length + 1
    end
  end

  def last()
    @tail
  end 

  def length()
    @length
  end

  def element_at(position_count)
    if position_count >= 0
      retrieve_forward_by_recursion(@head,position_count,0)
    end
  end

  private
    def retrieve_forward_by_recursion(element,position_count,current_count)
      unless element.nil?
        if current_count == position_count
          element
        else
          current_count=current_count + 1
          retrieve_forward_by_recursion(element.next_node,position_count,current_count)
        end
      end
    end

end

Food for thought is to consider how the Double Linked List (DoLL) would change the solutions we wrote for the Single Linked List (SLL). For example the 'element_at' method is basically the same method as the 'retrieve' method we wrote for the SLL. With the DoLL we could compare the position being requested and start from the tail or the head depending on which one is closer.

Algorithmathon Day 5: Single Linked List Nth to the Last Element

17 July 2013

Our challenge today will be to retrieve the nth element from the tail of a Single Linked List (SLL). We will start with the SLL Base code found here. If you want to jump ahead and see all of the code at once the Source is found here on GitHub. Constraints and rules are also available.

We will be adding the 'retrieve' method which will take an integer as a parameter. If the integer is positive it will return an element counted from the head of the list. If the integer is negative it will retrieve the element counted from the tail of the list. Our first test will be the following.

single_linked_list_spec.rb (excerpt)



#code omitted here
    it "should have method 'retrieve'" do
      SingleLinkedList.method_defined?(:retrieve).should be_true
    end  
#code omitted here
    it "should return the 5th object from the tail when 'retrieve(-5)' is called" do
      target = SingleLinkedListElement.new("target")
      add_elements(@list)
      @list.add(target)
      add_elements(@list)
      @list.retrieve(-5).eql?(target).should be_true
    end
#code omitted here

With tests in the Red we need to modify the SLL so that they turn Green. While working on solving this problem I realized that I could solve the counting backwards problem by counting forward. This resulted in the code below.

single_linked_list.rb



#code omitted here
  def retrieve(position_count)
    if position_count == 0
      nil
    end
    if position_count > 0
      retrieve_forward_by_recursion(@head,position_count,0)
    else
      count = length()
      count = count + position_count + 1
      retrieve_forward_by_recursion(@head,count,0)
    end
  end
#code omitted here
    def retrieve_forward_by_recursion(element,position_count,current_count)
      unless element.nil?
        current_count=current_count + 1
        if current_count == position_count
          element
        else
          retrieve_forward_by_recursion(element.next_node,position_count,current_count)
        end
      end
    end
#code omitted here

This solution seems almost to easy. Lets add some additional tests to verify.

single_linked_list_spec.rb (excerpt)



#code omitted here
    it "should return the 5th object from the head when 'retrieve(5)' is called" do
      target = SingleLinkedListElement.new("target")
      add_elements(@list)
      @list.add(target)
      add_elements(@list)
      @list.retrieve(5).eql?(target).should be_true
    end    

    it "should return the head when 'retrieve(1)' is called" do
      target = SingleLinkedListElement.new("target")
      @list.add(target)
      add_elements(@list)
      @list.retrieve(1).eql?(target).should be_true
    end

    it "should return the tail when 'retrieve(-1)' is called" do
      target = SingleLinkedListElement.new("target")
      add_elements(@list)
      add_elements(@list)
      @list.add(target)
      @list.retrieve(-1).eql?(target).should be_true
    end

    it "should return the head when 'retrieve(-1)' is called" do
      target = SingleLinkedListElement.new("target")
      @list.add(target)
      @list.retrieve(-1).eql?(target).should be_true
    end
#code omitted here

All of the tests are passing! So we are done ... yes? Maybe not. Our current solution requires almost two passes through the SLL. We could do it with only one pass if we track the nth position back from the current position. To keep the code simple I will allow myself to use an array in this solution.

single_linked_list.rb (excerpt)



#code omitted here
  def retrieve(position_count)
    if position_count == 0
      nil
    end
    if position_count > 0
      retrieve_forward_by_recursion(@head,position_count,0)
    else
#      count = length()
#      count = count + position_count + 1
#      retrieve_forward_by_recursion(@head,count,0)
      position_count = position_count * -1
      retrieve_nth_from_forward_by_recursion(@head,Array.new(),position_count,0)
    end
  end
#code omitted here
    def retrieve_nth_from_forward_by_recursion(element,nth_elements,position_count,current_count)
      unless element.nil?
        current_count = current_count + 1
        if current_count >= position_count
          nth_elements.push(element)
          if nth_elements.length > position_count
            nth_elements.delete_at(0)
          end
        end
        retrieve_nth_from_forward_by_recursion(element.next_node,nth_elements,position_count,current_count)        
      else
        if nth_elements.length > 0
          nth_elements[0]
        end
      end
    end    
#code omitted here

I think we are done for the day. Tomorrow we will start looking into list flattening.

Algorithmathon Day 4: Single Linked List Remove, Insert After, Insert Before

16 July 2013

Once again we will be working with a Single Linked List (SLL) starting with the SLL Base found here. Our goal for today will be to add remove, insert_after and insert_before methods the SLL base class. Source code found here on GitHub. If you haven't already read them, rules for the Algorithmathon can be found here.

As a first step we should create our first RSpec tests for remove.

single_linked_list_spec.rb (excerpt)



#code omitted here
    it "should have method 'remove'" do
      SingleLinkedList.method_defined?(:remove).should be_true
    end
#code omitted here

     it "should return removed object  when 'remove' is called" do
      first = SingleLinkedListElement.new("first")
      @list.add(first)
      @list.remove(first).eql?(first).should be_true
    end 

#code omitted here

Now that we have our failing tests lets update the SLL so that they will pass.

single_linked_list.rb



require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def add(element)
    if @head.nil?
      @head = element
    else
      last_element=last()
      last_element.next_node=element
    end
  end

  def remove(element)
    remove_by_recursion(@head,element,nil)
  end

  def last()
    last_element=SingleLinkedListElement.new()
    last_by_recursion(@head,last_element)
    last_element.next_node
  end        

  private
  def last_by_recursion(element,last_element)
    unless element.nil?
      last_element.next_node=element
      unless element.next_node.nil?
        last_by_recursion(element.next_node,last_element)
      end
    end
  end

  def remove_by_recursion(element,match_element,previous_element)
    if element.nil?
      element
    else
      if element == match_element
        if previous_element.nil?
          @head=element.next_node
        else
          previous_element.next_node=element.next_node
        end
        element
      end
    end
  end    
end

Having added the remove and the remove_by_recursion methods our tests are now passing. Now lets add multiple objects in a new test to make sure it still works under those conditions. Our new test add elements after the first/head element.

single_linked_list_spec.rb (excerpt)



#code omitted here
     it "should return removed object  when 'remove' is called and object is the head among many" do
      first = SingleLinkedListElement.new("first")
      @list.add(first)
      add_elements(@list)
      @list.length().should == 5
      @list.remove(first).eql?(first).should be_true
      @list.length().should == 4
    end  
#code omitted here

Whew! That one passed. What about if we try to remove the tail of the list?

single_linked_list_spec.rb (excerpt)



#code omitted here
    it "should return removed object  when 'remove' is called and object is the last among many" do
      last = SingleLinkedListElement.new("last")
      add_elements(@list)
      @list.add(last)
      @list.length().should == 5
      @list.remove(last).eql?(last).should be_true
      @list.length().should == 4
    end  
#code omitted here

Ooops! It failed this test. We need to go back and look at our method. Looks like we had some faulty logic in remove_by_recursion so lets update it to the below.

single_linked_list.rb



#code omitted here
  def remove_by_recursion(element,match_element,previous_element)
    if element.nil?
      element
    else
      if element.eql?(match_element)
        if previous_element.nil?
          @head=element.next_node
        else
          previous_element.next_node=element.next_node
        end
        element
      else
        remove_by_recursion(element.next_node,match_element,element)
      end
    end
  end 

#code omitted here

Rerunning our RSpec test we see that they are all now passing. What if our element is placed in the middle of several other elements? We should add another test to see if our remove method still works under these conditions.

single_linked_list_spec.rb (excerpt)



#code omitted here
    it "should return removed object  when 'remove' is called and object is the in the middle of many" do
      last = SingleLinkedListElement.new("last")
      add_elements(@list)
      @list.add(last)
      add_elements(@list)
      @list.length().should == 9
      
      @list.remove(last).eql?(last).should be_true
      @list.length().should == 8      
    end
#code omitted here

Yay! This test passed so we are looking pretty good. Lets move one to insert_after. For the sake of brevity I will add all the tests at once.

single_linked_list_spec.rb (excerpt)



#code omitted here
     it "should return the parent object  when 'insert_after' targets the middle of a list" do
      middle = SingleLinkedListElement.new("middle")
      after = SingleLinkedListElement.new("after")
      add_elements(@list)
      @list.add(middle)
      add_elements(@list)
      middle_next=middle.next_node
      @list.length().should == 9
      @list.insert_after(middle,after).eql?(middle).should be_true
      middle.next_node.eql?(after).should be_true
      after.next_node.eql?(middle_next).should be_true
      @list.length().should == 10
    end 

    it "should return the parent object  when 'insert_after' targets the head of a list" do
      head = SingleLinkedListElement.new("head")
      after = SingleLinkedListElement.new("after")
      @list.add(head)
      add_elements(@list)
      head_next=head.next_node
      @list.length().should == 5
      @list.insert_after(head,after).eql?(head).should be_true
      head.next_node.eql?(after).should be_true
      after.next_node.eql?(head_next).should be_true
      @list.length().should == 6
    end

    it "should return the parent object  when 'insert_after' targets the tail of a list" do
      last = SingleLinkedListElement.new("last")
      after = SingleLinkedListElement.new("after")
      add_elements(@list)
      @list.add(last)
      last_next=last.next_node
      @list.length().should == 5
      @list.insert_after(last,after).eql?(last).should be_true
      last.next_node.eql?(after).should be_true
      after.next_node.eql?(last_next).should be_true
      @list.length().should == 6
    end
#code omitted

With three failing tests we code our method so that it will pass.

single_linked_list.rb (excerpt)




#code omitted here
  def insert_after(target_element, new_element)
    if new_element.nil?
      new_element
    else
      insert_after_by_recursion(@head, target_element, new_element)
    end
  end
#code omitted here
  def insert_after_by_recursion(current_element,target_element,new_element)
    if current_element.nil?
      current_element
    else
      if current_element.eql?(target_element)
        new_element.next_node=current_element.next_node
        current_element.next_node=new_element
        current_element
      else
        insert_after_by_recursion(current_element.next_node,target_element,new_element)
      end
    end
  end

#code omitted here

Repeat and rinse for insert_before.

single_linked_list_spec.rb (excerpt)



#code omitted here
     it "should return the parent object  when 'insert_after' targets the middle of a list" do
      middle = SingleLinkedListElement.new("middle")
      after = SingleLinkedListElement.new("after")
      add_elements(@list)
      @list.add(middle)
      add_elements(@list)
      middle_next=middle.next_node
      @list.length().should == 9
      @list.insert_after(middle,after).eql?(middle).should be_true
      middle.next_node.eql?(after).should be_true
      after.next_node.eql?(middle_next).should be_true
      @list.length().should == 10
    end 

    it "should return the parent object  when 'insert_after' targets the head of a list" do
      head = SingleLinkedListElement.new("head")
      after = SingleLinkedListElement.new("after")
      @list.add(head)
      add_elements(@list)
      head_next=head.next_node
      @list.length().should == 5
      @list.insert_after(head,after).eql?(head).should be_true
      head.next_node.eql?(after).should be_true
      after.next_node.eql?(head_next).should be_true
      @list.length().should == 6
    end

    it "should return the parent object  when 'insert_after' targets the tail of a list" do
      last = SingleLinkedListElement.new("last")
      after = SingleLinkedListElement.new("after")
      add_elements(@list)
      @list.add(last)
      last_next=last.next_node
      @list.length().should == 5
      @list.insert_after(last,after).eql?(last).should be_true
      last.next_node.eql?(after).should be_true
      after.next_node.eql?(last_next).should be_true
      @list.length().should == 6
    end
#code omitted

With three failing tests we code our method so that it will pass.

single_linked_list.rb (excerpt)




#code omitted here
  def insert_before(target_element, new_element)
    if new_element.nil?
      new_element
    else
      insert_before_by_recursion(@head, target_element, new_element, nil)
    end
  end
#code omitted here
  def insert_before_by_recursion(current_element,target_element,new_element,previous_element)
    if current_element.nil?
      current_element
    else
      if current_element.eql?(target_element)
        new_element.next_node=current_element
        if previous_element.nil?
          @head = new_element
        else
          previous_element.next_node=new_element
        end
        new_element
      else
        insert_before_by_recursion(current_element.next_node,target_element,new_element,current_element)
      end
    end
  end 

#code omitted here

This seems more than enough for today so we will pick back up tomorrow with a new challenge.

Algorithmathon Day 3: Single Linked List Stack

15 July 2013

Today we will be looking into the Stack data structure and writing the push and pop methods to add and remove data from the stack. While we will need to change it quite a bit we will start with the Single Linked List (SLL) Base found here. If you haven't already read them, rules for the Algorithmathon can be found here. The code can be found here on GitHub. First we write our failing tests.

single_linked_list_spec.rb



require 'spec_helper'
require 'single_linked_list_spec_helper'

describe SingleLinkedList do

  describe "Class" do
    it "should have method 'push'" do
      SingleLinkedList.method_defined?(:push).should be_true
    end

  end

  describe "Instance" do

    before(:each) do
      @list = SingleLinkedList.new()
    end

    it "should return object when 'push' is called and successful" do
      first = SingleLinkedListElement.new("first")
      @list.push(first).eql?(first).should be_true
    end
  end

end

When we run RSpec we get failing (Red) results. To pass these failing tests we can add the method push to our SLL like so.

single_linked_list.rb



require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def push(element)
    unless element.nil?
      @head=element
    end
  end
end

Now when we run our test the results will be passing (Green). Writing your test before you write your code is Test Driven Development. Your goal is to write your test and then to write the minimal amount of code to satisfy the test. Now that the tests for our push method are passing we should write tests for our pop method.

single_linked_list_spec.rb



require 'spec_helper'
require 'single_linked_list_spec_helper'

describe SingleLinkedList do

  describe "Class" do
    it "should have method 'push'" do
      SingleLinkedList.method_defined?(:push).should be_true
    end

    it "should have method 'pop'" do
      SingleLinkedList.method_defined?(:pop).should be_true
    end


  end

  describe "Instance" do

    before(:each) do
      @list = SingleLinkedList.new()
    end

    it "should return first object when 'push' is called and successful" do
      first = SingleLinkedListElement.new("first")
      @list.push(first).eql?(first).should be_true
    end

    it "should return first object when 'pop' is called" do
      first = SingleLinkedListElement.new("first")
      @list.push(first)
      @list.pop().eql?(first).should be_true
    end    
  end

end

Our test for pop will of course fail and thus we should update our code so that they pass.

single_linked_list.rb



require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def push(element)
    unless element.nil?
      @head=element
    end
  end

  def pop()
    element=@head
    @head=@head.next_node
    element
  end
  
end

We now have passing tests for both push and pop. Still we should add another test using multiple objects since a stack must handle multiple objects.

single_linked_list_spec.rb (exerpt)



    ...
    it "should return all objects popped in the reverse order they where pushed" do
      first = SingleLinkedListElement.new("first")
      second = SingleLinkedListElement.new("second")
      third = SingleLinkedListElement.new("third")
      fourth = SingleLinkedListElement.new("fourth")
      fifth = SingleLinkedListElement.new("fifth")
      @list.push(first).eql?(first).should be_true
      @list.push(second).eql?(second).should be_true
      @list.push(third).eql?(third).should be_true
      @list.push(fourth).eql?(fourth).should be_true
      @list.push(fifth).eql?(fifth).should be_true
      @list.pop().eql?(fifth).should be_true
      @list.pop().eql?(fourth).should be_true
      @list.pop().eql?(third).should be_true
      @list.pop().eql?(second).should be_true
      @list.pop().eql?(first).should be_true
    end    
    ...

Ooops our new test is failing! We need to go back and fix our push method to handle linking these objects. Which is simple enough as shown below.

single_linked_list.rb



require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def push(element)
    unless element.nil?
      if @head.nil?
        @head=element
      else
        element.next_node=@head
        @head=element
      end
    end
  end

  def pop()
    element=@head
    @head=@head.next_node
    element
  end
  
end

All our tests are now passing and we are done with our stack for today.

Algorithmathon Day 2: Single Linked List Cycle

14 July 2013

The tail of a Single Linked List (SLL) can be found by working your way along the chain until the next node reference/pointer is null. What do you do if instead the last node points to another node such as the head? When a SLL tail (final node) points back to a previous node it is considered to be cyclic. If it does have a cycle how do we determine this? One way is to use The Tortoise and the Hare Algorithm.

Note: I have seen this condition referred to as cyclic and looped.

To solve our problem we will start with the SLL Base which can be found here. If you haven't already read them, rules for the Algorithmathon can be found here.

Lets add new RSpec tests for "is_cyclic". The new tests will check for SSLs that end in nil, a tail that points to the head and a tail that points to the middle. The last two of which are cyclic.

single_linked_list_spec.rb (excerpt)



    it "should return true when 'is_cyclic' is called: last to first" do
      first = SingleLinkedListElement.new("first")
      last = SingleLinkedListElement.new("last")
      last.next_node=first
      @list.add(first)
      add_elements(@list)
      @list.add(last)
      @list.is_cyclic().should be_true
    end

    it "should return false when 'is_cyclic' is called: nil terminated" do
      add_elements(@list)
      @list.is_cyclic().should be_false
    end

    it "should return true when 'is_cyclic' is called: last to middle" do
      middle = SingleLinkedListElement.new("middle")
      last = SingleLinkedListElement.new("last")
      last.next_node=middle
      add_elements(@list)
      @list.add(middle)
      add_elements(@list)
      @list.add(last)
      @list.is_cyclic().should be_true
    en

We can solve this problem by by using two object references. The tortoise will advance one link at a time and the hare will advance two links at a time. If there is a cycle then eventually the hare and the tortoise references will point to the same location. This is accomplished in the code below.

single_linked_list.rb



require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def add(element)
    if @head.nil?
      @head = element
    else
      last_element=last()
      last_element.next_node=element
    end
  end

  def last()
    last_by_recursion(@head)
  end        

  def is_cyclic()
    if has_nil?(@head)
      false
    else
      @tortoise=@head
      @hare=@head.next_node.next_node
      is_cyclic_recursion()
    end
  end        

  private
    def last_by_recursion(element)
      unless element.nil?
        unless element.next_node.nil?
          last_by_recursion(element.next_node)
        else
          element
        end
      end
    end

    def is_cyclic_recursion()
      if @tortoise.eql?(@hare)
        true
      else
        if has_nil?(@tortoise) || has_nil?(@hare)
          false
        else
          @tortoise=@tortoise.next_node
          @hare=@hare.next_node.next_node
          is_cyclic_recursion()          
        end
      end

    end

    def has_nil?(element)
      element.nil? || element.next_node.nil? || element.next_node.next_node.nil?
    end


end

This code can be summed up in four simple rules.


  1. Tortoise advances one link at a time.

  2. Hare advances two links at a time.

  3. If you find a nil return false.

  4. If the hare and tortoise are in the same place return true.

There is more that one way to solve this problem and Ostermiller.org provides a good discussion of the solution options.

Algorithmathon Single Linked List Base

14 July 2013

Below is the code to be used as the base starting with Day 2 of the Algorithmathon. We have our RSpec test along with our Single Linked List (SLL) Element and the SLL itself. This code will be used as the starting point for most of the Algorithms involving SLL. The code for which can be found on GitHub.

single_linked_list_element_spec.rb



require 'spec_helper'

describe SingleLinkedListElement do
  describe "Class" do
    it "should have a 'next_node' method" do
      SingleLinkedListElement.method_defined?(:next_node).should be_true
    end
    it "should have a 'data' method" do
      SingleLinkedListElement.method_defined?(:data).should be_true
    end

  end
end

single_linked_list_spec.rb




require 'spec_helper'
require 'single_linked_list_spec_helper'

describe SingleLinkedList do

  describe "Class" do
    it "should have method 'last'" do
      SingleLinkedList.method_defined?(:last).should be_true
    end

    it "should have method 'add'" do
      SingleLinkedList.method_defined?(:add).should be_true
    end

    it "should have method 'length'" do
      SingleLinkedList.method_defined?(:length).should be_true
    end    
  end

  describe "Instance" do

    before(:each) do
      @list = SingleLinkedList.new()
    end

    it "should return nil when 'last()' is called" do
      @list.last().should be_nil
    end

    it "should not return nil when 'last()' is called" do
      add_elements(@list)
      @list.last().should_not be_nil
    end
    
    it "should return 'four' when 'last().data' is called" do
      add_elements(@list)
      @list.last().data.should == "four"
    end 

     it "should return 4 when 'length' is called" do
      add_elements(@list)
      @list.length().should == 4
    end   

  end

end

single_linked_list_element.rb



class SingleLinkedListElement
  attr_accessor :next_node, :data

  def initialize(data=nil,next_node=nil)
    self.data=data
    self.next_node=next_node
  end
en

single_linked_list.rb



require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def add(element)
    if @head.nil?
      @head = element
    else
      last_element=last()
      last_element.next_node=element
    end
  end

  def last()
    last_element=SingleLinkedListElement.new()
    last_by_recursion(@head,last_element)
    last_element.next_node
  end 

  def length()
    length_by_recursion(@head,0)
  end  

  private
    def last_by_recursion(element,last_element)
      unless element.nil?
        last_element.next_node=element
        unless element.next_node.nil?
          last_by_recursion(element.next_node,last_element)
        end
      end
    end

    def length_by_recursion(element,count)
      unless element.nil?
        count = count + 1
        length_by_recursion(element.next_node,count)
      else
        count
      end
    end    
end

Algorithmathon Day 1

12 July 2013

Algorithmathon

Algorithms are an important part of programming that I so rarely use. Java, Ruby and most languages already take care the details for us. We just pull the class from the API and move on. Over the next several days we will attempt to comUsing Ruby to write algorithms over the next several days. I decided to start with the venerable Single Linked List implemented in Ruby. What Ruby code would be complete without RSpec to keep it inline. The algorithms in question will be to list the contents in forward and reverse order. You will find the code on GitHub https://github.com/ChrisLynch42/algorythms/tree/master/ruby/single-linked-list

So first lets look at the RSpec

RSpec Results


bash$> rspec

SingleLinkedListElement
Class
should have a 'next' method
should have a 'data' method

SingleLinkedList
Class
should have method 'length'
should have method 'add'
should have method 'next'
should have method 'list'
should have method 'list_reverse'
Instance
should have a length of zero
should have a length of four
should not return nil when 'next()' is called
should return 'one' when 'next().data' is called
should return '["one", "two", "three", "four"]' when 'list()' is called
should return '["four", "three", "two", "one"]' when 'list_reverse()' is called

Finished in 0.02251 seconds
13 examples, 0 failures

These show the expectations we have for our classes. Now lets look into the code.

single_linked_list_element.rb



     class SingleLinkedListElement
       attr_accessor :next, :data
     end

Ruby makes the element very easy. We just define our accessors and move on. Our list will be a little more involved.
single_linked_list.rb



require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :length, :head, :tail, :current

  def initialize
    @length=0
  end

  def add(data)
    element = SingleLinkedListElement.new()
    element.data=data
    if @head.nil?
      @head=element
      @tail=element
      @current=element
    else
      @tail.next=element
      @tail=element
    end
    @length=@length+1
  end

  def next
    unless @current.nil?
      data = @current.data
      @current = @current.next
    end
    if block_given?
      yield data
    end
    data
  end

  def list
    last = @current
    @current = @head
    return_value = Array.new()
    while return_value.length < @length
      self.next {|data|
        return_value.push(data)
      }
    end
    @current = last
    return_value
  end


  def list_reverse
    last = @current
    @current = @head
    return_value = Array.new()
    reverse_by_recursion(return_value)
    @current = last
    return_value
  end

  private
    def reverse_by_recursion(values)
      local_element = self.next 
      unless local_element.nil?
        reverse_by_recursion(values)
        values.push(local_element)
      end
    end

end

Ruby's closures allow us to write the code in the next and list methods. We can pass a block of code to the method which will populate our array for us. The list_reverse method uses recursion. Using the closure took 12 lines of code while using recursion took 15 lines of code. Let us further explore this and see if there is any time difference between the two options of solving the problem.

What about performance? Recursion seems to require less behind the scenes work and therefore might be faster. We can write an RSpec test to verify this.

single_linked_list_spec.rb



    it "should take less time for list to run than list_no_recursion" do
      (1..1000).each { |a_number|
        @list.add(a_number.to_s)
      }

      start_time=Time.now
      @list.list_no_recursion()
      end_time=Time.now
      closure_time=end_time.to_f - start_time.to_f


      start_time=Time.now
      @list.list()
      end_time=Time.now
      recursion_time=end_time.to_f - start_time.to_f

      recursion_time.should > closure_time
    end

This test turns out to be true! There is a measurable difference in favor of recursion. If we kick it up to 100000 we will see that recursion will give us a "stack level too deep" error. This is shown in the two following tests.

single_linked_list_spec.rb




    it "should not raise error when using closure" do
      (1..100000).each { |a_number|
        @list.add(a_number.to_s)
      }

      lambda { @list.list_no_recursion()}.should_not raise_error
    end

    it "should raise error when using closure" do
      (1..100000).each { |a_number|
        @list.add(a_number.to_s)
      }

      lambda { @list.list()}.should raise_error
    end

Thus using a closure with iteration allows us to handle larger data sets with a price on performance. Tail Call Optimization would likely solve this problem for us but it is not part of the Ruby specification and is not turned on by default in most Ruby Virtual Machines for performance reasons.

Algorithmathon Rules

11 July 2013

As a series of Code Katas I have decided to write solutions for a variety of common programming problems. To add restrictions and therefore increase creativity I will add the following constraints.

  1. Use the Ruby programming language
  2. Use RSpec and Test Driven Development
  3. Recursion should be used whenever possible
  4. If iteration is used then closures must also be used.
  5. Rely mostly on the use of primitives. Only use of Arrays or Hash objects where they do not solve the problem in an of themselves and to not use them would cause unnecessary complication.

CodePalousa, Backbone.js and TDD Javascript

15 June 2013

I attended CodePalousa in March of this year and this brought my first exposure to Backbone.js. Backbone is a Javascript API that provides a framework to create a single page web application and it utilizes the MVC design pattern. Backbone appeared to have great potential both as a better way to write a web application interface and improve the web development process. There are a variety of other JavaScript frameworks such as Angularjs which fill the same niche as Backbone. I concentrated on Backbone.

You may be familiar with the Model View Controller design pattern. This design pattern is used extensively in web development and is the core behind such frameworks as Struts 2, Ruby on Rails and ASP.NET. Other than MVC, what these each have in common is that they are all server side frameworks. Most or all of the view construction occurs on the server. With Backbone.js we can move the view construction to the browser. This results in a more responsive interface and can eliminate the annoying flicker between page loads. This design pattern is being referred to as the Model View View Model design pattern. I tend to think of it as the Double MVC pattern. You have a MVC pattern on the server and in the browser.

How this works is the server side framework constructs a view and delivers that view to the browser. Which is how MVC web frameworks have and still work. The difference with MVVM is that this view is now constructed to be a data construct, very often JSON, that becomes the model in a seperate MVC pattern running in the browser. With this design pattern we are no longer processing the view on the server and transporting all of the HTML/JavaScript in the view to the browser. All we are getting from the server is the data. The view is being handled in the browser. Below is a diagram showing this.

MVVM Diagram
MVVM Diagram

This brings us to the part that I found really exciting. This can completely change how web applications are prototyped and designed. Using local storage (Backbone.localStorage) you can build a prototype web application that interacts with the user and stores data without having to setup a database or an application server. All you need is a lightweight web server. To some extent you don't even need the web server. You can get much done just with HTML files on your local drive. Working on the local drive can cause difficulties. Cross domain issues being one of them. So working on any available light weight web server is recommended. In my case I installed Apache httpd on my Linux box and got to work.

An important piece we haven't talked about yet is testing. QUnit provides a nice unit testing framework and Jasmine provides a handy Rspec framework for Test/Business Driven Development (TDD). What this means is that you can not only develop your web application on any web server or inexpensive web hosting account but you can also apply the discipline of unit testing and TDD! I have spent many hours of my life setting up development environments. Setting up the database and application/web server can take a significant amount of time. Time better spent designing and building an application. This is one of the things that attracted me to ROR.

Finally it separates the view that a user sees from the data so effectively that we should be able to switch out server side application servers with ease. All you need on the server side is restful web services. Whether that service is provided by a J2EE framework, Rails or ASP.net not longer matters to us as long as it gives us the JSON data in a restful way.

We have been doing a lot of talking so lets get an application. I decided to experiment with creating a Initiative tool for Role Playing Games. Initiative can be viewed online as well as the Jasmine tests. You may have to refresh your browser page once or twice to get it to work. A bug I haven't had time to track down. Require.js was also used to allow the application to broken down into modules. This helps create a clean and understandable file structure and avoids having multiple objects in one file. The larger an application becomes the more critical this is. Click here for the source code.

The application should allow the user to add characters as shown here. Enter initiative roll, name and hit points and click the plus sign.

Add Character
Add Character

Once a character is added click the plus sign next to conditions to add a condition. You can save the condition by clicking the disk icon.

Add Condition
Add Condition

Add at least three characters.

Add 3 Characters
Add 3 Characters

Click the round green button to begin a session. Next, Previous and stop buttons will appear.

Click Start Button
Click Start Button

Click the Next button several times and notice how the condition duration decrements when the character leaves the top of the queue. You can go to the previous character up to the beginning of the current round.

A colleague Wesley Reisz mentioned MeteorJS to me and it looks to be a key piece for an application such as this initiative tool. So that multiple users can receive updates immediately when changes occur. This will most likely be the subject of my next article.

Ruby on Rails Authentication and Authorization Update 3.2

09 March 2013

This is an update to the source code to modify it for Rails 3.2 and Devise 2.2.3. I have also added some helpful bits to the default page and corrected flaws. You should at least already have Ruby, Ruby On Rails, Devise and CanCan installed. It would be preferable that the reader has gone through the five part article first, though not required.

The first difficulty that I found was the lack of a dedicated admin user. Our first goal will be to create the admin@nowhere.com user who has permissions to everything.

First lets create the following script which will encrypt our password for our admin user. Having already installed Devise the bcrypt should already be available.

password-encrypter.rb



  require 'bcrypt'

  pepper = nil
   cost = 10
   password='password'
   puts encrypted_password = ::BCrypt::Password.create("#{password}#{pepper}", :cost => cost).to_s

We should get something close to the following when running the script

Running password-encrypter.rb script



     c:filesarticle-update>ruby password-encrypter.rb
     $2a$10$BzIoyBkWO7iW2nZsdVn36eFSvvRrds/T5DjvVM.qnv79aL9lZIXve

This gives us the password so that we can use the SQLite Manager in Firefox to create our admin user. As shown below edit the record with an id of 1 and enter admin@nowhere.com for username/email and the encrypted password returned by your script for the password.

Here is the table ...

User Table
User Table

Double click the record with id of 1 and edit it.

User Table Edit Record 1
User Table Edit Record 1

Next we need to use the same methods to create the "administrator" role in the role table.

Role Table
Role Table

Now we need to associate this role with our user by editing the user_role table and entering a user id of 1 and a role of id of 1 which we just edited and created.

User Role Table
User Role Table

Finally we go into the role_permissions table and add "all" for the controller and "manage" for the permissions.

Role Permissions Table
Role Permissions Table

We now have an admin user whom we have assigned management privileges to all controller actions. Now our journey can truly begin.

If you are like me you find it annoying to have to remember the URL addresses and type them into the application. Lets edit the static landing page for URL http://localhost:3000 so that it has links we can use.

public/index.html



<!DOCTYPE html>
<html>
  <head>
    <title>Ruby on Rails: MySecurity Example</title>
    <style type="text/css" media="screen">
      body {
        margin: 0;
        margin-bottom: 25px;
        padding: 0;
        background-color: #f0f0f0;
        font-family: "Lucida Grande", "Bitstream Vera Sans", "Verdana";
        font-size: 13px;
        color: #333;
      }

      h1 {
        font-size: 28px;
        color: #000;
      }

      a  {color: #03c}
      a:hover {
        background-color: #03c;
        color: white;
        text-decoration: none;
      }


      #page {
        background-color: #f0f0f0;
        width: 750px;
        margin: 0;
        margin-left: auto;
        margin-right: auto;
      }

      #content {
        float: left;
        background-color: white;
        border: 3px solid #aaa;
        border-top: none;
        padding: 25px;
        width: 500px;
      }

      #sidebar {
        float: right;
        width: 175px;
      }

      #footer {
        clear: both;
      }

      #header, #about, #getting-started {
        padding-left: 75px;
        padding-right: 30px;
      }


      #header {
        background-image: url("/assets/rails.png");
        background-repeat: no-repeat;
        background-position: top left;
        height: 64px;
      }
      #header h1, #header h2 {margin: 0}
      #header h2 {
        color: #888;
        font-weight: normal;
        font-size: 16px;
      }


      #about h3 {
        margin: 0;
        margin-bottom: 10px;
        font-size: 14px;
      }

      #about-content {
        background-color: #ffd;
        border: 1px solid #fc0;
        margin-left: -55px;
        margin-right: -10px;
      }
      #about-content table {
        margin-top: 10px;
        margin-bottom: 10px;
        font-size: 11px;
        border-collapse: collapse;
      }
      #about-content td {
        padding: 10px;
        padding-top: 3px;
        padding-bottom: 3px;
      }
      #about-content td.name  {color: #555}
      #about-content td.value {color: #000}

      #about-content ul {
        padding: 0;
        list-style-type: none;
      }

      #about-content.failure {
        background-color: #fcc;
        border: 1px solid #f00;
      }
      #about-content.failure p {
        margin: 0;
        padding: 10px;
      }


      #getting-started {
        border-top: 1px solid #ccc;
        margin-top: 25px;
        padding-top: 15px;
      }
      #getting-started h1 {
        margin: 0;
        font-size: 20px;
      }
      #getting-started h2 {
        margin: 0;
        font-size: 14px;
        font-weight: normal;
        color: #333;
        margin-bottom: 25px;
      }
      #getting-started ol {
        margin-left: 0;
        padding-left: 0;
      }
      #getting-started li {
        font-size: 18px;
        color: #888;
        margin-bottom: 25px;
      }
      #getting-started li h2 {
        margin: 0;
        font-weight: normal;
        font-size: 18px;
        color: #333;
      }
      #getting-started li p {
        color: #555;
        font-size: 13px;
      }


      #sidebar ul {
        margin-left: 0;
        padding-left: 0;
      }
      #sidebar ul h3 {
        margin-top: 25px;
        font-size: 16px;
        padding-bottom: 10px;
        border-bottom: 1px solid #ccc;
      }
      #sidebar li {
        list-style-type: none;
      }
      #sidebar ul.links li {
        margin-bottom: 5px;
      }

      .filename {
        font-style: italic;
      }
    </style>
    <script type="text/javascript">
      function about() {
        info = document.getElementById('about-content');
        if (window.XMLHttpRequest)
          { xhr = new XMLHttpRequest(); }
        else
          { xhr = new ActiveXObject("Microsoft.XMLHTTP"); }
        xhr.open("GET","rails/info/properties",false);
        xhr.send("");
        info.innerHTML = xhr.responseText;
        info.style.display = 'block'
      }
    </script>
   <script src="/assets/jquery.js?body=1" type="text/javascript"></script>
   <script src="/assets/jquery_ujs.js?body=1" type="text/javascript"></script>
    
  </head>
  <body>
    <div id="page">
      <div id="sidebar">
        <ul id="sidebar-items">
          <li>
            <h3>Browse the documentation</h3>
            <ul class="links">
              <li><a href="http://guides.rubyonrails.org/">Rails Guides</a></li>
              <li><a href="http://api.rubyonrails.org/">Rails API</a></li>
              <li><a href="http://www.ruby-doc.org/core/">Ruby core</a></li>
              <li><a href="http://www.ruby-doc.org/stdlib/">Ruby standard library</a></li>
            </ul>
          </li>
        </ul>
      </div>

      <div id="content">
        <div id="header">
          <h1>Welcome aboard</h1>
          <h2>Ruby On Rails:  Mysecurity Example</h2>
        </div>

        <div id="about">
          <h3><a href="rails/info/properties" onclick="about(); return false">About your application&rsquo;s environment</a></h3>
          <div id="about-content" style="display: none"></div>
        </div>

        <div id="getting-started">
          <h1>Getting started</h1>
          <h2>Here&rsquo;s how to get rolling:</h2>

          <ol>
            <li>
              <h2>Read this article</h2>
              <p><a href='/2012/02/ruby-on-rails-authentication-and-authorization-part-1/'>Ruby on Rails Authentication and Authorization</a></p>
            </li>

            <li>
              <h2>Helpful Links</h2>
              <p>Log in - <a href="/user/sign_in">/user/sign_in</a></p>
              <p>Log out - <a href="/user/sign_out" data-method="delete" rel="nofollow">/user/sign_out</a></p>
              <p>Roles - <a href="roles">/roles</a></p>
              <p>Users - <a href="users">/users</a></p>
            </li>

          </ol>
        </div>
      </div>

      <div id="footer">&nbsp;</div>
    </div>
  </body>
</html>

Now we have a friendly landing that is a little helpful. Next lets update our gemfile to indicate rails 3.2 and to update our sass versions.

public/index.html



source 'http://rubygems.org'

gem 'rails', '3.2.11'

gem 'sqlite3'
gem 'devise'
gem 'cancan'


# Gems used only for assets and not required
# in production environments by default.
group :assets do
  gem 'sass-rails',   '~> 3.2.6'
  gem 'uglifier', '>= 1.0.3'
end

gem 'jquery-rails'

group :test do
  gem 'turn', '~> 0.8.3', :require => false
end

Now Rails application is configured but if you play around with it you will realize that the Role Permissions fail to load when on the Edit Role screen. This is because rails 3.2 handles helper files differently and it handles layouts differently.

Helper files are to be used with the View of the MVC model not with the controller which is what we chose to do the first time around. The contents of role_permissions_helper.rb should be copied and pasted to the end of the role_permissions_controller.rb file. The "layout nil" at the beginning of the controller no longer works to suppress the layout for a controller. Now instead we add "render :layout => nil if request.xhr?" to the "format.html" lines in the controller.

app/controllers/role_permissions_controller.rb



class RolePermissionsController < ApplicationController
  load_and_authorize_resource
  # GET /role_permissions
  # GET /role_permissions.json



  def index
    index_helper

    respond_to do |format|
      format.html { render :layout => nil if request.xhr? } # index.html.erb
      format.json { render json: @role_permissions }
    end
  end

  # GET /role_permissions/1
  # GET /role_permissions/1.json
  def show
    @role_permission = RolePermission.find(params[:id])
    #authorize! :show, @role_permission
    respond_to do |format|
      format.html { render :layout => nil if request.xhr? } # show.html.erb
      format.json { render json: @role_permission }
    end
  end

  # GET /role_permissions/new
  # GET /role_permissions/new.json



  def new
    prepare
    @role_permission = RolePermission.new
    @role_permission.role_id = params[:role_id]
    respond_to do |format|
      format.html { render :layout => nil if request.xhr? }# new.html.erb
      format.json { render json: @role_permission }
    end
  end

  # GET /role_permissions/1/edit
  def edit
    prepare
    @role_permission = RolePermission.find(params[:id])
    respond_to do |format|
      format.html { render :layout => nil if request.xhr? }# new.html.erb
      format.json { render json: @role_permission }
    end
  end

  # POST /role_permissions
  # POST /role_permissions.json
  def create
    @role_permission = RolePermission.new(params[:role_permission])
#    @role_permission = RolePermission.new()

    respond_to do |format|
      if @role_permission.save
        format.html { 
          index_helper
          render :action => 'index', :layout => nil if request.xhr?
        }
        format.json { render json: @role_permission, status: :created, location: @role_permission }
      else
        format.html { render action: "new", :layout => nil if request.xhr? }
        format.json { render json: @role_permission.errors, status: :unprocessable_entity }
      end
    end
  end

  # PUT /role_permissions/1
  # PUT /role_permissions/1.json
  def update
    @role_permission = RolePermission.find(params[:id])

    respond_to do |format|
      if @role_permission.update_attributes(params[:role_permission])
        format.html {
          index_helper
          render :action => 'index', :layout => nil if request.xhr?
        }
        format.json { head :ok }
      else
        format.html { render action: "edit" }
        format.json { render json: @role_permission.errors, status: :unprocessable_entity }
      end
    end
  end

  # DELETE /role_permissions/1
  # DELETE /role_permissions/1.json
  def destroy
    @role_permission = RolePermission.find(params[:id])
    @role_permission.destroy

    respond_to do |format|
      format.html {
        index_helper
        render :action => 'index', :layout => nil if request.xhr?
      }
      format.json { head :ok }
    end
  end


  #private :prepare
  private
    def index_helper
    if params[:role_id].nil?
      if params[:role_permission][:role_id].nil?
        log_error " role_id parameter is invalid!"
      else
        @the_role_id = params[:role_permission][:role_id]
      end
    else
      @the_role_id = params[:role_id]
    end

    begin
      @role_permissions = RolePermission.find(:all,:conditions => ["role_id=?",@the_role_id])
    rescue ActiveRecord::RecordNotFound
      log_error "record not found role_id=" + params[:role_id]
    end
  end

  def prepare
    Rails.application.eager_load!
    @roles = Role.all
    @regulators = get_models
    @conducts = get_actions
  end

  def get_models
    regulators = Array.new
    ActiveRecord::Base.descendants.each{ |model|
      regulators[regulators.length] = model.name
    }
    return regulators
  end

  def get_actions
    conducts = Array.new
    ApplicationController.descendants.each { |regulator|
      the_actions = regulator.action_methods
      the_actions.each {|the_action|
        conducts[conducts.length] = the_action
      }
    }
    return conducts
  end

end

Additionally we need to go to appassetsjavascripts and delete the role_permissions.js.coffee file. With the controller updated and the file deleted we should now have a working role permissions controller.

Now comes the big finale! We modify the application_controller.rb to call Devise authentication. The application_controller is the parent of our other controllers and thus through the magic of inheritance all our controllers will that authentication.

app/controllers/application_controller.rb



class ApplicationController < ActionController::Base
  protect_from_forgery
  before_filter :authenticate_user!

end

Finally make sure that your users controller and your role controller have the "load_and_authorize_resource" right after the class declaration.

app/controllers/users_controller.rb



    class UsersController < ApplicationController
      load_and_authorize_resource
      #I cut out the rest for the sake of brevity.
    end

Your Ruby on Rails 3.2 with authentication and authorization should be good to go! Happy programming.

Command Design Pattern Part 1

07 January 2013

Encapsulates a request as an object, thereby letting you parameterize other objects with different requests, queue or log requests, and support undoable operations.

We have the definition but what does it mean? Lets start with a drawing where the names have been changed to protect my sanity! The terminology used to describe the pattern did not lend itself to my learning. The original and my own lexicon is provided in the following list. As we go through the pattern remembering both terms will help us understand the pattern.

Parts one and two of this article were developed using the Netbeans IDE 7.2
First the terms.

  • Client (Controller) - This object orchestrates the other objects. It is the puppet master of the Command Design Pattern!
  • Command - An object that encapsulates the command to be given and the functionality to perform said command.
  • Invoker (Command Manager) - this maintains a list of commands and tracks what commands have have been executed. May also track undo and redo histories. Manages commands.
  • Reciever (Command Target) - this is the object that the command acts on or changes. The "target" of the command.

The following drawing is the basis for the code in this article.

Command Pattern Drawing 1
Command Pattern Drawing where the command target/receiver is passed to the command manager/invoker

Our SimpleCommand program, aka the "client", creates a command object, command manager object, and command target. The command and command target are passed into the command manager object. Then the execute method of the command manager is called. This method executes each command on the one command target. There is another option which is illustrated by the following drawing.

Command Pattern Drawing 2
Command Pattern drawing where the command target/receiver is passed into the command and then the command is passed into the command manager/invoker.

In this drawing the command target is passed into the command and then the command is passed into the command manager. The advantage of this design is you can have multiple targets and multiple commands and only one command manager. This is more than we need for our simple example. From this we can extrapolate the following class diagram. To be honest, I went right to the code and then came back and put the class diagram together.

Simple Command Pattern UML Diagram
Simple Command Pattern UML Diagram

Our business rules will be that we need to create a Character with the attributes: strength, dexterity, constitution and name. Character will be our receiver. We will need to create a command for each of our attributes. Once we have our commands and receiver we will need our invoker which will manage our commands for us. Finally we will need our client application. Let's start with our invoker ,CharacterCommandManager, as shown below.

CharacterCommandManager.java




package simplecommand;
import java.util.*;

public class CharacterCommandManager {
  Character character;
  List commands = new ArrayList();
  
  public CharacterCommandManager(Character character) {
    this.character = character;  
  }
  
  public void add(ICharacterCommand command) {
    if(commands != null) {
      commands.add(command);
    }    
  }
  
  public void execute() {
    for(ICharacterCommand command : commands) {
      if(command != null) {
        command.execute(character);
      }
    }
  }
  
}

As you can see the invoker has a list to store commands and an execute method to run the commands. The constructor for this class requires a Character object.

Character.java



package simplecommand;

public class Character {
  private String name;
  private int strength;
  private int dexterity;
  private int constitution;

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public int getStrength() {
    return strength;
  }

  public void setStrength(int strength) {
    this.strength = strength;
  }

  public int getDexterity() {
    return dexterity;
  }

  public void setDexterity(int dexterity) {
    this.dexterity = dexterity;
  }

  public int getConstitution() {
    return constitution;
  }

  public void setConstitution(int constitution) {
    this.constitution = constitution;
  }
  
  public String toString() {
    return "name=" + name +
           "; strength=" + strength +
           "; dexterity=" + dexterity +
           "; constitution=" + constitution;
                   
  }
  
}

Character has all the attributes that we wanted. Now we need to define an interface, ICharacterCommand, to be used by each of our commands.

ICharacterCommand.java



package simplecommand;

public interface ICharacterCommand {
  public void execute(Character character);  
}

Using our interface we will define the following classes for each of our selected attributes.

StrengthCommand.java



package simplecommand;

public class StrengthCommand implements ICharacterCommand {
  private int strength;
  
  public StrengthCommand(int strength) {
    this.strength=strength;
  }
  
  public void execute(Character character) {
    if(character != null) {
      character.setStrength(strength);
    }
  }
  
}

DexterityCommand.java



package simplecommand;

public class DexterityCommand implements ICharacterCommand {
  private int dexterity;
  
  public DexterityCommand(int dexterity) {
    this.dexterity=dexterity;
  }
  
  public void execute(Character character) {
    if(character != null) {
      character.setDexterity(dexterity);
    }
  }
  
}

ConstitutionCommand.java



package simplecommand;

public class ConstitutionCommand implements ICharacterCommand {
  private int constitution;
  
  public ConstitutionCommand(int constitution) {
    this.constitution=constitution;
  }
  
  public void execute(Character character) {
    if(character != null) {
      character.setConstitution(constitution);
    }
  }
  
}

NameCommand.java



package simplecommand;

public class NameCommand implements ICharacterCommand {
  private String name;
  
  public NameCommand(String name) {
    this.name=name;
  }
  
  public void execute(Character character) {
    if(character != null) {
      character.setName(name);
    }
  }
  
  public String toString() {
    return name;
  }
  
}

Finally we create our client, SimpleCommand, to manage and controll all our other objects.

SimpleCommand.java



package simplecommand;

public class SimpleCommand {

  public static void main(String[] args) {
    Character character = new Character();
    CharacterCommandManager queue = new CharacterCommandManager(character);
    ICharacterCommand command = new NameCommand("Bob");
    queue.add(command);
    command = new StrengthCommand(14);
    queue.add(command);
    command = new DexterityCommand(17);
    queue.add(command);
    command = new ConstitutionCommand(10);
    queue.add(command);
    
    queue.execute();
    
    System.out.println(character);
  }
}

Now we run our SimpleCommand and we should see the following results.

  SimpleCommand Results


name=Bob; strength=14; dexterity=17; constitution=10

In the second part of this article we will explore a more complex implementation of the Command Design Pattern.

Command Design Pattern Part 2

07 January 2013

In part 1 we created a simple Command Design Pattern in Java. Here in the second part we will add undo and redo capabilities to our implementation. This implementation will use the flow illustrated below. Instead of passing the receiver to the invoker and from the invoker to the command the client will be passing the receiver to the command and the command to the invoker. This, in my opinion, is the better of the two options.

Command Pattern Drawing 2
Command Pattern drawing where the command target/receiver is passed into the command and then the command is passed into the command manager/invoker.

From this we should end up with a class diagram similar to the following.

Complex Command Pattern UML Class Diagram
Complex Command Pattern UML Class Diagram

In our invoker we will need to switch to LinkedLists and add two lists. The new lists will be used to track the undo and redo commands. This implementation is shown below.

CharacterCommandManager.java



package complexcommand;
import java.util.*;

public class CharacterCommandManager {
  private Deque commands = new LinkedList();
  private Deque undoCommands = new LinkedList();
  private Deque redoCommands = new LinkedList();
  
  public CharacterCommandManager() {
  }
  
  public void add(ICharacterCommand command) {
    if(commands != null) {
      commands.add(command);
    }    
  }
  
  public void execute() {
    ICharacterCommand command=null;    
    while(!commands.isEmpty()) {
      command = commands.removeFirst();
      if(command != null) {
        command.execute();
        undoCommands.add(command);
      }
    }
  }

  public void undo() {
    ICharacterCommand command=null;
    if(!undoCommands.isEmpty()) {
      command = undoCommands.removeLast();
      if(command != null) {
        command.undo();
        redoCommands.add(command);
      }
    }
  }

  public void redo() {
    ICharacterCommand command=null;
    if(!redoCommands.isEmpty()) {
      command = redoCommands.removeLast();
      if(command != null) {
        command.execute();      
      }
    }
  }
  
  
  
}

Our receiver remains the same.

Character.java



package complexcommand;

public class Character {
  private String name;
  private int strength;
  private int dexterity;
  private int constitution;

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public int getStrength() {
    return strength;
  }

  public void setStrength(int strength) {
    this.strength = strength;
  }


  public int getDexterity() {
    return dexterity;
  }

  public void setDexterity(int dexterity) {
    this.dexterity = dexterity;
  }

  public int getConstitution() {
    return constitution;
  }

  public void setConstitution(int constitution) {
    this.constitution = constitution;
  }

  
  public String toString() {
    return "name=" + name +
           "; strength=" + strength +
           "; dexterity=" + dexterity +
           "; constitution=" + constitution;
                   
  }
  
}

We have added the undo method to our ICharacterCommand interface.

ICharacterCommand.java



package complexcommand;

public interface ICharacterCommand {
  public void execute();
  public void undo();
}

Our command classes which implement the interface have added an "undo" attribute.

NameCommand.java



package complexcommand;

public class NameCommand implements ICharacterCommand {
  private String name;
  private String undoName;
  private Character character;
  
  public NameCommand(Character character, String name) {
    this.name=name;
    this.character=character;
  }
  
  public void execute() {
    if(character != null) {
      this.undoName = character.getName();
      character.setName(name);
    }
  }
  
  public void undo() {
    if(character != null) {
      character.setName(undoName);
    }
  }  
  
  public String toString() {
    return name;
  }
  
}

StrengthCommand.java



package complexcommand;

public class StrengthCommand implements ICharacterCommand {
  private int strength;
  private int undoStrength;
  private Character character;
  
  public StrengthCommand(Character character, int strength) {
    this.strength=strength;
    this.character=character;
  }
  
  public void execute() {
    if(character != null) {
      this.undoStrength=character.getStrength();
      character.setStrength(strength);
    }
  }

  public void undo() {
    if(character != null) {
      character.setStrength(undoStrength);
    }
  }
  
}

DexterityCommand.java



package complexcommand;

public class DexterityCommand implements ICharacterCommand {
  private int dexterity;
  private int undoDexterity;
  private Character character;
  
  public DexterityCommand(Character character, int dexterity) {
    this.dexterity=dexterity;
    this.character=character;
  }
  
  public void execute() {
    if(character != null) {
      this.undoDexterity=character.getDexterity();
      character.setDexterity(dexterity);
    }
  }

  public void undo() {
    if(character != null) {
      character.setDexterity(undoDexterity);
    }
  }
  
}

ConstitutionCommand.java



package complexcommand;

public class ConstitutionCommand implements ICharacterCommand {
  private int constitution;
  private int undoConstitution;
  private Character character;
  
  public ConstitutionCommand(Character character, int constitution) {
    this.constitution=constitution;
    this.character=character;    
  }
  
  public void execute() {
    if(character != null) {
      this.undoConstitution=character.getConstitution();
      character.setConstitution(constitution);
    }
  }

  public void undo() {
    if(character != null) {
      character.setConstitution(undoConstitution);
    }
  }
  
}

Our client now sets the receivers attributes twice and calls the undo and redo methods. Which nicely demonstrates the functionality that we have added.

ComplexCommand.java



package complexcommand;

public class ComplexCommand {

  public static void main(String[] args) {
    CharacterCommandManager manager = new CharacterCommandManager();
    Character character = new Character();
    
    ICharacterCommand command = new NameCommand(character,"Bob");
    manager.add(command);

    command = new StrengthCommand(character,14);
    manager.add(command);

    command = new DexterityCommand(character,13);
    manager.add(command);

    command = new ConstitutionCommand(character,11);
    manager.add(command);
    
    manager.execute();
    System.out.println("First time attributes set:");
    System.out.println(character + "n");
    
    command = new NameCommand(character,"Joe");
    manager.add(command);

    command = new StrengthCommand(character,18);
    manager.add(command);

    command = new DexterityCommand(character,10);
    manager.add(command);

    command = new ConstitutionCommand(character,12);
    manager.add(command);

    manager.execute();
    System.out.println("Second time attributes set:");
    System.out.println(character + "n");
    
    manager.undo();
    manager.undo();
    manager.undo();
    manager.undo();
    System.out.println("After undo operation called 4 times:");
    System.out.println(character + "n");
    
    manager.redo();
    manager.redo();
    manager.redo();
    manager.redo();
    System.out.println("After redo operation called 4 times:");
    System.out.println(character + "n");
    
  }
}

If all has gone well we will see the following results.

  SimpleCommand Results


First time attributes set:
name=Bob; strength=14; dexterity=13; constitution=11

Second time attributes set:
name=Joe; strength=18; dexterity=10; constitution=12

After undo operation called 4 times:
name=Bob; strength=14; dexterity=13; constitution=11

After redo operation called 4 times:
name=Joe; strength=18; dexterity=10; constitution=12

Singleton Design Pattern Part 2

20 December 2012

In Part 1 of these articles we discussed the negative aspects of the Singleton Design Pattern. Now let us discuss what can be done to reduce the negative aspects. The first item that springs to mind is that we can loosen the coupling by returning an interface rather than the object itself. Keep in mind that by doing this it will no longer be a Singleton when considering a strict definition.

RuleSystem.java



package singletonloosed;

public class RuleSystem implements IRuleSystem {

  private static volatile IRuleSystem ruleSystem;

  public RuleSystem() {
    
  }  
  
  private static synchronized void initializeInstance() {
    ruleSystem = new RuleSystem();
  }

  public static IRuleSystem getInstance() {
    if (ruleSystem == null) {
      initializeInstance();
    }
    return ruleSystem;
  }
}

IRuleSystem.java



package singletonloosed;

public interface IRuleSystem {
  
}

We now can change the object type being returned by the "Singleton" as long as it implements the IRuleSystem interface. We could create FantasyRule and SuperHeroRule classes that implement the IRuleSystem interface and return either one. We can add or remove a variety of rule systems to the RuleSystem class without changing code where the class is called. We can change the code in one location, which is the goal of being loosely coupled.

This design needs more thought. How will our RuleSystem class know which rule system to return? The option I am going with here is to pass in a parameter to the getInstance method. Let us write some code starting with our "Singleton" class.

RuleSystems.java


package singletonimproved;

import java.util.*;
import singletonimproved.RuleSystemEnum;

public class RuleSystems {

private static volatile HashMap<RuleSystemEnum, IRuleSystem> ruleSystems;

private RuleSystems() {
}

private static synchronized void initializeInstance() {
ruleSystems = new HashMap(2);
ruleSystems.put(RuleSystemEnum.SUPER, new SuperRuleSystem());
ruleSystems.put(RuleSystemEnum.FANTASY, new FantasyRuleSystem());
}

public static IRuleSystem getInstance(RuleSystemEnum system) {
IRuleSystem returnValue = null;
if (ruleSystems == null) {
initializeInstance();
}

returnValue = ruleSystems.get(system);

return returnValue;

}
}

Wow! Our Singleton Design pattern has been transformed into a Factory Design pattern. Does this mean, when we are tempted to use a Singleton, we should instead use a Factory instead? I would say the answer is yes 99% of the time. Now for our Enumerations which will help keep our code uncluttered.

  RuleSystemEnum.java


package singletonimproved;

public enum RuleSystemEnum {
FANTASY,
SUPER
}

Next our simple interface.

  IRuleSystem.java


package singletonimproved;

public interface IRuleSystem {

}

Followed by two rule systems which implement our interface.

  FantasyRuleSystem.java


package singletonimproved;

public class FantasyRuleSystem implements IRuleSystem {

public String toString() {
return "I am a Medieval Fantasy rule system!";
}

}

  SuperRuleSystem.java


package singletonimproved;

public class SuperRuleSystem implements IRuleSystem {

public String toString() {
return "I am a system for Super Heros!";
}

}

Now lets add a class that will use our Factory and show us how it works.

  SuperRuleSystem.java


package singletonimproved;

public class SingletonImproved {

public static void main(String[] args) {
RuleSystems rules = new RuleSystems();
IRuleSystem rule = RuleSystems.getInstance(RuleSystemEnum.SUPER);
System.out.println(rule.toString());
rule = RuleSystems.getInstance(RuleSystemEnum.FANTASY);
System.out.println(rule.toString());
}
}

When run you should see results similar to the following.

  SingletonImproved Results


I am a system for Super Heros!
I am a Medieval Fantasy rule system!

What hasn't been addressed is the global nature of using Singleton's and their affect on testing/debugging. I will leave those subjects to others for now as I am anxious to move onto another design pattern.

Singleton Design Pattern Part 1

14 November 2012

Ensures a class has only one instance and provides a global point of access to it.

My first impressions on Singleton's were that they are a simple pattern and didn't seem particularly interesting. It didn't take long for me to become disabused of that notion. Surprisingly there is something of a controversy when it comes to singleton's, which can quickly result in brain fatigue. The various arguments for and against the Singleton pattern are rarely accompanied by code or even diagrams to illustrate the points being made.

One common complaint being that it results in tightly coupled code. I found this assertion somewhat baffling, but going back to some fundamentals of programming, it began to make more sense. That is what we will explore here in this article. Along the way we will discuss tightly coupled code and throw in a little Rock and Roll!

Continuing our Role Playing Game theme will give us our example business story/rule to play with. In this case rules are the subject matter! For the game to be fun, everyone and everything must be using the same rules. So it makes sense for there to be one and only one set of rules which everyone and everything must use. This sounds like a great place for a singleton!

Let us write a basic singleton pattern in Java as shown below.

RuleSystem.java



package singleton;

public class RuleSystem {

  private static volatile RuleSystem ruleSystem;

  private RuleSystem() {
    
  }
  
  public static synchronized RuleSystem getInstance() {
    if (ruleSystem == null) {
      ruleSystem = new RuleSystem();
    }
    return ruleSystem;
  }

}

This class uses static methods and static attributes because our goal is to have one and only one instance of the RuleSystem class. The method is "synchronized" to avoid assigning one object to "ruleSystem", followed by another object, in a multiple thread scenario.

If you Google or search on StackOverflow you will find discussions on the benefits and detriments of the Singleton Design Pattern. The most predominant one being that it results in tightly coupled code. I faced two obstacles in understanding their point. The first was that they are discussing a singleton, as defined at the beginning of this article, exactly, without deviation. We will discuss this more in Part 2 of Singletons. The second was in understanding what "tightly coupled" and "loosely coupled" mean.

...Just Hold On Loosely But don't let go. If you cling to tightly. You're gonna lose control...

In addition to being a pretty good song, Hang on Loosely, is part of the core principles behind the design patterns. Loosely coupled code requires less maintenance than tightly coupled code. How do we recognize tightly coupled code and will it really increase my workload? A good question and one we should look into.

When two objects are loosely coupled, they can interact, but have very little knowledge of each other.

Well we have a definition now, but what does it mean when you are writing code? Well I still don't know either! So let's go an see what Wikipedia has to say. Wow! While starting to make sense, things have gotten more complicated. The most obvious problem seems to be that singleton's are a module that other modules depend on. This can make testing more difficult. Tightly coupled code would also be a result. Since it is static it is acting on a global scope and has all the problems and benefits associated with global variables. Which is a whole article itself!

We should write code to illustrate the tight coupling problem. Using Java we will create a TightCouple and a LooseCouple class. Using a Coupling class we will show the difference between the two. These three files are shown below.

TightCouple.java



package coupling;

import java.util.ArrayList;

public class TightCouple {
  private ArrayList myList;

  public ArrayList getMyList() {
    return myList;
  }

  public void setMyList(ArrayList myList) {
    this.myList = myList;
  }    
}

LooseCouple.java



package coupling;

import java.util.*;

public class LooseCouple {
  private List myList;

  public List getMyList() {
    return myList;
  }

  public void setMyList(List myList) {
    this.myList = myList;
  }    
}

Coupling.java



package coupling;
import java.util.*;

public class Coupling {
  
  
  public static void main(String[] args) {
    TightCouple tight = new TightCouple();
    tight.setMyList(new ArrayList());
    
    LooseCouple loose = new LooseCouple();
    loose.setMyList(new Vector());
    loose.setMyList(new Stack());
    loose.setMyList(new ArrayList());
  }
}

In the TightCouple class we specified myList as an ArrayList class. This means that we can only assign classes of type ArrayList, or possibly a subclass of ArrayList, to the myList variable. The LooseCouple class, on the other hand, defines myList as a List interface. This means we can assign any class to the myList variable as long as it implements the List interface. As we can see in the Coupling class we are able to set myList to a Vector, Stack and ArrayList. This gives us flexibility, which is used in the design patterns we have been discussing.

Tightly coupled code can increase your workload. I recently built a few classes that had methods that took HashMap as a parameter. I later decided that in some cases I really needed LinkedHashMap to be passed into the methods. The result was that I would have to modify each of the classes to allow LinkedHashMap to be passed to the classes' methods. We know the right way is to define the method parameter as a Map interface so that any class implementing it could be used. If I had done this the first time, I wouldn't have needed to modify the existing classes when I switched to using LinkedHashMap.

The singleton code above results in tightly coupled code because it returns an object of the RuleSystem class. We could fix this by returning an interface which would allow us to return any number of objects as long as they implement the appropriate interface. This would only work if we thought well enough ahead to define an appropriate interface. Keep in mind that just using an interface without forethought will limit its effectiveness.

Java and C# programmers sometimes take the advice to "program to an interface" literally, as the interface is an actual construct in those languages.

This only scratches the surface of Tightly vs Loosely coupled code. In Part 2, of this article, we will explore how we can modify the Singleton pattern to eliminate some of the problems we have discussed.

Back from the salt mines

05 November 2012

I have been working a crazy amount of hours to finish a project. Which was unfortunate, because I missed the first comments posted to my site! I have approved the comments and will address the requests as soon as I am able:) I have added the source code I used for writing the Rails Authentication and Authorization Articles I haven't reviewed the code for months and sometimes the gremlins creep in when you aren't looking. At least that's what I tell myself. The alternative is that I didn't get it correct the first time! gasp. I plan to have a new blog on Singleton's out this week.

Abstract Factory Pattern

04 September 2012

Provides an interface for creating families of related or dependent objects without specifying their concrete classes.

This design pattern will be useful building attributes of the different types of heroes we will need. All the files can be downloaded.

Abstract Factory Pattern
Abstract Factory Pattern

As I have mentioned before Ruby doesn't need to define the abstract classes or the interfaces. I defined different classes for the various hero attributes. This isn't necessary with Ruby but it made the use of the Abstract Factory Pattern in the code more obvious.

Abstract-Factory-Pattern.rb





class Skill
  attr_accessor :description 
  def initialize(description)
    @description = description
  end
end

class Feat
  attr_accessor :description 
  def initialize(description)
    @description = description
  end
end

class Race
  attr_accessor :description 
  def initialize(description)
    @description = description
  end
end

class Talent
  attr_accessor :description 
  def initialize(description)
    @description = description
  end
end

class Power
  attr_accessor :description 
  def initialize(description)
    @description = description
  end
end

class BodyType
  attr_accessor :description 
  def initialize(description)
    @description = description
  end
end

class FantasyHeroAttributes
  def create_skill()
    Skill.new("I can build catupults!")
  end 
 
  def create_feat()
    Feat.new("I can dodge arrows!")
  end 
  
  def create_race()
    Race.new("I am an elf.")
  end 
 
end

class SuperHeroAttributes
  def create_talent()
    Talent.new("I have in depth knowledge of guns and how to build them.")
  end 
 
  def create_power()
    Power.new("I can fly!")
  end 
  
  def create_body_type()
    BodyType.new("I am a robot.")
  end 
 
end

module HandleAttributeFactory
  attr_accessor :attribute_factory_class, :attributes, :attribute_factory
  def initialize(attribute_factory_class)
    @attribute_factory_class = attribute_factory_class
    @attributes = Hash.new()
  end
end


class TechHero
  include HandleAttributeFactory
 
  def describe
    puts 'I am a technology based hero!'
    @attribute_factory = @attribute_factory_class.new()
    @attribute_factory_class.instance_methods(false).each { | the_method |
      @attributes[the_method.to_s] = @attribute_factory.send the_method
    }
    @attributes.each { | the_attribute |
      puts the_attribute[1].description
    }    
  end
end


class HeroCreator
  def createHero(hero_type,attribute_factory=nil)
    @heroClass = self.class.const_get("#{hero_type}Hero")
    @heroClass.new(attribute_factory)
  end
end

creator = HeroCreator.new()


hero = creator.createHero('Tech',SuperHeroAttributes)
hero.describe

hero = creator.createHero('Tech',FantasyHeroAttributes)
hero.describe

Factory Method Pattern

28 August 2012

Defines an interface for creating an object, but lets subclasses decide which class to instantiate. Factory method lets a class defer instantiation to subclasses.

This design pattern will come in handy when we want a character generator that will not only build SuperHeroes but Fantasy Heroes as well. We define an interface and build different hero creators from this interface. These hero creators will then build heroes. All the files can be downloaded.

Factory Method Pattern
Factory Method Pattern

Finally we can build these classes and objects in Ruby as seen in the following code. One difference between the code and the class diagram is that Ruby doesn't need to define the abstract classes. Nor does it need to define separate creators for the Fantasy and Super Heros such as Java would have to do.

Factory-Method-Pattern.rb



class TechHero
  def describe
    puts 'I have a suit of wondrous technology!'
  end
end


class MutantHero
  def describe
    puts 'I genetic legacy of wonder!'
  end
end


class FighterHero
  def describe
    puts 'I am an unparalleled warrior!'
  end
end

class ThiefHero
  def describe
    puts 'I an a sneak of no mean skill!'
  end
end


class HeroCreator
  def createHero(hero_type)
    @heroClass = self.class.const_get("#{hero_type}Hero")
		@hero = @heroClass.new()
		@hero
  end
end

creator = HeroCreator.new()

hero = creator.createHero('Tech')
hero.describe

hero = creator.createHero('Mutant')
hero.describe()

hero = creator.createHero('Fighter')
hero.describe()

hero = creator.createHero('Thief')
hero.describe()

Decorator Pattern

13 August 2012

Attaches additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality

This design pattern would be useful when you consider the attributes of of a Super Hero. A hero can have a normal strength and yet have a power that enhances his strength beyond human norms. Also heros can achieve greater strength via mechanical or pharmaceutical means.

This is achieved by the decorator objects swallowing the core object and other decorator objects. This swallowing is called composition. Any object is then accessible as long as it is part of the composition. This access is usually defined through abstraction or an interface. Through the interface the innermost object to the outermost can make calls through the agreed method to the other objects.

Decorator Pattern Encapsulation
Decorator Pattern Encapsulation

Taking this basic concept we can then build the class structure below. The classes in italics are abstract.

Decorator Pattern Class
Decorator Pattern Class

Finally we can build these classes and objects in Ruby as seen in the following code. One difference between the code and the class diagram is that Ruby doesn't need to define the abstract classes. It more or less defines an interface using a module.

Decorator-Pattern.rb


module HeroDecorator
  def initialize(heroDecorated)
    @heroDecorated = heroDecorated
  end
end


class Hero
  def name
    "Bob"
  end

  def description
    "He is really strong"
  end

  def strength
    40
  end

  def intelligence
    10
  end
end


class CombatDrugs
	include HeroDecorator
  def strength
    @heroDecorated.strength() + 40
  end

  def intelligence
    @heroDecorated.intelligence() + -5  
  end
end


class SuperStrength
  include HeroDecorator
  def strength
    @heroDecorated.strength() + 40
  end

  def intelligence
    @heroDecorated.intelligence() + 0  
  end
end

bob = CombatDrugs.new(SuperStrength.new(Hero.new()))

puts "Strength=" + bob.strength.to_s
puts "Intelligence=" + bob.intelligence.to_s

Strategy Pattern

18 July 2012

Defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from the clients that use it.

If we were to use this pattern to associate a Super Hero's talents and powers to the hero themselves it might look like the diagram below.

Strategy Pattern
Strategy Pattern

Experience tells me I would store the powers in a persistence layer (database) and would need something more flexible. Such as a name attribute for talents and powers that would let me use one class each for talents and powers.

The Lost Programmer

08 July 2012

Why did we start programming? I started programming to create worlds of wonder. To assist me in engaging with alternate realities. The first program I ever tried to write, on my own, was a character generator for the Marvel Super Heroes role playing game. I attempted this feat using the venerable Commodore 64 and its included Basic programming language. I have never completed it.

Do we fail ourselves as a programmer by allowing time and life to distract us from our joys? I enjoy shaping data and finding solutions to problems. Thankfully the world at large is willing to pay me for it! However, my day to day work alone, does not bring me all the satisfaction I desire in my work. The parts I most enjoy in my day to day work are those small pieces that I build to make my own life easier or more interesting. This often has the effect of making it easier to meet my employer's goals. While this is nice it does not satisfy the desire to just have fun!

Admittedly, living only for ones own desires can quickly pall. Not to mention that it often doesn't pay very well! More importantly when trying to achieve common goals by working together we are exposed to others. This conveniently happens, quite often, when working for an employer. We as programmers grow more skilled and competent by exposure to others from whom we can learn and be challenged. My early career was hampered by working positions that lacked senior developers who could mentor me. Working alone does give you a "can do" attitude and an independent streak! Like Nnanji in the The Destiny of the Sword (Dave Duncan) challenge those around you to learn! Find that better swordsman and learn something. You won't become the greatest swordsman in the world by watching He-Man reruns! In short working to achieve others goals is not wasted time or effort. Even if periodically it seems like you have been stranded on Dagobah with only a horde of Zombies!!! to keep you company.

In modern software development the programmer is little more than a subroutine in the system. When terms like Project Management, Change Management and CMMI are bandied about on a daily basis you quickly realize that large organizations tend to view programs as the by-product of their mammoth bureaucratic tar pit. It can be quite easy to lose sight of the joy in our work when it is obscured by the blizzard of paperwork that proliferates in such systems.

Programmer's should be more like the poet who write's newspaper copy by day and pens his fantasies and despairs by night in verse. Where is our Programmer Laurete? Where are the application haikus? Where is our Shakespeare? We have the Art of Programming (Donald Knuth) which delves into subjects so arcane as to be barely intelligible to many programmers yet alone the laymen. A laymen can still appreciate a poem such as Casey At Bat or The Raven. Where is the equivalent program? XKCD? Angry Birds?

Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears.

- Edgar Allen Poe

Is it even possible for a program to elicit an emotional response as naturally as a painting? Words and therefore poetry is a form of programming. Programs which elicit emotional responses from the reader once they are trained to read.

Do we then need to mandate a certain level of algorythmic knowledge of all students much as we demanded literacy in language and mathematics? Certainly algorythms which is just a fancy way to say problem solving is already widly acknowledged to be necessary even critical to our nation. Whether or not you read modern computer languages we as a race can indeed appreciate solutions to problems when they are presented in an understandable format.

For example a recipe that results in delicious food is merely a program or algorythm which the cook executes. Once again this is an area that is widely considered an art. Though the recent trend toward molecular cooking may take some of the mystery out of it. Donald Knuth is leading us down the path towards using natural language to write our programs. Though how the written word can be described as "natural" is somewhat beyond me. Business proposals are written using "natural" language and yet are not considered art. Art requires inspiration and a step beyond the mundane.

For this to happen we must follow our muse! What is your muse? I have no idea! Perhaps the Super Cool Marvel Super Heroes character generator is mine and perhaps not. That is however, where I am going to start. Using Ruby on Rails I will write this long delayed character generator. It is high time that I once again move from a place of work to a place of play on the Matrix of T'sel as described in John Dalmas' The Regiment. Eddie the poet might have put it thus.

With me programming has not been a purpose, but a passion.

Ruby on Rails Authentication and Authorization Part 5

09 May 2012

In Part 1 of this series we described what we wanted our application to accomplish and installed gems we would need to work with. In Part 2 we generate our application framework and integrate Devise into it. In Part 3 we generate the MVC for roles and customize them to allow for building hierarchies. In Part 4 we customize Devise to integrate roles and users. This this part we will tie all of this together and emerge with a full blow authentication and authorization framework for any future applications.

To paraphrase Clausewitz "No application design survives contact with reality." The original design called for the use of declarative_authorization but we are going to be switching to CanCan for authorization. The reason for this is that declarative_authorization uses a static file to define roles and CanCan will allow us to define roles from a database. This will allow us to build permissions during runtime.

Since we are no longer using declarative_authorization and are using CanCan the CanCan gem needs to be installed and the Gemfile updated like so.

Terminal window in the mysecurity directory


bash-4.2$ gem install cancan
Fetching: cancan-1.6.7.gem (100%)
Successfully installed cancan-1.6.7
1 gem installed
Installing ri documentation for cancan-1.6.7...
Installing RDoc documentation for cancan-1.6.7...
bash-4.2$
mysecurity/Gemfile


source 'http://rubygems.org'

gem 'rails', '3.1.3'

gem 'sqlite3'
gem 'devise'
gem 'cancan'


# Gems used only for assets and not required
# in production environments by default.
group :assets do
  gem 'sass-rails',   '~> 3.1.5'
  gem 'uglifier', '>= 1.0.3'
end

gem 'jquery-rails'

group :test do
  gem 'turn', '~> 0.8.3', :require => false
end

Now that our Gemfile is in order we will want a table to store the permissions. The first step will be to design the table and update our database diagram as shown below.

Authentication Authorization Security Model
Authentication Authorization Security Model

The design will allow us to assign controllers and actions to roles. Using Merriam-Webster's thesaurus I used regulator for model and conduct for action. I did this to avoid any name conflicts that might occur in the Rails code. You might be confused because regulator is not a synonym for model. Before I understood CanCan I was going to use controller and action for permissions:) Our next step will be to generate the model as shown below.

Terminal window in the mysecurity directory


bash-4.2$ rails generate scaffold role_permission role_id:integer regulator:string conduct:string
      invoke  active_record
      create    db/migrate/20120410182942_create_role_permissions.rb
      create    app/models/role_permission.rb
      invoke    test_unit
   identical      test/unit/role_permission_test.rb
   identical      test/fixtures/role_permissions.yml
       route  resources :role_permissions
      invoke  scaffold_controller
      create    app/controllers/role_permissions_controller.rb
      invoke    erb
      create      app/views/role_permissions
      create      app/views/role_permissions/index.html.erb
      create      app/views/role_permissions/edit.html.erb
      create      app/views/role_permissions/show.html.erb
      create      app/views/role_permissions/new.html.erb
      create      app/views/role_permissions/_form.html.erb
      invoke    test_unit
      create      test/functional/role_permissions_controller_test.rb
      invoke    helper
      create      app/helpers/role_permissions_helper.rb
      invoke      test_unit
      create        test/unit/helpers/role_permissions_helper_test.rb
      invoke  assets
      invoke    coffee
      create      app/assets/javascripts/role_permissions.js.coffee
      invoke    scss
      create      app/assets/stylesheets/role_permissions.css.scss
      invoke  scss
   identical    app/assets/stylesheets/scaffolds.css.scss
bash-4.2$

With our table in hand we can define the relationship between roles and role_permissions.

mysecurity/app/models/role.rb


class Role < ActiveRecord::Base
  has_many :role_children, :foreign_key => 'parent_id', :class_name => 'RoleRole'
  has_many :children, :through => :role_children
  
  has_many :role_parents, :foreign_key => 'role_id', :class_name => 'RoleRole'
  has_many :parents, :through => :role_parents

  has_many :permissions, :foreign_key => 'role_id', :class_name => 'RolePermission'


end

What we will end up with is a Role edit page where the user can assign and remove permissions for a role. We will end up with something close to the screen below.

Role Permissions added to Role Edit Screen
Role Permissions added to Role Edit Screen

To accomplish this will require the modification and creation of several files. There were several pieces of advice on how to work with AJAX and rails in the world wide web. In the end the only method that worked well was to start from scratch using JQuery and figure it out. This is the path we will be going down today.

The first file we will modifiy is the application layout to include application JavaScript and CSS as well as controller specific JavaScripat and CSS. This code follows.

mysecurity/app/views/layouts/application.html.erb


<!DOCTYPE html>
<html>
<head>
  <title>Mysecurity</title>
  <%= stylesheet_link_tag    'application' %>
  <%= stylesheet_link_tag    params[:controller] %>
  <%= javascript_include_tag 'application' %>
  <%= javascript_include_tag params[:controller] %>
  <%= csrf_meta_tags %>
</head>
<body>

       <p class="notice"><%= notice %></p>
       <p class="alert"><%= alert %></p>
      <div id="user_login_box" style="float:right">
      <% if user_signed_in? -%>
          <%= current_user.email %> |
          <%= link_to 'My info', edit_user_registration_path %> |
          <%= link_to 'Sign out', destroy_user_session_path, :method => :delete %>
      <% else %>
        <%= link_to "Sign up", new_user_registration_path %> or <%= link_to "sign in", new_user_session_path %>
      <% end %>
      </div>


<%= yield %>

</body>
</html>

Our next move will be to modify the Roles edit page to pull in via AJAX the Role Permission pages. We need for the role_permissions index page to load by default and to take the role_id as a parameter. We also need the edit and show pages to load into the page seemlessly. The majority of the code to support AJAX will be in the allPages.js file we will create. The code that follows is needed to make this happen.

mysecurity/app/views/roles/edit.html.erb




<script>
  $(document).ready(function(){
    defaultLocation();
  });

  function defaultLocation() {
    fillAjaxHolder('/role_permissions?role_id=<%= @role.id %>');
  }
</script>


<h1>Editing role</h1>

<%= render 'form' %>



<%= link_to 'Show', @role %> |
<%= link_to 'Back', roles_path %>

<h2>Permissions</h2>
<div id="ajaxHolder">

</div>

The main purpose of allPages.js is abstract the functionality out of a specific page so that I can reuse it with other pages when opportunity allows.

mysecurity/app/assets/javascripts/allPages.js


$.ajaxSetup({ cache: false });



function submitFormPost(theForm, theFunction ) {
  $.post(theForm.action, $("#" + theForm.id).serialize(),theFunction,'html');
}


  function fillAjaxHolder(theURL) {
    $.get(theURL,
      function(data, statusText, xhrObject) {
        $('#ajaxHolder').html(data);
      });
      return false;
  }

  function writeAjaxHolder(theContent) {
    $('#ajaxHolder').html(theContent);
    return false;
  }


  $(".ajaxDeleteLink").live('click',function(event){
    event.preventDefault();
    $.post(event.target,
    "_method=DELETE",
    function(data) {
      writeAjaxHolder(data);
    },
    'html');
  });


  $('.ajaxLink').live('click',function(event){
    event.preventDefault(); // Prevent link from following its href
    fillAjaxHolder(event.target);
    return false;
  });

  $('.ajaxSubmit').live('click',function(event){
    event.preventDefault(); // Prevent link from following its href
    submitFormPost(event.target.form,
      function(data) {
        writeAjaxHolder(data);
      }
    );
  });

This code expects the role_permissions controller to be able to handle a role_id parameter. Additionally we want it to return to the index page after a permission is the subject of a CRUD operation. Normally I would perform a redirect after these operations to permit problems during a page refresh. Since these pages are being pulled in via AJAX that will not be needed and we can render the index page after each operation. This is the primary purpose of the index_helper method. This also contains helper methods to load a list of all models and actions into JavaScript which will be used in the Role Permissions edit page. At the top of the controller we set "layout nil" so that the layout files will not be loaded. These two files are shown below.

mysecurity/app/helpers/role_permissions_helper.rb



module RolePermissionsHelper

  def index_helper
    if params[:role_id].nil?
      if params[:role_permission][:role_id].nil?
        log_error " role_id parameter is invalid!"
      else
        @the_role_id = params[:role_permission][:role_id]
      end
    else
      @the_role_id = params[:role_id]
    end

    begin
      @role_permissions = RolePermission.find(:all,:conditions => ["role_id=?",@the_role_id])
    rescue ActiveRecord::RecordNotFound
      log_error "record not found role_id=" + params[:role_id]
    end
  end

  def prepare
    Rails.application.eager_load!
    @roles = Role.all
    @regulators = get_models
    @conducts = get_actions
  end

  def get_models
    regulators = Array.new
    ActiveRecord::Base.descendants.each{ |model|
      regulators[regulators.length] = model.name
    }
    return regulators
  end

  def get_actions
    conducts = Array.new
    ApplicationController.descendants.each { |regulator|
      the_actions = regulator.action_methods
      the_actions.each {|the_action|
        conducts[conducts.length] = the_action
      }
    }
    return conducts
  end
end
mysecurity/app/controllers/role_permissions_controller.rb



class RolePermissionsController < ApplicationController
  layout nil
  # GET /role_permissions
  # GET /role_permissions.json



  def index
    index_helper

    respond_to do |format|
      format.html # index.html.erb
      format.json { render json: @role_permissions }
    end
  end

  # GET /role_permissions/1
  # GET /role_permissions/1.json
  def show
    @role_permission = RolePermission.find(params[:id])
    #authorize! :show, @role_permission
    respond_to do |format|
      format.html # show.html.erb
      format.json { render json: @role_permission }
    end
  end

  # GET /role_permissions/new
  # GET /role_permissions/new.json



  def new
    prepare
    @role_permission = RolePermission.new
    @role_permission.role_id = params[:role_id]
    respond_to do |format|
      format.html # new.html.erb
      format.json { render json: @role_permission }
    end
  end

  # GET /role_permissions/1/edit
  def edit
    prepare
    @role_permission = RolePermission.find(params[:id])
  end

  # POST /role_permissions
  # POST /role_permissions.json
  def create
    @role_permission = RolePermission.new(params[:role_permission])

    respond_to do |format|
      if @role_permission.save
        format.html { 
          index_helper
          render :action => 'index'
        }
        format.json { render json: @role_permission, status: :created, location: @role_permission }
      else
        format.html { render action: "new" }
        format.json { render json: @role_permission.errors, status: :unprocessable_entity }
      end
    end
  end

  # PUT /role_permissions/1
  # PUT /role_permissions/1.json
  def update
    @role_permission = RolePermission.find(params[:id])

    respond_to do |format|
      if @role_permission.update_attributes(params[:role_permission])
        format.html {
          index_helper
          render :action => 'index'
        }
        format.json { head :ok }
      else
        format.html { render action: "edit" }
        format.json { render json: @role_permission.errors, status: :unprocessable_entity }
      end
    end
  end

  # DELETE /role_permissions/1
  # DELETE /role_permissions/1.json
  def destroy
    @role_permission = RolePermission.find(params[:id])
    @role_permission.destroy

    respond_to do |format|
      format.html {
        index_helper
        render :action => 'index'
      }
      format.json { head :ok }
    end
  end


  private :prepare
end

In the role_permissions controller you will see a reference to a log_error method which I defined in applicaiton_helper.rb as displayed below.

mysecurity/app/helpers/application_helper.rb


module ApplicationHelper
  def log_seperator
    return "***************************************************"
  end

  def log_error(message)
    logger.error(log_seperator);
    logger.error(controller_name + '.' + action_name + ":  " + message)
  end

end

Now that our controllers are in order we can modify our views to work with them. The default page to be displayed is the Role Permissions index and that is where we should start. The most important change here is that we have added CSS classes to the links so that the jQuery code in allPages.js can find and bind to the links. We will perform the same on the new, show and edit pages as well. These four files follow.

mysecurity/app/views/role_permissions/index.html.rb


<table class="showTableBorder">
  <tr>
    <th class="firstCell">Controller</th>
    <th class="lastCell">Action</th>
    <th class="lastCell firstCell" colspan="3"></th>
  </tr>
  <%  @role_permissions.each do |role_permission| %>
    <tr>
      <td class="firstCell"><%= role_permission.regulator %></td>
      <td class="middleCell"><%= role_permission.conduct %></td>
      <td class="middleCell"><%= link_to 'Show', role_permission, :class => 'ajaxLink' %></td>
      <td class="middleCell"><%= link_to 'Edit', edit_role_permission_path(role_permission), :class => 'ajaxLink' %></td>
      <td class="lastCell"><%= link_to 'Destroy', role_permission_path(role_permission,:role_id => role_permission.role_id), :class => 'ajaxDeleteLink' %></td>
    </tr>
  <%   end %>
</table>

<br />

<%= link_to 'New Role permission', new_role_permission_path(:role_id => @the_role_id), :class => 'ajaxLink' %>
mysecurity/app/views/role_permissions/new.html.rb


<h3>New Permission</h3>

<%= render 'form' %>

<%= link_to 'Back', role_permissions_path(:role_id => params[:role_id]), :class => 'ajaxLink' %>
mysecurity/app/views/role_permissions/show.html.rb


<h3>Show Permission</h3>
<p>
  <b>Regulator:</b>
  <%= @role_permission.regulator %>
</p>

<p>
  <b>Conduct:</b>
  <%= @role_permission.conduct %>
</p>


<%= link_to 'Edit', edit_role_permission_path(@role_permission), :class => 'ajaxLink' %> |
<%= link_to 'Back', role_permissions_path(:role_id => @role_permission.role_id), :class => 'ajaxLink' %>
mysecurity/app/views/role_permissions/edit.html.rb


<h3>Edit Permission</h1>

<%= render 'form' %>

<%= link_to 'Show', @role_permission, :class => 'ajaxLink' %> |
<%= link_to 'Back', role_permissions_path(:role_id => @role_permission.role_id), :class => 'ajaxLink' %>
<%= render 'javascript' %>

This leaves us with our _form.html.erb partial which is used by three of the proceeding files.

mysecurity/app/views/role_permissions/_form.html.rb


<%= form_for(@role_permission) do |f| %>
  <% if @role_permission.errors.any? %>
    <div id="error_explanation">
      <h2><%= pluralize(@role_permission.errors.count, "error") %> prohibited this role_permission from being saved:</h2>

      <ul>
      <% @role_permission.errors.full_messages.each do |msg| %>
        <li><%= msg %></li>
      <% end %>
      </ul>
    </div>
  <% end %>

  <div class="field">
    <%= f.hidden_field :role_id %>
  </div>
  <div class="field">
    <%= f.label 'Controller' %><br />
    <%= collection_select(:role_permission, :regulator, @regulators, :to_s, :to_s)  %>
  </div>
  <div class="field">
    <%= f.label 'Action' %><br />
    <%= collection_select(:role_permission, :conduct, @conducts, :to_s, :to_s) %>
  </div>
  <div class="actions">
    <%= f.submit  (action_name.upcase == 'EDIT' ? 'Update' : 'Add') + " Permission", :class => "ajaxSubmit" %>
  </div>
<% end %>

The next files to modify are the application.js and application.cs assets. Rails Assets are a subject all to themselves. Below are the modified files.

mysecurity/app/assets/javascripts/application.js



// This is a manifest file that'll be compiled into including all the files listed below.
// Add new JavaScript/Coffee code in separate files in this directory and they'll automatically
// be included in the compiled file accessible from http://example.com/assets/application.js
// It's not advisable to add code directly here, but if you do, it'll appear at the bottom of the
// the compiled file.
//
//= require jquery
//= require jquery_ujs
//= require allPages
mysecurity/app/assets/stylesheets/application.css


/*
 * This is a manifest file that'll automatically include all the stylesheets available in this directory
 * and any sub-directories. You're free to add application-wide styles to this file and they'll appear at
 * the top of the compiled file, but it's generally better to create a new file per style scope.
 *= require_self
 *= require tables
*/

As we can see the application.css file references a table.css file which needs to be added and is diplayed below.

mysecurity/app/assets/javascripts/application.js


/* 
    Document   : tables
    Created on : Apr 19, 2012
    Author     : lynchcs
*/

.showTableBorder {
  border-style: solid;
  border-color: Black;
  border-left-width: .2em;
  border-right-width: .2em;
  border-top-width: .15em;
  border-bottom-width: .15em;

  padding: 0px;
  margin: 0px;
  border-collapse: 0px;
  border-spacing: 0px;
}

.showTableBorder td, .showTableBorder th {
  padding: .5em;
}

.showTableBorder tr {
  border-style: solid;
  border-color: Black;
  border-width: 0px;
  padding: 0px;
  margin: 0px;
}

.showTableBorder th {
  border-style: solid;
  border-color: Black;
  border-width: .05em;
  border-bottom-width: .1em;
}

.showTableBorder td {
  border-style: solid;
  border-color: Black;
  border-width: .05em;
}

.showTableBorder .firstCell {
  border-left-width: 0px;
}

.showTableBorder .lastCell {
  border-right-width: 0px;
}

Before proceeding further you should create one or two users. This can be done by going to http://localhost:3000/users/new . You can also do this by going to http://localhost:3000/user/sign_up. I used "test@test.com" for my user name and "tester" for my password.

With our users created we are ready to get to the heart of the matter! CanCan relies on a model called Ability to determine whether a user has permissions or not. This file can be generated as shown below.

Terminal window in the mysecurity directory


bash-4.2$ rails g cancan:ability
      create  app/models/ability.rb
bash-4.2$

We will then modify mysecurity/app/models/ability.rb to determine the permissions assigned to the user. We will do this by looping through the users roles and permissions.

mysecurity/app/models/ability.rb


class Ability
  include CanCan::Ability

  def initialize(user)
    user.roles.each { |role|
      role.permissions.each { |permission|
        can permission.conduct.to_sym, permission.regulator.constantize
      }
    }

  end
end

The last part is execute the authorization check in a controller. Remember we haven't assigned any permissions to our user yet. Modify roles_controller.rb and change the show action to the following.

mysecurity/app/models/ability.rb


  def show
    @role = Role.find(params[:id])
    authorize! :show, @role

    respond_to do |format|
      format.html # show.html.erb
      format.json { render json: @role }
    end
  end

Start your application and login using the user account you created earlier. The results you should see is that you can see the index and edit pages but will receive an exception when you try to show a role. To automatically add the checks to all actions add "load_and_authorize_resource" to the top of the controller.

We now have a working authentication and authorization system. Since we are pulling the permissions from a database keep in mind that we have a chicken or an egg situation. We can't use the interface to add permissions because we don't have permissions yet. Your options are to remove the CanCan authorization checks long enough to add permissions or to go into the database directly and enter the necessary records.

Ruby on Rails JavaScript and CSS Assets

17 April 2012

Learned today that CSS and JavaScript Assets in Rails 3 are minified automatically for you. Additionally the application.js and application.css can take "require" statements and include any JavaScript into one file called application.js or application.css. I am guessing the logic here is that fewer javascript includes makes for faster page loading. An example is shown below.

mysecurity/app/assets/javascripts/application.js


// This is a manifest file that'll be compiled into including all the files listed below.
// Add new JavaScript/Coffee code in separate files in this directory and they'll automatically
// be included in the compiled file accessible from http://example.com/assets/application.js
// It's not advisable to add code directly here, but if you do, it'll appear at the bottom of the
// the compiled file.
//
//= require jquery
//= require jquery_ujs
//= require_tree .

The "//= require jquery" includes the jQuery JavaScript APi which is included as a gem file. The "//= require_tree ." seems to include all javascript files into the page. I will be taking out the require_tree which was placed in as default.

Create your own shape for Dia

13 April 2012

I needed to create a System Flow Diagram. I wanted to use Dia but I find their basic shapes unaesthetic. So I used Dia Installer Website to learn how. Between their custom objects and directions on the site it was relatively easy. Of course weeding through the less helpful sites and finding this information was somewhat difficult.

A sheet is a collection of shapes. A shape is a wrapper around a SVG image. If your browser support SVG you will be able to see the SVG image I created using Inkscape.

All of the files and more are in the 20120413Chris-Dia-Shapes.tar.gz file.

Action SVG

Action.shape


<?xml version="1.0" encoding="UTF-8"?>
<shape xmlns="http://www.daa.com.au/~james/dia-shape-ns" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
  <name>Action</name>
  <icon>Action.png</icon>
  <connections>
    <point x="1" y="1" main="yes"/>
    <point x="1" y="0" />
    <point x="0" y="1" />
    <point x="2" y="1" />
    <point x="1" y="2" />
  </connections>
  <textbox x1="0" y1="0" x2="2" y2="2" />
  <svg:svg>
    <svg:rect style="fill:default;stroke:bg;stroke-width:0;" x="0" y="0" width="2" height="2"/>
    <svg:image x="0" y="0" width="2" height="2" xlink:href="./Action.svg"/>
    
  </svg:svg>

</shape>
Action.svg


<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!-- Created with Inkscape (http://www.inkscape.org/) -->

<svg
   xmlns:osb="http://www.openswatchbook.org/uri/2009/osb"
   xmlns:dc="http://purl.org/dc/elements/1.1/"
   xmlns:cc="http://creativecommons.org/ns#"
   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
   xmlns:svg="http://www.w3.org/2000/svg"
   xmlns="http://www.w3.org/2000/svg"
   xmlns:xlink="http://www.w3.org/1999/xlink"
   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
   width="100"
   height="50"
   id="svg3777"
   version="1.1"
   inkscape:version="0.48.1 r9760"
   sodipodi:docname="Action.svg">
  <defs
     id="defs3779">
    <linearGradient
       id="linearGradient4435">
      <stop
         style="stop-color:#080808;stop-opacity:1;"
         offset="0"
         id="stop4437" />
      <stop
         id="stop4451"
         offset="0.07860228"
         style="stop-color:#7d6019;stop-opacity:1;" />
      <stop
         id="stop4449"
         offset="0.13536197"
         style="stop-color:#e8bd56;stop-opacity:1;" />
      <stop
         id="stop4443"
         offset="0.50731438"
         style="stop-color:#dfac33;stop-opacity:1;" />
      <stop
         style="stop-color:#e8bd56;stop-opacity:1;"
         offset="0.83510321"
         id="stop4447" />
      <stop
         style="stop-color:#7d6019;stop-opacity:1;"
         offset="0.9279992"
         id="stop4445" />
      <stop
         style="stop-color:#000000;stop-opacity:1;"
         offset="1"
         id="stop4439" />
    </linearGradient>
    <linearGradient
       id="linearGradient3911"
       osb:paint="gradient">
      <stop
         style="stop-color:#0000ff;stop-opacity:0.99350649;"
         offset="0"
         id="stop3913" />
      <stop
         id="stop4427"
         offset="0.5"
         style="stop-color:#11171a;stop-opacity:0.52156866;" />
      <stop
         style="stop-color:#ff0000;stop-opacity:0.04313726;"
         offset="1"
         id="stop3915" />
    </linearGradient>
    <linearGradient
       inkscape:collect="always"
       xlink:href="#linearGradient4435"
       id="linearGradient4441"
       x1="95"
       y1="12"
       x2="6.5"
       y2="43.5"
       gradientUnits="userSpaceOnUse" />
  </defs>
  <sodipodi:namedview
     id="base"
     pagecolor="#ffffff"
     bordercolor="#666666"
     borderopacity="1.0"
     inkscape:pageopacity="0.0"
     inkscape:pageshadow="2"
     inkscape:zoom="2"
     inkscape:cx="30"
     inkscape:cy="0"
     inkscape:document-units="px"
     inkscape:current-layer="layer1"
     showgrid="false"
     inkscape:window-width="1280"
     inkscape:window-height="938"
     inkscape:window-x="0"
     inkscape:window-y="45"
     inkscape:window-maximized="1" />
  <metadata
     id="metadata3782">
    <rdf:RDF>
      <cc:Work
         rdf:about="">
        <dc:format>image/svg+xml</dc:format>
        <dc:type
           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
        <dc:title></dc:title>
      </cc:Work>
    </rdf:RDF>
  </metadata>
  <g
     inkscape:label="Layer 1"
     inkscape:groupmode="layer"
     id="layer1"
     transform="translate(0,-3107.0866)">
    <rect
       style="fill:url(#linearGradient4441);fill-rule:evenodd;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;fill-opacity:1"
       id="rect4433"
       width="99"
       height="51"
       x="0.5"
       y="0"
       transform="translate(0,3107.0866)"
       ry="23.089012" />
  </g>
</svg>
Chris_Activity.sheet



<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<sheet xmlns="http://www.lysator.liu.se/~alla/dia/dia-sheet-ns">
<!--Dia-Version: 0.97-->
<!--File: /home/lynchcs/.dia/sheets/Chris_Activity.sheet-->
<!--Date: Thu Apr 12 13:59:33 2012-->
<!--For: lynchcs-->

<name>Chris Activity</name>
<description></description>
<contents>
<!--add shapes here-->
<object name="Action">
<description>System Flow Action</description></object>
<object name="Decision">
<description>System Flow Decision</description></object>
<object name="Arrow1">
<description>System Flow Arrow1</description></object>


</contents></sheet>

Ruby on Rails Authentication and Authorization Part 4

06 April 2012

In Part 3 of the series we modified the model and views generated by the Rails utilities to allow for creating hierarchical roles. In Part 4 we will perform almost the same series of steps to allow us to assign Roles to Users.

Our first step will be to use Rails to generate a model for your "user_role" linking table.

Terminal window in the mysecurity directory


bash-4.2$ rails generate model user_role user_id:integer role_id:integer
      invoke  active_record
      create    db/migrate/20120302182538_create_user_roles.rb
      create    app/models/user_role.rb
      invoke    test_unit
      create      test/unit/user_role_test.rb
      create      test/fixtures/user_roles.yml
bash-4.2$ rake db:migrate
==  CreateUserRoles: migrating ================================================
-- create_table(:user_roles)
   -> 0.0010s
==  CreateUserRoles: migrated (0.0010s) =======================================

bash-4.2$

The generator will build the user_role.rb file as shown below.

mysecurity/app/models/user_role.rb (unmodified)


class UserRole < ActiveRecord::Base
end

We go ahead and modify the file to link UserRole to User and to Role.

mysecurity/app/models/user_role.rb (modified)


class UserRole < ActiveRecord::Base
  belongs_to :user, :foreign_key => 'user_id', :class_name => 'User'
  belongs_to :role, :foreign_key => 'role_id', :class_name => 'Role'
end

Below we have the User model that was generated by Devise for us.

mysecurity/app/models/user.rb (unmodified)


class User < ActiveRecord::Base
  # Include default devise modules. Others available are:
  # :token_authenticatable, :encryptable, :confirmable, :lockable, :timeoutable and :omniauthable
  devise :database_authenticatable, :registerable,
         :recoverable, :rememberable, :trackable, :validatable

  # Setup accessible (or protected) attributes for your model
  attr_accessible :email, :password, :password_confirmation, :remember_me
end

We will modify the user.rb file to add the relationship between User and Role. One difference here is that we need to add ":role_ids" to the list of accessible attributes. Only those fields of the model passed to "attr_accessible" will be updateable. This message "WARNING: Can't mass-assign protected attributes: role_ids" led me to this discovery. Fortunately other developers had been there before me and had the answers!

mysecurity/app/models/user.rb (modified)


class User < ActiveRecord::Base
  has_many :user_roles, :foreign_key => 'user_id', :class_name => 'UserRole'
  has_many :roles, :through => :user_roles
  
  # Include default devise modules. Others available are:
  # :token_authenticatable, :encryptable, :confirmable, :lockable, :timeoutable and :omniauthable
  devise :database_authenticatable, :registerable,
         :recoverable, :rememberable, :trackable, :validatable

  # Setup accessible (or protected) attributes for your model
  attr_accessible :email, :password, :password_confirmation, :remember_me, :role_ids

end

Next we will use the Rails generator to build the scaffolding for the user model.

Terminal window in the mysecurity directory


bash-4.2$ rails generate scaffold_controller user
      create  app/controllers/users_controller.rb
      invoke  erb
      create    app/views/users
      create    app/views/users/index.html.erb
      create    app/views/users/edit.html.erb
      create    app/views/users/show.html.erb
      create    app/views/users/new.html.erb
      create    app/views/users/_form.html.erb
      invoke  test_unit
      create    test/functional/users_controller_test.rb
      invoke  helper
      create    app/helpers/users_helper.rb
      invoke    test_unit
      create      test/unit/helpers/users_helper_test.rb
bash-4.2$

In the following steps I alias devise to use the "user" path and set resources for the users controller in the routes.rb file.

mysecurity/config/routes.rb (unmodified)


Mysecurity::Application.routes.draw do
  resources :roles
  
  devise_for :users

  # Several comments omitted here in the center section.


  root :to => "home#index"

end
mysecurity/config/routes.rb (unmodified)


Mysecurity::Application.routes.draw do
    devise_for :users, :path => 'user'

    resources :roles
    resources :users
  

  # Several comments omitted here in the center section.


  root :to => "home#index"

end

My next step is to copy part of the contents of /devise/registrations/new.html.erb and create the file /devise/registrations/_user_fields.html.erb. This will allow me to include the fields in the /users/_form.html.erb file giving me one location to change the fields for three locations where it is used. The three files that need to be modified follow along with the _form.htm.erb.

/devise/registrations/new.html.erb/_user_fields.htm.erb


 <div><%= f.label :email %><br />
  <%= f.email_field :email %></div>

  <div><%= f.label :password %><br />
  <%= f.password_field :password %></div>

  <div><%= f.label :password_confirmation %><br />
  <%= f.password_field :password_confirmation %></div>
/devise/registrations/new.html.erb/new.htm.erb


<h2>Sign up</h2>

<%= form_for(resource, :as => resource_name, :url => registration_path(resource_name)) do |f| %>
  <%= devise_error_messages! %>

  <%= render :partial => 'user_fields' , :locals => {:f => f} %>

  <div><%= f.submit "Sign up" %></div>
<% end %>

<%= render "links" %>
/devise/registrations/new.html.erb/edit.htm.erb



<h2>Edit <%= resource_name.to_s.humanize %></h2>

<%= form_for(resource, :as => resource_name, :url => registration_path(resource_name), :html => { :method => :put }) do |f| %>
  <%= devise_error_messages! %>

   <%= render :partial => 'user_fields' , :locals => {:f => f} %>

  <div><%= f.label :current_password %> <i>(we need your current password to confirm your changes)</i><br />
  <%= f.password_field :current_password %></div>

  <div><%= f.submit "Update" %></div>
<% end %>

<h3>Cancel my account</h3>

<p>Unhappy? <%= link_to "Cancel my account", registration_path(resource_name), :confirm => "Are you sure?", :method => :delete %>.</p>

<%= link_to "Back", :back %>
/users/_form.htm.erb


<%= form_for(@user) do |f| %>
  <% if @user.errors.any? %>
    <div id="error_explanation">
      <h2><%= pluralize(@user.errors.count, "error") %> prohibited this user from being saved:</h2>

      <ul>
      <% @user.errors.full_messages.each do |msg| %>
        <li><%= msg %></li>
      <% end %>
      </ul>
    </div>

  <% end %>
  <%= render :partial => '/devise/registrations/user_fields' , :locals => {:f => f} %>

  <div class="actions">
    <%= f.submit %>
  </div>
<% end %>

Now our next step is to add the functionality to the view that allows us to assign roles to users.

/users/_role_checkbox.htm.erb


<li><%= check_box_tag "user[role_ids][]", current_role.id, @user.roles.include?(current_role), :disabled => current_role.eql?(@role) %><%= current_role.description %></li><%= the_children %>
/users/_form.htm.erb


<%= form_for(@user) do |f| %>
  <% if @user.errors.any? %>
    <div id="error_explanation">
      <h2><%= pluralize(@user.errors.count, "error") %> prohibited this user from being saved:</h2>

      <ul>
      <% @user.errors.full_messages.each do |msg| %>
        <li><%= msg %></li>
      <% end %>
      </ul>
    </div>

  <% end %>
  <%= render :partial => '/devise/registrations/user_fields' , :locals => {:f => f} %>
  <div class="field">
    <%= f.label 'Roles' %><br />
    <%=  build_role_list('/users/role_checkbox') %>
  </div>
  <div class="actions">
    <%= f.submit %>
  </div>
<% end %>

Start the application server using the "rails server" command and navigate to http://localhost:3000/users/new and you should see a screen similar to the screenshot below.

User Edit Page
User Edit Page

In Part 5 of this series we will finally pull all of the functionality together and secure our web application.

HTML Encoder

04 April 2012

I put together a quick little HTML Encoder for myself using JavaScript. I find I am frequently searching for an online encoder when I am writing my posts. The code is below and I find it entertaining that it was encoded for display using the code itself:).

<span class="codeCaption prettyprint">html-encode</span>


<script>
  function encode() {
    var theHTML = document.getElementById('rawArea').value;
    theHTML= theHTML
            .replace(/&/g, '&')
            .replace(/"/g, '"')
            .replace(/'/g, ''')
            .replace(/</g, '<')
            .replace(/>/g, '>');
    document.getElementById('encodedArea').value=theHTML;
  }
</script>


<form id="rawForm">
   <textarea id="rawArea" rows="5" cols="40"></textarea>
   <input value="Encode" type="button" onclick="encode(); return false;"/>
</form>

<form id="encodedForm">
   <textarea id="encodedArea" rows="5" cols="40"></textarea>
</form>

CodePaLOUsa Coding Contest Part 3

26 March 2012

The JSONP Web Service provided for the contest is no longer available so I am placing the last iteration of code below and will discuss briefly some of the mistakes and difficulties that I had run into. One difficulty I had is not using "$.ajaxSetup({ cache: false });" before making JQuery AJAX calls. The first night I was having difficulties making a second AJAX call to Google and that was the reason. A second problem I had was that the "or" statements I was using with the keyword search of LinkedIn wasn't working and that was due to it not being capitalized. I found this answer on Google's help on searching. I didn't see any mention of it on LinkedIn. One area I did not get to explore was using a dummy account to see how accurate the keyword search was without the additional information of the other accounts my LinkedIn account has associations with.

<span class="codeCaption prettyprint">index.html</span>


<html>
 <head>
  <style>
   #container {
     background-color: Gray;
    width: 100%;
    display: block;
    float: left;
   }
   #informationContainer {
    background-color: Gray;
    width: 70%;
    display: block;
    padding: 1em;
    float: right;
    
   }

   #feedList {
     background-color: Green;
     float: left;
     width: 25%;
     height: 100%;
     overflow: auto;
     max-width: 25%;
     min-width: 25%;
    } 
    #lineItem {
     background-color: #BBBBBB;
     width: 90%;
     float: left;
     clear: both;
    } 

    #mustLogin {
      display: none;
    } 


  </style>
  <script type="text/javascript" src="jquery-1.7.1.js"></script>
  <script type="text/javascript" src="http://platform.linkedin.com/in.js">
      api_key: ###get your own!###
      authorize: true
      onLoad: onLinkedLoad
    </script>
  <script type="text/javascript">
    var lloaded = false
    
    function onLinkedLoad() {
      initiatePage();    
    }
    
    function loginComplete() {
      $("#mustLogin").hide();   	
      showLoggedInMessage();
    }
    
    
    function showLoggedInMessage() {
      $("#informationContainer").append("<div>Click the links to the left to display information about the speaker</div>");
    }
    
    function initiatePage() {
      lloaded = true;
      //alert("lloaded=" + lloaded);
      var jsonUrl="http://winaspectreapi.appspot.com/api/sessions";
      callDataAJAX(jsonUrl);
    }
    
    
    
    function listNames(data) {
      var i=0;
      for(i=0;i < data.length; i++) {
        names = data[i].author.split(" ");
        var searchTitle = cleanTitle(data[i].title);
        searchTitle = searchTitle + " OR software OR louisville OR codepalousa";
        var output = '<div id="lineItem">Speaker:  <a href="#'' + data[i].author + ''" onclick="getLinkedInfo('' + names[0] + '','' + names[names.length - 1] + '','' + searchTitle + ''); return false;">' + data[i].author + '</a><br/>';
        output = output +  'Title:  ' + data[i].title + '<hr/></div>';
        $("#feedList").append(output);
        if(data[i].author.toLowerCase().indexOf("amundsen") > -1) {
         //alert(searchTitle);
        }
      }
    }
    
    function cleanTitleSymbols(theTitle) {
      var i=0;
      var removeWords = ["[\,\:\;\&\?\!\.\=\+\|\)\(\"]","\'s"];
      var newTitle = theTitle.toLowerCase();
      var re = new RegExp("","g");
      for(i=0;i < removeWords.length;i++) {
        re = new RegExp(removeWords[i],"g");
        newTitle=newTitle.replace(re," ");        
      }
      return newTitle;
    }    
    
    function cleanTitle(theTitle) {
      var i=0;
      var removeWords = [".","..W*","your","use","from","the","get","what","you","can","with","within","for","about","are","hour","without","\w*\'t"];
      var newTitle = theTitle.toLowerCase();
      
      newTitle=cleanTitleSymbols(newTitle);
      
      var re = new RegExp("","g");
      for(i=0;i < removeWords.length;i++) {
        re = new RegExp("^" + removeWords[i] + "\s|\s" + removeWords[i] + "\s|\s" + removeWords[i] + "$" ,"g");
        newTitle=newTitle.replace(re," ");        
      }
      newTitle=newTitle.replace(/w+ings/g," ");        
      newTitle=newTitle.replace(/ +/g," ");
      newTitle=newTitle.replace(/^ +| +$/g,"");
      newTitle=newTitle.replace(/'/g,"");
      
      newTitle=newTitle.replace(/ /g," OR ");
      
      return newTitle;
    }
    
    function receiveData(data, status) {
      if($.isArray(data)) {
        listNames(data);
      }
      if(IN.User.isAuthorized()) {
        showLoggedInMessage();
      } else {
        $("#mustLogin").show();	
      }
    }
    
    
    function callDataAJAX(jsonUrl) {
      $.ajax({
         url: jsonUrl,
         dataType: 'jsonp',
         jsonpCallback: 'receiveData'
      });
      
    }
    
    function getLinkedInfo(firstName, lastName, keywords) {
      IN.API.PeopleSearch().fields("firstName", "lastName", "distance", "publicProfileUrl","pictureUrl","headline").params({"first-name":firstName,"last-name":lastName,"keywords": keywords,"sort": "distance"}).result(showResults);
    }
    
    function showResults(result) {
      $("#informationContainer").html('');
      $("#informationContainer").append("<span>Click a link to the left to list possible LinkedIn matches.  The one you want is most likely on top.</span>");
      for (var index in result.people.values) {
       var profHTML = "";
        profile = result.people.values[index]
        if (profile.pictureUrl) {
            profHTML += "<p><a target="_blank" href="" + profile.publicProfileUrl + "">";
            profHTML += "<img class=img_border height=30 align="left" src="" + profile.pictureUrl + "">"; 
            profHTML += "" + profile.firstName + " " + profile.lastName + " - " +  profile.headline +  "</a>";  
        }
        $("#informationContainer").append(profHTML);
      }     
    }
   
   

 
   
  </script>
 </head>
 <body>
  
  <div id="container">
   <div id="feedList">
   </div>
   <div id="informationContainer">
	   <div id="mustLogin">
	     <h2>Please login to LinkedIn using the button.</h2>
	     <script type="IN/Login" data-onAuth="loginComplete"></script> 
	   </div>
   </div>   
  </div>
 </body>
</html>

CodePaLOUsa Coding Contest Part 2

19 March 2012

NOTE: The JSONP Web Service has since gone down.

In Part 1 we discussed the contest, what information you should be familiar with and that we would be improving the code that I submitted for entry. One of the things that through me for a loop is that LinkedIn requires you to have an API Key and for whoever is using your site to be logged in. While there may be a strong business case for it from a developer standpoint I ask myself "Why bother making an API Key if you are just going to make the user login in anyway?".

The first thing I changed was to have the list of speakers display on the left and if the user is not logged in to display the LinkedIn login to the right. Once the user logs into LinkedIn a default message replaces the login and login message.

I followed this up by cleaning up the code. Renaming a few functions to make more sense and to improve the formatting some. This code is what I should have submitted if my sleep deprived brain had been able to function:) Still not a winner but much better. View the results and see the changes made. In Part 3 we will attempt to improve the search for the speakers on LinkedIn by adding search keywords.

<span class="codeCaption prettyprint">index.html</span>



<html>
 <head>
  <style>
   #container {
     background-color: Gray;
    width: 100%;
    display: block;
    float: left;
   }
   #informationContainer {
    background-color: Gray;
    width: 70%;
    display: block;
    padding: 1em;
    float: right;
    
   }

   #feedList {
     background-color: Green;
     float: left;
     width: 25%;
     max-width: 25%;
     min-width: 25%;
    } 
    #lineItem {
     background-color: #BBBBBB;
     width: 90%;
     float: left;
     clear: both;
    } 

    #mustLogin {
      display: none;
    } 


  </style>
  <script type="text/javascript" src="jquery-1.7.1.js"></script>
  <script type="text/javascript" src="http://platform.linkedin.com/in.js">
      api_key: ###get your own!###
      authorize: true
      onLoad: onLinkedLoad
    </script>
  <script type="text/javascript">
   var lloaded = false
   
   function onLinkedLoad() {
     initiatePage();    
   }
   
   function loginComplete() {
   	 $("#mustLogin").hide();   	
   	 showLoggedInMessage();
   }


   function showLoggedInMessage() {
     $("#informationContainer").append("<div>Click the links to the left to display information about the speaker</div>");
   }
   
   function initiatePage() {
     lloaded = true;
     //alert("lloaded=" + lloaded);
     var jsonUrl="http://winaspectreapi.appspot.com/api/sessions";
     callDataAJAX(jsonUrl);
   }

   
   
   function listNames(data) {
     for(i=0;i < data.length; i++) {
       names = data[i].author.split(" ");
       var output = '<div id="lineItem">Speaker:  <a href="#'' + names[0] + ''" onclick="getLinkedInfo('' + names[0] + '','' + names[names.length - 1] + ''); return false;">' + data[i].author + '</a><br/>';
       output = output +  'Title:  ' + data[i].title + '<hr/></div>';
       $("#feedList").append(output);
     }
   }
   
   function receiveData(data, status) {
     if($.isArray(data)) {
       listNames(data);
     }
     if(IN.User.isAuthorized()) {
			 showLoggedInMessage();
		 } else {
		   $("#mustLogin").show();	
		 }
   }
   

   function callDataAJAX(jsonUrl) {
     $.ajax({
         url: jsonUrl,
         dataType: 'jsonp',
         jsonpCallback: 'receiveData'
     });
      
   }
   
   function getLinkedInfo(firstName, lastName) {
     IN.API.PeopleSearch().fields("firstName", "lastName", "distance", "publicProfileUrl","pictureUrl","headline").params({"first-name":firstName,"last-name":lastName,"sort": "distance"}).result(showResults);
   }

   function showResults(result) {
    $("#informationContainer").html('');
            $("#informationContainer").append("<span>Click a link to the left to list possible LinkedIn matches.  The one you want is most likely on top.</span>");
        for (var index in result.people.values) {
         var profHTML = "";
            profile = result.people.values[index]
            if (profile.pictureUrl) {
                profHTML += "<p><a target="_blank" href="" + profile.publicProfileUrl + "">";
                profHTML += "<img class=img_border height=30 align="left" src="" + profile.pictureUrl + "">"; 
                profHTML += "" + profile.firstName + " " + profile.lastName + " - " +  profile.headline +  "</a>";  
            }
            $("#informationContainer").append(profHTML);
        }     
   }
   
   

 
   
  </script>
 </head>
 <body>
  
  <div id="container">
   <div id="feedList">
   </div>
   <div id="informationContainer">
	   <div id="mustLogin">
	     <h2>Please login to LinkedIn using the button.</h2>
	     <script type="IN/Login" data-onAuth="loginComplete"></script> 
	   </div>
   </div>   
  </div>
 </body>
</html>

CodePaLOUsa Coding Contest Part 1

18 March 2012

Hewlett Packard sponsored a coding contest to win a very nice laptop! The goal was to consume was to consume two restful winaspectre web services. You can see some of the entries on Twitter using the #winaspectre hash. Congratulations to all the winners!

NOTE: The JSONP Web Service has since gone down.

My entry while submitted was not complete and I thought I would complete the project discussing where I went wrong. My goal was to list out the speakers creating hyperlinks on their name and lecture titles. When their name is clicked it would search for them on LinkedIn and when their lecture title was clicked it would pull back Google search results. I ran into several problems while writing my submitted effort. My two biggest problems where that I had never before used a JSONP web service before or the LinkedIn API. Between the two I wasted several hours trying to make a standard JSON web service call and trying to anonymously query LinkedIn. See the results.

My submission is shown below and our goal will be to go over the code discuss where I've gone wrong and how to achieve something better. The first change I would make is to list all the speakers and their lecture titles. Next I would search for the first speaker listed on LinkedIn and display the results. The third change is to provide the option of logging into LinkedIn. Logging in will give the user better and more detailed information. Once I have done this I will discuss the changes that I made in Part 2.

It would be beneficial for you to become familiar with the LinkedIn APIs and to make sure you are ready to get started. Do not forget to setup your API key! JQuery is the JavaScript API that I am using and is very easy to use if you have basic knowledge of Cascading Style Sheets (CSS).

In Part 2 we will cleanup the code, make the speaker list display by default and improve how the LinkedIn login is handled.

<span class="codeCaption prettyprint">index.html</span>



<html>
 <head>
  <style>
   #container {
     background-color: Gray;
    width: 100%;
    display: block;
    float: left;
   }
    #feedList {
     background-color: Green;
     float: left;
     width: 25%;
     max-width: 25%;
     min-width: 25%;
    } 
     #lineItem {
     background-color: #BBBBBB;
     width: 90%;
     float: left;
     clear: both;
    } 

  </style>
  <script type="text/javascript" src="jquery-1.7.1.js"></script>
  <script type="text/javascript" src="http://platform.linkedin.com/in.js">
      api_key: ###get your own!###
      authorize: true
      onLoad: onLinkedLoad
    </script>
  <script type="text/javascript">
   var lloaded = false
   
   function onLinkedLoad() {
    
     if(IN.User.isAuthorized()) {
      loadData();
     } else {
      hideData();
     }
   }
   
   function showData() {
    //alert("show");
        $("#container").css("display","block");
        $("#feedList").css("display","block");
        $("#lineItem").css("display","block");
        $("#mustLogin").hide();    
   }

   function hideData() {
    //alert("hide");
        $("#container").css("display","none");
        $("#feedList").css("display","none");
        $("#lineItem").css("display","none");
        $("#mustLogin").show();    
   }

   
   function loadData() {
     lloaded = true;
     //alert("lloaded=" + lloaded);
     var jsonUrl="http://winaspectreapi.appspot.com/api/sessions";
        showData();
        
        
        
        buildListAJAX(jsonUrl);
         
   }

      function getLinkedInfo(firstName, lastName) {
       IN.API.PeopleSearch().fields("firstName", "lastName", "distance", "publicProfileUrl","pictureUrl","headline").params({"first-name":firstName,"last-name":lastName,"sort": "distance"}).result(showResults);
      }

   function showResults(result) {
    $("#informationContainer").html('');
            $("#informationContainer").append("<span>Click a link to the left to list possible LinkedIn matches.  The one you want is most likely on top.</span>");
        for (var index in result.people.values) {
         var profHTML = "";
            profile = result.people.values[index]
            if (profile.pictureUrl) {
                profHTML += "<p><a target="_blank" href="" + profile.publicProfileUrl + "">";
                profHTML += "<img class=img_border height=30 align="left" src="" + profile.pictureUrl + "">"; 
                profHTML += "" + profile.firstName + " " + profile.lastName + " - " +  profile.headline +  "</a>";  
            }
            $("#informationContainer").append(profHTML);
        }     
   }
   
   
   function showUser(result) {
    alert(result);
   }
   
   
   $(document).ready(function(){
       // twitter api's base url
     var jsonUrl="http://winaspectreapi.appspot.com/api/sessions";
     //alert("jquery works");
     
    // alert(document.domain);
     
        
   });
   
   function listNames(data) {
       for(i=0;i < data.length; i++) {
        names = data[i].author.split(" ");
        var output = '<div id="lineItem">Speaker:  <a href="#'' + names[0] + ''" onclick="getLinkedInfo('' + names[0] + '','' + names[names.length - 1] + ''); return false;">' + data[i].author + '</a><br/>';
        output = output +  'Title:  ' + data[i].title + '<hr/></div>';
         $("#feedList").append(output);
       }
    
   }
   
   
   function alertResponse(data, status) {
        //alert("data: " + data + ", status: " + status);
         if($.isArray(data)) {
          listNames(data);
         }
      }
   
   //not being used because apparently JSON is not valid
   function buildListAJAX(jsonUrl) {
    // alert(jsonUrl);
     $.ajax({
         url: jsonUrl,
         dataType: 'jsonp',
         jsonpCallback: 'alertResponse'
     });
      
   }
   
   
   

 
   
  </script>
 </head>
 <body>
  <div id="mustLogin">
   <h2>You must login Facebook using the button below to use this CodePaLOUsa application.</h2>
    <script type="IN/Login" data-onAuth="loadData"></script> 
   </div>
  
  <div id="container">
   <div id="feedList">
              
   </div>
   <div id="informationContainer">
         Click a link to the left to list possible LinkedIn matches.  The one you want is most likely on top.    
   </div>   
  </div>
 </body>
</html>

CodePaLOUsa (Day Two)

17 March 2012

Today we started off with a key not speech by Billy Hollis. Essentially learn and remain flexible else you'll end up in tar pits with the rest of the dinosaurs. Mr Hollis of course said it better and in more depth:) He also had some nice points about software usability and design. Which tied into the point about dinosaurs in that he thinks an industry shift centered on user experience and design will kill off the careers of current industry professionals.

Mike Amundsen gave a lecture on Representational State Transfer (REST) which was well done. I now understand the origins and goals of REST. One of my points of confusion with REST has been how do RESTful web services differ significantly from SOAP Web Services. Fortunately Stackoverflow came to the rescue as it so often does:) Now whether or not the difference is significant would be an argument for another time.

While it was perhaps least relevant to me personally the best lecture of the day goes to Joshua Rosenthol's lecture on building a startup and having an exit plan. I was pretty impressed with his pointed lecture, his knowledge of the subject and his credentials. Mr. Rosenthal's covered many points but the most critical was to find a business need that you can solve. Preferably this should be done with analytics to maximize the return on yours and others investment. Technology is a means to an end not an end in itself. Good business may lead to success in spite of bad technology but good technology will not succeed in spite of bad business.

CodePaLOUsa (Day One)

16 March 2012

Spent the whole day learning Test Driven Development (TDD) with Dennis as my partner in a paired programmer setup. Heya Dennis! The vehicle we chose for learning was Cucumber. I have to admit I am loving Cucumber! Cucumber is setup so that you describe the story/requirement up front followed by what is essentially a use case that is backed up by code that actually executes. Now today I used it to perform testing on a class. Normally that would be handled by RSpec and Cucumber would be used for testing at the applicaton level. This according to our trainers Guy Royse and George Walters. Anything that I attribute to them that isn't correct is probably my fault:)

Now we did several scenarios during the TDD session with Guy and Walter, but I though I would just show you one of my favorites. This demonstrates feeding data into template and then checking to verify the methods exist dynamically.

<span class="codeCaption prettyprint">evercraft/features/evercraft_create_character.feature</span>


Feature: evercraft creates character

  As a player
  I want to create a character
  So that I can customize it

  Scenario Outline:  character has attributes
    Given I have a character
    Then I see the character has <attribute>
    Examples:
      |attribute   |
      |strength    |
      |intelligence|
      |dexterity   |
      |constitution|
      |charisma    |
      |wisdom      |
<span class="codeCaption prettyprint">evercraft/features/step_definitions/evercraft_steps.rb</span>


  Given /^I have a character$/ do
    @character = EverCraft::Character.new
  end

  Then /^I see the character has (w*)$/ do |attribute|
    @character.respond_to?(attribute).should == true
  end
<span class="codeCaption prettyprint">evercraft/lib/EverCraft/character.rb</span>


module EverCraft
  class Character
    attr_accessor :name, :alignment, :armor_class, :hit_points, :strength, :dexterity, :constitution, :intelligence, :wisdom, :charisma

    def initialize
      self.armor_class=10
      self.hit_points=5
      self.charisma=10
      self.constitution=10
      self.wisdom=10
      self.dexterity=10
      self.strength=10
      self.intelligence=10
    end
  end
end
<span class="terminalCaption">Results of running "cucumber features" in the evercraft directory</span>


Feature: evercraft creates character
  
  As a player
  I want to create a character
  So that I can customize it

  Scenario Outline: character has attributes # features/evercraft_create_character.feature:7
    Given I have a character                 # features/step_definitions/evercraft_steps.rb:1
    Then I see the character has <attribute> # features/step_definitions/evercraft_steps.rb:5

    Examples: 
      | attribute    |
      | strength     |
      | intelligence |
      | dexterity    |
      | constitution |
      | charisma     |
      | wisdom       |

6 scenarios (6 passed)
12 steps (12 passed)
0m0.014s

CodePaLOUsa (The night before)

15 March 2012

CodePaLOUsa begins tomorrow! I will be attending the Test Driven Development workshop. Last night I installed Fedora 16 using VirtualBox and setup Ruby, RSpec and Cucumber. Tonight I have been reading The RSpec Book so that I will be familiar with it as a testing framework. Tomorrows workshop is supposed to be language agnostic and I have chosen to use Ruby. Strangely The RSpec Book has mostly been about cucumber so far:) The book is also focused on Business Driven Development and I look forward to seeing what contrasts between BDD and TDD become apparent. Well back to reading and coding!

Ruby on Rails Authentication and Authorization Part 3

28 February 2012

In Part 2 of this article we installed Devise and configured it so that we will be able to customize it. In Part 3 we will add the functionality for hierarchical roles.

Our first step will be to generate the roles and the role_roles tables we defined in Part 1. This can be done using the "rails generate" command as illustrated below.

Terminal window in the mysecurity directory


bash-4.2$ rails generate scaffold role description:string
      invoke  active_record
      create    db/migrate/20120224180650_create_roles.rb
      create    app/models/role.rb
      invoke    test_unit
      create      test/unit/role_test.rb
      create      test/fixtures/roles.yml
       route  resources :roles
      invoke  scaffold_controller
      create    app/controllers/roles_controller.rb
      invoke    erb
      create      app/views/roles
      create      app/views/roles/index.html.erb
      create      app/views/roles/edit.html.erb
      create      app/views/roles/show.html.erb
      create      app/views/roles/new.html.erb
      create      app/views/roles/_form.html.erb
      invoke    test_unit
      create      test/functional/roles_controller_test.rb
      invoke    helper
      create      app/helpers/roles_helper.rb
      invoke      test_unit
      create        test/unit/helpers/roles_helper_test.rb
      invoke  assets
      invoke    coffee
      create      app/assets/javascripts/roles.js.coffee
      invoke    scss
      create      app/assets/stylesheets/roles.css.scss
      invoke  scss
      create    app/assets/stylesheets/scaffolds.css.scss
bash-4.2$ 
bash-4.2$ rails generate model role_role role_id:integer parent_id:integer
      invoke  active_record
      create    db/migrate/20120224181028_create_role_roles.rb
      create    app/models/role_role.rb
      invoke    test_unit
      create      test/unit/role_role_test.rb
      create      test/fixtures/role_roles.yml
bash-4.2$

I chose the "rails generate scaffold" command for the roles table because we will need a user interface to enter and edit the roles and this command builds the model, view and controller. The role_roles table will not need this so I used the "rails generate model" command to just build the model. Now I will use the "rake db:migrate" command to actually build the tables in the database.

Terminal window in the mysecurity directory


bash-4.2$ rake db:migrate
==  CreateRoles: migrating ====================================================
-- create_table(:roles)
   -> 0.0009s
==  CreateRoles: migrated (0.0009s) ===========================================

==  CreateRoleRoles: migrating ================================================
-- create_table(:role_roles)
   -> 0.0009s
==  CreateRoleRoles: migrated (0.0010s) =======================================

bash-4.2$

Now using the SQLite Manager we can look at the tables and we can see that the created_at and updated_at and primary key columns were automatically generated for us as illustrated below.

Roles table in database
Roles table in database

We should now run the "rails server" command and go to the URL http://localhost:3000/roles and verify that the scaffold for roles is working. You should see something similar to the screen capture below.

Roles list page
Roles list page

Press Ctrl-c to exit out of the rails server running in the terminal. Now that we have verified that it is working let us begin our customization. If you recall one of the requirements from Part 1 is that we would have the ability to assign roles to other roles and this is the first part we will build. The first step is to customize the roles and role_roles models to define the relationships between the tables.

Each role will have the capability of having both children and parents. For Example Role A is assigned to Role B which in turn is assigned to Role C. Role B would have Role A as a child and Role C as a Parent. Now if we assign Role D to Role B then Role B will have both Role A and Role D as children. Furthermore if we assign Role B to Role E then Role B will have both Role C and Role E as parents. To allow this is the purpose of the role_roles table. Using the "has_many" method inside the models we will define the relationships. Below is the original role.rb model found in mysecurity/app/models directory followed by the modified version

mysecurity/app/models/role.rb


class Role < ActiveRecord::Base
end
mysecurity/app/models/role.rb


class Role < ActiveRecord::Base
  has_many :role_children, :foreign_key => 'parent_id', :class_name => 'RoleRole'
  has_many :children, :through => :role_children
  
  has_many :role_parents, :foreign_key => 'role_id', :class_name => 'RoleRole'
  has_many :parents, :through => :role_parents
end

This is the most confusing part in building this application and you may want to view outside resources to gain a better understanding. What we have done here is to first define a relationship to the RoleRole class and specify the foreign key that defines the relationship. Thus the parent_id column in role_roles points to the parent and if something is pointing to a parent it is a child. This is defined by the line "has_many :role_children, :foreign_key => 'parent_id', :class_name => 'RoleRole'". The next part says that a Role can have many Roles as children through RoleRole as shown by the line "has_many :children, :through => :role_children".

To recap we said that Role has many RoleRoles as linked through the parent_id in RoleRole. We call this relationship "role_children". Next we said that through "role_children" a Role can have many Roles and we will call this relationship "children". Clear as mud? Good;)

The parent relationships are defined by the same process but in reverse. We say a Role can have many RoleRoles as linked by the role_id in RoleRole. We called this relationship "role_parents". We then say that Role can have many relationships with Roles as defined through the "role_parents" relationship which we call "parents". Through Ruby on Rails goodness ActiveRecord will build the parents and children collections onto the Role object for us. But wait! We let the Role model know that it has a relationship with RoleRole and with itself but we haven't told RoleRole that it has a relationship with Role. Below is the original RoleRole model followed by the modified model.

mysecurity/app/models/role_role.rb


class RoleRole < ActiveRecord::Base
end
mysecurity/app/models/role_role.rb


class RoleRole < ActiveRecord::Base
  belongs_to :parent, :foreign_key => 'parent_id', :class_name => 'Role'
  belongs_to :child, :foreign_key => 'role_id', :class_name => 'Role'  
end

Here we define both a parent and child relationship from RoleRole to Role. Thankfully this one is much easier to understand. RoleRole belongs to Role through the parent_id in RoleRole and the relationship is called "parent". Additionally RoleRole belongs to Role through the role_id in RoleRole and this one is called "child". Combined with the has_many relationships defined in the Role object are the relationships now fully established.

We have defined the relationships between our role tables and now we must be able to display, update and assign roles to roles. The default views defined using the "rails generate scaffold" command are not up to this task and must be modified. Roles can have both parents and children and we will need to display this information. My suggestion is that for the listing of the roles that we list all roles in the system and display them in a hierarchical fashion which will make the parent/child relationships obvious. When a role is being edited all the roles will be hierarchically displayed under a Parents and Children section. On to listing Roles!

The algorithm that I chose to use is to list all the roles that do not have parents and then to list the children. The code to implement this I will place in the Role helper class located "mysecurity/app/helpers/roles_helper.rb".

mysecurity/app/helpers/roles_helper.rb


module RolesHelper

  def build_role_list(partialFile='')
    list_items = ""
    roleList = Role.find_by_sql("SELECT * FROM roles WHERE id NOT IN (SELECT role_id FROM role_roles)")
    for role in roleList
      list_items += build_role_list_item(role ,partialFile)
    end
    output = list_items
    return output.html_safe
  end

  def build_role_list_item(local_role,partialFile)
    local_children=""
    if local_role.children.length > 0
      child_output = ""
      for child in local_role.children
        child_output += build_role_list_item(child,partialFile)
      end
      local_children += render :partial => '/roles/ul', :locals => { :list_items => child_output.html_safe }
    end
    output = render( :partial => partialFile, :locals => {:the_children => local_children.html_safe,:current_role => local_role})
    return output.html_safe
  end

end

Next I edited the "mysecurity/app/views/roles/index.html.erb" and changed it to the following

mysecurity/app/views/roles/index.html.erb


<h1>Listing roles</h1>

<%= link_to 'New Role', new_role_path %>
<br />
<ul>
  <li class="listNoDecorate">
    <span class="roleDescription">Role Name</span>
    <span class="roleCommands">[Commands]</span>
  </li>

  <%=  build_role_list('indexrow') %>
</ul>

I then edited the "mysecurity/app/views/roles/_form.html.erb" to the following

mysecurity/app/views/roles/_form.html.erb


<%= form_for(@role) do |f| %>
  <% if @role.errors.any? %>
    <div id="error_explanation">
      <h2><%= pluralize(@role.errors.count, "error") %> prohibited this role from being saved:</h2>

      <ul>
      <% @role.errors.full_messages.each do |msg| %>
        <li><%= msg %></li>
      <% end %>
      </ul>
    </div>
  <% end %>

  <div class="field">
    <%= f.label :description %><br />
    <%= f.text_field :description %>
  </div>
  <div class="field">
    <%= f.label 'Parents' %><br />
    <%=  build_role_list('parents_checkbox') %>
  </div>
  <div class="field">
    <%= f.label 'Children' %><br />
    <%=  build_role_list('children_checkbox') %>
  </div>
  <div class="actions">
    <%= f.submit %>
  </div>
<% end %>

I then created three new files _indexrow.html.erb, _parents_checkbox.html.erb and _children_checkbox.html.erb. These are located in the "mysecurity/app/views/roles" directory. The files are called from inside the helper methods build_role_list and build_role_list_item. The underscore in the beginning of the file name indicates that they are partials. Their contents are displayed below.

mysecurity/app/views/roles/_indexrow.html.erb


  <li>
    <span class="roleDescription"><%= current_role.description %></span>
    <span class="roleCommands">[<%= link_to 'Show', current_role %> -
    <%= link_to 'Edit', edit_role_path(current_role) %> -
    <%= link_to 'Destroy', current_role, confirm: 'Are you sure?', method: :delete %>]
    </span>
  </li>
  <%= the_children %>
mysecurity/app/views/roles/_parents_checkbox.html.erb


<li><%= check_box_tag "role[parent_ids][]", current_role.id, @role.parents.include?(current_role), :disabled => current_role.eql?(@role) %><%= current_role.description %></li><%= the_children %>

A tricky bit that I ran into with the checkbox tags has to do with the name inside the brackets. Handling multiple values with checkboxes is described very well in the HABTM Checkboxes on Railscasts.com. In the _parents_checkbox.html.erb file i placed the code "role[parent_ids][]" which works. However when I placed the code "role[role_ids][]" it didn't work and threw an error. I was confused by this because I thought that "parent_ids" referred to the foreign key "parent_id" in the role_roles table and "role_id" would then be the other foreign key. This is not the case however. "parent_ids" is the singular of the relationship "parents" defined in the Role class "has_many :parents, :through => :role_parents". The child relationship is defined as "has_many :children, :through => :role_children" and thus for the list of children "role[child_ids][]" defines the relationship for saving in the form. Which saves quite a bit of coding once you get the hang of it.

mysecurity/app/views/roles/_children_checkbox.html.erb


<li><%= check_box_tag "role[child_ids][]", current_role.id, @role.children.include?(current_role), :disabled => current_role.eql?(@role) %><%= current_role.description %></li><%= the_children %>

Now if we have put everything together correctly we should see screens similar to the below when we go to http://localhost:3000/roles.

Roles Listing Page
Roles Listing Page

Roles Edit Page
Roles Edit Page

We have covered quite a bit of ground in Part 3. In Part 4 we will integrate the Roles with the Users that was created in Part 2 when we configured Devise.

Ruby on Rails Authentication and Authorization Part 2

17 February 2012

In Part 1 of this article we discussed what authentication and authorization means and what we want our security to do for us. Now it is time to configure Devise so that we can begin to customize it.

First lets create our Rails application "mysecurity" by running the command "rails new mysecurity".

Terminal window in a directory of your choice



bash-4.2$ rails new mysecurity
      create  
      create  README
      create  Rakefile
      create  config.ru
      create  .gitignore
      create  Gemfile
      create  app
      create  app/assets/images/rails.png
      create  app/assets/javascripts/application.js
      create  app/assets/stylesheets/application.css
      create  app/controllers/application_controller.rb
      create  app/helpers/application_helper.rb
      create  app/mailers
      create  app/models
      create  app/views/layouts/application.html.erb
      create  app/mailers/.gitkeep
      create  app/models/.gitkeep
      create  config
      create  config/routes.rb
      create  config/application.rb
      create  config/environment.rb
      create  config/environments
      create  config/environments/development.rb
      create  config/environments/production.rb
      create  config/environments/test.rb
      create  config/initializers
      create  config/initializers/backtrace_silencers.rb
      create  config/initializers/inflections.rb
      create  config/initializers/mime_types.rb
      create  config/initializers/secret_token.rb
      create  config/initializers/session_store.rb
      create  config/initializers/wrap_parameters.rb
      create  config/locales
      create  config/locales/en.yml
      create  config/boot.rb
      create  config/database.yml
      create  db
      create  db/seeds.rb
      create  doc
      create  doc/README_FOR_APP
      create  lib
      create  lib/tasks
      create  lib/tasks/.gitkeep
      create  lib/assets
      create  lib/assets/.gitkeep
      create  log
      create  log/.gitkeep
      create  public
      create  public/404.html
      create  public/422.html
      create  public/500.html
      create  public/favicon.ico
      create  public/index.html
      create  public/robots.txt
      create  script
      create  script/rails
      create  test/fixtures
      create  test/fixtures/.gitkeep
      create  test/functional
      create  test/functional/.gitkeep
      create  test/integration
      create  test/integration/.gitkeep
      create  test/unit
      create  test/unit/.gitkeep
      create  test/performance/browsing_test.rb
      create  test/test_helper.rb
      create  tmp/cache
      create  tmp/cache/assets
      create  vendor/assets/stylesheets
      create  vendor/assets/stylesheets/.gitkeep
      create  vendor/plugins
      create  vendor/plugins/.gitkeep
         run  bundle install
Fetching source index for http://rubygems.org/
Using rake (0.9.2.2) 
Using multi_json (1.0.4) 
Using activesupport (3.1.3) 
Using builder (3.0.0) 
Using i18n (0.6.0) 
Using activemodel (3.1.3) 
Using erubis (2.7.0) 
Using rack (1.3.6) 
Using rack-cache (1.1) 
Using rack-mount (0.8.3) 
Using rack-test (0.6.1) 
Using hike (1.2.1) 
Using tilt (1.3.3) 
Using sprockets (2.0.3) 
Using actionpack (3.1.3) 
Using mime-types (1.17.2) 
Using polyglot (0.3.3) 
Using treetop (1.4.10) 
Using mail (2.3.0) 
Using actionmailer (3.1.3) 
Using arel (2.2.1) 
Using tzinfo (0.3.31) 
Using activerecord (3.1.3) 
Using activeresource (3.1.3) 
Using ansi (1.4.1) 
Using bundler (1.0.21) 
Using coffee-script-source (1.2.0) 
Installing execjs (1.3.0) 
Using coffee-script (2.2.0) 
Using rack-ssl (1.3.2) 
Installing json (1.6.5) with native extensions 
Using rdoc (3.12) 
Using thor (0.14.6) 
Using railties (3.1.3) 
Using coffee-rails (3.1.1) 
Using jquery-rails (1.0.19) 
Using rails (3.1.3) 
Using sass (3.1.12) 
Using sass-rails (3.1.5) 
Using sqlite3 (1.3.5) 
Using turn (0.8.3) 
Installing uglifier (1.2.2) 
Your bundle is complete! Use `bundle show [gemname]` to see where a bundled gem is installed.

Our RoR application framework has now been created in the directory in which you ran the command. Change into the newly created "mysecurity" directory and edit the file "Gemfile". We are going to add the line gem 'devise' to the "Gemfile" file as shown below.

Gemfile in the mysecurity directory


gem 'sqlite3'

gem 'devise'

The next step is to install devise using the command rails generate devise:install which produces the result.

Terminal window in mysecurity directory


bash-4.2$ rails generate devise:install

[DEVISE] Devise.case_insensitive_keys is false which is no longer supported. If you want to continue running on this mode, please ensure you are not using validatable (you can copy the validations directly to your model) and set case_insensitive_keys to an empty array.


[DEVISE] Devise.use_salt_as_remember_token is false which is no longer supported. Devise now only uses the salt as remember token and the remember_token column can be removed from your models.


[DEVISE] Devise.reset_password_within is nil. Please set this value to an interval (for example, 6.hours) and add a reset_password_sent_at field to your Devise models (if they don't have one already).

      create  config/initializers/devise.rb
      create  config/locales/devise.en.yml

===============================================================================

Some setup you must do manually if you haven't yet:

  1. Setup default url options for your specific environment. Here is an
     example of development environment:

       config.action_mailer.default_url_options = { :host => 'localhost:3000' }

     This is a required Rails configuration. In production it must be the
     actual host of your application

  2. Ensure you have defined root_url to *something* in your config/routes.rb.
     For example:

       root :to => "home#index"

  3. Ensure you have flash messages in app/views/layouts/application.html.erb.
     For example:

<%= notice %>

<%= alert %>

4. If you are deploying Rails 3.1 on Heroku, you may want to set: config.assets.initialize_on_precompile = false On config/application.rb forcing your application to not access the DB or load models when precompiling your assets. ===============================================================================

Following the directions of the output from the command change to the "mysecurity/config/environments" directory and add.

mysecurity/config/environments/development.rb


config.action_mailer.default_url_options = { :host => 'localhost:3000' }

to the development.rb file. Change to the "mysecurity/config" directory and add the following line to the routes.rb file.

mysecurity/config/routes.rb


root :to => "home#index"

Next we need to run the "rails generate devise user" followed by the "rake db:migrate" commands to build the database tables for Devise.

Terminal window in mysecurity directory


bash-4.2$ rails generate devise user
      invoke  active_record
      create    db/migrate/20120131140922_devise_create_users.rb
      create    app/models/user.rb
      invoke    test_unit
      create      test/unit/user_test.rb
      create      test/fixtures/users.yml
      insert    app/models/user.rb
       route  devise_for :users

bash-4.2$ rake db:migrate
==  DeviseCreateUsers: migrating ==============================================
-- create_table(:users)
   -> 0.0684s
-- add_index(:users, :email, {:unique=>true})
   -> 0.0384s
-- add_index(:users, :reset_password_token, {:unique=>true})
   -> 0.0005s
==  DeviseCreateUsers: migrated (0.1076s) =====================================

If we now run the "rails server" and go to the URL "http://localhost:3000/user/sign_in" we should see the results as shown below.

Terminal window in mysecurity directory


bash-4.2$ rails server
=> Booting WEBrick
=> Rails 3.1.3 application starting in development on http://0.0.0.0:3000
=> Call with -d to detach
=> Ctrl-C to shutdown server
[2012-02-17 11:35:43] INFO  WEBrick 1.3.1
[2012-02-17 11:35:43] INFO  ruby 1.9.3 (2011-10-30) [i686-linux]
[2012-02-17 11:35:43] INFO  WEBrick::HTTPServer#start: pid=5533 port=3000

Devise Sign In Screen
Devise Sign In Screen

Using the Firefox add-on SQLite Manager we can also view the SQLite database development.sqlite3 located in directory mysecurity/db/. This will look similar to the below and is how I knew what fields to use in my database design in Part 1. This is illustrated in the screenshot below.

Devise user table
Devise user table

Lets press the keys "Ctrl-C" and shutdown the application server. Next we will generate view files that will allow us to customize the user interface. Go to the mysecurity folder and run the command "rails generate devise:views". Which should deliver results similar to the following.

Terminal window in mysecurity directory


bash-4.2$ rails generate devise:views
      create  app/views/devise/_links.erb
      invoke  form_for
      create    app/views/devise/confirmations
      create    app/views/devise/confirmations/new.html.erb
      create    app/views/devise/passwords
      create    app/views/devise/passwords/edit.html.erb
      create    app/views/devise/passwords/new.html.erb
      create    app/views/devise/registrations
      create    app/views/devise/registrations/edit.html.erb
      create    app/views/devise/registrations/new.html.erb
      create    app/views/devise/sessions
      create    app/views/devise/sessions/new.html.erb
      create    app/views/devise/unlocks
      create    app/views/devise/unlocks/new.html.erb
      invoke  erb
      create    app/views/devise/mailer
      create    app/views/devise/mailer/confirmation_instructions.html.erb
      create    app/views/devise/mailer/reset_password_instructions.html.erb
      create    app/views/devise/mailer/unlock_instructions.html.erb
bash-4.2$

We have now installed and configured Devise preparing it to be customized. In Part 3 of the article we are going to modify and add files necessary to handle our hierarchical roles.

Ruby on Rails Authentication and Authorization Part 1

01 February 2012

One of the strengths and weaknesses of Ruby on Rails (RoR) is that it requires you to setup your own authentication and authorization systems. Which I will refer to as security going forward. This makes sense seeing as RoR is a development framework rather than being a full blown content management system like Drupal. The weakness is that it takes longer to get a basic web application put together and the strength is that it gives you much greater control of your applications functionality. Working with RoR 3.1 on a Linux box I will construct a security framework. This article will require basic knowledge of Linux and to already have Ruby installed on your system.

The requirements for security is that we want to know who is using our application and what they are allowed to access. In technical terms knowing who is requesting access is referred to as authentication. This is usually handled by a login screen. When I login to my email account authentication tells the email provider that Chris is accessing his email. Now that we know who we need to know what. What pages or resources are we going to allow our user to access. This is the portion known as authorization. After logging into my email account I try to read my email and the email provider checks to see if I am authorized to read my own email. Of course I will be able to read my own email. If however I attempt to read the lovely Joann's email I will not be authorized to do so.

What I want in a security system is to be able to create roles and users, assign roles to user, assign roles to roles and assign roles to resources through a web interface. Straight out of the gate I think this is quite ambitious so to keep things more manageable I will only create the first three requirements and leave out being able to assign roles to resources through the interface.

You have several options when it comes to building an security for your web application. The path I chose is to use Devise for authentication and declarative_authorization for authorization. Devise lets us know who is using our application by forcing the user to provide a username and password in order to get to the good stuff. Declarative_authorization tells us what resources (i.e. webpages) the user is allowed to access. Using knowledge of the tables created by Devise and the functionality I am looking for I created the database table design as illustrated below.

Security Model
Security Model

Now that we have a rough design lets install our two Ruby Gems; Devise and declarative_authorization. There are some helpful videos on Railscasts.com. Let us install them on our system by running "gem install declarative_authorization" and "gem install devise" commands in a terminal window as shown below.

Terminal window in mysecurity directory

bash-4.2$ gem install declarative_authorization
Successfully installed declarative_authorization-0.5.5
1 gem installed
Installing ri documentation for declarative_authorization-0.5.5...
Installing RDoc documentation for declarative_authorization-0.5.5...
bash-4.2$ gem install devise
Fetching: devise-2.0.0.gem (100%)
Fetching: activesupport-3.2.1.gem (100%)
Fetching: activemodel-3.2.1.gem (100%)
Fetching: rack-1.4.1.gem (100%)
Fetching: journey-1.0.1.gem (100%)
Fetching: sprockets-2.1.2.gem (100%)
Fetching: actionpack-3.2.1.gem (100%)
Successfully installed devise-2.0.0
Successfully installed activesupport-3.2.1
Successfully installed activemodel-3.2.1
Successfully installed rack-1.4.1
Successfully installed journey-1.0.1
Successfully installed sprockets-2.1.2
Successfully installed actionpack-3.2.1
7 gems installed
Installing ri documentation for devise-2.0.0...
Installing ri documentation for activesupport-3.2.1...
Installing ri documentation for activemodel-3.2.1...
Installing ri documentation for rack-1.4.1...
Installing ri documentation for journey-1.0.1...
Installing ri documentation for sprockets-2.1.2...
Installing ri documentation for actionpack-3.2.1...
Installing RDoc documentation for devise-2.0.0...
Installing RDoc documentation for activesupport-3.2.1...
Installing RDoc documentation for activemodel-3.2.1...
Installing RDoc documentation for rack-1.4.1...
Installing RDoc documentation for journey-1.0.1...
Installing RDoc documentation for sprockets-2.1.2...
Installing RDoc documentation for actionpack-3.2.1...
bash-4.2$

Now that we have the two plugins installed we can begin to customize them to our needs. The next step will be to setup Devise to be customizeable and we will walk through this in Part 2 of this article.

Setting up TortoiseCVS SSH with Putty

28 May 2010

Do this so you don't keep having to type in a password.



1)  Install TortoiseCVS
2)  Download Putty, Plink and Pageant and install into TortoiseCVS Directory.
3)  Create Shortcuts to Putty and Plink on the desktop.
4)  Create Putty session for the website.  
4.1)  Enter address under Session -> Host Name
4.2)  Enter login name under Connection -> Data -> Auto-login name
4.3)  Browse and select Private ssh key (*.ppk) Connection -> SSH -> Auth -> Private Key for Authentication.
4.4)  Click the Session -> Save button.

CSS Expressions

28 August 2009

Expressions allow javascript to be placed in the style sheet. Internet Explorer only though.

Example:



.internetexplorercontent {
  position: absolute;
  top: expression((offsetParent.scrollTop + 10) + 'px');
}

Accurate

13 September 2002

Main Entry: ac�cu�rate
Pronunciation: 'a-ky&-r&t, 'a-k(&-)r&t
Function: adjective
Etymology: Latin accuratus, from past participle of accurare to take care of, from ad- + cura care
Date: 1596
1 : free from error especially as the result of care <an accurate diagnosis>
2 : conforming exactly to truth or to a standard : EXACT <providing accurate color>
3 : able to give an accurate result <an accurate gauge>
Courtesy of Merriam-Webster

Improving ASP performance using Option Explicit

13 September 2002

You can enhance your websites performance by using "option explicit" at the beggining of your ASP(VBScript) scripts. When we use Option explicit it forces us to dimension all our variables. It wil throw an error if it finds a variable that has not been declared (dimensioned). Dimensioning your variables causes them to be referenced by an ordinal number. Variables which are not dimensioned are referenced by their name. Referencing variables by ordinals is 200%-300% faster than referencing them by name. I determined these numbers by comparing the execution times of the two scripts below.

If you would like to reproduce the experiment the process is very straight forward. Place each script in a seperate ASP page(file). Place the asp pages on your web server. Load the web pages in your browser alternating between the pages. I prefer alternating between the pages because it reduces the chance that outside factors cause one page to execute more slowly than the other. This experiment is accurate , but not very precise . Have a pencil and paper ready (or your favorite editor) to record the length of time it takes each script to execute. Execute the scripts five times each (a total of ten times alternating) and compare your results.

Using Option Explicit

<%@ Language=VBScript %>

<%
OPTION EXPLICIT Dim DimI, DimVariable response.write now() response.write "
" FOR DimI = 0 to 9000000 DimVariable = DimI NEXT response.write now() response.write "
"
Without Option Explicit

%>
<%
@ Language=VBScript %>
<%
response.write now() response.write "
" FOR noDimI = 0 to 9000000 noDimVariable = noDimI NEXT response.write now() response.write "
" %>

Ordinal Number

13 September 2002

Main Entry: ordinal number
Function: noun
Date: 1607
1 : a number designating the place (as first, second, or third) occupied by an item in an ordered sequence -- see NUMBER table
2 : a number assigned to an ordered set that designates both the order of its elements and its cardinal number
Courtesy of Merriam-Webster

Precise

13 September 2002

Main Entry: pre�cise
Pronunciation: pri-'sIs
Function: adjective
Etymology: Middle English, from Middle French precis, from Latin praecisus, past participle of praecidere to cut off, from prae- + caedere to cut
Date: 15th century
1 : exactly or sharply defined or stated
2 : minutely exact
3 : strictly conforming to a pattern, standard, or convention
4 : distinguished from every other <at just that precise moment>
Courtesy of Merriam-Webster

Precision

13 September 2002

Main Entry: 1pre�ci�sion
Pronunciation: pri-'si-zh&n
Function: noun
Date: 1740
1 : the quality or state of being precise : EXACTNESS
2a : the degree of refinement with which an operation is performed or a measurement stated -- compare ACCURACY
2b : the accuracy (as in binary or decimal places) with which a number can be represented usually expressed in terms of the number of computer words available for representation <double precision arithmetic permits the representation of an expression by two computer words>
Courtesy of Merriam-Webster


Older posts are available in the archive.