Parent

Files

SparseArray

SparseArray

SparseArray is an implemenation of the Array class using only Hashes. Regular Arrays are never used except once to delegate the pack method, (and *args parameters of course). SparseArray is almost fully compatible with Array. There are still a few missing methods that came in with Ruby 1.9 that need to be added, and negative indexes are not quite fully supported yet.

Benchmarks comparing Ruby 1.6 circa 2004 compared to Ruby 1.8.7 circa 2010, show that Ruby's Array implementation has improved quite a bit. Where as Array was about 2-4 times faster than SparseArray in 2004, it is now over 10x faster, and able to handle large sparse arrays quite easily. Though surely SparseArray could still be improved, SparseArray is little more than an interesting novelty at this point, as opposed to a useful class, but we will keep her nonetheless for simple interests sake.

NOTE: SparseArray is also the first piece of code I used TDD to create.

Copyright (c) 2004 Thomas Sawyer

Public Class Methods

[](*args) click to toggle source
# File lib/hashery/sparsearray.rb, line 29
def self.[](*args)
  s = new
  args.each{ |e| s << e }
  s
end
new(i=0,e=nil) click to toggle source
# File lib/hashery/sparsearray.rb, line 41
def initialize(i=0,e=nil)
  if i > 0
    i.times { set(self.length,e) }
  end
end
new_h(hsh) click to toggle source
# File lib/hashery/sparsearray.rb, line 35
def self.new_h(hsh)
  nha = new
  nha.replace(hsh)
  #nha.reindex!
end

Public Instance Methods

&(ha) click to toggle source
# File lib/hashery/sparsearray.rb, line 47
def &(ha)
  nha = self.class.new
  (0..self.length-1).each do |i|
    if ha.has_value?(self.fetch(i)) and !nha.has_value?(self.fetch(i))
      nha.set(nha.length,self.fetch(i))
    end
  end
  nha
end
*(j) click to toggle source
# File lib/hashery/sparsearray.rb, line 57
def *(j)
  if j.kind_of?(String)
    return self.join(j)
  else
    nha = self.class.new
    j.times { (0...self.length).each { |i| nha.set(nha.length,self.fetch(i)) } }
    return nha
  end
end
+(ha) click to toggle source
# File lib/hashery/sparsearray.rb, line 67
def +(ha)
  nha = self.dup
  (0..ha.length-1).each { |i| nha.set(nha.length,ha.fetch(i)) }
  nha
end
-(ha) click to toggle source
# File lib/hashery/sparsearray.rb, line 73
def -(ha)
  nha = self.class.new
  self.each { |v| nha << v if !ha.has_value?(v) }
  #ha.each { |v| nha << i if !self.include?(v) }
  nha
end
<<(e) click to toggle source
# File lib/hashery/sparsearray.rb, line 80
def <<(e)
  set(length,e)
  self
end
<=>(ha) click to toggle source
# File lib/hashery/sparsearray.rb, line 85
def <=>(ha)
  (0..self.length-1).each do |i|
    ieq = (self.fetch(i) <=> ha.fetch(i))
    return ieq if ieq != 0
  end
  self.length <=> ha.length
end
===(ha) click to toggle source
# File lib/hashery/sparsearray.rb, line 93
def ===(ha)
  self.==(ha)
end
[](i,l=nil) click to toggle source

TODO: Ranges with negative indexes not yet supported.

# File lib/hashery/sparsearray.rb, line 101
def [](i,l=nil)
  if l
    i = size + i if i < 0
    i = i...i+l
  elsif ! i.kind_of?(Range)
    return self.at(i)
  end
  nha = self.class.new
  i.each { |j| nha.set(nha.length,get(j)) if has_key?(j) }
  nha
end
Also aliased as: get
[]=(i,b,c=nil) click to toggle source
# File lib/hashery/sparsearray.rb, line 116
def []=(i,b,c=nil)
  if c
    rng = (Integer(i)..Integer(i+b))
    b = c
  elsif i.kind_of? Range
    rng = i
  else
    self.set(Integer(i),b)
    return b
  end
  if b == nil
    rng.each { |i| qdelete(i) }
    self.reindex!
  elsif b.kind_of?(Array) or b.kind_of?(self.class)
    j = 0
    rng.each { |i| self[i] = b[j]; j+=1 }
  else
    rng.each { |i| qdelete(i) }
    self[rng.fist] = b
    self.reindex!
  end
