public
Last active

Evenly distribute new elements between existing queues in a vector.

  • Download Gist
Main.cpp
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
#include <vector>
#include <queue>
#include <iostream>
#include <random>
#include <string>
 
#include "QueueManip.h"
 
 
void printSizes(const vector_type & v)
{
for ( unsigned i=0; i<v.size(); ++i )
std::cout << i << ": " << v[i].size() << '\n' ;
}
 
vector_type generateJagged(unsigned maxElements=10, unsigned minLength=0, unsigned maxLength=25)
{
static std::mt19937 gen((std::random_device()())) ;
std::uniform_int_distribution<unsigned> size_rng(minLength, maxLength) ;
 
vector_type v(maxElements) ;
 
for ( auto & element : v )
{
unsigned queueSize = size_rng(gen) ;
for ( unsigned i=0; i< queueSize; ++i )
element.push(int()) ;
}
 
return v ;
}
 
std::vector<int> generateElementsToAdd(unsigned elements)
{
return std::vector<int>(elements) ;
}
 
int main()
{
char const * prompt = "Add how many elements? " ;
unsigned input ;
 
while ( std::cout << prompt && std::cin >> input )
{
auto v = generateJagged() ;
printSizes(v) ;
std::cout << '\n' ;
 
addElements(v, generateElementsToAdd(input)) ;
printSizes(v) ;
std::cout << '\n' ;
}
}
QueueManip.cpp
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
#include <functional>
#include <queue>
#include <vector>
 
#include "QueueManip.h"
 
namespace {
typedef std::reference_wrapper<std::queue<int>> queue_ref_type ;
 
std::vector<queue_ref_type> bySize( vector_type& v )
{
std::vector<queue_ref_type> index ;
for ( auto & element : v )
index.emplace_back(element) ;
 
std::sort(index.begin(), index.end(),
[](queue_ref_type a, queue_ref_type b)
{ return a.get().size() < b.get().size() ; }) ;
return index ;
}
 
unsigned calculateMinimumSize( const std::vector<queue_ref_type>& queues, unsigned numToAdd )
{
unsigned index = 1 ;
unsigned free = 1 ;
unsigned occupied = queues.front().get().size() ;
unsigned prevSize = occupied ;
while ( index != queues.size() && free < numToAdd )
{
const unsigned curSize = queues[index].get().size() ;
occupied += curSize ;
 
free += (curSize-prevSize) * index ;
 
prevSize = curSize ;
++index ;
}
 
return (occupied + numToAdd) / index ;
}
}
 
void addElements( vector_type& container, const std::vector<int>& elements )
{
if ( container.size() == 0 )
return ;
 
auto indexed = bySize(container) ;
auto minimumSize = calculateMinimumSize(indexed, elements.size()) ;
 
unsigned added = 0 ;
auto it = indexed.begin() ;
 
while ( it != indexed.end() && added < elements.size() )
{
std::queue<int>& queue = *it ;
 
if ( queue.size() < minimumSize )
queue.push(elements[added++]) ;
else
++it ;
}
 
// (indexed.size() > elements.size()-added) should be true here.
 
it = indexed.begin();
while ( added < elements.size() )
{
std::queue<int>& queue = *it++ ;
queue.push(elements[added++]) ;
}
}
QueueManip.h
C++
1 2 3 4 5 6 7 8
#ifndef EMS_QUEUEMANIP_H_
#define EMS_QUEUEMANIP_H_
 
typedef std::vector<std::queue<int>> vector_type ;
 
void addElements( vector_type& container, const std::vector<int>& elements );
 
#endif

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.