×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Javascript
Posted by: Isaac Dettman
Added: Nov 26, 2016 6:14 PM
Modified: Nov 26, 2016 6:18 PM
Views: 4
Queue
  1. function Queue(capacity){
  2.     'use strict';
  3.  
  4.     if((typeof capacity === 'undefined') || capacity <= 0){
  5.         capacity = 100;
  6.     }
  7.  
  8.     this.capacity = capacity;
  9.     this.container = [];
  10.     this.nextWriteIndex = 0;
  11.     this.nextReadIndex = 0;
  12.     this.lastWriteIndex = null;
  13.     this.lastReadIndex = null;
  14. }
  15.  
  16. Queue.prototype.getCapacity = function(){
  17.     'use strict';
  18.     return this.capacity;
  19. };
  20.  
  21. Queue.prototype.getCount = function(){
  22.     'use strict';
  23.  
  24.     if(this.noOneEverWrite())
  25.         return 0;
  26.  
  27.     if(this.noOneEverRead())
  28.         return this.lastWriteIndex + 1;
  29.  
  30.     if(this.writtenMoreOrAsMuchAsRead())
  31.         return this.lastWriteIndex - this.lastReadIndex;
  32.  
  33.     return this.capacity + this.lastWriteIndex - this.lastReadIndex;
  34.  
  35. };
  36.  
  37. Queue.prototype.noOneEverWrite = function(){
  38.     'use strict';
  39.  
  40.     return this.lastWriteIndex === null;
  41. };
  42.  
  43. Queue.prototype.noOneEverRead = function(){
  44.     'use strict';
  45.  
  46.     return this.lastReadIndex === null;
  47. };
  48.  
  49. Queue.prototype.writtenMoreOrAsMuchAsRead = function(){
  50.     'use strict';
  51.  
  52.     return this.lastWriteIndex >= this.lastReadIndex;
  53. };
  54.  
  55. Queue.prototype.enqueue = function(item){
  56.     'use strict';
  57.  
  58.     if(this.getCount() === this.capacity)
  59.         throw new Error("Queue is full!");
  60.  
  61.     this.container[this.nextWriteIndex] = item;
  62.  
  63.     this.updateWriteIndicies();
  64. };
  65.  
  66. Queue.prototype.updateWriteIndicies = function(){
  67.     'use strict';
  68.  
  69.     this.lastWriteIndex = this.nextWriteIndex;
  70.  
  71.     if (this.nextWriteIndex + 1 === this.capacity)
  72.         this.nextWriteIndex = 0;
  73.     else
  74.         this.nextWriteIndex++;
  75. };
  76.  
  77. Queue.prototype.dequeue = function(){
  78.     'use strict';
  79.  
  80.     if(this.getCount() === 0)
  81.         throw new Error("Queue is empty!");
  82.  
  83.     var item = this.container[this.nextReadIndex];
  84.  
  85.     this.updateReadIndicies();
  86.  
  87.     return item;
  88. };
  89.  
  90. Queue.prototype.peek = function(){
  91.     'use strict';
  92.  
  93.     if(this.getCount() === 0)
  94.         throw new Error("Queue is empty!");
  95.  
  96.     var item = this.container[this.nextReadIndex];
  97.  
  98.     return item;
  99. };
  100.  
  101. Queue.prototype.last = function(){
  102.     'use strict';
  103.  
  104.     if(this.getCount() === 0)
  105.         throw new Error("Queue is empty!");
  106.  
  107.     var item = this.container[this.lastWriteIndex];
  108.  
  109.     return item;
  110. };
  111.  
  112. Queue.prototype.updateReadIndicies = function(){
  113.     'use strict';
  114.  
  115.     this.lastReadIndex = this.nextReadIndex;
  116.  
  117.     if (this.nextReadIndex + 1 === this.capacity)
  118.         this.nextReadIndex = 0;
  119.     else
  120.         this.nextReadIndex++;
  121. };
  122.  
  123. module.exports = Queue;
  124.  
  125. /*
  126. describe('Queue', function(){
  127.     'use strict';
  128.  
  129.     var Queue, capacity, queue;
  130.  
  131.     beforeEach(function(){
  132.                 Queue = require('../index');
  133.         capacity = 10;
  134.         queue = Queue.create(capacity);
  135.     });
  136.  
  137.     it('should return queue capacity and count', function(){
  138.  
  139.         expect(queue.getCapacity()).toEqual(capacity);
  140.         expect(queue.getCount()).toEqual(0);
  141.  
  142.     });
  143.  
  144.     it('should set default capacity value', function(){
  145.  
  146.         var default_capacity_queue = Queue.create(-1);
  147.         expect(default_capacity_queue.getCapacity()).toEqual(100);
  148.  
  149.         default_capacity_queue = Queue.create(0);
  150.         expect(default_capacity_queue.getCapacity()).toEqual(100);
  151.  
  152.         default_capacity_queue = Queue.create();
  153.         expect(default_capacity_queue.getCapacity()).toEqual(100);
  154.     });
  155.  
  156.     it('should enqueue value', function(){
  157.  
  158.         queue.enqueue({ name: 'value' });
  159.  
  160.         expect(queue.getCount()).toEqual(1);
  161.  
  162.     });
  163.  
  164.     it('should dequeue value', function(){
  165.  
  166.         var original = { name: 'value' };
  167.         queue.enqueue(original);
  168.         var item = queue.dequeue();
  169.  
  170.         expect(item).toEqual(original);
  171.  
  172.     });
  173.  
  174.     it('should throw when dequeue from empty', function(){
  175.  
  176.         var method = function(){
  177.             queue.dequeue();
  178.         };
  179.  
  180.         expect(method).toThrow(new Error('Queue is empty!'));
  181.     });
  182.  
  183.     it('should throw queue is full error', function(){
  184.  
  185.         for(var i = 0; i < queue.getCapacity(); i++){
  186.             expect(queue.getCount()).toEqual(i);
  187.             queue.enqueue(i);
  188.         }
  189.  
  190.         var method = function(){
  191.             queue.enqueue(10);
  192.         };
  193.  
  194.         expect(method).toThrow(new Error('Queue is full!'));
  195.  
  196.     });
  197.  
  198.     it('should enqueue to full and dequeue to empty', function(){
  199.  
  200.         for(var i = 0; i < queue.getCapacity(); i++){
  201.             expect(queue.getCount()).toEqual(i);
  202.             queue.enqueue(i);
  203.         }
  204.  
  205.         for(var j = queue.getCount(); j > 0; j--){
  206.             expect(queue.getCount()).toEqual(j);
  207.             queue.dequeue();
  208.         }
  209.  
  210.     });
  211.  
  212.     it('should enqueue and dequeue in loop', function(){
  213.  
  214.         for(var i = 0; i < 100; i++){
  215.             queue.enqueue(i);
  216.             var item = queue.dequeue();
  217.             expect(item).toEqual(i);
  218.         }
  219.  
  220.         expect(queue.getCount()).toEqual(0);
  221.  
  222.     });
  223.  
  224.     it('should peek an element', function(){
  225.  
  226.         var original = { name: 'value'};
  227.         queue.enqueue(original);
  228.         var copy = queue.peek();
  229.         expect(queue.getCount()).toEqual(1);
  230.         expect(copy).toEqual(original);
  231.  
  232.     });
  233.  
  234.     it('should throw an error on try to peek from empty queue', function(){
  235.  
  236.         var method = function(){
  237.             queue.peek();
  238.         };
  239.  
  240.         expect(method).toThrow(new Error("Queue is empty!"));
  241.  
  242.     });
  243.  
  244.     it('should peek first element', function(){
  245.  
  246.         var first = { name: 'first'};
  247.         var second = { name: 'second'};
  248.  
  249.         queue.enqueue(first);
  250.         queue.enqueue(second);
  251.         expect(queue.getCount()).toEqual(2);
  252.  
  253.         var copyOfFirst = queue.peek();
  254.         expect(copyOfFirst).toEqual(first);
  255.  
  256.     });
  257.  
  258.     it('should return last inserted element', function(){
  259.  
  260.         var original = { name: 'value'};
  261.         queue.enqueue(original);
  262.         var copy = queue.last();
  263.         expect(queue.getCount()).toEqual(1);
  264.         expect(copy).toEqual(original);
  265.  
  266.     });
  267.  
  268.     it('should throw an error on try to get last from empty queue', function(){
  269.  
  270.         var method = function(){
  271.             queue.last();
  272.         };
  273.  
  274.         expect(method).toThrow(new Error("Queue is empty!"));
  275.  
  276.     });
  277.  
  278.     it('should return last inserted element', function(){
  279.  
  280.         var first = { name: 'first'};
  281.         var second = { name: 'second'};
  282.  
  283.         queue.enqueue(first);
  284.         queue.enqueue(second);
  285.         expect(queue.getCount()).toEqual(2);
  286.  
  287.         var copyOfLast = queue.last();
  288.         expect(copyOfLast).toEqual(second);
  289.  
  290.     });
  291.  
  292. });
  293.  */