[PDF] [PDF] Appendix A ABSTRACT DATA TYPES IN JAVA

[PDF] Abstract Data Types Data Structure “Grand Tour” Java Collections

▻ Remember, O isn't a tight bound Page 4 ▻ explain what an ADT is ▻ list four examples of ADTs in the Collections

[PDF] ADT and Data Structure Example

The Java primitive data types (e g int) have values and operations defined in Java itself • An Abstract Data Type (ADT) is a data type that has values and 

[PDF] Introduction: Abstract Data Types and Java Review - Fas Harvard

public class ArrayBag implements Bag { private Object[] items; private int numItems; public boolean add(Object item) { } (see ~cscie119/examples/ bag/ 

[PDF] Abstract Data Types and Data Structures - Fas Harvard

We want the bag to be able to store objects of any type Specifying an ADT Using an Interface • In Java, we can use an interface to specify an ADT:

[PDF] Abstract Data Type (ADT)

Understanding data abstraction Defining ADT ➢Abstract data type (ADT) is a collection of data a In Java 7 and earlier, methods in an interface only have

[PDF] Abstract Data Types - COMP1005/1405 Notes 1

In JAVA, there are a variety of ADT-related classes that can be used to represent these various programming needs These ADTs are located in the java util

[PDF] Abstract Data Types - Washington

Data abstraction (Abstract Data Type, or ADT): 3 type Common in immutable types, e g , java lang String: String substring(int offset, int len) No side effects 

[PDF] Appendix A ABSTRACT DATA TYPES IN JAVA

Abstract data types(ADT) are a way of organizing the objects and operations that de- fine a data type in such a way that the specifications and behaviours of the 

[PDF] Data Abstraction and Abstract Data Types - cssiuedu - Southern

Data Type • Java provides eight primitive types: – boolean – char, byte, short, int , Abstract Data Type An ADT has built-in operations that can be performed

[PDF] abstract essay example

[PDF] abstract example for case report

[PDF] abstract example for engineering report

[PDF] abstract example for internship report

[PDF] abstract example for lab report

[PDF] abstract example for project report

[PDF] abstract example for scientific report

[PDF] abstract example for technical report

[PDF] abstract example lab report

[PDF] abstract example mla

[PDF] abstract example psychology

[PDF] abstract example research paper

[PDF] abstract example science

[PDF] abstract example sentence

[PDF] abstract examples apa research paper

Appendix A

ABSTRACT DATA TYPES IN JAVA

ab-stract: That which comprises or concentrates in itself the es- sential qualities of a larger thing or of several things. - The New Merriam-Webster Pocket Dictionary In practice, the larger the program, the harder the debugging and the more limited the confidence in its correctness. One of the basic programming rules is that no method should ever exceed a page. The years of experience have shown that the best way is to split the program into small coherent and understandable pieces, ormodules, and then fit them together. Generally speaking, a module is a unit in a larger software system that bundles together some data and some operations and has a carefully definedinterface. The external users of the module can make use of the operations and data provided in the module interface, but the internal implementation of the module is concealed and is made inaccessible to external users. Thus the hidden internal data representation can be completely replaced without affecting the external users. This is calledsubstitutability of data representations, and it permits us to improve the efficiency of a software system by replacing less efficient data representations with more efficient ones. Most of the algorithms in this handout are too small to involve this technique. Nonethe- less, it can be used to separate data structures from algorithms. Consider, for example, any above-mentioned algorithm for sorting a set of numbers. It is clear that the algorithm will work, even without specifying what data structure is used to represent the set. This separation of data structure from algorithm permits us to study each in isolation as well as to organize and simplifythem. This concept iscalleddata abstraction.Anabstractionof a thing has two qualities: it suppresses irrelevant details and it seeks to isolate the essence of the thing being abstracted. 221

222COMPSCI.220FT

A.1 Abstract Data Types

Abstract data types(ADT) are a way of organizing the objects and operations that de- fine a data type in such a way that the specifications and behaviours of the data type are rigorously separated from the data type"s implementation. Java provides strong, general- purpose support for modular programming through itsclasses,interfaces, andpackages.

A Java class is an example of an ADT.

ADT"sexternallyaccessibleoperationsand dataare givenbypublicmethodsand data fields declared in the class. The ADT"s hidden implementation details are represented by theprivatedata fields and methods of the class. Javainterfacescan be used to define ADTs that can incorporate general pur- pose replaceable data components. Theinterfacedefines abstract behavioural characteristics that allowable components must implement. Any specific kinds of data components that implement theinterfacecan then be used as plug- compatible components, suitable for plugging-in to the ADT. Javapackagesare named collections of related classes and interfaces that can be separately compiled for use in Java applets or applications. Typically, packages, such as the Javautil(utilities) package or the Javaawt(abstract window tools) package, bundle collections of useful software components into a software compo- nent library suitable for use by others in building their own Java programs. By using Java classes to implement ADTs, the hidden implementation details can be modified (or can even be totally replaced) within the local boundaries of the Java class definitions without having to make a single external change elsewhere in the program. Ease of modification is thus convincingly achieved. Although the termsdata type(or justtype),data structure, andADTsound alike, they have different meanings. In a programming language, thedata typeof a variable is the set of values that the variable may assume (e.g., a variable of typebooleancan assume either the valuetrueor the valuefalse, but no other value). An ADT is a mathematical model, together with various operations defined on the model. We shall design algorithms in terms of ADT"s, but to implement an algorithm in a partic- ular programming language we must find some way of representing the ADT"s in terms of data types and operators supported by the programming language itself. To represent the mathematicalmodel underlying an ADT we usedata structures, which are collections of variables, possibly of several different data types, connected in various ways.

COMPSCI.220FT223

ADT in mathematics

Here are some standard examples of mathematical entities, not tied to any particular rep- resentation. Asetis a collection of zero or more entries. An entry may not appear more than once. A set of nentries may be denotedfa1 ;a2 ;:::;an g, but the position of an entry has no significance; f0;3;6;7;8gandf3;0;8;7;6grepresent just the same set. Amapis a special kind of set, namely, a set of pairs, each pair representing a one-dimensional mapping from one element to another. For example, a dictionary (words mapped to meanings) or the conversion from base 2 to base 10 are maps. Amultisetis a set in which repeated elements are allowed; e.g.,f1;3;1;5;4;0gis a multiset. Multisets are generally easier to deal with than sets, since checking for duplicates is expensive. Asequenceisan ordered collectionof zero or moreentries, denoted[a1 ;a2 ;:::,an The position of an entry in a sequence is significant; for example, the fifth entry, or the successor of a given entry, may be referred to. AgraphG=[V; E]is a setVofvertices(nodes) and a setEofedges(arcs, links), i.e. two-element subsets of V. This definition excludes self-loops (edges from a vertex to itself) and parallel edges (two edges connecting the same two vertices).

An example is given in Figure A.1.

V = { a, b, c, d }E = { { a, d }, { d, c }, { a, c } }ba cd Figure A.1: GraphG=[V; E]with the four vertices and three edges. This list can be easily extended to include, for example, directed graphs (digraphs), com- plex numbers, matrices, etc. When one of these entities is used in an algorithm, certain operations are performed on it (say, insertions and membership tests on a set). This ob- servation leads naturally to theconcept of an ADT:a mathematical entity together with some operations defined on it.

224COMPSCI.220FT

The ADT concept

The ADT concept has been implicitly used since the beginning of modern computing history. For example, the mathematical entityintegerwith the operations addition, sub- traction, negation, multiplication, division, and the comparisons, has always been at the heart of computing machinery, and it provides a good illustration of the advantages to be gained from specifying ADTs.

1. Users ofintegernever need concern themselves with the implementation of the

operations: they know what the operations do, and can use them effectively without ever knowing what (micro)electronic circuitry is being employed.

2. The implementor ofinteger, in this case a hardware designer, is free to experiment

with different implementations. All that matters is that the right result be returned. By providing a clean interface between use and implementation, the ADT separates the two and clarifies the task of both. The integer ADT model consists of a finite range of integers (either machine or language dependent) together with those operations supported by the language that can be performed directly on integers. As a programmer, you do not need to understand how the integers will be represented internally (binary, two"s comple- ment form, etc.) or how the specific operations have been implemented by the language processor in order to use them in writing a program. When a class of data objects or data structures belongs to an ADT, it should not be nec- essary for a programmer to know the internal representation of the ADT data objects in order to use or manipulate them within the rules for the class; this property is known as information hiding. Information hiding is important for several reasons.

1. By hiding the internal structure of a data object, the user is able to work at a higher

programming level and is less likely to inadvertantly misuse data objects of the class (a prime source of bugs is thus avoided).

2. Less sophisticated users are able to use data objects effectively without having to

understand the complexities of the internal structure of the data object or how the operations for the ADT class were implemented. The ADT concept is useful in the study of data structures. As each new data structure is introduced, the set of procedures developed to create and manipulate the structure can be ture. The ADT concept impliesthatthe manipulationof the ADT data objects is restricted toonlythoseoperationsthatarepartoftheADTdefinition. Thisrestrictionsimplifiespro- gram development and significantly reduces a major source of program bugs. We think of an ADT as a mathematical data model with a collection of operations defined on that model. Sets of integers, together with the operations of union, intersection and

COMPSCI.220FT225

set difference, form a simple example of an ADT. In an ADT, the operations can take as operands not only instances of the ADT being defined but other types of operands, say, integers or instances of another ADT, and the result of an operation can be other than an instance of that ADT. However, at least one operand, or the result, of any operation is of the ADT in question. ADTs are generalizations of primitive data types (integer, real, and so on), just as proce- dures or methods are generalizations of primitive operations( +,, and so on). The ADT encapsulates a data type in the sense that the definition of the type and all operations on that type are localized to one section of the program (therefore, each Java class can be treated as an ADT). If you wish to change the implementation of an ADT, you know where to look, and by revising one small section you can be sure that there is no subtlety elsewhere in the program that will cause errors concerning this data type. Outside the section in which the ADT"s operations are defined, you can treat the ADT as a primitive type; you have no concern with the underlying implementation. Simple example - the Palindrome class.Using the ADT principles you can write pro- grams that use a data type without knowing any more about its implementation. In fact, that is a sign of a properly specified interface. If you need to peek into the code that im- plements a data type in order to use the type, then the type is not properly specified. Let us use a sample program calledPalindrometo illustrate these principles with a bit more complex data structure than integers. A palindrome is a character string that is the same when read forward or backward, for instance, “anna", “bob", and “+*=*+". Since computer character sets differentiate between the lower- and uppercase letters, “Anna" is not a palindrome. Our program will read a character string from the terminal, deter- mine whether it is a palindrome, and print an appropriate message. Thejava.lang package contains the desired string data structures, namely, the classesStringand StringBuffer. The instance methodequals()of the first class permits you to check whether two strings are the same and the methodreverse()of the second class is able to reverse a string. The data typesStringandStringBufferare used below withoutknowinganyof theirdetails. Allwe knewwere theirspecificationsin thepackage java.lang.

1 import java.io.*; // methods for reading input data

2

3 public class Palindrome {

4

5 public static void main( String args[] ) {

6

7 String s = new String( "" );

8 BufferedReader in = new BufferedReader(

9 new InputStreamReader( System.in ) );

226COMPSCI.220FT

10

11 System.out.println("Enter one string per line");

12 System.out.println("(an empty line stops the program)");

13 while( true ) {

14 try{

15 s = in.readLine();

16 } catch( IOException e ) {

17 s = "";

18 } finally {

19 if ( s.length() > 0 ) {

20 StringBuffer fsb = new StringBuffer( s );

21 StringBuffer rsb = fsb.reverse();

22 if ( s.equals( rsb.toString() ) )

23 System.out.println("is a palindrome !!!");

24 else

25 System.out.println("is not a palindrome ...");

26 } else {

27 System.out.println( "-------END-----" );

28 System.exit(0);

29 }
30 }
31 }
32 }
33 }
Lines 1, 8-12, and 14-17 permit you to read a text line from your terminal. You must use thetry-catch()-finallyconstruction because theBufferedReader"s method readLine()may throw anIOException. Lines 13 and 31 produce the infinite loop for entering and checking text lines, and lines 19 and 26-29 terminate the pro- gram when an empty line is entered. Lines 20 and 21 reverse a given text by using theStringBufferdata type and the available instance methodreverese().To compare the input string to the reversed one, using the methodequals()of the class String, the methodtoString()converts theStringBufferdata to theString data. Of course, you may write another version of the program, giving similar results like

Enter one string per line

(an empty line stops the program) Anna

It is not a palindrome ...

ANNA

It is a palindrome !!!

westtsew

It is a palindrome !!!

COMPSCI.220FT227

It is a palindrome !!!

l

It is a palindrome !!!

-------END----- But in either case,you need not know how the classesStringandStringBuffer are implemented in Java. We have an interface that includes everything the user needs to knowinordertousethedatatypes,andeverythingan implementorneedstoknowinorder to write code to implement the type. It is a contract between the user and implementor.

A.2 ADTs and Java classes

Abstract data types are collections of objects and operations that present well-defined abstract properties to their users, while hiding the way they are represented in terms of lower-level data representations. It should be emphasized that there is no limit to the number of operations that can be applied to instances of a given mathematical model, or object. Each set of operations defines a distinct ADT. Javaclasses,interfaces, andpackagesare used to express the concepts of modularity, in- formation hiding, and data abstraction. The access modifiers (public,private, and so on) for data fields and methods in Java class definitions permit us to define whether these data fields and methods arepublic(and thus visible to and available for use by outside users of the class) or areprivate(and thus invisible to and unavailable for use by outside users). Objects and operations at higher level of data abstraction are represented by organizing objects and operations at lower levels. The ADTs at the highest level of data abstraction - structures such assets,trees,lists,stacks, andqueues- can be represented in a variety of different ways by lower-level representations, including those in the two broad classes -sequential representationsandlinked representations 1 . At still lower levels, the linked representations can be represented in a variety of different ways, such as usingthe parallel arrays or Java objects that contain references to other Java objects in their data fields (see

Figure A.2).

For security reasons, Java does not provide explicit pointer values (in contrast to other OOP languages such as C++ or Object Pascal). However, Java uses implicit pointers to 1

Sequential data representation uses a sequence of individual blocks of storage, each block is indepen-

dently accessed by its unique address in that sequence. Linked data representations are created by linking

individual blocks of storage together using pointers.

228COMPSCI.220FT

ADTsLists Queues Stacks Sets Trees SequentialRepresentations LinkedRepresentations Arrays StringsImplicit PointerRepresentationsParallelArrays

Figure A.2: Levels of data abstraction.

access arrays and objects. In fact, Java divides its data values into two classes:primitive datavalues(suchasintegers,characters, booleantruthvalues,andfloatingpointnumbers) andreference valuesthat are references to objects and arrays. Such Java reference values are just pointers to objects and arrays, even though Java does not provide any pointer fol- lowing operations. Java reference values can be stored in data fields of objects, as items in arrays, or as values of variables. This provides a satisfactory basis for implementing linked data representations.quotesdbs_dbs19.pdfusesText_25