Contents

Preface

About the Authors

  1. Foundations

1.1 Categories of Ideas: Entity, Species, Genus

1.2 Values

1.3 Objects

1.4 Procedures

1.5 Regular Types

1.6 Regular Procedures

1.7 Concepts

1.8 Conclusions

  2. Transformations and Their Orbits

2.1 Transformations

2.2 Orbits

2.3 Collision Point

2.4 Measuring Orbit Sizes

2.5 Actions

2.6 Conclusions

  3. Associative Operations

3.1 Associativity

3.2 Computing Powers

3.3 Program Transformations

3.4 Special-Case Procedures

3.5 Parameterizing Algorithms

3.6 Linear Recurrences

3.7 Accumulation Procedures

3.8 Conclusions

  4. Linear Orderings

4.1 Classification of Relations

4.2 Total and Weak Orderings

4.3 Order Selection

4.4 Natural Total Ordering

4.5 Clusters of Derived Procedures

4.6 Extending Order-Selection Procedures

4.7 Conclusions

  5. Ordered Algebraic Structures

5.1 Basic Algebraic Structures

5.2 Ordered Algebraic Structures

5.3 Remainder

5.4 Greatest Common Divisor

5.5 Generalizing gcd

5.6 Stein gcd

5.7 Quotient

5.8 Quotient and Remainder for Negative Quantities

5.9 Concepts and Their Models

5.10 Computer Integer Types

5.11 Conclusions

  6. Iterators

6.1 Readability

6.2 Iterators

6.3 Ranges

6.4 Readable Ranges

6.5 Increasing Ranges

6.6 Forward Iterators

6.7 Indexed Iterators

6.8 Bidirectional Iterators

6.9 Random-Access Iterators

6.10 Conclusions

  7. Coordinate Structures

7.1 Bifurcate Coordinates

7.2 Bidirectional Bifurcate Coordinates

7.3 Coordinate Structures

7.4 Isomorphism, Equivalence, and Ordering

7.5 Conclusions

  8. Coordinates with Mutable Successors

8.1 Linked Iterators

8.2 Link Rearrangements

8.3 Applications of Link Rearrangements

8.4 Linked Bifurcate Coordinates

8.5 Conclusions

  9. Copying

9.1 Writability

9.2 Position-Based Copying

9.3 Predicate-Based Copying

9.4 Swapping Ranges

9.5 Conclusions

10. Rearrangements

10.1 Permutations

10.2 Rearrangements

10.3 Reverse Algorithms

10.4 Rotate Algorithms

10.5 Algorithm Selection

10.6 Conclusions

11. Partition and Merging

11.1 Partition

11.2 Balanced Reduction

11.3 Merging

11.4 Conclusions

12. Composite Objects

12.1 Simple Composite Objects

12.2 Dynamic Sequences

12.3 Underlying Type

12.4 Conclusions

Afterword

Appendix A. Mathematical Notation

Appendix B. Programming Language

B.1 Language Definition

B.2 Macros and Trait Structures

Bibliography

Index