Space-efficient geometric algorithms and data structures By Ilya Katz and Hervé Brönnimann

block_tree_heap.hpp

Go to the documentation of this file.

//#define DEBUG
//TODO: break insert_into_block into smaller functions!!!!!
//TODO:account for block size 1
//TODO: in order to adjust PQ, need to have KeyOfValuePQ
/*
 * Copyright © Ilya Katz and Hervé Brönnimann, 2006.
 *
 * This is the definition of space efficient tree/heap that employs Red-Black tree
 * from the STL and a block that refers to several line segments
 *
 * This file was creted by adopting stl_set.h of
 * the SGI STL library
 */

// Set implementation -*- C++ -*-

// Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library 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, or (at your option)
// any later version.

// This library 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 General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

#include "block_tree_heap/tree.h"
#include "functions.hpp"
#include <iterator>
#include <utility>

#ifndef _BLOCK_TREE_HEAP_H
#define _BLOCK_TREE_HEAP_H 1

namespace inplaceds
{
         /*
                * Distinction between different iterators
                *
                * \li \c iterator is the iterator that refences to \b blocks
                * \li \c SequenceIterator is the iterator that references elements
                * in the original sequence. It is basically the \c value_type for this
                * data stucture
                * \li \c tree_iterator is the iterator that is used in the underlying
                * red-black tree, it references DataNodes.
                *
                */


        template<class SequenceIterator, class Geometry,
                                                                                                                                                        class _Compare = std::less<typename SequenceIterator::value_type>,
                                                                                                                                                        class _Compare_PQ = std::less<typename SequenceIterator::value_type>,
                                                                                                                                                        class _Alloc = std::allocator<typename SequenceIterator::value_type> >
        class block_tree_heap
        {
                        // typedefs:

                        typedef typename SequenceIterator::value_type _Key;
                        typedef _Key                                                                                                            key_type;
                        typedef _Key                                                                            value_type;
                        typedef _Compare                                                                        key_compare;
                        typedef _Compare_PQ                                             key_compare_pq;
                        typedef key_type*                                                               key_ptr;
                        typedef typename Geometry::point_type priority_type;

                public:


                                                #define LEFT_EVENT                      0
                                                #define RIGHT_EVENT             1
                                                #define INTERSECTION_EVENT      2
                                                #define INVALID_EVENT           100

                                                struct DataNode
                                                {
                                                                typedef SequenceIterator                                                                                                                                                                                        value_type;
                                                                typedef typename
                                                                                        std::iterator_traits<SequenceIterator>::difference_type
                                                                                                                                                                                                                                                                                                                                                                                                                                                        difference_type;
                                                                typedef char                                                                                                                                                                                                                                                                            event_type;


                                                                value_type block_begin;
                                                                difference_type line_top_pq;
                                                                event_type my_event;
                                                                value_type intersecting;
                                                                priority_type point;
                                                                difference_type gap_begin;
                                                                difference_type gap_size;


                                                                DataNode(value_type l, event_type event = RIGHT_EVENT)
                                                                {
                                                                        line_top_pq = 0;
                                                                        //intersecting  = NOTHING;
                                                                        my_event=event;
                                                                        //point=(*l)[1];
                                                                        gap_size = 1; //size of 1
                                                                }

                                                                ~DataNode(){

                                                                }

/*                                                                      DataNode(const DataNode& rhs){
                                                                                block_begin = rhs.block_begin;
                                                                                my_event = rhs.my_event;
                                                                                point = rhs.point;
                                                                                intersecting = rhs.intersecting;
                                                                }

                                                                const DataNode& operator=(const DataNode& rhs)
                                                                {
                                                                        if(gap_size!=rhs.gap_size)
                                                                        {
                                                                                cout<<"Fatal error: trying to copy nodes with different block sizes\n";
                                                                                exit(1);
                                                                        }
                                                                        block_begin =  rhs.block_begin;
                                                                        line_top_pq =  rhs.line_top_pq;
                                                                        my_event = rhs.my_event;
                                                                        intersecting = rhs.intersecting;
                                                                        point = rhs.point;
                                                                        gap_begin = rhs.gap_begin;
                                                                        gap_size = rhs.gap_size;
                                                                        //next_of_the_same_gap_size is not copied
                                                                        return *this;
                                                                }
*/
//                                                              void right_event(){
//                                                                      my_event = RIGHT_EVENT;
//                                                                      point = block_begin[1]; should be KeyOfValuePQ()(*block_begin)
//                                                              }

//                                                              void intersection_event(priority_type p, DataNode* n ){
//                                                                      my_event = INTERSECTION_EVENT;
//                                                                      point = p;
//                                                                      intersecting = n;
//                                                              }

                                                                DataNode(){}

                                                                const value_type& top_BST() const
                                                                {
                                                                        return block_begin;
                                                                }

                                                                value_type top_PQ(value_type my_gap,
                                                                                                                                                                                                         difference_type block_size,
                                                                                                                                                                                                         bool full_block)
                                                                {

                                                                        if(full_block)
                                                                        {
                                                                                return line_top_pq+block_begin;
                                                                        }
                                                                        else
                                                                        {
                                                                                return (my_gap+line_top_pq)-block_size;
                                                                        }
                                                                }

                                                                priority_type get_priority()
                                                                {
                                                                        return point;
                                                                }

