Pioneering Software

Import CSV files in Rails 3

Tue, 13 Jul 2010 07:52:29 -0700

CSV is a ubiquitous importing and exporting format for tables of information conforming to row-column layout. Lines correspond to rows. On each line, commas separate values under each column; hence Comma-Separated Values. Values between commas define table-cell contents, strings or numbers. The format is relatively flexible, relatively easy for machines and even humans to read and write.

In terms of user stories, it answers the following requirement.

As a: database maintainer

I want to: import information from external files, particularly Comma-Separated Value files where rows appear on each line and columns within each row have comma delimiters

So that I can: select columns (and rows) from the CSV files and merge these to create other new pieces of information.

Question is, How do you import CSV files in Rails 3. This article attempts an answer, or at least part of an answer, enough perhaps to point you in the right direction. You can find the sources here at GitHub.

Prerequisites

Rails 3
FasterCSV gem (Ruby parlance for an installable package)
JQuery

Why?

That is an important question. Has this sort of thing not been done before, many times? Well, yes. This is nothing new. But it does offer a fresh look at the subject, especially in the light of the upcoming new version of Rails and with preference for jQuery over Prototype for Rails’ JavaScript library. If you like, consider this a scenic voyage into Rails 3 and jQuery. The seas are fairly calm even though only at Beta.

Check your versions

Entering rails -v on the command line reports,

Rails 3.0.0.beta4

At the time of writing this version is the latest prerelease. Install it using sudo gem install rails --pre; option pre allows installation of prerelease versions, i.e. betas.

Doing similarly for RubyGems using gem -v gives,

1.3.7

Test-driven approach

Begin with a new Rails application.

The command to create a new application has changed since Rails 2. The Rails project now brings together the various disparate scripts and generators under one umbrella, so to speak. New applications now appear when you ask,

rails new APP_PATH

where APP_PATH specifies where your Rails application tree will reside on the local file system. The exact name does not actually matter too much. Although the name does become part of the application proper: it names the application module, and appears in the cookie store key; but you can change these later if you wish.

I will give it a long name. The following command creates a new folder called import-csv-files-in-rails-3. Rails fills it with basic structure and content, enough to get you started.

rails new import-csv-files-in-rails-3

The application is ready to run already. It does not do anything yet, of course. However, you can launch the server and access the application at localhost:3000. Note, syntax for launching a local server has also changed in Rails 3. You no longer enter script/server; it is now in the slightly-less wordy form,

rails s

s for server, naturally.

Test bed

As a simple starting point, imagine a Rails application comprising people and places. People have a first and last name; places have an address. Let the application’s database store these two entities, along with these attributes. Person entity with first and last name attributes, both strings. Place entity with address attribute, a simple string for now.

Generating the basic Rails scaffolding is very easy. Just two commands gives us the entities and their properties, together with corresponding controllers and views to access them via HTML and RESTful XML. g is short for generate in the following two commands.

rails g scaffold person first_name:string last_name:string
rails g scaffold place address:string

Migrate the database using rake db:migrate to update the database schema. By default Rails will use SQLite. Good enough for this exercise. You can then launch a local server to access people at localhost:3000/people and places at localhost:3000/places.

Once set up, the goal will become to import people and place information using CSV files. This is the real challenge.

Test import

One more thing. You may not have a list of people and places handy. But a CSV file or two will definitely be very useful for testing. So just for testing purposes, let us write a script to generate a file.

See below. Copy this and run it to generate some CSV files comprised of random words using Dan Croak’s Webster gem, a package for randomly generating short non-offensive words. You will need to install the gem using sudo gem install webster. Do the same for fastercsv if you haven’t already.

#!/usr/bin/env ruby

require 'optparse'
require 'ostruct'

options = OpenStruct.new
options.rows = 10
options.columns = 10
OptionParser.new do |opts|
  opts.on('-r', '--rows [INTEGER]', 'Number of rows', Integer) do |x|
    options.rows = x
  end
  opts.on('-c', '--columns [INTEGER]', 'Number of columns', Integer) do |x|
    options.columns = x
  end
end.parse!

require 'rubygems'
require 'fastercsv'
require 'webster'

webster = Webster.new

ARGV << '/dev/stdout' if ARGV.empty?
ARGV.each do |file_name|
  FasterCSV.open(file_name, 'w') do |csv|
    options.rows.times do |row_index|
      row = []
      options.columns.times do |column_index|
        row << webster.random_word
      end
      csv << row
    end
  end
end

You will find this script here as a Gist. Download it, make it executable and run using,

./gen-webster-csv.rb test.csv

Two-stage process: upload and merge

For simplicity, the application design will take a two-stage approach to importing.

Stage 1: upload
Stage 2: merge

Here, upload refers to the action of receiving a raw CSV file from a browser and storing it somewhere within the application’s database or otherwise readily-accessible place. Merge refers to the action of moving selected columns to the database proper. In a real application, you might choose to fold both stages into one action. But for this exercise, we make them distinct. The first stage takes a CSV file and stores it. The second stage lets the user pick out one or more columns and choose where to move the data: to people or places within the database. This second stage does have an advantage: it allows the user to see the imported information and select and deselect columns. Only selected columns will merge and become useful to the app.

Uploading, stage 1

First upload the CSV file, then store it.

Uploading files

Uploading a file is straightforward. Just add a form with a ‘file field.’ When submitted, the form will send a POST request with the file contents attached.

Create a CSV controller with an import action.

$ rails g controller csv import
      create  app/controllers/csv_controller.rb
       route  get "csv/import"
      invoke  erb
      create    app/views/csv
      create    app/views/csv/import.html.erb
      invoke  test_unit
      create    test/functional/csv_controller_test.rb
      invoke  helper
      create    app/helpers/csv_helper.rb
      invoke    test_unit
      create      test/unit/helpers/csv_helper_test.rb

Notice, Rails creates a default controller, a GET-request route for the action, an ERB-based view for the action along with test and helper stubs. Hence, when an external browser sends the application a GET request at csv/import, Rails will match the route, find the ERB template, render the HTML response and reply. The ‘view’ only needs to incorporate a standard HTML form which the browser will promptly display.

Navigate to the import view, app/views/csv/import.html.erb and add the HTML form, as follows.

<%= form_for :upload, :html => { :multipart => true } do |f| -%>
  <%= f.file_field :csv %>
  <%= f.submit "Upload", :disable_with => 'Uploading...' %>
<% end -%>

TextMate makes this very easy to type. Type ff then press Tab to lay out the basic form_for skeleton. Use : then Tab to add a key-value pair of the form :key => "value"; type the key, press Tab and type the value. Tab again moves you to the comma delimiter, and so on.

The most important part of the form is the :html => { :multipart => true } option. This ensures that the POST-request parameters will contain the actual file contents. The request will contain a parameter called upload (as defined by the first argument of the form_for) which maps to a dictionary with key csv mapping to a File object which the application can parse to extract the uploaded CSV. Within the Rails controller for handling the POST request, the File object will be found by accessing params[:upload][:csv].

When the user fills in the form and clicks Upload, the browser will send a POST request containing the CSV-file contents. The Rails application needs to respond. Hence it needs a route describing how the request and URL path translates to controller and action. Under Rails 3, this becomes very easy. Just add the following line to your config/routes.rb. Here, csv/import specifies the URL path; while csv#upload specifies controller and action respectively. When Rails routing sees a POST at that URL path, it will invoke method upload of the CSV controller, class CsvController.

  post "csv/import" => 'csv#upload'

This route needs a corresponding action for the CSV controller. Add this method to your CsvController class, source at app/controllers/csv_controller.rb under the application’s source tree.

  def upload
    # While under development, just respond by rendering some in-line text.
    # Send back the request parameters in JSON (JavaScript Object Notation)
    # format, i.e. something reasonably easy to parse with the human eye.
    render :text => params.to_json
  end

Store the CSV contents

Where to store the imported CSV information? We could store the CSV file verbatim somewhere on a local file system; that would be typical. But let us assume that there is no local file system such as for web applications running in the cloud.

Storing the CSV temporarily in some kind of document-based key-value store like MongoDB or CouchDB would be another alternative. It would live outside the database. The application database would contain a link to the external ‘document’ and read it when required. But no. For now, let us keep it fairly simple. Instead, we will conceptually map the CSV to a simple data model and store the CSV information within the database itself. See data model below.

ImportTables have many ImportCells; ImportCells have row and column indices, string contents and belong to one particular ImportTable. The database will index the cells by their import_table_id (back-reference to the owning import table) in order to pull all cells belonging to a table quickly from the database into main memory.

Implementing this model in Rails proves relatively easy.

$ rails g scaffold import_table original_path:string
      invoke  active_record
      create    db/migrate/20100715123031_create_import_tables.rb
      create    app/models/import_table.rb
      invoke    test_unit
      create      test/unit/import_table_test.rb
      create      test/fixtures/import_tables.yml
       route  resources :import_tables
      invoke  scaffold_controller
      create    app/controllers/import_tables_controller.rb
      invoke    erb
      create      app/views/import_tables
      create      app/views/import_tables/index.html.erb
      create      app/views/import_tables/edit.html.erb
      create      app/views/import_tables/show.html.erb
      create      app/views/import_tables/new.html.erb
      create      app/views/import_tables/_form.html.erb
      invoke    test_unit
      create      test/functional/import_tables_controller_test.rb
      invoke    helper
      create      app/helpers/import_tables_helper.rb
      invoke      test_unit
      create        test/unit/helpers/import_tables_helper_test.rb
      invoke  stylesheets
   identical    public/stylesheets/scaffold.css
$ rails g model import_cell import_table_id:integer row_index:integer column_index:integer contents:string
      invoke  active_record
      create    db/migrate/20100715123207_create_import_cells.rb
      create    app/models/import_cell.rb
      invoke    test_unit
      create      test/unit/import_cell_test.rb
      create      test/fixtures/import_cells.yml

To establish the one-to-many association between import table and import cell, add two new lines: a has_many and a belongs_to. Your app/models/import_table.rb and app/models/import_cell.rb should look like this. The import table’s :dependent => :destroy option instructs Rails to delete its cells when you delete a table.

class ImportTable < ActiveRecord::Base
  has_many :import_cells, :dependent => :destroy
end

class ImportCell < ActiveRecord::Base
  belongs_to :import_table
end

For speedy performance, you also need to add an index for the import cells. Generate a migration.

$ rails g migration add_index_for_import_cells
      invoke  active_record
      create    db/migrate/20100715124738_add_index_for_import_cells.rb

Then edit the newly-created migration code, adding instructions to add and remove an index. Without this, whenever you ask Rails for a table’s cells using table.import_cells where table references an instance of ImportTable, the answer will arrive but slowly because the database cannot quickly lookup the cells given a particular import_table_id which uniquely identifies the import table. Note also, the index is non-unique. The answers to table.import_cells which navigate the one-to-many table-to-cell association is an array of many ImportCell instances.

class AddIndexForImportCells < ActiveRecord::Migration
  def self.up
    add_index :import_cells, [:import_table_id]
  end

  def self.down
    remove_index :import_cells, :column => [:import_table_id]
  end
end

Finally, do not forget to run the ‘up’ migrations to upgrade your database schema. Run rake db:migrate.

Upload action

Thus far, we have the means to store CSV table information, but do not yet have the code in place to parse the uploaded CSV into import tables. The CsvController method below uses the FasterCSV gem to parse the incoming file. Edit your app/controllers/csv_controller.rb source to look like this.

require 'fastercsv'

