Skip to content

Instantly share code, notes, and snippets.

@highwaycoder
Created July 9, 2013 01:14
Show Gist options
  • Save highwaycoder/5953866 to your computer and use it in GitHub Desktop.
Save highwaycoder/5953866 to your computer and use it in GitHub Desktop.
A queue implementation in JavaScript that doesn't suck. Note that the search-based retrieval algorithm is O(n) but 'dequeue' is O(1) so the overall search speed is O(n) where it would've been O(n**2) if I used Array.shift() to perform the 'dequeue' step. Feedback welcome.
var QueueElement = function(playerInfo) {
this.name = playerInfo.name;
this.rank = playerInfo.rank;
this.last_seen = playerInfo.last_seen;
this.next = undefined;
this.prev = undefined;
}
var head = undefined,
queue_size = 0;
exports = {
addPlayer: function(playerInfo) {
if(head == undefined) {
head = new QueueElement(playerInfo);
head.next = head;
head.prev = head;
} else {
var newElement = new QueueElement(playerInfo);
newElement.next = head;
newElement.prev = head.prev;
head.prev = newElement;
}
queue_size++;
},
seekPlayer: function(rank,error_margin) {
var current_element;
for(var i = 0; i < queue_size; i++) {
if(current_element.rank <= rank + error_margin / 2 && current_element.rank >= rank - error_margin / 2) {
dequeue(current_element);
return current_element;
}
}
return undefined;
},
dequeue: function(element) {
var next = element.next,
prev = element.prev;
prev.next = next;
next.prev = prev;
element = undefined;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment