IdFactory.hpp

/* $Id$ */

#ifndef _IDMAKER_HPP_
#define _IDMAKER_HPP_

#include <list>
#include <set>
#include <iostream>

namespace jafar {
  namespace kernel {
    
    template <typename T>
    class IdCollectorNone
    {
      public:
        bool empty() { return true; }         
        T get() { return 0; }                 
        bool collect(T id) { return false; }  
        T size() { return 0; }                
        void clear() {}                       
        T defrag(T lastid) { return lastid; } 
    };
    
    template <typename T>
    class IdCollectorList
    {
      private:
        typedef std::list<T> storage_t;
        storage_t freed;
      public:
        bool empty() { return freed.empty(); }
        T get() { T res = freed.front(); freed.pop_front(); return res; }
        bool collect(T id) { freed.push_back(id); return true; }
        T size() { return freed.size(); }
        void clear() { freed.clear(); }
        T defrag(T lastid) { return lastid; } // would be too expensive to do something (at least n*log(n))
    };
    
    template <typename T>
    class IdCollectorSet
    {
      private:
        typedef std::set<T> storage_t;
        storage_t freed;
      public:
        bool empty() { return freed.empty(); }
        T get() { T res = *freed.begin(); freed.erase(freed.begin()); return res; }
        bool collect(T id) { return freed.insert(id).second; }
        T size() { return freed.size(); }
        void clear() { freed.clear(); }
        T defrag(T lastid)
        {
          typename storage_t::reverse_iterator rit;
          for(rit = freed.rbegin(); !freed.empty() && *rit == lastid; --lastid)
          {
            freed.erase(--rit.base());
            if (!freed.empty()) ++rit;
          }
          return lastid; 
        }
    };
    
    template <typename T = unsigned, template<typename> class IdCollector = IdCollectorNone>
    class IdFactory {
      public:
        IdFactory() : m_lastId(0) {}
        ~IdFactory() {}

        typedef T storage_t;
        
        T getId()
        {
          T id = (freed.empty() ? ++m_lastId : freed.get());
//std::cout << "IdFactory::getId " << id << std::endl;
          return id;
        }
        
        bool releaseId(T id) 
        {
//std::cout << "IdFactory::releaseId " << id << std::endl;
          if (id == 0 || id > m_lastId) return false;
          if (id == m_lastId ) 
            m_lastId = freed.defrag(m_lastId-1); 
          else 
            return freed.collect(id);
          return true;
        }
        
        void reset() { m_lastId = 0; freed.clear(); }
        
        T countUsed() { return m_lastId-freed.size(); }
        
        T countCollected() { return freed.size(); }
      private:
        T m_lastId;
        IdCollector<T> freed;
    };
    
    typedef IdFactory<unsigned, IdCollectorNone> IdFactoryNone;
    typedef IdFactory<unsigned, IdCollectorList> IdFactoryList;
    typedef IdFactory<unsigned, IdCollectorSet> IdFactorySet;
  }
}

#endif