← Back to branch summary

~brian-sidebotham/wxwidgets-cmake/wxpython-2.9.4

« back to all changes in this revision

Viewing changes to src/stc/scintilla/src/Partitioning.h

  • Committer: Brian Sidebotham
  • Date: 2013-08-03 14:30:08 UTC
  • Revision ID: brian.sidebotham@gmail.com-20130803143008-c7806tkych1tp6fc
Initial import into Bazaar

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/stc/scintilla/src/Partitioning.h
 
1
// Scintilla source code edit control
 
2
/** @file Partitioning.h
 
3
 ** Data structure used to partition an interval. Used for holding line start/end positions.
 
4
 **/
 
5
// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
 
6
// The License.txt file describes the conditions under which this software may be distributed.
 
7
 
 
8
#ifndef PARTITIONING_H
 
9
#define PARTITIONING_H
 
10
 
 
11
/// A split vector of integers with a method for adding a value to all elements 
 
12
/// in a range.
 
13
/// Used by the Partitioning class.
 
14
 
 
15
class SplitVectorWithRangeAdd : public SplitVector<int> {
 
16
public:
 
17
        SplitVectorWithRangeAdd(int growSize_) {
 
18
                SetGrowSize(growSize_);
 
19
                ReAllocate(growSize_);
 
20
        }
 
21
        ~SplitVectorWithRangeAdd() {
 
22
        }
 
23
        void RangeAddDelta(int start, int end, int delta) {
 
24
                // end is 1 past end, so end-start is number of elements to change
 
25
                int i = 0;
 
26
                int rangeLength = end - start;
 
27
                int range1Length = rangeLength;
 
28
                int part1Left = part1Length - start;
 
29
                if (range1Length > part1Left)
 
30
                        range1Length = part1Left;
 
31
                while (i < range1Length) {
 
32
                        body[start++] += delta;
 
33
                        i++;
 
34
                }
 
35
                start += gapLength;
 
36
                while (i < rangeLength) {
 
37
                        body[start++] += delta;
 
38
                        i++;
 
39
                }
 
40
        }
 
41
};
 
42
 
 
43
/// Divide an interval into multiple partitions.
 
44
/// Useful for breaking a document down into sections such as lines.
 
45
 
 
46
class Partitioning {
 
47
private:
 
48
        // To avoid calculating all the partition positions whenever any text is inserted
 
49
        // there may be a step somewhere in the list.
 
50
        int stepPartition;
 
51
        int stepLength;
 
52
        SplitVectorWithRangeAdd *body;
 
53
 
 
54
        // Move step forward
 
55
        void ApplyStep(int partitionUpTo) {
 
56
                if (stepLength != 0) {
 
57
                        body->RangeAddDelta(stepPartition+1, partitionUpTo + 1, stepLength);
 
58
                }
 
59
                stepPartition = partitionUpTo;
 
60
                if (stepPartition >= body->Length()-1) {
 
61
                        stepPartition = body->Length()-1;
 
62
                        stepLength = 0;
 
63
                }
 
64
        }
 
65
 
 
66
        // Move step backward
 
67
        void BackStep(int partitionDownTo) {
 
68
                if (stepLength != 0) {
 
69
                        body->RangeAddDelta(partitionDownTo+1, stepPartition+1, -stepLength);
 
70
                }
 
71
                stepPartition = partitionDownTo;
 
72
        }
 
73
 
 
74
        void Allocate(int growSize) {
 
75
                body = new SplitVectorWithRangeAdd(growSize);
 
76
                stepPartition = 0;
 
77
                stepLength = 0;
 
78
                body->Insert(0, 0);     // This value stays 0 for ever
 
79
                body->Insert(1, 0);     // This is the end of the first partition and will be the start of the second
 
80
        }
 
81
 
 
82
public:
 
83
        Partitioning(int growSize) {
 
84
                Allocate(growSize);
 
85
        }
 
86
 
 
87
        ~Partitioning() {
 
88
                delete body;
 
89
                body = 0;
 
90
        }
 
91
 
 
92
        int Partitions() const {
 
93
                return body->Length()-1;
 
94
        }
 
95
 
 
96
        void InsertPartition(int partition, int pos) {
 
97
                if (stepPartition < partition) {
 
98
                        ApplyStep(partition);
 
99
                }
 
100
                body->Insert(partition, pos);
 
101
                stepPartition++;
 
102
        }
 
103
 
 
104
        void SetPartitionStartPosition(int partition, int pos) {
 
105
                ApplyStep(partition+1);
 
106
                if ((partition < 0) || (partition > body->Length())) {
 
107
                        return;
 
108
                }
 
109
                body->SetValueAt(partition, pos);
 
110
        }
 
111
 
 
112
        void InsertText(int partitionInsert, int delta) {
 
113
                // Point all the partitions after the insertion point further along in the buffer
 
114
                if (stepLength != 0) {
 
115
                        if (partitionInsert >= stepPartition) {
 
116
                                // Fill in up to the new insertion point
 
117
                                ApplyStep(partitionInsert);
 
118
                                stepLength += delta;
 
119
                        } else if (partitionInsert >= (stepPartition - body->Length() / 10)) {
 
120
                                // Close to step but before so move step back
 
121
                                BackStep(partitionInsert);
 
122
                                stepLength += delta;
 
123
                        } else {
 
124
                                ApplyStep(body->Length()-1);
 
125
                                stepPartition = partitionInsert;
 
126
                                stepLength = delta;
 
127
                        }
 
128
                } else {
 
129
                        stepPartition = partitionInsert;
 
130
                        stepLength = delta;
 
131
                }
 
132
        }
 
133
 
 
134
        void RemovePartition(int partition) {
 
135
                if (partition > stepPartition) {
 
136
                        ApplyStep(partition);
 
137
                        stepPartition--;
 
138
                } else {
 
139
                        stepPartition--;
 
140
                }
 
141
                body->Delete(partition);
 
142
        }
 
143
 
 
144
        int PositionFromPartition(int partition) const {
 
145
                PLATFORM_ASSERT(partition >= 0);
 
146
                PLATFORM_ASSERT(partition < body->Length());
 
147
                if ((partition < 0) || (partition >= body->Length())) {
 
148
                        return 0;
 
149
                }
 
150
                int pos = body->ValueAt(partition);
 
151
                if (partition > stepPartition)
 
152
                        pos += stepLength;
 
153
                return pos;
 
154
        }
 
155
 
 
156
        int PartitionFromPosition(int pos) const {
 
157
                if (body->Length() <= 1)
 
158
                        return 0;
 
159
                if (pos >= (PositionFromPartition(body->Length()-1)))
 
160
                        return body->Length() - 1 - 1;
 
161
                int lower = 0;
 
162
                int upper = body->Length()-1;
 
163
                do {
 
164
                        int middle = (upper + lower + 1) / 2;   // Round high
 
165
                        int posMiddle = body->ValueAt(middle);
 
166
                        if (middle > stepPartition)
 
167
                                posMiddle += stepLength;
 
168
                        if (pos < posMiddle) {
 
169
                                upper = middle - 1;
 
170
                        } else {
 
171
                                lower = middle;
 
172
                        }
 
173
                } while (lower < upper);
 
174
                return lower;
 
175
        }
 
176
 
 
177
        void DeleteAll() {
 
178
                int growSize = body->GetGrowSize();
 
179
                delete body;
 
180
                Allocate(growSize);
 
181
        }
 
182
};
 
183
 
 
184
#endif