end
Also aliased as: set
assoc(k) click to toggle source
# File lib/hashery/sparsearray.rb, line 145
def assoc(k)
  (0...self.length).each { |i| return self.fetch(i) if self.fetch(i)[0] == k }
  return nil
end
at(i) click to toggle source
# File lib/hashery/sparsearray.rb, line 150
def at(i)
  i = self.length + i if i <= -1
  get(i)
  #return nil if i < 0 or i >= self.length
  #return self.fetch(i)
end
collect() click to toggle source
# File lib/hashery/sparsearray.rb, line 163
def collect
  nha = self.class.new
  (0...self.length).each { |i| nha << yield(self.fetch(i)) }
  nha
end
collect!() click to toggle source
# File lib/hashery/sparsearray.rb, line 169
def collect!
  nha = self.class.new
  (0...self.length).each { |i| nha << yield(self.fetch(i)) }
  self.replace(nha)
end
Also aliased as: map!
compact() click to toggle source
# File lib/hashery/sparsearray.rb, line 179
def compact
  nha, j = self.class.new, 0
  (0..self.length-1).each do |i|
    if self.fetch(i) != nil
      nha.set(j,self.fetch(i))
      j+=1
    end
  end
  nha
end
compact!() click to toggle source
# File lib/hashery/sparsearray.rb, line 190
def compact!
  if self.has_value?(nil)
    nha, j = self.class.new, 0
    (0..self.length-1).each do |i|
      if self.fetch(i) != nil
        nha.set(j,self.fetch(i))
        j+=1
      end
    end
    return self.replace(nha)
  else
    return nil
  end
end
concat(ha) click to toggle source
# File lib/hashery/sparsearray.rb, line 206
def concat(ha)
  (0...ha.length).each { |i| self.set(self.length,ha.fetch(i)) }
  self
end
count(e=nil) click to toggle source
# File lib/hashery/sparsearray.rb, line 211
def count(e=nil)
  if block_given?
    cnt = 0
    (0...self.length).each { |i| cnt += 1 if yield(self.fetch(i)) }
    return cnt
  else
    cnt = 0
    (0...self.length).each { |i| cnt += 1 if self.fetch(i) == e }
    return cnt
  end
end
delete(e) click to toggle source
# File lib/hashery/sparsearray.rb, line 228
def delete(e)
  if has_value?(e)
    qdelete_if { |i,v| v == e }
    reindex!
    return e
  else
    return yield if block_given?
    return nil
  end
end
Also aliased as: qdelete
delete_at(i) click to toggle source
# File lib/hashery/sparsearray.rb, line 240
def delete_at(i)
  if self.has_key?(i)
    e = self.fetch(i)
    qdelete(i)
    reindex!
    return e
  else
    return nil
  end
end
delete_if() click to toggle source
# File lib/hashery/sparsearray.rb, line 255
def delete_if
  qdelete_if { |i,v| yield(v) }
  reindex!
end
Also aliased as: qdelete_if
each() click to toggle source
# File lib/hashery/sparsearray.rb, line 260
def each
  (0...self.length).each{ |i| yield(get(i)) }
end
each_index() click to toggle source
# File lib/hashery/sparsearray.rb, line 264
def each_index
  (0...self.length).each{ |i| yield(i) }
end
eql?(ha) click to toggle source

empty? okay as is

# File lib/hashery/sparsearray.rb, line 270
def eql?(ha)
  return false if self.length != ha.length
  return true if (0...self.length).all? { |i| self.fetch(i).eql?(ha.fetch(i)) }
  return false
end
fill(f,s=nil,l=nil) click to toggle source
# File lib/hashery/sparsearray.rb, line 276
def fill(f,s=nil,l=nil)
  if s.kind_of?(Range)
    r = s
  else
    s = 0 if !s
    l = self.length - s if !l
    r = s...(s+l)
  end
  r.each{ |i| self.set(i,f) }
  self
end
first() click to toggle source
# File lib/hashery/sparsearray.rb, line 288
def first
  return nil if self.empty?
  self.fetch(0)
