Constraint-Based Document Layout for Mobile Computers
Lawrence Teo <Lawrence.Teo@infotech.monash.edu.au>
Monash University, Melbourne, Australia
This is a joint project between the Distributed Systems and Software Engineering (DSSE) and Optimisation and Constraint Solving (O&CS) research groups. It is funded by DSTC as a summer vacation student project.
One of the main technical challenges of document delivery over the Internet results from the tensions among the document designer's desire to specify the exact appearance of the document, the document viewer's desires and needs, and the capabilities of the viewing device. This is particularly true for hand-held computing devices whose screen area is extremely limited. Constraint-based layout provides a possible solution [1,2]. Constraints allow the designer to specify what are the desired properties of the layout, rather than precisely detail the layout, thus allowing more flexibility.
The aim of this project is to determine whether constraint-based layout is provides sufficient flexibility for hand-held devices .
This project uses two technologies for formatting document layouts on mobile devices: constraints and Composite Capabilities/Preferences Profiles (CC/PP).
Constraints provide a declarative way of specifying the desired layout of a document. Constraints have previously been researched in areas such as web development. In this project, constraints was tested for its feasibility as a means for formatting document layouts on mobile devices.
CC/PP is a draft standard proposed by the World Wide Web Consortium (W3C). CC/PP is used to state the capabilities and preferences of users and their user agents. For example, the CC/PP for a PDA would describe its hardware, software, operating system, etc. It would also state the user's preferences (such as whether the user wants sound to be turned on), and hardware extensions.
How the System Works
A system was designed to use constraints and CC/PP to format document layout on mobile devices. The system was implemented as a Perl script called pdaformat.pl. The system takes in an input document, applies constraints and CC/PP attributes to it in order to produce a Palm database (.pdb) file which will be shown on a PalmOS device.
In the system, instead of focusing on all kinds of documents, we chose to use tables as our input document. We then define constraints specific to tables (such as column widths). CC/PP is used to provide the screen width for the device, which is then used as an input value for the constraints (in this case, the screen width is used as the value for the total width of the table).
The constraints are declared in a file using a simple constraint declaration language (which will be described in the section Constraint Declaration Language).
The following software are required to run the system:
Installing the System
You can download the system from here: pdaformat.tar.gz (971KB). Here are some short instructions on installing the system:
Another way to obtain the latest version of the system is through CVS. The system has been placed on the CVS server at bowman.csse.monash.edu.au on 24 January 2001. To obtain the CVS version, you can use the following instructions on a UNIX system.
export CVSROOT=:pserver:email@example.com:/home/cvsroot cvs login (password is "anonymous") cvs co cns-tbls
Running the System
Go to the pdaformat/ directory and type ./pdaformat.pl at the shell. You should get the following output:
The pdaformat.tar.gz package comes with a few sample files that can be used to test the pdaformat.pl script. These files are described as follows:
The sample files are shown as follows:
"Name","Email","Phone" "Arkady","firstname.lastname@example.org","32 479" "Kim","email@example.com","55 525" "Lawrence","firstname.lastname@example.org","32 309" "Nathan","email@example.com","55 779" "Peter","firstname.lastname@example.org","55 779"
wines3.xls (represented here in HTML):
You can test the script as follows:
./pdaformat.pl -i phonebook.csv -c phonebook.con -p palm-iii.ccpp -o phonebook.pdb -n "myphonebook"
That command should generate a file called phonebook.pdb. In summary, the command takes in the phonebook.csv file, and uses constraints declared in phonebook.con and the screen size of the Palm specified in palm-iii.ccpp. It then generates the phonebook.pdb database file with the name "myphonebook". The following figure shows a screenshot of the PDB file being displayed on a PalmOS emulator.
The -D option can be used to print out (hopefully) useful debugging information. Here's a sample use for it:
./pdaformat.pl -i wines3.xls -c wines3.con -p palm-iii.ccpp -o wines3.pdb -n "My wines" -D1
The command generates the wines3.pdb file from wines3.xls, wines3.con and palm-iii.ccpp. The debug level was set to "1", which prints out debugging information. The greater the level, the more debugging information is printed.
Constraint declaration language
The system uses a simple constraint declaration language, which is defined in "pseudo-BNF" as follows:
For a better explanation of these constraints, please refer to the constraint examples given below.
The variable names used in the constraints have special meanings attached to them. These meanings are described as follows:
On average, each character is 5.6 pixels wide on the Palm. The actual width of each character is variable - for example, a "w" will occupy more pixels compared to an "i". 5.6 pixels was chosen as the average size, as the width of most characters range from 5 to 6 pixels.
Here is a sample file containing simple constraints:
The constraints above can be summarised like this: The total width of the table is equal to the sum of the widths of columns 1, 2 and 3. The width of column 1 must be equal to column 3. Column 2's width will be twice that of column 1.
Here is an example of a constraints file using weighted constraints.
The set of sample weighted constraints given above can be summarised like this: The "!type = weighted" statement means that the constraints specified in this file are weighted constraints. The system will therefore expect to read weighted constraint declaration lines.
"cw1 >= ce1" means that the width of column 1 must be greater than the width of the widest entry in column 1. "cw1 >= cl1" means that the width of column 1 must be greater than the width of the longest word in column 1. Likewise, the widths of the rest of the columns are greater than the widths of the widest entries and the longest words in those columns ("cwx >= cex" and "cwx >= clx").
There are weights associated with each constraint. In this example, the strong and verystrong weights are associated with columns 1,2 and 4, because those are important columns. Column 3 is given a weak weight. The figures below show the screenshots of the output using these set of constraints on the sample wines3.xls file (the wines3.xls file has four columns: Manufacturer, Name, Description, Price/bottle). Note that column 3 has been given the weakest weight, and therefore its width is not greater than the widest entry nor the longest word. On the other hand, columns 1, 2 and 4 have been given greater priority.
This section presents some notes on the internal workings of the system.
The program is summarised in the following order:
The weight strings ("verystrong", "strong", ...) and their respective weight values are stored using an associative array called %weight_values which has the following associations:
A seminar was held to present the results and status of this project:
Constraint-Based Document Layout for Mobile Computers, Distributed Systems Technology Centre, Room B4.61, Monash University, Caulfield, 24 January 2001, 4pm.
As mobile devices become more popular, their users have an increasing need for such devices to be connected to the Internet. However, the limitations of such devices make it difficult for Internet content to be displayed on them. As an example, some webpages that are graphically rich are almost impossible to display on a Personal Digital Assistant with a limited screen size without colours.
There is therefore a need to adapt the content of Internet resources into a format that fits the limitations of a mobile device. Content adaptation has been done before, and it remains active in research today.
This project investigates the feasibility of two technologies - constraints and Composite Capabilities/Preferences Profiles (CC/PP) - as a means for formatting document layouts on mobile devices. I will also present a small prototype of a mobile computing system which merges both technologies to format documents for mobile devices. An interesting aspect of this system is that it uses Qoca, a constraint-solving toolkit developed by CSSE.
I would like to acknowledge the help of my supervisors Arkady Zaslavsky and Kim Marriott. Thanks also goes out to Peter Moulder for his help on Qoca, CVS, and many other things, and Nathan Hurst for writing Qoca Perl. Dr Seng Wai Loke introduced me to resources on CC/PP. Rob Gray helped me with administrative matters.
It has been a great pleasure working with all of you -- and tell me when you guys get a paper published! :-)
This section describes some of my personal experiences throughout the duration of this project.
When I first started the project, I had no idea about constraint solving and CC/PP. My research interest was in network security; therefore, constraints and CC/PP were alien to me. I really wondered whether I could actually finish this entire project.
I had a few meetings with Arkady, Kim, Peter and Nathan in the initial weeks of the project. Kim brought me some papers on constraints, which proved to be immensely useful. It provided me with some ideas on constraint solving. Arkady introduced me to Dr Seng Wai Loke, who in turn showed me the W3C resources on CC/PP.
I remember facing a lot of difficulties in the beginning. I was running an OpenBSD box in my lab, and I ran into compilation problems when trying to compile Qoca because of the non-GNU utilities on the system. I exchanged a lot of emails with Peter, who helped me out tremendously. In the end, Peter and Nathan gave me an account on bowman, their Linux box in their lab, and I developed the system there ever since. Although the compilation problems delayed my project for awhile, I did learn a lot about UNIX development tools, especially how BSD and GNU utilities differ (note to Peter: okay, I shall make sure that my future BSD boxes have the proper GNU tools on them! :) ).
I also had difficulty understanding how Qoca worked in the beginning. The documentation was actually there, just that I was looking in the wrong places. Eventually I found the tutorial on the Qoca project webpage, and using the information on that page together with trial-and-error, I finally understood how it worked. I soon got it working on my system. And I'm now thinking of using Qoca for some of my own projects in the future! :)
The goals for the project changed as well. Originally, I defined two goals in the project:
Goal #1: Convert an Excel file to a PDB file, using constraints and CC/PP to format the document layout. Demonstrate this on MobileDB on the Palm emulator. The aim of this is to show the basics of using constraint-solving techniques and CC/PP to format documents on present mobile devices.
Goal #2: Convert an Excel file to an XML file, using constraints and CC/PP to format the document layout. Demonstrate this on Tarpaulin, the XML browser written by Nathan. This will be used to show more advanced uses of constraints and CC/PP to format documents on "future" mobile devices.
These goals evolved along the way. At the end of it, I was supporting Excel spreadsheets, XHTML tables and CSV files. It supported weighted constraints too, which just got added into Qoca recently. Unfortunately, I didn't manage to use Tarpaulin as planned. Tarpaulin was an XML browser that was supposed to be used in the project to simulate future and more advanced mobile devices.
Presenting a seminar about the project was an interesting experience. I received a lot of questions from the audience, a lot of which I never expected, but the audience input was very helpful in determining the future areas that can be looked into in this project. I had a good discussion with the audience. I was glad to have Arkady, Kim and Peter in the seminar too to help me answer questions which I have no idea of!
Overall, I think my whole DSTC summer project has been a really rewarding experience. I solved many interesting problems and enjoyed the numerous challenges along the way. It was also great to work with a team of people who supported me all the way. Although the project wasn't easy, I had a lot of fun and learnt a heap of stuff, which will definitely be useful in the future.