class CsvController < ApplicationController
  def import
  end

  def upload
    table = ImportTable.new :original_path => params[:upload][:csv].original_path
    row_index = 0
    FasterCSV.parse(params[:upload][:csv]) do |cells|
      column_index = 0
      cells.each do |cell|
        table.import_cells.build :column_index => column_index, :row_index => row_index, :contents => cell
        column_index += 1
      end
      row_index += 1
    end
    table.save
    redirect_to import_table_path(table)
  end
end

The code constructs a new import table passing the original file’s path; original_path is a column in the ImportTable database table. The upload method uses the build method on the to-many association between table and cell in order to build new cells and attach them to the table. After parsing, the method saves the table then redirects the user to its ‘show’ page so that the user can see the newly-imported data.

Add the following to Gemfile for Rails 3. This tells Rails to prepare the package for import. Without this you cannot do a require 'fastercsv'. Gemfile appears in the root directory of the application folder. Although, if you are using TextMate on a Mac, locating any file no matter where it lives is very quick using Command+T then start typing the name. A list of matches starts to appear. Just pick the one you want.

gem 'fastercsv'

Then to view the uploaded table, add these lines to your ImportTablesController’s show method.

    @import_cells = @import_table.import_cells
    @row_index_max = @import_cells.map { |cell| cell.row_index }.max
    @column_index_max = @import_cells.map { |cell| cell.column_index }.max

Add the lines above after finding the import table, i.e. after @import_table = ImportTable.find(params[:id]). Then display cell contents in app/views/import_tables/show.html.erb by adding this piece of Ruby-embedded HTML.

<table border="1" cellspacing="1" cellpadding="1">
  <% 0.upto(@row_index_max) do |row_index| %>
    <% row = @import_cells.select { |cell| cell.row_index == row_index } %>
    <tr>
      <% 0.upto(@column_index_max) do |column_index| %>
        <td>
          <%= row.select { |cell| cell.column_index == column_index }[0].contents %>
        </td>
      <% end %>
    </tr>
  <% end %>
</table>

Given the import cells collected by the CSV controller together with the index maxima, this view code builds a standard HTML table comprised of tr and td (table row and table data) tags. The row = line (line 3) optimises the iteration somewhat by first collecting together all cells matching the current row index. This is a smaller number of cells from which to select individual cells matching the column index within the inner loop.

Merging, stage 2

At this point, you can navigate to http://localhost:3000/csv/import. You can generate and drop a CSV file from Finder onto the Choose File button (a Mac shortcut for choosing a file) and click Upload. The Rails application then uploads and builds an import table of cells. By redirection, the app then displays the table. So far so good.

However, this is only half the story. What the user actually wants to do is to create People and Places. The CSV information is just the raw data. Some of the columns will contain names of people (first name, last name) while some columns may contain addresses. The columns just contain random words of course, unless you have some real data to play with. But you get the idea. The data needs merging with the other tables to create workable records.

Sketch below outlines the design for merging CSV import tables.

We will add a row of table headers to the import table viewing page. Initially they will contain empty ‘select’ buttons. The user starts by selecting which table to import into. After choosing, the page will automatically update the column headers with the appropriate choices for input field mapping. If the chosen table is Person, column choices switch to none, first name or last name. For Places, only two choices: none or address. The user can then assign columns to fields, clicking Merge when ready.

We therefore want the import-table show page to become dynamic. When the user selects the table, the selectors for column field must change appropriately. To make this happen, we take a page out of Ryan Bates’ book. Since the database records are static, we can set up a JavaScript array of mappings between tables and columns. When the user selects the table to import into, person or place, JavaScript within the page can respond by updating the column selectors.

Converting to jQuery with UJS

We plan to use jQuery rather than Prototype as our JavaScript framework. By default however, Rails has set up our application to include Prototype and script.aculo.us. Remove the following list of files.

public/javascripts/controls.js
public/javascripts/dragdrop.js
public/javascripts/effects.js
public/javascripts/prototype.js

Replace the rails.js UJS script found in public/javascripts with the jQuery-based version found at GitHub. UJS stands for Unobtrusive JavaScript, new in Rails 3. By making use of HTML 5 enhancements, the UJS feature avoids littering HTML pages with embedded JavaScript. Download and install jQuery 1.4.1 in the same place, at public/javascripts.

There is one more thing to do before jQuery becomes the new default JavaScript framework for our application: create a new ‘initialiser’ to override Prototype and script.aculo.us as the default framework. Create a new Ruby script, config/initializers/jquery.rb; exact name is not critical. This will run when the Rails server initialises. Add the following code.

module ActionView::Helpers::AssetTagHelper
  remove_const :JAVASCRIPT_DEFAULT_SOURCES
  JAVASCRIPT_DEFAULT_SOURCES = %w(jquery-1.4.1.min rails)
  reset_javascript_include_default
end

This will override the default JavaScript sources with jQuery 1.4.1 and its UJS helper. jQuery ready!

Table headers, table selection, Merge button

Next, we need to add the import table headers, a table selection and a Merge button to the current import-table viewing code. Add the following. I’ve commented out where the table contents go, just to make it a little clearer.

<% form_for :merge do |f| -%>
  <table border="1" cellspacing="1" cellpadding="1">
    <tr>
      <% 0.upto(@column_index_max) do |column_index| %>
        <th>
          <%= f.select(column_index, []) %>
        </th>
      <% end %>
    </tr>
    # same as before goes here
  </table>
  <label><%= 'Select a table for merging:' %></label>
  <%= f.select(:table, @tables.collect { |t| [t, t] }, { :include_blank => true }, { :onchange => "mergeTableSelected();" }) %>
  <%= f.submit "Merge", :disable_with => 'Merging...' %>
<% end -%>

Some things to note about this code:

It encloses the entire table within a form. That means that the form will send a POST request with the form parameters as fields. Within the receiving controller method, expression params[:merge] will answer a Hash of values: one for each of the columns, and one for the selected table.
Initially, the table headers are null selections. It will produce select tags with no options. We will fill this with content using JavaScript when the user chooses which table (people or places) for merging into.
Whenever the user changes the table selection, the browser will invoke a JavaScript function named mergeTableSelected.

The code accesses an instance variable @tables. This is not yet defined. But we will now define it in the import tables controller as follows.

@tables = ActiveRecord::Base.connection.tables.select { |t| t != 'schema_migrations' }

This code performs a little bit of Active Record introspection. It asks Rails for the tables associated with its database connection. The answer is an array of table names, strings. The Array select method de-selects the schema_migrations table, an internal table used by Rails. We want our app to ignore this one, in future possibly others too.

Merge table selected

Next, add the following JavaScript code to the show.html.erb amoung the import tables views. It injects a blob of JavaScript into the show page.

<%= javascript_tag do -%>
  var columns = new Array();
  <% for table in @tables -%>
    <% for column in ActiveRecord::Base.const_get(ActiveRecord::Base.class_name(table)).columns -%>
      columns.push(new Array('<%= table %>', '<%= column.name %>'));
    <% end -%>
  <% end -%>
  function mergeTableSelected() {
    var o = $('select#merge_table option:selected');
    $('th select option').remove();
    $('th select').each(function(i, select) {
      select.options.add(new Option());
      $.each(columns, function(j, column) {
        if (o.text() == column[0]) {
          select.options.add(new Option(column[1]));
        }
      });
    });
  }
<% end -%>

When Rails renders the page, it iterates the introspected @tables, building an array of arrays called columns. Each element contains a table name and a column name. When the user picks a table, the mergeTableSelected() function accesses the selection, removes all existing options from the table header select tags and fills them with new options based on the column names matching the newly selected table name. Does that make sense? The JavaScript relies on jQuery of course. See jQuery documentation.

The merge

Finally, the actual merge operation. When the user clicks Merge, their browser posts the parameters to import_tables/:id where :id stands for the unique identifier of the relevant import table. We need to match this to a method on the import tables controller. Add the following route to routes.rb.

  match 'import_tables/:id' => 'import_tables#merge'

And add the merge method implementation.

  def merge
    # Uncomment the following line if you want to debug this method. However,
    # do not forget to uncomment the gem 'ruby-debug' in Gemfile also; this
    # assumes you have the ruby-debug gem installed too, and do the usual
    # thing if not, i.e. sudo gem install ruby-debug. Calling "debugger"
    # inserts a break point when the server hits this point in the
    # application. From that point you can interrogate the Rails state, single
    # step over or into message-sends and so forth. Very useful for debugging!
    #
    # debugger
    
    import_table = ImportTable.find(params[:id])
    import_cells = import_table.import_cells
    row_index_max = import_cells.map { |cell| cell.row_index }.max
    column_index_max = import_cells.map { |cell| cell.column_index }.max
    
    # Pull the merge parameters from the POST request. The form sets up the
    # column mappings and merge table choice. Then use a little bit of
    # ActiveRecord introspection to derive the table's class name followed by
    # the class object. We will use this latter object to instantiate the
    # merged records.
    merge = params[:merge]
    merge_table = merge[:table]
    klass = ActiveRecord::Base.const_get(ActiveRecord::Base.class_name(merge_table))
    
    # Determine which columns have been mapped. Ignore the rest. Intersect the
    # requested column names with actual column names. Perhaps we should abort
    # and display some error message if the intersection proves empty because
    # the user did not select any columns.
    inverted_merge = merge.invert
    column_names = inverted_merge.keys & klass.column_names
    
    # Finally, create new instances, one per row. Iterate the rows, then for
    # each row, iterate the mapped columns. Select the matching cell and
    # update the record's corresponding column. Redirect to the merged table
    # when done.
    0.upto(row_index_max) do |row_index|
      row = import_cells.select { |cell| cell.row_index == row_index }
      instance = klass.new
      column_names.each do |column_name|
        column_index = inverted_merge[column_name].to_i
        contents = row.select { |cell| cell.column_index == column_index }[0].contents
        instance[column_name] = contents
      end
      instance.save
    end
    eval "redirect_to #{merge_table}_path"
  end

Hopefully, the in-line comments will help to elucidate what this method is doing and why.

Conclusions

What have we learned? Importing CSV is relatively straightforward using Rails 3 and jQuery. But the exercise has raised some outstanding questions and pointed forward to some interesting future directions.

Outstanding questions

Uploading of CSV files does not deal with encoding issues. For the English language that might not be an enormous problem. But supporting other languages might begin to throw up bigger and bigger issues depending on how exotic the language needing conversion to Unicode (the internal encoding). There may also be number-formatting issues, e.g. some languages use commas for full stops (periods) within numbers.
Column typing has not been considered. Some CSV columns may contain strings, others numbers. How these convert from CSV to real data within the application will depend on the conversion path between uploading and merging of data.

Future directions

Some CSV files may have headings in the first row. Import merging might be friendlier if the user could ignore the first row by checking a box entitled, “Ignore first row.”
The software does not yet support any form of row selection and de-selection. It merges all rows. A real application would need to trim off the fat: remove duplicates, sort by columns, combine rows by dragging and dropping cell contents in-between rows, etc.

Retaining C++ Objects

Tue, 09 Mar 2010 22:31:53 -0800

C++ and Objective-C do not always mix too well, although the two languages are fully compatible.

With respect to compilation phases, alternating between C, C++, Objective-C and Objective-C++ presents no problem. You just write your software accordingly, freely mixing C, Objective-C, C++ and Objective-C++. Just make sure that the compiler knows what each translation unit contains, normally by source file extension: c for C; cc or cpp or cxx for C++; m for Objective-C; and mm for Objective-C++.

