Class: 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 for *args parameters (since there is no way around those is some cases). SparseArray is for all practical purposes 100% compatible with Array.

SparseArray is slower then the built in Array class, but not as slow as one might expect, since a Hash in general is faster than an Array. It might be interesting to see how this would perform if it were written in c. Not all that useful, but an interesting example.

Methods

& * + - << <=> === [] [] []= assoc at collect collect! compact compact! concat count delete delete_at delete_if each each_index eql? fill first flatten flatten! include? join last map! new new_h nitems pack pop push qsort rassoc reindex reindex! reject! reverse reverse! reverse_each rindex shift slice slice! sort sort! to_a to_ary to_h to_s uniq uniq! unshift values_at |

Public Class methods

[](*args)

[ + ]

# File lib/more/facets/sparse_array.rb, line 40
  def self.[](*args)
    nha = new
    args.each { |a| nha.set(nha.length,a) }
    nha
  end

new(i=0,e=nil)

[ + ]

# File lib/more/facets/sparse_array.rb, line 52
  def initialize(i=0,e=nil)
    if i > 0
      i.times { self.set(self.length,e) }
    end
  end

new_h(hsh)

[ + ]

# File lib/more/facets/sparse_array.rb, line 46
  def self.new_h(hsh)
    nha = new
    nha.replace(hsh)
    #nha.reindex!
  end

Public Instance methods

&(ha)

[ + ]

# File lib/more/facets/sparse_array.rb, line 58
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 68
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 78
  def +(ha)
    nha = self.dup
    (0..ha.length-1).each { |i| nha.set(nha.length,ha.fetch(i)) }
    nha
  end

-(ha)

[ + ]

# File lib/more/facets/sparse_array.rb, line 84
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 91
  def <<(e)
    self.set(self.length,e)
    self
  end

<=>(ha)

[ + ]

# File lib/more/facets/sparse_array.rb, line 96
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 104
  def ===(ha)
    self.==(ha)
  end

[](i,l=nil)

[ + ]

# File lib/more/facets/sparse_array.rb, line 111
  def [](i,l=nil)
    if l
      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

[]=(i,b,c=nil)

[ + ]

# File lib/more/facets/sparse_array.rb, line 123
  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

assoc(k)

[ + ]

# File lib/more/facets/sparse_array.rb, line 152
  def assoc(k)
    (0...self.length).each { |i| return self.fetch(i) if self.fetch(i)[0] == k }
    return nil
  end

at(i)

[ + ]

# File lib/more/facets/sparse_array.rb, line 157
  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() {|self.fetch(i)| ...}

clear okay

[ + ]

# File lib/more/facets/sparse_array.rb, line 166
  def collect
    nha = self.class.new
    (0...self.length).each { |i| nha << yield(self.fetch(i)) }
    nha
  end

collect!() {|self.fetch(i)| ...}

This method is also aliased as map!

[ + ]

# File lib/more/facets/sparse_array.rb, line 172
  def collect!
    nha = self.class.new
    (0...self.length).each { |i| nha << yield(self.fetch(i)) }
    self.replace(nha)
  end

compact()

[ + ]

# File lib/more/facets/sparse_array.rb, line 178
  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!()

[ + ]

# File lib/more/facets/sparse_array.rb, line 189
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 204
  def concat(ha)
    (0...ha.length).each { |i| self.set(self.length,ha.fetch(i)) }
    self
  end

count(e=nil) {|self.fetch(i)| ...}

[ + ]

# File lib/more/facets/sparse_array.rb, line 209
  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) {|if block_given?| ...}

[ + ]

# File lib/more/facets/sparse_array.rb, line 224
  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

delete_at(i)

[ + ]

# File lib/more/facets/sparse_array.rb, line 235
  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() {|v| ...}

[ + ]

# File lib/more/facets/sparse_array.rb, line 249
  def delete_if
    qdelete_if { |i,v| yield(v) }
    reindex!
  end

each() {|self.fetch(i)| ...}

[ + ]

# File lib/more/facets/sparse_array.rb, line 254
  def each
    (0...self.length).each { |i| yield(self.fetch(i)) }
  end

each_index() {|i| ...}

[ + ]

# File lib/more/facets/sparse_array.rb, line 258
  def each_index
    (0...self.length).each { |i| yield(i) }
  end

eql?(ha)

empty? okay as is

[ + ]

# File lib/more/facets/sparse_array.rb, line 264
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 270
  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()

[ + ]

# File lib/more/facets/sparse_array.rb, line 282
  def first
    return nil if self.empty?
    self.fetch(0)
  end

flatten()

[ + ]

# File lib/more/facets/sparse_array.rb, line 287
  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!()

[ + ]

# File lib/more/facets/sparse_array.rb, line 300
  def flatten!
    return nil if !self.any? { |e| e.kind_of?(self.class) or e.kind_of?(Array) }
    self.replace(self.flatten)
  end

include?(v)

[ + ]

# File lib/more/facets/sparse_array.rb, line 305
  def include?(v)
    self.has_value?(v)
  end

join(sep='')

index okay

[ + ]

# File lib/more/facets/sparse_array.rb, line 311
  def join(sep='')
    s = ''
    (0...self.length).each { |i| s << "#{self.fetch(i)}#{sep}" }
    return s.chomp(sep)
  end

last()

[ + ]

# File lib/more/facets/sparse_array.rb, line 317
  def last
    self[self.length-1]
  end

map!()

Alias for collect!

nitems()

[ + ]

# File lib/more/facets/sparse_array.rb, line 325
  def nitems
    cnt = 0
    (0...self.length).each { |i| cnt += 1 if self.fetch(i) != nil }
    cnt
  end

pack(*args)

[ + ]

# File lib/more/facets/sparse_array.rb, line 331
  def pack(*args)
    self.to_a.pack(*args)
  end

pop()

[ + ]

# File lib/more/facets/sparse_array.rb, line 335
  def pop
    self.delete_at(self.length-1)
  end

push(*e)

[ + ]

# File lib/more/facets/sparse_array.rb, line 339
  def push(*e)
    self.concat(e)
  end

qsort(ha, l, r)

[ + ]

# File lib/more/facets/sparse_array.rb, line 438
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 343
  def rassoc(k)
    (0...self.length).each { |i| return self.fetch(i) if self.fetch(i)[1] == k }
    return nil
  end

reindex()

[ + ]

# File lib/more/facets/sparse_array.rb, line 348
  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!()

[ + ]

# File lib/more/facets/sparse_array.rb, line 361
  def reindex!
    self.replace(self.reindex)
  end

reject!() {|v| ...}

[ + ]

# File lib/more/facets/sparse_array.rb, line 365
  def reject!
    chg=nil
    qdelete_if { |i,v| r=yield(v); chg=true if r; r }
    return nil if !chg
    reindex!
  end

reverse()

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/more/facets/sparse_array.rb, line 379
  def reverse
    nha = self.class.new
    (0...self.length).each { |i| nha.set(self.length-1-i,self.fetch(i)) }
    nha
  end

reverse!()

[ + ]

# File lib/more/facets/sparse_array.rb, line 385
  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() {|self.fetch(i)| ...}

[ + ]

# File lib/more/facets/sparse_array.rb, line 395
  def reverse_each
    i = self.length - 1
    while i >= 0
      yield(self.fetch(i))
      i -= 1
    end
  end

rindex(e)

[ + ]

# File lib/more/facets/sparse_array.rb, line 403
  def rindex(e)
    i = self.length - 1
    while i >= 0
      return i if self.fetch(i) == e
      i -= 1
    end
    return nil
  end

shift()

[ + ]

# File lib/more/facets/sparse_array.rb, line 412
  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

slice(*args)

size okay

[ + ]

# File lib/more/facets/sparse_array.rb, line 422
  def slice(*args)
    self[*args]
  end

slice!(*args)

[ + ]

# File lib/more/facets/sparse_array.rb, line 426
  def slice!(*args)
    result = self[*args]
    self[*args] = nil
    result
  end

sort()

[ + ]

# File lib/more/facets/sparse_array.rb, line 432
  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!()

[ + ]

# File lib/more/facets/sparse_array.rb, line 463
  def sort!
    raise "SparseArray does not currently support sorting with blocks" if block_given?
    qsort(self,0,self.length-1)
  end

to_a()

[ + ]

# File lib/more/facets/sparse_array.rb, line 468
  def to_a
    a = []
    (0..self.length-1).each { |i| a << self.fetch(i) }
    a
  end

to_ary()

[ + ]

# File lib/more/facets/sparse_array.rb, line 474
  def to_ary
    self
  end

to_h()

[ + ]

# File lib/more/facets/sparse_array.rb, line 478
  def to_h
   h = Hash.new
   self.each { |k,v| h[k] = v }
   h
  end

to_s()

[ + ]

# File lib/more/facets/sparse_array.rb, line 484
  def to_s
   self.join
  end

uniq()

[ + ]

# File lib/more/facets/sparse_array.rb, line 488
  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!()

[ + ]

# File lib/more/facets/sparse_array.rb, line 496
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 507
  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)

[ + ]

# File lib/more/facets/sparse_array.rb, line 518
  def values_at(*ix)
    nha = self.class.new
    ix.each {|i| nha[nha.length] = self.at(i)}
    nha
  end

|(ha)

[ + ]

# File lib/more/facets/sparse_array.rb, line 146
  def |(ha)
    nha = self.dup
    ha.each { |v| nha << v if !nha.has_value?(v) }
    nha
  end