Author: Oasis Digital

Oasis Digital sponsors Cloud Camp St. Louis

Oasis Digital is a proud sponsor of Cloud Camp St. Louis, Dec. 9, 2009.

CloudCamp is an unconference where early adopters of Cloud Computing technologies exchange ideas. With the rapid change occurring in the industry, we need a place we can meet to share our experiences, challenges and solutions. At CloudCamp, you are encouraged you to share your thoughts in several open discussions, as we strive for the advancement of Cloud Computing. End users, IT professionals and vendors are all encouraged to participate. The event will be held at the Savvis headquarters in Town and Country, MO.

Help! My Hierarchy is Slow – Faster Hierarchies with Nested Sets

A great many applications, including many that I’ve worked on, have a hierarchy of things: of parts, of people, of organizations, etc. The way most of us represent such hierarchy is with the first thing that generally comes to mind: make each Widget have a parent Widget, with a table like so:

create table widget (widget_id int, parent_widget_id int, other_fields_here);

This representation is called an “adjacency list”, and is simple and easy. You can readily build a tool to manipulate a hierarchy stored this way. Many off the shelf visual components, for both client-side and web applications, know how to manipulate hierarchies represented this way. Some reporting tools know how to report on hierarchies represented this way.

However, for answering common questions like “who all is under person X in the hierarchy”, the adjacency list approach is unwieldy and slow.

There are various other approaches to representing a hierarchy, most of them discussed in detail in Joe Celko’s articles and books, prominently in the book Trees and Hierarchies in SQL for Smarties. If you work with SQL and hierarchies, buy this book now.

One approach Celko is especially fond of is the “nested set” representation. You can read about it online here and here.

Of course, changing an entire application to use nested sets might be a very big deal in a mature application. That’s OK; in most cases we can get much of the benefit by building a nested-sets “cache” of the share of the hierarchy, with a table like so:

create table widget_hier_cache (widget_id int, left int, right int);

Each time the hierarchy has changed, or before each time we need to run complex queries, delete the rows in this cache table and repopulate them based on the current canonical adjacency data. Celko offers SQL code in his book to do that, which could be translated to work in the stored procedure language of the DBMS at hand. But what about DBMSs that don’t offer stored procedures, such as lightweight local databases (SQLite), MySQL, etc.? The translation must be done in application code instead.

I wrote such code in Delphi a while back, in the process of getting a full understanding of this problem; I’ve cleaned it up and now offer code for download here (DelphiAdjacencyNestedSets.zip), under an open source license (MIT license – use it all you want). I tested this today with Delphi 2007 Win32, but it should work fine at least back to Delphi 7. As far as I can tell with some searching, this is the only Delphi code for translating adjacency to nested sets available on the internet. This code doesn’t know about databases – it is a module to which you feed adjacency data, and from which you get back nested set data. It includes DUnit test cases.

I’ve also put the code on github, for easy browsing and forking.

(Update in August 2007: a new version (DelphiAdjacencyNestedSets2.zip) optionally tolerates “orphan” nodes and forests. Update in January 2008: a newer version (DelphiAdjacencyNestedSets3.zip) propagates an integer value down the hierarchy; it is named Tag as a nod to the .Tag property on VCL components. Both of these newer versions were tested with Delphi 2006/2007 also.)

The essence of the translation is a depth-first traversal of the hierarchy, and of course this can be easily implemented in other languages; the Delphi code is easy to understand, so don’t be afraid to take a look even if you need some Java or C# or PHP etc. I also stumbled across this PHP nested sets implementation, which offers a set of functions to maintain (insert, update, etc.) a hierarchy stored as nested sets, rather than only translate from adjacency to nested sets.

Another useful way to represent a hierarchy for fast querying is with a transitive closure table. I’ll write this up in a future post; it turns out to be especially useful (and necessary) to make arbitrary hierarchies work in the Mondrian OLAP server.

Delphi as High Level Assembly Code?

A while back I needed to reverse the order of the 4 8-bit bytes in a 32-bit word, in some Delphi code. I worked out a way to do it with bit shifting, read the docs for a few minutes, and got something to work with AND, SHL, SHR, and some $FF constants. Later I encountered (on a usenet post which I can’t find at the moment), this implementation, which consists of some Delphi cruft around a single assembly statement:

function Swap32(aLong: Longint): Longint; assembler;
asm
BSWAP eax
end;

This is an unusual occurence: the assembly code is shorter, simpler, and more obviously correct (see this explanation of BSWAP), than the high level language implementation. Hmmm.

Take control of Delphi forms in your multimonitor application

