module SknUtils module Lists # Singly Linked List # Forward or #next navigation only # Head is absolute via #first # Tail when (next == nil) class LinkedList attr_accessor :size # &compare_key_proc supplies an method to identify # the key of an object for comparison purposes def initialize(*vargs, &compare_key_proc) @sort_condition = nil @current = nil @head = nil @tail = nil @size = 0 @match_value = block_given? ? compare_key_proc : lambda {|obj| obj } @sort_ascending = lambda {|a_obj,b_obj| @match_value.call(a_obj) >= @match_value.call(b_obj)} @sort_descending = lambda {|a_obj,b_obj| @match_value.call(a_obj) <= @match_value.call(b_obj)} @sort_condition = @sort_ascending vargs.each {|value| insert(value) } first if vargs.size > 1 end # # Navigation # # return values and position current to last node accessed def first @current = head if head @current.value rescue nil end def next @current = @current.next if @current and @current.next @current.value rescue nil end def current @current.value rescue nil end def last @current = tail if tail @current.value rescue nil end # -+ int position from current node def nth(index) node = @current while index > 1 and node and node.next node = node.next index -= 1 @current = node end # no reverse or prev for Single List current rescue NoMethodError nil end # return node at positive index from head def at_index(index) find_by_index(index) current end def empty? size == 0 end # # Modifications # # return new size def insert(value) temp = @current.value rescue nil insert_after(temp, value) end # return new size def prepend(value) temp = head.value rescue nil insert_before(temp, value) end # return new size def append(value) temp = tail.value rescue nil insert_after(temp, value) end # return new size def insert_before(position_value, value) prior, target = find_by_value(position_value) node = LinkNode.new(value, prior, :single, &@match_value) node.next = target if target self.head = node if head === target self.tail = node if tail.nil? @current = node self.size += 1 end # return new size def insert_after(position_value, value) prior, target = find_by_value(position_value) node = LinkNode.new(value, target, :single, &@match_value) self.head = node if head.nil? self.tail = node if tail === target @current = node self.size += 1 end # return remaining size def remove(value) @current, target_node = find_by_value(value) @current.next = target_node.remove! self.tail = @current.next if tail === target_node self.head = @current if head === target_node self.size -= 1 end # return number cleared def clear rc = 0 node = head position = head while node do node = node.remove! rc += 1 break if position === node end @current = nil self.head = nil self.tail = nil self.size = 0 rc end # # Enumerate # # perform each() or return enumerator def each(&block) @current = head position = head if block_given? while position do block.call(position.value.dup ) position = position.next end else Enumerator.new do |yielder, val| while position do yielder << position.value.dup position = position.next end end end end # convert self to a value array def to_a @current = head position = head result = [] while position do result << position.value.dup position = position.next break if position === @current end result end # block format: sort condition : {|a_obj,b_obj| a_obj >= b_obj} def sort!(direction_sym=:default, &compare_sort_proc) @active_sort_condition = block_given? ? compare_sort_proc : case direction_sym when :asc @sort_ascending when :desc @sort_descending else @sort_condition end sorted = merge_sort(to_a) clear sorted.each {|item| insert(item) } size end private attr_accessor :head, :tail def find_by_value(value) return [nil,nil] if head.nil? or value.nil? prior = head target = prior while target and not target.match_by_value(value) prior = target target = prior.next @current = target if target end [prior, target] end def find_by_index(index) return nil if head.nil? or index < 1 or index > size node = head node = node.next while ((index -= 1) > 0 and node.next) @current = node if node node end # Merged Sort via Ref: http://rubyalgorithms.com/merge_sort.html # arr is Array to be sorted, sort_cond is Proc expecting a/b params returning true/false def merge_sort(arr) return arr if arr.size < 2 middle = arr.size / 2 left = merge_sort(arr[0...middle]) right = merge_sort(arr[middle..arr.size]) merge(left, right) end def merge(left, right) sorted = [] while left.any? && right.any? if @active_sort_condition.call(left.first, right.first) sorted.push right.shift else sorted.push left.shift end end sorted + left + right end end # end class end # end module end # end module