Data Structures and Software Development in an Object-Oriented Domain (Object and Component Technology Series) - Hardcover

FEATURES

• Use of a subset of the UML—Shows how to use UML for analysis and modeling.
• CD-ROM included—CD contains an Eiffel compiler and development environment, all the code for the text, and the data structures library.
• Modeling of the Problem Domain—Absent in other texts, this book models the problem domain that an object-oriented project must begin with.
• Two case studies—Illustrates the steps followed in an object-oriented development process for the analysis and design of non-trivial systems.
• Extensive Data Structures Library—Consists of the standard data structures, including lists, stacks, queues, trees, balanced trees, graphs, and files.
• Extensive Reference for the Eiffel language—A full-featured object-oriented language, Eiffel, specifically developed for large object-oriented systems.

Preface

Most computer-science curricula have at least one course in data structures. Such a course s usually taken by all majors, since its contents are used in subsequent courses. Historically, his course has dealt almost solely with data structures, including their time and space analyses (along the lines of the courses CSl and CS2 of the ACM88 Curriculum). However, in recent years such a course is also expected to give students a good object-oriented programming background, and, increasingly, an introductory background in software development. This is in keeping with the ACM/IEEE-CS Computing Curricula 1991 report, which emphasizes, among other things, software engineering and software design, rather than merely implementing the data structures in an object-oriented language.

Whereas this book is designed for our present second-year course taken by all our majors, it is also appropriate for the second term of first year (i.e., CS2) in some situations. In particular, it will be useful to those institutions that have a strong object-oriented CS1 course and wish to present more on application-level software development to their students. To fit at the CS2 level, the book includes all the material on the basic data structures arrays and linked lists-before treating more advanced data structures. The amount of the advanced material that can be covered in a second-term first-year course will depend on the background of the students and the pace of the course. However, the book has more material than can typically be covered in a CS2 course. As a result, it can also be used in a subsequent course to develop more depth in data structures and software engineering. Alternately, if first year uses a breadth-first approach, this book will be suitable for a strong second-year course that integrates data structures and software engineering.

Our presentation is from an object-oriented perspective and includes many of the recent software engineering techniques for an object-oriented development of a system. For our implementation language, we have chosen Eiffel, a language specifically designed for developing large object-oriented systems. It is a full-featured object-oriented language that includes abstract classes, assertions such as preconditions, postconditions, and class invariants, multiple inheritance, generic classes, exception handling, automatic garbage collection, and GUI interfaces. In particular, preconditions and postconditions were designed to support the software engineering approach of Design by Contract. Also, the simple concepts can be expressed in a clean and simple syntax without being clouded by a multitude of alternatives, options, and exception handling. Even for more complex concepts, the syntax is still simple, although the semantics necessarily increase in complexity. Although Eiffel is the language of implementation, we only use moderate amounts of code.

Like in most other recent data structure books, abstract data types (ADTs) are discussed early. ADTs offer several advantages that include encapsulation and information hiding. In any object-oriented programming language, a deferred/abstract class provides a clean implementation of an abstract data type. Also, the use of inheritance facilitates the design of modular, extendible, and reusable systems. The existence of multiple and repeated inheritance in Eiffel opens up more possibilities for the system design implementation.

But using ADTs and inheritance in developing software does not by themselves guarantee quality software. One of the primary goals is to integrate several software-engineering principles with the data structures content of the course. Students at the first- or second-year level should be introduced to the principles of software engineering, but they do not have the programming experience to understand the problems or complexities of writing large projects. Often, if these software principles are studied in isolation, they can be beyond their comprehension and are viewed as just requiring more work. They do see the need for data structures, and, with a library of data structures, they can design and build much larger applications. Thus, the book integrates data structures, library design, and the software principles into one package. Obviously at the first- or second-year level, software engineering cannot be presented to the depth of a third-year or fourth-year/graduate course. However, by gradually introducing more and more software design concepts when building up a data structures library, students can obtain a surprisingly good background in the analysis and design of software systems.

