tjstd.h

/***************************************************************************
                          tjstd.h  -  description
                             -------------------
    begin                : Thu Dec 5 2002
    copyright            : (C) 2001 by Thies H. Jochimsen
    email                : jochimse@cns.mpg.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef TJSTD_H
#define TJSTD_H


#ifndef TJUTILS_CONFIG_H
#define TJUTILS_CONFIG_H
#include <tjutils/config.h>
#endif

#include <tjutils/tjheap.h>  // memory management
#include <tjutils/tjcstd.h>  // C standard lib


// Macros for stream replacement
// Must be placed here to avoid circular dependencies

#ifdef STREAM_REPLACEMENT

#define STD_ostream tjstd_ostream
#define STD_istream tjstd_istream
#define STD_ostringstream tjstd_ostringstream
#define STD_ofstream tjstd_ofstream
#define STD_ifstream tjstd_ifstream
#define STD_cout tjstd_cout
#define STD_cerr tjstd_cerr
#define STD_cin tjstd_cin
#define STD_endl tjstd_endl
#define STD_flush tjstd_flush
#define STD_setprecision tjstd_setprecision
#define STD_getline tjstd_getline
#define STD_make_pair tjstd_make_pair

class tjstd_ostream; // forward declaration
class tjstd_istream; // forward declaration
class tjstd_string; // forward declaration

#else

#define STD_ostream std::ostream
#define STD_istream std::istream
#define STD_ostringstream std::ostringstream
#define STD_ofstream std::ofstream
#define STD_ifstream std::ifstream
#define STD_cout std::cout
#define STD_cerr std::cerr
#define STD_cin std::cin
#define STD_endl std::endl
#define STD_flush std::flush
#define STD_setprecision std::setprecision
#define STD_getline std::getline
#define STD_make_pair std::make_pair

#include <iostream>
#include <fstream>
#include <sstream>

#endif // STREAM_REPLACEMENT



#ifdef STL_REPLACEMENT

#define STD_list tjstd_list
#define STD_find tjstd_find
#define STD_pair tjstd_pair
#define STD_map tjstd_map
#define STD_vector tjstd_vector
#define STD_complex tjstd_complex
#define STD_back_inserter tjstd_back_inserter
#define STD_unique_copy tjstd_unique_copy
#define STD_swap tjstd_swap
#define STD_max tjstd_max
#define STD_min tjstd_min

// complex math funcs
#define STD_abs tjstd_abs
#define STD_arg tjstd_arg
#define STD_log tjstd_log
#define STD_exp tjstd_exp
#define STD_conj tjstd_conj

#else // STL_REPLACEMENT

#include <list>
#include <utility>
#include <map>
#include <complex>
#include <cmath>
#include <new>
#include <vector>
#include <algorithm> // For Visual Studio 2005

#define STD_list std::list
#define STD_find std::find
#define STD_pair std::pair
#define STD_map std::map
#define STD_vector std::vector
#define STD_complex std::complex<float>
#define STD_back_inserter std::back_inserter
#define STD_unique_copy std::unique_copy
#define STD_swap std::swap
#define STD_max std::max
#define STD_min std::min

// complex math funcs
#define STD_abs std::abs
#define STD_arg std::arg
#define STD_log std::log
#define STD_exp std::exp
#define STD_conj std::conj

#endif // STL_REPLACEMENT



#ifdef STRING_REPLACEMENT

#define STD_string tjstd_string

#else // STRING_REPLACEMENT

#include <string>
#define STD_string std::string

#endif // STRING_REPLACEMENT






#ifdef STL_REPLACEMENT


template<class I>
class tjnode {

 public:
  tjnode() : value(0), next(0), prev(0) {}
  tjnode (const I& newval) : value(new I(newval)), next(0), prev(0) {}
  ~tjnode() {if(value) delete value;}
  I* value;
  tjnode<I>* next;
  tjnode<I>* prev;

 private:
  // make these member functions private to prevent their usage
  tjnode(const tjnode&) {}
  tjnode& operator = (const tjnode&) {return *this;}

};



template<class I>
class tjiterator {

 public:
  tjiterator(tjnode<I>* itemptr=0) : current(itemptr) {}

  operator I* () {
    if(current) return (current->value);
    else return 0;
  }

  operator const I* () const {
    if(current) return (current->value);
    else return 0;
  }


  I& operator * () {return *(operator I* ());}
  const I& operator * () const {return *(operator const I* ());}

  I* operator -> () {return operator I* ();}
  const I* operator -> () const {return operator const I* ();}


  tjiterator<I> operator ++ () {
    if(current && current->next) current=current->next;
    return *this;
  }

  tjiterator<I> operator ++ (int) { // postfix
    tjnode<I>* old=current;
    if(current && current->next) current=current->next;
    return tjiterator<I>(old);
  }

  tjiterator<I> operator -- () {
    if(current && current->prev) current=current->prev;
    return *this;
  }

  tjiterator<I> operator -- (int) { // postfix
    tjnode<I>* old=current;
    if(current && current->prev) current=current->prev;
    return tjiterator<I>(old);
  }


  bool operator == (const tjiterator<I>& i2) const {
    return (current==i2.current);
  }

  bool operator != (const tjiterator<I>& i2) const {
    return (current!=i2.current);
  }

  tjnode<I>* current;
};



template<class I>
class tjstd_list {

 public:

  typedef tjiterator<I> iterator;
  typedef tjiterator<I> const_iterator;

  tjstd_list() : first(&end_node), size_cache(0) {}

  tjstd_list(unsigned int n, const I& value) : first(&end_node), size_cache(0) {
    for(unsigned int i=0; i<n; i++) push_back(value);
  }

  tjstd_list(const tjstd_list& l) : first(&end_node), size_cache(0) {tjstd_list::operator = (l);}

  ~tjstd_list() {clear();}

  tjstd_list& operator = (const tjstd_list& l) {
    check("operator = (pre)");
    clear();
    for(const_iterator it=l.begin(); it!=l.end(); ++it) push_back(*it);
    check("operator = (post)");
    return *this;
  }


  tjiterator<I> begin() {return tjiterator<I>(first);}
  tjiterator<I> end() {return tjiterator<I>(&end_node);}

  tjiterator<I> begin() const {return tjiterator<I>(first);}
  tjiterator<I> end() const {return tjiterator<I>(&end_node);}


  tjiterator<I> push_back(const I& newval) {
    check("push_back(pre)");
    tjnode<I>* newnode=new tjnode<I>(newval);
    push_back_node(newnode);
    check("push_back(post)");
    return tjiterator<I>(newnode);
  }


  tjiterator<I> push_front(const I& newval) {
    check("push_front(pre)");
    tjnode<I>* newnode=new tjnode<I>(newval);
    push_front_node(newnode);
    check("push_front(post)");
    return tjiterator<I>(newnode);
  }



  tjiterator<I> insert(const tjiterator<I>& pos, const I& newval) {
    check("insert(pre)");
    tjnode<I>* newnode=new tjnode<I>(newval);
    insert_node(pos.current, newnode);
    return tjiterator<I>(newnode);
  }


  void remove(const I& remval) {
    check("remove(pre)");
    I value2Bremoved(remval); //create copy in the case it is an element of the list itself
    iterator it=begin();
    while(it!=end()) {
      if((*it)==value2Bremoved) {
        tjnode<I>* toberemoved=it.current;
        ++it;
        remove_node(toberemoved);
        delete toberemoved;
      } else ++it;
    }
    check("remove(post)");
  }


  tjiterator<I> erase(const tjiterator<I>& b,const tjiterator<I>& e) {
    check("erase2(pre)");
    iterator it=b;
    while(it!=e) {
      tjnode<I>* toberemoved=it.current;
      it.current=toberemoved->next; // iterate to next node
      remove_node(toberemoved);
      delete toberemoved;
    }
    check("erase2(post)");
    return e;
  }


  tjiterator<I> erase(const tjiterator<I>& p) {
    check("erase1(pre)");
    tjiterator<I> result=p; result++;
    tjnode<I>* toberemoved=p.current;
    remove_node(toberemoved);
    delete toberemoved;
    check("erase1(post)");
    return result;
  }


  void clear() {erase(begin(),end());}


  unsigned int size() const {return size_cache;}
  bool empty() const {return !size_cache;}



  void sort() {
    check("sort(pre)");

    // make list_unsrt a shallow copy of this
    tjstd_list<I> list_unsrt;
    if(first!=(&end_node)) {
      list_unsrt.first=first;
      list_unsrt.end_node.prev=end_node.prev;
      list_unsrt.end_node.prev->next=&(list_unsrt.end_node);
      list_unsrt.size_cache=size_cache;
    }

    // reset me
    first=&end_node;
    end_node.prev=0;
    size_cache=0;

    while(list_unsrt.begin()!=list_unsrt.end()) {
      tjnode<I>* node2sort=list_unsrt.first;
      list_unsrt.remove_node(node2sort);
      iterator it=begin();
      while(it!=end() && (*it)<(*(node2sort->value))) ++it;
      insert_node(it.current,node2sort);
    }

    list_unsrt.check("sort::list_unsrt");
    check("sort(post)");
  }



  void unique() {
    check("unique(pre)");
    for(iterator it=begin(); it!=end(); ++it) {
      while(it.current->next && it.current->next->value && (*(it.current->value))==(*(it.current->next->value)) ) {
        tjnode<I>* toberemoved=it.current->next;
        remove_node(toberemoved);
        delete toberemoved;
      }
    }
    check("unique(post)");
  }

 private:

  void push_back_node(tjnode<I>* newnode) {
    check("push_back_node(pre)");
    newnode->next=0;
    newnode->prev=0;
    if(first==(&end_node)) {
      first=end_node.prev=newnode;
      newnode->next=&end_node;
    } else {
      end_node.prev->next=newnode;
      newnode->prev=end_node.prev;
      end_node.prev=newnode;
      newnode->next=&end_node;
    }
    size_cache++;
    check("push_back_node(post)");
  }


  void push_front_node(tjnode<I>* newnode) {
    check("push_front_node(pre)");
    newnode->next=0;
    newnode->prev=0;
    if(first==(&end_node)) {
      first=end_node.prev=newnode;
      newnode->next=&end_node;
    } else {
      first->prev=newnode;
      newnode->next=first;
      first=newnode;
    }
    size_cache++;
    check("push_front_node(post)");
  }


  void remove_node(tjnode<I>* toberemoved) {
    check("remove_node(pre)");
    if(toberemoved->prev) toberemoved->prev->next=toberemoved->next;
    if(toberemoved->next) toberemoved->next->prev=toberemoved->prev;
    if(toberemoved==first) first=toberemoved->next;
    if(toberemoved==end_node.prev) end_node.prev= toberemoved->prev;
    toberemoved->next=0;
    toberemoved->prev=0;
    size_cache--;
    check("remove_node(post)");
  }


  // Insert before posnode
  void insert_node(tjnode<I>* posnode, tjnode<I>* newnode) {
    check("insert_node(pre)");
    newnode->next=0;
    newnode->prev=0;
    if(posnode==(&end_node)) {
      push_back_node(newnode);
    } else {
      if(posnode==first) push_front_node(newnode);
      else {
        // in the following the order is important
        posnode->prev->next=newnode;
        newnode->prev=posnode->prev;
        newnode->next=posnode;
        posnode->prev=newnode;
        size_cache++;
      }
    }
    check("insert_node(post)");
  }


  void check(const char* /*caller*/) const {
#ifdef ODIN_DEBUG
/*
    if(!first) STD_cerr << "ERROR: tjstd_list::" << caller << " !first " << STD_endl;

    int size=0;
    for(const_iterator it=begin(); it!=end(); ++it) size++;
    if(size!=size_cache) STD_cerr << "ERROR: tjstd_list::" << caller << " size(" << size << ") != size_cache(" << size_cache << ")" << STD_endl;
*/
#endif
  }


  tjnode<I>* first;
  mutable tjnode<I>  end_node;
  int size_cache;
};


