From: Robert Klemme <bob.news@...>
Date: 2004-03-29T23:54:23+09:00
Subject: Re: [newbie] linked hash

------=_NextPart_000_00E6_01C415AE.37564530
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit


"Yvon Thoraval" <yvon.thoravalNO-SPAM@free.fr> schrieb im Newsbeitrag
news:1gbf4b9.12juctd1qzju96N%yvon.thoravalNO-SPAM@free.fr...
> Robert Klemme <bob.news@gmx.net> wrote:
>
> > Dunno that class but what is it that you want to achieve?  Do you need
a
> > sorted Hash?
>
> no ordered only as it is entered, in the mean time i've found a solution

<snip/>

Ah, I see.  Alternatively you can use an LRU hash map like the one
attached.  You can easily adapt this to only reflect insertion order and
not general access order.

I guess there are other implementations in the RAA.

Kind regards

    robert

------=_NextPart_000_00E6_01C415AE.37564530
Content-Type: application/octet-stream;
	name="LRUCache.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="LRUCache.rb"


class LRUCache < Hash

  CacheNode = Struct.new(:key, :val, :prev, :next)

  attr_reader :max_size

  def initialize(max_size)
    @max_size = max_size
    @first = @last = nil
  end

  def []=(key, val)
    node = self[key]

    unless node
      if max_size && size >= max_size && @last
        delete @last.key
        # remove_last
      end

      node = CacheNode.new(key)
      super(key, node)
    end

    node.val = val
    move_to_head node

    val
  end

  def [](key)
    node = super

    if CacheNode === node
      # found
      move_to_head node
      node.val
    else
      # not found
      node
    end
  end

  # alias :store :[]=

  def delete(key, &b)
    node = super

    if CacheNode === node
      # found
      node.prev.next = node.next if node.prev
      node.next.prev = node.prev if node.next

      @last = node.prev if @last == node
      @first = node.next if @first == node

      node.val
    else
      # not found
      node
    end
  end

  def clear
    @first = @last = nil
    super
  end

  def each
    iter = @first

    while iter
      yield iter.key, iter.val
      iter = iter.next
    end

    self
  end

  def inspect
    str = nil

    each do |k,v|
      if str
        str << ", "
      else
        str = "{"
      end

      str << k.inspect << "=>" << v.inspect
    end

    str = "{" unless str
    str << "}"
  end

  private

  def move_to_head(node)
    return if node == @first

    node.prev.next = node.next if node.prev
    node.next.prev = node.prev if node.next

    @last = node.prev if @last == node

    @first.prev = node if @first
    node.next = @first
    @first = node

    node.prev = nil

    @last = @first unless @last
  end

  def remove_last
    if @last.prev
      @last.prev.next = nil
    else
      @first = nil
    end

    @last = @last.prev
  end
end

------=_NextPart_000_00E6_01C415AE.37564530--