From e26434979adc33bd949566ba7bf02dff64e80a3e Mon Sep 17 00:00:00 2001 From: Chris Dyer Date: Tue, 2 Oct 2012 00:19:43 -0400 Subject: cdec cleanup, remove bayesian stuff, parsing stuff --- gi/pyp-topics/src/utility.h | 962 -------------------------------------------- 1 file changed, 962 deletions(-) delete mode 100644 gi/pyp-topics/src/utility.h (limited to 'gi/pyp-topics/src/utility.h') diff --git a/gi/pyp-topics/src/utility.h b/gi/pyp-topics/src/utility.h deleted file mode 100644 index 405a5b0a..00000000 --- a/gi/pyp-topics/src/utility.h +++ /dev/null @@ -1,962 +0,0 @@ -// utility.h -// -// (c) Mark Johnson, 24th January 2005 -// -// modified 6th May 2002 to ensure write/read consistency, fixed 18th July 2002 -// modified 14th July 2002 to include insert() (generic inserter) -// modified 26th September 2003 to use mapped_type instead of data_type -// 25th August 2004 added istream >> const char* -// 24th January 2005 added insert_newkey() -// -// Defines: -// loop macros foreach, cforeach -// dfind (default find function) -// afind (find function that asserts key exists) -// insert_newkey (inserts a new key into a map) -// insert (generic inserter into standard data structures) -// disjoint (set operation) -// first_lessthan and second_lessthan (compares elements of pairs) -// -// Simplified interfaces to STL routines: -// -// includes (simplified interface) -// set_intersection (simplified interface) -// inserter (simplified interface) -// max_element (simplified interface) -// min_element (simplified interface) -// hash functions for pairs, vectors, lists, slists and maps -// input and output for pairs and vectors -// resource_usage (interface improved) - - -#ifndef UTILITY_H -#define UTILITY_H - -#include -// #include // Comment out this line if boost is not used -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#if (__GNUC__ > 3) || (__GNUC__ >= 3 && __GNUC_MINOR__ >= 1) -#define EXT_NAMESPACE __gnu_cxx -#else -#define EXT_NAMESPACE std -#endif - -namespace ext = EXT_NAMESPACE; - -inline float power(float x, float y) { return powf(x, y); } -inline double power(double x, double y) { return pow(x, y); } -inline long double power(long double x, long double y) { return powl(x, y); } - -typedef unsigned U; -typedef long double F; // slower than double, but underflows less - -/////////////////////////////////////////////////////////////////////////// -// // -// Looping constructs // -// // -/////////////////////////////////////////////////////////////////////////// - -// foreach is a simple loop construct -// -// STORE should be an STL container -// TYPE is the typename of STORE -// VAR will be defined as a local variable of type TYPE::iterator -// -#define foreach(TYPE, VAR, STORE) \ - for (TYPE::iterator VAR = (STORE).begin(); VAR != (STORE).end(); ++VAR) - -// cforeach is just like foreach, except that VAR is a const_iterator -// -// STORE should be an STL container -// TYPE is the typename of STORE -// VAR will be defined as a local variable of type TYPE::const_iterator -// -#define cforeach(TYPE, VAR, STORE) \ - for (TYPE::const_iterator VAR = (STORE).begin(); VAR != (STORE).end(); ++VAR) - - -/////////////////////////////////////////////////////////////////////////// -// // -// Map searching // -// // -// dfind(map, key) returns the key's value in map, or map's default // -// value if no such key exists (the default value is not inserted) // -// // -// afind(map, key) returns a reference to the key's value in map, and // -// asserts that this value exists // -// // -/////////////////////////////////////////////////////////////////////////// - -// dfind(Map, Key) returns the value Map associates with Key, or the -// Map's default value if no such Key exists -// -template -inline typename Map::mapped_type dfind(Map& m, const Key& k) -{ - typename Map::iterator i = m.find(k); - if (i == m.end()) - return typename Map::mapped_type(); - else - return i->second; -} - -template -inline const typename Map::mapped_type dfind(const Map& m, const Key& k) -{ - typename Map::const_iterator i = m.find(k); - if (i == m.end()) - return typename Map::mapped_type(); - else - return i->second; -} - - -// afind(map, key) returns a reference to the value associated -// with key in map. It uses assert to check that the key's value -// is defined. -// -template -inline typename Map::mapped_type& afind(Map& m, const Key& k) -{ - typename Map::iterator i = m.find(k); - assert(i != m.end()); - return i->second; -} - -template -inline const typename Map::mapped_type& afind(const Map& m, const Key& k) -{ - typename Map::const_iterator i = m.find(k); - assert(i != m.end()); - return i->second; -} - -//! insert_newkey(map, key, value) checks that map does not contain -//! key, and binds key to value. -// -template -inline typename Map::value_type& -insert_newkey(Map& m, const Key& k,const Value& v) -{ - std::pair itb - = m.insert(Map::value_type(k, v)); - assert(itb.second); - return *(itb.first); -} // insert_newkey() - - -/////////////////////////////////////////////////////////////////////////// -// // -// Insert operations // -// // -/////////////////////////////////////////////////////////////////////////// - - -template -void insert(std::list& xs, const T& x) { - xs.push_back(x); -} - -template -void insert(std::set& xs, const T& x) { - xs.insert(x); -} - -template -void insert(std::vector& xs, const T& x) { - xs.push_back(x); -} - - -/////////////////////////////////////////////////////////////////////////// -// // -// Additional versions of standard algorithms // -// // -/////////////////////////////////////////////////////////////////////////// - -template -inline bool includes(const Set1& set1, const Set2& set2) -{ - return std::includes(set1.begin(), set1.end(), set2.begin(), set2.end()); -} - -template -inline bool includes(const Set1& set1, const Set2& set2, Compare comp) -{ - return std::includes(set1.begin(), set1.end(), set2.begin(), set2.end(), comp); -} - - -template -bool disjoint(InputIter1 first1, InputIter1 last1, - InputIter2 first2, InputIter2 last2) -{ - while (first1 != last1 && first2 != last2) - if (*first1 < *first2) - ++first1; - else if (*first2 < *first1) - ++first2; - else // *first1 == *first2 - return false; - return true; -} - -template -bool disjoint(InputIter1 first1, InputIter1 last1, - InputIter2 first2, InputIter2 last2, Compare comp) -{ - while (first1 != last1 && first2 != last2) - if (comp(*first1, *first2)) - ++first1; - else if (comp(*first2, *first1)) - ++first2; - else // *first1 == *first2 - return false; - return true; -} - -template -inline bool disjoint(const Set1& set1, const Set2& set2) -{ - return disjoint(set1.begin(), set1.end(), set2.begin(), set2.end()); -} - -template -inline bool disjoint(const Set1& set1, const Set2& set2, Compare comp) -{ - return disjoint(set1.begin(), set1.end(), set2.begin(), set2.end(), comp); -} - - -template -inline OutputIterator set_intersection(const Set1& set1, const Set2& set2, - OutputIterator result) -{ - return set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), result); -} - -template -inline OutputIterator set_intersection(const Set1& set1, const Set2& set2, - OutputIterator result, Compare comp) -{ - return set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), result, comp); -} - - -template -inline std::insert_iterator inserter(Container& container) -{ - return std::inserter(container, container.begin()); -} - -// max_element -// -template inline typename Es::iterator max_element(Es& es) -{ - return std::max_element(es.begin(), es.end()); -} - -template inline typename Es::const_iterator max_element(const Es& es) -{ - return std::max_element(es.begin(), es.end()); -} - -template -inline typename Es::iterator max_element(Es& es, BinaryPredicate comp) -{ - return std::max_element(es.begin(), es.end(), comp); -} - -template -inline typename Es::const_iterator max_element(const Es& es, BinaryPredicate comp) -{ - return std::max_element(es.begin(), es.end(), comp); -} - -// min_element -// -template inline typename Es::iterator min_element(Es& es) -{ - return std::min_element(es.begin(), es.end()); -} - -template inline typename Es::const_iterator min_element(const Es& es) -{ - return std::min_element(es.begin(), es.end()); -} - -template -inline typename Es::iterator min_element(Es& es, BinaryPredicate comp) -{ - return std::min_element(es.begin(), es.end(), comp); -} - -template -inline typename Es::const_iterator min_element(const Es& es, BinaryPredicate comp) -{ - return std::min_element(es.begin(), es.end(), comp); -} - -// first_lessthan and second_lessthan -// -struct first_lessthan { - template - bool operator() (const T1& e1, const T2& e2) { - return e1.first < e2.first; - } -}; - -struct second_lessthan { - template - bool operator() (const T1& e1, const T2& e2) { - return e1.second < e2.second; - } -}; - -// first_greaterthan and second_greaterthan -// -struct first_greaterthan { - template - bool operator() (const T1& e1, const T2& e2) { - return e1.first > e2.first; - } -}; - -struct second_greaterthan { - template - bool operator() (const T1& e1, const T2& e2) { - return e1.second > e2.second; - } -}; - - -/////////////////////////////////////////////////////////////////////////// -// // -// hash<> specializations // -// // -// These must be in namespace std. They permit the corresponding STL // -// container to be used as a key in an STL hash table. // -// // -/////////////////////////////////////////////////////////////////////////// - -//namespace EXT_NAMESPACE { -namespace std { - /* - // hash function for bool - // - template <> struct hash - { - size_t operator() (bool b) const - { - return b; - } // operator() - }; // hash{} - - // hash function for double - // - template <> struct hash - { - size_t operator() (double d) const - { - int exponent; - double fraction = frexp(d, &exponent); - return size_t(exponent) ^ size_t(1000000.0*(fabs(fraction-0.5))); - } // operator() - }; // hash{} - - // hash function for strings - // - template <> struct hash - { - size_t operator()(const std::string& s) const - { - typedef std::string::const_iterator CI; - - unsigned long h = 0; - unsigned long g; - CI p = s.begin(); - CI end = s.end(); - - while (p!=end) { - h = (h << 4) + (*p++); - if ((g = h&0xf0000000)) { - h = h ^ (g >> 24); - h = h ^ g; - }} - return size_t(h); - } // operator() - }; // hash{} - -*/ - // hash function for arbitrary pairs - // - template struct hash > { - size_t operator()(const std::pair& p) const - { - size_t h1 = hash()(p.first); - size_t h2 = hash()(p.second); - return h1 ^ (h1 >> 1) ^ h2 ^ (h2 << 1); - } - }; - - - // hash function for vectors - // - template struct hash > - { // This is the fn hashpjw of Aho, Sethi and Ullman, p 436. - size_t operator()(const std::vector& s) const - { - typedef typename std::vector::const_iterator CI; - - unsigned long h = 0; - unsigned long g; - CI p = s.begin(); - CI end = s.end(); - - while (p!=end) { - h = (h << 5) + hash()(*p++); - if ((g = h&0xff000000)) { - h = h ^ (g >> 23); - h = h ^ g; - }} - return size_t(h); - } - }; - - // hash function for slists - // - template struct hash > - { // This is the fn hashpjw of Aho, Sethi and Ullman, p 436. - size_t operator()(const ext::slist& s) const - { - typedef typename ext::slist::const_iterator CI; - - unsigned long h = 0; - unsigned long g; - CI p = s.begin(); - CI end = s.end(); - - while (p!=end) { - h = (h << 7) + hash()(*p++); - if ((g = h&0xff000000)) { - h = h ^ (g >> 23); - h = h ^ g; - }} - return size_t(h); - } - }; - - // hash function for maps - // - template struct hash > - { - size_t operator()(const std::map& m) const - { - typedef typename std::map M; - typedef typename M::const_iterator CI; - - unsigned long h = 0; - unsigned long g; - CI p = m.begin(); - CI end = m.end(); - - while (p != end) { - h = (h << 11) + hash()(*p++); - if ((g = h&0xff000000)) { - h = h ^ (g >> 23); - h = h ^ g; - }} - return size_t(h); - } - }; - -} // namespace EXT_NAMESPACE - - - -/////////////////////////////////////////////////////////////////////////// -// // -// Write/Read code // -// // -// These routines should possess write/read invariance IF their elements // -// also have write-read invariance. Whitespace, '(' and ')' are used as // -// delimiters. // -// // -/////////////////////////////////////////////////////////////////////////// - - -// Define istream >> const char* so that it consumes the characters from the -// istream. Just as in scanf, a space consumes an arbitrary amount of whitespace. -// -inline std::istream& operator>> (std::istream& is, const char* cp) -{ - if (*cp == '\0') - return is; - else if (*cp == ' ') { - char c; - if (is.get(c)) { - if (isspace(c)) - return is >> cp; - else { - is.unget(); - return is >> (cp+1); - } - } - else { - is.clear(is.rdstate() & ~std::ios::failbit); // clear failbit - return is >> (cp+1); - } - } - else { - char c; - if (is.get(c)) { - if (c == *cp) - return is >> (cp+1); - else { - is.unget(); - is.setstate(std::ios::failbit); - } - } - return is; - } -} - - -// Write out an auto_ptr object just as you would write out the pointer object -// -template -inline std::ostream& operator<<(std::ostream& os, const std::auto_ptr& sp) -{ - return os << sp.get(); -} - - -// Pairs -// -template -std::ostream& operator<< (std::ostream& os, const std::pair& p) -{ - return os << '(' << p.first << ' ' << p.second << ')'; -} - -template -std::istream& operator>> (std::istream& is, std::pair& p) -{ - char c; - if (is >> c) { - if (c == '(') { - if (is >> p.first >> p.second >> c && c == ')') - return is; - else - is.setstate(std::ios::badbit); - } - else - is.putback(c); - } - is.setstate(std::ios::failbit); - return is; -} - -// Lists -// -template -std::ostream& operator<< (std::ostream& os, const std::list& xs) -{ - os << '('; - for (typename std::list::const_iterator xi = xs.begin(); xi != xs.end(); ++xi) { - if (xi != xs.begin()) - os << ' '; - os << *xi; - } - return os << ')'; -} - -template -std::istream& operator>> (std::istream& is, std::list& xs) -{ - char c; // This code avoids unnecessary copy - if (is >> c) { // read the initial '(' - if (c == '(') { - xs.clear(); // clear the list - do { - xs.push_back(T()); // create a new elt in list - is >> xs.back(); // read element - } - while (is.good()); // read as long as possible - xs.pop_back(); // last read failed; pop last elt - is.clear(is.rdstate() & ~std::ios::failbit); // clear failbit - if (is >> c && c == ')') // read terminating ')' - return is; // successful return - else - is.setstate(std::ios::badbit); // something went wrong, set badbit - } - else // c is not '(' - is.putback(c); // put c back into input - } - is.setstate(std::ios::failbit); // read failed, set failbit - return is; -} - -// Vectors -// -template -std::ostream& operator<< (std::ostream& os, const std::vector& xs) -{ - os << '('; - for (typename std::vector::const_iterator xi = xs.begin(); xi != xs.end(); ++xi) { - if (xi != xs.begin()) - os << ' '; - os << *xi; - } - return os << ')'; -} - -template -std::istream& operator>> (std::istream& is, std::vector& xs) -{ - char c; // This code avoids unnecessary copy - if (is >> c) { // read the initial '(' - if (c == '(') { - xs.clear(); // clear the list - do { - xs.push_back(T()); // create a new elt in list - is >> xs.back(); // read element - } - while (is.good()); // read as long as possible - xs.pop_back(); // last read failed; pop last elt - is.clear(is.rdstate() & ~std::ios::failbit); // clear failbit - if (is >> c && c == ')') // read terminating ')' - return is; // successful return - else - is.setstate(std::ios::badbit); // something went wrong, set badbit - } - else // c is not '(' - is.putback(c); // put c back into input - } - is.setstate(std::ios::failbit); // read failed, set failbit - return is; -} - -// Slists -// -template -std::ostream& operator<< (std::ostream& os, const ext::slist& xs) -{ - os << '('; - for (typename ext::slist::const_iterator xi = xs.begin(); xi != xs.end(); ++xi) { - if (xi != xs.begin()) - os << ' '; - os << *xi; - } - return os << ')'; -} - -template -std::istream& operator>> (std::istream& is, ext::slist& xs) -{ - char c; - if (is >> c) { - if (c == '(') { - xs.clear(); - T e; - if (is >> e) { - xs.push_front(e); - typename ext::slist::iterator xi = xs.begin(); - while (is >> e) - xi = xs.insert_after(xi, e); - is.clear(is.rdstate() & ~std::ios::failbit); - if (is >> c && c == ')') - return is; - else - is.setstate(std::ios::badbit); - } - else { // empty list - is.clear(is.rdstate() & ~std::ios::failbit); - if (is >> c && c == ')') - return is; - else // didn't see closing ')' - is.setstate(std::ios::badbit); - } - } - else // didn't read '(' - is.putback(c); - } - is.setstate(std::ios::failbit); - return is; -} - -// Sets -// -template -std::ostream& operator<< (std::ostream& os, const std::set& s) -{ - os << '('; - for (typename std::set::const_iterator i = s.begin(); i != s.end(); ++i) { - if (i != s.begin()) - os << ' '; - os << *i; - } - return os << ')'; -} - -template -std::istream& operator>> (std::istream& is, std::set& s) -{ - char c; - if (is >> c) { - if (c == '(') { - s.clear(); - T e; - while (is >> e) - s.insert(e); - is.clear(is.rdstate() & ~std::ios::failbit); - if (is >> c && c == ')') - return is; - else - is.setstate(std::ios::badbit); - } - else - is.putback(c); - } - is.setstate(std::ios::failbit); - return is; -} - -// Hash_sets -// -template -std::ostream& operator<< (std::ostream& os, const std::unordered_set& s) -{ - os << '('; - for (typename std::unordered_set::const_iterator i = s.begin(); i != s.end(); ++i) { - if (i != s.begin()) - os << ' '; - os << *i; - } - return os << ')'; -} - -template -std::istream& operator>> (std::istream& is, std::unordered_set& s) -{ - char c; - if (is >> c) { - if (c == '(') { - s.clear(); - T e; - while (is >> e) - s.insert(e); - is.clear(is.rdstate() & ~std::ios::failbit); - if (is >> c && c == ')') - return is; - else - is.setstate(std::ios::badbit); - } - else - is.putback(c); - } - is.setstate(std::ios::failbit); - return is; -} - - -// Maps -// -template -std::ostream& operator<< (std::ostream& os, const std::map& m) -{ - typedef std::map M; - os << '('; - for (typename M::const_iterator it = m.begin(); it != m.end(); ++it) { - if (it != m.begin()) - os << ' '; - os << *it; - } - return os << ")"; -} - -template -std::istream& operator>> (std::istream& is, std::map& m) -{ - char c; - if (is >> c) { - if (c == '(') { - m.clear(); - std::pair e; - while (is >> e) - m.insert(e); - is.clear(is.rdstate() & ~std::ios::failbit); - if (is >> c && c == ')') - return is; - else - is.setstate(std::ios::badbit); - } - else - is.putback(c); - } - is.setstate(std::ios::failbit); - return is; -} - -// Hash_maps -// -template -std::ostream& operator<< (std::ostream& os, const std::unordered_map& m) -{ - typedef std::unordered_map M; - os << '('; - for (typename M::const_iterator it = m.begin(); it != m.end(); ++it) { - if (it != m.begin()) - os << ' '; - os << *it; - } - return os << ")"; -} - -template -std::istream& operator>> (std::istream& is, std::unordered_map& m) -{ - char c; - if (is >> c) { - if (c == '(') { - m.clear(); - std::pair e; - while (is >> e) - m.insert(e); - is.clear(is.rdstate() & ~std::ios::failbit); - if (is >> c && c == ')') - return is; - else - is.setstate(std::ios::badbit); - } - else - is.putback(c); - } - is.setstate(std::ios::failbit); - return is; -} - - -/////////////////////////////////////////////////////////////////////////// -// // -// Boost library additions // -// // -/////////////////////////////////////////////////////////////////////////// - -#ifdef BOOST_SHARED_PTR_HPP_INCLUDED - -// enhancements to boost::shared_ptr so it can be used with hash -// -namespace std { - template struct equal_to > - : public binary_function, boost::shared_ptr, bool> { - bool operator() (const boost::shared_ptr& p1, const boost::shared_ptr& p2) const { - return equal_to()(p1.get(), p2.get()); - } - }; -} // namespace std - -//namespace EXT_NAMESPACE { -namespace std { - template struct hash > { - size_t operator() (const boost::shared_ptr& a) const { - return hash()(a.get()); - } - }; -} // namespace ext - -template -inline std::ostream& operator<< (std::ostream& os, const boost::shared_ptr& sp) -{ - return os << sp.get(); -} - -#endif // BOOST_SHARED_PTR_HPP_INCLUDED - -struct resource_usage { }; - -#ifndef __i386 -inline std::ostream& operator<< (std::ostream& os, resource_usage r) -{ - return os; -} -#else // Assume we are on a 586 linux -inline std::ostream& operator<< (std::ostream& os, resource_usage r) -{ - FILE* fp = fopen("/proc/self/stat", "r"); - assert(fp); - int utime; - int stime; - unsigned int vsize; - unsigned int rss; - int result = - fscanf(fp, "%*d %*s %*c %*d %*d %*d %*d %*d %*u %*u %*u %*u %*u %d %d %*d %*d %*d %*d" - "%*u %*u %*d %u %u", &utime, &stime, &vsize, &rss); - assert(result == 4); - fclose(fp); - // s << "utime = " << utime << ", stime = " << stime << ", vsize = " << vsize << ", rss = " << rss - ; - // return s << "utime = " << utime << ", vsize = " << vsize; - return os << "utime " << float(utime)/1.0e2 << "s, vsize " - << float(vsize)/1048576.0 << " Mb."; -} -#endif - -//! A default_value_type{} object is used to read an object from a stream, -//! assigning a default value if the read fails. Users should not need to -//! construct such objects, but should use default_value() instead. -// -template -struct default_value_type { - object_type& object; - const default_type defaultvalue; - default_value_type(object_type& object, const default_type defaultvalue) - : object(object), defaultvalue(defaultvalue) { } -}; - -//! default_value() is used to read an object from a stream, assigning a -//! default value if the read fails. It returns a default_value_type{} -//! object, which does the actual reading. -// -template -default_value_type -default_value(object_type& object, const default_type defaultvalue=default_type()) { - return default_value_type(object, defaultvalue); -} - -//! This version of operator>>() reads default_value_type{} from an input stream. -// -template -std::istream& operator>> (std::istream& is, - default_value_type dv) { - if (is) { - if (is >> dv.object) - ; - else { - is.clear(is.rdstate() & ~std::ios::failbit); // clear failbit - dv.object = dv.defaultvalue; - } - } - return is; -} - -// inline F random1() { return rand()/(RAND_MAX+1.0); } -inline F random1() { return mt_genrand_res53(); } - -#endif // UTILITY_H -- cgit v1.2.3