UniqueContainer.h

Go to the documentation of this file.

// Copyright 2015 Sensics, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//  http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef INCLUDED_PassthruUniqueContainer_h_GUID_AD5E86CA_230D_4BBA_8DF0_F2C3811CFD00
#define INCLUDED_PassthruUniqueContainer_h_GUID_AD5E86CA_230D_4BBA_8DF0_F2C3811CFD00

// Internal Includes
#include <osvr/Util/ContainerWrapper.h>

// Library/third-party includes
// - none

// Standard includes
#include <algorithm>
#include <functional>

namespace osvr {
namespace util {
    namespace unique_container_policies {
        struct PushBack {
            template <typename Container> struct Specialized {
                using policy = Specialized<Container>;
                using iterator = typename Container::iterator;
                using const_iterator = typename Container::const_iterator;
                using value_type = typename Container::value_type;
                using reference = typename Container::reference;
                using rv_reference = typename Container::value_type &&;
                using const_reference = typename Container::const_reference;
                static bool contains(Container const &c, const_reference v) {
                    return policy::find(c, v) != end(c);
                }

                static bool remove(Container &c, const_reference v) {
                    auto it = policy::find(c, v);
                    if (end(c) != it) {
                        c.erase(it);
                        return true;
                    }
                    return false;
                }

                static bool insert(Container &c, const_reference v) {
                    if (!policy::contains(c, v)) {
                        c.push_back(v);
                        return true;
                    }
                    return false;
                }

                static bool insert(Container &c, rv_reference v) {
                    if (!policy::contains(c, v)) {
                        c.emplace_back(v); // move-construct
                        return true;
                    }
                    return false;
                }

                static auto find(Container const &c, const_reference v)
                    -> decltype(std::find(begin(c), end(c), v)) {
                    return std::find(begin(c), end(c), v);
                }

                static auto find(Container &c, const_reference v)
                    -> decltype(std::find(begin(c), end(c), v)) {
                    return std::find(begin(c), end(c), v);
                }
            };
        };

        template <template <class X> class Comparison = std::less>
        struct SortedInsert {
            template <typename Container> struct Specialized {
                using policy = Specialized<Container>;
                using iterator = typename Container::iterator;
                using const_iterator = typename Container::const_iterator;
                using value_type = typename Container::value_type;
                using reference = typename Container::reference;
                using rv_reference = typename Container::value_type &&;
                using const_reference = typename Container::const_reference;
                using comparator = Comparison<value_type>;

                static comparator get_comparator() { return comparator{}; }

                static auto lower_bound(Container &c, const_reference v)
                    -> decltype(std::lower_bound(begin(c), end(c), v,
                                                 policy::get_comparator())) {
                    return std::lower_bound(begin(c), end(c), v,
                                            policy::get_comparator());
                }

                static auto lower_bound(Container const &c, const_reference v)
                    -> decltype(std::lower_bound(begin(c), end(c), v,
                                                 policy::get_comparator())) {
                    return std::lower_bound(begin(c), end(c), v,
                                            policy::get_comparator());
                }

                static bool contains(Container const &c, const_reference v) {
                    return std::binary_search(begin(c), end(c), v,
                                              policy::get_comparator());
                }

                static bool remove(Container &c, const_reference v) {
                    auto it = policy::find(c, v);
                    if (end(c) != it) {
                        c.erase(it);
                        return true;
                    }
                    return false;
                }

                static bool insert(Container &c, const_reference v) {
                    auto it = policy::lower_bound(c, v);
                    if (!policy::iter_indicates_contains(c, it, v)) {
                        c.insert(it, v);
                        return true;
                    }
                    return false;
                }

                static bool insert(Container &c, rv_reference v) {
                    auto it = policy::lower_bound(c, v);
                    if (!policy::iter_indicates_contains(c, it, v)) {
                        c.emplace(it, v); // move-construct
                        return true;
                    }
                    return false;
                }

                static auto find(Container const &c, const_reference v)
                    -> decltype(policy::lower_bound(c, v)) {
                    auto it = policy::lower_bound(c, v);
                    return policy::iter_indicates_contains(c, it, v) ? it
                                                                     : end(c);
                }

                static auto find(Container &c, const_reference v)
                    -> decltype(policy::lower_bound(c, v)) {
                    auto it = policy::lower_bound(c, v);
                    return policy::iter_indicates_contains(c, it, v) ? it
                                                                     : end(c);
                }

                static bool check_equiv(const_reference a, const_reference b) {
                    auto comp = policy::get_comparator();
                    return !(comp(a, b)) && !(comp(b, a));
                }

                template <typename IteratorType>
                static bool iter_indicates_contains(Container const &c,
                                                    IteratorType const &it,
                                                    const_reference v) {
                    if (end(c) == it) {
                        return false;
                    }
                    return check_equiv(*it, v);
                }

                static void sort(Container &c) {
                    std::sort(begin(c), end(c), policy::get_comparator());
                }
            };
        };
#if 0
        struct SortedInsert {
            template <typename Container>
            using Specialized = SortedInsertCustomCompare<
                std::less>::template Specialized<Container>;
        };
#endif
    } // namespace unique_container_policies

    template <typename Container,
              typename Policy = unique_container_policies::PushBack,
              typename... WrapperArgs>
    class UniqueContainerBase
        : public ContainerWrapper<Container, WrapperArgs...> {
        typedef typename Policy::template Specialized<Container> policy;
        typedef ContainerWrapper<Container, WrapperArgs...> base;

      protected:
        using value_type = typename Container::value_type;
        using reference = typename Container::reference;
        using rv_reference = typename Container::value_type &&;
        using const_reference = typename Container::const_reference;
        bool contains(const_reference v) {
            return policy::contains(container(), v);
        }
        bool insert(const_reference v) {
            return policy::insert(container(), v);
        }
        bool insert(rv_reference v) { return policy::insert(container(), v); }
        bool remove(const_reference v) {
            return policy::remove(container(), v);
        }

        Container const &container() const { return base::container(); }

      private:
        Container &container() { return base::container(); }
    };

    template <typename Container,
              typename Policy = unique_container_policies::PushBack,
              typename... WrapperArgs>
    class UniqueContainer
        : public UniqueContainerBase<Container, Policy, WrapperArgs...> {
        typedef UniqueContainerBase<Container, Policy, WrapperArgs...> base;

      public:
        using rv_reference = typename Container::value_type &&;
        using const_reference = typename Container::const_reference;
        bool contains(const_reference v) { return base::contains(v); }
        bool insert(const_reference v) { return base::insert(v); }
        bool insert(rv_reference v) { return base::insert(v); }
        bool remove(const_reference v) { return base::remove(v); }

        Container const &container() const { return base::container(); }
    };

} // namespace util
} // namespace osvr
#endif // INCLUDED_PassthruUniqueContainer_h_GUID_AD5E86CA_230D_4BBA_8DF0_F2C3811CFD00