                                                                /*
                                                                 * \brief Sets line_top_pq offset
                                                                 *
                                                                 * @param new_top_pq iterator to the line segment that should
                                                                 * become the highest priority one in the node
                                                                 * @param my_gap beginning of the gap of the current node
                                                                 * @param block_size block size of the node
                                                                 * @full_block \c true if the current node has a full block
                                                                 *
                                                                 * @pre new_top_pq must be in the current node
                                                                 * either in the full block or the gap
                                                                 *
                                                                 * Even if the full block for the node does not exist
                                                                 * the offset includes the full-block size to simplify calculations
                                                                 */
                                                                void inline set_top_pq(const value_type& new_top_pq,
                                                                                                                                                                                                const value_type& my_gap,
                                                                                                                                                                                                difference_type block_size,
                                                                                                                                                                                                bool full_block)
                                                                {
                                                                        if(full_block && new_top_pq>=block_begin && new_top_pq<block_begin+block_size)
                                                                        {
                                                                                line_top_pq = new_top_pq-block_begin;
                                                                        }
                                                                        else
                                                                        {
                                                                                line_top_pq = new_top_pq-my_gap+block_size;
                                                                        //cout<<"NO fulll block top pq "<<line_top_pq<<endl;
                                                                        }
                                                                }


                                                                /*
                                                                 * \brief Returns true if the block
                                                                 * contains a full block and the gap is one less
                                                                 * than the full block.
                                                                 *
                                                                 * This means that if one more element is added, the block
                                                                 * needs to be broken up into two blocks
                                                                 *
                                                                 * @param size full block size
                                                                 */
                                                                bool is_full_gap(difference_type size, value_type last)
                                                                {
                                                                        //TODO: IF THERE IS NO BLOCK_BEGIN, IS IT LAST OR IS IT GAP_BEGIN
                                                                                return gap_size==size-1;
                                                                }
                                        };
                                                struct _M_key_comp
                                                {
/*                                                      bool operator()(const DataNode& a, const DataNode& b)
                                                        {

                                                                        return key_compare()(*(a.top_BST()),*(b.top_BST()));
                                                        }

                                                        bool operator()(const SequenceIterator& a, const DataNode& b)
                                                        {
                                                                        return key_compare()(*a, *b.top_BST());
                                                        }

*/                                                      bool operator()(const SequenceIterator& a, const SequenceIterator& b)
                                                        {
                                                                        return key_compare()(*a, *b);
                                                        }

/*                                                      bool operator()(DataNode& a, SequenceIterator& b)
                                                        {
                                                                        return key_compare()(*(a.top_BST()), *b);
                                                        }
*/                                              };

                                                //TODO:do not create anything on the fly

                                                struct _M_key_comp_pq
                                                //MAKE SURE THAT IN THE INTERNAL TREE WE COMPARE BY NODES NOT BY SequenceIterator
                                                {
                                                        bool operator()(const DataNode& a, const DataNode& b)
                                                        {
                                                                        return key_compare_pq()(a.point, b.point);
                                                        }
                                                };

                                                //TODO:need to chnage this to reference _M_first, _M_last, gaps_offsets
                                                struct _M_KeyOfValue
                                                {
                                                        const SequenceIterator& operator()(const DataNode& a)
                                                        {
                                                                return a.block_begin;
/*                                                              if(a.block_begin!=no_full_block())
                                                                {
                                                                        return a.block_begin;
                                                                }

                                                        if(block.gap_size!=0)
                                                                        return (block.gap_begin)+_M_first+gaps_offsets[block.gap_size];
                                                                else
                                                                        return _M_last;*/

                                                        }
                                                };



                public:
                 private:
//                      typedef typename DataNode::_M_key_comp    _M_key_comp;
//                      typedef typename DataNode::_M_key_comp_pq _M_key_comp_pq;
//                      typedef typename DataNode::_M_KeyOfValue  _M_KeyOfValue;
                 public:
                        typedef typename _Alloc::pointer pointer;
                        typedef typename _Alloc::const_pointer const_pointer;
                        typedef typename _Alloc::reference reference;
                        typedef typename _Alloc::const_reference const_reference;
                 //TODO: chnage these
                        typedef         block::_Rb_tree<SequenceIterator, DataNode,
                                         _M_KeyOfValue, _M_key_comp ,_M_key_comp_pq, _Alloc> _Rep_type;
                                typedef typename DataNode::event_type event_type;
                                typedef typename DataNode::priority_type priority_type;
                        typedef typename _Rep_type::const_iterator const_iterator;
                        typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
                        typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
                        typedef typename _Rep_type::size_type size_type;
                        typedef typename _Rep_type::difference_type difference_type;
                        typedef typename _Rep_type::allocator_type allocator_type;
                                        private:
                        typedef typename _Rep_type::iterator tree_iterator;
                                        public:

                        template <class _Tp>
                        /*
                         * TODO: encasulate tree iterator in _space_th ietartor
                         * such that every space_iter has
                         * 1. tree_iterator
                         * 2. sequence_iterator
                         */
                                class _Space_TH_Iterator: public tree_iterator
                                {
                                        public:
                                                typedef typename _Tp::value_type::value_type value_type;
                                                typedef value_type& reference;
                                                                typedef value_type* pointer;

                                                                typedef typename tree_iterator::_Base_ptr  _Base_ptr;
                                                                typedef typename tree_iterator::_Link_type _Link_type;
                                                                typedef _Space_TH_Iterator<_Tp> _Self;

                                                                        _Space_TH_Iterator():tree_iterator(){};
                                                                        _Space_TH_Iterator (tree_iterator a):_M_node(a._M_node){}
                                                                        _Space_TH_Iterator(_Link_type __x): _M_node(__x) { }

                                                                        reference
                                                                        operator*() const
                                                                        {return *((static_cast<_Link_type>(_M_node)->_M_value_field).top_BST());}

