June 30th, 2009 in Uncategorized | No Comments »
Here is implementation of level order traversal of a binary tree.
Level order traversal is nothing more than traversing each level at a time
10 Lev 1
/ \
9 15 Lev 2
/ / \
7 12 17 Lev 3
Output
10 9 15 7 12 17
AVL Tree example
++++++++++++++++++++++
69: 29 77
29: 15 48
15: 5 23
5: 3 11
11: - 14
23: 16 26
16: - 18
48: 33 64
33: 32 46
64: 50 68
77: 72 84
72: 71 76
84: 80 89
80: 79 82
89: 87 93
++++++++++++++++++++++
The level order result is:
++++++++++++++++++++++
69 29 77 15 48 72 84 5 23 33 64 71 76 80 89 3 11 16 26 32 46 50 68 79 82 87 93 14 18
++++++++++++++++++++++
Implementation
/**
* Implementation of Level order traversal
* Prints nodes at each level left to right
*/
template <class Record>
void AVL_tree<Record>::level_order() {
cout << "++++++++++++++++++++++" << endl;
if(this->root == NULL){
cout << "EMPTY TREE" << endl;
}else{
cout << endl;
queue<Binary_node<Record>*> nodeQueu;
nodeQueu.push(this->root);
while(!nodeQueu.empty()){
Binary_node<Record>* entry=nodeQueu.front();
cout<<entry->data<<" ";
if(entry->left != NULL){
nodeQueu.push(entry->left);
}
if(entry->right != NULL){
nodeQueu.push(entry->right);
}
nodeQueu.pop();
}
}
cout << "\n++++++++++++++++++++++" << endl;
}
Complexity
Running time complexity of this algorithm is O(n) since every node will have to be explored
June 18th, 2009 in Uncategorized | No Comments »
Sometimes we like to see whats going on under the hood of jsf application (Checkout my JSFConsole). One such task is being able to display all the registered managed-beans during runtime.
Here we can see all registered beans, including implicit object(cookie,header,param etc…)
Result
a4j
a4jSkin
ajaxContext
ajaxHandler
application
applicationScope
beeHive --- My Managed bean
cookie
facesContext
header
headerValues
initParam
param
paramValues
request
requestScope
richSkin
session
sessionScope
view
Source
/**
* Retrieve all registered beans for given {@link ScopeType}
* @param scopeType to search in
* @return List of beanNames
*/
public static List<String> getRegisteredBeans(ScopeType scopeType){
FacesContext facesContext=FacesContext.getCurrentInstance();
ApplicationAssociate application = ApplicationAssociate.getInstance(facesContext.getExternalContext());
BeanManager beanManager = application.getBeanManager();
Map<String, BeanBuilder> beanMap=beanManager.getRegisteredBeans();
Set<Entry<String, BeanBuilder>>beanEntries=beanMap.entrySet();
List<String> registeredBeans=new ArrayList<String>();
for(Entry<String, BeanBuilder> bean:beanEntries){
String beanName=bean.getKey();
if(!beanManager.isManaged(beanName)){
continue;
}
BeanBuilder builder=bean.getValue();
Scope bScope=builder.getScope();
if(scopeType==ScopeType.ALL || bScope.toString().equals(scopeType.toString())){
registeredBeans.add(beanName+":"+bScope.toString());
}
}
if(scopeType==ScopeType.ALL || scopeType==ScopeType.IMPLICIT){
List<String> implicitList=getProperties(new ImplicitObjectELResolver(), null);
for(String implicitBeanName:implicitList){
registeredBeans.add(implicitBeanName+":"+ScopeType.IMPLICIT.toString());
}
}
Collections.sort(registeredBeans);
return registeredBeans;
}
ScopeType is nothing more than an emun wrapper
/**
* Scope type with additional properties for all/implicit
* @author devil
*
*/
public enum ScopeType {
//Really not a scope but a marker
ALL("all"),
IMPLICIT("implicit"),
REQUEST("request"),
SESSION("session"),
APPLICATION("application");
String scope;
ScopeType(String scope) {
this.scope = scope;
}
public String toString() {
return scope;
}
/**
* Get Enum from value
* @param name
* @return
*/
public static ScopeType fromValue(String name) {
name=name!=null?name.toUpperCase():"";
for(ScopeType v:values()){
if(v.name().equals(name)){
return v;
}
}
//By default return all scoped objects
return ScopeType.ALL;
}
}
June 18th, 2009 in android, java | 13 Comments »
Sorry it took little longer than expected, run in some issues with cupcake (SDK 1.5)
I have attached a Demo project for all interested with some screenshots and modified .project for TabWidget Project(fixes cupcake problem ref http://groups.google.com/group/android-developers/browse_thread/thread/5537ae10e4143240) if you use eclipse.
1. My env:
Eclipse Version: 3.4.2
Android SDK 1.5
Windows
2.After you import the TabWidgedDemo project you will probably need to fix your buildpath.
Make sure to add TabWidet as a reference to TabWidgedDemo.
3.In TabWidged project you will need to update the .project file otherwise you will get Verify error when deploying to the device.
If you have any questions let me know, I hope you enjoy the project, more improvements to come
Download tabwidgetdemo for eclipse
June 9th, 2009 in Uncategorized | No Comments »
Problem
When we add default constraint on a field it is automatically assigned a name in following format
Format:
DF__tablename__PARTOFFIELDNAME__HASHCODE
Example:
DF__scheduled__CREAT__00DF2177
DF__scheduled__MODIF__01D345B0
HashCode part of the format is different on each database so we can’t just find the name of constraint and use that in our alter script. That’s when sysobjects table comes to the rescue.
This will list all the default field values for all tables
SELECT OBJECT_NAME(ID) AS NameofConstraint,
OBJECT_NAME(parent_obj) AS TableName
FROM sysobjects
WHERE xtype = 'D'
from here we can construct our TSQL script to suit our needs.
Solution
- Get default fields of interes t(ConstraintName, TableName)
- Drop each constraint
- Add new default constraint with a NAME
/**
@Desc: Remove default constraints from a given table, then add new default constraint
2000/2005 compatible
@Author Greg B.
**/
USE [mydb]
GO
BEGIN TRANSACTION
GO
Declare MyCursor Cursor FOR
SELECT OBJECT_NAME(ID) AS NameofConstraint,
OBJECT_NAME(parent_obj) AS TableName
FROM sysobjects
WHERE xtype = 'D'
AND (OBJECT_NAME(parent_obj) = 'procedures' AND OBJECT_NAME(ID) LIKE '%DF__procedure__INHER%')
OR
(
OBJECT_NAME(parent_obj) = 'subarea'
AND (OBJECT_NAME(ID) LIKE '%DF__subarea__ABS_INH__%')
OR (OBJECT_NAME(ID) LIKE '%DF__subarea__ASSIGNE__%')
)
DECLARE @SQLScript NVARCHAR(300)
Declare @NameofConstraint VARCHAR(255)
Declare @SchemaName VARCHAR(255)
Declare @TableName VARCHAR(255)
Declare @ConstraintType VARCHAR(255)
Open MyCursor
Declare @Count int
SELECT @Count = 0
FETCH NEXT FROM MyCursor INTO @NameofConstraint, @TableName
WHILE @@FETCH_STATUS = 0
BEGIN
--PINT 'RECORD='+@NameofConstraint +' :: '+@TableName
SELECT @SQLScript= 'ALTER TABLE '+ @TableName +' DROP CONSTRAINT '+@NameofConstraint
EXEC sp_executesql @SQLScript
SELECT @Count=@Count+1
--Advance to next record
FETCH NEXT FROM MyCursor INTO @NameofConstraint,@TableName
END
Close MyCursor
DEALLOCATE MyCursor
IF @Count != 0
BEGIN
print 'Adding alter'
-- Now we add the constrains back again to the tables with standarized names
ALTER TABLE [dbo].[procedures] ADD CONSTRAINT DF_PROCEDURE_INHERENT_RISK DEFAULT ((1)) FOR [INHERENT_RISK]
ALTER TABLE [dbo].[subarea] ADD CONSTRAINT DF_SUBAREA_ABS_INHERENT_RISK DEFAULT ((1)) FOR [ABS_INHERENT_RISK]
ALTER TABLE [dbo].[subarea] ADD CONSTRAINT DF_SUBAREA_ASSIGNED_INHERENT_RISK DEFAULT ((1)) FOR [ASSIGNED_INHERENT_RISK]
END
COMMIT TRANSACTION
IF @@TRANCOUNT > 0
BEGIN
ROLLBACK TRAN
END
GO
June 9th, 2009 in Uncategorized | No Comments »
PhaseListener designed to serve resources like css, javascript, images, pdf etc.. from jar file
ResourcePhaseListener.java
All required files can be downloaded here.
package com.gregbugaj.jsfdump.console;
import java.io.IOException;
import java.io.InputStream;
import java.util.HashMap;
import java.util.Map;
import javax.activation.MimetypesFileTypeMap;
import javax.faces.context.FacesContext;
import javax.faces.event.PhaseEvent;
import javax.faces.event.PhaseId;
import javax.faces.event.PhaseListener;
import javax.servlet.ServletOutputStream;
import javax.servlet.http.HttpServletResponse;
import org.w3c.dom.Document;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
import com.gregbugaj.jsfdump.util.JarUtil;
import com.gregbugaj.jsfdump.util.XMLUtil;
/**
* Serve resources from jar file back to the user by specifying resource name in resource-config.xml
*
* This works with following syntax if faces servlet is *.jsf /jsfdump/resource/script.js.jsf
* or /jsfdump/resource/script.js if faces servlet is *.*
*
* @author devil
*
*/
@SuppressWarnings("serial")
public class ResourcePhaseListener implements PhaseListener {
//This is how the resource will be accessed ex /jsfdump/resource/script.js
private static final String RESOURCE_PREFIX = "/jsfdump/resource/";
//Location of where the js, img, css etc files reside inside the jar, we could also placed them in META-INF folder
private static final String RESOURCE_PATH = "/com/gregbugaj/jsfdump/resources/";
private static Map<String, String> resources=new HashMap<String,String>();
private boolean isLoaded;
@Override
public void afterPhase(PhaseEvent event) {
FacesContext facesContext=event.getFacesContext();
String rootId=facesContext.getViewRoot().getViewId();
//Clean up key
String key=rootId.replace(RESOURCE_PREFIX, "");
key=key.replace(".xhtml", "");
key=key.replace(".jsf", "");
if(!rootId.startsWith(RESOURCE_PREFIX)){
return;
}
//Lazy loading
if(!isLoaded){
isLoaded=initResources();
}
String resourceName=resources.get(key);
//Location of resources inside the jar file
String fileName=RESOURCE_PATH+resourceName;
InputStream resourceStream=JarUtil.getStreamFromJar(fileName);
HttpServletResponse response = (HttpServletResponse) facesContext.getExternalContext().getResponse();
response.setCharacterEncoding("UTF-8");
ServletOutputStream sos = null;
try {
sos = response.getOutputStream();
if(resourceStream!=null){
response.setStatus(HttpServletResponse.SC_OK);
//Resolve mime type, required that we have activation.jar loaded
//Additional mime types can be defined in /META-INF/mimes.types {@link http://java.sun.com/j2ee/sdk_1.3/techdocs/api/javax/activation/MimetypesFileTypeMap.html }
String contentType = new MimetypesFileTypeMap().getContentType(fileName);
response.setContentType(contentType);
byte[] buffer= new byte[1024];
for (int bytesRead = 0; (bytesRead = resourceStream.read(buffer, 0, buffer.length)) > 0;)
{
sos.write(buffer, 0, bytesRead);
}
}else{
//Resource not found
response.setStatus(HttpServletResponse.SC_NOT_FOUND);
response.setContentType("text/html");
}
sos.flush();
sos.close();
} catch (IOException e) {
e.printStackTrace();
}
facesContext.responseComplete();
}
@Override
public void beforePhase(PhaseEvent event) {
//Do nothing
}
/**
* Load resource mapping from resource-config.xml
* @return true if we successfully loded resource
*/
private boolean initResources() {
boolean retVal=true;
InputStream stream=null;
try {
stream=JarUtil.getStreamFromJar("/META-INF/resource-config.xml");
Document document=XMLUtil.getXmlDocument(stream);
NodeList resourceNodes=XMLUtil.extract("/resources/resource", document);
for(int i=0;i<resourceNodes.getLength();i++){
Node node=resourceNodes.item(i);
String name=XMLUtil.attributeText(node, "name");
String src=XMLUtil.attributeText(node, "src");
//No forward slash in the resource name
//ex js/scriptname.js not /js/script.js
if(src.startsWith("/")){
src=src.replaceFirst("/", "");
}
resources.put(name, src);
}
} catch (IOException e) {
retVal=false;
e.printStackTrace();
}
catch (Exception e) {
retVal=false;
e.printStackTrace();
}
return retVal;
}
@Override
public PhaseId getPhaseId() {
return PhaseId.RESTORE_VIEW;
}
}
resource-config.xml
This is where we define resources that we will be serving. One reasons we use xml configuration is to prevent security breaches.
<?xml version="1.0" encoding="UTF-8"?>
<resources>
<resource name="proto.js" src="js/proto.js" />
<resource name="logo.png" src="images/a.png" />
<resource name="main.css" src="css/hello.css" />
</resources>
Two common ways to access the resources are
If faces servlet is *.jsf /jsfdump/resource/script.js.jsf
Of /jsfdump/resource/script.js if faces servlet is *.*
META-INF/mime.types
This is where we add additional mime types, requires that we have activation.jar loaded More info
This file is not required but it helps, for example png files resolve to application/octet-stream rather than image/x-png
Examples