ext/scintilla/src/SplitVector.h

   1 // Scintilla source code edit control\r
   2 /** @file SplitVector.h\r
   3  ** Main data structure for holding arrays that handle insertions \r
   4  ** and deletions efficiently.\r
   5  **/\r
   6 // Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>\r
   7 // The License.txt file describes the conditions under which this software may be distributed.\r
   8 \r
   9 #ifndef SPLITVECTOR_H\r
  10 #define SPLITVECTOR_H\r
  11 \r
  12 template <typename T>\r
  13 class SplitVector {\r
  14 protected:\r
  15         T *body;\r
  16         int size;\r
  17         int lengthBody;\r
  18         int part1Length;\r
  19         int gapLength;  /// invariant: gapLength == size - lengthBody\r
  20         int growSize;\r
  21 \r
  22         /// Move the gap to a particular position so that insertion and\r
  23         /// deletion at that point will not require much copying and\r
  24         /// hence be fast.\r
  25         void GapTo(int position) {\r
  26                 if (position != part1Length) {\r
  27                         if (position < part1Length) {\r
  28                                 memmove(\r
  29                                         body + position + gapLength,\r
  30                                         body + position,\r
  31                                         sizeof(T) * (part1Length - position));\r
  32                         } else {        // position > part1Length\r
  33                                 memmove(\r
  34                                         body + part1Length,\r
  35                                         body + part1Length + gapLength,\r
  36                                         sizeof(T) * (position - part1Length));\r
  37                         }\r
  38                         part1Length = position;\r
  39                 }\r
  40         }\r
  41 \r
  42         /// Check that there is room in the buffer for an insertion,\r
  43         /// reallocating if more space needed.\r
  44         void RoomFor(int insertionLength) {\r
  45                 if (gapLength <= insertionLength) {\r
  46                         if (growSize * 6 < size)\r
  47                                 growSize *= 2;\r
  48                         ReAllocate(size + insertionLength + growSize);\r
  49                 }\r
  50         }\r
  51 \r
  52         void Init() {\r
  53                 body = NULL;\r
  54                 growSize = 8;\r
  55                 size = 0;\r
  56                 lengthBody = 0;\r
  57                 part1Length = 0;\r
  58                 gapLength = 0;\r
  59         }\r
  60 \r
  61 public:\r
  62         /// Construct a split buffer.\r
  63         SplitVector() {\r
  64                 Init();\r
  65         }\r
  66 \r
  67         ~SplitVector() {\r
  68                 delete []body;\r
  69                 body = 0;\r
  70         }\r
  71 \r
  72         int GetGrowSize() const {\r
  73                 return growSize;\r
  74         }\r
  75 \r
  76         void SetGrowSize(int growSize_) {\r
  77                 growSize = growSize_;\r
  78         }\r
  79 \r
  80         /// Reallocate the storage for the buffer to be newSize and\r
  81         /// copy exisiting contents to the new buffer.\r
  82         /// Must not be used to decrease the size of the buffer.\r
  83         void ReAllocate(int newSize) {\r
  84                 if (newSize > size) {\r
  85                         // Move the gap to the end\r
  86                         GapTo(lengthBody);\r
  87                         T *newBody = new T[newSize];\r
  88                         if ((size != 0) && (body != 0)) {\r
  89                                 memmove(newBody, body, sizeof(T) * lengthBody);\r
  90                                 delete []body;\r
  91                         }\r
  92                         body = newBody;\r
  93                         gapLength += newSize - size;\r
  94                         size = newSize;\r
  95                 }\r
  96         }\r
  97 \r
  98         /// Retrieve the character at a particular position.\r
  99         /// Retrieving positions outside the range of the buffer returns 0.\r
 100         /// The assertions here are disabled since calling code can be \r
 101         /// simpler if out of range access works and returns 0.\r
 102         T ValueAt(int position) const {\r
 103                 if (position < part1Length) {\r
 104                         //PLATFORM_ASSERT(position >= 0);\r
 105                         if (position < 0) {\r
 106                                 return 0;\r
 107                         } else {\r
 108                                 return body[position];\r
 109                         }\r
 110                 } else {\r
 111                         //PLATFORM_ASSERT(position < lengthBody);\r
 112                         if (position >= lengthBody) {\r
 113                                 return 0;\r
 114                         } else {\r
 115                                 return body[gapLength + position];\r
 116                         }\r
 117                 }\r
 118         }\r
 119 \r
 120         void SetValueAt(int position, T v) {\r
 121                 if (position < part1Length) {\r
 122                         PLATFORM_ASSERT(position >= 0);\r
 123                         if (position < 0) {\r
 124                                 ;\r
 125                         } else {\r
 126                                 body[position] = v;\r
 127                         }\r
 128                 } else {\r
 129                         PLATFORM_ASSERT(position < lengthBody);\r
 130                         if (position >= lengthBody) {\r
 131                                 ;\r
 132                         } else {\r
 133                                 body[gapLength + position] = v;\r
 134                         }\r
 135                 }\r
 136         }\r
 137 \r
 138         T& operator[](int position) const {\r
 139                 PLATFORM_ASSERT(position >= 0 && position < lengthBody);\r
 140                 if (position < part1Length) {\r
 141                         return body[position];\r
 142                 } else {\r
 143                         return body[gapLength + position];\r
 144                 }\r
 145         }\r
 146 \r
 147         /// Retrieve the length of the buffer.\r
 148         int Length() const {\r
 149                 return lengthBody;\r
 150         }\r
 151 \r
 152         /// Insert a single value into the buffer.\r
 153         /// Inserting at positions outside the current range fails.\r
 154         void Insert(int position, T v) {\r
 155                 PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));\r
 156                 if ((position < 0) || (position > lengthBody)) {\r
 157                         return;\r
 158                 }\r
 159                 RoomFor(1);\r
 160                 GapTo(position);\r
 161                 body[part1Length] = v;\r
 162                 lengthBody++;\r
 163                 part1Length++;\r
 164                 gapLength--;\r
 165         }\r
 166 \r
 167         /// Insert a number of elements into the buffer setting their value.\r
 168         /// Inserting at positions outside the current range fails.\r
 169         void InsertValue(int position, int insertLength, T v) {\r
 170                 PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));\r
 171                 if (insertLength > 0) {\r
 172                         if ((position < 0) || (position > lengthBody)) {\r
 173                                 return;\r
 174                         }\r
 175                         RoomFor(insertLength);\r
 176                         GapTo(position);\r
 177                         for (int i = 0; i < insertLength; i++)\r
 178                                 body[part1Length + i] = v;\r
 179                         lengthBody += insertLength;\r
 180                         part1Length += insertLength;\r
 181                         gapLength -= insertLength;\r
 182                 }\r
 183         }\r
 184 \r
 185         /// Ensure at least length elements allocated, \r
 186         /// appending zero valued elements if needed.\r
 187         void EnsureLength(int wantedLength) {\r
 188                 if (Length() < wantedLength) {\r
 189                         InsertValue(Length(), wantedLength - Length(), 0);\r
 190                 }\r
 191         }\r
 192         \r
 193         /// Insert text into the buffer from an array.\r
 194         void InsertFromArray(int positionToInsert, const T s[], int positionFrom, int insertLength) {\r
 195                 PLATFORM_ASSERT((positionToInsert >= 0) && (positionToInsert <= lengthBody));\r
 196                 if (insertLength > 0) {\r
 197                         if ((positionToInsert < 0) || (positionToInsert > lengthBody)) {\r
 198                                 return;\r
 199                         }\r
 200                         RoomFor(insertLength);\r
 201                         GapTo(positionToInsert);\r
 202                         memmove(body + part1Length, s + positionFrom, sizeof(T) * insertLength);\r
 203                         lengthBody += insertLength;\r
 204                         part1Length += insertLength;\r
 205                         gapLength -= insertLength;\r
 206                 }\r
 207         }\r
 208 \r
 209         /// Delete one element from the buffer.\r
 210         void Delete(int position) {\r
 211                 PLATFORM_ASSERT((position >= 0) && (position < lengthBody));\r
 212                 if ((position < 0) || (position >= lengthBody)) {\r
 213                         return;\r
 214                 }\r
 215                 DeleteRange(position, 1);\r
 216         }\r
 217 \r
 218         /// Delete a range from the buffer.\r
 219         /// Deleting positions outside the current range fails.\r
 220         void DeleteRange(int position, int deleteLength) {\r
 221                 PLATFORM_ASSERT((position >= 0) && (position + deleteLength <= lengthBody));\r
 222                 if ((position < 0) || ((position + deleteLength) > lengthBody)) {\r
 223                         return;\r
 224                 }\r
 225                 if ((position == 0) && (deleteLength == lengthBody)) {\r
 226                         // Full deallocation returns storage and is faster\r
 227                         delete []body;\r
 228                         Init();\r
 229                 } else if (deleteLength > 0) {\r
 230                         GapTo(position);\r
 231                         lengthBody -= deleteLength;\r
 232                         gapLength += deleteLength;\r
 233                 }\r
 234         }\r
 235 \r
 236         /// Delete all the buffer contents.\r
 237         void DeleteAll() {\r
 238                 DeleteRange(0, lengthBody);\r
 239         }\r
 240 \r
 241         T* BufferPointer() {\r
 242                 RoomFor(1);\r
 243                 GapTo(lengthBody);\r
 244                 body[lengthBody] = 0;\r
 245                 return body;\r
 246         }\r
 247 };\r
 248 \r
 249 #endif\r