                                                                        pointer
                                                                        operator->() const
                                                                        {return &((static_cast<_Link_type>(_M_node)->_M_value_field).top_BST()); }

                                                                        _Tp&
                                                                        data()
                                                                {return ((static_cast<_Link_type>(_M_node)->_M_value_field)); }


                                                                        _Self&
                                                                        operator++()
                                                                        {
                                                                                        _M_node = _Rb_tree_increment(_M_node);
                                                                                        return *this;
                                                                        }

                                                                        _Self
                                                                        operator++(int)
                                                                        {
                                                                                        _Self __tmp = *this;
                                                                                        _M_node = _Rb_tree_increment(_M_node);
                                                                                        return __tmp;
                                                                        }

                                                                        _Self&
                                                                        operator--()
                                                                        {
                                                                                        _M_node = _Rb_tree_decrement(_M_node);
                                                                                        return *this;
                                                                        }

                                                                        _Self
                                                                        operator--(int)
                                                                        {
                                                                                        _Self __tmp = *this;
                                                                                        _M_node = _Rb_tree_decrement(_M_node);
                                                                                        return __tmp;
                                                                        }

                                                                        bool
                                                                        operator==(const _Self& __x) const
                                                                        { return _M_node == __x._M_node; }

                                                                        bool
                                                                        operator!=(const _Self& __x) const
                                                                        { return _M_node != __x._M_node; }

                                                                        _Base_ptr _M_node;
                                        };
                                                typedef  _Space_TH_Iterator<DataNode> iterator;
                                                typedef typename std::iterator_traits<SequenceIterator>::difference_type block_size_type;

                        _Rep_type _M_t;  // red-black tree representing my_tree_heap

                        //\todo TODO: block size needs to be determined in the constructor
                        block_size_type block_size;

                        SequenceIterator _M_first;
                        SequenceIterator _M_last;

                        SequenceIterator _M_last_in_th;

                        //iterator to the node that points to the last gap of any size>0
                        tree_iterator _M_last_gap;

//                      SequenceIterator* gaps;

                        tree_iterator* left_most_gap;
   block_size_type* gaps_offsets;
                        _Compare                                                                _comp;
                        _Compare_PQ                                     _comp_pq;
                public:

                        // allocation/deallocation
                                block_tree_heap(SequenceIterator f, SequenceIterator l, int b = 1)
                                : _M_t(_M_key_comp(), _M_key_comp_pq(), allocator_type()),
                                                _comp(_Compare()), _comp_pq(_Compare_PQ()),block_size(b)
                                {
//cout<<"constructing"<<endl;
                                                _M_first=f;
                                                //beacuse of the offset it is not ok to put _M_last=l
                                                //since the value of pointer may infact be l
                                                //but when offsett is subtracted it a valid number
                                         _M_last=f-1;
                                         _M_last_in_th=f-1;
                                         //the last position is temporary
                                                gaps_offsets = new block_size_type [int(b)+1];
                                                left_most_gap = new tree_iterator [int(b)+1];

                                         for(int i=0; i<int(b+1); ++i)
                                         {
                                                gaps_offsets[i]=0;
                                                left_most_gap[i]=_M_t.end();
                                         }

                                }

                        template<class RandomAccessIterator>
                                block_tree_heap(RandomAccessIterator first, RandomAccessIterator last,
                                                                                                                                                                                const _Compare& __comp,
                                                                                                                                                                                const _Compare_PQ& __comp_pq,
                                                                                                                                                                                const allocator_type& __a = allocator_type())
                                                                : _M_t(__comp, __comp_pq, __a), _comp(__comp), _comp_pq(__comp_pq)
                                {
                                        //TODO:
                                }

                                ~block_tree_heap()
                                {
                                        //TODO add deletes
                                }

private:
                        block_tree_heap(const block_tree_heap<_Key,Geometry, _Compare,_Compare_PQ,_Alloc>& __x)
                        {}
public:


                void print()
                {
                        //cout<<"BST\n";

                        for(tree_iterator it=_M_t.begin(); it!=_M_t.end(); ++it)
                        {
                                //cout<<"+==============+"<<endl;
//                              //cout<<"Priority: "<<it->point<<endl;
//                              //cout<<"Event: "<<(int)it->my_event<<endl;
//                              //cout<<"Top pq : "<<*(get_top_pq(it))<<endl;
                                //cout<<"Next gap :";
                                        if(_M_t.get_gap_next(it)!=_M_t.end())
                                        {
                                                cout<<_M_t.get_gap_next(it)->block_begin[0];
                                        }
                                        else
                                        {
                                                cout<<"null";
                                        }
                                        cout<<endl;
                                cout<<"Prev gap :";
                                        if(_M_t.get_gap_prev(it)!=_M_t.end())
                                        {
                                                cout<<_M_t.get_gap_prev(it)->block_begin[0];
                                        }
                                        else
                                        {
                                                cout<<"null";
                                        }
                                cout<<endl;
                                cout<<"Gap "<<get_gap(it)-_M_first<<" ";
                                if(get_gap(it)!=_M_last)
                                {
                                        cout<<""<<get_gap(it)-_M_first<<"";
                                }else
                                {
                                        cout<<"null";
                                }
                                cout<<"\nGap size ";
                                        cout<<it->gap_size;


                                cout<<endl<<endl;;

                                if(it->block_begin!=no_full_block())
                                {
                                        for(int i=0; i<block_size; ++i)
                                        {
                                                cout<<""<<it->block_begin[i]<<" ";
//                                              if(successor(it,it->block_begin+i)!=_M_last)
//      cout<<"N: "<<*successor(it,it->block_begin+i);
//      else
//      cout<<"N: null";

                                        }
                                }
                        cout<<endl<<"..................."<<endl;
                                if(it->gap_size!=0)
                                {
                                        for(int i=0; i<it->gap_size; ++i)
                                        {
                                                cout<<""<<get_gap(it)[i]<<" ";
//                                              if(successor(it,get_gap(it)+i)!=_M_last)
//      cout<<"N: "<<*successor(it,get_gap(it)+i);
//      else
//      cout<<"N: null";
                                        }
                                }
                                cout<<endl<<"+==============+"<<endl;
                        }

                        cout<<endl<<"---------"<<endl;
                                cout<<"Offsets:\n";
                                for(int i=0; i<block_size; i++)
                                {
                                        cout<<i<<" "<<gaps_offsets[i]<<endl;
                                }

                                cout<<"Leftmost gaps"<<endl;
                                for(int i=0; i<block_size; i++)
                                {
                                        if(left_most_gap[i]==_M_t.end())
                                        {
                                                cout<<i<<"none"<<endl;
                                        }
                                        else
                                        {
                                                cout<<i<<" ["<<(get_gap(left_most_gap[i])-_M_first)<<"] "<<*get_gap(left_most_gap[i])<<endl;
                                        }
                                }

cout<<endl;
                                cout<<"Last gap: ";
                                if(_M_last_gap!=_M_t.end())
                                {
                                        cout<<"["<<get_gap(_M_last_gap)-_M_first<<"]"<<endl;
                                }
                                else
                                {
                                        cout<<"nill"<<endl;
                                }


                }
        public:


