Ruby References - Revision history

PeterHarding at 01:10, 18 March 2010

2010-03-18T01:10:23Z

← Older revision		Revision as of 11:10, 18 March 2010
Line 42:		Line 42:

	http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html		http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html

			<pre>
			# Priority queue with array based heap.
			#
			# This is distributed freely in the sence of
			# GPL(GNU General Public License).
			#
			# K.Kodama 2005/09/01. push_array, pop_array
			# Rick Bradley 2003/02/02. patch for Ruby 1.6.5. Thank you!
			# K.Kodama 2001/03/10. 1st version

			class PQueue

			attr_accessor :qarray # format: [nil, e1, e2, ..., en]
			attr_reader :size # number of elements
			attr_reader :gt # compareProc

			def initialize(compareProc=lambda{\|x,y\| x>y})
			# By default, retrieves maximal elements first.
			@qarray=[nil]; @size=0; @gt=compareProc; make_legal
			end
			private :initialize

			def upheap(k)
			k2=k.div(2); v=@qarray[k];
			while ((k2>0)and(@gt[v,@qarray[k2]]));
			@qarray[k]=@qarray[k2]; k=k2; k2=k2.div(2)
			end;
			@qarray[k]=v;
			end
			private :upheap

			def downheap(k)
			v=@qarray[k]; q2=@size.div(2)
			loop{
			if (k>q2); break; end;
			j=k+k; if ((j<@size)and(@gt[@qarray[j+1],@qarray[j]])); j=j+1; end;
			if @gt[v,@qarray[j]]; break; end;
			@qarray[k]=@qarray[j]; k=j;
			}
			@qarray[k]=v;
			end;
			private :downheap

			def make_legal
			for k in 2..@size do; upheap(k); end;
			end;

			def empty?
			return (0==@size)
			end

			def clear
			@qarray.replace([nil]); @size=0;
			end;

			def replace_array(arr=[])
			# Use push_array.
			@qarray.replace([nil]+arr); @size=arr.size; make_legal
			end;

			def clone
			q=new; q.qarray=@qarray.clone; q.size=@size; q.gt=@gt; return q;
			end;

			def push(v)
			@size=@size+1; @qarray[@size]=v; upheap(@size);
			end;

			def push_array(arr=[])
			@qarray[@size+1,arr.size]=arr; arr.size.times{@size+=1; upheap(@size)}
			end;

			def pop
			# return top element. nil if queue is empty.
			if @size>0;
			res=@qarray[1]; @qarray[1]=@qarray[@size]; @size=@size-1;
			downheap(1);
			return res;
			else return nil
			end;
			end;

			def pop_array(n=@size)
			# return top n-element as an sorted array. (i.e. The obtaining array is decreasing order.)
			# See also to_a.
			a=[]
			n.times{a.push(pop)}
			return a
			end;

			def to_a
			# array sorted as increasing order.
			# See also pop_array.
			res=@qarray[1..@size];
			res.sort!{\|x,y\| if @gt[x,y]; 1;elsif @gt[y,x]; -1; else 0; end;}
			return res
			end

			def top
			# top element. not destructive.
			if @size>0; return @qarray[1]; else return nil; end;
			end;

			def replace_top_low(v)
			# replace top element if v<top element.
			if @size>0; @qarray[0]=v; downheap(0); return @qarray[0];
			else @qarray[1]=v; return nil;
			end;
			end;

			def replace_top(v)
			# replace top element
			if @size>0; res=@qarray[1]; @qarray[1]=v; downheap(1); return res;
			else @qarray[1]=v; return nil;
			end;
			end;

			def each_pop
			# iterate pop. destructive. Use as self.each_pop{\|x\| ... }.
			while(@size>0); yield self.pop; end;
			end;

			def each_with_index
			# Not ordered. Use as self.each_with_index{\|e,i\| ... }.
			for i in 1..@size do; yield @qarray[i],i; end;
			end

			end # class pqueue

			if $0 == __FILE__
			pq=PQueue.new(proc{\|x,y\| x>y})
			pq.push(2)
			pq.push(3)
			pq.push(4)
			pq.push(3)
			pq.push(2)
			pq.push(4)
			pq.push_array([3,5,4])
			print "size: "+pq.size.to_s+"\n"
			print "heap: "; pq.each_with_index{\|x,y\| print x.to_s+" "}; print "\n"
			print "to_a: "+pq.to_a.to_s+"\n"

			# a=pq.pop_array; p a.to_s
			print "pop : ";pq.each_pop{\|x\| print x.to_s+" "}; print "\n"
			end;
			</pre>

	=Ruby Archives=		=Ruby Archives=

PeterHarding at 01:04, 18 March 2010

2010-03-18T01:04:07Z

← Older revision		Revision as of 11:04, 18 March 2010
Line 43:		Line 43:
	http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html		http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html

			=Ruby Archives=

			* http://raa.ruby-lang.org/


	[[Category:Ruby]]		[[Category:Ruby]]

PeterHarding at 01:03, 18 March 2010

2010-03-18T01:03:11Z

← Older revision		Revision as of 11:03, 18 March 2010
Line 1:		Line 1:
	* http://www.zytrax.com/tech/lang/ruby/		* http://www.zytrax.com/tech/lang/ruby/
	\
	=Dijkstra’s Algorithm in Ruby=		=Dijkstra’s Algorithm in Ruby=

PeterHarding at 01:03, 18 March 2010

2010-03-18T01:03:00Z

← Older revision		Revision as of 11:03, 18 March 2010
Line 1:		Line 1:
			* http://www.zytrax.com/tech/lang/ruby/
			\
			=Dijkstra’s Algorithm in Ruby=

			http://blog.linkedin.com/2008/09/19/implementing-di/

			<pre>
			require 'pqueue'

			class Algorithm
			INFINITY = 1 << 32

			def self.dijkstra(source, edges, weights, n)
			visited = Array.new(n, false)
			shortest_distances = Array.new(n, INFINITY)
			previous = Array.new(n, nil)
			pq = PQueue.new(proc {\|x,y\| shortest_distances[x] < shortest_distances[y]})

			pq.push(source)
			visited = true
			shortest_distances = 0

			while pq.size != 0
			v = pq.pop
			visited[v] = true
			if edges[v]
			edges[v].each do \|w\|
			if !visited[w] and shortest_distances[w] > shortest_distances[v] + weights[v][w]
			shortest_distances[w] = shortest_distances[v] + weights[v][w]
			previous[w] = v
			pq.push(w)
			end
			end
			end
			end
			return [shortest_distances, previous]
			end
			end
			</pre>

			=pqueue=

			http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html


	* http://www.zytrax.com/tech/lang/ruby/

	[[Category:Ruby]]		[[Category:Ruby]]

PeterHarding: Created page with ' * http://www.zytrax.com/tech/lang/ruby/ Category:Ruby'

2010-03-18T00:58:51Z

Created page with ' * http://www.zytrax.com/tech/lang/ruby/ Category:Ruby'

New page

* http://www.zytrax.com/tech/lang/ruby/

[[Category:Ruby]]