ABSTRACT DATA TYPES (ADTS)

·         One of the basic rules concerning programming is that no routine should ever exceed a page. This is accomplished by breaking the program down into modules.

·         Each module is a logical unit and does a specific job. Its size is kept small by calling other modules.

·         Modularity has several advantages. First, it is much easier to debug small routines than large routines. Second, it is easier for several people to work on a modular program simultaneously. Third, a well-written modular program places certain dependencies in only one routine, making changes easier.

·         For instance, if output needs to be written in a certain format, it is certainly important to have one routine to do this.

·          If printing statements are scattered throughout the program, it will take considerably longer to make modifications.

·         The idea that global variables and side effects are bad is directly attributable to the idea that modularity is good.

·         An abstract data type (ADT) is a set of operations. Abstract data types are mathematical abstractions; nowhere in an ADT's definition is there any mention of how the set of operations is implemented. This can be viewed as an extension of  modular design.

·          Objects such as lists, sets, and graphs, along with their operations, can be viewed as abstract data types, just as integers, reals, and booleans are data types. Integers, reals, and booleans have operations associated with them, and so do abstract data types.

·         For the set ADT, there may be operations as union, intersection, size, and complement. Alternately, the two operations union and find, which would define a different ADT on the set.

·          The basic idea is that the implementation of these operations is written once in the program, and any other part of the program that needs to perform an operation on the ADT can do so by calling the appropriate function.

·         If for some reason implementation details need to change, it should be easy to do so by merely changing the routines that perform the ADT operations. This change, would be completely transparent to the rest of the program.

Character to Number conversion algorithm

This blog explains about the algorithm which will explain about character to number conversion,

Given the character representation of an integer convert it to its conventional decimal format.

Algorithm development

            The difference between the character representation of an integer and its conventional number representation is to be known. The number of different characters needed to represent textual and string information is relatively small. The upper and lower case alphabetic characters, the ten digits, and various punctuation and control characters make up only about one hundred different characters.

In contrast to this, the range of different integers (and real numbers) that are needed may extend into the millions, the bil1ions and even further. To obtain unique representations for such a large span of numbers requires a considerable amount of "space" to store each individual number. Numbers are represented in the computer in binary positional notation using just the 0 and 1 digits. As an example, let us examine the binary and decimal positional representations for the decimal number 221.

Comparing the two representations for 221, only 3 decimal digits are needed to represent 221 whereas 8 binary digits are used. To represent one billion, we need 10 decimal digits and about 32 binary digits or bits. The fundamental unit or computer word size for storing numbers is usually one of 16,32,36,60 or 64 bits. since only 7 or 8 bits (8 bits are called a byte) are all that is needed to distinguish among the hundred or so characters that we are likely to need (i.e. 2M=256) it is therefore very wasteful of computer memory to store only one character in the basic storage unit for numbers.

The solution is therefore to pack several characters into each computer word. for example, on 32-bit computers we find that four 8-bit characters are usually stored in each computer word. To make this packing possible It has been necessary to assign fixed 8-bit codes to the one hundred or so characters. One of the most widely used of these coding systems is called the American Standard Code for Information Interchange or ascii code. Some examples from this system are shown in Table .

Note that the decimal digits ,'0, 1,2,3, ..., 9, a~ also assigned 8-bit character code values. Because of this it is convenient in many applications to represent numbers as sequences of character), For example, a date may be represented by a string of characters; for example,

                                                            23 April 1984

With representations like this there are times when it is necessary to do conventional arithmetic calculations on the numbers represented as sequences of 8-bit characters. In our example above the 23 does not have the value of 2 tens and 3 units but rather there are the decimal values.50 and 51 in successive8-bit bytes.

The arithmetic operations  cannot be done directly one character code representations because the corresponding binary representation does not conform to the standard binary positional notation used to represent numbers in the computer. . Our only alternative in such circumstances is to convert the number from its character representation to its conventional number internal representation. This brings us back to our original character-to-number conversion problem.

The task is therefore to accept as input a character representation of a number containing a known number of characters and make the conversion to the conventional decimal representation. To do this it will be necessary to use the knowledge of the particular character code being employed. In this example, we will choose to work with the ascii code. Fortunately, most programming languages including Pascal provide some additional functions to make tasks like this relatively straightforward to perform. To convert the four-character sequence, 1984 to the decimal number 1984. The representation start out with is,

To make the conversion, the 49 will need to be converted to 1000, the 57 to 900, the 56 to 80 and the 52 to 4 units. To get the appropriate decimal digit in each case we have had to subtract 48 (the ascii value of character 0) from the ascii value of each character. Pascal makes this job easier by providing a function called word which accepts an 8-bit character as its argument and returns as output its corresponding decimal (in our case ascii) value, e.g. the statement.

                                                            x := ord(‘9’)

will assign to x the decimal value 57.

In our example, to get the decimal digits subtract ord(‘0’) from the ascii values of each of the characters in the sequence.

The next step is to use the digits to construct the corresponding decimal number. The character sequence will need to be processed one character at a time to obtain the decimal digits. What we must now work out is how each digit is to be converted to make its appropriate contribution to the decimal number we are seeking.

Start processing the characters from the left, when " 1" is encountered it is not immediately obvious what power of ten it should be multiplied by after the ascii conversion.

            However, by the time when a second character is encountered in the sequence, it should be multiplied by at least 10. And, at the time we have encountered the third character, we know the second digit should have been multiplied by 10 and the first digit multiplied by 100. That is, for our example of 1984,

All that is left now is to work out the details of the mechanism for implementing this process. The "shifting-to-the-left" mechanism can be obtained at each step by multiplying the previous decimal value by 10 and adding in the current decimal digit. Details of our implementation can now be outlined. It is assumed that the length of the character string has been determined and that a check has been made to confirm that the string represents a positive integer.

Algorithm description

1. Establish the character string for, conversion to decimal and its length n.
2. Initialize decimal vaJue to zero.
3.  Set base0 value to the ascii or ordinal value of '0'.
4.  While less than n characters have been examined do

(a) convert next character to corresponding decimal digit,

            (b) shift current decimal value to the left one digit and add in digit for current character,

      5. Return decimal integer corresponding to input character representation.

Convert TWList object to xls

Do you want to convert BPM TWLIst object to excel file , here the code


import com.lombardisoftware.client.persistence.TWClass;
import com.lombardisoftware.data.twclass.TWClassDefinitionData;
import com.lombardisoftware.data.twclass.TWClassProperty;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.text.ParseException;
import java.util.ArrayList;
import java.util.List;
import org.apache.poi.ss.usermodel.Cell;
import org.apache.poi.ss.usermodel.CellStyle;
import org.apache.poi.ss.usermodel.Font;
import org.apache.poi.ss.usermodel.Row;
import org.apache.poi.ss.usermodel.Sheet;
import org.apache.poi.xssf.streaming.SXSSFWorkbook;
import teamworks.TWList;
import teamworks.TWObject;

public class XlsxWriter {
    private SXSSFWorkbook workbook = new SXSSFWorkbook(100);

    public void createMultipleExcelFile(String path, TWObject object, TWList sheetNameList) throws ExcelWriterException {
        try {
            List<String> varList = this.getPropertyList(object);
            for (int i = 0; i < varList.size(); ++i) {
                TWList proertyValue = (TWList)object.getPropertyValue(varList.get(i));
                List<String> colModelList = this.getPropertyList((TWObject)proertyValue.getArrayData(0));
                this.addSheet(proertyValue, colModelList, sheetNameList.getArrayData(i).toString());
            }
            FileOutputStream output = new FileOutputStream(path);
            this.write(output);
            output.close();
        }
        catch (Exception e) {
            throw new ExcelWriterException(0, e.getMessage());
        }
    }

    public void createExcelFile(String path, TWList object, String sheetName) throws ExcelWriterException {
        try {
            ArrayList<String> colModelList = new ArrayList();
            TWObject report = (TWObject)object.getArrayData(0);
            colModelList = this.getPropertyList(report);
            this.addSheet(object, colModelList, sheetName);
            FileOutputStream output = new FileOutputStream(path);
            this.write(output);
            output.close();
        }
        catch (ParseException e) {
            throw new ExcelWriterException(0, e.getMessage());
        }
        catch (FileNotFoundException e) {
            throw new ExcelWriterException(0, e.getMessage());
        }
        catch (Exception e) {
            throw new ExcelWriterException(0, e.getMessage());
        }
    }

    private void addSheet(TWList data, List<String> colModel, String sheetName) throws ExcelWriterException {
        Sheet sheet = this.workbook.createSheet(sheetName);
        int numCols = colModel.size();
        int currentRow = 0;
        try {
            int i;
            Row row = sheet.createRow(currentRow);
            for (i = 0; i < numCols; ++i) {
                Cell cell = row.createCell(i);
                Font fn = this.workbook.createFont();
                fn.setBoldweight(700);
                CellStyle cs = this.workbook.createCellStyle();
                cs.setFont(fn);
                cell.setCellStyle(cs);
                cell.setCellValue(colModel.get(i).toString());
            }
            ++currentRow;
            for (i = 0; i < data.getArraySize(); ++i) {
                row = sheet.createRow(currentRow++);
                TWObject bean = (TWObject)data.getArrayData(i);
                for (int y = 0; y < numCols; ++y) {
                    Object proertyValue = bean.getPropertyValue(colModel.get(y));
                    String value = proertyValue != null ? proertyValue.toString() : "";
                    Cell cell = row.createCell(y);
                    cell.setCellValue(value);
                }
            }
            for (i = 0; i < numCols; ++i) {
                sheet.autoSizeColumn((int)((short)i));
            }
        }
        catch (Exception e) {
            throw new ExcelWriterException(0, e.getMessage());
        }
    }

