TPIEUser Manual and ReferenceLars Arge Rakesh Barve David Hutchinson Octavian ProcopiucLaura Toma Darren Erik Vengroff Rajiv WickeremesingheDRAFT of August 29, 20022TPIE User Manual and ReferenceEdition 082902, for TPIE version 082902.Copyrightc1994, 1995 Darren Erik Vengroff, 2002 Lars Arge, Rakesh Barve, David Hutchinson, OctavianProcopiuc, Laura Toma, Darren Erik Vengroff, Rajiv Wickeremesinghe.The programs described in this manual are free software; you can redistribute them and/or modifythem under the terms of the GNU General Public License as published by the Free Software Foundation;either version 2 of the License, or (at your option) any later version.This manual and the programs it describes are distributed in the hope that they will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY orFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License (Appendix D) formore details.You should have received a copy of the GNU General Public License along with this manual; if not,write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.2ContentsIntroduction 7Acknowledgements 9I User Manual 111 Overview 131.1 Hardware Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.2 Future releases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Obtaining and Installing TPIE 152.1 Licensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Where to get TPIE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.4 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A Taste of TPIE via a Sample Program 173.1 Sample Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Discussion of Sample Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 Tutorial 234.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3 Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.4 Operation Management Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5 Scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5.1 Basic Scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5.2 ASCII Input/Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.5.3 Multi-Type Scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.5.4 Out of Step Scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.6 Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.6.1 Implementing Mergesort: An Extended Example . . . . . . . . . . . . . . . . . . . 324.7 Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.8 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.8.1 Comparison Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.8.2 Merge Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.8.3 Key Bucket Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …