home *** CD-ROM | disk | FTP | other *** search
/ Chip 2002 May / Chip_2002-05_cd1.bin / chplus / cpp / 3 / stl.exe / alg3.cpp < prev    next >
C/C++ Source or Header  |  1998-02-09  |  10KB  |  325 lines
  1. #include "stlexam.h"
  2. #pragma hdrstop
  3. /**************************************************************************
  4.  *
  5.  * alg3.cpp - Sample programs for STL generic algorihtms that modify 
  6.  *   their arguments in place.  Section 12.4
  7.  *
  8.  * $Id: alg3.cpp,v 1.17 1996/08/28 01:18:47 smithey Exp $
  9.  *
  10.  ***************************************************************************
  11.  *
  12.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  13.  * ALL RIGHTS RESERVED *
  14.  * The software and information contained herein are proprietary to, and
  15.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  16.  * intends to preserve as trade secrets such software and information.
  17.  * This software is furnished pursuant to a written license agreement and
  18.  * may be used, copied, transmitted, and stored only in accordance with
  19.  * the terms of such license and with the inclusion of the above copyright
  20.  * notice.  This software and information or any other copies thereof may
  21.  * not be provided or otherwise made available to any other person.
  22.  *
  23.  * Notwithstanding any other lease or license that may pertain to, or
  24.  * accompany the delivery of, this computer software and information, the
  25.  * rights of the Government regarding its use, reproduction and disclosure
  26.  * are as set forth in Section 52.227-19 of the FARS Computer
  27.  * Software-Restricted Rights clause.
  28.  * 
  29.  * Use, duplication, or disclosure by the Government is subject to
  30.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  31.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  32.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  33.  * P.O. Box 2328, Corvallis, Oregon 97339.
  34.  *
  35.  * This computer software and information is distributed with "restricted
  36.  * rights."  Use, duplication or disclosure is subject to restrictions as
  37.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  38.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  39.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  40.  * then the "Alternate III" clause applies.
  41.  *
  42.  **************************************************************************/
  43.   
  44. #ifndef _RWSTD_HEADER_REQUIRES_HPP
  45. #include <vector>
  46. #include <list>
  47. #include <algorithm>
  48. #include <functional>
  49. #include <ctype.h>
  50. #include <string>
  51. #include <string.h>
  52. #else
  53. #include <vector.hpp>
  54. #include <list.hpp>
  55. #include <algorithm.hpp>
  56. #include <functional.hpp>
  57. #include <ctype.h>
  58. #include <string.hpp>
  59. #include <string.h>
  60. #endif
  61.  
  62. #ifdef _RW_STD_IOSTREAM
  63. #include <iostream>
  64. #else
  65. #include <iostream.h>
  66. #endif
  67.   
  68. #ifndef _RWSTD_NO_NAMESPACE
  69.   using namespace std;
  70. #endif
  71.  
  72. class iotaGenerator
  73. {
  74.   public:
  75.     iotaGenerator (int iv) : current(iv) { }
  76.     int operator () () { return current++; }
  77.   private:
  78.     int current;
  79. };
  80.  
  81. bool isEven (int n) { return 0 == (n % 2); }
  82.  
  83. //
  84. // Illustrate the use of the reverse function.
  85. //
  86.  
  87. void reverse_example ()
  88. {
  89.     cout << "Illustrate reverse algorithm" << endl;
  90.     //
  91.     // Example 1, reversing a string.
  92.     //
  93.     char text[30] = "Rats live on no evil star";
  94.     reverse (text, text + strlen(text));
  95.     cout << text << endl;
  96.     //
  97.     // Example 2, reversing a list.
  98.     //
  99.     list<int,allocator<int> > iList;
  100.     generate_n(inserter(iList, iList.begin()), 10, iotaGenerator(2));
  101.     reverse (iList.begin(), iList.end());
  102.     copy (iList.begin(), iList.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  103.     cout << endl;    
  104. }
  105.  
  106. //
  107. // Illustrate the use of the replace function.
  108. //
  109.  
  110. void replace_example ()
  111. {
  112.     cout << "Illustrate replace algorithm" << endl;
  113.     //
  114.     // Make vector 0 1 2 3 4.
  115.     //
  116.     vector<int,allocator<int> > numbers(11);    
  117.     for (int i = 0; i < 11; i++)
  118.         numbers[i] = i < 5 ? i : 10 - i;
  119.     copy (numbers.begin(), numbers.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  120.     cout << endl;
  121.     //
  122.     // Replace 0 by 2.
  123.     //
  124.     replace (numbers.begin(), numbers.end(), 3, 7);
  125.     copy (numbers.begin(), numbers.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  126.     cout << endl;
  127.     //
  128.     // Replace even numbers by 9.
  129.     //
  130.     replace_if (numbers.begin(), numbers.end(), isEven, 9);
  131.     copy (numbers.begin(), numbers.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  132.     cout << endl;
  133.     //    
  134.     // Copy into a list, replacing 9 by 3.
  135.     //
  136.     int aList[] = { 2, 1, 4, 3, 2, 5 };
  137.     int bList[6];
  138.     int cList[6];
  139.     replace_copy (aList, aList+6, &bList[0], 2, 7);
  140.     replace_copy_if (bList, bList+6, &cList[0], bind2nd(greater<int>(), 3), 8);
  141.     copy (bList, bList + 6, ostream_iterator<int,char,char_traits<char> >(cout, " ")); cout << endl;
  142.     copy (cList, cList + 6, ostream_iterator<int,char,char_traits<char> >(cout, " ")); cout << endl;
  143. }
  144.  
  145. //
  146. // Illustrate the use of the rotate function.
  147. //
  148.  
  149. void rotate_example ()
  150. {
  151.     cout << "Illustrate rotate algorithm" << endl;
  152.     //
  153.     // Create the list 1 2 3 ... 10
  154.     //
  155.     list<int,allocator<int> > iList;
  156.     generate_n(inserter(iList, iList.begin()), 10, iotaGenerator(1));
  157.     //
  158.     // Find the location of the seven.
  159.     //
  160.     list<int,allocator<int> >::iterator  middle = find(iList.begin(), iList.end(), 7);
  161.     //
  162.     // Now rotate around that location.
  163.     //
  164.     rotate(iList.begin(), middle, iList.end());
  165.     copy (iList.begin(), iList.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  166.     cout << endl;
  167.     //    
  168.     // Rotate again around the same location.
  169.     //
  170.     list<int,allocator<int> > cList;
  171.     rotate_copy(iList.begin(), middle,iList.end(),
  172.                 inserter(cList, cList.begin()));
  173.     copy (cList.begin(), cList.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  174.     cout << endl; 
  175. }
  176.  
  177. //
  178. // Illustrate the use of the paration function.
  179. //
  180.  
  181. void partition_example ()
  182. {
  183.     cout << "Illustrate partition algorithm" << endl;
  184.     //
  185.     // First make the vector 1 2 3 ... 10.
  186.     //
  187.     vector<int,allocator<int> > numbers(10);
  188.     generate(numbers.begin(), numbers.end(), iotaGenerator(1));
  189.     //
  190.     // Now put the odd values low, even values high.
  191.     //
  192.     vector<int,allocator<int> >::iterator result = partition(numbers.begin(),numbers.end(),
  193.                                              isEven);
  194.     copy (numbers.begin(), numbers.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  195.     cout << endl;
  196.     cout << "middle location " << result - numbers.begin() << endl; 
  197.     //
  198.     // Now do a stable partition.
  199.     //
  200.     generate(numbers.begin(), numbers.end(), iotaGenerator(1));
  201.     copy (numbers.begin(), numbers.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  202.     cout << endl;
  203. }
  204.  
  205. bool nameCompare (char * a, char * b) { return strcmp(a, b) <= 0; }
  206.  
  207. //
  208. // Illustrate the use of the next_permutation function.
  209. //
  210.  
  211. void permutation_example ()
  212. {
  213.     //
  214.     // Start with the values 1 2 3 in sequence.
  215.     //
  216.     int start [] = {1, 2, 3 };
  217.     
  218.     do
  219.     {
  220.         copy (start, start + 3, ostream_iterator<int,char,char_traits<char> >(cout, " "));
  221.         cout << endl;
  222.     }
  223.     while (next_permutation(start, start + 3));
  224.         
  225.     char * names[] = { "Alpha", "Beta", "Gamma" };
  226.  
  227.     do
  228.     {
  229.         copy (names, names + 3, ostream_iterator<char *,char,char_traits<char> >(cout, " "));
  230.         cout << endl;
  231.     }
  232.     while (next_permutation(names, names + 3, nameCompare));
  233.     
  234.     char * word = "bela";
  235.  
  236.     do
  237.         cout << word << ' ';
  238.     while (prev_permutation(word, &word[4]));
  239.  
  240.     cout << endl;   
  241. }
  242.  
  243. //
  244. // Illustrate the use of the inplace_merge function.
  245. //
  246.  
  247. void inplace_merge_example ()
  248. {
  249.     cout << "Illustrate inplace merge algorithm" << endl;
  250.     //
  251.     // First generate the numbers 0 2 4 6 8 1 3 5 7 9.
  252.     //
  253.     vector<int,allocator<int> > numbers(10);
  254.     for (int i = 0; i < 10; i++)
  255.         numbers[i] = i < 5 ? 2 * i : 2 * (i - 5) + 1;
  256.     copy (numbers.begin(), numbers.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  257.     cout << endl; 
  258.     vector<int,allocator<int> >::iterator midvec = find(numbers.begin(), numbers.end(), 1);
  259.     //
  260.     // Copy them into a list.
  261.     //
  262.     list<int,allocator<int> > numList;
  263.     copy(numbers.begin(), numbers.end(), inserter(numList, numList.begin()));
  264.     list<int,allocator<int> >::iterator midList = find(numList.begin(), numList.end(), 1);
  265.     copy (numList.begin(), numList.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  266.     cout << endl; 
  267.     //
  268.     // Now put them back together.
  269.     //
  270.     inplace_merge(numbers.begin(), midvec, numbers.end());
  271.     inplace_merge(numList.begin(), midList, numList.end());
  272.     copy (numList.begin(), numList.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  273.     cout << endl; 
  274. }
  275.  
  276. struct RandomInteger
  277. {
  278.     int operator() (int m) { return rand() % m; }
  279. };
  280.  
  281. //
  282. // Illustrate the use of the random_shuffle function.
  283. //
  284.  
  285. void random_shuffle_example ()
  286. {
  287.     //
  288.     // First make the vector 1 2 3 ... 10.
  289.     //
  290.     vector<int,allocator<int> > numbers(10);
  291.     generate(numbers.begin(), numbers.end(), iotaGenerator(1));
  292.  
  293.     RandomInteger random;
  294.  
  295.     //
  296.     // Randomly shuffle the elements.
  297.     //
  298.     random_shuffle(numbers.begin(), numbers.end(), random);
  299.     copy (numbers.begin(), numbers.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  300.     cout << endl;
  301.     //
  302.     // Do it again.
  303.     //
  304.     random_shuffle(numbers.begin(), numbers.end(), random);
  305.     copy (numbers.begin(), numbers.end(), ostream_iterator<int,char,char_traits<char> >(cout, " "));
  306.     cout << endl;
  307. }
  308.  
  309. int main ()
  310. {
  311.     cout << "STL generic algorithms -- in-place algorithms" << endl;
  312.  
  313.     reverse_example();
  314.     replace_example();
  315.     rotate_example();
  316.     partition_example();
  317.     permutation_example();
  318.     inplace_merge_example();
  319.     random_shuffle_example();
  320.     
  321.     cout << "End of in-place algorithm sample program"  << endl;
  322.  
  323.     return 0;
  324. }
  325.