PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Abstract Data TypesContents 1. Description and and definition on an ADT2. Terminology3. Notation4. Example 1 -- ADT WaterTank5. Implementing an ADT description6. Example 2 – ADT Bag7. Interface BagAbstract Data Types An Abstract Data Type (ADT) is a description of the operations performed on a collection of data. It has the following components:•Name of the ADT•Types represented in the collection of dataEach type has previously been defined in an ADT (or is a well-known primitive type)•Functions that operate on the data•Preconditions for any function that is not a total function•Post-conditions for each of the functionsFunctions will specify the domain (parameters) and range (return type)Abstract Data TypesTerminologyTotal Function – A Total Function is one that is defined for every value in the domain. Correspondingly,Partial Function – is a function that is defined only on a subset of the domainExamplesSQR (square) is a function that is defined for all real numbersSQR: Real  RealSQRT (square root) is a partial function on the real numbersSQRT: Real -/-> RealPartial functions have a precondition specifying the subset of the domain over which they are defined.The precondition for SQRT is that it is defined only for real numbers greater than or equal to 0.Abstract Data TypesTerminology For container classes transformations such as remove are usually partial functions, and observations such as isEmpty are almost always total functions.Given the following function:remove: Container, Integer -/-> ContainerThis partial function expresses the fact that remove takes as its arguments a Container object and an integer (index) and returns a transformed container. It is a partial functions because it is not defined on the empty container and is only defined over integers greater than 0 and less than the size (number of items contained) of the containerNote! In this terminology a Container is mapped into another container much as SQR maps a real into a different real. The transformed container has a different state (expressed by its capacity and contents) and is therefore regarded as a different container.Abstract Data TypesNotationThe list of function takes the following form:Function Name : Domain of definition (arguments) Range (return type)SQR : Real  RealSQRT : Real -/-> Realremove : Container , Integer -/-> ContainerThe symbol  denotes that the mapping is that of a total function, whereas The symbol -/-> denotes a partial functionAbstract Data TypesNotation Preconditions – all partial functions have a precondition that specifies the sub-domain over which they are definedWe express the precondition that SQRT is defined for real numbers greater than or equal to 0 asFor all x  Real pre-SQRT(x) ::= x  0pre-SQRT(x) ::= translates as-- a precondition for SQRT acting on x, where x is any real number, is defined to be (::=) that x is greater than or equal to 0Similarly, the precondition for remove is written For all c  Container and i  Integer pre-remove(c, i) ::= !empty(c) && 0  i < size(c) empty and size are other functions in the ADT expressing observations on cAbstract Data TypesNotation Post-conditions describe the state of the collection after a a function has acted.There are three kinds of functions:1. Create/Dissolve functions – implemented by constructors in Java2. Transformations – change the state of one or more of the arguments3. Observations – return information about the arguments, but do not change the state of the collectionFor observations, the state of the system is the same after as it was before – post conditions only state the obvious (that a particular type of object has been returned) and therefore can be omitted from the ADT descriptionAbstract Data TypesNotation We use the following notation to express post-conditions:For all x, y  Real post-SQR(x; y) ::= y = x * x && y  0post-SQR(x; y) ::= translates as – The post condition for the function SQR that maps a real number x into a real number y is defined to be y is equal to x times x and y is greater than or equal to 0.For the remove function, we can express the post-condition as follows:For all c, c’  Container, and all i  Integer post-remove(c, i; c’) :: = size(c’) = size(c) –1 arguments returned valueAbstract Data TypesPutting it all TogetherConsider an ADT description of a Water Tank where we will use type Real to denote the amount of water held in the tankADT WaterTank TYPES: Real, Boolean FUNCTIONSCreate: Real -/-> WaterTankDissolve: WaterTank  ( )add: WaterTank, Real -/-> WaterTankremove: WaterTank, Real -/-> WaterTankisEmpty: WaterTank  Booleancontents: WaterTank  Realcapacity : WaterTank  RealAbstract Data TypeADT WaterTank (continued)PRECONDITIONS for all t  WaterTank, n,x  Realpre-Create(n) ::= n > 0 //capacity of new tank > 0pre-add(t, x) ::= x  t – contents(t) //can’t add more than tank can holdpre-remove(t, x) ::= x  contents(t) //can’t remove more than you havePOST-CONDITIONS    for all t, t’  WaterTank, x, y, n  Realpost-Create(n; t’) ::= capacity(t’) = n && isEmpty(t’)post-add(t, x; t’) ::= contents(t’) = contents(t) + xpost-remove(t, x; t’) ::= contents(t’) = contents (t) - xNew tank t’ has a capacity of n and is emptyAbstract Data TypeConverting the ADT to a Class DescriptionThe principal difference between the ADT representation of a WaterTank and a java class description is that in the ADT the WaterTank is just one of the types in the collection and it can appear as an argument and/or as a return type for a function. In an ADT description, the WaterTank object is not an argument or a return type, but the recipient of a message that causes it to execute a method (function) that may change its state.In class WaterTank, the function Create is replaced by a constructor, and the function Dissolve is performed automatically.Abstract Data TypesClass WaterTankpublic class WaterTank { private double content, capacity; //data attributes public WaterTank(double cap) throws TankNotBuiltException{ //precondition: cap > 0 //post-condition: new tank has capacity n and content 0 if (cap > 0 ) {capacity = cap; content = 0; } else throw new