edbee - Qt Editor Library
gapvector.h
Go to the documentation of this file.
1 
6 #pragma once
7 
8 #include <QChar>
9 #include <QString>
10 
11 //#define GAP_VECTOR_CLEAR_GAP
12 
13 namespace edbee {
14 
15 
18 template <typename T>
19 class GapVector
20 {
21 public:
22  GapVector( int capacity=16 ) : items_(0), capacity_(0), gapBegin_(0), gapEnd_(0) {
23  items_ = new T[capacity];
25  gapBegin_ = 0;
26  gapEnd_ = capacity;
27  growSize_ = 16;
28  }
29 
31  delete items_;
32  }
33 
35  inline int length() const { return capacity_ - gapEnd_ + gapBegin_; }
36  inline int gapSize() const { return gapEnd_ - gapBegin_; }
37  inline int gapBegin() const { return gapBegin_; }
38  inline int gapEnd() const { return gapEnd_; }
39  inline int capacity() const { return capacity_; }
40 
41 
43  void clear()
44  {
45  delete[] items_;
46  capacity_ = 16;
47  items_ = new T[capacity_];
48  gapBegin_ = 0;
50  growSize_ = 16;
51  }
52 
53 
54 protected:
61  void replace( int offset, int length, const T* data ) {
62 //qlog_info() << "** replace: " << offset << "," << length << ": gapBegin:" << gapBegin();
63  // copy the first part
64  if( offset < gapBegin() ) {
65  int len = qMin( gapBegin_-offset, length ); // issue 141, added -offset
66 //qlog_info() << "** A) len:"<<len;
67  memcpy( items_ + offset, data, sizeof(T)*len );
68  data += len; // increase the pointer
69  offset += len;
70  length -= len;
71  }
72 
73  if( 0 < length ) {
74 //qlog_info() << "** B) offset:"<<offset+",gapSize:"<<gapSize()<<",length:"<<length;
75  memcpy( items_ + offset + gapSize(), data, sizeof(T)*length );
76  }
77  }
78 
85  void fill( int offset, int length, const T& data ) {
86 
87  // copy the first part
88  if( offset < gapBegin() ) {
89  int len = qMin( gapBegin_-offset, length );
90  for( int i=0; i<len; ++i ) { items_ [offset + i] = data; }
91  offset += len;
92  length -= len;
93  }
94 
95  if( 0 < length ) {
96  offset += gapSize();
97  for( int i=0; i<length; ++i ) { items_ [offset + i] = data; }
98  }
99  }
100 
101 public:
102 
103 
109  void replace( int offset, int length, const T* data, int newLength ) {
110  int currentLength=this->length();
111  Q_ASSERT( 0 <= offset && ((offset+length) <= currentLength) );
112  Q_UNUSED(currentLength);
113 // Q_ASSERT(data && "You probably mean fill :)" );
114 
115 //if( debug ) {
116 //qlog_info() << "REPLACE: " << offset << length << newLength;
117 //}
118  int gapSize = this->gapSize();
119 
120  // Is it a 'delete' or 'insert' or 'replace' operation
121 
122  // a replace operation (do not perform gap moving)
123  if( length == newLength ) {
124  replace( offset, length, data );
125 
126  // insert operation
127  } else if( length < newLength ) {
128  int gapSizeRequired = newLength - length;
129  ensureGapSize( gapSizeRequired );
130  moveGapTo( offset + length );
131  memcpy( items_ + offset, data, sizeof(T) * newLength );
132  gapBegin_ = offset + newLength;
133 
134  // delete operation
135  } else {
136  moveGapTo( offset );
137  memcpy( items_ + offset, data, sizeof(T) * newLength );
138  gapBegin_ = offset + newLength;
139  gapEnd_ = offset + gapSize + length;
140  }
141 
142  Q_ASSERT( gapBegin_ <= gapEnd_ );
143  Q_ASSERT( this->gapSize() <= capacity_ );
144  Q_ASSERT( this->length() <= capacity_ );
145 
146  }
147 
152  void fill( int offset, int length, const T& data, int newLength ) {
153  int currentLength=this->length();
154  Q_ASSERT( 0 <= offset && ((offset+length) <= currentLength) );
155  Q_UNUSED(currentLength);
156 
157  int gapSize = this->gapSize();
158 
159  // Is it a 'delete' or 'insert' or 'replace' operation
160 
161  // a replace operation (do not perform gap moving)
162  if( length == newLength ) {
163  fill( offset, length, data );
164 
165  // insert operation
166  } else if( length < newLength ) {
167  int gapSizeRequired = newLength - length;
168  ensureGapSize( gapSizeRequired );
169  moveGapTo( offset + length );
170  for( int i=0; i<newLength; ++i ) { items_[offset+i] = data; }
171  gapBegin_ = offset + newLength;
172 
173  // delete operation
174  } else {
175  moveGapTo( offset );
176  for( int i=0; i<newLength; ++i ) { items_[offset+i] = data; }
177  gapBegin_ = offset + newLength;
178  gapEnd_ = offset + gapSize + length;
179  }
180 
181  Q_ASSERT( gapBegin_ <= gapEnd_ );
182  Q_ASSERT( this->gapSize() <= capacity_ );
183  Q_ASSERT( this->length() <= capacity_ );
184 
185  }
186 
188  void append( T t ) {
189  replace( length(), 0, &t, 1 );
190  }
191 
193  void append( const T* t, int length ) {
194  replace( this->length(), 0, t, length );
195  }
196 
197 
199  T at( int offset ) const {
200  Q_ASSERT( 0 <= offset && offset < length() );
201  if( offset < gapBegin_ ) {
202  return items_[offset];
203  } else {
204  return items_[gapEnd_ + offset - gapBegin_];
205  }
206  }
207 
209  void set( int offset, const T& value ) {
210  Q_ASSERT( 0 <= offset && offset < length() );
211  if( offset < gapBegin_ ) {
212  items_[offset] = value;
213  } else {
214  items_[gapEnd_ + offset - gapBegin_] = value;
215  }
216  }
217 
218 
220  T& operator[]( int offset ) {
221  Q_ASSERT( 0 <= offset && offset < length() );
222  if( offset < gapBegin_ ) {
223  return items_[offset];
224  } else {
225  return items_[gapEnd_ + offset - gapBegin_];
226  }
227  }
228 
231  T& rawAt( int index ) {
232  Q_ASSERT(index < capacity_);
233  return items_[index];
234  }
235 
236 
238  void copyRange( QChar* data, int offset, int length ) const {
239 
240 //AB__CD"
241 //qlog_info() << "copyRange" << offset << length;
242  if( !length ) { return; }
243  Q_ASSERT( 0 <= offset && offset < this->length() );
244  Q_ASSERT( (offset+length) <= this->length() );
245 
246  // copy the first part
247  if( offset < gapBegin() ) {
248  int len = qMin( gapBegin_-offset, length );
249 //qlog_info() << " - 1: memcpy: offset=" << offset << ", len=" << len << items_[offset];
250  memcpy( data, items_ + offset, sizeof(T)*len );
251  data += len; // increase the pointer
252  offset += len;
253  length -= len;
254  }
255 
256  if( length > 0 ) {
257 //qlog_info() << " - 2: memcpy: offset="<<offset << "gapSize=" << gapSize()<< ", length=" << length << items_[offset + gapSize()];
258  memcpy( data, items_ + offset + gapSize(), sizeof(T)*length );
259  }
260  }
261 
262 
266  T* data() {
267  ensureGapSize(1);
268  moveGapTo( length() );
269  items_[length()] = QChar(); // a \0 character
270  return items_;
271  }
272 
273 
274 
277  void moveGapTo( int offset ) {
278  Q_ASSERT( offset <= capacity_);
279  Q_ASSERT( offset <= length() );
280  if( offset != gapBegin_ ) {
281 //qlog_info() << "BEGIN moveGapTo: offset=" << offset << "/ gapBegin_"; // << gapBegin_ << getUnitTestString();
282  int gapSize = this->gapSize();
283 
284  // move the the data right after the gap
285  if (offset < gapBegin_ ) {
286 //qlog_info() << "- move" << offset << "," << gapBegin_ << "(charcount:" << (gapBegin_ - offset)<<")";
287  memmove( items_ + offset + gapSize, items_ + offset, sizeof(T) * (gapBegin_ - offset)); // memmove( target, source, size )
288 
289  } else {
290 //qlog_info() << "- move2: gapBegin_" << gapBegin_ << ", gapEnd_" << gapEnd_ << ", capacity_" << capacity_ << ", gapSize" << gapSize << "(charcount:"<<(offset - gapBegin_)<<")";
291  memmove( items_ + gapBegin_, items_ + gapEnd_, sizeof(T) * (offset - gapBegin_ )); // memmove( target, source, size )
292  }
293  gapBegin_ = offset;
294  gapEnd_ = gapBegin_ + gapSize; //qMin( gapBegin_ + gapSize, capacity_ );
295 
296  }
297  Q_ASSERT( gapBegin_ <= gapEnd_ );
298 
299 #ifdef GAP_VECTOR_CLEAR_GAP
300  memset( items_+gapBegin_, 0, sizeof(T)*(gapEnd_-gapBegin_));
301 #endif
302  }
303 
304 
306  void ensureGapSize( int requiredSize ) {
307  if( gapSize() < requiredSize ) {
308  while( growSize_ < capacity_ / 6) { growSize_ *= 2; }
309  resize(capacity_ + requiredSize + growSize_ - gapSize() );
310  }
311  }
312 
313 
315  void resize(int newSize)
316  {
317  if( capacity_ >= newSize) return;
318  int lengte = length();
319  Q_ASSERT( lengte <= capacity_);
323 //qlog_info() << "BEGIN resize: capacity =" << capacity_<< " => " << newSize;
324 
325 
326  moveGapTo( lengte );
327  T *newChars = new T[ newSize ];
328 
329  if( capacity_ > 0 ) {
330  memmove( newChars, items_, sizeof(T)*lengte );
331  delete[] items_;
332  }
333  items_ = newChars;
334  capacity_ = newSize;
335  gapEnd_ = newSize;
336 
337  // DEBUG gapsize
338 #ifdef GAP_VECTOR_CLEAR_GAP
339  memset( items_+gapBegin_, 0, sizeof(T)*(gapEnd_-gapBegin_));
340 #endif
341 
342 //qlog_info() << "END resize";
343  }
344 
345 
347  void setGrowSize( int size ) { growSize_=size; }
348 
350  int growSize() { return growSize_; }
351 
352 
354  QString getUnitTestString( QChar gapChar = '_' ) const {
355  QString s;
356  int gapBegin = this->gapBegin();
357  int gapEnd = this->gapEnd();
358  int capacity = this->capacity();
359 
360  for( int i=0; i<gapBegin; ++i ) {
361  if( items_[i].isNull() ) {
362  s.append("@");
363  } else {
364  s.append( items_[i] );
365  }
366  }
367  s.append( "[" );
368  for( int i=gapBegin; i<gapEnd; ++i ) {
369  s.append( gapChar );
370  }
371  s.append( ">" );
372  for( int i=gapEnd; i<capacity; ++i ) {
373  if( items_[i].isNull() ) {
374  s.append("@");
375  } else {
376  s.append( items_[i] );
377  }
378  }
379 
380  return s;
381  }
382 
384  QString getUnitTestString2( ) const {
385  QString s;
386  int gapBegin = this->gapBegin();
387  int gapEnd = this->gapEnd();
388  int capacity = this->capacity();
389 
390  for( int i=0; i<capacity;i++ ) {
391  if( i ) { s.append(","); }
392  if( gapEnd == i) s.append(">");
393  s.append( QString("%1").arg( "X" ));
394  if( gapBegin==i ) s.append("[");
395  }
396  return s;
397  }
398 
399 
400 protected:
401 
402  T *items_;
403  int capacity_;
404  int gapBegin_;
405  int gapEnd_;
406  int growSize_;
407 };
408 
409 
411 class QCharGapVector : public GapVector<QChar>
412 {
413 public:
414 
415  QCharGapVector( int size=16 ) : GapVector<QChar>(size){}
416 
418  QCharGapVector( const QString& data, int gapSize ) : GapVector<QChar>( data.length() + gapSize )
419  {
420  memcpy( items_, data.constData(), sizeof(QChar)*data.length() );
421  gapBegin_ = data.length();
422  gapEnd_ = capacity_;
423  }
424 
425 
427  void init( const QString& data, int gapSize )
428  {
429  delete items_;
430  capacity_ = data.length() + gapSize;
431  items_ = new QChar[capacity_];
432  memcpy( items_, data.constData(), sizeof(QChar)*data.length() );
433  gapBegin_ = data.length();
434  gapEnd_ = capacity_;
435  growSize_ = 16;
436  }
437 
439  void replaceString( int offset, int length, const QString& data ) {
440 
441 // qlog_info() << "replace(" << offset << length << data << ") : " << getUnitTestString().replace("\n","|");
442 
443  replace( offset, length, data.constData(), data.length() );
444 
445 // qlog_info() << " ==> " << getUnitTestString().replace("\n","|");
446  }
447 
449  QString mid( int offset, int length ) const
450  {
451  Q_ASSERT( length >= 0 );
452 
453 // QString str( length, QChar() );
454 // this->copyRange( str.data(), offset, length );
455 
456  QChar* data = new QChar[length];
457  copyRange( data, offset, length );
458  QString str( data, length );
459  delete[] data;
460 
461 //qlog_info() << "mid(" << offset << "," << length << ") => " << str.replace("\n","|") << " // " << getUnitTestString().replace("\n","|");
462  return str;
463  }
464 
465 
466 
467 };
468 
469 
473 template <typename T>
475 {
476 public:
477  NoGapVector( int capacity=16 ) {
478  Q_UNUSED(capacity);
479  }
480 
482  }
483 
485  inline int length() const { return items_.size(); }
486  inline int gapSize() const { return 0; }
487  inline int gapBegin() const { return 0; }
488  inline int gapEnd() const { return 0; }
489  inline int capacity() const { return items_.capacity(); }
490 
491 
493  void clear()
494  {
495  items_.clear();
496  }
497 
498 
499 
500 public:
501 
502 
508  void replace( int offset, int length, const T* data, int newLength ) {
509  items_.remove(offset,length);
510  for( int i=0; i < newLength; i++ ) {
511  items_.insert(offset+i,data[i]);
512  }
513  }
514 
519  void fill( int offset, int length, const T& data, int newLength ) {
520  items_.remove(offset,length);
521  for( int i=0; i < newLength; i++ ) {
522  items_.insert(offset+i,data);
523  }
524 
525  }
526 
528  void append( T t ) {
529  items_.append(t);
530  }
531 
533  void append( const T* t, int length ) {
534  for( int i=0; i < length; i++ ) {
535  items_.append(t[i]);
536  }
537  }
538 
539 
541  T at( int offset ) const {
542  return items_.at(offset);
543  }
544 
546  void set( int offset, const T& value ) {
547  items_.replace(offset,value);
548  }
549 
550 
552  T& operator[]( int offset ) {
553  return items_[offset];
554  }
555 
556 /*
558  void copyRange( QChar* data, int offset, int length ) const {
559 
560 //AB__CD"
561 //qlog_info() << "copyRange" << offset << length;
562  if( !length ) { return; }
563  Q_ASSERT( 0 <= offset && offset < this->length() );
564  Q_ASSERT( (offset+length) <= this->length() );
565 
566  // copy the first part
567  if( offset < gapBegin() ) {
568  int len = qMin( gapBegin_-offset, length );
569 //qlog_info() << " - 1: memcpy: offset=" << offset << ", len=" << len << items_[offset];
570  memcpy( data, items_ + offset, sizeof(T)*len );
571  data += len; // increase the pointer
572  offset += len;
573  length -= len;
574  }
575 
576  if( length > 0 ) {
577 //qlog_info() << " - 2: memcpy: offset="<<offset << "gapSize=" << gapSize()<< ", length=" << length << items_[offset + gapSize()];
578  memcpy( data, items_ + offset + gapSize(), sizeof(T)*length );
579  }
580  }
581 */
582 
586 /*
587  T* data() {
588  ensureGapSize(1);
589  moveGapTo( length() );
590  items_[length()] = QChar(); // a \0 character
591  return items_;
592  }
593 */
594 
595 
598 /*
599  void moveGapTo( int offset ) {
600  Q_ASSERT( offset <= capacity_);
601  Q_ASSERT( offset <= length() );
602  if( offset != gapBegin_ ) {
603 //qlog_info() << "BEGIN moveGapTo: offset=" << offset << "/ gapBegin_"; // << gapBegin_ << getUnitTestString();
604  int gapSize = this->gapSize();
605 
606  // move the the data right after the gap
607  if (offset < gapBegin_ ) {
608 //qlog_info() << "- move" << offset << "," << gapBegin_ << "(charcount:" << (gapBegin_ - offset)<<")";
609  memmove( items_ + offset + gapSize, items_ + offset, sizeof(T) * (gapBegin_ - offset)); // memmove( target, source, size )
610 
611  } else {
612 //qlog_info() << "- move2: gapBegin_" << gapBegin_ << ", gapEnd_" << gapEnd_ << ", capacity_" << capacity_ << ", gapSize" << gapSize << "(charcount:"<<(offset - gapBegin_)<<")";
613  memmove( items_ + gapBegin_, items_ + gapEnd_, sizeof(T) * (offset - gapBegin_ )); // memmove( target, source, size )
614  }
615  gapBegin_ = offset;
616  gapEnd_ = gapBegin_ + gapSize; //qMin( gapBegin_ + gapSize, capacity_ );
617  }
618  Q_ASSERT( gapBegin_ <= gapEnd_ );
619 
620  }
621 
622 
624  void ensureGapSize( int requiredSize ) {
625  if( gapSize() < requiredSize ) {
626  while( growSize_ < capacity_ / 6) { growSize_ *= 2; }
627  resize(capacity_ + requiredSize + growSize_ - gapSize() );
628  }
629  }
630 
631 
633  void resize(int newSize)
634  {
635  if( capacity_ >= newSize) return;
636  int lengte = length();
637  Q_ASSERT( lengte <= capacity_);
641 //qlog_info() << "BEGIN resize: capacity =" << capacity_<< " => " << newSize;
642 
643 
644  moveGapTo( lengte );
645  T *newChars = new T[ newSize ];
646 
647  if( capacity_ > 0 ) {
648  memmove( newChars, items_, sizeof(T)*lengte );
649  delete[] items_;
650  }
651  items_ = newChars;
652  capacity_ = newSize;
653  gapEnd_ = newSize;
654 //qlog_info() << "END resize";
655  }
656 
657 
659  void setGrowSize( int size ) { growSize_=size; }
660 
662  int growSize() { return growSize_; }
663 
664 
666  QString getUnitTestString( QChar gapChar = '_' ) const {
667  QString s;
668  int gapBegin = this->gapBegin();
669  int gapEnd = this->gapEnd();
670  int capacity = this->capacity();
671 
672  for( int i=0; i<gapBegin; ++i ) {
673  if( items_[i].isNull() ) {
674  s.append("@");
675  } else {
676  s.append( items_[i] );
677  }
678  }
679  s.append( "[" );
680  for( int i=gapBegin; i<gapEnd; ++i ) {
681  s.append( gapChar );
682  }
683  s.append( ">" );
684  for( int i=gapEnd; i<capacity; ++i ) {
685  if( items_[i].isNull() ) {
686  s.append("@");
687  } else {
688  s.append( items_[i] );
689  }
690  }
691 
692  return s;
693  }
694 */
695 
696 
697 protected:
698 
699  QVector<T> items_;
700 };
701 
702 
703 
704 } // edbee
QCharGapVector(const QString &data, int gapSize)
initializes the vector with a given string
Definition: gapvector.h:418
QCharGapVector(int size=16)
Definition: gapvector.h:415
This class is used to define a gap vector. A Gapvector is split in 2 parts. where the gap is moved to...
Definition: gapvector.h:19
int gapBegin() const
Definition: gapvector.h:37
void fill(int offset, int length, const T &data, int newLength)
this method replaces the given items with a single data item
Definition: gapvector.h:152
int gapEnd_
The end of the gap.
Definition: gapvector.h:405
void resize(int newSize)
resizes the array of data
Definition: gapvector.h:315
void fill(int offset, int length, const T &data)
this method replaces the given text with the given data. because the length of the source and target ...
Definition: gapvector.h:85
void clear()
clears the data
Definition: gapvector.h:493
T & operator[](int offset)
This method return an index.
Definition: gapvector.h:220
int gapSize() const
Definition: gapvector.h:36
QVector< T > items_
This method returns a direct pointer to the 0-terminated buffer This pointer is only valid as long as...
Definition: gapvector.h:699
void replace(int offset, int length, const T *data, int newLength)
this method replaces the given items
Definition: gapvector.h:109
void init(const QString &data, int gapSize)
Initializes the gapvector.
Definition: gapvector.h:427
void setGrowSize(int size)
sets the growsize. The growsize if the amount to reserve extra
Definition: gapvector.h:347
void ensureGapSize(int requiredSize)
this method makes sure there&#39;s enough room for the insertation
Definition: gapvector.h:306
int capacity() const
Definition: gapvector.h:39
T & operator[](int offset)
This method return an index.
Definition: gapvector.h:552
void copyRange(QChar *data, int offset, int length) const
This method copies the given range to the data pointer.
Definition: gapvector.h:238
int capacity() const
Definition: gapvector.h:489
QString getUnitTestString(QChar gapChar='_') const
Converts the &#39;gap-buffer&#39; to a unit-test debugging string.
Definition: gapvector.h:354
T & rawAt(int index)
This method returns the &#39;raw&#39; element at the given location This method does NOT take in account the ...
Definition: gapvector.h:231
QString getUnitTestString2() const
Converts the &#39;gap-buffer&#39; to a unit-test debugging string.
Definition: gapvector.h:384
Copyright 2011-2013 - Reliable Bits Software by Blommers IT.
Definition: commentcommand.cpp:22
QString mid(int offset, int length) const
a convenient method to retrieve a QString part
Definition: gapvector.h:449
T * data()
This method returns a direct pointer to the 0-terminated buffer This pointer is only valid as long as...
Definition: gapvector.h:266
void clear()
clears the data
Definition: gapvector.h:43
void moveGapTo(int offset)
Definition: gapvector.h:277
GapVector(int capacity=16)
Definition: gapvector.h:22
void append(T t)
convenient append method
Definition: gapvector.h:528
void fill(int offset, int length, const T &data, int newLength)
this method replaces the given items with a single data item
Definition: gapvector.h:519
void append(T t)
convenient append method
Definition: gapvector.h:188
~NoGapVector()
Definition: gapvector.h:481
int length() const
returns the used length of the data
Definition: gapvector.h:35
int growSize()
returns the growsize
Definition: gapvector.h:350
void replaceString(int offset, int length, const QString &data)
a convenient string replace function
Definition: gapvector.h:439
NoGapVector(int capacity=16)
Definition: gapvector.h:477
int growSize_
The size to grow extra.
Definition: gapvector.h:406
~GapVector()
Definition: gapvector.h:30
The character vecor to use.
Definition: gapvector.h:411
void replace(int offset, int length, const T *data)
this method replaces the given text with the given data. because the length of the source and target ...
Definition: gapvector.h:61
T at(int offset) const
This method returns the item at the given index.
Definition: gapvector.h:199
void append(const T *t, int length)
another append method
Definition: gapvector.h:533
int gapSize() const
Definition: gapvector.h:486
A special GapVector class that isn&#39;t a gapvector. It forwards it&#39;s request to a normal vector class (...
Definition: gapvector.h:474
int length() const
returns the used length of the data
Definition: gapvector.h:485
void append(const T *t, int length)
another append method
Definition: gapvector.h:193
int gapBegin() const
Definition: gapvector.h:487
int capacity_
The number of reserved bytes.
Definition: gapvector.h:403
T at(int offset) const
This method returns the item at the given index.
Definition: gapvector.h:541
int gapEnd() const
Definition: gapvector.h:488
void replace(int offset, int length, const T *data, int newLength)
this method replaces the given items
Definition: gapvector.h:508
T * items_
The item data.
Definition: gapvector.h:402
int gapEnd() const
Definition: gapvector.h:38
int gapBegin_
The start of the gap.
Definition: gapvector.h:404