jsos

college code for operating system fundamentals in js
priorityQueue.js

(3681B)
      1 /*
      2  * https://github.com/STRd6/PriorityQueue.js/blob/master/src/priority_queue.js
      3  *
      4  * Modified by Julio Enrique Cabrera:
      5  * - Added unix time to break priority ties. 
      6  * - Only sorts when OS has priority enabled.
      7  */
      8 (function() {
      9   /**
     10    * @private
     11    */
     12   var prioritySortLow = function(a, b) {
     13     var value = b.priority - a.priority;
     14     
     15     if(value == 0)
     16       value = prioritySortDate(a,b);
     17     return value;
     18   };
     19 
     20   /**
     21    * @private
     22    */
     23   var prioritySortHigh = function(a, b) {
     24     var value = a.priority - b.priority;
     25     
     26     if(value == 0)
     27       value = prioritySortDate(a,b);
     28     return value;
     29   };
     30 
     31   /**
     32    * @private
     33    */
     34   var prioritySortDate = function(a, b) {
     35     return b.date - a.date;
     36   };
     37 
     38   /*global PriorityQueue */
     39   /**
     40    * @constructor
     41    * @class PriorityQueue manages a queue of elements with priorities. Default
     42    * is highest priority first.
     43    *
     44    * @param [options] If low is set to true returns lowest first.
     45    */
     46   PriorityQueue = function(options) {
     47     var contents = [];
     48 
     49     var sorted = false;
     50     var sortStyle;
     51 
     52     if(options && options.low) {
     53       sortStyle = prioritySortLow;
     54     } else {
     55       sortStyle = prioritySortHigh;
     56     }
     57 
     58     /**
     59      * @private
     60      */
     61     var sort = function() {
     62       contents.sort(sortStyle);
     63       sorted = true;
     64     };
     65 
     66     /**
     67      * @private
     68      * Requires: global.js (in juliOS) 
     69      */
     70     var priority = function() {
     71       return CPU_STATE == CPU_STATE_PRIORITY.name;
     72     };
     73 
     74     var self = {
     75       /**
     76        * Removes and returns the next element in the queue.
     77        * @member PriorityQueue
     78        * @return The next element in the queue. If the queue is empty returns
     79        * undefined.
     80        *
     81        * @see PrioirtyQueue#top
     82        */
     83       pop: function() {
     84         if(!sorted && priority) {
     85           sort();
     86         }
     87 
     88         var element = contents.pop();
     89 
     90         if(element) {
     91           return element.object;
     92         } else {
     93           return undefined;
     94         }
     95       },
     96 
     97       /**
     98        * Returns but does not remove the next element in the queue.
     99        * @member PriorityQueue
    100        * @return The next element in the queue. If the queue is empty returns
    101        * undefined.
    102        *
    103        * @see PriorityQueue#pop
    104        */
    105       top: function() {
    106         if(!sorted && priority) {
    107           sort();
    108         }
    109 
    110         var element = contents[contents.length - 1];
    111 
    112         if(element) {
    113           return element.object;
    114         } else {
    115           return undefined;
    116         }
    117       },
    118 
    119       /**
    120        * @member PriorityQueue
    121        * @param object The object to check the queue for.
    122        * @returns true if the object is in the queue, false otherwise.
    123        */
    124       includes: function(object) {
    125         for(var i = contents.length - 1; i >= 0; i--) {
    126           if(contents[i].object === object) {
    127             return true;
    128           }
    129         }
    130 
    131         return false;
    132       },
    133 
    134       /**
    135        * @member PriorityQueue
    136        * @returns the current number of elements in the queue.
    137        */
    138       size: function() {
    139         return contents.length;
    140       },
    141 
    142       /**
    143        * @member PriorityQueue
    144        * @returns true if the queue is empty, false otherwise.
    145        */
    146       empty: function() {
    147         return contents.length === 0;
    148       },
    149 
    150       /**
    151        * @member PriorityQueue
    152        * @param object The object to be pushed onto the queue.
    153        * @param priority The priority of the object.
    154        */
    155       push: function(object, priority) {
    156         contents.push({
    157           object: object, 
    158           priority: priority, 
    159           date: new Date().getTime()
    160         });
    161         sorted = false;
    162       }
    163     };
    164 
    165     return self;
    166   };
    167 })();