1 4 package gnu.lists; 5 6 11 12 public class GapVector extends AbstractSequence implements Sequence 13 { 14 public SimpleVector base; 15 public int gapStart; 16 public int gapEnd; 17 18 public GapVector(SimpleVector base) 19 { 20 this.base = base; 21 this.gapStart = 0; 22 this.gapEnd = base.size; 23 } 24 25 protected GapVector () 26 { 27 } 28 29 public int size() 30 { 31 return base.size - (gapEnd - gapStart); 32 } 33 34 public boolean hasNext(int ipos) 35 { 36 int index = ipos >>> 1; 37 if (index >= gapStart) 38 index += gapEnd - gapStart; 39 return index < base.size; 40 } 41 42 public int getNextKind(int ipos) 43 { 44 return hasNext(ipos) ? base.getElementKind() : EOF_VALUE; 45 } 46 47 public Object get (int index) 48 { 49 if (index >= gapStart) 51 index += gapEnd - gapStart; 52 return base.get(index); 53 } 54 55 public Object set (int index, Object value) 56 { 57 if (index >= gapStart) 59 index += gapEnd - gapStart; 60 return base.set(index, value); 61 } 62 63 public void fill (Object value) 64 { 65 base.fill(gapEnd, base.size, value); 66 base.fill(0, gapStart, value); 67 } 68 69 public void fillPosRange(int fromPos, int toPos, Object value) 70 { 71 int from = fromPos == -1 ? base.size : fromPos >>> 1; 72 int to = toPos == -1 ? base.size : toPos >>> 1; 73 int limit = gapStart < to ? gapStart : to; 74 for (int i = from; i < limit; i++) 75 base.setBuffer(i, value); 76 for (int i = gapEnd; i < to; i++) 77 base.setBuffer(i, value); 78 } 79 80 protected void shiftGap(int newGapStart) 81 { 82 int delta = newGapStart - gapStart; 83 if (delta > 0) 84 base.shift(gapEnd, gapStart, delta); 85 else if (delta < 0) 86 base.shift(newGapStart, gapEnd + delta, - delta); 87 gapEnd += delta; 88 gapStart = newGapStart; 89 } 90 91 92 protected void gapReserve(int size) 93 { 94 if (size > gapEnd - gapStart) 95 { 96 int oldLength = base.size; 97 int newLength = oldLength < 16 ? 16 : 2 * oldLength; 98 int minLength = oldLength - (gapEnd - gapStart) + size; 99 if (newLength < minLength) 100 newLength = minLength; 101 base.setSize(newLength); 104 int newGapEnd = newLength - oldLength + gapEnd; 105 base.shift(gapEnd, newGapEnd, oldLength - gapEnd); 106 gapEnd = newGapEnd; 107 } 108 } 109 110 111 protected void gapReserve(int where, int size) 112 { 113 gapReserve(size); 114 if (where != gapStart) 115 shiftGap(where); 116 } 117 118 122 123 public int getSegment (int where, int len) 124 { 125 int length = size(); 126 if (where < 0 || where > length) 127 return -1; 128 if (len < 0) 129 len = 0; 130 else if (where + len > length) 131 len = length - where; 132 if (where + len <= gapStart) 135 return where; 136 if (where >= gapStart) 137 return where + (gapEnd - gapStart); 138 if (gapStart - where > (len >> 1)) 140 { 141 shiftGap(where + len); 142 return where; 143 } 144 else 145 { 146 shiftGap(where); 147 return where + (gapEnd - gapStart); 148 } 149 } 150 151 protected int addPos (int ipos, Object value) 152 { 153 int index = ipos >>> 1; 154 if (index >= gapStart) 155 index += gapEnd - gapStart; 156 add(index, value); 157 return ((index + 1) << 1) | 1; 158 } 159 160 public void add(int index, Object o) 161 { 162 gapReserve(index, 1); 163 base.set(index, o); 164 gapStart++; 165 } 166 167 protected void removePosRange(int ipos0, int ipos1) 168 { 169 ipos0 >>>= 1; 170 ipos1 >>>= 1; 171 if (ipos0 > gapEnd) 172 shiftGap(ipos0-gapEnd+gapStart); 173 else if (ipos1 < gapStart) 174 shiftGap(ipos1); 175 if (ipos0 < gapStart) 176 { 177 base.clearBuffer(ipos0, gapStart - ipos0); 178 gapStart = ipos0; 179 } 180 if (ipos1 > gapEnd) 181 { 182 base.clearBuffer(gapEnd, ipos1 - gapEnd); 183 gapEnd = ipos1; 184 } 185 } 186 187 195 196 public int createPos(int index, boolean isAfter) 197 { 198 if (index > gapStart) 199 index += gapEnd - gapStart; 200 return (index << 1) | (isAfter ? 1 : 0); 202 } 203 204 protected boolean isAfterPos(int ipos) 205 { 206 return (ipos & 1) != 0; 207 } 208 209 protected int nextIndex(int ipos) 210 { 211 int index = ipos == -1 ? base.size : ipos >>> 1; 212 if (index > gapStart) 213 index -= gapEnd - gapStart; 214 return index; 215 } 216 217 public void consumePosRange (int iposStart, int iposEnd, Consumer out) 218 { 219 if (out.ignoring()) 220 return; 221 int i = iposStart >>> 1; 222 int end = iposEnd >>> 1; 223 if (i < gapStart) 224 { 225 int lim = end > gapStart ? end : gapStart; 226 consumePosRange(iposStart, lim << 1, out); 227 } 228 if (end > gapEnd) 229 { 230 i = i < gapEnd ? gapEnd : i; 231 consumePosRange(i << 1, iposEnd, out); 232 } 233 } 234 235 } 236 | Popular Tags |