The authors of the the VCL helpfully added multi monitor “support” a few versions back. Somewhat less helpfully, this support is very limited – it has no way to say “create form X on monitor 3”, which is a very useful thing to do in some kinds of applications – those intended to run on a multimon system in a specific configuration.

You can readily move forms around (with .Left, .Top, etc.) on to specific monitors after a Form is open, but not while it is opening (in OnShow or OnCreate), because a fine method TCustomForm.SetWindowToMonitor will jump in and undo your work.

Not surprisingly, most of the obvious methods to override to fix this, are not virtual. (An aside – I think the bias toward final methods in Delphi, C#, and some other languages, is a poor idea, and I think the guideline of “design for overriding, or prevent it” is even worse.) With some looking, I found a workaround, shown here somewhat mangled by WordPress:

private
FSetBoundsEnabled: boolean;
public
procedure SetBounds(ALeft, ATop, AWidth, AHeight: Integer); override;

…..

procedure TSomeForm.SetBounds(ALeft, ATop, AWidth, AHeight: Integer);
begin if FSetBoundsEnabled then inherited;
end;

FSetBoundsEnabled will be False by default. Sometime after your form is loaded (use a Timer or a windows message to signal this), set FSetBoundsEnabled := True then set your .Left and .Top to put your form whereever it needs to be.

Slider Control for Touch-Screen Applications

At Oasis Digital we are working on an application that will run on a touch-screen computer, and which will be used to (among other things) control an audio amplification system. There are some design considerations for touch-screen applications which are rather stark once you use the touch-screen for a few minutes:

  • A finger is much less precise than a mouse pointer – hitting small targets is hard.
  • Drag/drop operations (or grab-adjust operations) sometimes don’t start quite where you aimed.
  • Your finger blocks the point on the screen where you are pressing.
  • The concept of keyboard “focus” is moot on applications with no keyboard.

To accommodate the first two of these, we coded a prototype/example of a slider control suitable to use for audio adjustment in such an application. It has these key features:

  1. It does not matter if you click on the “handle” or on the rest of the bar – because with touch screen you won’t be able to reliably do one vs. the other.
  2. The adjustment is not immediate; there is a limit of the speed of the adjustment to produce smoother audio control. The slider handle will move down very quickly, but will move up slowly. This avoids the possibility of an accidental touch pushing the audio amplification in to feedback.

The prototype/example looks like the screenshot here:

Touchscreen Slider

… but ignore the static image, it doesn’t tell the story. To see it in action, take a look at the screencast below (also available in a WMV file, easily viewable only on Windows) or download the example program (Windows) and play with it. The source is also on github.

This example is compiled in Delphi 2007. An enhanced version of it is in a production application for a touch-screen audio control system.

 

 

Graph Visualization in Delphi

For a project at Oasis Digital, we need to show the end user a graphical representation of a graph (in the “graph theory” sense of the word). The application is written in Delphi, and in looking around I didn’t find any native Delphi components for doing that.

I did find GraphViz, and a COM Wrapper for it called WinGraphViz. Wiring the latter up to Delphi turned out to be quite easy. The minimal code to do it, for a demo app, is below. To make this compile you’ll need to import the type library for WinGraphviz.

procedure TExampleForm.DrawGraphForData(Data: string);
var
Dot: IDot;
Image: IBinaryImage;
ImageFileName: string;
begin
ImageFileName := 'c:image.gif';
Dot := CoDOT.Create;
Image := Dot.ToGIF(Data);
Image.Save(ImageFileName);
WebBrowser1.Navigate('file:///C:/image.gif');
end;

Production code would probably use a better way of getting the generated graph on to the screen. GraphViz support imagemaps, making it easy to make the notes clickable. It can draw various arrow types, node shapes, etc., and tries to lay out graphs in a readable way, without crossing lines, etc.

A trivial sample app looks like this:

Update: a correspondent pointed out that the graphic example above is a bit ugly, with non-anti-aliased lines and fonts. To resolve that, I turned to SVG; GraphViz can produce output in SVG format (among others), and the freely downloadable Adobe SVG Viewer can display them.

With slightly different code:

ImageFileName := 'c:image.svg';
Dot := CoDOT.Create;
Image := Dot.ToSVGZ(Data);
Image.Save(ImageFileName);
WebBrowser1.Navigate('file:///C:/image.svg');

We get an application with this appearance:

You can download the Delphi WinGraphViz Sample Application Source code.

Test Intensive Development in Delphi

At the 2002 Borland Conference, I presented a “Birds of a Feather” session on Test Intensive Development in Delphi. A couple of dozen people attended, in spite of the early morning time slot. Most of the attendees were new to test intensive development, though a few were experienced in it and shared useful tips.

My introductory talk and demo was adversely impacted by a technical problem with the projector and missing microphone; hopefully this slightly expanded set of slides will fill in the gaps that caused.

Download TID-Delphi-BOF-Borcon-2002.ppt

Improving Delphi Object Pascal

In a conversation between me and others in a newsgroup thread a while
back, I made some comment about not caring for the Object Pascal syntax
in some way. Someone asked:

> If you dislike Pascal so much, please explain what you like and
why.

This is a slightly more detailed answer to the question than I presented
at the time:

I actually like Delphi / OP, just not as much as I could. In case
you are interested, here are some things I wish were different:

  • I find the begin and end keywords to be needlessly verbose.
  • Control structures could have matching, non-optional blocks… like
    Modula-2 or (!) VB. if .. then .. endif would be more concise than "if
    .. then begin .. end", and make it easier to read code and prevent
    bugs. The whole begin/end thing really belies Pascal’s origin as a teaching
    language. When you write 2-page programs, it doesn’t matter if begin/end
    is verbose.
  • Case insensitivity permits sloppy coding.
  • Now that I’ve used Java quite extensively, I am really sold on garbage
    collection as a Very Good Thing for large-scale projects.
  • I wish there was a more effective structure for handling large amounts
    of code, other than the flat module structure. Java packages are nice.
  • I wish the RTTI covered everything about the class, not just published
    properties.
  • Why do we have to do:
    •   try
    try
      // yada
    except
      // yada
    end;
  finally
    // yada
  end;

    rather than

      try
    // yada
  except
    // yada
  finally
    // yada
  end;

    Borland could easily allow the latter, short and clear syntax.

The underlying point to all of this is that Object Pascal is Borland’s language;
they can do anything they want with it. The things above are within their
power to change; it’s not like that are complying with a standard.

But do I really want them to change all this? Probably not. Would I choose
OP for my code if it weren’t for the great stuff around it (the IDE, VCL,
weatlh of third party components, etc.)? Definately not.

In my opinion, the core strength of Delphi is not the language. It’s the IDE, VCL,
lightning-fast compiler, linker, and overall environment which have made it possible for Delphi to have
a vast array of available plugin components. Delphi has attracted a remarkable
number of vendors of high quality components. Using those components as well
as Delphi’s (object-oriented) core features, it is often possible to build a working solution in Delphi
much sooner than would be possible with another tool… and that is what I
like most about Delphi.

Shared-Risk Pricing for Custom Software Development

In any custom software development project, there are well-known risks:

  • The scope may be underestimated at the start.
  • The scope may increase over time (not always a bad thing – often a client discovers that additional functionality would deliver additional business value).
  • The development firm may be unable to deliver any working solution at all.
  • The project may take more time than anticipated.
  • The project may take less time than anticipated.

In a time-and-materials pricing model, the client takes most of the risk, and this is generally accepted because the client will receive most of the benefits of a successful project. Many development firms (including many very good ones) only offer time-and-materials pricing.

They do this because of the problems with the other extreme – fixed-price contracts in which an attempt is made to fully describe the software project in advance, then specify a fixed price to build it. In this model, the development firm takes most of the risk, with some unfortunate side effects:

  1. The development firm is strongly motivated to interpret software requirement as narrowly as possible, rather than in a way which maximizes the business value of the software.
  2. The development firm and its client can end up in an adversarial relationship.
  3. Arriving at a project specification and price can be very expensive and time consuming, so much so that this model is often infeasible.
  4. It can result in an overly conservative approach to software development, estimation, and design. The client might be quoted a price which covers the highest amount of time than anyone can imagine the project taking, when then becomes a self-fulfilling prophecy.

However, a key merit in the development firm taking on some of the risk, is that the development firm is in a position to affect the outcome. This suggests a compromise.

One possible compromise between these two extremes is referred to here as Shared-Risk Pricing. It works like so: a small set of core software requirements is developed for a fixed price, then the remainder of the project is billed on a time-and-materials basis. That core set of requirement is intended to demonstrate that the developers can deliver working software, encompass the efforts needed to set up development environments, ensure familiarity with tools, and show progress on any unusual/key features of the software.

The client accepts some risks: The development firm accepts others:
Scope creep risk. Risk that the firm will be unable to deliver a working solution.
Risk that the work will go faster than expected getting basic features working. Risk that the firm will spend more time than expected getting basic features working.
Some of the risk of the project taking longer then expected. Some of the risk of the project taking longer then expected.

As we start out, Oasis Digital will perform most work on an hourly / T&M basis, while looking for projects where the shared-risk model fit.