plonk_Collections.h

/*
 -------------------------------------------------------------------------------
 This file is part of the Plink, Plonk, Plank libraries
  by Martin Robinson
 
 http://code.google.com/p/pl-nk/
 
 Copyright University of the West of England, Bristol 2011-14
 All rights reserved.
 
 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are met:
 
 * Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
 * Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
 * Neither the name of University of the West of England, Bristol nor 
   the names of its contributors may be used to endorse or promote products
   derived from this software without specific prior written permission.
 
 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
 DISCLAIMED. IN NO EVENT SHALL UNIVERSITY OF THE WEST OF ENGLAND, BRISTOL BE 
 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 
 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 
 OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 
 This software makes use of third party libraries. For more information see:
 doc/license.txt included in the distribution.
 -------------------------------------------------------------------------------
 */

#ifndef PLONK_COLLECTIONS_H
#define PLONK_COLLECTIONS_H

#include "../core/plonk_CoreForwardDeclarations.h"
#include "plonk_ContainerForwardDeclarations.h"
#include "plonk_DynamicContainer.h"

#include "../core/plonk_SmartPointer.h"
#include "../core/plonk_WeakPointer.h"
#include "../core/plonk_Thread.h"
#include "plonk_ObjectArray.h"
#include "plonk_SimpleArray.h"


template<class ValueType, class KeyType>
class DictionaryInternal : public SmartPointer
{
public:
    typedef Dictionary<ValueType,KeyType> Container;
    
        DictionaryInternal() throw()
        {
        }
        
    DictionaryInternal (const int initialCapacity) throw()
    :   values (ObjectArray<ValueType>::emptyWithAllocatedSize (initialCapacity)),
        keys (ObjectArray<KeyType>::emptyWithAllocatedSize (initialCapacity))
        {
        }
    
        ~DictionaryInternal()
        {
        }
        
        ObjectArray<ValueType>& getValues() throw()
        {
                return values;
        }
        
        ObjectArray<KeyType>& getKeys() throw()
        {
                return keys;
        }
        
        const ObjectArray<ValueType>& getValues() const throw()
        {
                return values;
        }
        
        const ObjectArray<KeyType>& getKeys() const throw()
        {
                return keys;
        }
        
private:
        ObjectArray<ValueType> values;
        ObjectArray<KeyType> keys;
};


//------------------------------------------------------------------------------

template<class ValueType, class KeyType>
class KeyValuePair
{
public:
        KeyValuePair() throw()
        {
        }
        
        KeyValuePair (KeyType const& key, ValueType const& value) throw()
        :       v (value), 
        k (key)
        {
        }
    
    KeyValuePair (KeyValuePair const& copy) throw()
    :   v (copy.v),
        k (copy.k)
    {
    }
    
    KeyValuePair operator= (KeyValuePair const& other) throw()
    {
        if (this != &other)
        {
            v = other.v;
            k = other.k;
        }
        
        return *this;
    }
        
        const KeyType& getKey() const throw() { return k; }
        const ValueType& getValue() const throw() { return v; }
        
private:
        ValueType v;
        KeyType k;
};


//------------------------------------------------------------------------------


template<class ValueType, class KeyType>
class Dictionary : public SmartPointerContainer< DictionaryInternal<ValueType,KeyType> >
{
public:
        typedef KeyValuePair<ValueType,KeyType>         KeyValuePairType;
        typedef ObjectArray<KeyValuePairType>           KeyValuePairArrayType;

    typedef DictionaryInternal<ValueType,KeyType>   Internal;
    typedef SmartPointerContainer<Internal>         Base;
    typedef WeakPointerContainer<Dictionary>        Weak;    
    
        Dictionary() throw()
        :       Base (new Internal())
        {
        }
        
    explicit Dictionary (const int initialCapacity) throw()
        :       Base (new Internal (initialCapacity))
        {
        }
    
    explicit Dictionary (Internal* internalToUse) throw() 
        :       Base (internalToUse)
        {
        } 
    
    Dictionary (Dictionary const& copy) throw()
        :       Base (static_cast<Base const&> (copy))
        {
        }        
    
    Dictionary (Dynamic const& other) throw()
    :   Base (other.as<Dictionary>().getInternal())
    {
    }    
    
    Dictionary& operator= (Dictionary const& other) throw()
        {
                if (this != &other)
            this->setInternal (other.getInternal());//this->setInternal (other.containerCopy().getInternal());
        
        return *this;
        }
    
    static Dictionary fromWeak (Weak const& weak) throw()
    {
        return weak.fromWeak();
    }    

    static const Dictionary& getNull() throw()
        {
                static Dictionary null;
                return null;
        }                                       
    
