B-tree and Binary Search Tree Data Structures

B-tree and Binary Search Tree data structures are similar but different ways to store data. The advantage of using search trees is that the test for membership can be performed efficiently provided that the tree is reasonably balanced, that is, the leaves of the tree are at comparable depths.

B-tree Implementations

B-tree implementations are normally commercial. Languages don't typically provide direct B-tree support. To find B-tree implementations, search Google for B-tree software.

Binary Search Tree Implementations

Some languages do provide support for Binary Search Trees. In Java, see the TreeMap class, which implements a variant of the Binary Search Tree, the Red-Black Tree.

Binary Tree Data Structure Comparison

Both structures operate in the average in O(log n) time. Note that in the worst case, B-tree, at O(log n), is faster than Binary Search Tree at O(n).

P Versus NP Complexity Theory

The P Versus NP issue deals with whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. This is a major unsolved problem in computer science.

In common, practical terms, it deals with how to identify problems that are either extremely difficult or impossible to solve.  In order of difficulty from easy to hard, problems are classified as P, NP, NP-Complete and NP-Hard.

So why do we care? When approaching complex problems, it's useful to have at least some idea of whether the problem is precisely solvable, or if an approximation is the best that can be accomplished. 

Android WebView Combines Native and HTML5 Code

A battle is raging over whether native mobile code apps, such as those for Android and iOS, are a better approach than using HTML5.  Each has its advantages.

There is, though, a way to blend the two in order to take advantages of the benefits each has to offer.  The graphic below shows the anatomy of an app that displays an HTML5 Canvas on an Android screen display.

This app is from the Learning Android App Programming video training course.

The HTML5 Canvas animation displayed is from HTML5 Canvas for Dummies.

You can see the HTML5 Canvas animation by clicking here. To see the JavaScript code that generates the animation, right click on the display page and select View Source Code.

Creating a 3D Effect in 2D HTML5 Canvas Games

HTML5 Canvas doesn’t include a built-in 3D context. Without using an add-on product such as WebGL (www.khronos.org/webgl), 3D has to be simulated using the 2D context.

Some games require the sophistication of a true 3D engine like WebGL. However, many games built using the Canvas 2D context can be significantly enhanced by simulating aspects of 3D motion.

In the Ballpark sample game from HTML5 Canvas for Dummies, the thrown baseball is simulated moving away from the ball thrower toward the ball player along a simulated z axis third dimension. The z axis 3D effect is accomplished by decreasing the size of the baseball in proportion to it's movement upward along the 2D y axis.

You can play the game yourself by clicking here.  To see the full code, right click on the game web page and select View Page Source.

To simulate 3D movement using this technique, the following steps were used:

1.    Assign a z axis variable to each new object.

Along with the xPos and yPos variables, assign a zPos variable as in code section S2 assignments for baseballs:

     ball[b].zPos = zStart;

2.    As the object moves, update the z position.

In the sample game, in code section R8, the z position is calculated based  on the y axis position (yPos) and a z sizing factor (zSizeFact):

     var newZPos  = (ball[b].yPos/canvasBL.height) * zSizeFact;

     ball[b].zPos = newZPos;  

3.    Fix the z position under specified conditions.

In the sample game, the baseball is simulated to move along the z axis only away from the ball thrower. Also, to simplify the simulation, only movement up the y axis is used to increase z axis movement. So, when the ball starts to move down on the y axis, the z position is fixed. This code is in sections R9-R12:

     // FIX Z position of zFix is greater than zero.      

     if(ball[b].zFix > 0)  {ball[b].zPos = ball[b].zFix};

     // Z FIX check for not already set.

     if(ball[b].zFix == 0)

     {   // Z FIX conditions check. 

        var newYPos  = ball[b].yPos;

        if(((newYPos > curYPos) || (ball[b].bounce)) && (curYPos < zFixMaxY))

        {  // FIX Z POSITION at current level and no smaller than minSize.

           ball[b].zFix = Math.max((curYPos/canvasBL.height)*zSizeFact, minSize);   }   }

Using Randomized Variable Values to Enhance HTML5 Canvas Animations