                        SequenceIterator no_full_block()
                        {
                                return _M_last;
                        }

                        const iterator insert(SequenceIterator new_line)
                        {

                                #ifdef DEBUG
                                        //cout<<new_line-_M_first<<" "<<_M_last_in_th-_M_first<<endl;
                                        if(new_line!=_M_last_in_th+1)
                                        {
                                                cerr<<"Fatal error: new_line!=_M_last_in_th+1\n";
                                                exit(1);
                                        }
                                #endif

                                std::pair<tree_iterator, bool> p;
                                //find the first node whose smallest element is larger
                                //that is, a node where a the top line is located
                                //below new_line
                                tree_iterator it = _M_t.find(new_line);
                                //cout<<"Finished find it==end is"<<(it==_M_t.end())<<endl;

                                //tree is empty
                                if(it==_M_t.end() && it==_M_t.begin())
                                {
                                        //cout<<"Starting insert one node tree"<<endl;
                                        p=_M_t.insert_unique(create_node(new_line));
                                        if(p.second)
                                        {
                                                it=_M_t.PQ_insert(p.first);
                                                left_most_gap[it->gap_size]=it;
                                         _M_t.set_gap_next(it, _M_t.end());
                                         _M_t.set_gap_prev(it, _M_t.end());
                                                _M_last_in_th++;
                                                it->block_begin=no_full_block();
                                                //cout<<"Setting "<<*new_line<<" as top pq"<<endl;
                                                set_top_pq(it, new_line);
                                        }
                                        //cout<<"Finish insert one node tree"<<endl;
                                        _M_last_gap = it;
                                return it;
                                }
                                else
                                {
                                        //else, insert into a node before it
                                        if(it!=_M_t.begin())
                                        {
                                                //cout<<"I was NOT begins, hence --it!"<<endl;
                                                --it;
                                                //cout<<"it = "<<*(it->top_BST())<<endl;
                                        }

                                        //if gap is full, split
                                        if(it->is_full_gap(block_size, _M_last))
                                        {
                                                //cout<<"Starting insert full node. gapsize ="<<it->gap_size<<endl;
                                                #ifdef DEBUG
                                                        if(it->gap_size!=block_size-1)
                                                        {
                                                                cerr<<"Fatal error: max gap size is not the same as gap size of full block!\n";
                                                                exit(1);
                                                        }
                                                #endif


                                                //TODO:if gapsize becomes 0, where should next point to

                                                //if the gap is full, there are two cases
                                                 //1.if there is a full block, need to insert and make the current gap a full block
                                                 //2.otherwise  need to insert and split into two

                                         //case 1
                                         if(it->block_begin==no_full_block())
                                         {
                                                //cout<<"starting NOT full block, but full gap"<<endl;
                                                        insert_into_gap(it, new_line);
                                                        it->block_begin=get_gap(it);
                                                        //TODO: need to move over to the other side of dead elements
                                                        it->gap_size=0;
                                                 left_most_gap[block_size]=_M_t.end();
                                                 //cout<<"_M_last_in_th is "<<_M_last_in_th-_M_first<<endl;
                                                 _M_last_in_th++;
//                                              update_top_pq(it);
                                                        return it;
                                         }

                                         //case 2
                                                 SequenceIterator new_block;
                                                //cout<<"starting full block, AND full gap"<<endl;
                                                        insert_into_gap(it, new_line);
                                                        //cout<<"Finished insert_into_gap"<<endl;
                                                        //TODO: need to move over to the other side of dead elements
                                                        new_block=get_gap(it);
                                                        std::pair<tree_iterator, bool> p;
                                                        p=_M_t.insert_unique(create_node(new_block));
                                                        if(p.second)
                                                        {

                                                        /*for(SequenceIterator i=get_gap(it); i<get_gap(it)+it->gap_size; i++)
                                                        cout<<*i<<" ";
                                                        cout<<endl;
                                                        for(SequenceIterator i=it->block_begin; i<it->block_begin+block_size; i++)
                                                        cout<<*i<<" ";
*/
                                                        if(left_most_gap[block_size]==it)
                                                        {
                                                                //cout<<"IM LEFTMOST"<<endl;
                                                                if(_M_t.get_gap_next(it)->gap_size!=block_size-1)
                                                                {
                                                        left_most_gap[block_size-1]=_M_t.end();
                                                        gaps_offsets[block_size-1]=0;
                                                                }
                                                                else
                                                                {
                                                                        left_most_gap[block_size-1]=_M_t.get_gap_next(it);
                                                                }
                                                        }
                                                //for consistancy
                                                left_most_gap[block_size]=_M_t.end();
                                        gaps_offsets[block_size]=0;

                                                        //cout<<"starting update_pointers"<<endl;
                                                        if(_M_t.get_gap_next(it)!=_M_t.end())
                                                        {
                                                                _M_t.set_gap_prev(_M_t.get_gap_next(it), _M_t.end());
                                                        }
                                                 _M_t.set_gap_next(it, _M_t.end());

                                                 if(_M_t.get_gap_prev(it)!=_M_t.end())
                                                        {
                                                                _M_t.set_gap_next(_M_t.get_gap_prev(it), _M_t.get_gap_next(it));
                                                        }
                                                        else
                                                        {
                                                                if(_M_last_gap==it && _M_t.get_gap_next(it)==_M_t.end())
                                                                {
                                                                        _M_last_gap=_M_t.get_gap_prev(it);
                                                                }
                                                        }

                                                 _M_t.set_gap_prev(it, _M_t.end());


       it->gap_size=0;
                                                        it=_M_t.PQ_insert(p.first);
                                                        //TODO: is this correct, should it point to gap size of 1
                                                        _M_t.set_gap_next(it, _M_t.end());
                                                 _M_t.set_gap_prev(it, _M_t.end());
                                                        _M_last_in_th++;
                                                        it->block_begin=new_block;
                                                        it->gap_size=0;
                                                        return it;
                                                }
                                                //cout<<"Finish insert "<<endl;
//                                                                                              update_top_pq(it);
                                        return it;

                                        }
                                        else //node is not full
                                        {
                                                //cout<<"Starting insert not full node, gapsize "<<it->gap_size<<endl;
                                        insert_into_gap(it, new_line);
                                        _M_last_in_th++;
                                                //cout<<"Set gap to be "<<_M_first[get_gap(it)-_M_first-gaps_offsets[it->gap_size]]<<endl;
//                                                                                      update_top_pq(it);
                                        return it;
                                        }

                                }
                        }


