This article shows you how to deploy a stand-alone iPhone web application. In the process, we’ll also create a basic installer for any iPhone web application. To provide a working example, we’ll adapt a variation of the RedGreenYellowBlue web app described in the earlier article Building a Simple iPhone Web Application - RedGreenYellowBlue. We’ll turn our new program, rg_rotate, into a self-reliant, stand-alone application and also empower it with its own icon on the iPhone home screen. Once installed, the program can be run off-line, independently of any network connection or server-side resources. rg_rotate will show only two colors (red/green) but will conveniently change color when the iPhone is merely rotated. In portrait orientation the iPhone will shine red and in landscape it’ll show green. Tapping the screen is no longer needed to switch color.

Getting Started

To make an iPhone web application stand-alone, we need to provide up-front all the resources required for it to run independently. This means that any images, stylesheets, and scripts that are part of the structure of the program must be included in the program at the time it is installed. The easiest way to accomplish this is to convert any external URL references in img, script, link and other HTML tags into self-contained data URLs. Data URLs are a way for tags to embed their own data directly. A data URL is used as the value of a reference or location attribute within a tag. For example, an ordinary image tag <img src="some.gif"> could be transformed into something like

<img src="data:image/gif;base64,iVBORw0KGgoAAAANSUhEUg...">

The source attribute of the img tag now holds a base 64 encoding of the GIF along with a simple descriptor which specifies the protocol identifier (”data”), the appropriate mime type and subtype (”image/gif”) and the encoding method (”base64″).

All of the resources required by a stand-alone iPhone web application are encoded as data URLs. The web application is also encoded as a data URL. The encoded program is just a string of numbers and letters but it is far too long to type into the URL Bar of Mobile Safari. The challenge is how to provide the encoded program conveniently to the iPhone. The HTML viewer within the iPhone’s Mail application will not resolve a data URL, so the program cannot simply be e-mailed in a link to the iPhone. Mobile Safari, however, fully supports data URLs. A straightforward solution therefore is to provision an HTML page with a link that contains the complete, encoded program. This HTML page can be dynamically generated or provided statically. A dynamic strategy is quite flexible and can easily support an interface for uploading associated resources such as scripts, icons, buttons, and HTML fragments. A generator could then assemble the parts and return a complete, encoded result in a page for Safari to load as a bookmark. Once loaded into a bookmark, the stand-alone program executes independently from where it was initially installed as well as independently of any specific network connection.

Our Approach

For the sake of simplicity, however, our approach in this article will be to build a static HTML page that incorporates the target web application program source and the resources it requires. In our simple example, we will supply two external files: an image file that will be used as the home screen icon and the JavaScript/HTML web application itself. Both files will be converted to data URLs. First, the image file will be encoded into base 64 and embedded into the web application within a link tag. Then, perhaps surprisingly, the web application will be converted to a data URL as well. The data URL of the encoded program is incorporated into a provisioning web page which will be provided to Mobile Safari running on the iPhone. Any web server that is accessible to your iPhone can host the static HTML provisioning page needed by Safari. Mobile Safari can then be instructed to install your program into a bookmark along with its embedded home screen icon. Note that this solution avoids depending on a proprietary application like iTunes to synchronize bookmarks.

Installation Steps

In detail, the steps we will accomplish are as follows.

1. Identify files that need to be encoded into base 64. In our example, these are rg_rotate_touch_icon.png, containing the apple-touch-icon shortcut icon and rg_rotate.html, containing the JavaScript/HTML web application we want to provision.

2. Encode rg_rotate_touch_icon.png into a base 64 representation. This can be accomplished in a variety of ways. Linux distributions, including Ubuntu and Fedora, have a base64 command line utility. So

   echo "data:image/png;base64,`/usr/bin/base64 -w 0 rg_rotate_touch_icon.png`" > \ rg_rotate_touch_icon.b64

   creates rg_rotate_touch_icon.b64 as a fully specified data URL that will become the apple-touch-icon resource. The “-w 0” argument to base64 disables default line wrapping. Turning off line wrapping is not strictly necessary but is convenient for handling the encoded image as a single element.

   On Linux as well as other systems, Ruby or Perl can provide a cross-platform capability. The Ruby version would be

   ruby -e 'print %{data:image/png;base64,#{[ARGF.read].pack("m").gsub("\n","")}\n}' \ rg_rotate_touch_icon.png > rg_rotate_touch_icon.b64

   where pack("m") base 64 encodes its Array target element and gsub("\n","") removes line wrapping (Ruby 1.9+ allows m0 as pack’s argument to remove line wrap).

