Class SparseArray
In: lib/more/facets/sparse_array.rb
Parent: Hash

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   |  

External Aliases

[] -> get
[]= -> set
delete -> qdelete
delete_if -> qdelete_if

Public Class methods

[Source]

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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

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

[Source]

# 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

[Source]

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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

clear okay

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

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

[Source]

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

[Source]

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

empty? okay as is

[Source]

# 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

[Source]

# 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

[Source]

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

[Source]

# 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

[Source]

# 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

[Source]

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

index okay

[Source]

# 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

[Source]

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

Alias for collect!

[Source]

# 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

[Source]

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

[Source]

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

[Source]

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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

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

[Source]

# 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

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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

size okay

[Source]

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

[Source]

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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

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

[Source]

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

[Source]

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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Source]

# 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

[Validate]