mxml.it
avoid mickey mouse programming
Longest common subsequence problem
Jun 4th
Dynamic Programming is a powerful technique that can be used to solve many problems in time T(n2) or T(n3) for which a naive approach would take exponential time. “DP” is a general approach to solving problems, much like “divide-and-conquer” is a general method, except that unlike divide-and-conquer, the subproblems will typically overlap and are used to solve the next one.
The cost of an algorithm in a program is a critical aspect because it can significantly impact on performances. In order to keep the cost low “DP” follow a couple of standard ways to progress
• memorization
• converting from top-down to bottom-up
Another very common problem when dealing with dynamic programming is the longest common subsequence problem (for brevity since now “LCS”). The “LCS” problem is as follows
We are given two strings: string S of length n, and string T of length m. The goal is to produce their longest common subsequence: the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.
The problem can be solved comparing the two strings; in the case S and T have a different length the desired subsequence has to ignore the ending elements of one of the two strings, in the case S and T have the same length all the characters have to be considered.
As subproblems the algorithm will look at the “LCS” of a prefix of S and a prefix of T, running over all pairs of prefixes. For simplicity, let’s worry first about finding the length of the LCS and then we can modify the algorithm to produce the actual sequence itself.
The longest common subsequence(LCS) problem is one of the classical and well- studied problems in computer science. The computation of the “LCS” is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. Another practical application of the “LCS” algorithm is in order to compute the file differences.
Theoretically speaking the algorithm just fill out a matrix row by row, doing constant amount of work per entry, so this takes T(mn) time overall. The work actually performed is a comparison between the chars of the two strings at specific indexes.
The final answer (i.e. the length of the LCS of S and T) is in the lower-right corner.
To find the common sequence, the algorithm just walk backwards through matrix starting the lower-right corner.
If either the cell directly above or directly to the right contains a value equal to the value in the current cell, then move to that cell (if both to, then chose either one). If both such cells have values strictly less than the value in the current cell, then move diagonally up-left, and output the associated character.
This will output the characters in the LCS in reverse order.
Consider a practical example and search the “LCS” of the following strings
• ABAZDC
• BACBAD
The algorithm will fill out a matrix like the following one and running backward the matrix the output will be DABA that is the “LCS” between the two strings.
| B | A | C | B | A | D | |
| A | 0 | 1 | 1 | 1 | 1 | 1 |
| B | 1 | 1 | 1 | 2 | 2 | 2 |
| A | 1 | 2 | 2 | 2 | 3 | 3 |
| Z | 1 | 2 | 2 | 2 | 3 | 3 |
| D | 1 | 2 | 2 | 2 | 3 | 4 |
| C | 1 | 2 | 3 | 3 | 3 | 4 |
From a practical point of view the following diagram shows up the classes involved into an ActionScript “DP” solution to the problem.
Let’s start to examine what model used by these classes.
The class LCSTable is the one to use in order to represent the matrix outlined at the beginning of the post, for this reason the constructor accept two arguments that represent the rows and columns of the matrix (i.e. the length of the two strings that will be examined) and use them to create an Array of Vectors
public function LCSTable(rows:int, columns:int){
_table = [];
for(var i:int = 0; i <= rows; i++){
table[i] = new Vector.(columns + 1, true);
for(var j:int = 0; j <= columns; j++){
table[i][j] = new LCSCell(0, LCSCell.UNDEFINED);
}
}
}
The property _table is exposed through a public getter and return the array of Vectors that is the way all the cells are represented into the model.
The LCSCell class is pretty simple, it stores the total number of matching strings and the direction the algorithm has to follow to walk backwards through matrix starting, the direction is stored into four static constants
- public static const UP:String = “^”;
- public static const LEFT:String = “<”;
- public static const DIAGONAL:String = “\\”;
- public static const UNDEFINED:String = “+”;
when the LCSTable create the new cells set the direction to UNDEFINED and the total to 0.
The core of this solution for the longest common subsequence problem is the LCSParser class, let’s start to explore it.
The constructor of the class needs two arguments (i.e. the strings to compare) and store them into two private members of the class
public function LCSParser(first:String, second:String){
firstString = first;
secondString = second;
init();
populate();
}
The protected method init() store the number of columns in other two private members and initialize the table setting the default values of the cells (i.e. direction UNDEFINED and total 0)
protected function init():void{
_lcs = "";
columns = firstString.length;
rows = secondString.length;
table = new LCSTable(rows, columns).table;
}
The populate() method creates two local variables to keep track of the total numbers of matching strings for each column and start the exploration of the LCSTable with tow nested for loops
var totalTemp1:int;
var totalTemp2:int;
for(var i:int = 1; i <= rows; i++){
for(var j:int = 1; j <= columns; j++){
// Additional code here
}
}
In the body of the loop the method checks if there are matching characters or not in the two stored strings. If there is a match the current cell is updated considering if it belongs to the first row or column of the table (in this situation the total is 0 and the direction is intentionally left as UNDEFINED) or not.
When updating the cell the local variable totalTemp1 is used in order to increase the total property of the LCSCell instance properly.
if(firstString.charAt(j - 1) == secondString.charAt(i - 1)){
var currentCell:LCSCell = getCell(i, j);
if (i == 0 || j == 0) {
currentCell.total = 0;
// if not, set it to 1 plus the value of its upper left element
} else {
totalTemp1 = getCell(i - 1, j - 1).total;
currentCell.total = totalTemp1 + 1;
currentCell.direction = LCSCell.DIAGONAL;
}
}else{
totalTemp1 = getCell(i - 1, j).total;
totalTemp2 = getCell(i, j - 1).total;
updateDirection(getCell(i, j), totalTemp1, totalTemp2);
}
If there are not matching chars the method updateDirection() is called.
This method consider the position in the table (i.e. actual row and column) and update the direction and total accordingly to the position
private function updateDirection(cell:LCSCell, s1:int, s2:int):void{
if(s1 >= s2){
cell.total = s1;
cell.direction = LCSCell.UP;
}else{
cell.total = s2;
cell.direction = LCSCell.LEFT;
}
}
Once the table is populated the public method lcs() can be used to recover the longest common subsequence.
The method calls another one to walk backwards through matrix and return a string
public function get lcs():String{
parseLCS(secondString, rows, columns);
return _lcs;
}
The parseLCS() method uses recursion and populate the _lcs property accordingly to the direction of each cell
private function parseLCS(data:String, i:int, j:int):void{
if ((i == 0) || (j == 0)){
return;
}
var currentCell:LCSCell = getCell(i, j);
if(currentCell){
if(currentCell.direction == LCSCell.DIAGONAL){
parseLCS(data, i - 1, j- 1);
var temp:String = data.charAt(i - 1);
_lcs += temp;
}else if(currentCell.direction == LCSCell.UP){
parseLCS(data, i - 1, j);
}else{
parseLCS(data, i, j - 1);
}
}
}
A fully working demo is available here with the source code included (right click -> view source), please feel free to use it as you want but please provide me as much as possible your feedback.
Just in case you would like to go deeper on this topic following you can find some interesting linka
- http://en.wikipedia.org/wiki/Dynamic_programming
- http://wordaligned.org/articles/longest-common-subsequence
- http://igm.univ-mlv.fr/~lecroq/seqcomp/node4.html
Enjoy with dynamic programming!
Flex and Jabber, a practical approach
May 7th
The widely adopted open protocol for instant messaging XMPP (also called Jabber) is a de facto standard used in various instant messaging systems. The aim of this article is to show how quick and easy it is to create a real time application using this protocol that relies on a restful architecture.
In order to start playing with Flex and the XMPP protocol you have to select the server you prefer and install it.
My choice is Open Fire (http://www.igniterealtime.org/), and the main reasons for this choice are:
• It’s fully compliant to the standards
• It’s very easy to install
• It can work with several databases in addition to the built-in one (it supports MySQL, PostgressSQL, Oracle, SQLServer and IBM DB2)
• It can interact with OpenLDAP and / or Active Directory
• It can track all the IM traffic and store it as XML files
• It has a great log panel
• It can easily administer chats and rooms
• Options allow control over room moderation, maximum occupancy, presence information, and more
• There is a good ActionScript library that can interact with Open Fire
In order to setup your environment you have to follow the wizard provided with the Open Fire installer (I suggest you keep in place the built-in database and the default settings) and then you can login on your localhost to the administrative console.
Create a new Flex project with you favorite IDE and add the XIFF library (http://www.igniterealtime.org/downloads/download-landing.jsp?file=xiff/xiff_3_0_0-beta1.zip) to the project.
As you can see the XIFF library is very rich and it supports more or less all the features of the XMPP protocol.
In a project I worked on, some of the junior developers’ first reactions to the XIFF library and to the restful architecture you can get with the XMPP protocol was to interrupt development in order to study all the protocols and servers we were using for the project.
This reaction led me to write down a “driver” that can deal with the XIFF library and the XMPP protocol in order to avoid any panic in the development team and to prevent people from wasting time on a concept that was beyond the scope of the project itself.
Let’s think of this driver as a layer component that hides the complexity and the richness of the XIFF library to make things easier.
In order to show you how it works I created a very simple application with the following features:
• Anonymous and registered login
• Chat services discovery
• Personal chat room creation and destruction
• Room user list
• Friends request support (accept and deny)
• Messages broadcast
The user interface of this demo is quite simple and easy to understand, take a look to it on-line.
The driver is made up of several classes, events and value objects but it’s really simple to use because the two most important files you have to know are two interfaces and a class used to discover the available services
• IRealTime
• ServiceBrowser
• IChatControls
The first one is responsible for the connection to the XMPP server and for the initialization of communication between client and server.
Available methods are:
• init(port:int, resource:String):void;
// initialize the connection over a specific port and
// send the appropriate resource type the XIFF library
• connect(domain:String, anonymous:Boolean, user:User = null):void;
// connect to a specific domain using anonymous login or an User object that is made up by username and password
• disconnect():void;
// self explanatory
• keepAlive(live:Boolean):void;
// keep the connection with the server alive also
// after long period of inactivity
• connection():XMPPConnection
// return the established connection instance
• startRealtime(room:OpenFireRoomEssentials):void
// create or join an existing room
The class that implements this interface is the RealtimeManager, each instance of which can dispatch some events. To keep things simple, the class actually wraps some events defined in the XIFF library using a custom event class. Dispatched events are:
• UserAccessEvent.CONNECTED
• UserAccessEvent.LOGIN
• UserAccessEvent.LOGOUT
The ServiceBrowser class is responsible for discovering chat services, the rooms defined on each service and the details of each room.
All information is made available through a series of events. Events dispatched from the ServiceBrowser class are:
• AvailableRoomsEvent
• AvailableServicesEvents
• DetailRoomEvent
Each event provides information about the services available on the server, the rooms that are active on a specific service and the detail of a specific room (needed in order to launch the realTime method).
The last interface you should know about is the IChatControls. Methods defined by this interface are:
• updatePresence( show:String, status:String ):void;
// send to the roster the user status
• joinRoom(room:Room, jid:UnescapedJID):void;
// join a specific room and using the JID initialize the loading of the roster
// and the set up of the room
• isValidJID( jid:UnescapedJID):Boolean;
// check if the JID is valid or not
• sendMessage(message:String = null, html:String = null):void;
// send a message in the joined room, it supports both html and plain text
• sendMessageTo(text:String, tojid:EscapedJID):void;
// send a message to a specific user
• createRoom(room:Room):void;
// create a personal room
• destroyRoom(room:Room, reason:String = null):void;
// destroy the personal room the user has created
• leave():void;
// allow the user to leave the current room
• invite(userId:EscapedJID):void;
// invite a specific to the personal room
• addFriend(user:RoomOccupant):void;
// add an user as a friends to the user roster
• removeFriend( user:RosterItemVO ):void;
// remove a specific user from the friends list
• grantSubscription(id:UnescapedJID, status:Boolean = true):void;
// grant to an user the request of subscription to the friends list
• denySubscription(id:UnescapedJID):void;
// deny the subscription to a specific user
• personalRoom():Room;
// recover the personal room created by the user
• dispose();
// free the memory and the event listener
The class that implements this interface is the ChatManager, which can dispatch events in order to distribute the data recovered and managed internally, and the events are:
• FriendsInvitation.FRIEND_REQUEST_INCOMING
• FriendsEvent.LIST_RECOVERED
• FriendsInvitation.FRIEND_REQUEST_DENIED
• FriendsInvitation.FRIEND_REQUEST_ACCETPED
• FriendsInvitation.FRIEND_LIST_REMOVED
• ChatMessageEvent.GROUP_MESSAGE
• PersonalRoomEvent.ROOM_DESTROYED
• RoomUsersEvent.JOINED
• RoomUsersEvent.LEFT
• RoomUsersEvent.PRESENCE
As in the case of the RealtimeManager class, these events wrap some events defined in the XIFF library in order to keep things a little bit simpler and to prevent concepts like rosters, persistent rooms, etc. from becoming a problem during development.
Now you know everything you need to start using this driver that keeps things simpler and easier to understand.
Come back for one moment to the image that shows the user interface of our application, and let’s examine what we have to do to make it work.
In order to set up our application we have to put in place the following workflow:
• Create an instance of the IChatControls interface implementer
• Create an instance of the IRealTime interface implementer
• Define the listeners for the UserAccessEvent.LOGIN event
• Create an instance of the ServiceBrowser class in the UserAccessEvent.LOGIN handler and recover the services available through the currentServices() method
• Handle through the user interface the data propagated through the events of the ServiceBrowser class
• Invoke the joinRoom() method of the IChatControls interface implementer
Create a new Flex application, add the XIFF library to your libs folder and grab the source code of the driver you can get here www.mxml.it/tutorials/xiffdriver.zip.
First of all, define the user interface in the main MXML file of the project
<mx:Panel width="30%" title="Authenticate" left="5" top="5">
<mx:Form width="100%" id="inputForm">
<mx:FormItem width="100%" label="Authentication Method:">
<mx:ComboBox id="method" change="handleMethodChange()">
<mx:dataProvider>
<mx:Array>
<mx:Object label="Anonymous" value="ANONYMOUS" />
<mx:Object label="Plain" value="PLAIN" />
</mx:Array>
</mx:dataProvider>
</mx:ComboBox>
</mx:FormItem>
<mx:FormItem width="100%" label="Server:">
<mx:TextInput width="100%" id="server" text="{SERVER_DEFAULT}" />
</mx:FormItem>
<mx:FormItem width="100%" label="Username:">
<mx:TextInput width="100%" id="username" text="gino" enabled="false" />
</mx:FormItem>
<mx:FormItem width="100%" label="Password:">
<mx:TextInput width="100%" displayAsPassword="true" text="latino" id="password" enabled="false" />
</mx:FormItem>
</mx:Form>
<mx:HBox width="100%" horizontalAlign="right" paddingRight="18" paddingBottom="10">
<mx:Button label="Connect" id="connectButton" click="connect()" />
<mx:Button label="Disconnect" id="disconnectButton" click="disconnect()" enabled="false" />
</mx:HBox>
</mx:Panel>
<mx:Label id="userID" y="230" text="Here the uinque OF id will appear..." fontWeight="bold" left="5"/>
<mx:Label y="253" text="Available chat services" left="5" />
<mx:List id="chatServices" labelField="jid" y="273" left="5" width="30%" change="recoverChats(event)" height="100"/>
<mx:Label y="379" text="Available persistent chats" left="5"/>
<mx:List id="persitenteChats" labelField="name" change="chatDetails(event)" y="399" left="5" width="30%" height="100"/>
<mx:Label y="503" text="Room essentials information" left="5"/>
<mx:TextArea id="roomDetails" y="523" left="5" width="30%" height="100"/>
<mx:Button label="::: join the selected room :::" y="627" left="5" width="30%" click="joinRoom()"/>
<mx:Button label="::: leave the selected room :::" y="654" left="5" width="30%" click="leaveRoom()"/>
<mx:TextInput y="682" left="5" width="30%" id="roomName"/>
<mx:Button label="::: create new room :::" y="710" left="5" width="30%" click="createTemporaryRoom()"/>
<mx:Button label="::: destroy room :::" y="736" left="5" width="30%" click="destroyTemporaryRoom()"/>
<mx:Label y="10" text="Users list" right="5" fontWeight="bold"/>
<mx:DataGrid id="usersList" right="5" top="35" enabled="false" width="40%" height="150"/>
<mx:Button y="188" label="Add as a friend" click="addUserAsFriend()" right="5" enabled="false" id="addFriend"/>
<mx:ComboBox id="userStatus" dataProvider="{ChatManager.PRESENCE_VALUES}" change="updateStatus(event)" y="429" right="5" enabled="false" width="40%" />
<mx:Label y="220" text="Friends list" right="5" fontWeight="bold"/>
<mx:DataGrid id="friendsList" right="5" top="245" enabled="false" width="40%" height="150"/>
<mx:Button y="398" label="Remove friend" right="5" click="removeUserAsFriend()" enabled="false" id="removeFriend"/>
<mx:TextArea id="roller" y="460" width="40%" right="5" height="100" enabled="false"/>
<mx:HBox width="40%" y="570" right="5">
<mx:TextInput id="msg" width="80%" enabled="false"/>
<mx:Button id="send" label="send" width="20%" click="chatManager.sendMessage(msg.text);msg.text = ''" enabled="false"/>
</mx:HBox>
<mx:HBox width="40%" y="600" right="5">
<mx:TextInput id="requestFrom" width="80%" enabled="false"/>
<mx:Button id="accept" label="accept" width="20%" click="handleRequest(true)" enabled="false"/>
<mx:Button id="deny" label="deny" width="20%" click="handleRequest(false)" enabled="false"/>
</mx:HBox>
<mx:TextArea y="630" right="5" width="40%" height="60" id="requestsLog" enabled="false"/>
Next, open a script tag and define the constants used inside the application:
private const SERVER_DEFAULT:String = "wip.gnstudio.com"; private const PERSONAL_ROOMS_SERVICE:String = "conference"; private const PERSONAL_ROOM_SUFFIX:String = "presenter";
The first one represents the address of your Open Fire installation, the second is the name of the service on which personal rooms will be created and the third is the suffix that will be added to all personal room names.
Create the class members you need to store an instance of the 3 main actors of the application
private var realtimeManager:IRealtime; private var chatManager:IChatControls; private var serviceBrowser:ServiceBrowser;
and the class members needed to store the details of the room the user is going to join, the unique identifier provided by the XMPP server (inject this in the chat manager to perform all operations related to a user) and the unique identifier of the user that performs a friend request
private var roomDetailsInfo:OpenFireRoomEssentials; private var currentRequestId:UnescapedJID; private var unescapedJID:UnescapedJID;
In order to start playing with the driver classes, perform the override of the childrenCreated method and define here both instances of the IRealTime implementer and of the IChatControls implement and the event handlers needed to manage the data propagated from these classes
override protected function childrenCreated():void {
super.childrenCreated();
connectionType = "ANONYMOUS";
chatManager = new ChatManager();
chatManager.addEventListener(RoomUsersEvent.JOINED, onRoomJoin);
chatManager.addEventListener(RoomUsersEvent.LEFT, onRoomLeft);
chatManager.addEventListener(RoomUsersEvent.PRESENCE, onRoomPresence);
chatManager.addEventListener(FriendsEvent.LIST_RECOVERED, onFriendsList);
chatManager.addEventListener(ChatMessageEvent.GROUP_MESSAGE, onGroupMessageReceived);
chatManager.addEventListener(FriendsInvitation.FRIEND_ADD_NOT_SUPPORTED, onFriendsNotSupported);
chatManager.addEventListener(FriendsInvitation.FRIEND_REQUEST_INCOMING, onFriendsRequest);
chatManager.addEventListener(FriendsInvitation.FRIEND_REQUEST_DENIED, onFriendsRequestDenied);
chatManager.addEventListener(FriendsInvitation.FRIEND_REQUEST_ACCETPED, onFriendsRequestAccepted);
chatManager.addEventListener(FriendsInvitation.FRIEND_LIST_REMOVED, onFriendsListRemoved);
chatManager.addEventListener(PersonalRoomEvent.ROOM_CREATED, onPersonalRoomCreated);
chatManager.addEventListener(PersonalRoomEvent.ROOM_EXISTS, onPersonalRoomExists);
chatManager.addEventListener(PersonalRoomEvent.ROOM_DESTROYED, onPersonalRoomDestroyed);
realtimeManager = new RealtimeManager();
realtimeManager.init(5222, "xiff");
realtimeManager.addEventListener(UserAccessEvent.LOGIN, onUserLogin);
realtimeManager.addEventListener(OpenFireErrorsEvent.ERROR, onOpenFireError);
}
Let’s start exploring one by one all the methods registered as listeners in the childrenCreated method.
The onRoomJoin listener handles the UI, enabling it after user login
private function onRoomJoin(e:RoomUsersEvent):void {
usersList.enabled = userStatus.enabled = roller.enabled = msg.enabled = send.enabled = friendsList.enabled = true;
requestsLog.enabled = accept.enabled = requestFrom.enabled = deny.enabled = true;
removeFriend.enabled = this.addFriend.enabled = true;
usersList.dataProvider = e.usersList;
}
The onRoomLeft method handles the UI, disabling controls after the user has left a room
private function onRoomLeft(e:RoomUsersEvent):void {
usersList.enabled = userStatus.enabled = roller.enabled = msg.enabled = send.enabled = friendsList.enabled = false;
requestsLog.enabled = accept.enabled = requestFrom.enabled = deny.enabled = false;
removeFriend.enabled = this.addFriend.enabled = false;
usersList.dataProvider = null;
friendsList.dataProvider = null;
}
The onRoomPresence method is the handler used to get the status of a specific user, in this sample it simply shows some logs, in a real implementation this is the method in which you have to update the status of a specific user in the room user list
private function onRoomPresence(e:RoomUsersEvent):void {
trace("Current user", e.userData.jid, "status:", e.userData.show, e.userData.status)
}
The onFriendsList method is responsible for populating the list of friends (i.e. the roster)
private function onFriendsList(e:FriendsEvent):void {
friendsList.dataProvider = e.freindsList;
}
the onGroupMessageReceived method handles all messages sent against the ‘general’ chat
private function onGroupMessageReceived(e:ChatMessageEvent):void {
roller.text += "[" + e.from + " @ " + (e.lastMessage.time || "") + "]:" + e.lastPlainMessage + "\n";
callLater(scrollText, [roller]);
}
The onFriendsNotSupported method catches the notification that anonymous users cannot add another user to their friends list
private function onFriendsNotSupported(e:FriendsInvitation):void {
Alert.show("Chat not configured for friends support...", "Attention!");
}
The onFriendsRequest method handles friend requests that come from another user, storing that user’s unique identifier and updating the user interface controls
private function onFriendsRequest(e:FriendsInvitation):void {
currentRequestId = e.jid;
requestFrom.text = "Friend request from " + e.jid.bareJID + ", accept?\n";
}
The onFriendsRequestDenied method notifies the application that a friend request has been denied by another user
private function onFriendsRequestDenied(e:FriendsInvitation):void {
requestsLog.text += "Friend request from " + e.jid.bareJID + ", DENIED!!!!!!!!\n";
callLater(scrollText, [requestsLog]);
}
The onFriendsRequestAccepted method notifies the application that a friend request has been accepted
private function onFriendsRequestAccepted(e:FriendsInvitation):void {
requestsLog.text += "Friend request from " + e.jid.bareJID + ", accepted!!!!!!!!\n";
callLater(scrollText, [requestsLog]);
}
The onFriendsListRemoved method handles the event that notifies the application that a user has been removed from the friends list
private function onFriendsListRemoved(e:FriendsInvitation):void {
requestsLog.text += "Removed from " + e.jid.bareJID + ", friend list!!!!!!!!\n";
callLater(scrollText, [requestsLog]);
}
The onPersonalRoomCreated method simply gives an Alert to notify the application that the personal room has been created
private function onPersonalRoomCreated(e:PersonalRoomEvent):void {
Alert.show("Your personal room has been created....", "Attention!");
}
The onPersonalRoomExists method notifies the user that his personal room already exists and that another one cannot be created (this is not a limitation of XMPP but only a feature of the driver that doesn’t allow more than one personal room per user)
private function onPersonalRoomExists(e:PersonalRoomEvent):void {
Alert.show("Sorry, you can have only one personal room....", "Attention!");
}
The onPersonalRoomDestroyed method handles notifications that the personal room a user joined has been destroyed
private function onPersonalRoomDestroyed(e:PersonalRoomEvent):void {
Alert.show("Sorry, the room you are chatting has been destroyed....", "Attention!");
}
The onOpenFireError method handles all errors; in this sample implementation it handles only the 401 error code that means that a registered user has inserted wrong username and password
private function onOpenFireError(e:OpenFireErrorsEvent):void {
if (e.errorCode == 401) {
userID.text = "wrong credentials";
}
}
The on method handles anonymous or registered logins and initializes the ServiceBrowser instance and all the listeners needed to recover the information from this class. It’s important to note here that the realtimeManager instance is finally connected, that the keepAlive property is set to true and that the ServiceBrowser instance uses the connection to the server to start exploring available services
private function onUserLogin(e:UserAccessEvent):void {
userID.text = "logged as " + e.username;
unescapedJID = e.unescapedJID;
var serverJID:EscapedJID = new EscapedJID(e.unescapedJID.domain);
serviceBrowser = new ServiceBrowser(serverJID, realtimeManager.connection);
serviceBrowser.addEventListener(AvailableServicesEvents.SERVICES_RECOVERED, onAvailableServices);
serviceBrowser.addEventListener(AvailableRoomsEvent.ROOMS_RECOVERED, onAvailableRooms);
serviceBrowser.addEventListener(DetailRoomEvent.ROOM_DETAILS, onDetailRoom);
serviceBrowser.currentServices();
connectButton.enabled = false;
disconnectButton.enabled = true;
realtimeManager.keepAlive = true;
}
The listeners registered to the events dispatched from the ServiceBrowser are those that populate the controls of the user interface (i.e. the list of services and available rooms) and that store information about the room the user is going to join
private function onAvailableServices(e:AvailableServicesEvents):void {
e.target.removeEventListener(e.type, arguments.callee);
chatServices.dataProvider = e.currentServices;
}
private function onAvailableRooms(e:AvailableRoomsEvent):void {
persitenteChats.dataProvider = e.currentRooms;
}
private function onDetailRoom(e:DetailRoomEvent):void {
roomDetailsInfo = e.details;
}
All the building blocks needed to handle the real time communication provided through XMPP are now in place. The following code list includes all the methods called from the user interface and it’s self-explanatory: you will now be able to run the application against your Open Fire installation
private function handleRequest(status:Boolean):void {
if (status) {
chatManager.grantSubscription(currentRequestId, true);
} else {
chatManager.denySubscription(currentRequestId);
}
currentRequestId = null;
}
private function chatDetails(e:ListEvent):void {
var jid:EscapedJID = new EscapedJID(e.itemRenderer.data.jid);
serviceBrowser.roomDetails(jid)
}
private function recoverChats(e:ListEvent):void {
var jid:EscapedJID = new EscapedJID(e.itemRenderer.data.jid);
serviceBrowser.currentChatRooms(jid)
}
private function leaveRoom():void {
chatManager.leave()
}
private function joinRoom():void {
chatManager.joinRoom(realtimeManager.startRealtime(roomDetailsInfo), unescapedJID);
}
private function updateStatus(e:ListEvent):void {
var item:Object = e.currentTarget.selectedItem;
chatManager.updatePresence(item.label, item.data);
}
private function removeUserAsFriend():void {
chatManager.removeFriend(friendsList.selectedItem as RosterItemVO);
}
private function addUserAsFriend():void {
chatManager.addFriend(usersList.selectedItem as RoomOccupant);
}
private function handleMethodChange():void {
if (method.selectedItem.value != "ANONYMOUS") {
username.enabled = true;
password.enabled = true;
} else {
username.enabled = false;
password.enabled = false;
}
connectionType = method.selectedItem.value;
}
private function connect():void {
if (connectionType == "ANONYMOUS") {
realtimeManager.connect(server.text, true);
} else {
var user:User = new User();
user.username = username.text;
user.password = password.text;
realtimeManager.connect(server.text, false, user);
}
}
private function destroyTemporaryRoom():void {
if (chatManager.personalRoom) {
chatManager.destroyRoom(chatManager.personalRoom);
}
}
private function createTemporaryRoom():void {
var roomDetails:OpenFireRoomEssentials = new OpenFireRoomEssentials();
roomDetails.name = PERSONAL_ROOM_SUFFIX + roomName.text;
roomDetails.category = PERSONAL_ROOMS_SERVICE;
chatManager.createRoom(realtimeManager.startRealtime(roomDetails));
}
private function disconnect():void {
realtimeManager.disconnect();
chatManager.dispose();
connectButton.enabled = true;
disconnectButton.enabled = false;
chatServices.dataProvider = [];
persitenteChats.dataProvider = [];
usersList.enabled = userStatus.enabled = roller.enabled = msg.enabled = send.enabled = friendsList.enabled = false;
requestsLog.enabled = accept.enabled = requestFrom.enabled = deny.enabled = false;
removeFriend.enabled = removeFriend.enabled = false;
}
internal function scrollText():void {
arguments[0].verticalScrollPosition = roller.verticalScrollPosition + 8;
}
Conclusion
The real time applications are really engaging, both for the end user and for a developer. Sometimes people can be afraid of the potential difficulties in this kind of application but, as you have seen in this article, you don’t have to be a rocket scientist to be able to start playing with it.
The XMPP standard is not the only one available for the Flash Platform; the great advantage that comes with this standard is that you can handle several client side applications (developed with different technologies) with the same back end logic.
Reading Exif data with ActionScript 3.0
Jan 4th
Most of the digital cameras use Exif file format to store images and through this format tons of information is available so that each software that deals with images can show relevant data loading few bytes.
The nice thing is that in the first 64 kbytes of an image all the information, thumbnail included, are stored in separate and well organized image file directories (IFDs), this is the reason why you don’t need to load a complete image to show it’s preview (if images are smaller than 64kbytes you can get anyway the information and there is no need to close the stream of data).
There are already some resources about exif data reading in ActionScript, you can get some great examples here:
• http://code.shichiseki.jp/as3/ExifInfo/
• http://patrickshyu.com/2009/04/jpg-exif-metadata-in-actionscript-3/
I wrote my own solution because the first one load all the image before starting to parse the data, because the second one created me some issues with a Motorola image and because I get also information for exif 1.1 data.
What I’m missing and I would like to improve is the visualization of thumbnails stored not with the JPG information and the visualization of GPS information that I already get but are not shown properly.
In order to avoid the issues I have had I would like to spent few words before getting you to the source code.
First of all in order to understand the format I really started to read the specification you can get here http://www.exif.org/Exif2-2.PDF. I know that it may not seem the most amazing piece of paper to read but was the only way to put in place a solution with all the comments needed to make people able to extend and improve it.
My second step was to find a good software able to read exif data in order to make a comparison between the information recovered from the Exif class I created and the ones recovered from a professional software, I get ACDSEE (http://www.acdsee.com/).
The third step was to get a lot of sample images and thankfully the exif official web site has a lot of them (by the way I embedded the images also in the sample application I did) available here http://www.exif.org/samples.html.
The last step was to get an hexadecimal reader to really parse and count the raw data I was going to play with, on Mac I found 0xED (http://www.suavetech.com/0xed/0xed.html), on Windows I get Hex Workshop (http://www.hexworkshop.com/).
Before starting to write down my solution I studied how other people implemented working solutions in other languages, two of the most inspiring for me were this one in Java http://www.java2s.com/Open-Source/Java-Document/Web-Server/Jigsaw/org.w3c.tools.jpeg.htm and this one http://mediachest.sourceforge.net/mediautil/javadocs/mediautil/image/jpeg/package-summary.html always written in Java.
Let’s start with some clarifications …
The Exif file format is based on the JPEG file format. Exif inserts some of image / digital camera information and thumbnail image to JPEG in conformity to JPEG specification. Therefore you can view Exif formatted image files by JPEG compliant Internet browser / Picture viewer / Photo retouch software etc. as normal JPEG image files.
Every JPEG file starts from binary value ‘0xFFD8′, ends with binary value ‘0xFFD9′. There are several binary 0xFFXX data in JPEG data, they are known as ‘Marker’, and it starts a new part of JPEG information. 0xFFD8 means SOI (Start of image), 0xFFD9 means EOI (End of image). These two special Markers have no data following, the other markers have data with it.
The marker 0xFFE0~0xFFEF is named ‘Application Marker’, not necessary for decoding JPEG image. They are used by user application. For example, older olympus / canon / casio / agfa digital camera use JFIF (JPEG File Interchange Format) for storing images. JFIF uses APP0 (0xFFE0) marker for inserting digital camera configuration data and thumbnail image.
Exif format contains a thumbnail of the image (except Ricoh RDC-300Z). Usually it is located next to the IFD1. There are 3 formats for thumbnails; JPEG format (JPEG uses YCbCr), RGB TIFF format, YCbCr TIFF format. It seems that JPEG format and 160×120 pixels of size are recommended thumbnail format for Exif2.1 or later. By the DCF specification, thumbnail image MUST use JPEG format and image size is fixed to 160×120 pixels. If the value of Compression (0×0103) Tag in IFD1 is ‘6′, thumbnail image format is JPEG. Most of Exif image uses JPEG format for thumbnail. In that case, you can get offset of thumbnail from JpegIFOffset (0×0201) Tag in IFD1, size of thumbnail from JpegIFByteCount (0×0202) Tag. Data format is ordinary JPEG format, starts from 0xFFD8 and ends by 0xFFD9.
The following terms and notation are used as follows in the exif standard:
• “Tag” is used as a synonym of “field”,
• “.H” appended to a numerical value means it is hexadecimal notation,
• Unless otherwise indicated, other numerical values are given in decimal notation,
• The initial IFD in a file is the “0th IFD,” with the next IFD being called the 1st IFD
• The term Primary image refers to main image data
• The term Thumbnail indicates a small image used to index the primary image
• Exif is an abbreviation of Exchangeable image file format, used here as the general term for this standard and earlier versions of this standard
The main class of this solution is named Exif and contains all the exif tag uint values as class constants and a bunch of methods used to expose the data to the end user (i.g. the developer that use it in a project) and other methods to parse the information
The class extends the URLStream class so what you have to do in order to use it is creating and instance and load a valid URLRequest through it.
The events dispatched from the Exif class you have to aware of are
• PARSE_COMPLETE
• PARSE_FAILED
• PARSING_ERRORS
• DATA_READY
• THUMBNAIL_READY
The first one is fired when the data are parsed completely, the second one indicates that a serious error happened (i.g, not a valid jpg, not valid exif data, etc.), the third one can be used to handle not serious errors (i.g. a tag is not properly recorded), the fourth one indicates that the exif data have been completely parsed and the last one is the event that inform you that the thumbnail is ready.
The public API can be used in order to get the thumbnail, the error logs, all the IFD recovered from the class and the amount of data loaded in order to parse the exif data.
The class usage is quite simple but the logic inside is a little bit more complex, in fact the core consists of two methods
• exploreEntries
• parseTag
The first one is the one that read all the entries (i.g. tags) stored in an IFD and that collaborates with the parseTag method in order to read the data as defined in the exif specification and with the Naming class used to handle a lot of situations like flash, orientation, etc. making these values human readable.
The following types are used in Exif (you see this types recovered in the first lines of the exploreEntries method):
• 1 = BYTE An 8-bit unsigned integer.,
• 2 = ASCII An 8-bit byte containing one 7-bit ASCII code. The final byte is terminated with NULL.,
• 3 = SHORT A 16-bit (2-byte) unsigned integer,
• 4 = LONG A 32-bit (4-byte) unsigned integer,
• 5 = RATIONAL Two LONGs. The first LONG is the numerator and the second LONG expresses the
denominator.,
• 7 = UNDEFINED An 8-bit byte that can take any value depending on the field definition,
• 9 = SLONG A 32-bit (4-byte) signed integer (2’s complement notation),
• 10 = SRATIONAL Two SLONGs. The first SLONG is the numerator and the second SLONG is the
denominator.
The Naming class can be passed to the Exif class in the constructor so that you can easily create your localized version of exif reader overriding the methods that initialize some arrays used to store values for the flash, the orientation, the exposure, etc.
Each time and IFD is found in the file the exif class create an IFD instance so that you can easily keep track of them and create customized helper classes to parse all these information, each time a valid exif tag is defined an instance of the ExfTag class is created, thorugh this class you can easily know the name and the value of a tag, use the public getTagValue method passing as an argument one of the 130 and more constants defined in the Exif class.
All these classes are available inside nabiro, the open source ActionScript library made up of a lot of components created during our daily job published here http://agile.gnstudio.com/nabiro.
Sample Usage
At the end of this post you find the sample application with the source code include, byt the way in order to use this tool you only need to instantiate the class, define a couple of event listeners and load a file
exif = new Exif(); exif.addEventListener(Exif.PARSING_ERRORS, onParsingErrors); exif.addEventListener(Exif.DATA_READY, onExifDataRecovered); exif.addEventListener(Exif.THUMBNAIL_READY, onThumbnailReady); exif.load(new URLRequest(images.selectedItem.data));
The three event listeners populate a text area with the error log message, display a list of available data and load the image, so you can easily get this result
Download here the source and the application and please feel free to use it as you want but please provide me as much as possible your feedback.
