Subversion Repositories spk

/*
  defines bob_point_map - class that is responsible for the tricky
  "point compression" when converting from binary to text

  it acts as kind of Search Tree but not binary search tree

  the map itself is created by linked list consisting of p_node objects.
  p_node means "point node" although it does not contain any point.
  pp_node means "point point node" because it does contain bob_dom_point :)

  if you add a point into this map:

  - I will take the X coordinate
  - I will take its 1th byte (left most) of the coordinate and try to find it in list.
  Either I will find it or I will add new p_node object.
  - I will take the 2nd byte and try to find it in the previously returned p_node which
  is now the "base"
  - I will continue with the remaining 3 bytes
  - I will repeat this for Y and Z coordinates
  - when adding the last byte of the Z coordinate, the last object created is not p_node
  but pp_node which also contain the point we are adding to the map

  I "found" this "algorithm" when I looked at raw output of points coords exported in hexadecimal

  It should be rewritten to either AVL or Red Black Tree but I don't understand the way 2-3-4 trees
  (RB trees) are balanced and standard AVL trees are not exactly what I want because I would have to
  first find the point and then insert if unsuccessfull.

  Althouhg this map is not as fast as it would probaly could with binary search trees, it's still
  damned fast compared to linear search which I and CheckerTwo were using.

*/

#ifndef BOB_POINT_MAP_INCLUDED
#define BOB_POINT_MAP_INCLUDED

#include "../common/ext_array.h"
#include "../common/ext_simple_list.h"

//#include "bob_point_bst.h"

class bob_point_map
{
        private:
                struct p_node
                {
                        unsigned char id;
                        p_node *next;
                        p_node *child;

                        p_node() { next=0; child=0;  }
                };

                struct pp_node : public p_node
                {
                        int index;
                        bob_dom_point *pnt;
                        pp_node() { pnt=0; index=0; }
                };

                p_node m_root;

                p_node * addNode(p_node *parent, unsigned char id)
                {
                        p_node *n, *old;
                        for(n=parent->child; n!=NULL; old=n, n=n->next){
                                m_compCount++;
                                if(n->id==id) return n;
                        }
                        if(parent->child==NULL)
                                n=parent->child=new p_node();
                        else
                                n=old->next=new p_node();
                        n->id=id;
                        return n;
                }

                pp_node * addPPNode(p_node *parent)
                {
                        p_node *n, *old;
                        pp_node *pp;
                        for(n=parent->child; n!=NULL; old=n, n=n->next)
                                ;;

                        if(parent->child==NULL)
                                parent->child=pp=new pp_node();
                        else
                                old->next=pp=new pp_node();
                        return pp;
                }

                p_node * findNode(p_node *parent, unsigned char id)
                {
                        p_node *ch;
                        for(ch=parent->child; ch!=NULL; ch=ch->next){
                                if(ch->id==id) return ch;
                        }
                        return NULL;
                }

                void deleteChilds(p_node *parent)
                {
                        p_node *ch, *old;
                        for(old=0, ch=parent->child; ch!=NULL; old=ch, ch=ch->next){
                                deleteChilds(ch);
                                delete old;
                        }
                        delete old;
                }

        private:
                typedef ext::array<bob_dom_point*> point_array;
                typedef ext::array<int> int_array;
                typedef ext::simple_list<int> int_list;

                point_array m_points; // all points
                int_array m_indexes; // converted indexes
                int m_pointSize; // size of points

                int_list m_uniqueIndexes; // list of indexes to unique points in points array
                int_list::iterator m_unique_it;

        public:
                class point_rec
                {
                        private:
                                const pp_node *m_node;

                        public:
                                point_rec(const pp_node *node) { m_node=node; }
                                point_rec(const point_rec& other) { m_node=other.m_node; }

                                bob_dom_point * operator *() { return m_node->pnt; }
                };

                class point_bucket
                {
                        private:
                                size_t m_size;
                                const pp_node *m_first;