However, our discussion of software development is not limited to the data structures library context. We begin with simple software engineering concepts and repeatedly use them to develop applications throughout the book. After students have developed a working knowledge of the software basics, the more advanced concepts are introduced throughout the remainder of the book. The students absorb the software engineering material while working with concrete techniques and data structures.

An important part of this book not found in most other texts is the modeling of the problem domain. Any nontrivial object-oriented project must begin with problem modeling, and even at the first- or second-year level, students need exposure to modeling concepts. The static structure is modeled using types of relationships such as inheritance, aggregation, and association. The dynamic structure is modeled with events, users (and actors), use cases, and object-interaction diagrams. We develop and present a simplified methodology for system development. Included with it is the use of appropriate diagrams using the Unified Modeling Language (UML) to portray the key aspects of the system design. We use the methodology to develop significant applications that use the data structures being developed in parallel.

Some important aspects of this book are:

• The presentation of basic software engineering concepts at a level suitable for advanced first- or second-year students, including the use of a subset of the UML to present the results of analysis and modeling. Also, there is extensive use of diagrams to portray software relationships, which includes using the following types of diagrams: inheritance, context, sequence, collaboration, class, high-level architecture, and subsystem.
• The' standard data structures, including lists, stacks, queues, trees, balanced trees, graphs, and files, are developed, analyzed, applied, and placed in an extensive data structures library. Most of these data structures have iterators for traversing the data structures. The library also has a number of implementations of keyed and non-keyed dictionaries.
• The discussion of software engineering includes the concepts of Design by Contract, cohesion, and coupling.
• The object-oriented techniques of inheritance and polymorphism are used. Single inheritance is introduced in Chapter 2 and frequently used thereafter. Multiple inheritance is presented in Chapter 6 and used to define many of the data structures of the library. Polymorphism is introduced in Chapter 6 and used in both the data structures library and applications.
• Two case studies illustrate the steps followed in an object-oriented development process for the analysis and design of nontrivial systems.
• Timing analysis is extensively studied and used throughout. This includes the analysis of recursive algorithms, first by counting the number of calls and then by recurrence relations.
• A full chapter is included on software testing, which deals with traditional black box and white box test-case generation techniques, as well as testing techniques for object-oriented software.
• Abstract Data Types are presented from both the constructive and the axiomatic approaches using an object-oriented notation.
• Eiffel, the language used for implementation, is a full-featured object-oriented language. It has automatic garbage collection, polymorphism, multiple inheritance, generic classes, assertions for the support of the Design-by-Contract approach, and exception raising and handling. Eiffel was designed with a clean and simple syntax so that more advanced concepts, like exceptions, don't clutter the simple concepts.
• An extensive reference for the Eiffel language is included in an appendix.
• Some of the concepts and techniques are introduced on an as-needed basis rather than overwhelming the student with a full treatment of the topic in a single chapter. For example, the basics of the language Eiffel are presented in Chapter 2, and most of the subsequent chapters add various constructs, as they are needed for specific purposes. This approach is also used for timing analysis and UML notation.
• An appendix reviews basic mathematics for handling summations, logarithms, and functions.
• An extensive collection of problems is included. Also, there are a number of case studies that are suitable for student projects.
• A CD is included with the book that contains all code for the text, the data structures library, and an Eiffel compiler with its associated environment.

Summary by Chapters

Chapter 1 examines the phases present in most software development processes. This chapter explores briefly factors that are important in assessing the quality of software systems. The chapter also examines some fundamental principles of software design that have been used in the production of quality software. It concludes with an overview of three approaches to software design.

Chapter 2 presents the basics of the Eiffel language. The main goal of this chapter is to cover Eiffel's elementary constructs so that a student can write simple programs.

Chapter 3 introduces the elements and mechanisms that constitute the object mode...