Table of Contents

1. Programming and Software.


1.1 Computer science. 1.2 Computer programs. 1.3 Programming languages. 1.4 Structured and object-oriented programming. 1.5 Common software tools. 1.6 Programming. 1.6.1 Programming languages. 1.7 Goals of this book. 1.8 Exercises.



2. An Object-Oriented Approach to Problem Solving.


2.1 Object, objects everywhere. 2.1.1 Ordinary objects. 2.1.2 Objects as abstractions. 2.2 The object model. 2.2.1 An object model example. 2.2.2 The noun-verb and noun-noun metaphors. 2.2.3 Internal state. 2.2.4 Object scenarios and messages. 2.2.5 Parameters. 2.3 Relationships among objects. 2.3.1 Inheritance. 2.3.1.1 Classification. 2.3.2 Aggregation. 2.3.3 Uses relationship. 2.4 Abstract data type. 2.5 Producers and consumers. 2.6 Object modeling. 2.6.1 Analysis. 2.6.1.1 Aggregation relationship. 2.6.1.2 Uses relationship. 2.6.1.3 Inheritance relationship. 2.6.2 Analysis of an elevator. 2.6.3 Design. 2.7 Summary. 2.8 Exercises. 2.9 References.



3. The Basic Elements of Eiffel Programs.


3.1 Programming. 3.2 The Eiffel Language. 3.3 Creating and destroying objects. 3.4 Basic types, default values, and assignment. 3.5 Ordinary or reference type objects. 3.6 Copying objects. 3.7 Cloning. 3.8 Basic operators with examples. 3.9 Branching. 3.10 Iteration (loop). 3.11 Routines. 3.12 Arrays. 3.13 Strings. 3.14 Basic input and output. 3.15 Mathematical routines and “number crunching.” 3.16 Files and secondary storage. 3.17 Summary. 3.18 Exercises.



4. Algorithms.


4.1 Introduction. 4.2 Problems versus their instances. 4.3 A taste of algorithms-some simple examples. 4.3.1 Algorithms for finding smallest and largest array values. 4.3.2 Simple sorting algorithm. 4.4 The efficiency of algorithms. 4.5 Computing faster. 4.5.1 Illustrative example- subvector problem for arrays. 4.6 Some more sorting. 4.6.1 Bubble-sort. 4.6.2 Gap-sort-a magic number and a fast variant of bubble-sort. 4.6.3 Insertion-sort. 4.7 Hard problems. 4.7.1 Traveling salesperson problem. 4.7.2 Knapsack problem. 4.8 Concluding remarks. 4.9 Summary. 4.10 Exercises. 4.11 References.



5. Building Some Simple Eiffel Systems.


5.1 Dice. 5.1.1 Random number generators. 5.1.2 Implementation of die class. 5.2 Constant attributes. 5.3 A horse race using unusual dice. 5.3.1 Analysis and design of horse race game. 5.3.2 A four-way race. 5.4 Summary. 5.5 Exercises. 5.6 References.



6. The Construction of Eiffel Classes.


6.1 An overview of the components of an Eiffel class. 6.2 Creation. 6.2.1 Subclass creation. 6.2.2 More advanced subclass creation. 6.3 Inheritance. 6.3.1 Extension-subtypes. 6.3.2 Specialization-the redefine subclause. 6.3.3 Selective export-the export subclause. 6.3.4 Renaming inherited routines-the rename subclause. 6.3.5 The select subclause. 6.4 Abstract classes using Eiffel's deferred class facility. 6.5 Storage versus computation: attributes versus routines. 6.6 Protecting and documenting routines-assertions and programming by contract. 6.6.1 Account classes revisited with assertions. 6.6.2 Propagation of assertions through inheritance. 6.7 Summary. 6.8 Exercises.



7. Constructing Classes for Reuse-Generic Container Classes.


7.1 Stack. 7.1.1 Static implementation of stack. 7.1.2 Dynamic implementation. 7.2 Unordered list with duplicates not allowed. 7.2.1 Interface to UNORDERED_LIST class. 7.2.2 Implementation of class UNORDERED_LIST. 7.2.3 Discussion of implementation. 7.2.3.1 The data model. 7.2.3.2 Internal routine find. 7.2.3.3 Public routine item_before. 7.2.3.4 Public routine insert_front. 7.2.3.5 Public routine insert_back. 7.2.3.6 Public routine insert_before. 7.2.3.7 Public routine remove. 7.2.3.8 Public routines remove_front and remove_back. 7.2.3.9 Public routines remove_after and remove_before. 7.2.3.10 Public routine reverse_sequence. 7.3 Unordered list with duplicates allowed. 7.4 The stack revisited. 7.5 The queue. 7.6 Summary. 7.7 Exercises. 7.8 References.



8. Recursion as a Design Principle.


8.1 The mechanics of recursion. 8.2 Relationship between recursion and iteration. 8.3 Recursion used in design. 8.3.1 Binary search of sorted arrays. 8.3.2 Quicksort-an efficient recursive sorting algorithm. 8.3.3 Binary search tree. 8.4 One final and more advanced but important application of recursion-depth-first search of a graph and airline connection problem. 8.5 Some parting comments about recursion. 8.6 Summary. 8.7 Exercises.



9. Polymorphism as a Design Principle.


9.1 Late-binding and polymorphism. 9.2 A case study that features polymorphism. 9.2.1 Specifications. 9.2.2 The analysis and design. 9.2.3 Implementation details. 9.2.4 Output. 9.3 Version 2-improved design and implementation. 9.3.1 Revised implementation. 9.4 Summary. 9.5 Exercises.



Appendix 1.


Interface to String Class.



Appendix 2.


Interface to Class PLAIN_TEXT_FILE.



Appendix 3.


Class RANDOM_NUMBER.