end
flatten() click to toggle source
# File lib/hashery/sparsearray.rb, line 293
def flatten
  nha = self.class.new
  (0...self.length).each do |i|
    sfi = self.fetch(i)
    if sfi.kind_of?(self.class) or sfi.kind_of?(Array)
      nha.concat(sfi.flatten)
    else
      nha.set(nha.length,sfi)
    end
  end
  nha
end
flatten!() click to toggle source
# File lib/hashery/sparsearray.rb, line 306
def flatten!
  return nil if !self.any? { |e| e.kind_of?(self.class) or e.kind_of?(Array) }
  self.replace(self.flatten)
end
get(i,l=nil) click to toggle source
Alias for: []
include?(v) click to toggle source
# File lib/hashery/sparsearray.rb, line 311
def include?(v)
  self.has_value?(v)
end
insert(index, *objs) click to toggle source
# File lib/hashery/sparsearray.rb, line 316
def insert(index, *objs)
  index = size + index + 1 if index < 0
  tail = self[index...size]
  objs.each_with_index do |obj, i|
    set(index + i, obj)
  end
  tail.each_with_index do |obj, i|
    set(objs.size + index + i, obj)
  end
  self
end
join(sep='') click to toggle source
# File lib/hashery/sparsearray.rb, line 331
def join(sep='')
  s = ''
  (0...self.length).each { |i| s << "#{self.fetch(i)}#{sep}" }
  return s.chomp(sep)
end
last() click to toggle source
# File lib/hashery/sparsearray.rb, line 338
def last
  self[self.length-1]
end
map!() click to toggle source
Alias for: collect!
nitems() click to toggle source
# File lib/hashery/sparsearray.rb, line 348
def nitems
  cnt = 0
  (0...self.length).each { |i| cnt += 1 if self.fetch(i) != nil }
  cnt
end
pack(*args) click to toggle source
# File lib/hashery/sparsearray.rb, line 354
def pack(*args)
  self.to_a.pack(*args)
end
pop() click to toggle source
# File lib/hashery/sparsearray.rb, line 362
def pop
  self.delete_at(self.length-1)
end
push(*e) click to toggle source
# File lib/hashery/sparsearray.rb, line 370
def push(*e)
  self.concat(e)
end
qdelete(e) click to toggle source
Alias for: delete
qdelete_if() click to toggle source
Alias for: delete_if
qsort(ha, l, r) click to toggle source
# File lib/hashery/sparsearray.rb, line 484
def qsort(ha, l, r)
  l_hold = l
  r_hold = r
  pivot = ha[l]
  while l < r
    r -= 1 while (ha[r] <=> pivot) >= 0 and l < r
    if l != r
      ha[l] = ha[r]
      l += 1
    end
    l += 1 while (ha[l] <=> pivot) <= 0 and l < r
    if l != r
      ha[r] = ha[l]
      r -= 1
    end
  end
  ha[l] = pivot
  pivot = l
  l = l_hold
  r = r_hold
  qsort(ha,l,pivot-1) if l < pivot
  qsort(ha,pivot+1,r) if r > pivot
  ha
end
rassoc(k) click to toggle source
# File lib/hashery/sparsearray.rb, line 374
def rassoc(k)
  (0...self.length).each { |i| return self.fetch(i) if self.fetch(i)[1] == k }
  return nil
end
reindex() click to toggle source
# File lib/hashery/sparsearray.rb, line 379
def reindex
  nha, j, k, tl = self.class.new, 0, 0, self.length
  while k < tl
    if self.has_key?(j)
      nha.set(k,self.fetch(j))
      j+=1; k+=1
    else
      j+=1
    end
  end
  nha
end
reindex!() click to toggle source
# File lib/hashery/sparsearray.rb, line 392
def reindex!
  self.replace(self.reindex)
end
reject!() click to toggle source
# File lib/hashery/sparsearray.rb, line 396
def reject!
  chg=nil
  qdelete_if { |i,v| r=yield(v); chg=true if r; r }
  return nil if !chg
  reindex!
end
reverse() click to toggle source

def replace(ha)

if ha.length < self.length
  (ha.length..self.length-1).each { |i| self.delete(i) }
  (0..ha.length-1).each { |i| self.set(i,ha[i]) }
end

end

# File lib/hashery/sparsearray.rb, line 410
def reverse
  nha = self.class.new
  (0...self.length).each { |i| nha.set(self.length-1-i,self.fetch(i)) }
  nha
