Indexed file class (Generic programming)

Indexed file class (Generic programming)

Post by Pierre Baillarge » Sat, 02 Aug 2003 09:48:50



Is there a reason why you don't simply use the type list to generate a
tuple class to be kept as the map key? The tuple class would be a
generalization of the std::pair template that can be extended
indefinitely by using a type list. Something along the line:

// Normal type list.
template <class T, class U>
struct Typelist
{
   typedef T Head;
   typedef U Tail;

Quote:};

class NullType {};

// Note: generic template is undefined.
template <class T> class tuple;

// Note: NullType is the end-of-type-list.
template <> tuple<NullType>
{
   bool operator<( const tuple<NullType> & ) const
   {
      return false;
   }

Quote:};

template <class T, class U> class tuple< TypeList<T,U> >
{
   tuple( const T & val, const tuple<U> & other )
   : value( val ), rest( other )
   {
   }

   bool operator<( const tuple< TypeList<T,U> > & other ) const
   {
      return ( value <  other.value )
          || ( value == other.value && rest < other.rest );
   }

   const T & get() const
   {
      return value;
   }

   const tuple<U> & other() const
   {
      return rest;
   }

private:
   T value;
   tuple<U> rest;

Quote:};

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
 
 
 

Indexed file class (Generic programming)

Post by Joaquín Ma López Mu? » Sat, 02 Aug 2003 10:58:02


Hi Gareth,


> I am writing a class which implements an indexed file.  What I want to
> do is to store a collection of objects, along with one or more sets of
> keys which maps to those objects.  This can be thought of as a table,
> where the first N columns contain the keys, and the final column
> contains the 'value' object.  I have implemented a special case of
> this class, where all N keys are of the same type.  This gives me a
> class which looks like the following:

[stuff deleted]

Quote:

> Clearly there is a lot I have not gone into here, but I hope you get
> the idea.  This class works fine; the problem I have is that the
> design is not generic enough.  I would prefer to be able to specify
> different types for each key column, so I have started thinking about
> using TypeLists.  Then the signature of the class would be more like
> this:

>     template<class TL, typename Value> class IndexedFile { ... };

> where TL is a TypeList.  The problem is that I don't know how to
> implement the maps - the best I have come up with so far goes like
> this:

[stuff deleted]

I've recently wrote a class which I'm trying to submit to
Boost and implements ideas similar to yours. It is called
indexed_set and can be found at

http://groups.yahoo.com/group/boost/files/indexed_set.zip

(caveat: documentation is in preliminary stage, plus I'm still
adding features to the library).

indexed_set implements an associative container handling several
sorting criteria or keys, which are provided at compile-time
thru MPL typelists. Some of the design issues you mention
arose already in indexed_set, so you might find some inspiration
in the code (or even use it directly to implement your indexed
file class).
There's been some discussion about this container in the Boost
mailing list. Google for "indexed_set" or "multiindex_set" (its
former name) and "Boost".

Regards,

Joaqun M Lpez Mu?oz
Telefnica, Investigacin y Desarrollo

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

Indexed file class (Generic programming)

Post by Rob Williscrof » Sun, 03 Aug 2003 01:15:45



Quote:> I'd have to recursively define IndexedFile in a
> similar way to the definition of the TypeList itself, starting with an
> 'IndexedFile1' with just one index, then an 'IndexedFile2' which
> derives from IndexedFile2, just adding the second map, and so on...
> Could anyone shed some light?

I had a go at this using boost::tuple<> as a list of key's,
as the code is 180 lines I put it on my web site:

http://www.victim-prime.dsl.pipex.com/uploaded/multi_indexed.html

anyway here's the main() for flavour

int main()
{
  typedef tuple< int, int > keys_t;

  typedef indexed< keys_t, std::string > indexed_t;
  indexed_t idx;

  idx.insert( keys_t( 1, 1 ), "1 - 1");
  idx.insert( keys_t( 2, 2 ), "2 - 2");

  indexed_t::ptr_t ptr = idx.find< 0 >( 1 );
  std::string s(*ptr);
  std::cout << s << std::endl;

  ptr = idx.find< 1 >( 2 );
  s = *ptr;
  std::cout << s << std::endl;

  std::cout << "OK" << std::endl;

Quote:}

I've tried something similar myself, though I was specifically
trying to get all the map's to share common node's (i.e. no
list<> and no list<>::iterators) and also handle compound keys,
1 - 1, 1 - 2, 2 - 1, 2 - 2.

If its of any interest the (hairy) code is available on my web site.