That being specified correctly, your sources compile and link without issues. Only when you start running the code side-by-side however, you might find that memory management can become something of a mishmash. Basic C++ fundamentally has no memory management; I mean nothing automatic. Asking for memory when you want it, freeing memory when you’re done with it: that is all bare C++ gives you. So you typically just roll your own, or find some more-advanced alternative such as Boehm’s garbage collector.

Wouldn’t it be nice however, if you could just simply retain, release and auto-release your C++ objects, just like you do with NSObjects? It would be very nice.

This article outlines a little “trick” for retaining C++ objects on Mac and iPhone. It takes advantage of C++ inheritance; and is simple, so no dependence on internals of CFTypeRef or NSObject. The memory cost is low; just one additional NSObject-derived object per retained C++ object. Final feature, implementation separates from interface by design. Hence you can include retaining within bodies of source without the things being retained having any knowledge of Objective-C. Translation units remain plain old C++, no additional dependencies. The implementation exists apart.

MIT-licensed code provided in full.

Who Cares?

The audience for this topic are developers wanting to integrate C++ libraries with Objective-C on iPhone or Mac under the retain-release management paradigm. C++ objects become subject to standard Apple memory management, even without classes being aware of it.

Start With a Test

Always best: start with a test.

Basic failing test

Allocate a C++ object. Then autorelease it. Place this within an autorelease pool context. Initially test-failing gives a leak. Test-success eliminates the leak. This is the test.

In code form, it looks like this.

// Instantiate an instance of TestClass. Retain then auto-release it. Within
// the context of an auto-release pool, will it delete?
pool = [[NSAutoreleasePool alloc] init];
(new TestClass)->retain().autorelease();
[pool release];

TestClass has the following basic definition.

class TestClass : public c_plus_plus_retained
{
public:
    TestClass()
    {
        log("hello");
    }
    ~TestClass()
    {
        log("goodbye");
    }
private:
    void log(const char *message)
    {
        // print message
    }
};

While c_plus_plus_retained has the following declaration.

struct c_plus_plus_retained
{
    // constructors & virtual destructor
    c_plus_plus_retained() : retainer_object(0) {}
    c_plus_plus_retained(const c_plus_plus_retained &copy) : retainer_object(0) {}
    virtual ~c_plus_plus_retained() {}

    // mirroring NSObject semantics
    c_plus_plus_retained &retain();
    void release();
    c_plus_plus_retained &autorelease();

    // accessor
    void *retainer();

private:
    void *retainer_object;
};

The above code declares a pure C++ public interface; notice there are no includes hence no other dependencies. Any general C++ translation unit can see this interface declaration without baulking. It contains nothing about Objective-C or Objective-C++. Such dependencies appear at link- and run-time, not at compile-time.

This is by design. You can include this header in any C++ source.

Successful Implementation

The implementation allocates an NSObject-derived retainer which deletes the retained C++ instance during its -dealloc method.

c_plus_plus_retained &c_plus_plus_retained::retain()
{
    if (retainer_object)
    {
        [(CPlusPlusRetainer *)retainer_object retain];
    }
    else
    {
        retainer_object = [[CPlusPlusRetainer alloc] initWithRetained:this];
        // Hereafter you must never delete this object. Doing so will break the
        // implicit design contract. Asking to retain actually places the
        // retained object within the scope of retain-release memory
        // management. Only releasing hereafter will release the retainer and
        // delete the object. Henceforward, delete becomes release. Calling
        // delete will double-delete this object.
    }
    return *this;
}

void c_plus_plus_retained::release()
{
    if (retainer_object)
    {
        [(CPlusPlusRetainer *)retainer_object release];
    }
}

c_plus_plus_retained &c_plus_plus_retained::autorelease()
{
    if (retainer_object)
    {
        [(CPlusPlusRetainer *)retainer_object autorelease];
    }
    return *this;
}

void *c_plus_plus_retained::retainer()
{
    if (retainer_object == 0)
    {
        retain().autorelease();
    }
    return retainer_object;
}

Semantically, the c_plus_plus_retained class initially has no retain count. It remains initially invisible respecting retain-release memory management. This changes when you retain it for the first time. At that point, you no longer delete the object. You must release it, doing so manually or by auto-releasing.

Beware the C++ Copy Constructor!

By default the compiler supplies a bitwise copy that copies everything verbatim. If you create a copy however, the duplicate has no retainer. If you want duplicates to retain then invoke retain(). If you want duplicates to auto-release invoke retained->retain().autorelease() assuming ”retained” is a pointer to c_plus_plus_retained or its sub-class.

Grab a Copy

The repositories live on GitHub at Library of useful C++ classes for iPhone and Mac and iPhone app project encapsulating tests for c_plus_plus_retained. Drop the iPhone app project into the Library folder then open, build and run. You’ll see something like this (memory addresses will vary, of course).

Gloss Caustic Shader for iPhone

Thu, 04 Mar 2010 20:47:00 -0800

Ole Begemann has done some very useful work, porting the gloss-caustic shader to iPhone OS. This work has been long overdue. Many thanks Ole!

I’ve merged Ole’s changes into my Git repo, albeit with a few modifications. This article outlines the changes to the changes.

What has changed?

I’ll not dig too much into Ole’s enhancements. Ole does that on his page. In summary:

Shader sources compile for OS X and iPhone OS.
Has two sample projects, one for OS X and the other for iPhone.

Why does it need porting?

The fundamental difference between iPhone and OS X for the gloss-caustic shader concerns its use of NSColor. Simply put, iPhone does not have such a class; instead, it has UIColor with limited support for colour spaces and no support for RGB-to-HSB conversion.

Strangely, you can make the reverse conversion, from HSB to RGB by invoking class method

+colorWithHue:saturation:brightness:alpha:

and UIKit answers with a colour with triple RGB components whence you can access the red, green, blue and alpha component values. But iPhone has no instance method

-getHue:saturation:brightness:alpha:

as does OS X.

The basic approach

The simple approach Ole takes is to surround the difference between OS X and iPhone with #if TARGET_OS_IPHONE, #else, #endif blocks. Xcode defines TARGET_OS_IPHONE only when compiling for iPhone.

Under normal circumstances, I would avoid this approach since it makes code difficult to read and maintenance harder in the long run. Nevertheless, the pre-processor conditional blocks turns out relatively small in number and in extent. Each one in general surrounds just one line of code: the first condition presents the iPhone’s UIColor-based alternative, while the second condition presents OS X’s NSColor-based alternative.

Maintaining semantics

Ole has included a number of useful functions for colour conversion, based on work by Erica Sadun and some standard RGB-to-HSB conversion code. I’ve repackaged these as extensions on UIColor with semantics mirroring that of NSColor.

Interface for UIColor(RRUIKit) as follows.

// Fill in some of the "missing" UIColor methods, making UIColor more compatible
// with NSColor. This includes access to individual colour components and HSV
// conversion. Use similar method signatures and semantics as far as possible.

@interface UIColor(RRUIKit)

- (UIColor *)colorUsingColorSpaceModel:(CGColorSpaceModel)model;

- (CGColorSpaceRef)colorSpace;
- (CGColorSpaceModel)colorSpaceModel;

- (NSUInteger)numberOfComponents;
- (void)getComponents:(CGFloat *)components;

- (CGFloat)redComponent;
- (CGFloat)greenComponent;
- (CGFloat)blueComponent;

- (CGFloat)alphaComponent;

//---------------------------------------------------- Hue-Saturation-Brightness

- (void)getHue:(CGFloat *)hue saturation:(CGFloat *)saturation brightness:(CGFloat *)brightness alpha:(CGFloat *)alpha;
    // Answers the components of RGB colours as hue, saturation and
    // brightness. Adds the missing UIColor method for converting RGB to
    // HSB. This method assumes that self (an instance of UIColor) has RGB
    // colour model.

@end

Serialisation

Ole implements a set of extensions on RRGlossCausticShader for saving shader setting to a dictionary. I’ve enhanced this functionality by implementing the NSCoding protocol for shader and matcher classes.

Coding adds a level of extra flexibility. The coding protocol lets you serialise trees of objects (the shader and its enclosed matcher) by archiving to any data stream.

Key-value coding

I’ve also simplified the iPhone sample’s view controller. iPhone OS does not include bindings. Hence implementing the update cycle within the controller can become rather tedious when there are many control elements, such as with gloss-caustic shaders.

My enhancement on Ole’s enhencement employs key-value coding, i.e. accessing properties via -valueForKeyPath: and -setValue:forKeyPath:. It makes things a little less long-winded.

Your feedback

As always, very welcome. Thanks again Ole. Your improvements are much appreciated. You can find Ole’s work at GitHub. Mine also at GitHub.

Gloss-Caustic Shading

Tue, 09 Dec 2008 19:25:45 -0800

Matt Gallagher recently wrote a very useful article about drawing gloss gradients using Core Graphics. In his article, Matt describes how to reproduce the oft-seen glossy gradient effect. Thanks Matt! It’s a nice article. “Cocoa with Love” lovingly provides the working source code. This little article aims to complement Matt’s work.

I’ve also re-factored the software and packaged the result within an Objective-C class called RRGlossCausticShader. This packaging automatically adds support for key-value coding and observing. Bindings then let you easily wrap the class within a little application able to adjust the many parameters interactively.

Show me the money

Before going any further, you might first want to see the results. I know I would! Download the project to play with the shader. Compile and run the application using Xcode. The main window appears as follows. Inspector panels also appear from where you can interactively adjust the many shading parameters.

Gloss above, caustic below. Those are the two halves of the shading. Gloss appears in the top half, caustic in the bottom half. Within each half, an exponential function blends a given non-caustic base colour with whiteness above and with matching caustic colour below. The main window displays these basic elements of the shading process: the shading itself (left), non-caustic base colour (top right) and coefficient of the exponent function (bottom right).

Re-factoring

My version of Matt’s work includes some re-factoring. Rather than just the one functional interface, the version that you’ll find within the project involves three modular utility classes. - RRGlossCausticShader encapsulates shading - RRCausticColorMatcher finds caustic matches for given colours - RRExponentialFunction wraps the exponential maths - RRLuminanceFromRGBComponents returns luminance from RGB triples

This re-factoring has some benefits. First, it promotes re-use. Other requirements may call for RGB-to-luminance conversion, or a generic exponential function for example; or you might want to sub-class the caustic colour matcher and add some customisation. Separating out the individual sub-requirements adds some extra scope for growth. I think it also makes the source code somewhat easier to follow and therefore comprehend. But that might just be my own personal opinion. Your mileage may vary, as they say!

Anyway, the purpose of this article is to outline some of the differences in implementation and the underlying thinking. Comments welcome, of course.

Twinkle, twinkle

The gloss effect on the upper half of the gradient derives from the base colour’s luminosity. So obtaining luminance from a given Red, Green and Blue is part of the glossing requirement.

As you can see below, I replace Matt’s conversion with the one described at OpenGL. The difference is small, almost non-existent. Only, the comment that “Haeberli notes that [the YIQ colour conversion values used by Matt] are incorrect in a linear RGB colour space” convinced me to make the small change. Just call me fussy.

CGFloat RRLuminanceFromRGBComponents(const CGFloat *rgb)
{
    // 0.3086 + 0.6094 + 0.0820 = 1.0
    return 0.3086f*rgb[0] + 0.6094f*rgb[1] + 0.0820f*rgb[2];
}

Notice a few other things. I’m using CGFloat type for floats because this corresponds exactly with Apple’s usage for colour components. Can we always assume that CGFloat equals float? No. In fact, CGFloat is sometimes double! This happens when 64-bit compiling for instance. Argument const-correctness is another feature.

Caustic nature

The lower half of the gradient blends the base colour into shades of yellow (yellow is the default caustic hue). The lower end of the gradient starts to look more-and-more tinted towards the yellow. However, the precise colour depends upon the non-caustic base colour. For blue colours, for example, the default caustic switches to magenta. Blue looks better fading toward magenta, rather than yellow. In all cases though, the amount of caustic to non-caustic blending varies according to the cosine of the distance between the caustic and non-caustic hues.

So rather than having a function handle the caustic colour matching and implementing the adjustable parameters as manifest constants, the new version implements a “colour matching” class. Interface listed below. The class implements adjustable parameters as read-write class properties with all the necessary setters and getters. This approach buys some advantages. It automatically adds support for key-value coding and observing. In practice, it means that user-interface controls can bind to these properties using Cocoa Bindings.

@interface RRCausticColorMatcher : NSObject
{
    CGFloat causticHue;
        // Yellow by default.
    CGFloat graySaturationThreshold;
        // Saturation level at which colours appear grey. Below this level,
        // matcher response snaps to pure caustic.
    CGFloat causticSaturationForGrays;
        // Defines the caustic saturation for grey colours. Grey colours fall
        // below the grey saturation threshold. When saturation drops too low,
        // everything looks grey.
    CGFloat redHueThreshold;
        // Colours at this threshold and above match to default caustics rather
        // than default magenta for blues.
    CGFloat blueHueThreshold;
        // Triggers a switch to magenta caustics. Hues at blue and beyond
        // display magenta-modulated caustics by default.
    CGFloat blueCausticHue;
        // Magenta by default. Magenta caustics for blue colours.
    CGFloat causticFractionDomainFactor;
        // Expands or contracts the caustic fraction's domain. With factor equal
        // to 1, non-caustic and caustic hues blend according to the cosine of
        // their difference. Smaller the difference, greater the amount of
        // caustic hue. Defaults to 1.4 meaning that the point of absolutely no
        // caustic blending occurs at 1/1.4 difference from caustic hue. Try
        // plotting cos(x*pi*1.4) in the -1,1 interval.
    CGFloat causticFractionRangeFactor;
        // Scales the caustic fraction which without a factor outputs a blending
        // fraction between 0 and 1 in favour of the caustic blend. Defaults to
        // 0.6 which scales down the amount of caustic hue-and-brightness by
        // that amount.
}

- (NSColor *)matchForColor:(NSColor *)aColor;
    // Matches the given colour. Answers a matching caustic colour. The result
    // shifts hue and brightness towards yellow. Saturation remains unchanged.
- (void)matchForHSB:(const CGFloat *)hsb caustic:(CGFloat *)outHSB;
    // Does the work.

@property(assign) CGFloat causticHue;
@property(assign) CGFloat graySaturationThreshold;
@property(assign) CGFloat causticSaturationForGrays;
@property(assign) CGFloat redHueThreshold;
@property(assign) CGFloat blueHueThreshold;
@property(assign) CGFloat blueCausticHue;
@property(assign) CGFloat causticFractionDomainFactor;
@property(assign) CGFloat causticFractionRangeFactor;

@end

Exponentially

Shading employs an exponential function. As the gradient progresses from 0 to 0.5, gloss white blending increases exponentially in the 0,1 interval. Progressing through the bottom half of the gradient from 0.5 to 1, caustic blending increases exponentially. The implementation re-factors the exponential function. Interface listing below. It becomes a C-style object class and thereby minimises its dependencies: just plain C types and standard library math.h and hence very suitable for repeated invocations from the bowels of a shading function.

// Encapsulates an optimising generic Exponential Function where
//      y=1-(exp(x*-c)-exp(-c))/(1-exp(-c))
// and where 0<c is a general coefficient describing the exponential
// curvature. The function's input domain lies within the 0..1 interval, its
// output range likewise. The implementation optimises by pre-computing those
// constant terms depending only on the coefficient whenever the coefficient
// changes. Repeated evaluation takes less computing time thereafter.
struct RRExponentialFunction
{
    float coefficient;
    float exponentOfMinusCoefficient;
    float oneOverOneMinusExponentOfMinusCoefficient;
};

typedef struct RRExponentialFunction RRExponentialFunction;

void RRExponentialFunctionSetCoefficient(RRExponentialFunction *f, float c);
float RRExponentialFunctionEvaluate(RRExponentialFunction *f, float x);

Shading

And finally, the “gloss-caustic shader” class brings all the disparate pieces together. The design aims for reusability. Idea is that you instantiate a shader, set up the parameters such as non-caustic colour or any other necessary adjustments to defaults, then re-use it over-and-over whenever you need to draw the shading.

@interface RRGlossCausticShader : NSObject
{
    struct RRGlossCausticShaderInfo *info;
    RRCausticColorMatcher *matcher;
}

- (void)drawShadingFromPoint:(NSPoint)startingPoint toPoint:(NSPoint)endingPoint inContext:(CGContextRef)aContext;

- (void)update;
    // Send -update after changing one or more parameters. Setters do not
    // automatically update the shader. This is by design. It applies to the
    // caustic colour matcher too. Change anything? Send an update. Otherwise,
    // if the setters automatically update, multiple changes trigger unnecessary
    // multiple updates. It's a small optimisation.
    // Updating follows the dependency chain. Caustic colour depends on
    // non-caustic colour along with all the caustic colour matcher's tuneable
    // configuration settings. Updating also re-computes the gloss. Gloss
    // derives from non-caustic colour luminance, among other things.

//---------------------------------------------------------------------- setters

- (void)setExponentialCoefficient:(float)c;
- (void)setNoncausticColor:(NSColor *)aColor;
    // Converts aColor to device RGB colour space. The resulting colour
    // components become the new non-caustic colour. This setter, like all
    // others, does not automatically readjust the dependencies. Invoke -update
    // after adjusting one or more settings.
- (void)setGlossReflectionPower:(CGFloat)powerLevel;
    // Assigns a new power level to the gloss reflection.
- (void)setGlossStartingWhite:(CGFloat)whiteLevel;
    // White levels range between 0 and 1 inclusive. Gloss starting white levels
    // typically have higher values compared to ending white level.
- (void)setGlossEndingWhite:(CGFloat)whiteLevel;

//---------------------------------------------------------------------- getters

- (float)exponentialCoefficient;
- (NSColor *)noncausticColor;
    // Returns the non-caustic colour.
- (CGFloat)glossReflectionPower;
- (CGFloat)glossStartingWhite;
- (CGFloat)glossEndingWhite;

// Key-value coding automatically gives access to colour matching for caustic
// colours. Special note though, changing caustic matcher thresholds does not
// (repeat not) automatically adjust the shader's caustic colour. You need to
// update the shader when ready.
// Currently, the matcher property offers read-only access. You cannot set the
// matcher! However, perhaps future versions will allow setting in order to
// override the default caustic matching behaviour. Developers might want to
// customise the colour matching algorithmically as well as by tweaking
// parameters.
@property(readonly) RRCausticColorMatcher *matcher;

@end

The sample project explains how to use the shader. I hope it’s clear enough. The sources have an MIT license. I haven’t tried it out on iPhone or pre-Leopard Mac, so can’t make any comments about portability except to say that porting should be fairly straightforward. But no doubt you’ve heard that before!

Outline view, tree controller and itemForPersistentObject

Wed, 10 Sep 2008 07:42:56 -0700

This is the scenario: your user interface comprises an outline view and a hierarchical data model. You want the outline view to display the hierarchy and remember the expansion state automatically in preferences. Hence when the user re-runs the application, the items that were expanded are still expanded, and vice versa: what was collapsed remains so. Outline view, tree controller, hierarchical model, bindings. That’s the recipe.

According to some, storing expansion state of an outline view when used with a tree controller is not just difficult: it’s impossible! But is it? No, is the simple answer. It’s actually quite easy. In this article I introduce a new helper class called RROutlineViewExpandedItemsAutosaver! Original aren’t I? It does not involve sub-classing or access to private methods. The solution presented uses only documented interfaces and only requires a small stateless class instance for handling all outline view auto-saving technicalities. It does assume Core Data use for modelling. But you can easily adapt the technique for other data-model implementations.

It’s impossible?

At first it seems so. For a start, if you read the documentation for setAutosaveExpandedItems: you can see that you also need to implement two data-source methods: outlineView:itemForPersistentObject: and outlineView:persistentObjectForItem:. Goes without saying, you also need a data source implementing those methods. Otherwise it does not work. In fact, it’s not exactly clear what these two necessary methods are supposed to do. The document talks about translating to and from an “archived object.” What does that mean exactly?

You can find a number of posts at CocoaBuilder on this issue. Keith Blount started a thread in 2005; Nick Briggs asked about it again in 2006. But no answers forthcoming! Some discussion exists and some solutions have been posted at CocoaDev (OutlineViewCoreDataBindings and NSOutlineViewStateSavingWithNSTreeController). But there is nothing definitive. Plus, the solution supplied relies on private methods and sub-classing. Messy!

Start with a test

In the spirit of Agile, let’s start with a test that fails.

Apple’s Developer Connection provides sample code. Their AbstractTree demonstrates Core Data, use of bindings along with an NSTreeController. Download the sample here as a ZIP file. It contains two subdirectories: AbstractTree and Tutorial. The tutorial is pretty good. It should help you get up-to-speed if you need some familiarity with the basic technology. Build and run the project living under the AbstractTree folder. It presents you with a window comprising an empty outline view and two buttons.

Click Add a few times. You get a series of nested nodes named “untitled node”. Quit the application, re-run and you find that, although data saved, the expansion state of the outline view resets. You have to manually expand each item. Of course, you can Option-click the disclosure triangles to auto-expand an item and all its sub-items. But that’s not really what we want. We want the expand or collapse state of each element displayed in the outline view to persist! That’s the goal.

So far so good. We have a test case that fails. Just what we wanted.

Outline view’s auto-save name

Open the sample’s MainMenu.xib. Select the NSOutlineView. Set its Autosave name to (say) Nodes. Exact value does not matter. This is just a little piece of text for constructing the preferences key. The application’s defaults will contain an array containing the expanded items. The key will become “NSOutlineView Items Nodes” where Nodes corresponds the the specified Autosave name.

Leave the Autosave Expanded Items check box unchecked! Strange but important. If you check this box, the framework resolves the expand-collapse question straightaway. It needs to wait until bindings have been fully established and the data store has been added. The application will instead enable this option programmatically when the application finishes launching. Not before.

Add the new class

Add the interface header, RROutlineViewExpandedItemsAutosaver.h, to the project. Contents as follows. Download header and module sources here.

#import <AppKit/AppKit.h>

//------------------------------------------------------------------------------
// RROutlineViewExpandedItemsAutosaver
//------------------------------------------------------------------------------
// This class acts as a "dummy" outline-view data source. Dummy because it does
// not source any data. But you wire it up as though it did. In reality, its
// sole purpose is to enable automatic saving of an outline view's expanded
// items. It sounds counter-intuitive, but you can apply bindings through a tree
// controller and at the very same time hook up a data source (such as one of
// these) in order to provide the necessary persistence translations.
//
// Connect an outline view to an instance of this class. Note, you can connect
// multiple outlines views to the same instance! The instance carries no
// state. Message interactions with outline views pass the outline view
// instance. So no state needed.
//
// The implementation makes a number of assumptions. It assumes you connect
// using bindings to a Core Data model. Hence for every item, it sends [[item
// representedObject] objectID] which assumes that the represented object
// responds to -objectID. Core Data's managed objects respond with a unique
// object identifier.

@interface RROutlineViewExpandedItemsAutosaver : NSObject
@end

Add the source module RROutlineViewExpandedItemsAutosaver.m. Contents follow.

#import "RROutlineViewExpandedItemsAutosaver.h"

@implementation RROutlineViewExpandedItemsAutosaver

//------------------------------------------------------------------------------
#pragma mark Outline View Data Source
//------------------------------------------------------------------------------

// Although linked to the core-data context via bindings and a tree controller,
// the outline view also has an instance of this object connected to the outline
// view's data source.

- (id)outlineView:(NSOutlineView *)outlineView itemForPersistentObject:(id)object
{
    // Iterate all the items. This is not straightforward because the outline
    // view items are nested. So you cannot just iterate the rows. Rows
    // correspond to root nodes only. The outline view interface does not
    // provide any means to query the hidden children within each collapsed row
    // either. However, the root nodes do respond to -childNodes. That makes it
    // possible to walk the tree.
    NSMutableArray *items = [NSMutableArray array];
    NSInteger i, rows = [outlineView numberOfRows];
    for (i = 0; i < rows; i++)
    {
        [items addObject:[outlineView itemAtRow:i]];
    }
    for (i = 0; i < [items count] && ![object isEqualToString:[[[[[items objectAtIndex:i] representedObject] objectID] URIRepresentation] absoluteString]]; i++)
    {
        [items addObjectsFromArray:[[items objectAtIndex:i] childNodes]];
    }
    return i < [items count] ? [items objectAtIndex:i] : nil;
}

- (id)outlineView:(NSOutlineView *)outlineView persistentObjectForItem:(id)item
{
    // "Persistent object" means a unique representation of the item's object,
    // representing the objects identity, not its state. Outline view writes
    // this to user defaults as soon as the item expands. That's when it asks
    // for the persistent object, sending -outlineView:persistentObjectForItem:
    // and execution arrives here. A minor problem arises when adding new
    // items. The new item represents a new unsaved managed object. The managed
    // object only has a temporary object identifier. It will receive a
    // permanent one when saved. So, if the objectID answers a temporary one,
    // ask the context to save and re-request the objectID. The second request
    // gives a permanent identifier, assuming saving succeeds. Don't worry about
    // committing unsaved edits at this point.
    NSManagedObject *object = [item representedObject];
    NSManagedObjectID *objectID = [object objectID];
    if ([objectID isTemporaryID])
    {
        if (![[object managedObjectContext] save:NULL])
        {
            return nil;
        }
        objectID = [object objectID];
    }
    return [[objectID URIRepresentation] absoluteString];
}

@end

Add this header and module to the project, under the Classes group. An instance of this class will become the new data source for the outline view.

Add the new data-source

Add a new instance of RROutlineViewExpandedItemsAutosaver to the nib and connect the new instance to the NSOutlineView as the outline view’s dataSource. Use Interface Builder. Drag an Object from the palette to the nib. Change its class in the Identity Inspector panel (Command-6). Then connect the NSOutlineView to it as the new data source. It replaces the pre-existing connection between outline view and app delegate.

After this, the nib is ready.

App delegate

Apple have used the standard Core Data application delegate. It builds a managed object model, persistent store co-ordinator and managed object context. The classic Core Data stack! Our changes need to add a message-send for enabling auto-save expanded items to the outline view. But it’s not the only change required.

There is a subtle problem. It concerns bindings and Core Data. The important requirement is that when the outline view tries to restore auto-saved expanded items, the outline view has its items already loaded. Otherwise how can it translate “persistent objects” to items. Persistent objects, in this context, refers to keys used in the application defaults to identify the set of expanded items; everything not expanded defaults to collapsed.

Moving where the application adds its persistent store

When the application loads, it automatically loads MainMenu nib. All the object instances therein become instantiated. Indirectly, the managed object context and its other Core Data stack components come to life at this time. Therein lies the subtle problem. The Cocoa framework will not immediately load the Core Data objects if the context already has its store when nib-loading establishes the bindings. That’s a mouthful. Basically, the order must go: 1. Establish bindings. Do this wholesale. 2. Add persistent store. At this point, the outline view grabs its contents through bindings to the tree controller. 3. Enable auto-save expanded items.

Simplify the -persistentStoreCoordinator implementation to:

- (NSPersistentStoreCoordinator *)persistentStoreCoordinator {
    if (persistentStoreCoordinator == nil) {
        persistentStoreCoordinator = [[NSPersistentStoreCoordinator alloc]
            initWithManagedObjectModel:[self managedObjectModel]];
    }
    return persistentStoreCoordinator;
}

And second, add a new method:

- (void)applicationDidFinishLaunching:(NSNotification *)notification
{
    NSFileManager *fileManager;
    NSString *applicationSupportFolder = nil;
    NSURL *url;
    NSError *error;

    fileManager = [NSFileManager defaultManager];
    applicationSupportFolder = [self applicationSupportFolder];
    if (![fileManager fileExistsAtPath:applicationSupportFolder isDirectory:NULL]) {
        [fileManager createDirectoryAtPath:applicationSupportFolder attributes:nil];
    }

    url = [NSURL fileURLWithPath:[applicationSupportFolder
        stringByAppendingPathComponent:@"AbstractTree.xml"]];
    if (![[self persistentStoreCoordinator]
        addPersistentStoreWithType:NSXMLStoreType
                     configuration:nil
                               URL:url
                           options:nil
                             error:&error]) {
        [[NSApplication sharedApplication] presentError:error];
    }    
    // Watch out for this! Make sure that the data is available before enabling
    // auto-save for expanded items. You can switch it on within the nib. Problem
    // though is that the data store must be available at nib awaking time!
    // Otherwise, how can the auto-saving of expanded items compare against
    // existing items in order to determine whether or not they should be restored
    // as expanded or not.
    //
    // There's another caveat. You need to let the bindings make the necessary
    // connections first, before connecting the Core Data context and persistent
    // store coordinator to the store. In other words, the store must be added
    // last. Here is a good place. Application-did-finish-launching occurs after
    // all nib awaking methods, after bindings have been established. Hence, when
    // the store gets added, the outline view immediately sees the contents
    // through its bindings. Otherwise the outline-view expanded items auto-saver
    // cannot see the items at all.
    [outlineView setAutosaveExpandedItems:YES];
}

That’s it!

Successful test

Build and go. This time, when you expand nodes, quit then re-run, the sample correctly expands the previously-expanded items. Great. You can view the sample application’s user defaults by typing, in Terminal:

defaults read com.apple.dts.AbstractTreeApp

It will list the saved expanded items array, resembling something along these lines:

{
    "NSOutlineView Items Nodes" =     (
        "x-coredata://68A35129-6EA4-45E7-B3FB-F1C15FDC02D9/Node/p104",
        "x-coredata://68A35129-6EA4-45E7-B3FB-F1C15FDC02D9/Node/p102"
    );
}

Download the complete sample project here.

Organising view controllers, continued

Mon, 01 Sep 2008 16:59:24 -0700

The last article on this subject (Organising view controllers) started looking at an example. Apple’s ViewController sample illustrates basic use of multiple view controllers. This article completes the work.

Download the source if you would rather skip ahead. Sometimes it’s easier that way. You can see the code in its full context. Snippets and extracts don’t always tell you everything you need to know.

Missing pieces

Where did we leave off? Application delegate and window controller exist but don’t do much. The window controller has a stub for the pop-up action. It does nothing. Of course, the application needs some custom view controllers for handling the view-specific behaviours. The image view has an Open push-button for example. Click this and the controller presents an Open Panel letting the user change the view’s image. Lake Don Pedro looks nice, but perhaps you fancy a change! The table view initialises some names, etc. Custom view controllers will add the view-specific controller behaviour.

However, the biggest missing piece: the view meta-controller itself. The project needs a class for meta-controlling view controllers.

Start simple

What is the most basic requirement? Our test application (View Controller Mark II) wants to say “load a view” given by @"CustomImageView", a string. The meta-control architecture then loads the corresponding nib, constructs an instance of CustomImageViewController and then hangs the result in a graph of meta-controllers. At any time thereafter, any object method with access to the meta-control graph can access the view controller (i.e. [vmc viewControllerForViewPath:@"CustomImageView"] where vmc means the view meta-controller) and, from there, its view, represented object and title. Note, if there were nested sub-controllers, the view-path would read @"CustomImageView.SomeOtherName". SomeOtherName stands for a nested tier of control. In this case though, requirements only need non-nested controllers. Pity.

Let’s take the NSViewController class and bolt on a meta-controller. The new class associates with one view controller (its subordinate controller) and multiple subordinate meta-controllers by name. See diagram below.

The diagram indicates unidirectional associations using directed arrows. The viewController association from meta-controller to view controller is unidirectional, in that direction. Likewise from name to subordinate meta-controller. Names are unique strings identifying lower levels of meta-control. This model forms a graph or tree: a hierarchy of named meta-controllers.

It’s a simple model. Note, no reverse navigation from view controller to meta-controller. Hence no need for new NSViewController subclasses. The hierarchy lives outside the pre-existing view controller framework. Of course, the model supports view controller subclasses, but not for maintaining the meta-control graph.

You might have noticed the diamond shape at the name-end of the meta-controller association; it marks an aggregation. In fact, in this case, it marks a self-aggregation, also known as circular. Some sources say that self-aggregation does not make sense. I’m not so sure. In this instance, meta-controllers are “parts of” other meta-controllers. Aggregation is not a precise concept. Suffices to say there is a strong association between meta-controller parts.

Overlaying some methods

Of course, the diagram above shows RRViewMetaController without methods. So not a very useful class, at present.

Adding methods can prove challenging. It takes judgement, experience, skill, even art. There is never one “right” way. It’s almost like pouring custard over your pudding! You don’t want a thick blob at one side; a smooth even coating works best. Yes, I know, that carries it too far. But I’m sure you know what I mean: behaviour needs judicious placement within a class structure. Methods are little packets of behaviour. Placing them, naming them is as important as implementing them, because in the long run mistakes can have an important impact on maintenance. When the custard goes cold, it gets harder to spread. I’ll shut up about custard now (I must be hungry though I just ate).

Meta-control will need methods for the following function groups.

Initialising and de-allocating

The usual housekeeping work. * -init initialises an instance * -dealloc de-allocates an instance

Accessing properties

Every meta-controller controls a subordinate view controller. Other objects need access to this. * -viewController answers the associated view controller * -view answers the view controller’s view

Adding and removing from super-views

Every meta-controller directly and indirectly manages a triplet: a view controller, a nib and a view hierarchy. The view hierarchy does not automatically enter any given window undirected. The design requires methods for adding and removing the view, along with any sub-views. * -addToSuperview:aSuperview adds the meta-controlled view to aSuperview * -removeFromSuperview removes the meta-controlled view from its super-view

Naming and removing meta-controllers

Accessing meta-controllers’ names, removing them if necessary. * -namesOfMetaControllers gives all the names of the subordinate meta-controllers * -nameOfMetaController:aMetaController answers the name of aMetaController * -removeMetaController:aMetaController removes aMetaController by identity

Resolving and removing view paths

Given view-path strings, meta-controller instances answer corresponding controllers, loading view controllers and views as necessary. * -resolveViewPath:aViewPath resolves a view path answering an array of meta-controllers * -removeViewPath:aViewPath removes the meta-controller identified by aViewPath * -viewMetaControllerForViewPath:aViewPath answers the view meta-controller identified by aViewPath * -viewControllerForViewPath:aViewPath shortcuts the view controller accessor, answering a view controller for a given view path

Adding these to the class diagram:

