Object Structures

Jacob Gore is Assistant Professor of Computer Science at Eastern New Mexico University. Prior to that, he was an Adjunct and Visiting Assistant Professor of Computer Science at the University of Denver and Colorado School of Mines. He has been a programmer, researcher, advocate, and educator in object-oriented technology since 1984. He co-founded ToolCASE Computing, Inc., a software development and consulting firm, and has worked on object-oriented software projects at Hewlett-Packard, AT&T Wireless Services, IBM, and Chevron. He received his B.S., M.S., and Ph.D. in Computer Science from Northwestern University. 0201634805AB04062001

I. INTRODUCTION. 1. Object Structures. The Study of Object Structures. Objects. Object Structures. 2. Objects and Classes. Objects and Classes in Eiffel. Requesting a Feature of an Object. Inside, Outside. Summary. Exercises. 3. Pairs. What a PAIR Is and What It Does. How a PAIR Does What It Does. Sifting Out the Inside to Get the Outside View. Testing Class PAIR. Summary. Exercises. 4. Subclasses and Subcontracts. A More Sophisticated PAIR Structure. The "Can Act As a" Relationship. Subcontracting: Obligations of the Heir. When Subclassing Should Not Be Used. What PAIR Should Do As Subcontractor to ANY. Specifying Types with the like Keyword. Types, Classes, and Assignment. Summary. Exercises. II. LINEAR OBJECT STRUCTURES. 5. Arrays. What an ARRAY Is and What It Does. One Way for an ARRAY to Do What It Does. Summary. Exercises. 6. Lists. What a LIST Is and What It Does. How a LIST Does What It Does: Multiple Implementations. An Implementation Using an ARRAY. Testing List Implementations. Performance of the Array Implementation. Summary. Exercises. 7. Linked Implementations of Lists. Linked Implementations. Singly vs. Doubly Linked Lists and Their Class Hierarchy. Implementing a Singly Linked List. Factoring Out Implementation Commonalities. Choosing an Implementation: Performance Analyses. Summary. Exercises. 8. Stacks. What a STACK Is and What It Does. How a STACK Does What It Does. Using a LIST to Implement a STACK. Using an ARRAY to Implement a STACK. A Singly Linked Implementation of STACK. Choosing the Best STACK Implementation for a Given Use. Who Needs It? Summary. Exercises. 9. Queues. What a QUEUE Is and What It Does. How a QUEUE Does What It Does. Using a LIST to Implement a QUEUE. A Singly Linked Implementation of QUEUE. Using an ARRAY to Implement a QUEUE. Choosing the Best QUEUE Implementation for a Given Use. Who Needs It? Summary. Exercises. 10. Application: Calculators. Postfix Notation (RPN). Converting from Infix to Postfix. The Design. The Implementation. Exercises. III. SORTING AND SEARCHING. 11. Dictionaries and Associations. Dictionaries. The DICTIONARY Object Structure. Associations. The Contract for DICTIONARY. Linear Search Implementation. Performance Analysis. Summary. Exercises. 12. Sorting. Sortable Lists. Insertion Sort. Bubble Sort. Selection Sort. Summary. Exercises. 13. Faster Sorting. Merge Sort. Quick Sort. Space Complexity. Choosing the Best Sorting Algorithm for a Given Use. Summary. Exercises. 14. Faster Dictionaries. Binary Search.