3. Install the base 64 encoded image in the web application file, rg_rotate.html. Copy and paste the content of the file created in Step 2, rg_rotate_touch_icon.b64, into the href attribute of the link tag that identifies the Apple touch icon to Safari. This link tag appears after the opening head tag of the web application file, rg_rotate.html:

   <link rel="apple-touch-icon" href="[copy content of rg_rotate_touch_icon.b64 here]" />

4. Encode rg_rotate.html into base 64:

   echo "data:text/html;charset=utf-8;base64,`/usr/bin/base64 -w 0 rg_rotate.html`" > rg_rotate_html.b64

   In Ruby,

   ruby -e 'print %{data:text/html;charset=utf-8;base64,#{[ARGF.read].pack("m").gsub("\n","")}\n}' rg_rotate.html > rg_rotate_html.b64

   which encodes the entire web application, including any resources embedded as data URLs, as a data URL.

5. Install the base 64 encoded web application in the application installer file, rg_rotate_installer.html. The source for rg_rotate_installer.html is shown in Listing 3. Copy and paste the content of the file created in Step 4, rg_rotate_html.b64, into the href attribute of the a anchor tag that will be used to install the data URL into the URL Bar on Mobile Safari. For example:

   <a href="[copy contents of rg_rotate_html.b64 here]">INSTALL RG-ROTATE</a>



Figure 1: Installation Web Page

6. Provision the installation web page. Using a local or remote Web server, e.g, Apache, place the file rg_rotate_installer.html in a location that Mobile Safari on the iPhone can navigate to. A screen similar to Figure 1 will be displayed. Follow the installation steps shown. In the second step of Figure 1, when the “+” key on the iPhone Button Bar is pressed a menu rolls up. Select the menu item “Add to Home Screen”: a dialog screen, “Add to Home”, is activated. The application icon (encoded in Step 2 above) should appear on this dialog screen. Notice that the icon will have been enhanced by Safari with 3D shading and also will have been scaled to fit a 57×57 pixel rectangle. Next fill in the application name and press the Add button. The application can now be launched by simply tapping its icon on the iPhone home screen.

As a convenience, we have automated steps 1-5 in a Bash script (Listing 2) which you can download. This script will write an installer HTML file for rg_rotate by running the command: build_installer.sh rg_rotate. Other application installers can be built by providing different application names to the builder script: build_installer.sh [application name] creates the file [application name]_installer.html. Please see the next section, “Extending the Installer”, for more information about enhancing build_installer.sh to handle different applications.

The script prompts for a single image file to be used as the apple-touch-icon resource. The script determines the mime type of the image file from its extension and encodes the corresponding data URL appropriately.

Extending the Installer

Simplified for instructional purposes, the provided generator script prompts for and embeds only one external resource, However, it can easily be enhanced to prompt for multiple images and other resources that particular stand-alone web applications might need. As a first approach, one can add sed commands to replace additional target URL references with base 64 encoded resources. In build_installer.sh, each resource is identified in the source web application with a placeholder such as “RESOURCE_1“. An entry for this placeholder would be added to the script as a sed command of the form:

s~RESOURCE_1~"data:'$mime_type[1]';base64,'`$BASE64 -w 0 $resource_file[1]`'"~;

where the values for $mime_type[1] and $resource_file[1] must be set appropriately. See Listing 2 build_installer.sh for details. A much more robust web application installer could be built with a sophisticated micro-framework such as the Ruby-based Sinatra (see for example, Building a iPhone web app in under 50 lines with Sinatra and iUI), but this approach would require the installation and management of additional resources.

Listing 1: RG Rotate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

