[omniORB] python evictor

[enrico.sirola@riskmap.it]

>>>>> "darryl" == darryl  <developer@csrules.dyndns.org> writes:

    darryl> has anyone implemented an evictor pattern in python they'd
    darryl> like to share?

here we go... It's not very well tested, so i'd like to have some
feedback. Bye,
enrico

--------------------> Evictor.py <--------------------

# Copyright (C) 2003 RiskMap s.r.l. Milano          -*-python-*-
#
# RiskMap
# Via G. B. Vico 4
# I-20123 Milano
# ITALY
#
# phone: +39 02 43317510
# fax: +39 02 43911424
#
# email: info@riskmap.net
# 
# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE. 
# 
# Author: Enrico Sirola (sirola@fisica.unige.it)

__version__ = "$Revision: 1.3 $"[11:-2]

import UserDict
    
class Evictor(UserDict.UserDict):
    """
    A simple eviction class: to be more pythonic, it works like a dictionary
    eviction strategy is LRU.
    """
    class _LinkedList:
        """private Linked list implementation, used by the Evictor class only"""
        class ListItem:
            """linked list item, used by the Evictor class only"""
            def __init__(self, key, value, next = None, prev = None):
                self.key = key
                self.value = value
                self.next = next
                self.prev = prev
            def __repr__(self):
                return str((self.key, self.value))
            
        def __init__(self):
            self.first = None
            self.last = None
            self.size = 0
        
        def append(self, item):
            item.prev = self.last
            item.next = None
            if self.last: self.last.next = item
            if not self.first: self.first = item
            self.last = item
            self.size += 1
            return item
    
        def remove(self, item):
            p = item.prev
            n = item.next
            if p: p.next = n
            else: self.first = item.next
            if n: n.prev = p
            else: self.last = item.prev
            self.size -= 1
            del item


    def __init__(self,
                 itemsFactory,
                 size):
        """
        Evictor(itemsFactory, size):
        itemsFactory is a callable object which returns an instance given key (i.e.
        a constructor: obviously key must be hashable)
        size is the eviction queue size.
        """
        self.factory = itemsFactory
        self.list = Evictor._LinkedList()
        self.data = {}
        self.size = size
        
    def __getitem__(self, key):
        """
        returns the item related to the given key. if the item is not
        in the map, allocates it and returns. It returns KeyError iff
        the item constructor fails
        TODO: think about KeyError exception
        """
        item = self.data.get(key)
        if not item:
            if self.list.size == self.size:
                firstItem = self.list.first
                self.list.remove(firstItem)
                del self.data[firstItem.key]
            item = self.list.append(Evictor._LinkedList.ListItem(key, self.factory(key)))
            self.data[key] = item
        else:
            self.list.remove(item)
            self.list.append(item)
        return item.value

-- 
Enrico Sirola <enrico.sirola@riskmap.it>
gpg public key available from www.keyserver.net, Key ID 0x377FE07F
Key fingerprint = B446 7332 ED55 BC68 5FE8  DE0F 98DF EC86 377F E07F