Notice the method signatures reflect C++ and Java language styling. Method name comes before arguments and arguments appear in parentheses. Of course, in real life, Objective-C intermingles signature and arguments. Hence you see addToSuperview: as the name, with aSuperView : NSView as the argument-and-type pair. I’ve also skipped the pointer asterisk as implied. I hope it makes sense. Note also, plus prefix means public in this context, not a class method.

Interface, RRViewMetaController.h

Turning the requirements into Objective-C:

#import <AppKit/AppKit.h>

// Meta refers to a position beyond, of a higher or second-order kind. Thus, a
// meta-controller controls controllers! Hence, the view meta-controller class
// controls view controllers.
// Notice, the class does not implement a back-reference to the parent
// meta-controller. True, even though they form a tree. View paths specify leaf
// nodes. The class resolves the path by walking from root to leaf, recording
// the journey at each step. This approach obviates references to parent nodes.
// Effectively, the graph of meta-controllers "hovers" above the view
// controllers, retaining them and their view hierarchies. You address leaves on
// the meta-graph using view paths where the names of the path elements
// correspond to the nib names. That implies that you can have the same nib by
// the same name. You can but not at the same tier in the hierarchy unless you
// use a colon to add more context to the name without adding to the nib
// name. In short, name strings of the form myNib:blahBlah loads the nib file
// named myNib but uses myNib:blahBlah to uniquely identify the meta-controller
// within the graph.
@interface RRViewMetaController : NSObject
{
    NSMutableDictionary *metaControllersByName;
    NSViewController *viewController;
}

@property(retain) NSViewController *viewController;

//------------------------------------------------- Initialisers & De-Allocators

- (void)releaseViewController;
    // Releases the associated view controller and by implication also removes
    // the view controller's view from its super-view.

//-------------------------------------------------------------------- Accessors

- (NSView *)view;
    // Every meta-controller stands in the shadow of a view controller, an
    // instance of NSViewController. Every view controller associates with a
    // view. The meta-controller's -view method (this method) answers the
    // view. If not already loaded from its nib, this method also indirectly
    // does so.

//---------------------------------------- Adding to & Removing from Super-Views

- (void)addToSuperview:(NSView *)superview;
    // Adds the view linked to this meta-controller (via the view controller) to
    // the given super-view. The controlled sub-view's frame becomes equal to
    // the super-view's bounds. This is a simple approach to layout.

- (void)removeFromSuperview;
    // Removes the meta-controlled view from its super-view, but without
    // releasing the view controller.

//------------------------------------------- Naming & Removing Meta-Controllers

- (NSArray *)namesOfMetaControllers;
    // Answers all the unique names of the subordinate meta-controllers.

- (NSString *)nameOfMetaController:(RRViewMetaController *)metaController;
    // Answers the name of the given meta-controller. Assumes that the given
    // object is a direct child node of the receiving meta-controller. Returns
    // nil of not. Names are unique. Meta-controllers can only have one for each
    // subordinate meta-controller.

- (void)removeMetaController:(RRViewMetaController *)metaController;
    // Removes a meta-controller by its identity; the argument specifies a
    // meta-controller identity by pointer. Take care to retain the
    // meta-controller if necessary before removing.

//---------------------------------------------- Resolving & Removing View Paths

- (NSArray *)resolveViewPath:(NSString *)viewPath;
    // Resolves a given view path answering an array of view
    // meta-controllers. The method automatically constructs any missing
    // controller elements, if any. The given path applies relatively with
    // respect to the receiver. If the path specifies sub-controllers, resolving
    // continues by recursion. Note that resolving a view path constructs the
    // corresponding meta-controllers but does not automatically load the
    // corresponding views. Accessing a view controller's view method loads the
    // view.

- (void)removeViewPath:(NSString *)viewPath;
    // Removes the meta-controller identified by the given
    // view-path. Presumably, the application has already resolved the
    // path. Otherwise, resolving herein will first construct the path before
    // removing it. The path specifies a leaf in the meta-control
    // graph. Removing releases and removes the leaf only. It does not remove
    // any elements in-between the removed leaf and the root.

- (RRViewMetaController *)viewMetaControllerForViewPath:(NSString *)viewPath;
    // Answers the view meta-controller for a given view-path. It's a
    // convenience method, equivalent to resolving the path, then picking the
    // leaf node equal to the last element resolved.

- (NSViewController *)viewControllerForViewPath:(NSString *)viewPath;
    // Handy shortcut for asking for a meta-controller by view-path then asking
    // the meta-controller for its view controller.

@end

I’ve included comments describing the class and its methods. They might be worth reading. I know you’d rather skip. Anyway, notice the method groups.

Resolving view paths, that’s the key method. Given a view-path string, it answers an array of meta-controllers, one for each name appearing in the path. For example, given a string such as @"a.b.c", the -resolveViewPath: instance method walks the meta-controller graph starting at a, then subordinate b, followed finally by c. Resolving constructs the graph along the way. Dots in the view-path string delimit meta-controller names. Names must be unique and correspond to nib names. Loading a looks for a nib named @"a". You reuse nibs using a colon in the name, e.g. view-path of @"a:1" and @"a:2" resolve to the same nib (a) but have unique meta-controller names. Everything after the colon belongs to the unique meta-controller name. Everything before identifies the nib.

In the next article on this subject, I’ll deal with the implementation.

Organising view controllers

Fri, 29 Aug 2008 01:37:41 -0700

Understanding how individual view controllers work is one thing. Organising them is another. Applications typically deal with multiple view controllers. Views can change dynamically. Hence view controllers need dynamic capabilities.

This article presents an idea for organising view controllers within an application. Design goals include: flexibility, simplicity, convention over configuration.

View paths

The design idea centres around the concept of a view path. Paths are a ubiquitous paradigm. You find them in file systems, graphs, in Cocoa’s key-value coding, in X-Path querying, the list goes on. Graph is the underlying structure (directed acyclic, to be technical). Paths express a route between two points in the graph, from the root to some leaf node for example.

View hierarchies form such a nested model, so applying paths naturally expresses the intrinsic nested construct. Simple notion then: View hierarchy equals graph, use path to navigate it. Stay with me. You’ll see where I’m going.

Meta-control

Meta is a funny word. “It’s from the Greek,” in a Greek accent! Here it refers to things beyond or above, a higher order. View controllers control their views, yes. But what controllers the controller? Answer: some form a meta-control, controlling the control. It makes the head spin. Yet necessary. Every application, large and small, requires some form of overarching control, or, in object terms, some framework on which to overlay the flesh of behaviour.

I’m being a little cryptic. Are you following me?

So. Let’s assume: one view, one view controller. “View” here refers to a view sub-hierarchy, one that you load from a nib; so it might comprise many sub-views but has one container view. Our application wants to manage a hierarchy of such controller-view-nib triplets.

Tempting to directly overlay a tree structure by sub-classing a new view controller class, adding an array of view sub-controllers. A simple approach, but limiting. It forces the view controllers into a strict hierarchy. This does not fit the requirement for flexibility. It inserts the meta-controlling layer into the low-order control layer. A flexible solution really needs a second-order of controlling existing above the first rather than intermingled.

Show me the money

So far, we’ve been living in the abstract. Reality doesn’t live there. Let’s get practical. Take an example.

Start an experiment. Take Apple’s ViewController sample code (screen shot below) as the reference point. Let’s try to improve it. Can we reduce the number of lines? Make it easier to understand, maintain, expand? Seems like a tall order. Too tall?

As you see, there’s a large custom view in the upper portion of the window. Clicking the pop-up button presents you with four choices. The choice switches the custom view. Four different sets of view controller, nib and sub-view switch in and out accordingly.

Lies, lies and statistics

Improvement is hard to measure. Better is a subjective term. My better and your better might not be the same better. So for the experiment, we will add some objectivity. Start by measuring the existing ViewController project.

Basic software metric: lines of source code (SLOC).

The cloc tool reports:

-------------------------------------------------------------------------------
Language          files     blank   comment      code    scale   3rd gen. equiv
-------------------------------------------------------------------------------
Objective C          11       165       502       229 x   2.96 =         677.84
-------------------------------------------------------------------------------
SUM:                 11       165       502       229 x   2.96 =         677.84
-------------------------------------------------------------------------------

229 lines of code in total. I’m running cloc from the ViewController project directory and passing arguments ”--force-lang="Objective C",h .” meaning that source files with h classify as Objective C; dot refers to the current working directory, of course.

Adding the --by-file option produces some interesting statistics too.

-------------------------------------------------------------------------------
File                        blank   comment      code    scale   3rd gen. equiv
-------------------------------------------------------------------------------
./MyWindowController.m         30        64        92 x   2.96 =         272.32
./CustomImageViewController.m  17        58        37 x   2.96 =         109.52
./AppDelegate.m                17        50        24 x   2.96 =          71.04
./CustomVideoViewController.m  15        46        18 x   2.96 =          53.28
./CustomTableViewController.m  13        44        17 x   2.96 =          50.32
./MyWindowController.h         13        40         9 x   2.96 =          26.64
./CustomImageViewController.h  13        40         8 x   2.96 =          23.68
./AppDelegate.h                12        40         7 x   2.96 =          20.72
./CustomVideoViewController.h  12        40         6 x   2.96 =          17.76
./CustomTableViewController.h  12        40         6 x   2.96 =          17.76
./main.m                       11        40         5 x   2.96 =          14.80
-------------------------------------------------------------------------------
SUM:                          165       502       229 x   2.96 =         677.84
-------------------------------------------------------------------------------

Here we see that most of the complexity (in lines-of-code terms anyway) resides in the window controller implementation: 92 lines of code, top of the list. That’s likely where one might expect greater complexity. But on the other hand, shouldn’t the view controller paradigm mitigate window controller complexity to some degree. We shall see.

Cash register

Let’s also use David A. Wheeler’s SLOCCount tool. It’s easy to install using MacPorts. Just enter sudo port install sloccount in Terminal. After installing, entering ”sloccount .” in the ViewController project directory gives:

Total Physical Source Lines of Code (SLOC)                = 246
Development Effort Estimate, Person-Years (Person-Months) = 0.05 (0.55)
 (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months)                         = 0.17 (1.99)
 (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule)  = 0.28
Total Estimated Cost to Develop                           = $ 6,196
 (average salary = $56,286/year, overhead = 2.40).

Phew! 246 lines costing 6,000 dollars. Interesting that the number of lines do not agree. SLOCCount counts some of the comment lines. Big question is: can our experiment save bucks?

Let the games begin

Start with a new project. Use the Cocoa Application template: not document based, without Core Data. I’ll call it View Controller Mark II! That sounds Spitfire-esque. Excuse the appeal to glamour and (apparent) adventure. Just hope it doesn’t crash!

The new empty project provides just 5 lines of code in main.m. We have a blank MainMenu.xib too; just the main menu and main window. No application delegate, no window controller. Yet.

Rather than re-create the nibs, the experiment will just copy them from Apple’s sample code verbatim. That way, the comparison will be like-for-like. Only Objective-C code will change. Nothing else. So, delete MainMenu.xib; MainMenu.nib will replace it. Add to Resources: four Custom View nibs, MainMenu and TestWindow nibs. Add with Copy enabled. The custom video view uses QTMovieView so the project needs QTKit framework adding too. Add Quartz while we’re at it; the camera view uses Quartz’s QCView. The Lake Don Pedro JPEG image and QuickTime movie needs adding, finally.

Build already? No. It cannot run yet. Missing AppDelegate for one thing. After launch, the application delegate needs to create a new window controller (a custom one) and initialise it using the TestWindow nib.

So, we sub-class NSWindowController as MyWindowController. Add the necessary instance variables, myTargetView and viewController; add the (IBAction)viewChoicePopupAction:(id)sender instance method. That makes the project build and run, though do nothing remarkable of course.

By the time building and running reaches an error-free level of success, application delegate and window controller sources appear as follows.

Barebones application delegate

#import <Cocoa/Cocoa.h>

@class MyWindowController;

@interface AppDelegate : NSObject
{
    MyWindowController *myWindowController;
}
@end

It’s implementation:

#import "AppDelegate.h"
#import "MyWindowController.h"

@implementation AppDelegate

- (IBAction)newDocument:(id)sender
{
    // The MainMenu nib's main menu sends this action when you select File New,
    // or Command+N. The menu item target is the first responder. This falls
    // through the Responder Chain until it finally hits AppDelegate. Answer by
    // constructing the window controller, if not already existing, and show it.
    if (myWindowController == nil)
        myWindowController = [[MyWindowController alloc] initWithWindowNibName:@"TestWindow"];
    [myWindowController showWindow:self];
}

- (void)applicationDidFinishLaunching:(NSNotification *)notification
{
    // By virtue of AppDelegate being the application's delegate, it
    // automatically receives application notifications. How kind. Respond by
    // sending the -newDocument: action, just as if the user pressed Command+N.
    [self newDocument:self];
}

@end

Barebones window controller

#import <Cocoa/Cocoa.h>

@interface MyWindowController : NSWindowController
{
    IBOutlet NSView *myTargetView;
    NSViewController *viewController;
        // TestWindow.nib contains bindings to this instance variable's "title"
        // and "representedObject" property. Rather than naming it
        // myCustomViewController, as does the Apple sample code, name the
        // instance variable by its KVC key. Doing so saves an accessor.
}

- (IBAction)viewChoicePopupAction:(id)sender;

@end

And its implementation:

#import "MyWindowController.h"

@implementation MyWindowController

- (IBAction)viewChoicePopupAction:(id)sender
{
    // TestWindow nib connects action -viewChoicePopupAction: to the window
    // controller. MyWindowController is the nib's owner. The
    // Image-Table-Video-Camera pop-up button sends this action to the nib
    // owner. The window controller responds by switching view and view
    // controller.
}

@end

At this point, then, the project has 40 lines of source code. Where to go from here?

Switching view controllers

That’s the main point. When the user selects one of the four choices available in the pop-up button (Image, Table, Video or iSight Camera) the custom view responds by switching to the corresponding view alternative. As regards complexity, meaning breadth and depth of view controller nesting, the requirement is very trivial. Breadth of four, depth of one. It’s hardly worth having any meta-control. But you have to start somewhere. Here’s as good a place as any.

To be continued.

View controllers

Tue, 26 Aug 2008 12:30:00 -0700

NSViewController. It’s an enigmatic class.

Exactly what is it? When should it be used? Apple’s documentation does not paint a clear picture. What is there to glean from its interface, implementation as well as others’ work on this subject?

Class diagram

The class belongs to the AppKit framework. Its simplified UML class diagram looks like this:

It inherits from NSResponder, associates with a bundle, a view and some other represented object. That’s what the diagram says, in not so many words. Really though, the bundle association amounts to a nib association using a given nib name.

Title

What does the title attribute represent? An interesting question. Apple’s documentation proves most enigmatic. Described as the ‘localized title of the receiver’s view,’ the discussion continues:

“NSViewController does not use the title property directly. This property is here because so many anticipated uses of this class will involve letting the user choose among multiple named views using a pulldown menu or some other user interface.”

Exactly what ‘anticipated uses’ refers to, the reader is left to wonder! The warm feeling of anticipation remains.

Usage

According to documentation, the view controller becomes the nib’s owner. Its view outlet connects to the nib’s primary view. Using Interface Builder’s Cocoa View template gives you such a nib. The class of File’s Owner defaults to NSObject. Change this to NSViewController and link its view outlet to Custom View—the NSView already set-up by the template. (Makes you wonder why the View template does not automatically make the file owner’s class equal to NSViewController with its view outlet pointing at the custom view.) Via the nib’s owner, the controller, views and controls within the nib can bind to some other key-value coding and observing (KVC and KVO) compliant object for key-path “representedObject” applied to the controller, i.e. nib owner.

Does that make any sense? It assumes some grasp of nib and key-value paradigms.

In simple terms, NSViewController ties together a view and a model, the represented object. Isn’t that exactly what we’d expect from a controller in MVC architecture? Superficially, the class is analogous to NSWindowController. What window controller does for window and document, view controller does for view and represented object: view and model, plus controller. Window controller has -loadWindow behaviour for loading the window from its nib. View controller analogously carries the -loadView method. It almost makes you wonder if the two classes should really be one and the same; or belong to the same super-class, an abstract window-view controller.

Exemplars

Studying examples is a good way to grasp new concepts. A picture paints a thousand words. Samples are software engineering pictures. Where best to find good paintings? Where better than Apple? Surprisingly though, Apple’s sample code contains only a few examples that use NSViewController. Why is that surprising? Anyway, here they are: - CrossEvents from 2007 subclasses the view controller. It demonstrates sending Carbon events and NSNotifications between Carbon and Cocoa. View controller’s usage is not the primary focus. It’s used just as a tool for loading a nib-based NSView. Not a complicated example, but helps to show that view controllers have their trivial use. - HIView-NSView—same can be said. This sample was upgraded in May 2007 to use NSViewController. - IconCollection—same again, not a direct demonstration of NSViewController usage per se. NSCollectionView’s use as an icon collection viewer is the main purpose. Yet it combines window and view controllers together with bindings. - SourceView is an interesting sample. Relatively complex, it combines custom view-controller subclasses, as well as custom window controller. - ViewController directly demonstrates view controlling. It has three custom view controllers, one each for image, table and video viewing. The sample also includes a window controller. So interesting to see how window and view controllers co-ordinate.

Are there any more? I’ve made a thorough search but no others at Apple Developer. Third-party developer sources may include examples, of course.

There is one intriguing fact about the Apple samples: only ViewController uses the represented object and only to store a integer representing the number of subviews present in the view controller’s view. So not really useful.

Responder and responder chain

NSViewController is a kind of NSResponder.

What is a responder anyway? If, like me, you generally ignore things that work right until they break, you’ll likely know little about the “responder chain,” how it works and why; simply because it normally doesn’t matter. The framework takes care of such details. Why concern yourself?

In this case, the answer is simple. NSViewController does not automatically join the responder chain, as does NSWindowController. If you want your view controllers in the chain, you must put them there yourself.

Respond to what and how?

The simplified story: responders (subclasses of NSResponder) link up together in a chain. When event or action messages fire, Apple’s Application Kit invokes the responders one-by-one until it finds a response. Events and actions correspond to keyboard presses, mouse clicks, scroll wheels, tablet events, menu items, help requests and such. Interactive inputs, by another name. Responders include windows, views and application objects, window and view controllers also.

That’s a very simplified version. See Apple’s Cocoa Event-Handling Guide for the gross details. Read the section entitled The Responder Chain.

In reality, the responder chain amounts to just a singly-linked list of NSResponder objects. Each responder encapsulates a nextResponder reference to the next responder in the chain, or nil if none. No next responder indicates the end of the chain. Every NSWindow has a first responder marking the start of the chain. However, the starting point varies; exact route varies too. Multiple responder chains exist at any one time, and which to choose depends on the type of message, whether or not NSWindowController is involved, and whether document or non-document architecture applies. So not exactly straightforward!

In all cases though, first responder is always first. Then comes the view hierarchy followed by the enclosing NSWindow and its delegate.

Question arises: where in the chain do view controllers belong? For instance, they could sit between the view hierarchy and its window. Alternatively, behind each view so that the view responds first followed immediately by its view controller. In practise, applications may need custom configurations of responders, possibly even dynamic.

Permutation class

Fri, 22 Aug 2008 02:22:00 -0700

Permutations! I’ve hit this issue quite a number of times in my life: at university, at work. It’s not unusual to encounter problems where it’s very handy to able to iterate all possible permutations of something. And catch is: standard libraries sometimes do not offer any help. The engineer is left to tackle the problem by him- or herself.

The pragmatic answer typically involves digging in some favourite tome. Something like Numerical Recipes, or The Algorithm Design Manual. All very handy. And perfect if the implementations match your language and environment requirements. Otherwise you’re left to wade through the theory, or try to port. To understand or to port? That is the question. If, like me, you find yourself choosing between time pressures and interest, you normally end up porting.

It’s always handy if someone else has already been through the pain and made the gain for you. Quickly digging around the Internet (roughly translated means Googling) might find what you want. But not always exactly. Cutting a long story short, this article tries to fill the gap between permutations and Objective-C.

Already done

Ah, but work already done? Check out Marko Riedel’s GNUstep cookbook. Marko publishes some Objective-C code for a permutation enumerator. See section Counting II: Permutation enumerator.

I have a problem with it though. It’s sloppy. Call me a fusspot but I like quality code. Marco’s work while may be functional bears the hallmarks of cobbling: a done flag, zone-allocated array of ints, no testing for allocation failure. Do I ask too much? Maybe.

So not already out there! Until now.

Ruby Tuesday

I’m a fan of Ruby (and Rails). Ruby equips a useful permutation enumerator class written by Florian Frank. It has a number of admirable qualities, including simplicity. I like classes with low amounts of internal state. They have fewer bugs in general—maintenance and comprehension easier. True, it has some more advanced features that most would not require. Still, these can be added later when needs arise.

Only one strange thing about Florien’s implementation: the @last instance variable gets assigned by the initialiser but then ignored. Apart from its getter method, other instance methods re-compute last by asking for the size factorial. Strange. Never mind, our implementation will fix that oddity.

So here’s the mission: develop an Objective-C permutation enumerator class based on Florian’s Ruby implementation, which is itself based on algorithms presented in Steve Skiena’s The Algorithm Design Manual! Imitation is the sincerest form of flattery. It gives the outcome a satisfactory pedigree. It’s also more ideal than most porting source-target pairs since their are many conceptual similarities between Objective-C and Ruby, i.e. grounded in C, aspiring to Smalltalk.

Another advantage of this approach is that getting to mental grips with the underlying algorithm becomes unnecessary. Lazy bones!

Test-driven approach

As is good practise, let’s start with a test. It’s the agile way. It will mark the development iterations beginning and end: begin with the test fails, end when it succeeds.

Let’s take a very simple test: permuting an array of 3 elements. Our test wants to know how many alternative permutations exist. For arguments sake, the three elements are letters a, b and c. If we had an enumerator called say RRPermutation that conforms to the NSEnumerator protocol, our test would output the permutations using the code below.

#import <Foundation/Foundation.h>

#import <RRFoundation/RRPermutation.h>

int main(int argc, char *argv[])
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    RRPermutation *perm = [[RRPermutation alloc] initWithSize:3];
    for (id indices in perm)
    {
        // Project the indices into the test string "abc". Objective-C does not
        // have a "project" method, as such. We'll need to do this part by hand.
        NSString *s = @"";
        for (id i in indices)
        {
            s = [s stringByAppendingString:[@"abc" substringWithRange:NSMakeRange([i unsignedIntegerValue], 1)]];
        }
        NSLog(@"%@", s);
    }
    [perm release];
    [pool drain];
    return 0;
}

Note! The test code takes permutation values as indices not values.

This is important. It means that permutation enumeration is value-type indifferent. The design and implementation does not want to focus on one particular type of value, e.g. string or number. Rather, enumeration of permutation should be generic.

Hence, the enumeration outputs indices. You then apply (or project, in Ruby terms) the indices to whatever values you want. That’s neutral. That’s good. Otherwise, we’re looking at duplicate implementations for different types, since Objective-C types do not all have first-class status albeit they may have object wrappers. This approach however answers all requirements, including projecting into non-object sequences such as C arrays or plain C strings.

Test tool in hand. What next?

Interface

The preceding test case employs just two interface methods,

the initialiser, initWithSize: and
the iteration method, nextObject.

Of course, these aren’t the only methods necessary. They are only the permuting public interface. Add a designated initialiser, a set of accessors and some internals. Add a splash of instance variables (size and rank). This is what you get: listing of RRPermutation.h below.

#import <Foundation/Foundation.h>

@interface RRPermutation : NSEnumerator
{
    NSUInteger size, rank;
}

- (id)initWithSize:(NSUInteger)aSize rank:(NSUInteger)aRank;
- (id)initWithSize:(NSUInteger)aSize;

- (NSUInteger)size;
- (NSUInteger)rank;
- (NSUInteger)last;

- (void)setRank:(NSUInteger)newRank;
    // Rank ranges from 0 to factorial of size, less one, i.e. last. Use
    // setRank:0 to reset a permutation enumerator.

- (id)nextObject;
    // Send nextObject repeatedly to get the next array of permutation
    // indices. Answers nil after the last. Note that you cannot reset the
    // enumeration using the enumerator interface, although permutation
    // internals allow it.

// Following methods are generally for internal use and might be considered
// private. Nevertheless, feel free to access them for testing and debugging or
// other purposes if you wish. They are query methods, operations without side
// effects on enumerator state. So no pitfalls to avoid.

- (NSArray *)unrankIndices:(NSUInteger)m;

@end

Implementation #1

Listing of RRPermutation.m as follows.

#import "RRPermutation.h"

#import "RRFactorial.h"

@implementation RRPermutation

// designated initialiser
- (id)initWithSize:(NSUInteger)aSize rank:(NSUInteger)aRank
{
    if ((self = [super init]))
    {
        size = aSize;
        rank = aRank;
        // Rank steps by one, starting at zero, ending at RRFactorial(size) - 1;
        // no need to store this value because RRFactorial does all the storing
        // for us in its secret cache.
    }
    return self;
}

- (id)initWithSize:(NSUInteger)aSize
{
    return [self initWithSize:aSize rank:0];
}

#pragma mark Accessors

- (NSUInteger)size
{
    return size;
}

- (NSUInteger)rank
{
    return rank;
}

- (NSUInteger)last
{
    return RRFactorial(size) - 1;
}

- (void)setRank:(NSUInteger)newRank
{
    rank = newRank;
}

#pragma mark Enumerator

- (id)nextObject
{
    return rank < RRFactorial(size) ? [self unrankIndices:rank++] : nil;
}

- (NSArray *)unrankIndices:(NSUInteger)m
{
    NSMutableArray *result = [NSMutableArray arrayWithCapacity:size];
    NSUInteger i;
    for (i = 0; i < size; i++)
    {
        [result addObject:[NSNumber numberWithUnsignedInteger:0]];
    }
    for (i = 0; i < size; i++)
    {
        NSUInteger f = RRFactorial(i);
        NSUInteger x = m % (f * (i + 1));
        m -= x;
        x /= f;
        [result replaceObjectAtIndex:size - i - 1 withObject:[NSNumber numberWithUnsignedInteger:x]];
        // At this point, Florian decrements x in preparation for the following
        // comparisons with values from the result array. This assumes that x
        // can be negative however. In our case, it cannot because we implement
        // indices using NSUInteger (unsigned) as is the Foundation framework's
        // wont for array indices. To abviate the decrement, the subsequent test
        // becomes greater-than-or-equal-to instead of greater-than. Problem
        // solved, and simplifies the code too.
        // x -= 1;
        NSUInteger j;
        for (j = size - i; j < size; j++)
        {
            NSUInteger y = [[result objectAtIndex:j] unsignedIntegerValue];
            if (y >= x)
            {
                [result replaceObjectAtIndex:j withObject:[NSNumber numberWithUnsignedInteger:y + 1]];
            }
        }
    }
    return result;
}

@end

The size attribute describes the size of the permutation required: 3 for permutations of three elements, 7 for seven, etc. During enumeration, the rank attribute ranges in the integer interval [0, size! - 1] where size! refers to the factorial of size.

Testing

Applying the testing tool produces:

abc
acb
bac
bca
cab
cba

Exactly right!

Projecting indices

Taking a look again at the test code, the loop for projecting the resulting permutation indices needs simplifying. Does it not? It’s likely something that will be needed time and again, especially when using permutations. It’s a loop. Each iteration takes the next index (an NSNumber) and looks up an object from an array of values. The indexed elements combine to form a new array. Project indices! It needs a new NSArray method, like this:

- (NSArray *)projectIndices:(NSArray *)indices
{
    NSMutableArray *result = [NSMutableArray arrayWithCapacity:[indices count]];
    for (NSNumber *i in indices)
    {
        [result addObject:[self objectAtIndex:[i unsignedIntegerValue]]];
    }
    return result;
}

Using this, adding it to an Objective-C category applied to NSArray, lets the test case simplify to:

        NSLog(@"%@", [[abc projectIndices:indices] componentsJoinedByString:@","]);

This replaces the test’s inner loop. Variable abc is an NSArray pointer equal to the array given by [NSArray arrayWithObjects:@"a", @"b", @"c", nil].

Niggles

Call me fussy again, but there is a notable weakness. The implementation of unrankIndices uses a mutable array of NSNumber objects. Yet, the implementation really only requires a small fixed array of NSUIntegers. It might be more efficient to generate the array of unsigned integers first using a stack-allocated buffer, using alloca. Then, before returning the result, convert the raw C array of integers to an NSArray of NSNumber objects.

It’s a small difference. But is it worthwhile?

Download sources

MIT-licensed sources here.

Factorial function in Objective-C

Thu, 21 Aug 2008 04:04:00 -0700

Factorial, denoted by n! and defined as the product of all positive integers less than or equal to n.

How to implement such a function in Objective-C? It needs to be fast and, of course, accurate. Needless to say it will have limitations. Factorials very quickly become large. The implementation will use NSUInteger as the numeric type. This type’s size depends on architecture, 32 or 64 bit. Hence its ability to carry factorials will vary. Whatever the case, whatever architectural limitations and capabilities, the implementation will reside within them. No other choice!

Interface

The requirement is purely functional. No class required.

NSUInteger RRFactorial(NSUInteger n);

So very simple. One NSUInteger in, another out. Factorials deal with positive integers only. Hence U for unsigned integer.

Test case

The test case iterates all the integers n between 0 and 19 inclusive and logs the value of n and RRFactorial(n).

#import <RRFoundation/RRFactorial.h>

int main(int argc, char *argv[])
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    NSUInteger n;
    for (n = 0; n < 20; n++)
    {
        NSLog(@"%lu %lu", (unsigned long)n, (unsigned long)RRFactorial(n));
    }
    [pool drain];
    return 0;
}

At first, the test fails successfully! It even fails to link because no implementation for the function currently exists.

Implementation

General factorial implementation is extremely simple: given n, just multiply together every integer between 1 and n inclusive. Nothing difficult there.

However, the implementation herein will aim for speed by caching the results dynamically. So having already computed the factorial for any given integer, the answer just becomes a look-up transformation; no calculations required. Space is not at issue. Such a look-up implementation will not usually exceed say 20. After that, answers become silly numbers; e.g. 50! approximately equals 3*pow(10,64). That’s a pretty big number and bigger even than DBL_MAX.

Design-by-contract principles will set boundaries. Give it high values of n and don’t expect sensible answers. That’s a way of saying ‘ignore it!’

#import "RRFactorial.h"

NSUInteger RRFactorial(NSUInteger n)
{
    // Cache the factorials. Use NSZoneMalloc, Realloc and Free for memory management. For initial revisions, ignore memory leaks at application exit.
    static NSUInteger *factorials = NULL;
    static NSUInteger numberOfFactorials;
    if (factorials == NULL)
    {
        factorials = NSZoneMalloc(NSDefaultMallocZone(), sizeof(NSUInteger));
        factorials[0] = 1;
        numberOfFactorials = 1;
    }
    if (n >= numberOfFactorials)
    {
        NSUInteger *newFactorials = NSZoneRealloc(NSDefaultMallocZone(), factorials, (n + 1) * sizeof(NSUInteger));
        factorials = newFactorials;
        while (numberOfFactorials <= n)
        {
            factorials[numberOfFactorials] = numberOfFactorials * factorials[numberOfFactorials - 1];
            numberOfFactorials++;
        }
    }
    return factorials[n];
}

Testing

Executing the test case produces:

0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 1932053504
14 1278945280
15 2004310016
16 2004189184
17 4006445056
18 3396534272
19 109641728

Compare this to the factorial tableau at Wikipedia. It’s a match!

Or is it? Note deviations starting at n=13. That’s because 13! exceeds unsigned integer maximum of about 4,000 million on 32-bit platforms.

64-bit testing

Switching to pure 64-bit, by making architectures (ARCHS) equal to ppc64 plus x86_64, and rerunning the test produces a different result.

0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000

Much better. Or should I say less limited. Better is just a point of view in this case because even the 64-bit version will eventually find its limitations. Man’s got to know his limitations! (“Dirty” Harry Callahan, Magnum Force, 1973)

Failing gracefully

At present, nothing gracefully happens when n and n! reach limits of the host machine. That’s not very satisfying. Should it not stop after overflow? Nor is the fact that the function remains insensitive to memory allocation failures a source of satisfaction. Should it throw exceptions? That’s messy.

There’s another approach.

Since the factorial cache has limited size under normal conditions, why not make the cache static; its size depending on the compiler’s NSUInteger width. Once the cache is full, answer NSUIntegerMax indicating factorial out of integer range. That would solve two problems at the same time; two birds, one stone.

Compiler manifest constant __LP64__ signals 64-bit architecture. However, there is also a special NS_BUILD_32_LIKE_64 macro for making NSUInteger 64 bits wide regardless.

Updated version below. It eliminates dependence on memory allocation and obviates exception handling for allocation failure and boundary overflow. All in one fell swoop. I’ve also obfuscated variable names to make it more mathematical in nature: i for the index of the last computed factorial, f for the factorials, N for the upper inclusive boundary of n. Is that bad?

Listings

`RRFactorial.h`

#import <Foundation/Foundation.h>

NSUInteger RRFactorial(NSUInteger n);
    // Answers the factorial of n, or NSUIntegerMax if factorial exceeds
    // NSUInteger type's upper boundary. Uses Foundation framework's NSUInteger
    // type to carry factorials.

`RRFactorial.m`

#import "RRFactorial.h"

NSUInteger RRFactorial(NSUInteger n)
{
    // Use preprocessor macros to determine the maximum value of n computable
    // within the limits prescribed by NSUInteger, whose bit-width depends on
    // architecture: either 64 or 32 bits.
#if __LP64__ || NS_BUILD_32_LIKE_64
#define N 20 // 20! = 2,432,902,008,176,640,000
#else
#define N 12 // 12! = 479,001,600
#endif
    if (n > N) return NSUIntegerMax;
    static NSUInteger f[N + 1];
    static NSUInteger i = 0;
    if (i == 0)
    {
        f[0] = 1;
        i = 1;
    }
    while (i <= n)
    {
        f[i] = i * f[i - 1];
        i++;
    }
    return f[n];
}

Download sources

You can download the MIT-licensed sources here.