<html>
<head>
<link rel="apple-touch-icon" href="TOUCH_ICON" />
<meta name="viewport" content="width=device-width; initial-scale=1.0;
  maximum-scale=1.0; user-scalable=0;"/>
<style>
    body[orient="portrait"] {
        background-color: #f00;
    }
    body[orient="landscape"] {
        background-color: #0f0;
    }
    body[orient="portrait"] #content {
        width: 100%;
        height: 460px;
    }
    body[orient="landscape"] #content {
        width: 100%;
        height: 300px;
    }
</style>
<script>
  var currentWidth = 0;
  addEventListener("load", function() {
      setTimeout(orientationChange, 0);
  }, false);
  function orientationChange() {
      if (window.innerWidth != currentWidth) {
          currentWidth = window.innerWidth;
          document.body.setAttribute('orient', (currentWidth == 320) ? "portrait" : "landscape");
          setTimeout(scrollTo, 100, 0, 1);
      }
  }
  setInterval(orientationChange, 400);
</script>
</head>
 
  <body>
 
 
    <!--
      <img src="RESOURCE_1" alt="test jpg" />
      <p>TEST JPG: see build_installer.sh for details</p>
    -->
    <div id='content'></div>
  </body>
</html>

Listing 2: build_installer.sh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

#!/bin/bash
#
# build_installer.sh
#
# This script is part of the tutorial about "How to Install
# an iPhone Web Application". The script is run with a
# single argument, the application name, which defaults to
# rg_rotate for the purposes of the tutorial.
# 
 
