1| /*$Id: GapBuffer.hh,v 1.6 2002/04/26 01:21:14 chalky Exp $
    2|  *
    3|  * This source file is a part of the Berlin Project.
    4|  * Copyright (C) 1999 Stefan Seefeld <stefan@berlin-consortium.org> 
    5|  * http://www.berlin-consortium.org
    6|  *
    7|  * This library is free software; you can redistribute it and/or
    8|  * modify it under the terms of the GNU Library General Public
    9|  * License as published by the Free Software Foundation; either
   10|  * version 2 of the License, or (at your option) any later version.
   11|  *
   12|  * This library is distributed in the hope that it will be useful,
   13|  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   14|  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   15|  * Library General Public License for more details.
   16|  *
   17|  * You should have received a copy of the GNU Library General Public
   18|  * License along with this library; if not, write to the
   19|  * Free Software Foundation, Inc., 675 Mass Ave, Cambridge,
   20|  * MA 02139, USA.
   21|  */
   22| #ifndef _GapBuffer_hh
   23| #define _GapBuffer_hh
   24| 
   25| #include <vector>
   26| 
   27| //.
   28| //. the design of a gap buffer should follow the typical behavior
   29| //. when editing text. Editing text has two parts: modifying it
   30| //. and simply browsing it. The text contains a 'cursor', which indicates
   31| //. the actual position. When in editing mode, we have to take care to
   32| //. use smart memory management. For this purpose we introduce a little
   33| //. memory gap into the string where new characters can be inserted,
   34| //. so not on every insert() all the following characters have to be moved
   35| //.
   36| //. a gap buffer is layed out like this:
   37| //.   
   38| //.   |***********************..........**********|
   39| //.   ^                      ^         ^          ^
   40| //.  begin()                gbegin()  gend()     end()
   41| //.
   42| //. the following (in)equalities should always hold:
   43| //. 
   44| //. gend() > gbegin()
   45| //. gend() - gbegin() <= gmaxsize()
   46| //. end() >= gend()
   47| //. 
   48| //.
   49| template <class T, short gapsize>
   50| class GapBuffer : private std::vector<T>
   51| {
   52|   typedef std::vector<T> rep_type;
   53|   typedef typename std::vector<T>::value_type value_type;
   54|   iterator gbegin() { return begin() + gapbegin;}
   55|   iterator gend() { return begin() + gapend;}
   56|   iterator cursor() { return begin() + curs;}
   57|   void newgap()
   58|     {
   59|       rep_type::insert(gbegin(), gapsize, value_type(0));
   60|       gapend += gapsize;
   61|     }
   62|   void movegap(int d)
   63|     {
   64|       if (d > 0)
   65|         {
   66|           if (gend() + d > end()) rep_type::insert(end(), size_type(gend() + d - end()), value_type(0));
   67|           copy(gend(), gend() + d, gbegin());
   68|         }
   69|       else
   70|         copy(rep_type::reverse_iterator(gbegin()), rep_type::reverse_iterator(gbegin() + d), rep_type::reverse_iterator(gend()));
   71|       gapbegin += d, gapend += d;
   72|     }
   73|   size_type gap() { return gapend - gapbegin;}
   74|   void editing() { size_type d = curs - gapbegin; if (d != 0) movegap(d);}
   75|   void compact() { size_type d = end() - gend(); if (d > 0) movegap(d);}
   76| public:
   77|   GapBuffer() : curs(0), gapbegin(0), gapend(0) {}
   78|   size_type size() { compact(); return gbegin() - begin();}
   79|   //. these are methods to control the cursor position. This is a long
   80|   //. description for this group, but it will only be displayed if any of its
   81|   //. contents has a long description. Hmm, but then the group is a child of its
   82|   //. own section so thats okay!
   83|   //.{ Group1
   84|   //. move the cursor one position forward
   85|   void forward()
   86|     {
   87|       if (curs == gapbegin && gend() != end()) curs += gap();
   88|       else if (cursor() < end()) curs++;
   89|     }
   90|   //. move the cursor one position back
   91|   void backward()
   92|     {
   93|       if (curs == gapend) curs -= gap();
   94|       else if (cursor() > begin()) curs--;
   95|     }
   96|   //. shift the cursor d positions
   97|   void shift(size_type d)
   98|     {
   99|       size_type tmp = curs + d;
  100|       if ((curs > gapend && tmp > gapend) || (curs <= gapbegin && tmp <= gapbegin)) curs = tmp;
  101|       else if (d < 0) curs += d - gap();
  102|       else curs += d + gap();
  103|     }
  104|   //. return the current position
  105|   size_type position() { return curs > gapend ? curs - gap() : curs;}
  106|   //. set the current position
  107|   void position(size_type p) { shift(p - curs);}
  108|   //.}
  109|   //. Insert an item
  110|   void insert(value_type u)
  111|     {
  112|       editing();
  113|       if (!gap()) newgap();
  114|       *cursor() = u;
  115|       curs++, gapbegin++;
  116|     }
  117|   void insert(value_type *u, size_type n)
  118|     {
  119|       editing();
  120|       rep_type::insert(cursor(), u, u + n);
  121|       curs += n, gapbegin += n, gapend += n;
  122|     }
  123|   void remove_backward(size_type n)
  124|     {
  125|       if (curs <= gapbegin)
  126|         {
  127|           if (curs < n) n = curs;
  128|           erase(cursor() - n, cursor());
  129|           curs -= n, gapbegin -= n, gapend -= n;
  130|         }
  131|       else if (curs - gapend > n)
  132|         {
  133|           erase(cursor() - n, cursor());
  134|           curs -= n;
  135|         }
  136|       else
  137|         {
  138|           size_type d = curs - gapend;
  139|           erase(gbegin() - (n - d), gbegin());
  140|           erase(cursor() - d, cursor());
  141|           gapbegin -= n - d, gapend -= n - d;
  142|           curs -= n;
  143|         }
  144|     }
  145|   void remove_forward(size_type n)
  146|     {
  147|       if (curs >= gapend)
  148|         {
  149|           if (size_type(end() - cursor()) < n) n = end() - cursor();
  150|           erase(cursor(), cursor() + n);
  151|         }
  152|       else if (gapbegin - curs > n)
  153|         {
  154|           erase(cursor(), cursor() + n);
  155|           gapbegin -= n, gapend -= n;
  156|         }
  157|       else
  158|         {
  159|           size_type d = gapbegin - curs;
  160|           erase(gend(), gend() + (n - d));
  161|           erase(cursor(), cursor() + d);
  162|           gapbegin -= d, gapend -= d;
  163|         }
  164|     }
  165|   const value_type *get() { compact(); return begin();}
  166| private:
  167|   size_type curs, gapbegin, gapend;
  168| };
  169| 
  170| #endif