    private void write(OutputStream outputStream) throws Exception {
        this.workbook.write(outputStream);
    }

    private List<String> getPropertyList(TWObject twObj) throws ExcelWriterException {
        ArrayList<String> variables = null;
        try {
            variables = new ArrayList<String>();
            List defnPropList = ((com.lombardisoftware.core.TWObject)twObj).getTWClass().getDefinition().getProperties();
            for (TWClassProperty prop : defnPropList) {
                variables.add(prop.getName());
            }
        }
        catch (Exception e) {
            throw new Exception(0, e.getMessage());
        }
        return variables;
    }
}

Reversing the digits of an Integer Algorithm

Design an algorithm that accepts a positive integer and reverses the order of its digits.

Algorithm development

Digit reversal is a technique that is sometimes used in computing to remove bias from a set of numbers. It is important in some fast information'-retrieval algorithms. A specific example clearly defines the relationship of the input to the desired output. For example,

                                                            Input: 27953

                                                            Output: 35972

The number 27953 is actually

2 * 10^4 + 7 * 10^3 + 9 * 10^2 + 5 * 10^1 + 3 * 10^0

To access the individual digits it is probably going to be easiest to start at one end of the number and work through to the other end. Because other than visually it is not easy to tell how many digits there are in the input number it will be best to try to establish the identity of the least significant digit (i.e. the rightmost digit). To do this we need to effectively "chop off" the least significant digit in the number. In other words we want to end up with 2795 with the 3 removed and identified.

The number 2795 can be obtained by integer division of the original number by 10 i.e. 27953 div 10->2795 This chops off the 3 but does not save it. However, 3 is the remainder that results from dividing 27953 by 10. To get this remainder use the mod function. That is,

                                                27953 mod 10->3

Applying the following two steps

            r := n mod 10  (l)=>(r = 3)

            n := n div 10    (2)=>(n = 2795)

the digit 3 is obtained and the new number 2795. Applying the same two steps to the new value of n we can obtain the 5 digit. Iteratively access the individual digits of the input number. Next major concern is to carry out the digit reversal. Applying digit extraction procedure to the first two digits  3 and then 5 are obtained. In the final output they appear as:

3 followed by 5

If the original number was 53 then we could obtain its reverse by first extracting the 3, multiplying it by 10, and then adding 5 to give 35. That is

                                                                        3x 10+5->35

The last three digits of the input number are 953. They appear in the "reversed" number as 359. Therefore at the stage when we have the 35 and then extract the 9 we can obtain the sequence 359 by multiplying 35 by 10 and adding 9. That is,

35 * 10 +9 -> 359

359 * 10 + 7 -> 3597

3597 * 10 + 2  ->  35972

The last number obtained from the multiplication and addition process Is the "digit-reversed" integer we have been seeking. On closely examining the digit extraction, and the reversal process, it is evident that they both involve a set of steps that can be performed iteratively.

            We must now find a mechanism for building up the "reversed" integer digit by digit. Let us assume that the variable dreverse is to be used to build the reversed integer. At each stage in building the reversed integer its previous value is used in conjunction with the most recently extracted digit. Rewriting the multiplication and addition process we have just described in terms of the variable dreverse,

Therefore to build the reversed integer we can use the construct:

            dreverse := (previous value of dreverse)* 10 + (most recently extracted rightmost digit)

The variable dreverse can be used on both sides of this expression. For the value of dreverse to be correct (i.e. dreverse = 3) after the first iteration it must initially be zero. This initialization step for dreverse is also needed to ensure that the algorithm functions correctly when the input number to be reversed is zero. Under what conditions should the iterative process terminate is to be found. The termination condition must in some way be related to the number of digits in the input integer. In fact as soon as all digits have been extracted and processed termination should apply. With each iteration the number of digits in the number being reversed is reduced by one, yielding the sequence shown in Table 2.1. Accumulative integer division of the "number being reversed" by 10 produces the sequence 27953, 95,279, ... . In our example, when the integer division process is applied for 5thtime a zero results since 2 is less than 10. Since at this point in the computation the "reversed" number has been fully constructed we can use the zero result to terminate the iterative process.

The central steps in our digit reversal algorithm are: 1. While there are still digits in the number being reversed do (a) extract the right most digit from the number being reversed and append this digit to the right-hand end of the current reversed number representation; (b) remove the rightmost digit from the number being reversed.

Algorithm description

1. Establish n, the positive integer to be reversed.

2. Set the initial condition for the reversed integer dreverse.

3. While the integer being reversed is greater than zero do

(a) use the remainder function to extract the rightmost digit of the 11 number being reversed; .

(b) increase the previous reversed integer representation dreverse by a factor of 10and add to it the most recently extracted digit to give the current dreverse value; .

(c) use integer division by 10 to remove the rightmost digit from the number being reversed.

This algorithm is most suitably implemented as a function which accepts as input the integer to be reversed and returns as output the integer with its digits reversed.