1/*
2 * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
3 * Copyright (C) 2003, 2004, 2006, 2007, 2008 Apple Inc.  All right reserved.
4 * Copyright (C) 2011 Google, Inc.  All rights reserved.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB.  If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 *
21 */
22
23#ifndef BidiRunList_h
24#define BidiRunList_h
25
26#include "wtf/Assertions.h"
27#include "wtf/Noncopyable.h"
28
29namespace blink {
30
31template <class Run>
32class BidiRunList {
33    WTF_MAKE_NONCOPYABLE(BidiRunList);
34public:
35    BidiRunList()
36        : m_firstRun(0)
37        , m_lastRun(0)
38        , m_logicallyLastRun(0)
39        , m_runCount(0)
40    {
41    }
42
43    // FIXME: Once BidiResolver no longer owns the BidiRunList,
44    // then ~BidiRunList should call deleteRuns() automatically.
45
46    Run* firstRun() const { return m_firstRun; }
47    Run* lastRun() const { return m_lastRun; }
48    Run* logicallyLastRun() const { return m_logicallyLastRun; }
49    unsigned runCount() const { return m_runCount; }
50
51    void addRun(Run*);
52    void prependRun(Run*);
53
54    void moveRunToEnd(Run*);
55    void moveRunToBeginning(Run*);
56
57    void deleteRuns();
58    void reverseRuns(unsigned start, unsigned end);
59    void reorderRunsFromLevels();
60
61    void setLogicallyLastRun(Run* run) { m_logicallyLastRun = run; }
62
63    void replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns);
64
65private:
66    void clearWithoutDestroyingRuns();
67
68    Run* m_firstRun;
69    Run* m_lastRun;
70    Run* m_logicallyLastRun;
71    unsigned m_runCount;
72};
73
74template <class Run>
75inline void BidiRunList<Run>::addRun(Run* run)
76{
77    if (!m_firstRun)
78        m_firstRun = run;
79    else
80        m_lastRun->m_next = run;
81    m_lastRun = run;
82    m_runCount++;
83}
84
85template <class Run>
86inline void BidiRunList<Run>::prependRun(Run* run)
87{
88    ASSERT(!run->m_next);
89
90    if (!m_lastRun)
91        m_lastRun = run;
92    else
93        run->m_next = m_firstRun;
94    m_firstRun = run;
95    m_runCount++;
96}
97
98template <class Run>
99inline void BidiRunList<Run>::moveRunToEnd(Run* run)
100{
101    ASSERT(m_firstRun);
102    ASSERT(m_lastRun);
103    ASSERT(run->m_next);
104
105    Run* current = 0;
106    Run* next = m_firstRun;
107    while (next != run) {
108        current = next;
109        next = current->next();
110    }
111
112    if (!current)
113        m_firstRun = run->next();
114    else
115        current->m_next = run->m_next;
116
117    run->m_next = 0;
118    m_lastRun->m_next = run;
119    m_lastRun = run;
120}
121
122template <class Run>
123inline void BidiRunList<Run>::moveRunToBeginning(Run* run)
124{
125    ASSERT(m_firstRun);
126    ASSERT(m_lastRun);
127    ASSERT(run != m_firstRun);
128
129    Run* current = m_firstRun;
130    Run* next = current->next();
131    while (next != run) {
132        current = next;
133        next = current->next();
134    }
135
136    current->m_next = run->m_next;
137    if (run == m_lastRun)
138        m_lastRun = current;
139
140    run->m_next = m_firstRun;
141    m_firstRun = run;
142}
143
144template <class Run>
145void BidiRunList<Run>::replaceRunWithRuns(Run* toReplace, BidiRunList<Run>& newRuns)
146{
147    ASSERT(newRuns.runCount());
148    ASSERT(m_firstRun);
149    ASSERT(toReplace);
150
151    if (m_firstRun == toReplace) {
152        m_firstRun = newRuns.firstRun();
153    } else {
154        // Find the run just before "toReplace" in the list of runs.
155        Run* previousRun = m_firstRun;
156        while (previousRun->next() != toReplace)
157            previousRun = previousRun->next();
158        ASSERT(previousRun);
159        previousRun->setNext(newRuns.firstRun());
160    }
161
162    newRuns.lastRun()->setNext(toReplace->next());
163
164    // Fix up any of other pointers which may now be stale.
165    if (m_lastRun == toReplace)
166        m_lastRun = newRuns.lastRun();
167    if (m_logicallyLastRun == toReplace)
168        m_logicallyLastRun = newRuns.logicallyLastRun();
169    m_runCount += newRuns.runCount() - 1; // We added the new runs and removed toReplace.
170
171    delete toReplace;
172    newRuns.clearWithoutDestroyingRuns();
173}
174
175template <class Run>
176void BidiRunList<Run>::clearWithoutDestroyingRuns()
177{
178    m_firstRun = 0;
179    m_lastRun = 0;
180    m_logicallyLastRun = 0;
181    m_runCount = 0;
182}
183
184template <class Run>
185void BidiRunList<Run>::deleteRuns()
186{
187    if (!m_firstRun)
188        return;
189
190    Run* curr = m_firstRun;
191    while (curr) {
192        Run* s = curr->next();
193        delete curr;
194        curr = s;
195    }
196
197    clearWithoutDestroyingRuns();
198}
199
200template <class Run>
201void BidiRunList<Run>::reverseRuns(unsigned start, unsigned end)
202{
203    ASSERT(m_runCount);
204    if (start >= end)
205        return;
206
207    ASSERT(end < m_runCount);
208
209    // Get the item before the start of the runs to reverse and put it in
210    // |beforeStart|. |curr| should point to the first run to reverse.
211    Run* curr = m_firstRun;
212    Run* beforeStart = 0;
213    unsigned i = 0;
214    while (i < start) {
215        i++;
216        beforeStart = curr;
217        curr = curr->next();
218    }
219
220    Run* startRun = curr;
221    while (i < end) {
222        i++;
223        curr = curr->next();
224    }
225    Run* endRun = curr;
226    Run* afterEnd = curr->next();
227
228    i = start;
229    curr = startRun;
230    Run* newNext = afterEnd;
231    while (i <= end) {
232        // Do the reversal.
233        Run* next = curr->next();
234        curr->m_next = newNext;
235        newNext = curr;
236        curr = next;
237        i++;
238    }
239
240    // Now hook up beforeStart and afterEnd to the startRun and endRun.
241    if (beforeStart)
242        beforeStart->m_next = endRun;
243    else
244        m_firstRun = endRun;
245
246    startRun->m_next = afterEnd;
247    if (!afterEnd)
248        m_lastRun = startRun;
249}
250
251} // namespace blink
252
253#endif // BidiRunList
254