Abstract Data Types (ADTs) PDF

11/6/24, 7:10 PM cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt csci243 Week 08, 09: Abstract Data Types # Abstract Data Type Concept An Abstract Data Type is a conceptual entity composed of: - data - ope...

11/6/24, 7:10 PM cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt csci243 Week 08, 09: Abstract Data Types # Abstract Data Type Concept An Abstract Data Type is a conceptual entity composed of: - data - operations on that data An ADT applies encapsulation, which has these characteristics: 1: internal structure and representation is hidden in a 'black box'; 2: can modify data only via defined and specified operation functions. ADT Benefit: separate the interface from implementation - client program needs to know only WHAT the ADT does, NOT HOW. OO languages are designed with ADTs in mind. A class specification with private, internal data and public methods permits a client program to use only the defined methods to access data, and a program can instantiate multiple copies. ## Background: Abstraction Abstraction: a high-level view of low-level activities Examples: - average grade: divide sum of grades by the number of students - 'change a tire': use jack, remove old tire, put on new one Control Abstraction: looping/decision constructs Data Abstraction: separation of implementation from usage Advantages of abstraction: - easier to think about things without details - can control or prevent access to what should be hidden - enables plug-and-play modular design Example: replace an implementation without changing the interface ## Background: Data Types and Terminology Definitions Data type: specification of characteristics of data instances including - internal representation - range of values - set of permissible operations Type system: set of rules for associating type information in expressions including the following: - mechanism for defining types - procedure for associating operations with types - rules for type equivalence, compatability, and inference A type system REJECTS AN EXPRESSION if it cannot associate a type with it; this activity is part of semantic analysis. Example implicit type system in FORTRAN: variable names beginning I-N are integer; all others are real. literal constants: real if they contain '.'; otherwise integer if two instances E and F have the same type, then E op F have the same type, where op in {+ - * /} if E and F have different types, the result is real https://www.cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt 1/6 11/6/24, 7:10 PM cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt Type checking: process of enforcing language type rules - type check violation is called a TYPE CLASH - type checking may be strong, weak, or untyped strong type checking: - prohibits an operation on a type that should not support it. Examples: Ada and Pascal Ada has 'type conversion' functions that produce a new instance. weak type checking: - allows explicit or implicit conversion or coercion of types. Examples: - the C cast operation explicitly changes data interpretation - the C assignment of integer into float implicitly converts. untyped: - data has no associated type; the function determines interpretation. Examples: assembly and machine language static typing: type of a variable is set at compile time dynamic typing: type of a variable is set at run time # ADTs in C Creating an ADT is harder in a non-OO language such as C because it may be hard to completely hide internals, and it requires pointers. The example C ADT designs come close to the ideal of a 'real' ADT that has complete encapsulation of instance information and prevents access by any mechanism other than the defined operations. A C ADT is sometimes called a 'module type' because the implementation mechanism requires a header file and source file pair. Also, the ADT implementation changes based on linking of.o modules. An ADT consists of two pieces: specification: syntax and semantics of use; in a C header file implementation: how it works under the hood; in a C source file The specification is also often called the ADT interface. Examples: Stack and Queue Stack: interface: push, pop, top, empty, & full declarations and documentation implementation: array, linked list, or... Queue: interface: enqueue, dequeue, front,... declarations and docs implementation: array, linked list, of... The above interface descriptions are incomplete! An ADT needs constructors and destructors to create and destroy instances. What happens if you push() on a full stack, or pop() an empty stack? - Does the function 'blow up' or crash? - Does the function ignore? - Does the function provide an error code as a return status value? Also: - Does the function have restrictions on passed in values? The interface specification must describe behavior with DOCUMENTATION. https://www.cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt 2/6 11/6/24, 7:10 PM cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt ## Overview of stackADT implementation versions v1 through v4 For these versions, the driver programs (driver*.c) are identical. Note that some versions do not compile or link due to intentional errors. The errors illustrate features or restrictions of the C language. Specifications in stackADT.h: - ADT type: pointer typedef, stackADT, hides a struct implementation - payload data type: integers passed in or returned from functions - operations list: stackADT create() void destroy() void clear() void push() int pop() int top() bool empty() bool full() Details of the interface: - the typedef hiding the struct details differs in versions - create() returns NULL if upon failure; client should check result - destroy() push() pop() and top() 'blow up' if op cannot be performed - interface functions require a stackADT object as the first parameter ## Details of the ADT implementations: stackADT1.c: fixed-size array holds the data stackADT2.c: dynamic array on heap holds the data Note difference in stk_full() behavior: stackADT1:full() returns true or false; the stack can fill up stackADT2:full() always returns false; the stack cannot fill up The versions use different typedefs to present an ADT to client programs. These typedefs are in the header file, with implementation in the source file. ### v1: typedef struct stackStruct * stackADT; Version v1 compiles, links, and executes correctly. The 'v1' version declares stackADT in the header file as a pointer to a struct named 'stackStruct' which is not defined in client-visible code. Instead, the structure is defined privately in the implementation files. ### v2: typedef struct { } * stackADT; The 'v2' version replaces the stackADT declaration with an anonymous struct. Version v2 does not compile; tries to redefine struct in the implementation. ### v2b: typedef struct { } * stackADT; Version v2b compiles and runs, but is NOT SAFE because implementation files do not include stackADT.h; compiler cannot verify conformance to the interface. There is no longer protection of the function prototypes to ensure that the implementations match the header file specification. NEVER remove the interface header file inclusion! ### v3: typedef struct { } * stackADT; https://www.cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt 3/6 11/6/24, 7:10 PM cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt Version v3 compiles, links, and runs cleanly and correctly. Version v3 fixes the problems with the 'v2' version by conditionally declaring the stackADT type in the header file. It guards the declaration with the _STK_IMPL_ symbol. If the symbol _STK_IMPL_ is defined, no stackADT declaration occurs, and the compiler uses the declaration in the implementation file. NOTE: the stackADT declaration in the.c file must occur BEFORE the header file is included, or there will be compilation errors on all stackADT references in the prototypes. ### v4: typedef struct * stackADT; Version v4 does not compile; a struct must have either tagname or body {}. Version v4 illustrates that an anonymous struct declaration requires { }. ## Generics: Extending the stackADT Versions v5, v6, vu1, and vu2, extend the ADT to handle arbitrary data types. Generic version implementations use a generic pointer as the contents: struct stackStruct { void * contents; size_t capacity; size_t num; }; Interface Changes the payload parameter type and return type: void stk_push( StackADT stack, void * data ); void * stk_pop( StackADT stack ); void * stk_top( StackADT stack ); Call Examples: stk_push( stack, (void *) 5 ); stk_push( stack, (void *) 'x' ); For generic implementation versions, driver programs change because the stack data type is no longer an 'int'. ### v5: typedef struct * stackADT; Version v5 uses void * as the data type for pushed items and has the _STK_IMPL_ declaration guard. ### v6: typedef struct stackStruct * stackADT; Version v6 uses void * as the data type for pushed items. Version v6 does not need the _STK_IMPL_ to guard the declaration. ## Generic Design Problems: There are still some data types we cannot push. An added driver4.c program shows that floats cannot be cast to (void *). https://www.cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt 4/6 11/6/24, 7:10 PM cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt test4 does not link because a cast from double to pointer type is illegal. stk_push( stack, (void *) 4.25 ); // illegal cast fails to compile struct Space { long x; long y; long z; } bigdata; stk_push( stack, (void *) bigdata ); // struct larger than sizeof(void*) ## Other C ADT implementation versions ### linked list of nodes implementation struct stackData { void *data; struct stackData *next; } struct stackStruct { struct stackData *first; size_t num; } Pros: easy to manage stack data; for example, push(): push(): allocate new node new node points to old first node new node becomes new first node pop(): remove first node first node pointer changed to successor empty(): first node pointer == NULL Cons: much more overhead; each item now takes twice as much space ### Union Implementations Version vu1 and vu2 use union construction for the stack ADT concept. Note: The union is one of the next topics to discuss. A union allows a single memory byte sequence to be accessed using field names of diverse types. The union declaration specifies the field type and name, and code uses 'dot notation' to select the name and type by which to manipulate the memory. // example union has a memory size matching the largest field type. union stackData { char c; float f; int i; short s; unsigned int u; void *p; }; https://www.cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt 5/6 11/6/24, 7:10 PM cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt union stackData value; // allocates storage of sizeof( void*) value.c = 'B'; The union has a memory size matching the largest field type. For the above union, all data items fit into a sizeof( void*) byte allocation. The header file of version vu1 declares a Payload type for the elements. Version vu1 push and pop function declarations: void stk_push( StackADT stack, Payload * data ); Payload * stk_pop( StackADT stack ); Version vu2 maintains the void * generic approach and the driver. Client code must declare a union whose size matches the system's pointer size (e.g. 8 bytes, or 64 bits). This way a client can define their own union and pass any primitive type, or a pointer to any user-declared type, to the ADT. Version vu2 push and pop function declarations are the same as the generics: void stk_push( StackADT stack, void * data ); void * stk_pop( StackADT stack ); https://www.cs.rit.edu/~csci243/protected/lectures/08/stu-notes.txt 6/6