Basic docs are here:
http://www.victim-prime.dsl.pipex.com/docs/tuple_map/html/index.html
(uses boost::tuple<> tested with boost 1.30 using MSVC 7.1 & gcc 3.2).

If you can get it working on your compiler you could try
something like:

typedef tuple< Key0, Key1, Key2, Key3, proxy< Value > > tuple_t;

typedef tuple_map< tuple_t, 4, 1> map_t;
/* 4 keys the first is a unique key */

map_t map;

/* populate the map */

for ( /* each record in your file */ )
{
  tuple_t value(
    key0, key1, key2, key3, proxy< Value >( value_initializer )
  );

  map.insert( value );  

Quote:}

/* Lookup on a key */

map_t::iterator< 2 > iter2 = map.lower_bound<2>( key2 );
map_t::iterator< 2 > end2 =  map.upper_bound<2>( key2 );

for (; iter2 != end; ++iter2 )
{
  proxy< Value > & ref = iter2->get< 4 >();

Quote:}

Rob.
--
http://www.victim-prime.dsl.pipex.com/

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

Indexed file class (Generic programming)

Post by Siemel Nara » Sun, 03 Aug 2003 02:16:09



> Again, I hope this sketch is enough to illustrate the main features of
> the design.  The problem is that I feel I have only taken the generic
> programming half-way.  Since the types of all the key columns are
> known at compile-time, I don't think that the ValueBase/Value class
> system is really necessary.  Moreover, if the index contains a large
> number of entries, I don't want the storage and time overheads
> incurred by the wrapper class.  Is there some nifty template
> programming which I can use to get from e.g.

>     TYPELIST_3<int,double,float>

> to something analagous to

>     map<int,    list<proxy_t>::iterator>    map0;
>     map<double, list<proxy_t>::iterator>    map1;
>     map<float,  list<proxy_t>::iterator>    map2;

////////////////////////////////////////////////////////

template <bool cond, class A, class B>
struct template_if
{

Quote:};

template <class A, class B>
struct template_if<true,A,B>
{
   typedef A result;

Quote:};

template <class A, class B>
struct template_if<false,A,B>
{
   typedef B result;

Quote:};

////////////////////////////////////////////////////////

template <class T, class U=void>
struct typelist
{
   typedef T car;
   typedef U cdr;

Quote:};

template <class list>
struct typelist_size
{
   const unsigned result = 1u + typelist_size<typename list::cdr>;

Quote:};

template <>
struct typelist_size<void>
{
   const unsigned result = 0u;

Quote:};

template <class list, unsigned n>
struct typelist_at
{
   typedef typename list::car car;
   typedef typename list::cdr cdr;
   typedef typename template_if<!n, car, typename
typelist_at<cdr,n-1>::result>::result result;

Quote:};

template <template <class> class Predicate, class list>
struct typelist_find
{
   typedef typename list::car car;
   typedef typename list::cdr cdr;

   typedef typename
      template_if<
             Predicate<car>::result,
             car,
             typename find_typelist<Predicate,cdr>::result
            > :: result
         result;

Quote:};

template <template <class> class Predicate>
struct typelist_find<Predicate,void>
{
   typedef void result;

Quote:};

////////////////////////////////////////////////////////

typedef typelist<int, typelist<double> > MyKeyTypes;

template <class KeyTypes, class Value>
class IndexedFile {
        typedef proxy<Value>                 proxy_t;

        typedef list<proxy_t>                list_t;
        list_t                    data_;

        template <class TL>
        struct list_map_t {
           typedef map<typename TL::car, list_t::iterator>    car;
           car                    carobj;
           typedef list_map_t<typename TL::cdr> cdr;
           cdr         cdrobj;

           template <unsigned n>
           typedef typename typelist_at<list_map_t, n>::result at_t;

           template <unsigned n>
           const at_t& at() const {
              const void * result = (!n ? static_cast<const void *>(&carobj)
: static_cast<const void *>&(cdrobj.template at<n-1>()));
              return * static_cast<const at *>(result);
           }
        };

        template <>
        struct list_map_t<void> {
        };

        typedef list_map_t<TL> my_list_map_t;
        my_list_map_t list_map;

public:
           template <unsigned n>
           const Value&    get(const Key& key)    const {
              typedef typename my_list_map_t::template at_t<n>::at_t map_t;
              const map_t& map = list_map.template at<n>();
              return *map[key]; // oops: can't call operator[] on const
object, use find instead
           }

Disclaimer: Haven't tried to compile this, but it seems it should work.

--
+++++++++++
Siemel Naran

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]