The HTML5 Canvas feature is bringing additional animation power to web pages.  HTML5 Canvas allows web developers to embed sophisticated bit map animated graphics directly into web pages. 

In developing examples for my book on HTML5 Canvas (HTML5 Canvas for Dummies) I experimented with using randomized variable values to improve the realism of an animated fireworks display. I used random values within specified ranges for parameters such as fireworks colors, number of exploding particles, trajectory of particles, lifespan of particles and flight trajectories. I found that adding well constructed values (not too much or too little randomization) significantly increased the realism and appeal of the results.  Here's one example from the Fireworks app of setting a randomized value:

     part[newPart].life = lifeMin +(Math.random()*(lifeMax-lifeMin));

See what you think ... click here to see it in action.

HTML5 vs. Native App Development

As you're likely aware, there's a big debate going on about whether HTML5 web sites are a better platform for mobile apps than native code development using Android, iOS and Windows.

The main selling point for HTML5 is the write-once-run-anywhere advantage. Web browsers on mobile devices can access web sites from any mobile platform. HTML5 is providing features that allow web page JavaScript code to access phone features like devices sensors and geo positioning. In theory, a well constructed HTML5 web page will look and perform like a mobile device native code app.

However, currently not all device features are available to HTML5 JavaScript code and native code apps have a performance advantage over HTML5 web pages viewed using a browser. Native code apps are presently the dominant choice among developers.

In HTML5's corner, though, the technology is improving and web browsers are ramping up their implementation of HTML5 features. Life would certainly be simpler for mobile developers if they could develop for only one platform, HTML5, instead of multiple native platforms.

Longer term, HTML5 will certainly continue to get better. But so will native platforms. In fact, native platforms may improve more rapidly than HTML5. HTML5 is a global standard developed by the W3C. It takes years of effort to change the standard and have these changes adopted by the various browsers. The individual native platforms (Android, iOS, Windows) can change as quickly as their developers (Google, Apple and Microsoft) want them to. So will HTML5 ever catch up?

Maybe not. Google, Apple and Microsoft have lots of developers and big budgets. They want their products to be competitive ... and that means constant improvements.

So, what's likely to happen? In my opinion, we'll have a blend of the two. In fact, this is taking place today. Native code platforms have Application Programming Interfaces (APIs) that support displaying web pages from within native code apps. Developers can use native code for what it does best and HTML5 web pages for what they do best. The exact mix will shift over time as all the platforms change and improve. 

For developers, this means that separate native code platforms will likely continue to exist. Write-once-run-anywhere will remain an elusive goal probably not realized for a long time, if ever. This doesn't mean that development costs can't be managed or reduced. HTML5 web pages can be developed and used by native code apps where appropriate. Functions specific to those pages can be write-once-run-anywhere. This may not be an optimal solution, but it's the game on the ground.

Smartphone Website with Laptop 2.png

WebPlatform.org: A Resource for Web Development

WebPlatform.org is a new organization and collection of websites that will provide open source resources for web development. It will cover topics such as HTML5, Canvas, SVG, Video, Animations, IndexedDB, CSS, WebGL, Transforms, Audio, Media Queries and FileAPI.

Which is the Best Browser

An analysis of Internet browsers by Top Ten Reviews places Google Chrome at the head of the list. The analysis shows, however, that it's a real horse race between the top five: Chrome, Firefox, Internet Explorer, Opera and Safari. Here are some of my observations based on this analysis and personal tests and experience:

Change after new releases: All of the browser developers are working hard to improve their products. With each new browser version release, the competitive landscape can change. For example, Internet Explorer had recently lagged in speed due to the lack of graphics hardware acceleration. Based on my tests, they're now the fastest running HTML5 Canvas animations.

Graphics hardware acceleration: GPU (Graphics Processing Unit) hardware acceleration is an important factor in browser speed. A browser displaying video or animation with GPU acceleration will outperform a browser without it by a factor of 3-4. That's right, 300-400%. A computer using just the CPU to manipulate graphics displays simply can't keep up with one using the combination of CPU and GPU. Hardware acceleration is a fairly complex topic. Basically, the browser offloads calculations from the CPU to the GPU. If you're interesting in some of the details, take a look at this discussion of hardware acceleration from the Chromium Projects.

Mobile lags desktop: Especially in speed, the mobile browsers lag desktop versions. Mobile devices simply don't have the computing power to match desktop devices. 

HTML5 Status

Transient

The World Wide Web Consortium (W3C) has announced that a final recommendation for HTML 5.0 will be released in the 4th quarter of 2014. In spite of the "recommendation" terminology that W3C uses, this is official release of HTML5. This is a big deal and great news. Browser developers will have a firm definition of HTML5 they can use to bring their products up to a complete level of support for this latest version of HTML.

W3C has also defined the follow-on version, HTML 5.1, to be released in the 4th quarter of 2016. This release will include features that have been pushed out in order to get release 5.0 completed in 2014. Without this stragegy, W3C was looking at an indefinite specification development timeframe. 

Browser developers are not waiting for 2014 to begin implementation of HTML5. You can use www.html5test.com to check the status of your browser to see which features are supported and www.caniuse.com for a summary of the status of support by all the major browsers.

What is HTML5 Canvas?

HTML5 Logo.png

The Canvas feature of HTML5 is one of the most exciting new developments in web based capabilities in many years. Here are some key aspects:

HTML5 - Canvas is a part of the latest revision and improvement of the previous version (HTML4, released in the late 1990's) markup language for displaying web pages on the Internet.

Canvas Tag - The <canvas> tag joins the other HTML tags (there are around 100 now) as a way to include single or multiple Canvas areas on a web  page. 

Bit Map DisplayThe Canvas area you define with a <canvas> tag is a bit map display. You can manipulate individual pixels to draw objects, images, animations and video.

JavaScript ControlThe JavaScript language is used to control what is seen on the Canvas. The JavaScript application code is placed between the <head></head> and <script></script> tags of the web page.

Browser Based - The computing needed to create a Canvas display is done within the browser. In other words, it's client based, not server based. The means that creating a Canvas application is simpler than one requiring server based programming. It also means that the computing power needed to generate the Canvas display is not concentrated in single servers. Each user's browser handles its own work.

Animation - Canvas applications can generate animations. This is accomplished using callbacks from the browser. The Canvas application designates one of its functions to be called from the browser at specified time intervals. During each of these callbacks, the application draws a new Canvas display, moving objects slightly. When viewed as a continuous flow of Canvas displays, an animation is generated.

Audio/Video - Audio and video can be incorporated into your Canvas applications. Moving objects can create sounds and video images can be melded into other application objects. This is done without the use of any audio or video plugins.

Gaming - Game developers have all to tools necessary to create compelling HTML5 Canvas games.

Fun - Putting aside the technical aspects of Canvas ... it can be described as just plain fun. An HTML5 Canvas is a place where as a developer you can express your creative energies and as a user you can have expanded and enjoyable experiences.

For a more details look at HTML5 Canvas, watch for my upcoming book: HTML5 Canvas for Dummies.

Integrating Audio with HTML5 Canvas

One of the useful features of HTML5 Canvas is the ability to integrate audio, either with or without an audio player. Click here or on the image to see if it works on your browser ... click on my dog Daisy and/or the pelican to test simultaneous sounds.

When the new browser window opens, you can view the page source to see the code that generates the Canvas display.

This is one of the sample applications from HTML5 Canvas for Dummies.

HTML5 Canvas Performance Test

Browser support for HTML5 Canvas is constantly improving. More features are being supported and performance is improving. Click here or on the image below to see how your browser performs. The app rotates a ten layer gradient and displays the Frame Rate.

HTML5 Canvas on a Smartphone

HTML5 Canvas is a highly anticipated feature that allows web developers to create sophisticated graphics on their website pages. Most desktop and laptop browsers now support the Canvas feature. Mobile browsers are catching up. To see if your browser supports Canvas, you can access www.html5test.com for an analysis and rating of your browser.  Also, give this Canvas app a try: