Skip to content

Instantly share code, notes, and snippets.

@dwaltrip
Last active August 29, 2015 13:57
Show Gist options
  • Save dwaltrip/9611864 to your computer and use it in GitHub Desktop.
Save dwaltrip/9611864 to your computer and use it in GitHub Desktop.
Code snippet that can take a set of ordered integer streams and return a merged, ordered stream
// helper functions
// includes end points as possible return values
var randint = function(min, max) {
return (Math.floor(Math.random() * (max - min + 1)) + min);
}
// I was surprised to find out this is necessary to get a numerical sort
function sort_number(a,b) {
if (a < b)
return -1;
else if(a > b)
return 1;
return 0;
}
function has_key(obj, key) {
return Object.prototype.hasOwnProperty.call(obj, key);
};
// quick prototype IntStream object, for testing the merge_streams method
var IntStream = function(params) {
if (typeof(params)==='undefined') params = {};
if (typeof(params.size)==='undefined') params.size = randint(10, 20);
if (typeof(params.ordered)==='undefined') params.ordered = true;
if (typeof(params.empty)==='undefined') params.empty = false;
if (typeof(params.name)==='undefined') params.name = '';
this.name = params.name;
var size = params.size;
var ordered = params.ordered;
var empty = params.empty;
var that = this;
var elements = [];
var init = function() {
if (!empty) {
for(var i=0; i<size; i++)
elements.push(randint(1,100));
if (ordered)
elements.sort(sort_number);
}
};
this.append = function(new_elem) {
elements.push(new_elem);
}
this.print = function() {
console.log('Stream', that.name, '--', JSON.stringify(elements));
}
this.pop = function() {
if (elements.length > 0)
return elements.shift();
else
return false;
}
this.peek = function() {
if (elements.length > 0)
return elements[0];
else
return false;
}
this.has_data = function() {
return (elements.length > 0);
}
init();
}
//*************************************
// the function that sovles the problem
//*************************************
//
// Assumptions: stream objects have the methods 'pop', 'has_data', and 'peek'
// If the streams do not have 'peek', we can modify the merger method to cache the first values of each stream locally
//
// The input 'streams' parameter is a simple object with string keys and values that are stream objects
var merge_streams = function(streams) {
// I added 'append' to IntStream so we could use the object to make the resulting merged stream
var merged = new IntStream({ empty: true, name: 'merged' });
while(true) {
var sorted_streams = [];
for(var key in streams) {
var stream = streams[key];
if (stream.has_data())
sorted_streams.push(stream);
}
sorted_streams.sort(function(s1, s2) {
if (s1.peek() < s2.peek()) return -1;
if (s1.peek() > s2.peek()) return 1;
return 0;
});
var cutoff = null;
if (sorted_streams.length > 0)
cutoff = sorted_streams[0].peek();
for (var i=0; i < sorted_streams.length; i++) {
var stream = sorted_streams[i];
while (stream.has_data() > 0 && stream.peek() <= cutoff) {
var next_elem = stream.pop();
if (next_elem !== false) {
merged.append(next_elem);
if (i < sorted_streams.length - 1)
cuttoff = Math.min(stream.peek(), sorted_streams[i+1].peek());
else
cutoff = stream.peek() + 1;
}
}
}
if (sorted_streams.length == 0)
break;
}
return merged;
}
// example of using the stream merger
var streams = {
a: new IntStream({ name: 'a', size: 5 }),
b: new IntStream({ name: 'b', size: 5 }),
c: new IntStream({ name: 'c', size: 5 }),
d: new IntStream({ name: 'd', size: 5 }),
e: new IntStream({ name: 'e', size: 5 })
}
for(var key in streams) {
var stream = streams[key];
stream.print();
}
var merged_stream = merge_streams(streams);
merged_stream.print();
// and it works! woot
@dwaltrip
Copy link
Author

Made some minor improvements

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment