OpenWalnut  1.4.0
WSharedSequenceContainer.h
00001 //---------------------------------------------------------------------------
00002 //
00003 // Project: OpenWalnut ( http://www.openwalnut.org )
00004 //
00005 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
00006 // For more information see http://www.openwalnut.org/copying
00007 //
00008 // This file is part of OpenWalnut.
00009 //
00010 // OpenWalnut is free software: you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as published by
00012 // the Free Software Foundation, either version 3 of the License, or
00013 // (at your option) any later version.
00014 //
00015 // OpenWalnut is distributed in the hope that it will be useful,
00016 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 // GNU Lesser General Public License for more details.
00019 //
00020 // You should have received a copy of the GNU Lesser General Public License
00021 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
00022 //
00023 //---------------------------------------------------------------------------
00024 
00025 #ifndef WSHAREDSEQUENCECONTAINER_H
00026 #define WSHAREDSEQUENCECONTAINER_H
00027 
00028 #include <algorithm>
00029 
00030 #include <boost/thread.hpp>
00031 
00032 #include "WSharedObject.h"
00033 
00034 /**
00035  * This class provides a common interface for thread-safe access to sequence containers (list, vector, dequeue ).
00036  * \param S the sequence container to use. Everything is allowed here which provides push_back and pop_back as well as size functionality.
00037  */
00038 template < typename S >
00039 class WSharedSequenceContainer: public WSharedObject< S >
00040 {
00041 public:
00042     // Some helpful typedefs
00043 
00044     /**
00045      * A typedef for the correct const iterator useful to traverse this sequence container.
00046      */
00047     typedef typename S::const_iterator   ConstIterator;
00048 
00049     /**
00050      * A typedef for the correct iterator to traverse this sequence container.
00051      */
00052     typedef typename S::iterator         Iterator;
00053 
00054     /**
00055      * The type of the elements
00056      */
00057     typedef typename S::value_type value_type;
00058 
00059     /**
00060      * Default constructor.
00061      */
00062     WSharedSequenceContainer();
00063 
00064     /**
00065      * Destructor.
00066      */
00067     virtual ~WSharedSequenceContainer();
00068 
00069     //////////////////////////////////////////////////////////////////////////////////////////
00070     // These methods implement common methods of all sequence containers. The list is not
00071     // complete but should be enough for now.
00072     // \NOTE: all methods using or returning iterators are NOT implemented here. Use the access
00073     // Object (getAccessObject) to iterate.
00074     //////////////////////////////////////////////////////////////////////////////////////////
00075 
00076     /**
00077      * Adds a new element at the end of the container.
00078      *
00079      * \param x the new element.
00080      */
00081     void push_back( const typename S::value_type& x );
00082 
00083     /**
00084      * Adds a new element at the beginning of the container.
00085      *
00086      * \param x the new element.
00087      */
00088     void push_front( const typename S::value_type& x );
00089 
00090     /**
00091      * Removes an element from the end.
00092      */
00093     void pop_back();
00094 
00095     /**
00096      * Clears the container.
00097      */
00098     void clear();
00099 
00100     /**
00101      * The size of the container.
00102      *
00103      * \return the size.
00104      *
00105      * \note: be aware that the size can change at every moment after getting the size, since the read lock got freed. Better use
00106      * access objects to lock the container and use size() on the container directly.
00107      */
00108     size_t size() const;
00109 
00110     /**
00111      * Get item at position n. Uses the [] operator of the underlying container. Please do not use this for iteration as it locks every access.
00112      * Use iterators and read/write tickets for fast iteration.
00113      *
00114      * \param n the item index
00115      *
00116      * \return reference to element at the specified position
00117      */
00118     typename S::value_type& operator[]( size_t n );
00119 
00120     /**
00121      * Get item at position n. Uses the [] operator of the underlying container. Please do not use this for iteration as it locks every access.
00122      * Use iterators and read/write tickets for fast iteration.
00123      *
00124      * \param n the item index
00125      *
00126      * \return reference to element at the specified position
00127      */
00128     const typename S::value_type& operator[]( size_t n ) const;
00129 
00130     /**
00131      * Get item at position n. Uses the at-method of the underlying container. Please do not use this for iteration as it locks every access.
00132      * Use iterators and read/write tickets for fast iteration.
00133      *
00134      * \param n the item index
00135      *
00136      * \return reference to element at the specified position
00137      */
00138     typename S::value_type& at( size_t n );
00139 
00140     /**
00141      * Get item at position n. Uses the at-method of the underlying container. Please do not use this for iteration as it locks every access.
00142      * Use iterators and read/write tickets for fast iteration.
00143      *
00144      * \param n the item index
00145      *
00146      * \return reference to element at the specified position
00147      */
00148     const typename S::value_type& at( size_t n ) const;
00149 
00150     /**
00151      * Searches and removes the specified element. If it is not found, nothing happens. It mainly is a comfortable forwarder for std::remove and
00152      * S::erase.
00153      *
00154      * \param element the element to remove
00155      */
00156     void remove( const typename S::value_type& element );
00157 
00158     /**
00159      * Erase the element at the specified position. Read your STL reference for more details.
00160      *
00161      * \param position where to erase
00162      *
00163      * \return A random access iterator pointing to the new location of the element that followed the last element erased by the function call.
00164      */
00165     typename WSharedSequenceContainer< S >::Iterator erase( typename WSharedSequenceContainer< S >::Iterator position );
00166 
00167     /**
00168      * Erase the specified range of elements. Read your STL reference for more details.
00169      *
00170      * \param first Iterators specifying a range within the vector to be removed: [first,last).
00171      * \param last Iterators specifying a range within the vector to be removed: [first,last).
00172      *
00173      * \return A random access iterator pointing to the new location of the element that followed the last element erased by the function call.
00174      */
00175     typename WSharedSequenceContainer< S >::Iterator erase( typename WSharedSequenceContainer< S >::Iterator first,
00176                                                             typename WSharedSequenceContainer< S >::Iterator last );
00177 
00178     /**
00179      * Replaces the specified old value by a new one. If the old one does not exist, nothing happens. This is a comfortable forwarder for
00180      * std::replace.
00181      *
00182      * \param oldValue the old value to replace
00183      * \param newValue the new value
00184      */
00185     void replace( const typename S::value_type& oldValue, const typename S::value_type& newValue );
00186 
00187     /**
00188      * Counts the number of occurrences of the specified value inside the container. This is a comfortable forwarder for std::count.
00189      *
00190      * \param value the value to count
00191      *
00192      * \return the number of items found.
00193      */
00194     size_t count( const value_type& value );
00195 
00196     /**
00197      * Resorts the container using the specified comparator from its begin to its end.
00198      *
00199      * \tparam Comparator the comparator type. Usually a boost::function or class providing the operator().
00200      *
00201      * \param comp the comparator
00202      */
00203     template < typename Comparator >
00204     void sort( Comparator comp );
00205 
00206     /**
00207      * Resorts the container using the specified comparator between [first,last) in ascending order.
00208      *
00209      * \param first the first element
00210      * \param last the last element
00211      * \param comp the comparator
00212      */
00213     template < typename Comparator >
00214     void sort( typename WSharedSequenceContainer< S >::Iterator first, typename WSharedSequenceContainer< S >::Iterator last, Comparator comp );
00215 
00216     /**
00217      * Resorts the container using the specified comparator from its begin to its end. Uses stable sort algorithm.
00218      *
00219      * \tparam Comparator the comparator type. Usually a boost::function or class providing the operator().
00220      *
00221      * \param comp the comparator
00222      */
00223     template < typename Comparator >
00224     void stableSort( Comparator comp );
00225 
00226     /**
00227      * Resorts the container using the specified comparator between [first,last) in ascending order. Uses stable sort algorithm.
00228      *
00229      * \param first the first element
00230      * \param last the last element
00231      * \param comp the comparator
00232      */
00233     template < typename Comparator >
00234     void stableSort( typename WSharedSequenceContainer< S >::Iterator first, typename WSharedSequenceContainer< S >::Iterator last, Comparator comp );
00235 
00236     /**
00237      * Searches the specified value in the range [first,last).
00238      *
00239      * \param first the first element
00240      * \param last the last element
00241      * \param value the value to search.
00242      *
00243      * \return the iterator pointing to the found element.
00244      */
00245     typename WSharedSequenceContainer< S >::Iterator find( typename WSharedSequenceContainer< S >::Iterator first,
00246                                                            typename WSharedSequenceContainer< S >::Iterator last,
00247                                                            const typename S::value_type& value );
00248 
00249     /**
00250      * Searches the specified value in the range [begin,end).
00251      *
00252      * \param value the value to search.
00253      *
00254      * \return the iterator pointing to the found element.
00255      */
00256     typename WSharedSequenceContainer< S >::ConstIterator find( const typename S::value_type& value );
00257 
00258 protected:
00259 private:
00260 };
00261 
00262 template < typename S >
00263 WSharedSequenceContainer< S >::WSharedSequenceContainer():
00264     WSharedObject< S >()
00265 {
00266     // init members
00267 }
00268 
00269 template < typename S >
00270 WSharedSequenceContainer< S >::~WSharedSequenceContainer()
00271 {
00272     // clean up
00273 }
00274 
00275 template < typename S >
00276 void WSharedSequenceContainer< S >::push_back( const typename S::value_type& x )
00277 {
00278     // Lock, if "a" looses focus -> look is freed
00279     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00280     a->get().push_back( x );
00281 }
00282 
00283 template < typename S >
00284 void WSharedSequenceContainer< S >::push_front( const typename S::value_type& x )
00285 {
00286     // Lock, if "a" looses focus -> look is freed
00287     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00288     a->get().insert( a->get().begin(), x );
00289 }
00290 
00291 template < typename S >
00292 void WSharedSequenceContainer< S >::pop_back()
00293 {
00294     // Lock, if "a" looses focus -> look is freed
00295     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00296     a->get().pop_back();
00297 }
00298 
00299 template < typename S >
00300 void WSharedSequenceContainer< S >::clear()
00301 {
00302     // Lock, if "a" looses focus -> look is freed
00303     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00304     a->get().clear();
00305 }
00306 
00307 template < typename S >
00308 size_t WSharedSequenceContainer< S >::size() const
00309 {
00310     // Lock, if "a" looses focus -> look is freed
00311     typename WSharedObject< S >::ReadTicket a = WSharedObject< S >::getReadTicket();
00312     size_t size = a->get().size();
00313     return size;
00314 }
00315 
00316 template < typename S >
00317 typename S::value_type& WSharedSequenceContainer< S >::operator[]( size_t n )
00318 {
00319     typename WSharedObject< S >::ReadTicket a = WSharedObject< S >::getReadTicket();
00320     return const_cast< S& >( a->get() ).operator[]( n );    // read tickets return the handled object const. This is bad here although in most cases
00321     // it is useful and needed.
00322 }
00323 
00324 template < typename S >
00325 const typename S::value_type& WSharedSequenceContainer< S >::operator[]( size_t n ) const
00326 {
00327     typename WSharedObject< S >::ReadTicket a = WSharedObject< S >::getReadTicket();
00328     return a->get().operator[]( n );
00329 }
00330 
00331 template < typename S >
00332 typename S::value_type& WSharedSequenceContainer< S >::at( size_t n )
00333 {
00334     typename WSharedObject< S >::ReadTicket a = WSharedObject< S >::getReadTicket();
00335     return const_cast< S& >( a->get() ).at( n );    // read tickets return the handled object const. This is bad here although in most cases it
00336     // is useful and needed.
00337 }
00338 
00339 template < typename S >
00340 const typename S::value_type& WSharedSequenceContainer< S >::at( size_t n ) const
00341 {
00342     typename WSharedObject< S >::ReadTicket a = WSharedObject< S >::getReadTicket();
00343     return a->get().at( n );
00344 }
00345 
00346 template < typename S >
00347 void WSharedSequenceContainer< S >::remove( const typename S::value_type& element )
00348 {
00349     // Lock, if "a" looses focus -> look is freed
00350     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00351     a->get().erase( std::remove( a->get().begin(), a->get().end(), element ), a->get().end() );
00352 }
00353 
00354 template < typename S >
00355 typename WSharedSequenceContainer< S >::Iterator WSharedSequenceContainer< S >::erase( typename WSharedSequenceContainer< S >::Iterator position )
00356 {
00357     // Lock, if "a" looses focus -> look is freed
00358     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00359     return a->get().erase( position );
00360 }
00361 
00362 template < typename S >
00363 typename WSharedSequenceContainer< S >::Iterator WSharedSequenceContainer< S >::erase(
00364         typename WSharedSequenceContainer< S >::Iterator first,
00365         typename WSharedSequenceContainer< S >::Iterator last )
00366 {
00367     // Lock, if "a" looses focus -> look is freed
00368     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00369     return a->get().erase( first, last );
00370 }
00371 
00372 template < typename S >
00373 void WSharedSequenceContainer< S >::replace( const typename S::value_type& oldValue, const typename S::value_type& newValue )
00374 {
00375     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00376     std::replace( a->get().begin(), a->get().end(), oldValue, newValue );
00377 }
00378 
00379 template < typename S >
00380 size_t WSharedSequenceContainer< S >::count( const value_type& value )
00381 {
00382     typename WSharedObject< S >::ReadTicket a = WSharedObject< S >::getReadTicket();
00383     return std::count( a->get().begin(), a->get().end(), value );
00384 }
00385 
00386 template < typename S >
00387 template < typename Comparator >
00388 void WSharedSequenceContainer< S >::sort( Comparator comp )
00389 {
00390     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00391     return std::sort( a->get().begin(), a->get().end(), comp );
00392 }
00393 
00394 template < typename S >
00395 template < typename Comparator >
00396 void WSharedSequenceContainer< S >::sort( typename WSharedSequenceContainer< S >::Iterator first,
00397                                           typename WSharedSequenceContainer< S >::Iterator last,
00398                                           Comparator comp )
00399 {
00400     return std::sort( first, last, comp );
00401 }
00402 
00403 template < typename S >
00404 template < typename Comparator >
00405 void WSharedSequenceContainer< S >::stableSort( Comparator comp )
00406 {
00407     typename WSharedObject< S >::WriteTicket a = WSharedObject< S >::getWriteTicket();
00408     return std::stable_sort( a->get().begin(), a->get().end(), comp );
00409 }
00410 
00411 template < typename S >
00412 template < typename Comparator >
00413 void WSharedSequenceContainer< S >::stableSort( typename WSharedSequenceContainer< S >::Iterator first,
00414                                                 typename WSharedSequenceContainer< S >::Iterator last,
00415                                                 Comparator comp )
00416 {
00417     return std::stable_sort( first, last, comp );
00418 }
00419 
00420 template < typename S >
00421 typename WSharedSequenceContainer< S >::Iterator WSharedSequenceContainer< S >::find(
00422         typename WSharedSequenceContainer< S >::Iterator first,
00423         typename WSharedSequenceContainer< S >::Iterator last,
00424         const typename S::value_type& value )
00425 {
00426     return std::find( first, last, value );
00427 }
00428 
00429 template < typename S >
00430 typename WSharedSequenceContainer< S >::ConstIterator WSharedSequenceContainer< S >::find( const typename S::value_type& value )
00431 {
00432     typename WSharedObject< S >::ReadTicket a = WSharedObject< S >::getReadTicket();
00433     return std::find( a->get().begin(), a->get().end(), value );
00434 }
00435 
00436 #endif  // WSHAREDSEQUENCECONTAINER_H
00437