template<class I>
  tjiterator<I> tjstd_find(const tjiterator<I>& b,const tjiterator<I>& e, const I& findval) {
    tjiterator<I> it=b;
    while(it!=e) {
      if((*it)==findval) return it;
      ++it;
    }
    return e;
  }



template<class K, class V>
class tjstd_pair {

 public:
  tjstd_pair() {}
  tjstd_pair(const K& key, const V& value) : first(key), second(value) {}

  bool operator == (const tjstd_pair<K,V>& i2) const {
    // do not use == operator of K, otherwise it has to be defined
    if( (first<i2.first) || (i2.first<first) ) return false;
    return true;
  }

  bool operator < (const tjstd_pair<K,V>& i2) const {
    return (first<i2.first);
  }

  K first;
  V second;
};


template <class K, class V>
tjstd_pair<K,V> tjstd_make_pair(const K& k, const V& v) {
  return tjstd_pair<K,V>(k,v);
}




template<class K, class V> class tjstd_map : public tjstd_list< tjstd_pair<K,V> >  {

 public:
  V& operator [] (const K& key) {
    typename tjstd_map<K,V>::iterator it=find(key);
    if(it==tjstd_list< tjstd_pair<K,V> >::end()) {
      it=push_back(tjstd_pair<K,V>(key,V()));
      tjstd_list< tjstd_pair<K,V> >::sort();
    }
    return it->second;
  }

  typename tjstd_map<K,V>::iterator find(const K& key) {
    for(typename tjstd_map<K,V>::iterator it=tjstd_list< tjstd_pair<K,V> >::begin(); it!=tjstd_list< tjstd_pair<K,V> >::end(); ++it) {
      if( !( (key<(it->first)) || ((it->first)<key) ) ) return it;
    }
    return tjstd_list< tjstd_pair<K,V> >::end();
  }

  typename tjstd_map<K,V>::iterator find(const K& key) const {
    for(typename tjstd_map<K,V>::const_iterator it=tjstd_list< tjstd_pair<K,V> >::begin(); it!=tjstd_list< tjstd_pair<K,V> >::end(); ++it) {
      if( !( (key<(it->first)) || ((it->first)<key) ) ) return it;
    }
    return tjstd_list< tjstd_pair<K,V> >::end();
  }

  void insert(const tjstd_pair<K,V>& pair) {
    if(find(pair.first)==tjstd_list< tjstd_pair<K,V> >::end()) {
      (*this)[pair.first]=pair.second;
    }
  }

  typename tjstd_map<K,V>::iterator insert(typename tjstd_map<K,V>::iterator, const tjstd_pair<K,V>& pair) {
    if(find(pair.first)==tjstd_list< tjstd_pair<K,V> >::end()) {
      (*this)[pair.first]=pair.second;
    }
    return find(pair.first);
  }


};


// Extra type for vector size to avoid type-conversion problems in arithmetic expressions on VxWorks
// which occur if a simple 'unsigned int' is used in the constructor of tjstd_vector
struct tjstd_vector_size {
  tjstd_vector_size(unsigned int size) : s(size) {}
  unsigned int s;
};



template<class E>
class tjstd_vector {

 public:
  tjstd_vector() : data(0), nelements(0), cap(0) {}

  tjstd_vector(tjstd_vector_size size, const E& initval=E()) : data(0), nelements(0), cap(0) {
    resize(size.s);
    for(unsigned int i=0; i<nelements; i++) {
      data[i]=initval;
    }
  }

  tjstd_vector(const tjstd_vector<E>& v) : data(0), nelements(0), cap(0) {
    tjstd_vector<E>::operator = (v);
  }

  ~tjstd_vector() {
    if(data) delete[] data;
  }

  tjstd_vector<E>& operator = (const tjstd_vector<E>& v) {
    if(data) delete[] data;
    nelements=cap=v.nelements;
    data=new E[nelements];
    for(unsigned int i=0; i<nelements; i++) data[i]=v.data[i];
    return *this;
  }

  E& operator [] (unsigned long i) {
    if(i>=nelements) {
//      STD_cerr << "ERROR: tjstd_vector: operator[" << i << "] exceeds size=" << nelements << STD_endl;
      return retdummy;
    }
    else return data[i];
  }

  const E& operator [] (unsigned long i) const {
    if(i>=nelements) {
//      STD_cerr << "ERROR: tjstd_vector: operator[" << i << "] exceeds size=" << nelements << STD_endl;
      return retdummy;
    }
    else return data[i];
  }

  void clear() { resize(0);}

  void resize(unsigned long newsize) {
    if(newsize>cap) {
      cap=newsize*2;
      E* newdata=new E[cap];
      if(data) {
        for(unsigned int i=0; i<nelements; i++) newdata[i]=data[i];
        delete[] data;
      }
      data=newdata;
    }
    else if(newsize<cap/2) {
      cap=newsize;
      E* newdata=new E[cap];
      if(data){
        for(unsigned int i=0; i<newsize; i++) newdata[i]=data[i];
        delete[] data;
      }
      data=newdata;
    }
    nelements=newsize;
  }

  void reserve(unsigned long newcap) {
    if(newcap>cap) {
      cap=newcap;
      E* newdata=new E[cap];
      if(data) {
        for(unsigned int i=0; i<nelements; i++) newdata[i]=data[i];
        delete[] data;
      }
      data=newdata;
    }
  }

  unsigned long size() const {return nelements;}
  unsigned long capacity() const {return cap;}

  void push_back(const E& val) {
    resize(nelements+1);
    data[nelements-1]=val;
  }

 private:
  E* data;
  unsigned long nelements;
  unsigned long cap;
  E retdummy;

};


// comparison operators

template<class E>
bool operator == (const tjstd_vector<E>& v1, const tjstd_vector<E>& v2) {
  if(v1.size()!=v2.size()) return false;
  bool result=true;
  for(unsigned int i=0; i<v1.size(); i++) {
    if(v1[i]!=v2[i]) {
      result=false;
      break;
    }
  }
  return result;
}


template<class E>
bool operator != (const tjstd_vector<E>& v1, const tjstd_vector<E>& v2) {
  return !(v1==v2);
}


template<class E>
bool operator < (const tjstd_vector<E>& v1, const tjstd_vector<E>& v2) {
  unsigned int v1size=v1.size();
  unsigned int v2size=v2.size();
  if(v1size!=v2size) return (v1size<v2size);
  for(unsigned int i=0; i<v1size; i++) {
    if(v1[i]!=v2[i]) return (v1[i]<v2[i]);
  }
  return false;
}



class tjstd_complex {

  float re, im;

public:

  tjstd_complex (float real=0, float imaginary=0) {
    re = real;
    im = imaginary;
  }

  float real() const { return re;}
  float imag() const { return im;}


  friend STD_ostream & operator << (STD_ostream & s, tjstd_complex c);

  bool operator == (tjstd_complex c) const {
    if (c.re == re && c.im == im)
      return (1);
    else
      return (0);
  }

  bool operator != (tjstd_complex c) const {
    if (c.re != re || c.im != im)
      return (1);
    else
      return (0);
  }


  friend tjstd_complex operator + (tjstd_complex c) {
    return (c);
  }


  friend tjstd_complex operator + (tjstd_complex c1, tjstd_complex c2) {
    tjstd_complex sum;
    sum.re = c1.re + c2.re;
    sum.im = c1.im + c2.im;
    return (sum);
  }

  tjstd_complex operator += (tjstd_complex c) {
      re += c.re;
      im += c.im;
      return (*this);
  }



  friend tjstd_complex operator - (tjstd_complex c) {
    c.re = -c.re;
    c.im = -c.im;
    return (c);
  }



  friend tjstd_complex operator - (tjstd_complex c1, tjstd_complex c2) {
    tjstd_complex diff;
    diff.re = c1.re - c2.re;
    diff.im = c1.im - c2.im;
    return (diff);
  }

  tjstd_complex operator -= (tjstd_complex c) {
      re -= c.re;
      im -= c.im;
      return (*this);
  }


  friend tjstd_complex operator *(tjstd_complex c1, tjstd_complex c2) {
    tjstd_complex prod;
      prod.re = c1.re * c2.re - c1.im * c2.im;
      prod.im = c1.re * c2.im + c1.im * c2.re;
      return (prod);
  }

  tjstd_complex operator *= (tjstd_complex c) {
    operator = ((*this) * c);
    return (*this);
  }

  friend tjstd_complex operator / (tjstd_complex c1, tjstd_complex c2) {
    tjstd_complex div;
    float denominator = c2.re * c2.re + c2.im * c2.im;
    if (denominator == 0.0) {
      div.re = 0.0;
      div.im = 0.0;
    } else {
      div.re = (c1.re * c2.re + c1.im * c2.im) / denominator;
      div.im = (c1.im * c2.re - c1.re * c2.im) / denominator;
    }
    return (div);
  }

  tjstd_complex operator /= (tjstd_complex c) {
    operator = ((*this) / c);
    return (*this);
  }

  friend tjstd_complex tjstd_conj (tjstd_complex c) {
    return tjstd_complex (c.re, -c.im);
  }
  friend tjstd_complex conj (tjstd_complex c) {return tjstd_conj(c);}

  friend float tjstd_abs (tjstd_complex c) {
    return float(sqrt (c.re * c.re + c.im * c.im));
  }
  friend float abs (tjstd_complex c) {return tjstd_abs(c);}

  friend float tjstd_arg (tjstd_complex c) {
    return float(atan2 (c.im, c.re));
  }
  friend float arg (tjstd_complex c) {return tjstd_arg(c);}

  friend tjstd_complex tjstd_log (tjstd_complex c) {
    return (tjstd_complex ((float)log(abs(c)),arg(c)));
  }
  friend tjstd_complex log (tjstd_complex c) {return tjstd_log(c);}

  friend tjstd_complex tjstd_exp (tjstd_complex c) {
    return (   tjstd_complex ( (float)exp(c.re)*cos(c.im), (float)exp(c.re)*sin(c.im) ) );
  }
  friend tjstd_complex exp (tjstd_complex c) {return tjstd_exp(c);}

};



template<typename T>
void tjstd_swap(T& a1, T& a2){
  T temp=a1;
  a1=a2;
  a2=temp;
}


template<typename T>
T tjstd_max(const T& a1, const T& a2){
  if(a1>a2) return a1;
  else return a2;
}

template<typename T>
T tjstd_min(const T& a1, const T& a2){
  if(a1<a2) return a1;
  else return a2;
}


#endif // ifdef STL_REPLACEMENT



#ifdef STRING_REPLACEMENT



class tjstd_string {

 public:
  tjstd_string ();
  tjstd_string (unsigned int n, const char c=' ');
  tjstd_string (const char *charptr) : sdata(0)  {tjstd_string::operator = (charptr);}
  tjstd_string (const tjstd_string& str) : sdata(0)  {tjstd_string::operator = (str);}

  tjstd_string& operator = (const tjstd_string& str);
  tjstd_string& operator = (const char *charptr);

  ~tjstd_string();

  unsigned int size() const {return length_cache;}
  unsigned int length() const {return size();}

  const char * c_str() const;

  char& operator [] (unsigned int i);
  const char& operator [] (unsigned int i) const;

  friend tjstd_string operator + (const tjstd_string& s1, const tjstd_string& s2);
  friend tjstd_string operator + (const tjstd_string& s1, const char* s2);
  friend tjstd_string operator + (const char* s1, const tjstd_string& s2);

  tjstd_string& operator += (const tjstd_string& s2);

  friend bool operator == (const tjstd_string& s, const tjstd_string& t);
  friend bool operator == (const tjstd_string& s, const char* t);
  friend bool operator == (const char* s, const tjstd_string& t);


  friend bool operator != (const tjstd_string& s, const tjstd_string& t);
  friend bool operator != (const tjstd_string& s, const char* t);
  friend bool operator != (const char* s, const tjstd_string& t);

  friend bool operator < (const tjstd_string& s, const tjstd_string& t);
  friend bool operator > (const tjstd_string& s, const tjstd_string& t);

  friend STD_ostream& operator << (STD_ostream& s,const tjstd_string& t);
  friend STD_istream& operator >> (STD_istream& s, tjstd_string& t);

  tjstd_string substr(unsigned int begin,unsigned int sublength) const;
  void erase(unsigned int begin,unsigned int end);

  unsigned int find(const tjstd_string& searchstring, int startpos=0) const;

  typedef unsigned int size_type;

  static unsigned int npos;

 private:

  void concat2strings(const tjstd_string& srcstring1, const tjstd_string& srcstring2);
  static bool compare2strings(const char* str1, const char* str2);

  char* sdata;
  unsigned int length_cache;

  static char nullchar;
};

#endif // STRING_REPLACEMENT


#endif

---