[Boost-commit] svn:boost r7411

From: hervebronnimann_at_[hidden]
Date: 2007-07-12 01:37:21

Author: hervebronnimann
Date: 2007-07-12 01:37:19 EDT (Thu, 12 Jul 2007)
New Revision: 7411
URL: http://svn.boost.org/trac/boost/changeset/7411

Log:
First component for container selectors..

Added:
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.cpp
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.hpp
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.t.cpp

Added: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.cpp	2007-07-12 01:37:19 EDT (Thu, 12 Jul 2007)
@@ -0,0 +1,3 @@
+//container_selectors.cpp   -*- C++ -*-
+
+#include <boost/hdstl/halfedge_ds/container_selectors.hpp>

Added: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.hpp	2007-07-12 01:37:19 EDT (Thu, 12 Jul 2007)
@@ -0,0 +1,426 @@
+//container_selectors.hpp   -*- C++ -*-
+//
+//@PURPOSE: Provide selectors for container
+//
+//@CLASSES:
+//  'container_gen':  class for selecting the storage type of a collection
+//          'hashS':  selector for the 'std::tr1::hash_set' container
+//          'listS':  selector for the 'std::list' container
+//           'setS':  selector for the 'std::set' container
+//         'slistS':  selector for the 'std::ext::slist' container (if provided)
+//           'vecS':  selector for the 'std::vector' container
+//  
+//@SEE_ALSO: {halfedge_ds.hpp}
+//
+//@DESCRIPTION: This component provides 'container_gen', a class which,
+// properly specialized for the specified 'Selector', gives various traits of
+// the container of the specified 'ValueType' suitable by the 'halfedge_ds'
+// implementation.  The various selectors defined also in this component are:
+//..
+//  Selector    Container
+//  --------    -------------------------------
+//   'hashS'    'std::tr1::hash_set'
+//   'listS'    'std::list'
+//    'setS'    'std::set'
+//  'slistS'    'std::ext::slist' (if provided)
+//    'vecS'    'std::vector'
+//..
+//
+///Usage
+///-----
+// Suppose we want a data structure 'ElementCollection' containing instances of
+// a custom 'Element' type, stored in a container chosen by a selector given as
+// template parameter.  To make this picture more concrete, let us pick an
+// implementation:
+//..
+//  struct Element {
+//      int           userId;
+//      std::string   familyName;
+//      int           securityLevel;
+//      Element(int uId, std::string name, int level)
+//      : userId(uId), familyName(name), selected(level) {}
+//  };
+//  bool operator<(const Element& lhs, const Element& rhs) {
+//      return lhs.userId < rhs.userId;
+//  }
+//..
+//  We can implement 'ElementCollection' using the 'container_gen' facility as
+//  follows.  We purposely keep the de
+//..
+//  template <typename ContainerS>
+//  class ElementCollection {
+//      // This class stores and gives access to a collection of 'Element'
+//      // objects, using the container selected by the specified 'ContainerS'
+//      // selector.
+//
+//    public:
+//      // TYPES
+//      typedef typename container_gen<ContainerS>::type       container_type;
+//      typedef typename container_gen<ContainerS>::descriptor container_type;
+//
+//    private:
+//      // DATA
+//      container_type  m_collection;
+//
+//    public:
+//      // CREATORS
+//      ElementCollection();
+//          // Create an empty collection of 'Element' objects.
+//
+//      template <Iterator>
+//      ElementCollection(Iterator elementBegin, Iterator elementEnd);
+//          // Create a collection of 'Element' objects initially containing
+//          // the objects in the specified range '[elementBegin, elementEnd)'.
+//
+//      // MANIPULATORS
+//      iterator appendElement(Element const& object);
+//          // Append the specified 'object' to this collection.
+//
+//      iterator begin() { return m_collection.begin(); }
+//          // Return an iterator pointing to the beginning of this collection.
+//
+//      iterator end() { return m_collection.end(); }
+//          // Return an iterator pointing past the end of this collection.
+//
+//      container_type& theContainer() { return m_collection; }
+//          // Return the modifiable container underlying this collection.
+//
+//      // ACCESSORS
+//      const container_type& theContainer() const { return m_collection; }
+//          // Return the non-modifiable container underlying this collection.
+//  };
+//..
+// We can now use the collection as follows.  First let us create the
+// individual elements:
+//..
+//  Element george(632, "Harrison",  +78);
+//  Element john  (834, "Lennon",    +255);
+//  Element paul  (432, "McCartney", +126);
+//  Element ringo (432, "Starr",     +123);
+//  Element theBeatles[] = { george, john, paul, ringo };
+//..
+// We can use a collection as a searchable set:
+//..
+//  ElementCollection<setS> setCollection(theBeatles, theBeatles + 4);
+//  assert(setCollection.container().find(843) == setCollection.end());
+//  assert(setCollection.container()[834]->familyName == "Lennon");
+//..
+// or as an indexed array:
+//..
+//  ElementCollection<vecS> vectorCollection(theBeatles, theBeatles + 4);
+//  assert(setCollection.container()[1]->familyName == "Lennon");
+//  assert(setCollection.container()[3]->familyName == "Starr");
+//..
+
+#ifndef BOOST_HDSTL_CONTAINER_SELECTORS_HPP
+#define BOOST_HDSTL_CONTAINER_SELECTORS_HPP 1
+
+#include <list>
+#include <set>
+#if 0
+#include <slist>
+#include <tr1/hash_set>
+#endif
+#include <vector>
+
+namespace boost {
+namespace hdstl {
+
+template <typename Selector, typename ValueType>
+struct container_gen {
+    // This 'struct', properly specialized for the specified 'Selector', gives
+    // various traits of the container of the specified 'ValueType' suitable by
+    // the 'halfedge_ds' implementation.
+};
+
+/*
+struct hashS {
+    // This tag 'struct' is used by 'container_gen' to select the
+    // specialization that uses the 'std::tr1::hash_set' container.
+};
+*/
+
+struct listS {
+    // This tag 'struct' is used by 'container_gen' to select the
+    // specialization that uses the 'std::list' container.
+};
+
+struct setS {
+    // This tag 'struct' is used by 'container_gen' to select the
+    // specialization that uses the 'std::set' container.
+};
+
+/*
+struct slistS {
+    // This tag 'struct' is used by 'container_gen' to select the
+    // specialization that uses the 'slist' container (an SGI STL extension to
+    // the C++ Standard Library).
+};
+*/
+
+struct vecS {
+    // This tag 'struct' is used by 'container_gen' to select the
+    // specialization that uses the 'std::vector' container.
+};
+
+// SPECIALIZATIONS
+#if 0
+template <typename ValueType>
+struct container_gen<hashS, ValueType> {
+    // This specialization of 'container_gen' selects the 'std::tr1::hash_set'
+    // container.
+
+    // TYPES
+    typedef std::tr1::hash_set<ValueType> type;
+        // The container type, here a 'std::tr1::hash_set'.
+
+    typedef ValueType* descriptor;
+        // Type used to describe an element in the collection of elements
+        // present in a given container.
+        //
+        // TODO  This is only a suitable choice if hash_set uses chaining, but
+        // not if it uses double hashing.  TR1 allows iterators and references
+        // to be invalidated upon (implicit or explicit) rehashing.  Possible
+        // solution: rely on Boost.multiIndex hashed indices, which have
+        // stronger guarantees.
+
+    struct iterator : public std::list<ValueType>::iterator {
+        // Iterator type over a given container.  Note: the value type must be
+        // a descriptor, so we cannot use a 'tr1::hash_set:iterator'.  Instead,
+        // we create a very similar type, but override the 'operator*'.
+
+        typedef typename std::tr1::hash_set<ValueType>::iterator base_type;
+      public:
+        // CREATORS
+        iterator() {}
+            // Create an unitialized iterator.
+        iterator(base_type it) : base_type(it) {}
+            // Create an iterator pointing to the same element as the specified
+            // 'it' iterator in the specified 'container'.
+        // MANIPULATORS
+        ValueType* operator*()
+            // Return the descriptor of the element pointed to by this
+            // iterator.
+        {
+            return &(*base_type());
+        }
+        // ACCESSORS
+        ValueType* operator*() const
+            // Return the descriptor of the element pointed to by this
+            // iterator.
+        {
+            return &(*base_type());
+        }
+    };
+
+    // CLASS METHODS
+    static iterator container_begin(type& container)
+        // This utility returns an iterator to the beginning of the 
+        // specified 'container'.
+    {
+        return container.begin();
+    }
+
+    static iterator container_end(type& container)
+        // This utility returns an iterator to the beginning of the 
+        // specified 'container'.
+    {
+        return container.end();
+    }
+
+    static descriptor to_descriptor(iterator it, type& container)
+        // This utility translates the specified 'it' iterator to a descriptor
+        // referring to the same element in the specified 'container'.
+    {
+        return &(*it);
+    }
+
+    static iterator to_iterator(descriptor desc, type& container)
+        // This utility translates the specified 'desc' descriptor to an
+        // iterator referring to the same element in the specified 'container'.
+    {
+        return /* not known */;
+    }
+};
+#endif
+
+template <typename ValueType>
+struct container_gen<listS, ValueType> {
+    // This specialization of 'container_gen' selects the 'std::list'
+    // container.
+
+    // TYPES
+    typedef std::list<ValueType> type;
+        // The container type, here a 'std::list'.
+
+    typedef ValueType* descriptor;
+        // Type used to describe an element in the collection of elements
+        // present in a given container.
+
+    struct iterator : public std::list<ValueType>::iterator {
+        // Iterator type over a given container.  Note: the value type must be
+        // a descriptor, so we cannot use a 'std::list:iterator'.  Instead,
+        // we create a very similar type, but override the 'operator*'.
+
+        typedef typename std::list<ValueType>::iterator base_type;
+      public:
+        // CREATORS
+        iterator() {}
+            // Create an unitialized iterator.
+        iterator(base_type it) : base_type(it) {}
+            // Create an iterator pointing to the same element as the specified
+            // 'it' iterator in the specified 'container'.
+        // MANIPULATORS
+        ValueType* operator*()
+            // Return the descriptor of the element pointed to by this
+            // iterator.
+        {
+            return &(*base_type());
+        }
+        // ACCESSORS
+        ValueType* operator*() const
+            // Return the descriptor of the element pointed to by this
+            // iterator.
+        {
+            return &(*base_type());
+        }
+    };
+
+    // CLASS METHODS
+    static iterator container_begin(type& container)
+        // This utility returns an iterator to the beginning of the 
+        // specified 'container'.
+    {
+        return container.begin();
+    }
+
+    static iterator container_end(type& container)
+        // This utility returns an iterator to the beginning of the 
+        // specified 'container'.
+    {
+        return container.end();
+    }
+};
+
+template <typename ValueType>
+struct container_gen<setS, ValueType> {
+    // This specialization of 'container_gen' selects the 'std::set'
+    // container.
+
+    // TYPES
+    typedef std::set<ValueType> type;
+        // The container type, here a 'std::set'.
+
+    typedef const ValueType* descriptor;
+        // Type used to describe an element in the collection of elements
+        // present in a given container.
+
+    struct iterator : public std::set<ValueType>::iterator {
+        // Iterator type over a given container.  Note: the value type must be
+        // a descriptor, so we cannot use a 'std::set:iterator'.  Instead,
+        // we create a very similar type, but override the 'operator*'.
+
+        typedef typename std::set<ValueType>::iterator base_type;
+      public:
+        // CREATORS
+        iterator() {}
+            // Create an unitialized iterator.
+        iterator(base_type it) : base_type(it) {}
+            // Create an iterator pointing to the same element as the specified
+            // 'it' iterator in the specified 'container'.
+        // MANIPULATORS
+        const ValueType* operator*()
+            // Return the descriptor of the element pointed to by this
+            // iterator.
+        {
+            return &(*base_type());
+        }
+        // ACCESSORS
+        const ValueType* operator*() const
+            // Return the descriptor of the element pointed to by this
+            // iterator.
+        {
+            return &(*base_type());
+        }
+    };
+
+    // CLASS METHODS
+    static iterator container_begin(type& container)
+        // This utility returns an iterator to the beginning of the 
+        // specified 'container'.
+    {
+        return container.begin();
+    }
+
+    static iterator container_end(type& container)
+        // This utility returns an iterator to the beginning of the 
+        // specified 'container'.
+    {
+        return container.end();
+    }
+};
+
+template <typename ValueType>
+struct container_gen<vecS, ValueType> {
+
+    // TYPES
+    typedef std::vector<ValueType> type;
+        // The container type, here a 'std::list'.
+
+    typedef typename std::vector<ValueType>::size_type  descriptor;
+        // Type used to describe an element in the collection of elements
+        // present in a given container.
+
+    struct iterator : public std::vector<ValueType>::iterator {
+        // Iterator type over a given container.  Note: the value type must be
+        // a descriptor, so we cannot use a 'std::vector:iterator'.  Instead,
+        // we create a very similar type, but override the 'operator*'.
+
+        typedef typename std::vector<ValueType>::iterator base_type;
+        // DATA
+        std::vector<ValueType> *m_container;
+      public:
+        // CREATORS
+        iterator()
+            // Create an unitialized iterator.
+        : m_container(0) {}
+        iterator(std::vector<ValueType> *container, base_type it)
+            // Create an iterator pointing to the same element as the specified
+            // 'it' iterator in the specified 'container'.
+        : base_type(it), m_container(container) {}
+        // MANIPULATORS
+        typename std::vector<ValueType>::size_type operator*()
+            // Return the descriptor of the element pointed to by this
+            // iterator.
+        {
+            return base_type(*this) - m_container->begin();
+        }
+        // ACCESSORS
+        typename std::vector<ValueType>::size_type operator*() const
+            // Return the descriptor of the element pointed to by this
+            // iterator.
+        {
+            return base_type(*this) - m_container->begin();
+        }
+    };
+
+    // CLASS METHODS
+    static iterator container_begin(type& container)
+        // This utility returns an iterator to the beginning of the 
+        // specified 'container'.
+    {
+        return iterator(&container, container.begin());
+    }
+
+    static iterator container_end(type& container)
+        // This utility returns an iterator to the beginning of the 
+        // specified 'container'.
+    {
+        return iterator(&container, container.end());
+    }
+};
+
+} // namespace hdstl
+} // namespace boost
+
+#endif

Added: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.t.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.t.cpp	2007-07-12 01:37:19 EDT (Thu, 12 Jul 2007)
@@ -0,0 +1,232 @@
+//container_selectors.hpp   -*- C++ -*-
+//
+//@OVERVIEW:  The component under test is a selector class.  We
+// must make sure that all selectors are suitably defined and that the
+// selection is done properly.
+//
+//@TEST_PLAN: First create an instance of all the selectors (to make sure they
+// exist, and verify that there are no more than tested).  Then instantiate the
+// 'container_gen<ContainerS,ValueType>' for a given value type and all
+// selectors, and verify that its members have the expected types and
+// signatures.  Finally, verify that the usage example compiles and executes
+// without errors, when assert is replaced by BOOST_CHECK.
+
+#include <boost/hdstl/halfedge_ds/container_selectors.hpp>
+
+#include <boost/test/minimal.hpp>
+
+#include <set>
+#include <string>
+#include <vector>
+
+using namespace boost::hdstl;
+using namespace std;
+
+// ===========================================================================
+//                              SELECTOR CLASSES
+// ===========================================================================
+
+template <typename ContainerS>
+bool selector_requirements(ContainerS const&) {
+    return false;
+}
+
+#if 0
+bool selector_requirements(boost::hdstl::hashS const&) {
+    return true;
+}
+#endif
+
+bool selector_requirements(listS const&) {
+    return true;
+}
+
+bool selector_requirements(setS const&) {
+    return true;
+}
+
+bool selector_requirements(vecS const&) {
+    return true;
+}
+
+// ===========================================================================
+//                              CLASS CONTAINER_GEN
+// ===========================================================================
+
+template <class ContainerGen, typename ContainerS>
+bool selection_requirements(ContainerS const&, ContainerGen&) {
+    return false;
+}
+
+#if 0
+template <typename ValueType>
+bool selection_requirements(hashS, std::tr1::hash_set<ValueType>&) {
+    return true;
+}
+#endif
+    
+template <typename ValueType>
+bool selection_requirements(listS, std::list<ValueType>&) {
+    return true;
+}
+    
+template <typename ValueType>
+bool selection_requirements(setS, std::set<ValueType>&) {
+    return true;
+}
+    
+template <typename ValueType>
+bool selection_requirements(vecS, std::vector<ValueType>&) {
+    return true;
+}
+    
+template <class ContainerGen, typename ValueType, typename ContainerS>
+bool container_gen_requirements() {
+    ValueType array[] = { 0, 1, 2, 3 };
+    typename ContainerGen::type container(array, array + 4);
+    
+    BOOST_CHECK(( selection_requirements(ContainerS(), container) ));
+
+    // Types must exist.
+    typedef typename ContainerGen::descriptor descriptor;
+    typedef typename ContainerGen::iterator   iterator;
+
+    // Value type of iterator must be a descriptor.
+    iterator begin = ContainerGen::container_begin(container);
+    descriptor theBegin = *begin;
+
+    return true;
+}
+
+// ===========================================================================
+//                              USAGE EXAMPLE
+// ===========================================================================
+
+///Usage
+///-----
+// Suppose we want a data structure 'ElementCollection' containing instances of
+// a custom 'Element' type, stored in a container chosen by a selector given as
+// template parameter.  To make this picture more concrete, let us pick an
+// implementation:
+//..
+    struct Element {
+        int           userId;
+        std::string   familyName;
+        int           securityLevel;
+        Element(int uId, std::string name, int level)
+        : userId(uId), familyName(name), securityLevel(level) {}
+    };
+    bool operator<(const Element& lhs, const Element& rhs) {
+        return lhs.userId < rhs.userId;
+    }
+//..
+//  We can implement 'ElementCollection' using the 'container_gen' facility as
+//  follows.  We purposely keep the de
+//..
+    template <typename ContainerS>
+    class ElementCollection {
+        // This class stores and gives access to a collection of 'Element'
+        // objects, using the container selected by the specified 'ContainerS'
+        // selector.
+  
+      public:
+        // TYPES
+        typedef container_gen<ContainerS, Element>       container_generator;
+        typedef typename container_generator::type       container_type;
+        typedef typename container_generator::descriptor descriptor;
+        typedef typename container_generator::iterator   iterator;
+  
+      private:
+        // DATA
+        container_type  m_collection;
+  
+      public:
+        // CREATORS
+        ElementCollection() {}
+            // Create an empty collection of 'Element' objects.
+  
+        template <typename Iterator>
+        ElementCollection(Iterator elementBegin, Iterator elementEnd)
+            // Create a collection of 'Element' objects initially containing
+            // the objects in the specified range '[elementBegin, elementEnd)'.
+        : m_collection(elementBegin, elementEnd) {}
+  
+        // MANIPULATORS
+        iterator begin() { return container_generator::container_begin(m_collection); }
+            // Return an iterator pointing to the beginning of this collection.
+  
+        iterator end() { return container_generator::container_end(m_collection); }
+            // Return an iterator pointing past the end of this collection.
+  
+        container_type& theContainer() { return m_collection; }
+            // Return the modifiable container underlying this collection.
+  
+        // ACCESSORS
+        const container_type& theContainer() const { return m_collection; }
+            // Return the non-modifiable container underlying this collection.
+    };
+//..
+// We can now use the collection as follows.  First let us create the
+// individual elements:
+//..
+    bool usageExample() {
+        Element george(632,  "Harrison",  +78);
+        Element john  (834,  "Lennon",    +255);
+        Element paul  (932,  "McCartney", +126);
+        Element ringo (1432, "Starr",     +123);
+        Element theBeatles[] = { george, john, paul, ringo };
+//..
+// We can use a collection as a searchable set:
+//..
+        ElementCollection<setS> setCollection(theBeatles, theBeatles + 4);
+        Element unknown(843, "Unkown",   +0);
+        BOOST_CHECK(( setCollection.theContainer().find(unknown) == setCollection.end() ));
+        BOOST_CHECK(( setCollection.theContainer().find(john)->familyName == "Lennon" ));
+//..
+// and access the iterators of the collection (here identical to the
+// iterators of the container):
+//..
+        BOOST_CHECK(( setCollection.begin()->familyName == "Harrison" ));
+        BOOST_CHECK(( (--setCollection.end())->familyName == "Starr" ));
+//..
+// or we can use the collection as an indexed array:
+//..
+        ElementCollection<vecS> vectorCollection(theBeatles, theBeatles + 4);
+        BOOST_CHECK(( vectorCollection.theContainer()[1].familyName == "Lennon" ));
+        BOOST_CHECK(( vectorCollection.theContainer()[3].familyName == "Starr" ));
+//..
+// and access the iterators of the collection (whose value type here is the
+// descriptor, not the same as the iterators of the container):
+//..
+        BOOST_CHECK( *vectorCollection.begin() == 0 );
+        BOOST_CHECK( *vectorCollection.end() == 4 );
+
+        return true;
+    }
+//..
+
+// ===========================================================================
+//                              BOOST TEST APPARATUS
+// ===========================================================================
+
+int test_main(int, char **)
+{
+    #if 0
+    BOOST_CHECK(( selector_requirements(hashS()) ));
+    #endif
+    BOOST_CHECK(( selector_requirements(listS()) ));
+    BOOST_CHECK(( selector_requirements(setS()) ));
+    BOOST_CHECK(( selector_requirements(vecS()) ));
+
+    #if 0
+    BOOST_CHECK(( selection_requirements<container_gen<hashS, int>, hashS>() ));
+    #endif
+    BOOST_CHECK(( container_gen_requirements<container_gen<listS, int>, int, listS>() ));
+    BOOST_CHECK(( container_gen_requirements<container_gen<setS, int>, int, setS>() ));
+    BOOST_CHECK(( container_gen_requirements<container_gen<vecS, int>, int, vecS>() ));
+
+    BOOST_CHECK(( usageExample() ));
+    
+    return 0;
+}
+