                        void insert_into_gap(tree_iterator it, SequenceIterator new_line)
                        {
                                                if(it->gap_size==0)
                                                {
                                                                if(left_most_gap[1]==_M_t.end())
                                                                {
                                                                        left_most_gap[1]=it;
                                                                }

                                                                if(_M_last_gap!=_M_t.end() && _M_last_gap!=it)
                                                                {
                                                                        _M_t.set_gap_next(_M_last_gap,it);
                                                                        _M_t.set_gap_prev(it, _M_last_gap);
                                                                }
                                                                it->gap_size++;
                                                                set_gap(it, new_line);
                                                                update_block_after_insert(it, new_line);
                                                                _M_last_gap=it;
                                                                return;
                                                }

                                                tree_iterator tmp=left_most_gap[it->gap_size];
                                                //1. swap with the first gap with the same size
                                                if(get_gap(it)!=_M_last && get_gap(it)!=get_leftmost_gap(it->gap_size))
                                                {
                                                        //cout<<"get_gap(it)!=get_leftmost_gap(it->gap_size)"<<endl;
                                                        swap_gaps(get_gap(it), get_leftmost_gap(it->gap_size), it->gap_size);
                                                        //swap gap pointers
                                                        SequenceIterator t=get_gap(it);
                                                        //reset gap becuase when swapping location chnaged
                                                        set_gap(it, get_leftmost_gap(it->gap_size));
                                                        set_gap(left_most_gap[it->gap_size], t);
                                                        //cout<<"swapped blocks\n";
//                                                              <<it->block_begin[0]<<" "<<get_gap(it)-_M_first<<" "<<it->gap_size<<" "<<endl
//                                                              <<left_most_gap[1]->block_begin[0]<<" "<<get_gap(left_most_gap[1])-_M_first<<" "<<left_most_gap[1]->gap_size<<endl;

                                                        _M_t.swap_gap_next(it, left_most_gap[it->gap_size]);
                                                        _M_t.swap_gap_prev(it, left_most_gap[it->gap_size]);

                                                        if(_M_t.get_gap_prev(it)!=_M_t.end())
                                                        {
                                                                _M_t.set_gap_next(_M_t.get_gap_prev(it), it);
                                                        }
                                                        if(_M_t.get_gap_next(it)!=_M_t.end())
                                                        {
                                                                _M_t.set_gap_prev(_M_t.get_gap_next(it), it);
                                                        }

                                                        if(_M_t.get_gap_prev(left_most_gap[it->gap_size])!=_M_t.end())
                                                        {
                                                                _M_t.set_gap_next(_M_t.get_gap_prev(left_most_gap[it->gap_size]), left_most_gap[it->gap_size]);
                                                        }
                                                        if(_M_t.get_gap_next(left_most_gap[it->gap_size])!=_M_t.end())
                                                        {
                                                                _M_t.set_gap_prev(_M_t.get_gap_next(left_most_gap[it->gap_size]), left_most_gap[it->gap_size]);
                                                        }




                                                        //cout<<"updated gap_next and gap_prev"<<endl;


                                                }
                                                else
                                                {
                                                        //cout<<"did not swap"<<endl;
                                                        //swap not needed
                                                }


                                                        //2. move all elements by one
                                                        //place the new element as the first one in the gap
              if(it->gap_size!=0)
              {


                                                                //cout<<"move_blocks("<<get_gap(it)-_M_first<<", _M_last_in_th+1);"<<endl;

                                                        *(get_gap(it))=move_blocks(get_gap(it), _M_last_in_th+1);
                                                                new_line=get_gap(it);

                                                                //cout<<"finished move"<<endl;
//                                                              for(SequenceIterator i=get_gap(it); i<get_gap(it)+it->gap_size+1; ++i)
//                                                              cout<<*i<<endl;

                                                                //need to re-set the gap since, the offsets are now different
                                                                set_gap(it, get_gap(it), it->gap_size+1);

              }
              else
              {
                if(left_most_gap[1]==_M_t.end())
                {
                        left_most_gap[1]=it;
                        gaps_offsets[1]=0;
                        //cout<<"Setting gap"<<endl;
                                                                        set_gap(it, new_line, it->gap_size+1);
                }
                else
                {
                        //cout<<"!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"<<endl;
                        //WHAT IS THIS FOR???
                 it->gap_begin=new_line-get_gap(left_most_gap[1]);
                }
              }

                                                        //3. update offsets for all gaps of size less than or equal it->gap_size
                                                        for(int i=it->gap_size; i>0; i--)
                                                        {
                                                                if(left_most_gap[i]     !=_M_t.end())
                                                                {
                                                                 gaps_offsets[i]+=1;
                                                                }
                                                        }
                                                        //cout<<"updated all offsets"<<endl;

                                                        //3.6.update leftmost pointers for size it->gap_size+1
                                                        update_left_most_pointer(it, it->gap_size+1);

                                                        //3.7.update leftmost pointers for size it->gap_size
                                                        //after swap (or without it)
                                                        //it was the leftmost of its size
                                                        //since, we're are going to increment its size,
                                                        //the leftmost gap of same size must become the new leftmost
                                                        if(_M_t.get_gap_next(it)!=_M_t.end())
                                                        {

                                                                if(_M_t.get_gap_next(it)->gap_size==it->gap_size)
                                                                {
                                                                        left_most_gap[it->gap_size]=_M_t.get_gap_next(it);
                                                                }
                                                                else
                                                                {
                                                                        left_most_gap[it->gap_size]=_M_t.end();
                                                                        gaps_offsets[it->gap_size]=0;
                                                                }
                                                        }
                                                        else
                                                        {
                                                                                                                                        //cout<<"DOING THAT"<<endl;
                                                                        left_most_gap[it->gap_size]=_M_t.end();
                                                                        gaps_offsets[it->gap_size]=0;
                                                        }

                                                        //3.8 update last gap pointer
                                                        //a. if no swap, nothing chnages
                                                        //b. if swapped, the one that swapped with may become the last
                                                        if(_M_t.get_gap_next(tmp)==_M_t.end())
                                                        {
                                                                _M_last_gap=tmp;
                                                        }


                                                //5.increase size of the node
                                                it->gap_size++;
                                                //cout<<"increased current size"<<it->gap_size<<endl;

                                                //6.restore order in the block and tree/heap
                                                update_block_after_insert(it, new_line);
                        }


void update_left_most_pointer(tree_iterator it, int new_size)
{
         //cout<<"Updating leftmost"<<endl;
         #ifdef DEBUG
                        if(_M_t.get_gap_prev(it)==_M_t.end())
                        {
                                if(left_most_gap[new_size]!=_M_t.end())
                                {
                                        cerr<<"Fatal error: trying to assign it to leftmost["<<new_size<<"]"
                                                                        <<"which is non-null"<<endl;
                                        exit(-1);
                                }
                        }
                #endif


                        if(left_most_gap[new_size]==_M_t.end())
                        {
                                left_most_gap[new_size]=it;
                                gaps_offsets[new_size]=0;
                                //cout<<"Set leftmost["<<new_size<<"] = it"<<endl;
                        }
                else
                {
                        //cout<<"Leftmost is "<<endl;
                        //cout<<get_gap(left_most_gap[new_size])-_M_first<<endl;
                        _M_t.set_gap_next(_M_t.get_gap_prev(it), it);
                }
}


