The Ada(r) Generic Library: Linear List Processing Packages

ISBN-13: 9781468470918 / Angielski / Miękka / 2012 / 264 str.

David R. Musser; Alexander A. Stepanov

Opis

The Ada Generic Library provides an extensive well-documented library of generic packages whose use can substantially increase software productivity and reliability. The construction of the library follows a new approach whose principles include the following: - Extensive use of generic algorithms, such as generic sort and merge. - Building up functionality in layers. - Obtaining high efficiency in spite of the layering through the use of Ada's inline compiler directive. This volume contains eight Ada packages, with over 170 subprograms for various linear data structures based on linked lists. Professional Ada programmers will find The Ada Generic Library an invaluable tool in building application programs or in further construction of generic libraries. For these users the source code can be obtained on diskettes. The volume will also be useful to those interested in programming methodology, software reusability, and software engineering.

Spis treści

I Unrestricted-Access Data Structures.- 1 Introduction.- 1.1 Principles behind the library.- 1.2 Relation to software engineering goals.- 1.3 Structure of the library.- 1.3.1 Data abstractions.- 1.3.2 Algorithmic abstractions.- 1.3.3 Structural abstractions.- 1.3.4 Representational abstractions.- 1.4 Selection from the library.- 1.5 Using the library.- 1.6 Future directions.- 1.7 References.- 2 Linear Data Structures.- 2.1 Sequences.- 2.2 Organization.- 2.2.1 Low-level data abstractions.- 2.2.2 Algorithmic, structural and representational abstractions.- 2.3 Selection from the library.- 2.4 Package descriptions.- 3 System Allocated Singly Linked Package.- 3.1 Overview.- 3.2 Package specification.- 3.3 Package body.- 3.4 Subprograms.- 3.4.1 Construct.- 3.4.2 First.- 3.4.3 Free.- 3.4.4 Next.- 3.4.5 Set_First.- 3.4.6 Set_Next.- 4 User Allocated Singly Linked Package.- 4.1 Overview.- 4.2 Package specification.- 4.3 Package body.- 4.4 Subprograms.- 4.4.1 Construct.- 4.4.2 First.- 4.4.3 Free.- 4.4.4 Next.- 4.4.5 Set_First.- 4.4.6 Set_Next.- 5 Auto-Reallocating Singly Linked Package.- 5.1 Overview.- 5.2 Package specification.- 5.3 Package body.- 5.4 Subprograms.- 5.4.1 Construct.- 5.4.2 First.- 5.4.3 Free.- 5.4.4 Next.- 5.4.5 Set_First.- 5.4.6 Set_Next.- 6 Singly Linked Lists Package.- 6.1 Overview.- 6.1.1 Construction and modification of sequences.- 6.1.2 Examining sequences.- 6.1.3 Computing with sequences.- 6.1.4 Exception handling.- 6.1.5 Notes on efficiency.- 6.1.6 Implementation notes.- 6.1.7 Orderings for Merge and Sort.- 6.2 Package specification.- 6.3 Package body.- 6.4 Definitions for the examples.- 6.5 Subprograms.- 6.5.1 Append.- 6.5.2 Butlast.- 6.5.3 Butlast_Copy.- 6.5.4 Concatenate.- 6.5.5 Concatenate_Copy.- 6.5.6 Construct.- 6.5.7 Copy_First_N.- 6.5.8 Copy_Sequence.- 6.5.9 Count.- 6.5.10 Count_If.- 6.5.11 Count_If_Not.- 6.5.12 Delete.- 6.5.13 Delete_Copy.- 6.5.14 Delete_Copy_Duplicates.- 6.5.15 Delete_Copy_If.- 6.5.16 Delete_Copy_If_Not.- 6.5.17 Delete_Duplicates.- 6.5.18 Delete_If.- 6.5.19 Delete_If_Not.- 6.5.20 Equal.- 6.5.21 Every.- 6.5.22 Find.- 6.5.23 Find_If.- 6.5.24 Find_If_Not.- 6.5.25 First.- 6.5.26 For_Each.- 6.5.27 For_Each_Cell.- 6.5.28 For_Each_2.- 6.5.29 For_Each_Cell_2.- 6.5.30 Free.- 6.5.31 Free_Sequence.- 6.5.32 Invert.- 6.5.33 Invert_Copy.- 6.5.34 Is_End.- 6.5.35 Is_Not_End.- 6.5.36 Last.- 6.5.37 Length.- 6.5.38 Make_Sequence.- 6.5.39 Map.- 6.5.40 Map_2.- 6.5.41 Map_Copy.- 6.5.42 Map_Copy_2.- 6.5.43 Merge.- 6.5.44 Mismatch.- 6.5.45 Next.- 6.5.46 Not_Any.- 6.5.47 Not_Every.- 6.5.48 Nth.- 6.5.49 Nth_Rest.- 6.5.50 Position.- 6.5.51 Position_If.- 6.5.52 Position_If_Not.- 6.5.53 Reduce.- 6.5.54 Reverse_Append.- 6.5.55 Reverse_Concatenate.- 6.5.56 Search.- 6.5.57 Set_First.- 6.5.58 Set_Next.- 6.5.59 Set_Nth.- 6.5.60 Some.- 6.5.61 Sort.- 6.5.62 Subsequence.- 6.5.63 Substitute.- 6.5.64 Substitute_Copy.- 6.5.65 Substitute_Copy_If.- 6.5.66 Substitute_Copy_If_Not.- 6.5.67 Substitute_If.- 6.5.68 Substitute_If_Not.- 7 Linked List Algorithms Package.- 7.1 Overview.- 7.2 Package specification.- 7.3 Package body.- 7.4 Subprograms.- 7.4.1 Accumulate.- 7.4.2 Advance.- 7.4.3 Append.- 7.4.4 Append_First_N.- 7.4.5 Attach_To_Tail.- 7.4.6 Count.- 7.4.7 Delete_Copy_Append.- 7.4.8 Delete_Copy_Duplicates_Append.- 7.4.9 Delete_Duplicates.- 7.4.10 Equal.- 7.4.11 Every.- 7.4.12 Find.- 7.4.13 For_Each_Cell.- 7.4.14 For_Each_Cell_2.- 7.4.15 Invert_Partition.- 7.4.16 Last.- 7.4.17 Length.- 7.4.18 Map_Copy_2_Append.- 7.4.19 Map_Copy_Append.- 7.4.20 Merge.- 7.4.21 Merge_Non_Empty.- 7.4.22 Mismatch.- 7.4.23 Not_Any.- 7.4.24 Not_Every.- 7.4.25 Nth_Rest.- 7.4.26 Position.- 7.4.27 Reverse_Append.- 7.4.28 Reverse_Concatenate.- 7.4.29 Search.- 7.4.30 Some.- 7.4.31 Sort.- 8 Using the Packages.- 8.1 Partially instantiated packages.- 8.1.1 Using System Allocated Singly Linked.- 8.1.2 Using User Allocated Singly Linked.- 8.1.3 Using Auto Reallocating Singly Linked.- 8.2 Integer instantiation.- 8.3 Test suite and output.- II Restricted-Access Data Structures.- 9 Introduction.- 10 Double Ended Lists Package.- 10.1 Overview.- 10.1.1 A model of double-ended-lists.- 10.1.2 Invariants.- 10.1.3 Classification of operations.- 10.1.4 Construction and modification of sequences.- 10.1.5 Examining sequences.- 10.1.6 Computing with sequences.- 10.2 Package specification.- 10.3 Package body.- 10.4 Definitions for the examples.- 10.5 Subprograms.- 10.5.1 Add_Current.- 10.5.2 Add_First.- 10.5.3 Add_Last.- 10.5.4 Advance.- 10.5.5 Concatenate.- 10.5.6 Copy_Sequence.- 10.5.7 Count.- 10.5.8 Count_If.- 10.5.9 Count_If_Not.- 10.5.10 Current.- 10.5.11 Delete.- 10.5.12 Delete_Duplicates.- 10.5.13 Delete_If.- 10.5.14 Delete_If_Not.- 10.5.15 Drop_Head.- 10.5.16 Drop_Tail.- 10.5.17 Equal.- 10.5.18 Every.- 10.5.19 Find.- 10.5.20 Find_If.- 10.5.21 Find_If_Not.- 10.5.22 First.- 10.5.23 For_Each.- 10.5.24 For_Each_2.- 10.5.25 Free.- 10.5.26 Initialize.- 10.5.27 Invert.- 10.5.28 Is_Empty.- 10.5.29 Is_End.- 10.5.30 Last.- 10.5.31 Length.- 10.5.32 Map.- 10.5.33 Map_2.- 10.5.34 Merge.- 10.5.35 Mismatch.- 10.5.36 Not_Any.- 10.5.37 Not_Every.- 10.5.38 Reduce.- 10.5.39 Search.- 10.5.40 Set_Current.- 10.5.41 Set_First.- 10.5.42 Set_Last.- 10.5.43 Some.- 10.5.44 Sort.- 10.5.45 Split.- 10.5.46 Substitute.- 10.5.47 Substitute_If.- 10.5.48 Substitute_If_Not.- 11 Stacks Package.- 11.1 Package specification.- 11.2 Package body.- 11.3 Definitions for the examples.- 11.4 Subprograms.- 11.4.1 Create.- 11.4.2 For_Each.- 11.4.3 Is_Empty.- 11.4.4 Pop.- 11.4.5 Push.- 11.4.6 Top.- 12 Output Restricted Deques Package.- 12.1 Package specification.- 12.2 Package body.- 12.3 Definitions for the examples.- 12.4 Subprograms.- 12.4.1 Create.- 12.4.2 For_Each.- 12.4.3 Front.- 12.4.4 Is_Empty.- 12.4.5 Pop_Front.- 12.4.6 Push_Front.- 12.4.7 Push_Rear.- 12.4.8 Rear.- 13 Using the Packages.- 13.1 Partially instantiated packages.- 13.1.1 PIPs for Double Ended Lists.- 13.1.2 PIPs for Stacks.- 13.1.3 PIPs for Output Restricted Deques.- 13.2 Test suites and output.- A Examples Help Package.- B Combining Stacks with a Vector Representation.- B.1 Simple_Indexed_Vectors package specification.- B.2 Simple_Indexed_Vectors package body.- B.3 A PIP combining Vectors and Stacks.