                        public:
                                size_t size() const { return m_size; }

                                point_bucket(const pp_node *first)
                                {
                                        m_first=first;
                                        m_size=0;
                                        for(const p_node *n=m_first; n!=0; n=n->next)
                                                m_size++;
                                }

                                point_bucket(const point_bucket& other) { m_size=other.m_size; m_first=other.m_first; }

                                int index() { return m_first->index; }
                                void index(int idx) { ((pp_node*)m_first)->index=idx; }

                                point_rec operator[](size_t idx)
                                {
                                        size_t i;
                                        const p_node *n;
                                        for(n=m_first, i=0; i < idx; i++, n=n->next)
                                                ;;
                                        return point_rec((const pp_node*)n);
                                }
                };
        private:
                point_bucket _addPoint(bob_dom_point *pnt)
                {
                        p_node *n;
                        int v;
                        v=pnt->x;
                        n=&m_root;
                        unsigned char id;
                        for(int i=3; i >= 0; i--){
                                id=v >> (i * 8);
                                n=addNode(n, id);
                        }

                        v=pnt->y;
                        for(int i=3; i >= 0; i--){
                                id=v >> (i * 8);
                                n=addNode(n, id);
                        }

                        v=pnt->z;
                        for(int i=3; i >= 0; i--){
                                id=v >> (i * 8);
                                n=addNode(n, id);
                        }

                        pp_node *pp=addPPNode(n);
                        pp->pnt=pnt;

                        return point_bucket((pp_node*)n->child);
                }

        public:
                typedef point_array::iterator iterator;
                typedef int_list::const_iterator const_index_iterator;

                iterator begin() { return m_points.begin(); }
                iterator end() { return m_points.end(); }

                const_index_iterator indexBegin() const { return m_uniqueIndexes.begin(); }
                const_index_iterator indexEnd() const { return m_uniqueIndexes.end(); }

                //>>>>>>>>>>>>>
                //bob_point_bst map2;
                //<<<<<<<<<<<<<

                size_t m_compCount;

                void create(size_t size)
                {
                        m_points.resize(size, 0);
                        m_indexes.resize(size);
                        m_pointSize=0;
                        m_compCount=0;
                }

                void addPoint(bob_dom_point * pnt)
                {
                        point_bucket pb=_addPoint(pnt);

                        if(pb.size() == 1){
                                pb.index((int)m_uniqueIndexes.size());
                                m_uniqueIndexes.push_back(m_pointSize);
                        }
                        m_points[m_pointSize]=pnt;
                        m_indexes[m_pointSize]=pb.index();
                        m_pointSize++;

                        //map2.addPoint(pnt);
                }

                // c-tor
                bob_point_map() { m_pointSize=0; m_unique_it=m_uniqueIndexes.end(); }
                // d-tor
                ~bob_point_map() { clear(); }

                void clear()
                {
                        deleteChilds(&m_root); m_root.child=0;

                        for(point_array::iterator &it=m_points.begin(); it!=m_points.end(); ++it){
                                delete *it;
                        }
                        m_points.clear();
                        m_indexes.clear();
                        m_pointSize=0;

                        m_unique_it=m_uniqueIndexes.end();
                }

                bob_dom_point * operator[](int idx) { return m_points[idx]; }
                const bob_dom_point * operator[](int idx) const { return m_points[idx]; }

                int uniqueIndex(int idx) const { return (size_t)idx < m_points.size() ? m_indexes[idx] : -1; }

                size_t pointsSize() const { return m_points.size(); }
                size_t uniquePointsSize() const { return m_uniqueIndexes.size(); }

                bob_dom_point * nextUniquePoint()
                {
                        ++m_unique_it;
                        bob_dom_point *p=(m_unique_it!=m_uniqueIndexes.end() ? m_points[*m_unique_it] : 0);
                        return p;
                }
};

#endif // !defined(BOB_POINT_MAP_INCLUDED)