                        value_type move_blocks(SequenceIterator first, SequenceIterator last)
                        {

                                        //cout<<"In move_block"<<endl;
                                        //cout<<"last= "<<last-_M_first<<" "<<endl;
                                        //cout<<"first= "<<first-_M_first<<" "<<endl;
if(first==last)
 return *first;
                                        value_type tmp = *first;
                                        first++;
                                        for(;first!=last+1; ++first)
                                        {
                                                //cout<<"moving "<<*first<<endl;
                                                        std::swap(*first, tmp);
                                        }
                                        //cout<<"finished move_block"<<endl;
                                        return tmp;
                        }

                        //TODO:
                        // it is not necessary to perform the full
                        //scan after insert, but needs to be done after delete
                        void update_top_pq(tree_iterator it)
                        {
                                SequenceIterator top_block=_M_last, top_gap=_M_last, tmp;
                                point_type top_priority_block, top_priority_gap;
                                char type_block, type_gap;
                                std::pair<bool, point_type> x;


                                if(it->block_begin!=no_full_block())
                                {
                                        //cout<<"Updating PQ in block"<<endl;
                                        top_block=
                                                std::min_element(it->block_begin, it->block_begin+block_size, _comp_pq);
                                 top_priority_block = (*top_block)[1];
                                 type_block = RIGHT_EVENT;

                                //TODO:watch out for block size 2
                                        for(SequenceIterator i=it->block_begin; i!=it->block_begin+block_size-1; i++)
                                        {
                                                x=intersection(*i, *(i+1));
                                                if(x.first && _comp_pq(top_priority_block, x.second))
                                                {
                                                                top_block=i;
                                                                top_priority_block=x.second;
                                                                type_block=INTERSECTION_EVENT;
                                                }
                                        }

                                 if(it->gap_size!=0)
                                 {
                                         x=intersection(*(it->block_begin+block_size-1), *get_gap(it));
                                         if(x.first && _comp_pq(top_priority_block,x.second))
                                         {
                                                         top_block=it->block_begin+block_size-1;
                                                         top_priority_block = x.second;
                                                         type_block=INTERSECTION_EVENT;
                                         }
                                 }
                                }

                                if(it->gap_size!=0)
                                {
                                                                                //cout<<"Updating PQ in gap"<<endl;
                                        top_gap=
                                                std::min_element(get_gap(it), get_gap(it)+it->gap_size, _comp_pq);
                                        top_priority_gap=(*top_gap)[1];
                                 type_gap = RIGHT_EVENT;

                                        for(SequenceIterator i=get_gap(it); i<get_gap(it)+it->gap_size-1; i++)
                                        {
                                                x=intersection(*i, *(i+1));
                                                if(x.first && _comp_pq(top_priority_gap,x.second))
                                                {
                                                        top_gap=i;
                                                        top_priority_gap=x.second;
                                                        type_gap=INTERSECTION_EVENT;
                                                }
                                        }
//cout<<"After loop top_pq is "<<*top_gap<<endl;
                                        if(successor(it,get_gap(it)+it->gap_size-1)!=_M_last)
                                        {
                                                //cout<<"there is a successor"<<endl;
                                                x=intersection(*(get_gap(it)+it->gap_size-1),
                                                                                                                                                          *successor(it,get_gap(it)+it->gap_size-1));
                                                if(x.first && _comp_pq(top_priority_gap,x.second))
                                                {
                                                        top_gap=get_gap(it)+it->gap_size-1;
                                                        top_priority_gap=x.second;
                                                        type_gap=INTERSECTION_EVENT;
                                                }
                                        }
                                }

                                                                //DONT FORGET EVENTTYPE

                                if(top_block==_M_last)
                                {

                                        #ifdef DEBUG
                                        if(top_gap==_M_last)
                                        {
                                                cerr<<"Fatal error: top_block and top_gap are null in update_top_pq\n";
                                                exit(1);
                                        }
                                        #endif

                                                                                //cout<<"Setting "<<*top_gap<<" as top PQ"<<endl;
                                        set_top_pq(it, top_gap);
                                        it->point=top_priority_gap;
                                        it->my_event=type_gap;
                                }
                                else if(top_gap==_M_last)
                                {
                                        set_top_pq(it, top_block);
                                        it->point=top_priority_block;
                                        it->my_event=type_block;
                                }
                                else if(_comp_pq(top_priority_block, top_priority_gap))
                                {
                                        set_top_pq(it,top_block);
                                        it->point=top_priority_block;
                                        it->my_event=type_block;
                                }
                                else
                                {
                                        set_top_pq(it,top_gap);
                                        it->point=top_priority_gap;
                                        it->my_event=type_gap;
                                }

                        }


                        //Account for blocksize=1;
                        DataNode& create_node(SequenceIterator l)
                        {
                                 DataNode* block = new DataNode(l);
                                        block->gap_begin = l-_M_first;
                                        block->block_begin = l;
                                        return (*block);
                        }


                        inline SequenceIterator get_gap(tree_iterator block)
                        {
                                return get_gap(*block);
                        }

                 inline SequenceIterator get_gap(const DataNode& block)
                 {
                        if(block.gap_size!=0){
                                        return (block.gap_begin)+_M_first+gaps_offsets[block.gap_size];
                        }
                                else
                                        return _M_last;
                 }

                 inline void set_gap(tree_iterator block, SequenceIterator new_gap, block_size_type gap_size)
                 {
                                        block->gap_begin=new_gap - _M_first-gaps_offsets[gap_size];
                                        //cout<<"Setting gap to be "<<block->gap_begin<<" offset: "<<gaps_offsets[gap_size]<<endl;
                 }

inline void set_gap(tree_iterator block, SequenceIterator new_gap)
{
        set_gap(block, new_gap, block->gap_size);
}




                        inline SequenceIterator get_leftmost_gap(block_size_type size)
                        {
                                return get_gap(left_most_gap[size]);
                        }

                        inline void swap_gaps(SequenceIterator b1, SequenceIterator b2, block_size_type size)
                        {
                                std::swap_ranges(b1,b1+size, b2);
                                //cout<<"-----\n";
/*                              for(SequenceIterator i=b1;i!=b1+size; ++i)
                                //cout<<*i<<endl;
                                cout<<"-----\n";
                                for(SequenceIterator i=b2;i!=b2+size; ++i)
                                cout<<*i<<endl;
*/

                        }

                        block_size_type max_gap_size()
                        {
                                for(int i=block_size-1; i>1; --i)
                                {
                                        if(left_most_gap[i]!=_M_last)
                                        {
                                                return block_size_type(i);
                                        }
                                }

                        }