# The script demonstrates how to build a web page which can
# be used to provision an iPhone web application. The
# source file for the web application is expected to be named
# [application_name].html and the provisioning web page is
# written out as [application_name]_installer.html.
# 
# This script can be enhanced with prompts for additional
# resource files and mime types. Alternatively, additional
# resources can be hand coded where indicated.
# 
# The body of the provisioning web page holds the complete,
# encoded web application within a link that can be selected
# in the Mobile Safari browser. When this link is selected,
# the data URL that encodes the web application is placed
# in Safari's URL Bar. At this point the application can be
# installed with the + key of the Safari Button Bar. In order
# for Safari to access the provisioning web page, it must
# be placed on a preferably local web server that can be
# reached by the iPhone.
#
# The provisioning web page is generated to be run as a mini
# iPhone application itself. For example, it will respond to
# orientation changes and hides the URL Bar when loaded.
# 
# BEGIN RESOURCE MAPPINGS
# change the following dummy resource mappings as needed:
# Specifically, for each N define the mapping in this file
# as: mime_type[N]='type/subtype'; resource_file[N]='file_path'
# and the label RESOURCE_N as the corresponding URL reference
# in the web application file.
# E.g., mime_type[1]='image/jpg'; resource_file[1]='myface.jpg'
# and <img src="RESOURCE_1" alt="myface" /> in the web
# application file.
mime_type[1]='image/gif'; resource_file[1]='/dev/null'
mime_type[2]='image/gif'; resource_file[2]='/dev/null'
mime_type[3]='image/gif'; resource_file[3]='/dev/null'
# END RESOURCE MAPPINGS
MAX_RESOURCES=${#mime_type[*]} 
map_resource() {
 local ret=$1
 local id=$2 
 local resource='s~RESOURCE_${id}~data:'${mime_type[$id]}'\;base64,'\
`$BASE64 -w 0 ${resource_file[$id]}`'~\;'
 eval "$ret=$resource"
}
BASE64="/usr/bin/env base64"
XARGS="/usr/bin/env xargs"
TEMPFILE="/usr/bin/env tempfile"
application=${1:-rg_rotate}
touch_icon_image_file="${application}_touch_icon.png"
if [[ ! -e "${application}.html" ]]; then
  echo "Template web application file ${application}.html does not exist."
  echo "Please create and run application installer again -- exiting."
  exit
fi
read -p "Enter location of apple-touch-icon image file (./$touch_icon_image_file): " ipath
[[ "$ipath" ]] && touch_icon_image_file="$ipath"
if [[ ! -e "$touch_icon_image_file" ]]; then
  echo "$touch_icon_image_file does not exist, will create application with empty bookmark icon"
  touch_icon_image_file=/dev/null
fi
echo "Using ${application}.html as input template for web application"
touch_icon_mime_type="image/${touch_icon_image_file##*.}"
TFILE=`$TEMPFILE`
trap "rm -f $TFILE" 0 1 2 5 15
# TODO: hand code or prompt for additional resources
additional_resources_map=
for i in $(seq 1 $MAX_RESOURCES); do
  map_resource res $i
  additional_resources_map="$additional_resources_map$res"
done
cat <<EOM1 | $XARGS -I{} sed -e {} ${application}.html > $TFILE
's~TOUCH_ICON~data:'$touch_icon_mime_type';base64,'`$BASE64 -w 0 $touch_icon_image_file`'~; \
 $additional_resources_map \
'
EOM1
echo "Creating `pwd`/${application}_installer.html"
echo "Point Mobile Safari to the HTTP location of this file to install ${application}"
#
# Provisioning web page:
cat <<EOM2 > ${application}_installer.html
<html>
  <head>
    <meta name="viewport" content="width=device-width; initial-scale=1.0;
        maximum-scale=1.0; user-scalable=0;" />
    <style>
        body[orient="portrait"] {
          height: 460px;
 
        }
        body[orient="landscape"] {
          height: 300px;
        }
    </style>
    <script>
      var currentWidth = 0;
      addEventListener("load", function() {
          setTimeout(orientationChange, 0);
      }, false);
      function orientationChange() {
          if (window.innerWidth != currentWidth) {
              currentWidth = window.innerWidth;
              document.body.setAttribute('orient', (currentWidth == 320) ? \
                 "portrait" : "landscape");
              setTimeout(scrollTo, 100, 0, 1);
          }
      }
      setInterval(orientationChange, 400);
    </script>
  </head>
  <body style="background-color: #d0d0d0; font-size: 24px; height: 460px;">
      <h2 style="text-align: center;">
        <span style="background-color: #000; color: #fff;">"${application}"</span>
        <br />Installation Steps
      </h2>
      <ol>
          <li>Select
           <a style="background-color: #ff0; font-weight: bold;"
             href="data:text/html;charset=utf-8;base64,`$BASE64 $TFILE`">
             this link
           </a>
             to install "${application}" as a data URL in the URL Bar, then</li>
          <li>Press
            <span style="background-color: #ff0; font-weight: bold;">+</span>
            key on iPhone button bar to add "${application}" to home page.
          </li>
      </ul>
  </body>
</html>
EOM2

Listing 3: rg_rotate_installer.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

<html>
  <head>
    <meta name="viewport" content="width=device-width; initial-scale=1.0; 
     maximum-scale=1.0; user-scalable=0;" />
    <style>
      body[orient="portrait"] {
        height: 460px;
      }
      body[orient="landscape"] {
        height: 300px;
      }
    </style>
    <script>
      var currentWidth = 0;
      addEventListener("load", function() {
        setTimeout(orientationChange, 0);
      }, false);
      function orientationChange() {
        if (window.innerWidth != currentWidth) {
          currentWidth = window.innerWidth;
          document.body.setAttribute('orient', (currentWidth == 320) ?
              "portrait" : "landscape");
          setTimeout(scrollTo, 100, 0, 1);
        }
      }
      setInterval(orientationChange, 400);
    </script>
  </head>
  <body style="background-color: #d0d0d0; font-size: 24px; height: 460px;">
      <h2 style="text-align: center;">
        <span style="background-color: #000; color: #fff;">"rg_rotate"</span>
        <br />Installation Steps
      </h2>
      <ol>
          <li>Select
            <a style="background-color: #ff0; font-weight: bold;"
             href="[copy contents of rg_rotate_html.b64 here]">this link
            </a>
            to install "rg_rotate" as a data URL in the URL Bar, then
          </li>
          <li>Press <span style="background-color: #ff0; font-weight: bold;">+</span>
              key on iPhone button bar to add "rg_rotate" to home page.
          </li>
      </ul>
  </body>
</html>

Back in the early days of iPhone application development, when any release of free and open source software was caught up in an NDA controversy with the mothership, Chris Allen helped popularize the notion that the iPhone could become a viable platform for building open source applications. He offered as an example his simple and free iPhone application called “RedGreen”. The application was indeed simple. It permitted you to use the iPhone as a kind of public voting machine. It could splash a bright red screen for all to see by tapping on the glass to signify disapproval, and then it would go green with another tap, presumably to register approval. And it was free as in, er, advice and of course free as in freedom. You could get the MIT-licensed code from Chris by a simple e-mail request. Except perhaps for a “Hello World!” nothing could be easier.

The World Has Changed

But hello, the world has changed. Apple has allowed open source applications to be built and distributed through the App Store and has amassed a healthy collection of applications to download for free. So it seemed to us that the time had come to webify Chris’s wonderful application.

First, we thought we’d move it away from the world of still semi-proprietary development and out onto the free and open web. Hmmm… Free at last. And then we thought we’d add a couple more colors.

So here you have it: RedGreen…YellowBlue.

Back to Basics

Well, if the truth is told, we actually wanted to demonstrate some basics of writing near-native iPhone applications using web-based tools. With modern web browsers, technologies like AJAX and JavaScript can power many kinds of interactive applications while imposing few artificial constraints on any phase of development. A web approach can be crafted from generic components and may result in less overall complexity. The main downside, of course, is that applications need some sort of web site for program deployment as well as for data retrieval and storage. However, when developing in-house applications, these concerns become less important, and so many useful and highly interactive mobile applications can be built for the iPhone (as well as for other platforms like Android) as part of infrastructure development using sophisticated web technologies.

So How Do You Start?

We thought it would be instructive to see how a simple web-based application for the iPhone can be built. We started with Chris’s simple idea: display an electronic version of red-green voting cards. Once certain limitations of the iPhone as a web device are understood, it turns out to be pretty easy to produce a basic application. Some of the iPhone’s contraints include its 480×320 screen-size, an imprecise input device (your finger), and two orientation modes (portrait and landscape).

The 480×320 pixel screen and the variable size input device drive the bulk of the iPhone’s UI design. Buttons and other widgets must be drawn over-sized in order to be comfortable for the human finger to tap. This means fewer buttons and other interactive fields on any one screen. Furthermore, data must be organized carefully to fit onto the small screen. This requires vertical, instead of horizontal, scrolling and favors navigation techniques like sliding panels. Two screen orientation modes arise because the user can rotate the iPhone at any time while viewing a web page. Ideally, the web application will render a fresh screen with all the components (text, buttons, fields, etc.) being rotated and displayed in their appropriate relationships under the new geometry. There are additional details, like the 44 pixel (32 pixel in landscape mode) button bar at the bottom of every web screen which cannot be hidden or programmatically controlled. Likewise for the 20 pixel status bar at the top of the screen. Fortunately, the 60 pixel URL bar can be scrolled out of view when not in use through a simple JavaScript command. This leaves a screen real estate area usable for content which is only 416×320 in portrait mode and only 268×480 in landscape mode.

Diving in Deeper

The following web application illustrates practical solutions to some of the constraints imposed by the iPhone as a web client. Typically for this kind of application, JavaScript and CSS must partner in providing the solutions.

RGYB Screenshot

The application we have developed displays two panels next to each other, side-by-side. Each panel covers half the iPhone screen width and all of its height. The user can tap on one panel or the other to toggle different colors: red/green by tapping on the right panel, and yellow/blue by tapping on the left panel.

The application structure is summarized as follows:

First, a META tag recognized by the Safari browser on the iPhone specifies that the iPhone’s viewport is set to “device size” (480×320) and that it cannot be resized by the user. This is the first step in giving the web application the appearance and behavior of a typical native iPhone application.

Second, an embedded CSS style sheet defines a common set of properties for the left and right panels; e.g., they both start out red. Then different panel dimensions for each screen orientation mode are given. Notice also that the left edge of the right panel is increased when in landscape mode. This maintains the right panel’s position at half-screen.

The JavaScript in this application begins with a few variables and helper functions and then continues with a series of simple color toggle functions. Following these functions are methods which are more important for the behavior of the iPhone interface. They are ‘checkOrientation‘ and ‘loadHandlers‘. The onLoad property of the BODY tag is set to method ‘loadHandlers‘ in the HTML text. Consequently, ‘loadHandlers‘ will be called after the web page has been completely loaded into the browser. When invoked, ‘loadHandlers‘ starts by calling ‘checkOrientation‘ to determine the current screen orientation and then sets up a recurring task to perform this same check periodically. If ‘checkOrientation‘ finds that the orientation has changed, it sets the ‘orient‘ property of the BODY tag to ‘portrait’ or ‘landscape’ as appropriate. The orient flag guides the re-drawing of the web screen according to the automatically selected CSS properties. A window object scrollTo method is then scheduled by setTimeout to be run a tenth of a second later. This gives the browser time to make any adjustments needed to display the correct orientation and then the scrollTo method hides the 40 pixel URL bar.

This then is our web equivalent of Chris Allen’s first native iPhone application, a groundbreaking demonstration from the first iPhoneDevCamp long, long ago (actually, about a year and a half ago.) In our application, a lot of capabilities like AJAX and data access that are needed for any serious web application have been completely ignored. However, by exploring the structure of the simplest kind of mobile web application, we hope that more interesting and sophisticated applications will be developed for the iPhone using web tools and techniques.

Try This Out

If you would like to try ‘red_green_yellow_blue’ on your iPhone, please click here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

<html>
<head>
<meta name="viewport" content="width=device-width; initial-scale=1.0;
          maximum-scale=1.0; user-scalable=0;"/>
<style>
.container {
  top: 0;
  position: absolute;
  background-color: #f00;
}
body[orient='portrait'] .container {
  height: 460px;
  width: 160px;
}
body[orient='landscape'] .container {
  height: 320px;
  width: 240px;
}
body[orient='portrait'] #right_panel {
  left:160;
}
body[orient='landscape'] #right_panel {
  left:240;
}
</style> 
<script>
CURRENTWIDTH = 0;
RG = ['rgb(0, 255, 0)', 'rgb(255, 0, 0)' ]
YB = ['rgb(0, 0, 255)', 'rgb(255, 255, 0)' ]
function $(id) { return document.getElementById(id); }
function updateContainers(rgb) {
  $('right_panel').style.backgroundColor = $('left_panel').style.backgroundColor = rgb;
  setTimeout(scrollTo, 100, 0, 1);
}
function toggleRedGreen() {
  var color = $('right_panel').style.backgroundColor.toString();
  updateContainers(RG[(color == RG[0]) ? 1 : 0]);
}
function toggleYellowBlue() {
  var color = $('left_panel').style.backgroundColor.toString();
  updateContainers(YB[(color == YB[0]) ? 1 : 0]);
}
function checkOrientation() {
  if (window.innerWidth != CURRENTWIDTH) {   
    CURRENTWIDTH = window.innerWidth;
    document.body.setAttribute('orient', (CURRENTWIDTH == 320) ? 'portrait' : 'landscape');
    setTimeout(scrollTo, 100, 0, 1);
  }
} 
function loadHandlers() {
  checkOrientation();
  setInterval(checkOrientation, 300);
}
</script>
</head>
<body onLoad="loadHandlers();">
<div onClick="toggleRedGreen();" class="container" id="right_panel"></div>
<div onClick="toggleYellowBlue();" class="container" id="left_panel" style="left: 0;"></div>
</body>
</html>

How do we turn pipes into stacks without resorting to index or pointer manipulation? That is, suppose we have only the ability to create FIFOs for pipe-like behavior but we want to create LIFOs for alternative stack-like behavior.

A FIFO is an opaque structure that allows items to be placed or pushed onto it at one end (head) and removed or pulled from it, one at at time and in sequence, from the other end (tail). A LIFO is a similarly opaque structure that allows items to be pushed onto it at one end (head or top) and removed or popped from it from that same end (head). This means that items of a LIFO are removed one at a time but in the reverse order of when they were entered. Let us further suppose that our only FIFO primitives are an append operator ‘push’ and a pull operator ’shift’. ‘push’ adds elements to the head of the FIFO and ’shift’ grabs (and removes) items from the tail of the structure.

Therefore, we want to build a stack (LIFO) using the pipe (FIFO) structure and its two primitive operators, ‘push’ and ’shift’. Essentially, we wish to combine ‘push’ (onto head) and ’shift’ (from tail) pipe operators in some fashion to simulate ‘push’ (onto head) and ‘pop’ (from head) stack operators.

The following short Ruby program demonstrates a simple solution to this puzzle. Basically we shift items between two FIFO structures to simulate the operations of a stack. But this program is notable less in the algorithm selected and more in the way Ruby expresses the steps required. Interesting Ruby idioms include parallel assignment, variable length argument lists, and simple method definitions and usage.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

#!/usr/bin/env ruby
#
# Implementing a Stack with Two Queues: A Simple Ruby Demonstration
# -----------------------------------------------------------------
# 
# How do we turn pipes into stacks without resorting to index or
# pointer manipulation? That is, suppose we have only the ability to
# create FIFOs for pipe-like behavior but we want to create LIFOs
# for alternative stack-like behavior.
# 
# A FIFO is an opaque structure that allows items to be placed or
# pushed onto it at one end (head) and removed or pulled from it, one
# at at time and in sequence, from the other end (tail). A LIFO is a
# similarly opaque structure that allows items to be pushed onto it at one
# end (head or top) and removed or popped from it from that same end
# (head). This means that items of a LIFO are removed one at a time
# but in the reverse order of when they were entered. Let us further
# suppose that our only FIFO primitives are an append operator 'push'
# and a pull operator 'shift'. 'push' adds elements to the head of
# the FIFO and 'shift' grabs (and removes) items from the tail of
# the structure.
# 
# Therefore, we want to build a stack (LIFO) using the pipe
# (FIFO) structure and its two primitive operators, 'push' and
# 'shift'. Essentially, we wish to combine 'push' (onto head) and
# 'shift' (from tail) pipe operators in some fashion to simulate 'push'
# (onto head) and 'pop' (from head) stack operators.
# 
# The following short Ruby program demonstrates a simple solution to
# this puzzle. Basically we shift items between two FIFO structures
# to simulate the operations of a stack.  But this program is notable
# less in the algorithm selected and more in the way Ruby expresses the
# steps required. Interesting Ruby idioms include parallel assignment,
# variable length argument lists, and simple method definitions
# and usage.
#
# Copyright (c) 2008 Technetra Corp
# 
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
#
# Implementation of Stack Using Two Queues
class Stack
  def initialize *s # splat operator allows variable length argument list
    @q1 = []
    @q2 = []
    s.each { |e| push e }
  end
  def push v
    # pure FIFO allows only 'push' (onto head) and 'shift' (from tail)
    # LIFO requires 'push' (onto head) and 'pop' (from head)
    empty_queue, full_queue = @q1.length == 0 ? [ @q1, @q2 ] : [ @q2, @q1 ]
    empty_queue.push v
    until (v = full_queue.shift).nil? # shift each item from non-empty queue,
      empty_queue.push v              # pushing it onto initially empty queue:
                                      # produces new full queue in reverse entry order
    end 
  end
  def pop
    full_queue = @q1.length > 0 ? @q1 : @q2
    # full queue has been maintained in reverse order
    # by the push method of the Stack class, so a simple
    # shift is all that is needed to simulate a stack
    # pop operation
    el = full_queue.shift
  end
  def empty?
    @q1.length == 0 && @q2.length == 0
  end
end
 
# test:
puts "STACK: tail/bottom -> x, y, z <- head/top"
stack = Stack.new
stack.push 'x'
stack.push 'y'
stack.push 'z'
# or equivalently, stack = Stack.new('x', 'y', 'z')
until stack.empty?
  puts "popping stack, item: #{stack.pop}"
end
# prints items in reverse order: 'z', 'y', 'x'