Comparator.h

Go to the documentation of this file.

//
// Copyright (C) 2008 Institut fuer Telematik, Universitaet Karlsruhe (TH)
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//

#ifndef __COMPARATOR_H
#define __COMPARATOR_H

#include <OverlayKey.h>
#include <ProxNodeHandle.h>

template<class T>
class Comparator
{
public:
    virtual ~Comparator()
    {}

    virtual int compare( const T& lhs, const T& rhs ) const
    {
        return lhs.compareTo(rhs);
    }
};

//class KeyComparator : public Comparator<OverlayKey>
//{
//    //...
//};
typedef Comparator<OverlayKey> KeyComparator; //TODO needed?

class KeyStdMetric
{
public:
    inline OverlayKey distance(const OverlayKey& x,
                               const OverlayKey& y) const
    {
        return x > y ? (x-y) : (y-x);
    }
};

class KeyXorMetric
{
public:
    inline OverlayKey distance(const OverlayKey& x,
                               const OverlayKey& y) const
    {
        return x^y;
    }
};


class KeyRingMetric
{
public:
    static inline OverlayKey distance(const OverlayKey& x,
                               const OverlayKey& y)
    {
        OverlayKey dist1(x - y);
        OverlayKey dist2(y - x);

        if (dist1 > dist2)
            return dist2;
        else
            return dist1;
    }
};


class KeyCwRingMetric
{
public:
    inline OverlayKey distance(const OverlayKey& x,
                               const OverlayKey& y) const
    {
        return y-x;
    }
};

class KeyCcwRingMetric
{
public:
    inline OverlayKey distance(const OverlayKey& x,
                               const OverlayKey& y) const
    {
        return x-y;
    }
};



class KeyPrefixMetric
{
public:
    KeyPrefixMetric()
    {
        bitsPerDigit = 1;
    }

    inline OverlayKey distance(const OverlayKey& x,
                               const OverlayKey& y) const
    {
        return OverlayKey::getLength() / bitsPerDigit
               - x.sharedPrefixLength(y, bitsPerDigit);
    }

    inline void setBitsPerDigit(uint8_t bitsPerDigit)
    {
        this->bitsPerDigit = bitsPerDigit;
    }

private:
    uint8_t bitsPerDigit;
};

template<class Metric = KeyStdMetric>
class KeyDistanceComparator : public Comparator<OverlayKey>
{
private:
    Metric m; 
    OverlayKey key; 
public:

    KeyDistanceComparator( const OverlayKey& relativeKey )
    {
        this->key = relativeKey;
    }

    int compare( const OverlayKey& lhs, const OverlayKey& rhs ) const
    {
        return m.distance(lhs, key).compareTo(m.distance(rhs, key));
    }
};

template<>
class KeyDistanceComparator<KeyPrefixMetric> : public Comparator<OverlayKey>
{
private:
    KeyPrefixMetric m; 
    OverlayKey key; 
public:

    KeyDistanceComparator(const OverlayKey& relativeKey, uint32_t bitsPerDigit = 1)
    {
        key = relativeKey;
        m.setBitsPerDigit(bitsPerDigit);
    }
    int compare( const OverlayKey& lhs, const OverlayKey& rhs ) const
    {
        return m.distance(lhs, key).compareTo(m.distance(rhs, key));
    }
};

class AbstractProxComparator
{
  public:
    virtual ~AbstractProxComparator() {};

    virtual int compare(const Prox& lhs, const Prox& rhs) const = 0;
};

class StdProxComparator : public AbstractProxComparator
{
  public:
    int compare(const Prox& lhs, const Prox& rhs) const
    {
        // return 0 if accuracy is too low
        if (lhs.accuracy < 0.5 || rhs.accuracy < 0.5) return 0;

        if (lhs.proximity < rhs.proximity) return -1;
        if (lhs.proximity > rhs.proximity) return 1;
        return 0;
    }
};

class AbstractProxKeyComparator
{
  public:
      virtual ~AbstractProxKeyComparator() {};

    virtual int compare(const ProxKey& lhs, const ProxKey& rhs) const = 0;
};

template<class Metric, class ProxComp = StdProxComparator>
class ProxKeyComparator : public AbstractProxKeyComparator
{
  protected:
    Metric m; 
    ProxComp pc;
    OverlayKey key; 
  public:
    ProxKeyComparator(const OverlayKey& relativeKey)
    {
        this->key = relativeKey;
    }
};


template<>
class ProxKeyComparator<KeyPrefixMetric> : public AbstractProxKeyComparator
{
  protected:
    KeyPrefixMetric m; 
    StdProxComparator pc;
    OverlayKey key; 
  public:
    ProxKeyComparator(const OverlayKey& relativeKey, uint32_t bitsPerDigit = 1)
    {
        this->key = relativeKey;
        m.setBitsPerDigit(bitsPerDigit);
    }
};

class KademliaPRComparator : public ProxKeyComparator<KeyPrefixMetric>
{
  public:
    KademliaPRComparator(const OverlayKey& relativeKey, uint32_t bitsPerDigit = 1)
    : ProxKeyComparator<KeyPrefixMetric, StdProxComparator>(relativeKey, bitsPerDigit) { }

    int compare(const ProxKey& lhs, const ProxKey& rhs) const
    {
        int temp = m.distance(lhs.key, key).compareTo(m.distance(rhs.key, key));
        if (temp != 0) {
            return temp;
        }
        return pc.compare(lhs.prox, rhs.prox);
    }
};

class AccordionPRComparator : public ProxKeyComparator<KeyPrefixMetric>
{
  public:
    AccordionPRComparator(const OverlayKey& relativeKey, uint32_t bitsPerDigit = 1)
    : ProxKeyComparator<KeyPrefixMetric, StdProxComparator>(relativeKey, bitsPerDigit) { }

    int compare(const ProxKey& lhs, const ProxKey& rhs) const
    {
        int temp = m.distance(lhs.key, key).compareTo(m.distance(rhs.key, key));
        if (temp != 0) {
            return temp;
        }
        return pc.compare(lhs.prox, rhs.prox);
    }
};
#endif