/*
* opencog/atoms/base/Handle.h
*
* Copyright (C) 2008-2010 OpenCog Foundation
* Copyright (C) 2002-2007 Novamente LLC
* Copyright (C) 2013 Linas Vepstas <linasvepstas@gmail.com>
* All Rights Reserved
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License v3 as
* published by the Free Software Foundation and including the exceptions
* at http://opencog.org/wiki/Licenses
*
* 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 Affero General Public License
* along with this program; if not, write to:
* Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
#ifndef _OPENCOG_HANDLE_H
#define _OPENCOG_HANDLE_H
#include <iostream>
#include <climits>
#include <cstdint>
#include <functional>
#include <limits>
#include <map>
#include <memory>
#include <string>
#include <sstream>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <opencog/util/empty_string.h>
#include <opencog/atoms/atom_types/types.h>
/** \addtogroup grp_atomspace
* @{
*/
namespace opencog
{
//! ContentHash == 64-bit hash of an Atom.
typedef uint64_t ContentHash;
class Atom;
typedef std::shared_ptr<Atom> AtomPtr;
//! Pointer to an Atom, providing extra utility/convenience methods.
class Handle : public AtomPtr
{
friend class Atom;
friend class content_based_atom_ptr_less;
friend class content_based_handle_less;
private:
static bool atoms_less(const Atom*, const Atom*);
static bool content_based_atoms_less(const Atom*, const Atom*);
public:
static const ContentHash INVALID_HASH = std::numeric_limits<size_t>::max();
static const Handle UNDEFINED;
// Copy constructor
explicit Handle(const AtomPtr& atom) : AtomPtr(atom) {}
// Move constructor
explicit Handle(AtomPtr&& atom) : AtomPtr(atom) {}
explicit Handle() {}
~Handle() {}
ContentHash value(void) const;
// Copy assign operator
inline Handle& operator=(const AtomPtr& a) {
this->AtomPtr::operator=(a);
return *this;
}
// Move assign operator
inline Handle& operator=(AtomPtr&& a) {
this->AtomPtr::operator=(a);
return *this;
}
// Cython can't access operator->() so we'll duplicate here.
inline Atom* atom_ptr() {
return get();
}
inline const Atom* const_atom_ptr() const {
return get();
}
// Allows expressions like "if(h)..." to work
// when h has a non-null pointer.
explicit inline operator bool() const noexcept {
if (get()) return true;
return false;
}
inline bool operator==(std::nullptr_t) const noexcept {
return get() == nullptr;
}
inline bool operator!=(std::nullptr_t) const noexcept {
return get() != nullptr;
}
inline bool operator==(const Atom* ap) const noexcept {
return get() == ap;
}
inline bool operator!=(const Atom* ap) const noexcept {
return get() != ap;
}
inline bool operator==(const Handle& h) const noexcept {
return get() == h.get();
}
inline bool operator!=(const Handle& h) const noexcept {
return get() != h.get();
}
/**
* Defer to Atom::operator< thus is content based.
*/
bool operator< (const Handle& h) const noexcept;
/**
* Returns a negative value, zero or a positive value if the first
* argument is respectively smaller than, equal to, or larger than
* the second argument. The atom hashes are compared, so the
* comparison is content-based, and is stable, independent of the
* the address space layout.
*
* @param The first handle element.
* @param The second handle element.
* @return A negative value, zero or a positive value if the first
* argument is respectively smaller than, equal to, or larger then the
* second argument.
*/
static int compare(const Handle&, const Handle&);
};
static inline bool operator== (std::nullptr_t, const Handle& rhs) noexcept
{ return rhs == (Atom*) nullptr; }
static inline bool operator!= (std::nullptr_t, const Handle& rhs) noexcept
{ return rhs != (Atom*) nullptr; }
bool content_eq(const opencog::Handle& lh,
const opencog::Handle& rh) noexcept;
//! Boost needs this function to be called by exactly this name.
std::size_t hash_value(Handle const&);
//! a pair of Handles
typedef std::pair<Handle, Handle> HandlePair;
//! a list of handles
typedef std::vector<Handle> HandleSeq;
//! a set of lists of handles
typedef std::set<HandleSeq> HandleSeqSet;
//! a list of lists of handles
typedef std::vector<HandleSeq> HandleSeqSeq;
//! a set of handles. Default handle set container. Usually takes less
//! RAM and has faster iteration.
typedef std::set<Handle> HandleSet;
//! a set of sets of handles.
typedef std::set<HandleSet> HandleSetSet;
//! a sequence of sets of handles.
typedef std::vector<HandleSet> HandleSetSeq;
//! a hash table. Usually has faster insertion.
typedef std::unordered_set<Handle> UnorderedHandleSet;
//! an ordered map from Handle to Handle
typedef std::map<Handle, Handle> HandleMap;
//! a hash table. Usually has faster insertion.
typedef std::unordered_map<Handle, Handle> UnorderedHandleMap;
//! an ordered map from Handle to HandleSet
typedef std::map<Handle, HandleSet> HandleMultimap;
//! an ordered map from Handle to HandleSeq
typedef std::map<Handle, HandleSeq> HandleSeqMap;
//! a sequence of ordered handle maps
typedef std::vector<HandleMap> HandleMapSeq;
//! a sequence of sequences of ordered handle maps
typedef std::vector<HandleMapSeq> HandleMapSeqSeq;
//! a set of ordered handle maps
typedef std::set<HandleMap> HandleMapSet;
//! a sequence of handle pairs
typedef std::vector<HandlePair> HandlePairSeq;
// A map of variables to their groundings. Everyone working with
// groundings uses this type; changing the type here allows easy
// comparisons of performance for these two mapping styles.
// At this time (Dec 2019; gcc-8.3.0) there seems to be no difference
// in performance in the pattern matcher as a result of using the
// unordered aka std::_Hashtable variant vs the std::_Rb_tree variant.
// (as measured with the `guile -l nano-en.scm` benchmark.)
typedef HandleMap GroundingMap;
// typedef UnorderedHandleMap GroundingMap;
typedef std::vector<GroundingMap> GroundingMapSeq;
typedef std::vector<GroundingMapSeq> GroundingMapSeqSeq;
bool content_eq(const opencog::HandleSeq& lhs,
const opencog::HandleSeq& rhs);
bool content_eq(const opencog::HandleSet& lhs,
const opencog::HandleSet& rhs);
bool content_eq(const opencog::HandleSetSeq& lhs,
const opencog::HandleSetSeq& rhs);
//! Check if hs contains h using content_eq as equality. hs is not
//! assumed to be sorted, thus the complexity is up to linear with the
//! size hs.
bool content_contains(const opencog::HandleSeq& hs, const opencog::Handle& h);
struct content_based_atom_ptr_less
{
bool operator()(const Atom* al, const Atom* ar) const
{
return Handle::content_based_atoms_less(al, ar);
}
};
struct content_based_handle_less
{
bool operator()(const Handle& hl, const Handle& hr) const
{
return Handle::content_based_atoms_less(hl.const_atom_ptr(),
hr.const_atom_ptr());
}
};
//! Content based HandleSet less than operator
struct handle_seq_less
{
bool operator()(const HandleSeq& hsl, const HandleSeq& hsr) const
{
size_t sl = hsl.size();
size_t sr = hsr.size();
if (sl != sr) return sl < sr;
for (size_t i=0; i<sl; i++)
{
if (hsl[i] != hsl[i]) return hsl[i].operator<(hsr[i]);
}
return false;
}
};
//! Content based HandleSet pointer less than operator
struct handle_seq_ptr_less
{
bool operator()(const HandleSeq* hsl, const HandleSeq* hsr) const
{
return handle_seq_less().operator()(*hsl, *hsr);
}
};
//! append string representation of the Hash to the string
static inline std::string operator+ (const char *lhs, Handle h)
{
std::string rhs = lhs;
char buff[25];
// The cast to (unsigned long long) is for 32-bit arches
snprintf(buff, 24, "%llu)", (unsigned long long) h.value());
return rhs + buff;
}
//! append string representation of the Hash to the string
static inline std::string operator+ (const std::string &lhs, Handle h)
{
char buff[25];
// The cast to (unsigned long long) is for 32-bit arches
snprintf(buff, 24, "%llu)", (unsigned long long) h.value());
return lhs + buff;
}
// Debugging helpers see
// http://wiki.opencog.org/w/Development_standards#Print_OpenCog_Objects
#define OC_TO_STRING_INDENT " "
std::string oc_to_string(const Handle& h,
const std::string& indent=empty_string);
std::string oc_to_string(const HandlePair& hp,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleSeq& hs,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleSeqSeq& hss,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleSet& ohs,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleSetSet& ohss,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleSetSeq& ohss,
const std::string& indent=empty_string);
std::string oc_to_string(const UnorderedHandleSet& uhs,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleMap& hm,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleMap::value_type& hmv,
const std::string& indent=empty_string);
std::string oc_to_string(const UnorderedHandleMap& hm,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleMultimap& hmm,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleSeqMap& hsm,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleMapSeq& hms,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleMapSeqSeq& hmss,
const std::string& indent=empty_string);
std::string oc_to_string(const HandleMapSet& hms,
const std::string& indent=empty_string);
std::string oc_to_string(const HandlePairSeq& hps,
const std::string& indent=empty_string);
std::string oc_to_string(Type type,
const std::string& indent=empty_string);
std::string oc_to_string(const TypeSet& types,
const std::string& indent=empty_string);
} // namespace opencog
namespace std {
ostream& operator<<(ostream&, const opencog::HandleMap&);
ostream& operator<<(ostream&, const opencog::HandleSeq&);
ostream& operator<<(ostream&, const opencog::HandleSet&);
ostream& operator<<(ostream&, const opencog::UnorderedHandleSet&);
ostream& operator<<(ostream&, const opencog::UnorderedHandleMap&);
// Hash, needed for std::unordered_map
template<>
struct hash<opencog::Handle>
{
typedef std::size_t result_type;
typedef opencog::Handle argument_type;
std::size_t operator()(const opencog::Handle& h) const noexcept
{ return hash_value(h); }
#if HAVE_SPARSEHASH
// SparseHash want to have a void ctor. So provide that.
// This is kind of weird, so we don't provide it by default.
std::size_t operator()(void) const noexcept
{ return 0; }
#endif // HAVE_SPARSEHASH
};
// content-based equality
template<>
struct equal_to<opencog::Handle>
{
typedef bool result_type;
typedef opencog::Handle first_argument;
typedef opencog::Handle second_argument;
bool
operator()(const opencog::Handle& lh,
const opencog::Handle& rh) const noexcept
{
if (lh == rh) return true;
if (nullptr == lh or nullptr == rh) return false;
return opencog::content_eq(lh, rh);
}
};
template<>
struct hash<opencog::HandlePair>
{
typedef std::size_t result_type;
typedef opencog::HandlePair argument_type;
std::size_t
operator()(const opencog::HandlePair& hp) const noexcept
{ return hash_value(hp.first) + hash_value(hp.second); }
};
// content-based equality
template<>
struct equal_to<opencog::HandlePair>
{
typedef bool result_type;
typedef opencog::HandlePair first_argument;
typedef opencog::HandlePair second_argument;
bool
operator()(const opencog::HandlePair& lhp,
const opencog::HandlePair& rhp) const noexcept
{
if (lhp == rhp) return true;
std::equal_to<opencog::Handle> eq;
return eq.operator()(lhp.first, rhp.first) and
eq.operator()(lhp.second, rhp.second);
}
};
template<>
struct hash<opencog::HandleSeq>
{
typedef std::size_t result_type;
typedef opencog::HandleSeq argument_type;
std::size_t
operator()(const opencog::HandleSeq& hseq) const noexcept
{
std::size_t hsh = 0;
for (const opencog::Handle& h : hseq) hsh += hash_value(h);
return hsh;
}
};
// content-based equality
template<>
struct equal_to<opencog::HandleSeq>
{
typedef bool result_type;
typedef opencog::HandleSeq first_argument;
typedef opencog::HandleSeq second_argument;
bool
operator()(const opencog::HandleSeq& lhs,
const opencog::HandleSeq& rhs) const noexcept
{
if (lhs == rhs) return true;
size_t len = lhs.size();
if (rhs.size() != len) return false;
std::equal_to<opencog::Handle> eq;
for (size_t i=0; i<len; i++)
{
if (not eq.operator()(lhs[i], rhs[i])) return false;
}
return true;
}
};
} // ~namespace std
/** @}*/
#endif // _OPENCOG_HANDLE_H