michael@0: /*  GRAPHITE2 LICENSING
michael@0: 
michael@0:     Copyright 2013, SIL International
michael@0:     All rights reserved.
michael@0: 
michael@0:     This library is free software; you can redistribute it and/or modify
michael@0:     it under the terms of the GNU Lesser General Public License as published
michael@0:     by the Free Software Foundation; either version 2.1 of License, or
michael@0:     (at your option) any later version.
michael@0: 
michael@0:     This program is distributed in the hope that it will be useful,
michael@0:     but WITHOUT ANY WARRANTY; without even the implied warranty of
michael@0:     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
michael@0:     Lesser General Public License for more details.
michael@0: 
michael@0:     You should also have received a copy of the GNU Lesser General Public
michael@0:     License along with this library in the file named "LICENSE".
michael@0:     If not, write to the Free Software Foundation, 51 Franklin Street,
michael@0:     Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
michael@0:     internet at http://www.fsf.org/licenses/lgpl.html.
michael@0: 
michael@0: Alternatively, the contents of this file may be used under the terms of the
michael@0: Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
michael@0: License, as published by the Free Software Foundation, either version 2
michael@0: of the License or (at your option) any later version.
michael@0: */
michael@0: #pragma once
michael@0: 
michael@0: namespace graphite2
michael@0: {
michael@0: 
michael@0: class BracketPair
michael@0: {
michael@0: public:
michael@0:     BracketPair(uint16 g, Slot *s, uint8 b, BracketPair *p, BracketPair *l) : _open(s), _close(0), _parent(p), _next(0), _prev(l), _gid(g), _mask(0), _before(b) {};
michael@0:     uint16 gid() const { return _gid; }
michael@0:     Slot *open() const { return _open; }
michael@0:     Slot *close() const { return _close; }
michael@0:     uint8 mask() const { return _mask; }
michael@0:     int8 before() const { return _before; }
michael@0:     BracketPair *parent() const { return _parent; }
michael@0:     void close(Slot *s) { _close = s; }
michael@0:     BracketPair *next() const { return _next; }
michael@0:     BracketPair *prev() const { return _prev; }
michael@0:     void next(BracketPair *n) { _next = n; }
michael@0:     void orin(uint8 m) { _mask |= m; }
michael@0: private:
michael@0:     Slot        *   _open;          // Slot of opening paren
michael@0:     Slot        *   _close;         // Slot of closing paren
michael@0:     BracketPair *   _parent;        // pair this pair is in or NULL
michael@0:     BracketPair *   _next;          // next pair along the string
michael@0:     BracketPair *   _prev;          // pair that closed last before we opened
michael@0:     uint16          _gid;           // gid of closing paren
michael@0:     uint8           _mask;          // bitmap (2 bits) of directions within the pair
michael@0:     int8            _before;        // most recent strong type (L, R, OPP, CPP)
michael@0: };
michael@0: 
michael@0: class BracketPairStack
michael@0: {
michael@0: public:
michael@0:     BracketPairStack(int s) : _stack(grzeroalloc<BracketPair>(s)), _ip(_stack - 1), _top(0), _last(0), _lastclose(0), _size(s) {}
michael@0:     ~BracketPairStack() { free(_stack); }
michael@0: 
michael@0: public:
michael@0:     BracketPair *scan(uint16 gid);
michael@0:     void close(BracketPair *tos, Slot *s);
michael@0:     BracketPair *push(uint16 gid, Slot *pos, uint8 before, int prevopen);
michael@0:     void orin(uint8 mask);
michael@0:     void clear() { _ip = _stack - 1; _top = 0; _last = 0; _lastclose = 0; }
michael@0:     int size() const { return _size; }
michael@0:     BracketPair *start() const { return _stack; }
michael@0: 
michael@0:     CLASS_NEW_DELETE
michael@0: 
michael@0: private:
michael@0: 
michael@0:     BracketPair *_stack;        // start of storage
michael@0:     BracketPair *_ip;           // where to add the next pair
michael@0:     BracketPair *_top;          // current parent
michael@0:     BracketPair *_last;         // end of next() chain
michael@0:     BracketPair *_lastclose;    // last pair to close
michael@0:     int          _size;         // capacity
michael@0: };
michael@0: 
michael@0: inline BracketPair *BracketPairStack::scan(uint16 gid)
michael@0: {
michael@0:     BracketPair *res = _top;
michael@0:     while (res >= _stack)
michael@0:     {
michael@0:         if (res->gid() == gid)
michael@0:             return res;
michael@0:         res = res->parent();
michael@0:     }
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: inline void BracketPairStack::close(BracketPair *tos, Slot *s) 
michael@0: {
michael@0:     for ( ; _last && _last != tos && !_last->close(); _last = _last->parent())
michael@0:     { }
michael@0:     tos->close(s);
michael@0:     _last->next(NULL);
michael@0:     _lastclose = tos;
michael@0:     _top = tos->parent();
michael@0: }
michael@0: 
michael@0: inline BracketPair *BracketPairStack::push(uint16 gid, Slot *pos, uint8 before, int prevopen)
michael@0: {
michael@0:     if (++_ip - _stack < _size && _stack)
michael@0:     {
michael@0:         ::new (_ip) BracketPair(gid, pos, before, _top, prevopen ? _last : _lastclose);
michael@0:         if (_last) _last->next(_ip);
michael@0:         _last = _ip;
michael@0:     }
michael@0:     _top = _ip;
michael@0:     return _ip;
michael@0: }
michael@0: 
michael@0: inline void BracketPairStack::orin(uint8 mask)
michael@0: {
michael@0:     BracketPair *t = _top;
michael@0:     for ( ; t; t = t->parent())
michael@0:         t->orin(mask);
michael@0: }
michael@0: 
michael@0: }