#690

Committed 20 May 2014 10:46AM UTC coverage: 92.28% (-5.1%) from 97.353%

Build # #690

Build Type

push

Committed by

Commit Message

Merge pull request #87 from jdantonio/removed-actor-context-spike

Removed ActorContext spike.

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

128 existing lines in 11 files now uncovered.

2283 of 2474 relevant lines covered (92.28%)

618.76 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

65.42

/lib/concurrent/collection/priority_queue.rb

module Concurrent

  # @!macro [attach] priority_queue
  #
  #   A queue collection in which the elements are sorted based on their
  #   comparison (spaceship) operator `<=>`. Items are added to the queue
  #   at a position relative to their priority. On removal the element
  #   with the "highest" priority is removed. By default the sort order is
  #   from highest to lowest, but a lowest-to-highest sort order can be
  #   set on construction.
  #
  #   The API is based on the `Queue` class from the Ruby standard library.
  #
  #   The pure Ruby implementation, `MutexPriorityQueue` uses a heap algorithm
  #   stored in an array. The algorithm is based on the work of Robert Sedgewick
  #   and Kevin Wayne.
  #
  #   The JRuby native implementation is a thin wrapper around the standard
  #   library `java.util.PriorityQueue`.
  #
  #   When running under JRuby the class `PriorityQueue` extends `JavaPriorityQueue`.
  #   When running under all other interpreters it extends `MutexPriorityQueue`.
  #
  #   @note This implementation is *not* thread safe and performs no blocking.
  #
  #   @see http://en.wikipedia.org/wiki/Priority_queue
  #   @see http://ruby-doc.org/stdlib-2.0.0/libdoc/thread/rdoc/Queue.html
  #
  #   @see http://algs4.cs.princeton.edu/24pq/index.php#2.6
  #   @see http://algs4.cs.princeton.edu/24pq/MaxPQ.java.html
  #
  #   @see http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
  class MutexPriorityQueue

    # @!macro [attach] priority_queue_method_initialize
    #
    #   Create a new priority queue with no items.
    #  
    #   @param [Hash] opts the options for creating the queue
    #   @option opts [Symbol] :order (:max) dictates the order in which items are
    #     stored: from highest to lowest when `:max` or `:high`; from lowest to
    #     highest when `:min` or `:low`
    def initialize(opts = {})
      order = opts.fetch(:order, :max)
      @comparator = [:min, :low].include?(order) ? -1 : 1
      clear
    end

    # @!macro [attach] priority_queue_method_clear
    #
    #   Removes all of the elements from this priority queue.
    def clear
      @queue = [nil]
      @length = 0
      true
    end

    # @!macro [attach] priority_queue_method_delete
    #
    #   Deletes all items from `self` that are equal to `item`.
    #  
    #   @param [Object] item the item to be removed from the queue
    #   @return [Object] true if the item is found else false
    def delete(item)
      original_length = @length
      k = 1
      while k <= @length
        if @queue[k] == item
          swap(k, @length)
          @length -= 1
          sink(k)
          @queue.pop
        else
          k += 1
        end
      end
      @length != original_length
    end

    # @!macro [attach] priority_queue_method_empty
    #  
    #   Returns `true` if `self` contains no elements.
    #  
    #   @return [Boolean] true if there are no items in the queue else false
    def empty?
      size == 0
    end

    # @!macro [attach] priority_queue_method_include
    #
    #   Returns `true` if the given item is present in `self` (that is, if any
    #   element == `item`), otherwise returns false.
    #  
    #   @param [Object] item the item to search for
    #  
    #   @return [Boolean] true if the item is found else false
    def include?(item)
      @queue.include?(item)
    end
    alias_method :has_priority?, :include?

    # @!macro [attach] priority_queue_method_length
    #  
    #   The current length of the queue.
    #  
    #   @return [Fixnum] the number of items in the queue
    def length
      @length
    end
    alias_method :size, :length

    # @!macro [attach] priority_queue_method_peek
    #  
    #   Retrieves, but does not remove, the head of this queue, or returns `nil`
    #   if this queue is empty.
    #   
    #   @return [Object] the head of the queue or `nil` when empty
    def peek
      @queue[1]
    end

    # @!macro [attach] priority_queue_method_pop
    #  
    #   Retrieves and removes the head of this queue, or returns `nil` if this
    #   queue is empty.
    #   
    #   @return [Object] the head of the queue or `nil` when empty
    def pop
      max = @queue[1]
      swap(1, @length)
      @length -= 1
      sink(1)
      @queue.pop
      max
    end
    alias_method :deq, :pop
    alias_method :shift, :pop

    # @!macro [attach] priority_queue_method_push
    #  
    #   Inserts the specified element into this priority queue.
    #  
    #   @param [Object] item the item to insert onto the queue
    def push(item)
      @length += 1
      @queue << item
      swim(@length)
      true
    end
    alias_method :<<, :push
    alias_method :enq, :push

    # @!macro [attach] priority_queue_method_from_list
    #  
    #   Create a new priority queue from the given list.
    #  
    #   @param [Enumerable] list the list to build the queue from
    #   @param [Hash] opts the options for creating the queue
    #  
    #   @return [PriorityQueue] the newly created and populated queue
    def self.from_list(list, opts = {})
      queue = new(opts)
      list.each{|item| queue << item }
      queue
    end

    protected

    # Exchange the values at the given indexes within the internal array.
    # 
    # @param [Integer] x the first index to swap
    # @param [Integer] y the second index to swap
    # 
    # @!visibility private
    def swap(x, y)
      temp = @queue[x]
      @queue[x] = @queue[y]
      @queue[y] = temp
    end

    # Are the items at the given indexes ordered based on the priority
    # order specified at construction?
    #
    # @param [Integer] x the first index from which to retrieve a comparable value
    # @param [Integer] y the second index from which to retrieve a comparable value
    #
    # @return [Boolean] true if the two elements are in the correct priority order
    #   else false
    # 
    # @!visibility private
    def ordered?(x, y)
      (@queue[x] <=> @queue[y]) == @comparator
    end

    # Percolate down to maintain heap invariant.
    # 
    # @param [Integer] k the index at which to start the percolation
    # 
    # @!visibility private
    def sink(k)
      while (j = (2 * k)) <= @length do
        j += 1 if j < @length && ! ordered?(j, j+1)
        break if ordered?(k, j)
        swap(k, j)
        k = j
      end
    end

    # Percolate up to maintain heap invariant.
    # 
    # @param [Integer] k the index at which to start the percolation
    # 
    # @!visibility private
    def swim(k)
      while k > 1 && ! ordered?(k/2, k) do
        swap(k, k/2)
        k = k/2
      end
    end
  end

  if RUBY_PLATFORM == 'java'

    # @!macro priority_queue
    class JavaPriorityQueue

      # @!macro priority_queue_method_initialize
      def initialize(opts = {})
        order = opts.fetch(:order, :max)
        if [:min, :low].include?(order)
          @queue = java.util.PriorityQueue.new(11) # 11 is the default initial capacity
        else
          @queue = java.util.PriorityQueue.new(11, java.util.Collections.reverseOrder())
        end
      end

      # @!macro priority_queue_method_clear
      def clear
        @queue.clear
        true
      end

      # @!macro priority_queue_method_delete
      def delete(item)
        found = false
        while @queue.remove(item) do
          found = true
        end
        found
      end

      # @!macro priority_queue_method_empty
      def empty?
        @queue.size == 0
      end

      # @!macro priority_queue_method_include
      def include?(item)
        @queue.contains(item)
      end
      alias_method :has_priority?, :include?

      # @!macro priority_queue_method_length
      def length
        @queue.size
      end
      alias_method :size, :length

      # @!macro priority_queue_method_peek
      def peek
        @queue.peek
      end

      # @!macro priority_queue_method_pop
      def pop
        @queue.poll
      end
      alias_method :deq, :pop
      alias_method :shift, :pop

      # @!macro priority_queue_method_push
      def push(item)
        @queue.add(item)
      end
      alias_method :<<, :push
      alias_method :enq, :push

      # @!macro priority_queue_method_from_list
      def self.from_list(list, opts = {})
        queue = new(opts)
        list.each{|item| queue << item }
        queue
      end
    end

    # @!macro priority_queue
    class PriorityQueue < JavaPriorityQueue
    end
  else

    # @!macro priority_queue
    class PriorityQueue < MutexPriorityQueue
    end
  end
end

1	module Concurrent	1✔
2
3	# @!macro [attach] priority_queue
4	#
5	# A queue collection in which the elements are sorted based on their
6	# comparison (spaceship) operator `<=>`. Items are added to the queue
7	# at a position relative to their priority. On removal the element
8	# with the "highest" priority is removed. By default the sort order is
9	# from highest to lowest, but a lowest-to-highest sort order can be
10	# set on construction.
11	#
12	# The API is based on the `Queue` class from the Ruby standard library.
13	#
14	# The pure Ruby implementation, `MutexPriorityQueue` uses a heap algorithm
15	# stored in an array. The algorithm is based on the work of Robert Sedgewick
16	# and Kevin Wayne.
17	#
18	# The JRuby native implementation is a thin wrapper around the standard
19	# library `java.util.PriorityQueue`.
20	#
21	# When running under JRuby the class `PriorityQueue` extends `JavaPriorityQueue`.
22	# When running under all other interpreters it extends `MutexPriorityQueue`.
23	#
24	# @note This implementation is not thread safe and performs no blocking.
25	#
26	# @see http://en.wikipedia.org/wiki/Priority_queue
27	# @see http://ruby-doc.org/stdlib-2.0.0/libdoc/thread/rdoc/Queue.html
28	#
29	# @see http://algs4.cs.princeton.edu/24pq/index.php#2.6
30	# @see http://algs4.cs.princeton.edu/24pq/MaxPQ.java.html
31	#
32	# @see http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
33	class MutexPriorityQueue	1✔
34
35	# @!macro [attach] priority_queue_method_initialize
36	#
37	# Create a new priority queue with no items.
38	#
39	# @param [Hash] opts the options for creating the queue
40	# @option opts [Symbol] :order (:max) dictates the order in which items are
41	# stored: from highest to lowest when `:max` or `:high`; from lowest to
42	# highest when `:min` or `:low`
43	def initialize(opts = {})	1✔
44	order = opts.fetch(:order, :max)	158✔
45	@comparator = [:min, :low].include?(order) ? -1 : 1	158✔
46	clear	158✔
47	end
48
49	# @!macro [attach] priority_queue_method_clear
50	#
51	# Removes all of the elements from this priority queue.
52	def clear	1✔
53	@queue = [nil]	186✔
54	@length = 0	186✔
55	true	186✔
56	end
57
58	# @!macro [attach] priority_queue_method_delete
59	#
60	# Deletes all items from `self` that are equal to `item`.
61	#
62	# @param [Object] item the item to be removed from the queue
63	# @return [Object] true if the item is found else false
64	def delete(item)	1✔
65	original_length = @length	7✔
66	k = 1	7✔
67	while k <= @length	7✔
68	if @queue[k] == item	57✔
69	swap(k, @length)	9✔
70	@length -= 1	9✔
71	sink(k)	9✔
72	@queue.pop	9✔
73	else
74	k += 1	48✔
75	end
76	end
77	@length != original_length	7✔
78	end
79
80	# @!macro [attach] priority_queue_method_empty
81	#
82	# Returns `true` if `self` contains no elements.
83	#
84	# @return [Boolean] true if there are no items in the queue else false
85	def empty?	1✔
86	size == 0	264✔
87	end
88
89	# @!macro [attach] priority_queue_method_include
90	#
91	# Returns `true` if the given item is present in `self` (that is, if any
92	# element == `item`), otherwise returns false.
93	#
94	# @param [Object] item the item to search for
95	#
96	# @return [Boolean] true if the item is found else false
97	def include?(item)	1✔
98	@queue.include?(item)	9✔
99	end
100	alias_method :has_priority?, :include?	1✔
101
102	# @!macro [attach] priority_queue_method_length
103	#
104	# The current length of the queue.
105	#
106	# @return [Fixnum] the number of items in the queue
107	def length	1✔
108	@length	272✔
109	end
110	alias_method :size, :length	1✔
111
112	# @!macro [attach] priority_queue_method_peek
113	#
114	# Retrieves, but does not remove, the head of this queue, or returns `nil`
115	# if this queue is empty.
116	#
117	# @return [Object] the head of the queue or `nil` when empty
118	def peek	1✔
119	@queue[1]	192✔
120	end
121
122	# @!macro [attach] priority_queue_method_pop
123	#
124	# Retrieves and removes the head of this queue, or returns `nil` if this
125	# queue is empty.
126	#
127	# @return [Object] the head of the queue or `nil` when empty
128	def pop	1✔
129	max = @queue[1]	143✔
130	swap(1, @length)	143✔
131	@length -= 1	143✔
132	sink(1)	143✔
133	@queue.pop	143✔
134	max	143✔
135	end
136	alias_method :deq, :pop	1✔
137	alias_method :shift, :pop	1✔
138
139	# @!macro [attach] priority_queue_method_push
140	#
141	# Inserts the specified element into this priority queue.
142	#
143	# @param [Object] item the item to insert onto the queue
144	def push(item)	1✔
145	@length += 1	440✔
146	@queue << item	440✔
147	swim(@length)	440✔
148	true	440✔
149	end
150	alias_method :<<, :push	1✔
151	alias_method :enq, :push	1✔
152
153	# @!macro [attach] priority_queue_method_from_list
154	#
155	# Create a new priority queue from the given list.
156	#
157	# @param [Enumerable] list the list to build the queue from
158	# @param [Hash] opts the options for creating the queue
159	#
160	# @return [PriorityQueue] the newly created and populated queue
161	def self.from_list(list, opts = {})	1✔
162	queue = new(opts)	6✔
163	list.each{\|item\| queue << item }	34✔
164	queue	6✔
165	end
166
167	protected	1✔
168
169	# Exchange the values at the given indexes within the internal array.
170	#
171	# @param [Integer] x the first index to swap
172	# @param [Integer] y the second index to swap
173	#
174	# @!visibility private
175	def swap(x, y)	1✔
176	temp = @queue[x]	648✔
177	@queue[x] = @queue[y]	648✔
178	@queue[y] = temp	648✔
179	end
180
181	# Are the items at the given indexes ordered based on the priority
182	# order specified at construction?
183	#
184	# @param [Integer] x the first index from which to retrieve a comparable value
185	# @param [Integer] y the second index from which to retrieve a comparable value
186	#
187	# @return [Boolean] true if the two elements are in the correct priority order
188	# else false
189	#
190	# @!visibility private
191	def ordered?(x, y)	1✔
192	(@queue[x] <=> @queue[y]) == @comparator	654✔
193	end
194
195	# Percolate down to maintain heap invariant.
196	#
197	# @param [Integer] k the index at which to start the percolation
198	#
199	# @!visibility private
200	def sink(k)	1✔
201	while (j = (2 * k)) <= @length do	378✔
202	j += 1 if j < @length && ! ordered?(j, j+1)	88✔
203	break if ordered?(k, j)	88✔
204	swap(k, j)	74✔
205	k = j	74✔
206	end
207	end
208
209	# Percolate up to maintain heap invariant.
210	#
211	# @param [Integer] k the index at which to start the percolation
212	#
213	# @!visibility private
214	def swim(k)	1✔
215	while k > 1 && ! ordered?(k/2, k) do	440✔
216	swap(k, k/2)	422✔
217	k = k/2	422✔
218	end
219	end
220	end
221
222	if RUBY_PLATFORM == 'java'	1✔
223
224	# @!macro priority_queue
UNCOV 225	class JavaPriorityQueue	×
226
227	# @!macro priority_queue_method_initialize
UNCOV 228	def initialize(opts = {})	×
UNCOV 229	order = opts.fetch(:order, :max)	×
UNCOV 230	if [:min, :low].include?(order)	×
UNCOV 231	@queue = java.util.PriorityQueue.new(11) # 11 is the default initial capacity	×
232	else
UNCOV 233	@queue = java.util.PriorityQueue.new(11, java.util.Collections.reverseOrder())	×
234	end
235	end
236
237	# @!macro priority_queue_method_clear
UNCOV 238	def clear	×
UNCOV 239	@queue.clear	×
UNCOV 240	true	×
241	end
242
243	# @!macro priority_queue_method_delete
UNCOV 244	def delete(item)	×
UNCOV 245	found = false	×
UNCOV 246	while @queue.remove(item) do	×
UNCOV 247	found = true	×
248	end
UNCOV 249	found	×
250	end
251
252	# @!macro priority_queue_method_empty
UNCOV 253	def empty?	×
UNCOV 254	@queue.size == 0	×
255	end
256
257	# @!macro priority_queue_method_include
UNCOV 258	def include?(item)	×
UNCOV 259	@queue.contains(item)	×
260	end
UNCOV 261	alias_method :has_priority?, :include?	×
262
263	# @!macro priority_queue_method_length
UNCOV 264	def length	×
UNCOV 265	@queue.size	×
266	end
UNCOV 267	alias_method :size, :length	×
268
269	# @!macro priority_queue_method_peek
UNCOV 270	def peek	×
UNCOV 271	@queue.peek	×
272	end
273
274	# @!macro priority_queue_method_pop
UNCOV 275	def pop	×
UNCOV 276	@queue.poll	×
277	end
UNCOV 278	alias_method :deq, :pop	×
UNCOV 279	alias_method :shift, :pop	×
280
281	# @!macro priority_queue_method_push
UNCOV 282	def push(item)	×
UNCOV 283	@queue.add(item)	×
284	end
UNCOV 285	alias_method :<<, :push	×
UNCOV 286	alias_method :enq, :push	×
287
288	# @!macro priority_queue_method_from_list
UNCOV 289	def self.from_list(list, opts = {})	×
UNCOV 290	queue = new(opts)	×
UNCOV 291	list.each{\|item\| queue << item }	×
UNCOV 292	queue	×
293	end
294	end
295
296	# @!macro priority_queue
UNCOV 297	class PriorityQueue < JavaPriorityQueue	×
298	end
299	else
300
301	# @!macro priority_queue
302	class PriorityQueue < MutexPriorityQueue	1✔
303	end
304	end
305	end

jdantonio / concurrent-ruby / #690

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous