Strom (reverzna iteracia poduzlov)

Fórum › C / C++

Toto vlákno bylo označeno za vyřešené — příspěvek s řešením.

vitamin+8

Grafoman

17. 8. 2012 #1

Mam nasledovny kod. Je tam jeden template objekt Node ktory reprezentuje uzol stromu. Kazdy uzol moze obsahovat dynamicky pocet poduzlov. Na kratkom priklade mam vytvoreny jeden uzol ktory obsahuje 3 poduzly. Ak chcem prechadzat poduzly od prveho prvku az po posledny tak vsetko funguje, ale akonahle prechadzam opacne tak sa mi program zacykly. Neviete kde tam mam chybu?

#include <list>

template <class T>
class Node{
		Node* 				    root = nullptr;		
		typename std::list<Node*>::iterator root_iter;
		std::list<Node*>		    line;	//poduzly
		T				    data;
	public:
		enum eInsertPos_t{FRONT, BACK};
		
		Node(const T &t):data(t){}
		
                T &operator*(){return data;}
                const T& operator*()const{return data;}
                T& GetData(){return data;}
                const T& GetData()const{return data;}
                T  CopyData()const{return data;}		
		Node* Top()const{
			Node* n;
			for(n = const_cast<Node*>(this); n->root; n = n->root);
			return n;
		}
		void InsertRoot(Node* node, eInsertPos_t pos = BACK){
			if(root){
				node->root = root;
				node->root_iter = root_iter;
				*root_iter = node;
				root = node;
			}
			else{
				root = node;
				node->line.push_back(this);
				root_iter = std::prev(node->line.end());
			}
			
			if(pos == BACK){
				node->line.push_back(this);
				root_iter = std::prev(node->line.end());
			}
			else{	//FRONT
				node->line.push_front(this);
				root_iter = node->line.begin();
			}
		}
		void InsertLeaf(Node* node, eInsertPos_t pos = BACK){
			node->Pop();
			node->InsertRoot(this, pos);
		}
		void Pop(){
			if(root){
				root->line.erase(root_iter);
				root = nullptr;
			}
		}
		Node* Next()const{
			if(root){
				typename std::list<Node*>::const_iterator 	i = root_iter;
				i++;
				if(i != root->line.cend())return *i;
			}
			return nullptr;
		}
                // Toto nefunguje spravne:
		Node* Prew()const{
			if(root){
				typename std::list<Node*>::const_iterator 	i = root_iter;
				if(i == root->line.cbegin())return nullptr;		//podmienka sa vyhodnoti ako false aj ked obydva iteratory ukazuju na ten isty pointer, preco?
				i--;					//iterator sa nedekrementuje, preco?
				return *i;
			}
			return nullptr;
		}
		Node* Up()const{
			return root;
		}
		Node* Down(eInsertPos_t pos = FRONT)const{
			if(line.empty())return nullptr;
			if(pos == FRONT)return line.front();
			else return line.back();
		}
		Node* Front()const{
			if(root)return	root->line.front();
			else return this;
		}
		Node* Back()const{
			if(root)return	root->line.back();
			else return this;
		}
};


#include <iostream>
using namespace std;

int main(){
	Node<int> n1(1);
	Node<int> n2(2);
	Node<int> n3(3);
	Node<int> n4(4);
	
	//Node<int>* tree = n4.Top();
	
	n2.InsertRoot(&n1);
	n3.InsertRoot(&n1);
	n1.InsertLeaf(&n4);
	/*
	 * 1  ->  2
	 *    ->  3
	 *    ->  4
	 * 
	 */
	
	
	for(auto i = n1.Down(); i; i = i->Next())cout << **i << ", ";		//funguje pravne
	cout << endl;
	
	for(auto i = n1.Down(Node<int>::BACK); i; i = i->Prew())			//zacykli sa
	{
		cout << **i << ", ";
		cin.get();
	}
	cout << endl;
	
	return EXIT_SUCCESS;
}

Nahlásit jako SPAM

IP: 95.105.157.–

obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "

KIIV

~ Moderátor

+43

God of flame

17. 8. 2012 #2

neni teoreticky mozne, ze kdyz zavolas Prew (mimochodem co znamena Prew?) tak se ti i pokazde znovu vytvori a nainicializuje na root_iter - pak sice krasne dekrementujes, ale je ti to na dve veci... ?

Nahlásit jako SPAM

IP: 94.113.92.–

_{Program vždy dělá to co naprogramujete, ne to co chcete...}

ondra.holub +1

Stálý člen

17. 8. 2012 #3

Cyklus se inicializuje metodou Down. Metoda Down nic nedělá s root_iter. V Prew se i nastavuje na root_iter. Takže druhý a další průchod cyklem závisí na tom, co se dělo v předešlém cyklu. To už je celé principielně špatně.

Jinak ukládání (obyčejných) ukazatelů do STL kontejnerů moc práce neušetří. Musí se to ručně uvolňovat, není to moc přátelské k výjimkám.

Nahlásit jako SPAM

IP: 212.96.189.–

vitamin+8

Grafoman

17. 8. 2012 #4

#2 KIIV
Malo to byt Prev, ale stale neviem kde tam mam chybu.

Upravil som to takto a teraz to funguje:

Node* Prev()const{
	if(root){
		typename std::list<Node*>::const_reverse_iterator 	i(root_iter);
		i++;
		if(i != root->line.crend())return *i;
	}
	
	return nullptr;
}

#3 ondra.holub
Metoda Down vracia poduzol. root_iter je len pomocny "pointer" ktory ukazuje na bod v ktorom je spojeny nadradeny a podradeny uzol. V podstate metody Up(), Down() a Top() umoznuju "pohyb" medzi nadradenymi a podradenymi uzlami a metody Next(), Prev(), Front() a Back() umoznuju "pohyb" medzi poduzlami ktore su na rovnakej urovni(maju spolocny koren).

Nahlásit jako SPAM

IP: 95.105.157.–

obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "

KIIV

~ Moderátor

+43

God of flame

17. 8. 2012 #5

Zajímavé

Nejlepší odpověď

tak sem si trosku zaexperimentoval a udelal sem zjednodusenou tridu akorat s funkcnimi jednocestymi iteratory

(jen jako Proof-of-concept + C++0x)

#include <list>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using std::list;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::pair;
using std::for_each;


template<class T>
class Node {
  public:
    typedef list<Node *> NodeList;
    typedef typename NodeList::iterator NodeListIter;
    typedef typename NodeList::reverse_iterator NodeListRIter;

  private:
    Node *            m_parent;
    NodeList          m_childs;
    T                 m_data;

  public:

    Node(const T & d, Node * par = nullptr): m_parent(par), m_data(d) {
      if ( par != nullptr ) { par->back_insert(this); }
    }
    inline void front_insert(Node * n) { n->set_parent(this); m_childs.push_front(n); }
    inline void back_insert(Node * n) { n->set_parent(this); m_childs.push_back(n); }
    inline void set_parent(Node * n) { m_parent=n; }

    inline void print(string pref="") {
      cout << pref << m_data << endl;
      for ( auto i: m_childs) {
        i->print(pref+"  ");
      }
    }

    inline T & data() { return m_data; }

    inline NodeListIter   childs_begin()  { return m_childs.begin();  }
    inline NodeListIter   childs_end()    { return m_childs.end();    }
    inline NodeListRIter  childs_rbegin() { return m_childs.rbegin(); }
    inline NodeListRIter  childs_rend()   { return m_childs.rend();   }


    class iterator {
      public:
        typedef pair< NodeListIter, NodeListIter> NodeListIterPair;

      private:
        Node * m_owner, * m_data;
        vector< NodeListIterPair > m_iterators;

      public:
        iterator(): m_owner(nullptr), m_data(nullptr) {};
        explicit iterator(Node * owner): m_owner(owner), m_data(owner) {
          m_iterators.push_back(NodeListIterPair(owner->childs_begin(),owner->childs_end()));
        }
        iterator(const iterator & b): m_owner(b.m_owner), m_data(b.m_data), m_iterators(b.m_iterators) {
        }
        iterator(iterator && b): m_owner(b.m_owner), m_data(b.m_data), m_iterators(b.m_iterators) {
          b.m_owner = nullptr;
          b.m_data  = nullptr;
          b.m_iterators.clear();
        }
        iterator & next() {
          if ( !m_iterators.empty() ) {
            NodeListIterPair & last = m_iterators.back();
            if ( last.first != last.second ) {// there are some childs
              Node * item = *(last.first);
              m_data = item; // iterator dereference
              ++(last.first); // move to next item
              m_iterators.push_back(NodeListIterPair(item->childs_begin(),item->childs_end()));
            } else {
              m_iterators.pop_back();
              return next(); // recurse (to higher level)
            }
          } else {
            m_data = nullptr;
          }
          return *this;
        }
        inline Node * operator*() {
          return m_data;
        }
        inline const Node * operator*() const {
          return m_data;
        }
        inline iterator & operator++() {
          return next();
        }
        inline bool operator!=(const iterator & b) const {
          return b.m_data != m_data;
        }
    };

    class reverse_iterator {
      public:
        typedef pair< NodeListRIter, NodeListRIter> NodeListRIterPair;

      private:
        Node * m_owner, * m_data;
        vector< NodeListRIterPair > m_iterators;

      public:
        reverse_iterator(): m_owner(nullptr), m_data(nullptr) {};
        explicit reverse_iterator(Node * owner): m_owner(owner), m_data(owner) {
          m_iterators.push_back(NodeListRIterPair(owner->childs_rbegin(),owner->childs_rend()));
        }
        reverse_iterator(const reverse_iterator & b): m_owner(b.m_owner), m_data(b.m_data), m_iterators(b.m_iterators) {
        }
        reverse_iterator(reverse_iterator && b): m_owner(b.m_owner), m_data(b.m_data), m_iterators(b.m_iterators) {
          b.m_owner = nullptr;
          b.m_data  = nullptr;
          b.m_iterators.clear();
        }
        reverse_iterator & next() {
          if ( !m_iterators.empty() ) {
            NodeListRIterPair & last = m_iterators.back();
            if ( last.first != last.second ) {// there are some childs
              Node * item = *(last.first);
              m_data = item; // iterator dereference
              ++(last.first); // move to next item
              m_iterators.push_back(NodeListRIterPair(item->childs_rbegin(),item->childs_rend()));
            } else {
              m_iterators.pop_back();
              return next(); // recurse (to higher level)
            }
          } else {
            m_data = nullptr;
          }
          return *this;
        }
        inline Node * operator*() {
          return m_data;
        }
        inline const Node * operator*() const {
          return m_data;
        }
        inline reverse_iterator & operator++() {
          return next();
        }
        inline bool operator!=(const reverse_iterator & b) const {
          return b.m_data != m_data;
        }
    };

    inline iterator begin() { return iterator(this); }
    inline iterator end()   { return iterator();     } 
    inline reverse_iterator rbegin() { return reverse_iterator(this); }
    inline reverse_iterator rend()   { return reverse_iterator();     } 


};

int main() {
  Node<string> A1(string("A1")); 
  Node<string> A2(string("A2"),&A1); 
  Node<string> A3(string("A3"),&A1); 
  Node<string> A4(string("A4"),&A2); 
  Node<string> A5(string("A5"),&A2); 
  Node<string> A6(string("A6"),&A2);
  Node<string> A7(string("A7"),&A3); 
  Node<string> A8(string("A8"),&A3);
  cout << "Rekurzivni print: \n";
  A1.print(">>"); 

  cout << "Traverzace dopredu (for_each): \n";
  for_each(A1.begin(), A1.end(), [](Node<string> * item){
    cout << "item: " << item->data() << endl;
  });

  cout << "Traverzace pozpatku (for_each): \n";
  for_each(A1.rbegin(), A1.rend(), [](Node<string> * item){
    cout << "item: " << item->data() << endl;
  });

  cout << "Traverzace pozpatku (old way?): \n";
  Node<string>::reverse_iterator ri = A1.rbegin();
  Node<string>::reverse_iterator re = A1.rend();
  while ( ri != re ) {
    cout << "item: " << (*ri)->data() << endl;
    ++ri;
  }
  return 0;
}

Nahlásit jako SPAM

IP: 94.113.92.–

_{Program vždy dělá to co naprogramujete, ne to co chcete...}

vitamin+8

Grafoman

18. 8. 2012 #6

#5 KIIV
Dik, to vyzera dobre, nakoniec som nasiel na nete uz implementovanu triedu stromu v ktorom je to vyriesene nasledovne: