Software Architecture Structures

This post talks about the Software Architecture Structures, and how these structures relate in the creation of an architecture. Software Architecture Structures can be divided into 3 broad categories

1) Modules

2) Component and Connectors

3) Allocations

1) Modules -- These are the units of implementation. These represent code based views of the system. The intent here is not related to any runtime considerations. Module based structures can be further sub-divided into

1. Decomposition --The units addressed here are that of submodules of a particular module. The intent is to break modules into smaller units such that each unit can be understood. This normally is the starting point of high level design and subsequent low level design. It also incorporates things like implementations, test plans etc. In addition a decomposition can also address questions related to changes made to the system. The intent should be to keep the changes local to a few sub-modules.
2. Uses -- One unit uses another if the correctness of one depends on the existence of the correct version of another. The uses structure can be used to extend the capabilities of a system as well as extract subsets of functionality which can be used for incremental development
3. Layered -- When the Uses structure is carefully modeled, normally layers emerge. These layers are areas of common functionality. Layered structures can be used to assess the dependence of one layer on the other as well as ensuring that the interactions of one layers are only with the layers above or below this layer. In addition, a layer at n should only depend for services on the n-1 layer and none other.
4. Class or Generalization -- The units in this structure are classes. Classes can be used to reason about collection of similar behavior or capabilities. Class structures is used for assessing reuse and incremental addition of functionality.

2) Components and Connectors --Component-and-connector structures help answer questions such as What are the major executing components and how do they interact? What are the major shared data stores? Which parts of the system are replicated? How does data flow through the system? What parts of the system can run in parallel? How can the system's structure change as it executes? These can be further sub-divided into

1. Processes --The process structure shows processes connected to each other through connectors, snychronizers,exclusions etc. This structure is important when looking at a systems performance and availibility.
2. Concurrency -- This structure allows for determining the areas where there can be a resource contention or where parallelism can be employed.
3. Shared data -- This comprises connectors and components that create,store or access shared persistent data. It shows how data is produced and consumed by the runtime components and can be used to ensure performance and data integrity.
4. Client -Server -- This structure shows the components as client server units and the connectors are the underlying protocols which are used for communication.

3) Allocation Structures -- This structure shows the relation between the software elements and the environment in which the software executes. These can be classified as follows

1. Deployment -- The deployment structure shows how software is assigned to hardware-processing and communication elements. The elements are software, hardware entities and communication pathways. Relations are allocated-to, showing on which physical units the software elements reside. This view allows one to reason about performance, data integrity, availability, and security.
2. Implementation --This structure shows how usually modules are mapped to the file structure in the system's development, integration, or configuration environments. This is critical for the management of development activities and build processes

Kickstarting your day and honing your development skills

As per various studies conducted, it has been shown that developers tend to take at least an hour or more to get into the zone, where they are most productive. There are various ways which have been suggested like writing unit tests at the start if the day,etc. to get into the zone. Being a pragmatic programmer, i have found something which has helped me kick-start my day and get into the zone in the minimum time possible. The following recipe has done wonders for me.
At the start of the day, i take up a puzzle and spend 5-10 minutes in analyzing and solving it. Be aware the intent is not to come to a solution, but just to get the gray cells kicking. After this i normally try some programming problem, albeit a simple one using a new language which i am trying to acquire. I spend another 20-30 minutes in solving the problem. The problem could be as simple as trying to find a repeated integer in a list of otherwise unique sequential numbers. Getting these two activities at the start of the day has two-fold advantages. One it focuses the brain and secondly it helps me acquire a new skill. I have even tried using this after prolonged meetings just to get back into the zone. However a word of caution, the intent is not to get to perfection, but to time-box the effort. You can get back to the problems again the next day if you are stuck on something.

Regular Expressions Part 2

This entry continues the discussion regarding regular expressions from the previous post(Regular Expression part 1). We continue with a discussion of the rich meta-characters available. In this post i will take up some of the other meta-characters and discussion their usage. The pattern followed is the same as the previous post with some exercises thrown in for good measure.

• Optional Items -- Suppose we wanted to search for the word June, which could be represented as either June or Jun. The ? meta-character means optional. So the search could be accomplished using June?. This can be interpreted as match J, then u then n followed by e if its there. So the ? is placed after the character that is allowed to appear at that point in the regular expression, but the existence isn't required to consider it a successful match. Expanding on the same lets say we have to match June 5th, which can occur as Jun 5, June 5th, or fifth. To match the following we can use (June|Jun).(5|5th|fifth). The first expression can be simplified as (June?) and the second one as fifth|5(th)?. Hence the complete expression can be re-written as June?.(fifth|5(th)?). One point here is that although there are different alternatives, choosing the right one needs some thought and introspection.
• Repetition -- The + and * meta-characters are used for checking for repetition. + implies one or more of the preceding character and * implies any number including none of the item. Thus + fails if there are none of the characters but succeeds for one or many, * on the other hand always succeeds. As an example, to match spaces, one can use . ? which would match a single optional space, . + would match any number of spaces with at least one space and . * would match any number of spaces, if present. Lets take another example, where we have to search for the html tag &lt;hr size="10"&gt;. To build the regular expression, we need to have<, then HR followed by one or more spaces(allowed as per the semantics of html), followed by zero or more spaces, followed by = followed by zero or more spaces the number 10 , again zero or more spaces followed by >. Based on our discussion so far, this should be simple, Now lets try and generalise this to any size, not just 10, so the regular expression would look like For case insensitive search using egrep, we can use the -i option.
  

Exercise -- Write a regular expression for the same examplem as above, where the size attribute is optional e.i a simple

---

is a legal match.

• Back References -- Many tools provide the ability for parentheses to remember text matched by the sub-expression they invoke. So as an example, ([a-z])([0-9])\1\2, \1 refers to the text matched by [a-z] and \2 refers text matched by [0-9]. We will see examples of using back-referencing in following posts.
  
• Escapting Meta-characters -- In order to escape meta-characters, we can use \ to escape the meta-character. For example if we tried to match att.com, it could end up matching something like watt company. So we need to escape the meta-character . , this can be done using att\.com. This escapes the meta-character and treats the meta-character . like a normal character

This covers some of the most important meta-characters. In future posts i would expand on these fundamentals and show how applying regular expressions makes life simpler.

Regular Expressions Part 1

I have been a great fan of using regular expressions for solving day to day tasks. I thought it was time to post a series for discussing the use and syntax of regular expressions. In this post i will talk about some simple meta-characters and their uses with tools like egrep/grep. In addition i will try and set some small exercises to practice the understanding of the readers.

A regular expression is composed of a set of meta-characters like *, ^ etc and a set of literal characters like A-Z, a-z, 0-9 etc.

Some Simple Meta-characters
Let us start with a some simple meta-characters and how we can apply these to various scenario's. The

• ^ - The Caret/Anchor is one of the simplest meta-characters and represents the start of the line which is being checked. For example ^cat would match all lines which start with the literal cat like catalog
  
• $ - The dollar meta-character represents the end of the line which is being checked. So cat$ would match all lines which end with the literal characters cat, for example scat.
  

These 2 meta-characters are unique in the sense that they match a position rather than the actual literal characters themselves.

Exercise -- What would ^cat$, ^$ and ^ match ?

• Character Class -- The meta-character [...] called the character class lets you list the characters you want to allow at that point of match. For example e matches just e , a matches just a, however [ea] would match both e or a. Thus the implied meaning is that of OR. Suppose you wanted to check whether you have spelt grey or gray. The following regular expression would match the occurance of both gr[ea]y. This matches g follows by r followed by either e or a followed by y. The - operator within a character class matches a range, so [0-9A-Z] matches occurances of numbers and capital letters. For example ] would help you while searching headers in html documents. The - is special inside a character class, otherwise it is used as a normal character and not as a range.
• Negated Character classes -- A ^ inside a character class negates the matches. For example [^a-z] would match any character which is not a through z. Remember a negated character class means match a character thats not listed and not don't match whats listed
  

Exercise -- Figure out all words in a dictionary which contain a q not followed by a u

• Matching Any character with dot -- this is simpler to explain with an example. Suppose you want to find a date 26/02/1977, which can also be represented as 26-02-1977 or even 26.02.1977. Not the . character can be used to match any character. So seemingly, 26.02.1977 should return us the date however it be represented, maybe with a - or a /. However, the above would also match a random number like 12264023197734. This is because the dot character matches any character. The correct way to do so would be to use something like 26[-./]02[-./]1977 (Note, the - is this case would not be a meta-character, since it immediately follows the [, if the same was written as [.-/], then it would become the range meta-character, also the . is not treated as a meta-character since it is inside the character class)
• Matching any one of several sub-expressions -- The | (OR) operator lets you combine expressions into a single expression, that matches any of the individual ones. For example, based on the previous examples, we can rewrite gr[ea]y as gr(e|a)y. (Note-- we cannot use something like gr[e|a]y as inside the character class, | is treated as a normal character). We need the parenthesis because gre|ay would mean gre or ay.
  

Exercises 1) How does gr[ea]y differ from gr(e|a)y ?
2) What is the difference between ^:List|Of|Books: from ^(List|Of|Books): ?
Note -- Tools like egrep provide switches for case-insensitive searches. For egrep -i performs a case insensitive search.
Example -- egrep -i '^(Subject|Predicate):' myfile.txt
This serves as a good groundwork for someone wanting to start using regular expressions. I will be following up the post with detailed topics. Till then, cheers and keep the faith.

The Art of analysis and problem solving

I have been wondering about the art of analysis and problem solving and decided to do a writeup using an example. A lot of developers tend to jump to writing code and never seem to bother about thinking out their solutions. For them if it works its fine. Moving away from this is a pre-requisite for anyone who wants to hone his development skills. In order to convey my point, i take up a seemingly simple example which displays how to analyze a solution before implementing it.

Problem Statement

Write a function which removes a set of characters from a given String. The signature of the function should be as follows

public String removeCharsFromString(String source, String remove)

Problem Analysis
The problem involves the following 2 steps
1) For each character in source, determine whether it needs to be deleted
2) Delete the character

Lets start with the actual deletion process first. You have to remove an element from an array. An array is a contiguous block of memory, so you cant remove an element from the middle as can be done with a linked list. So you have to rearrange the elements to maintain it as a contiguous block. For example if you need to remove c from an array containing abcd , you have to rearrange the elements. So you can either shift ab up or shift d down. In addition you need to decrease the size of the string by one.

Now how would the proposed algorithm work if you had to delete all elements from the source string. If the String is n characters long, this would mean shifting the last element by n-1, the second last by n-2 and so on, giving the worst time ass O(n^2).

How can we avoid this. What if you allocated a temporary string buffer and built your modified string there instead of in place? Then you could simply copy the characters you need to keep into the temporary string, skipping the characters you want to delete. When you finish building the modified string, you can copy it from the temporary buffer back into str. This way, you move each character at most twice, giving O(n) deletion. However, you’ve incurred the memory overhead of a temporary buffer the same size as the original string, and the time overhead of copying the modified string back over the original string. Is there any way you could avoid these penalties while retaining your O(n) algorithm?

To implement the O(n) algorithm just described, you need to track a source position for the read location in the original string and a destination position for the write position in the temporary buffer. These positions both start at zero. The source position is incremented every time you read, and the destination position is incremented every time you write. In other words, when you copy a character you increment both positions, but when you delete a character you increment only the source position. This means the source position will always be the same as or ahead of the destination position. Once you read a character from the original string (that is, the source position has advanced past it), you no longer need that character - in fact, you’re just going to copy the modified string over it. Because the destination position in the original string is always a character you don’t need anymore, you can write directly into the original string, eliminating the temporary buffer entirely. This is still an O(n) algorithm, but without the memory and time overhead of the earlier version.

Now to the actual part of deciding whether a character needs to be deleted. The easiest way is to compare all characters in the remove string with all the characters in the source string. If the size of the source string is n and the size of the remove string is m, this entails a running time of O(nm). How can we reduce this to a running time of O(m).

If we construct an array or a hashtable which has a constant time lookup, we can reduce the running time to O(m).
Lets construct an array containing all Booleans which is indexed by all the possible values of the characters in the source string. This enables you to determine whether a character is in remove by checking a single element.

Now the function will have 3 parts

• Set all elements in the lookup array to false
• Iterate through each element in remove, setting the corresponding value in the lookup array to true
• Iterate through str with a source and destination index, copying each character only if its corresponding value in the lookup array is false

Now if we combine all the operations, the running time would be O(n+m) which is still linear.

Now lets take a look at the code


public String removeCharOccurances(String source,String remove){
char[] sourceArr = source.toCharArray();
char[] removeArr = remove.toCharArray();
boolean[] flags = new boolean[128]; // assumes ASCII!
int len = sourceArr.length;
int len1=removeArr.length;
int src, dst;

// Set flags for characters to be removed
for( src = 0; src < len1; ++src ){
flags[removeArr[src]] = true;
}
src = 0;
dst = 0;

// Now loop through all the characters,
// copying only if they aren't flagged
while( src < len ){
if( !flags[ (int)sourceArr[src] ] ){
sourceArr[dst++] = sourceArr[src];
}
++src;
}

return new String( sourceArr, 0, dst );
}