                        void update_block_after_insert(tree_iterator& block, SequenceIterator new_el)
                        {
                                //new element just inserted
                                SequenceIterator tmp=new_el;
                                value_type tmp_new_el = *new_el;
                                //cout<<"New_el is "<<*new_el<<endl;
                                //cout<<"Current top_pq "<<*get_top_pq(block)<<endl;

                                //if new element is smaller than the largest element in the
                                //block, both block and gap need to be sorted
                                if(block->block_begin!=no_full_block() && block->gap_size!=0)
                                {
                                        if(_comp(*new_el,*(block->block_begin+block_size-1)))
                                        {
                                                //cout<<"Sorting block and gap"<<endl;
                                                std::swap(*new_el, *(block->block_begin+block_size-1));
                                                std::sort(block->block_begin,block->block_begin+block_size, _comp);
                                                std::sort(get_gap(block), get_gap(block)+(block->gap_size), _comp);
                                                tmp=std::find(block->block_begin,block->block_begin+block_size, tmp_new_el);
                                        }
                                        else
                                        {
                                                std::sort(get_gap(block), get_gap(block)+(block->gap_size), _comp);
                                                tmp=std::find(get_gap(block), get_gap(block)+(block->gap_size), tmp_new_el);
                                        }
                                }
                                //only gap needs to be sorted
                                else if(block->gap_size!=0)
                                {
                                        //cout<<"Sorting only gap "<<endl;
                                        std::sort(get_gap(block), get_gap(block)+(block->gap_size), _comp);
                                        tmp=std::find(get_gap(block), get_gap(block)+(block->gap_size), tmp_new_el);
                                }
                                else
                                {
                                        //cout<<"Sorting only block "<<endl;
                                        std::sort(block->block_begin, block->block_begin+block_size, _comp);
                                        tmp=std::find(block->block_begin,block->block_begin+block_size, tmp_new_el);
                                }

                                #ifdef DEBUG
                                        if(tmp_new_el!=*tmp)
                                        {
                                                cerr<<"Fatal error: tmp_new_el!=*tmp  in update_block_after insert"
                                                <<*new_el<<" != "<<*tmp<<endl;
                                                exit(1);
                                        }
                                #endif

                                return;
                }

                        inline SequenceIterator get_top_pq(tree_iterator it)
                        {
                                return it->top_PQ(get_gap(it),block_size, !(it->block_begin==no_full_block()));
                        }

                        inline void set_top_pq(tree_iterator it, SequenceIterator new_top)
                        {
                                it->set_top_pq(new_top, get_gap(it), block_size, it->block_begin!=no_full_block());
                                //cout<<*get_top_pq(it)<<"Was  set as top pq"<<endl;
                        }

                        inline event_type get_event(iterator block)
                        {
                                        return (static_cast<typename iterator::_Link_type>(block._M_node)->_M_value_field).my_event;
                        }


         void
         pop()
         {
                 //remove from PQ
                                //remove from BST and destroy
//                              _M_t.erase(_M_t.erase_top_PQ());
         }
                        iterator
                        top() const
                        {
                                return _M_t.get_top();
                        }

                        priority_type get_priority(iterator block)
                        {
                                return (static_cast<typename iterator::_Link_type>(block._M_node)->_M_value_field).get_priority ();
                        }


                        void segment_intersection_event(iterator it)
                        {
//                              _M_t.segment_intersection_event(it._M_node, point, intersecting._M_node);
                }

                        bool empty()
                        {
                        }
private:
                        iterator successor(iterator block)
                        {
                                return ++block;
                        }

                        SequenceIterator successor(tree_iterator node, SequenceIterator line)
                        {

                                //there is a full block and like is not the last
                                if(node->block_begin!=no_full_block())
                                {
                                        if(line < node->block_begin + block_size -1)
                                        {
                                                return line+1;
                                        }
                                        if(get_gap(node)!=_M_last && line == node->block_begin + block_size-1)
                                        {
                                                return get_gap(node);
                                        }
                                }
                                //there is a gap and line is in the gap
                                if(get_gap(node)!=_M_last && line < get_gap(node) + node->gap_size -1)
                                {
                                        return line+1;
                                }
                                if(++node!=_M_t.end())
                                {
                                        return node->block_begin;
                                }
                                return _M_last;
                        }


                        iterator predecessor(iterator block)
                        {

                        }

                 void
                 swap_lines(iterator a, iterator b)
                 {
//                      _M_t._M_swap_nodes(a._M_node, b._M_node);
                 }

                public:

                        // accessors:
                        key_compare
                        key_comp() const
                        { return _M_t.key_comp(); }
                        key_compare_pq
                        key_comp_pq() const
                        {
//              return _M_t.key_comp_pq();
                        }
                        allocator_type
                        get_allocator() const
                        { return _M_t.get_allocator(); }
                        const_iterator
                        begin() const
                        { return _M_t.begin(); }

                        iterator
                        begin()
                        { return _M_t.begin(); }

                        const_iterator
                        end() const
                        { return _M_t.end();}

                        iterator
                        end()
                        { return _M_t.end();}

                        bool
                        empty() const
                        { return _M_t.empty(); }

                        size_type
                        size() const
                        { return _M_t.size(); }

                        void
                        clear()
                        {
                                _M_t.clear();
                        }


private:
                void adjust_PQ(iterator it)
                {
//              _M_t.adjust_PQ(it._M_node);
                }

private:
                        void
                        erase(iterator __position)
                        {
                                 typedef typename _Rep_type::iterator _Rep_iterator;
                                 _M_t.erase((_Rep_iterator&)__position);
                        }
public:

                };
} // namespace

#endif /* _my_tree_heap_H */

---

Code Documentation generated Using Doxygen

Copyright © Ilya Katz and Hervé Brönnimann, 2005, 2006.