        Dictionary (KeyValuePairArrayType const& pairs) throw()
        :       Base (new Internal())
        {
                put (pairs);
        }
    
        const ObjectArray<ValueType>& getValues() const throw()
        { 
                return this->getInternal()->getValues(); 
        }
        
        const ObjectArray<KeyType>& getKeys() const throw()
        {
                return this->getInternal()->getKeys(); 
        }

        KeyValuePairArrayType getPairs() const throw()
        {
                KeyValuePairArrayType pairs = KeyValuePairArrayType::withSize (length());
                
                for (int i = 0; i < length(); ++i)
                        pairs[i] = KeyValuePairType (key (i), value (i));
                
                return pairs;
        }
        
        ValueType put (KeyType const& key, ValueType const& value) throw()
        {
                ObjectArray<ValueType>& values = this->getInternal()->getValues();
                ObjectArray<KeyType>& keys = this->getInternal()->getKeys();

                int index = keys.indexOf (key);
                
                if (index >= 0)
                {
                        ValueType oldValue = values[index];
                        values.put (index, value);
                        return oldValue;
                }
                else
                {
                        keys.add (key);
                        values.add (value);
                        return ObjectArray<ValueType>::getNullObject();
                }
        }
        
        ValueType put (KeyValuePairType const& pair) throw()
        {
                return put (pair.getKey(), pair.getValue());
        }
        
        void put (KeyValuePairArrayType const& pairs) throw()
        {
                for (int i = 0; i < pairs.length(); ++i)
                        put (pairs[i]);
        }
        
    bool containsKey (KeyType const& key) throw()
        {
                return this->getInternal()->getKeys().contains (key);
        }

    bool containsValue (ValueType const& value) throw()
        {
                return this->getInternal()->getValues().contains (value);
        }
    
        ValueType& at (KeyType const& key) throw()
        {
                ObjectArray<ValueType>& values = this->getInternal()->getValues();
                ObjectArray<KeyType>& keys = this->getInternal()->getKeys();
                
                const int index = keys.indexOf (key);
                return values[index];
        }
        
        const ValueType& at (KeyType const& key) const throw()
        {
                ObjectArray<ValueType> const& values = getValues();
                ObjectArray<KeyType> const& keys = getKeys();
                
                const int index = keys.indexOf (key);
                return values[index];
        }
        
    ValueType& atIndex (const int index) throw()
        {
                ObjectArray<ValueType>& values = this->getInternal()->getValues();              
                return values[index];
        }    
    
    const ValueType& atIndex (const int index) const throw()
        {
                ObjectArray<ValueType> const& values = getValues();             
                return values[index];
        }
    
    ValueType& atIndexUnchecked (const int index) throw()
        {
                ObjectArray<ValueType>& values = this->getInternal()->getValues();              
                return values.atUnchecked (index);
        }    
    
    const ValueType& atIndexUnchecked (const int index) const throw()
        {
                ObjectArray<ValueType> const& values = getValues();             
                return values.atUnchecked (index);
        }
    
        ValueType& operator[] (KeyType const& key) throw()
        {
                ObjectArray<ValueType>& values = this->getInternal()->getValues();
                ObjectArray<KeyType>& keys = this->getInternal()->getKeys();
                
                const int index = keys.indexOf (key);
                return values[index];
        }
        
        const ValueType& operator[] (KeyType const& key) const throw()
        {
                ObjectArray<ValueType> const& values = getValues();
                ObjectArray<KeyType> const& keys = getKeys();
                
                const int index = keys.indexOf (key);
                return values[index];
        }
        
        ValueType remove (KeyType const& key) throw()
        {
                ObjectArray<ValueType>& values = this->getInternal()->getValues();
                ObjectArray<KeyType>& keys = this->getInternal()->getKeys();
                
                const int index = keys.indexOf (key);
                
                if (index >= 0)
                {
                        ValueType removed = values[index];
                        keys.remove (index);
                        values.remove (index);
                        return removed;
                }
                else
                {
                        return ObjectArray<ValueType>::getNullObject();
                }
        }

        const KeyType& keyForValue (ValueType const& value) const
        {
                ObjectArray<ValueType> const& values = getValues();
                ObjectArray<KeyType> const& keys = getKeys();
                
                const int index = values.indexOf (value);
                return keys[index];
        }
        
        KeyType& key (const int index) throw()
        {
                return getKeys()[index];
        }
        
        ValueType& value (const int index) throw()
        {
                return getValues()[index];
        }
        
        const KeyType& key (const int index) const throw()
        {
                return getKeys()[index];
        }
        
        const ValueType& value (const int index) const throw()
        {
                return getValues()[index];
        }
        