end
reverse!() click to toggle source
# File lib/hashery/sparsearray.rb, line 416
def reverse!
  (0...self.length/2).each do |i|
    ri = self.length-1-i
    tmp = self.fetch(ri)
    self.set(ri,self.fetch(i))
    self.set(i,tmp)
  end
  self
end
reverse_each() click to toggle source
# File lib/hashery/sparsearray.rb, line 426
def reverse_each
  i = self.length - 1
  while i >= 0
    yield(self.fetch(i))
    i -= 1
  end
end
rindex(e) click to toggle source
# File lib/hashery/sparsearray.rb, line 434
def rindex(e)
  i = self.length - 1
  while i >= 0
    return i if self.fetch(i) == e
    i -= 1
  end
  return nil
end
set(i,b,c=nil) click to toggle source
Alias for: []=
shift() click to toggle source
# File lib/hashery/sparsearray.rb, line 443
def shift
  e1 = self[0]
  tl = self.length - 1
  (1..tl).each { |i| self.set(i-1,self.fetch(i)) }
  self.delete_at(tl)
  e1
end
shuffle() click to toggle source
# File lib/hashery/sparsearray.rb, line 452
def shuffle
  dup.shuffle!
end
shuffle!() click to toggle source
# File lib/hashery/sparsearray.rb, line 457
def shuffle!
  size.times do
    a = rand(size).to_i
    b = rand(size).to_i
    self[a], self[b] = self[b], self[a]
  end 
end
slice(*args) click to toggle source
# File lib/hashery/sparsearray.rb, line 468
def slice(*args)
  self[*args]
end
slice!(*args) click to toggle source
# File lib/hashery/sparsearray.rb, line 472
def slice!(*args)
  result = self[*args]
  self[*args] = nil
  result
end
sort() click to toggle source
# File lib/hashery/sparsearray.rb, line 478
def sort
  raise "SparseArray does not currently support sorting with blocks" if block_given?
  nha = self.dup
  qsort(nha,0,nha.length-1)
end
sort!() click to toggle source
# File lib/hashery/sparsearray.rb, line 509
def sort!
  raise "SparseArray does not currently support sorting with blocks" if block_given?
  qsort(self,0,self.length-1)
end
to_a() click to toggle source
# File lib/hashery/sparsearray.rb, line 514
def to_a
  a = []
  (0..self.length-1).each { |i| a << self.fetch(i) }
  a
end
to_ary() click to toggle source
# File lib/hashery/sparsearray.rb, line 520
def to_ary
  self
end
to_h() click to toggle source
# File lib/hashery/sparsearray.rb, line 524
def to_h
 h = Hash.new
 self.each { |k,v| h[k] = v }
 h
end
to_s() click to toggle source
# File lib/hashery/sparsearray.rb, line 530
def to_s
  self.join
end
uniq() click to toggle source
# File lib/hashery/sparsearray.rb, line 539
def uniq
  nha = self.class.new
  (0..self.length-1).each do |i|
    nha[nha.length] = self[i] if !nha.has_value?(self[i])
  end
  nha
end
uniq!() click to toggle source
# File lib/hashery/sparsearray.rb, line 548
def uniq!
  j = 0
  (1..self.length-1).each do |i|
    if !self[0..j].has_value?(self[i])
      self[j+1] = self[i]
      j+=1
    end
  end
  (j+1..self.length-1).each { |i| qdelete(i) }
end
unshift(e) click to toggle source
# File lib/hashery/sparsearray.rb, line 559
def unshift(e)
  i = self.length - 1
  while i >= 0
    self.set(i+1,self.fetch(i))
    return i if self.fetch(i) == e
    i -= 1
  end
  self.set(0,e)
  self
end
values_at(*ix) click to toggle source
# File lib/hashery/sparsearray.rb, line 570
def values_at(*ix)
  nha = self.class.new
  ix.each {|i| nha[nha.length] = self.at(i)}
  nha
end
|(ha) click to toggle source
# File lib/hashery/sparsearray.rb, line 139
def |(ha)
  nha = self.dup
  ha.each { |v| nha << v if !nha.has_value?(v) }
  nha
end

[Validate]

Generated with the Darkfish Rdoc Generator 2.