sorted.h

Think in C++文中代码实现

// File from page 618 in "Thinking in C++" by Bruce Eckel
//////////////////////////////////////////////////
// From the compressed package ECKELT02.ZIP 4/11/95
// (Original ECKELT01.ZIP dated 2/21/95)
// Copyright (c) Bruce Eckel, 1995 
// Source code file from the book "Thinking in C++", 
// Prentice Hall, 1995, ISBN: 0-13-917709-4
// All rights reserved EXCEPT as allowed by the following 
// statements: You may freely use this file for your own 
// work, including modifications and distribution in 
// executable form only. You may copy and distribute this 
// file, as long as it is only distributed in the complete 
// (compressed) package with the other files from this 
// book and you do not remove this copyright and notice. 
// You may not distribute modified versions of the source 
// code in this package. This package may be freely placed 
// on bulletin boards, internet nodes, shareware disks and 
// product vendor disks. You may not use this file in 
// printed media without the express permission of the 
// author. Bruce Eckel makes no 
// representation about the suitability of this software 
// for any purpose. It is provided "as is" without express 
// or implied warranty of any kind. The entire risk as to 
// the quality and performance of the software is with 
// you. Should the software prove defective, you assume 
// the cost of all necessary servicing, repair, or 
// correction. 
// If you think you've found an error, please 
// email all modified files with loudly commented changes 
// to: [e-mail] (please use the same 
// address for non-code errors found in the book).
//////////////////////////////////////////////////

//: SORTED.H -- Template inheritance
#ifndef SORTED_H_
#define SORTED_H_
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "..\14\tstash.h"
#include "..\14\set.h"

template<class T>
class sorted :  public tstash<T> {
  void bubblesort();
public:
  int add(T* element) {
    tstash<T>::add(element);
    bubblesort();
    return 0; // Sort moves the element
  }
};

template<class T>
void sorted<T>::bubblesort() {
  for(int i = count(); i > 0; i--)
    for(int j = 1; j < i; j++)
      if(*storage[j-1] > *storage[j]) {
        // Swap the two elements:
        T* t = storage[j-1];
        storage[j-1] = storage[j];
        storage[j] = t;
      }
}

// Quick & dirty sorted set:
template<class T>
class sortedSet : public set<T> {
  sorted<T> Sorted;
public:
  void add(T& e) {
    if(contains(e)) return;
    set<T>::add(e);
    Sorted.add(new T(e));
  }
  T& operator[] (int index) {
    assert(index >= 0 && index < length());
    assert(Sorted[index]);
    return *Sorted[index];
  }
  int length() {
    return Sorted.count();
  }
};

// Unique random number generator:
template<int upper_bound>
class urand {
  int map[upper_bound];
  int recycle;
public:
  urand(int Recycle = 0);
  int operator()();
};

template<int upper_bound>
urand<upper_bound>::urand(int Recycle = 0)
  : recycle(Recycle) {
  memset(map, 0, upper_bound * sizeof(int));
  // Seed the random number generator:
  time_t t;
  srand((unsigned)time(&t));
}

template<int upper_bound>
int urand<upper_bound>::operator()() {
  if(!memchr(map, 0, upper_bound)) {
    if(recycle)
      memset(map, 0,
             sizeof(map) * sizeof(int));
    else
      return -1; // No more spaces left
  }
  int newval;
  while(map[newval = rand() % upper_bound])
    ; // Until unique value is found
  map[newval]++; // Set flag
  return newval;
}
#endif // SORTED_H_