the "hat" container class [C++]

From: AngleWyrm (no_spam_anglewyrm_at_hotmail.com)
Date: 05/24/04 

Date: Mon, 24 May 2004 19:17:41 GMT

This container serves a special purpose: To be able to pull a random sample
from a collection, where the chances of each item in the collection are NOT
uniform. It can store any kind of user-defined or standard class object, as
long as the object can be evaluated to an integer.

The value of the objects in the container are the number of "chances" that
object has, to be selected. It's probabability is numChances/totalChances.
And of course totalChances is the sum of all objects.

All critiques are welcome!

/*
 * RandomContainer
 * stores and returns objects according to specified probabilities
 */
#include <cstdlib>
#include <iostream>
#include <list>
#include <ctime> // time
#include <algorithm> // copy
#include <numeric> // accumulate
#include <iterator> // ostream_iterator
using namespace std;

////////////////////////////////////////////////////////////////////////////
////
// New container: Hat
//
// Interface:
// put(object)
// pull()
// peek()
//
template<class T, class C=list<T> >class hat{
    public:
        typedef typename C::value_type value_type;
        typedef typename C::size_type size_type;
        typedef C container_type;
        typedef typename container_type::iterator iterator;
    protected:
        C c;
        value_type totalChances;

        iterator GetRandom(){
            value_type randomPoint = value_type( rand() % totalChances );
            cout << "\nrandomPoint = " << randomPoint << " / " <<
totalChances
                 << " = " << (float)randomPoint/(float)totalChances << endl;
            iterator i;
            value_type walker = 0;
            for( i = c.begin(); i != c.end(); ++i){
                walker += *i;
                if( randomPoint <= walker ){
                    cout << "FOUND: " << randomPoint << " <= " << walker
                         << " at " << *i << endl;
                    break;
                }
            }
            return i;
        }

    public:
        explicit hat(const C& incomingContainer = C() ):c(incomingContainer)
{
            totalChances = accumulate( c.begin(), c.end(), 0 ); }

        bool empty() const{ return c.empty(); }
        size_type size() const { return c.size(); }
        void clear() { c.clear(); }
        iterator begin(){ return c.begin(); }
        iterator end(){ return c.end(); }

        template <class InputIterator>
        void put( InputIterator f, InputIterator l){
            c.insert( c.end(), f, l);
            totalChances = accumulate( f, l, totalChances );
        }

        value_type pull(){
            if(c.empty()) return *c.end();

            iterator i = GetRandom();
            value_type pulledObject = *i;
            totalChances -= pulledObject;
            c.erase(i);
            return pulledObject;
        }
        value_type& peek(){
            return *GetRandom();
        }

        value_type chances(){ return totalChances; }

        // Debugging purposes only
        void Display(){
            cout << endl;
            copy( c.begin(), c.end(), ostream_iterator<int>(cout, " ") );
            cout << " size: " << c.size() << " totalChances: " <<
totalChances << endl;
        }
};

////////////////////////////////////////////////////////////////////////////
///
// Main
int main(void){
    srand( time(NULL) ); rand(); rand();

    // create some data and store it in a hat
    int data[6] = { 10, 20, 30, 1, 2, 3 }; // set of 'Chances'
    hat<int> myHat;
    myHat.put( data, data+6 );

    myHat.Display();

    for(int i = 1; i <= 3; ++i ){
        cout << "Pull(): " << myHat.pull() << endl;
        myHat.Display();
    }

    system("pause");
}

Relevant Pages

  • Re: Disable Account
    ... but I don't know the exact right as I've never thought about doing ... Pull up the properties on an OU or container and choose security, ...
    (microsoft.public.win2000.active_directory)
  • Got a solution. Looking for a problem
    ... You got a container with a pull ... string, that can ignite stuff instantly, and with only a sharp pull. ...
    (rec.pyrotechnics)
  • Re: Flat Discussion Thread
    ... container and are organizing everything and putting online! ... I would do that but chances are that they won't be $12 like they are ... Posted Via Usenet.com Premium Usenet Newsgroup Services ...
    (rec.sport.unicycling)
  • Re: Moving a shop long distance
    ... hydraulic tilt bed trailers they deliver containers on. ... or go to the terminal where the container could be put on a regular ... pounds in little stuff I could put in there, ... Is that something they could pull up onto a trailer and move 1450 ...
    (rec.crafts.metalworking)
  • Re: Can I have a Precedence Constraint within a For Loop Container?
    ... Within the container you can "Precedence constrain" the other tasks within to each other. ... What you cannot do is take a task within the container and try to join to one outside of the container. ... ForLoop on some File List which will pull one FileName out of the List ... FTP Loaction n pulls down the file on local machine. ...
    (microsoft.public.sqlserver.dts)