#ifndef	__lru_h__
#define __lru_h__
/////////////////////////////////////////////////////
////////////////////////////////////////////////////
template<class KEY, class VALUE>
class LRUCache
{
  enum
  {
    SIZE=8,
  };
public:
  struct  cache_slot
  {
    KEY   key;
    VALUE val;
  };

private:
  unsigned    index;        //  We will use this to store the order in 1 based nibbles.
                            //  0 will be used for unasigned cache slots
                            //  We will store de most recent accesed index on the least 
                            //  significant bit.
  cache_slot  cache[SIZE];

public:
  LRUCache  ()  : index(0) {}

  inline  void  reset   ()
  {
    index=0;
  }

  inline  bool  find    (const  KEY& _key, VALUE& val_)
  {
    unsigned    msc = 0xffffffff; // auxiliary value we need to move one nibble from the middle
                                  // of the dword to the begining 
    unsigned    idx = index;
    cache_slot* ptr = (cache-1);  // prepare to access on 1 based index's
    while( idx )
    {
      unsigned hit = idx&0xf;
    //assert(hit<=8);
      msc<<=4;
      if(ptr[hit].key == _key)
      {
        //  key found, we move it to the "begining" so we find it faster next time.
        index = (index&msc) | ( (index<<4)&(~msc) ) | hit;
        val_  = ptr[hit].val;
        return(true);
      }
      idx>>=4;
    }
    return(false);
  }

  inline  void  insert  (const  KEY& _key, const VALUE& _val)
  {
    cache_slot* ptr = cache-1;    // prepare to access on 1 based index's
    unsigned    hit = index>>28;  // we remove the most significant nibble from the index table
    if(!hit)    //  only when filling de cache.
    {
      hit = 1;
      unsigned idx = index;
      while(idx&0xf)  { idx>>=4, ++hit; }
    //assert(hit<=SIZE);
    }
    ptr[hit].key = _key;
    ptr[hit].val = _val;
    index = (index<<4) | hit;
    return;
  }

};



/*
    LRUCache<int,int>  lru;
  
    lru.reset();

    int runs  = 1000;
    int range = 256;
    int hits  = 0;
    for(int i=0;i<runs;++i)
    {
      int key = rand()%range;
      int val = -1;
      if(!lru.find(key,val))
      {
        lru.insert(key,key);
      }
      else
      {
        assert(key==val);
        ++hits;
      }
    }
*/

/////////////////////////////////////////////////////
////////////////////////////////////////////////////
#endif  //__lru_h__