        int length() const throw()
        {
                ObjectArray<ValueType> const& values = getValues();
                
                plonk_assert (values.length() == getKeys().length()); // these should be the same length!
                
                return values.length();
        }
        
        int size() const throw()
        {
                ObjectArray<ValueType> const& values = getValues();
                ObjectArray<KeyType> const& keys = getKeys();
                
                plonk_assert (values.size() == keys.size()); // these should be the same size!
                
                return values.size();
        }
    
    PLONK_OBJECTARROWOPERATOR(Dictionary);

};


// The SmartPointerContainer and ScopedPointerContainer are thread-safe in terms
// of copying the object but not actions on the object. This class holds another
// container object and ensures thread-safe manipulations on the object. 
// The container must respond to the -> operator and implement copy() which
// should return a deep object of the object. */
//
//template<class Container>
//class ThreadSafeAccess
//{
//public:
//    typedef typename Container::Internal ContainerInternal;
//
//    ThreadSafeAccess() throw()
//    {
//    }
//    
//    ~ThreadSafeAccess()
//    {
//    }
//    
//    explicit ThreadSafeAccess (Container const& initialValue) throw()
//    :   read (initialValue.copy()), 
//        write (initialValue.copy())
//    {        
//    }
//    
//    const Container& getRead() throw() 
//    { 
//        return read;
//    }
//    
//    bool checkout() throw()
//    {
//        const Threading::ID threadID = Threading::getCurrentThreadID();
//        
//        if (writingThread.compareAndSwap (0, threadID))
//        {
//            write = read.copy();
//            return true;
//        }
//        
//        return false;
//    }
//        
//    bool commit() throw()
//    {
//        const Threading::ID threadID = Threading::getCurrentThreadID();
//
//        if (writingThread == threadID)
//        {
//            read.swapWith (write);
//            writingThread = 0;
//            return true;
//        }
//        
//        return false;
//    }
//    
//    Container operator->() throw() 
//    {   
//        plonk_assert (writingThread == Threading::getCurrentThreadID());
//        return write;
//    }
//    
//    const Container& operator*() const throw() 
//    {   
//        return read;
//    }
//
//
//    
//private:
//    Container read;
//    Container write;
//    AtomicValue<Threading::ID> writingThread;
//};

//template<class Container, int NumThreads>
//class ThreadSafeAccess
//{
//public:
//    typedef typename Container::Internal ContainerInternal;
//    typedef ObjectArray<Container> Containers;
//    typedef AtomicValue<Threading::ID> AtomicThreadID;
//    typedef ObjectArray<AtomicThreadID> Threads;
//    
//    ThreadSafeAccess() throw()
//    :   containers (Containers::withSize (NumThreads)),
//        threads (Threads::withSize (NumThreads))
//    {
//        clearThreads();
//        threads.atUnchecked (0) = Threading::getCurrentThreadID();
//    }
//    
//    ~ThreadSafeAccess()
//    {
//    }
//    
//    explicit ThreadSafeAccess (Container const& initialValue) throw()
//    :   containers (Containers::withSize (NumThreads)),
//        threads (Threads::withSize (NumThreads))
//    {        
//        for (int i = 0; i < NumThreads; ++i)
//            containers.atUnchecked (i) = initialValue.copy();
//        
//        clearThreads();
//        threads.atUnchecked (0) = Threading::getCurrentThreadID();
//    }
//    
//    Container operator->() throw() 
//    { 
//        const Threading::ID threadID = Threading::getCurrentThreadID();
//        
//        if (threads.contains (threadID))
//        {
//            return containers.atUnchecked (threads.indexOf (threadID));
//        }
//        else 
//        {
//            AtomicThreadID* const ids = threads.getArray();
//            
//            for (int i = 0; i < NumThreads; ++i)
//                if (ids[i].compareAndSwap (0, threadID))
//                    return containers.atUnchecked (i);
//        }
//        
//        plonk_assertfalse; // too many threads trying to access the data
//        return Container::getNull();
//    }
//    
//    void releaseThread() throw()
//    {
//        const Threading::ID threadID = Threading::getCurrentThreadID();
//        AtomicThreadID* const ids = threads.getArray();
//
//        for (int i = 0; i < NumThreads; ++i)
//            if (ids[i].compareAndSwap (threadID, 0))
//                return;
//    }
//    
//private:
//    Containers containers;
//    Threads threads;
//    
//    void clearThreads() throw()
//    {
//        for (int i = 0; i < NumThreads; ++i)
//            threads.atUnchecked (i) = 0;
//    }
//};



#endif // PLONK_COLLECTIONS_H