// ToolsLib Project

/* ToolsLib library for RusRoute firewall and other projects of
* Andrey A. Moiseenko / IE Moiseenko A.A. (Russia)
* e-mail: support@maasoftware.ru, maa2002@mail.ru
* web: http://maasoftware.ru, http://maasoftware.com, http://maasoft.ru, http://maasoft.org
* Author's full name: Andrey Alekseevitch Moiseenko
* (russian name: Моисеенко Андрей Алексеевич)
*/

// ToolsLib/a_trie.h

/* Copyright (C) 2002-2024 Andrey A. Moiseenko (support@maasoftware.ru)
* All rights reserved.
*
* This library contains strings and string's functions implementation.
* This CMaaString does not throws throws exception out of boundaries.
* The library implementation written
* by Andrey A. Moiseenko (support@maasoftware.ru).
* This library and applications are
* FREE FOR COMMERCIAL AND NON-COMMERCIAL USE
* as long as the following conditions are adhered to.
*
* Copyright remains Andrey A. Moiseenko, and as such any Copyright notices in
* the code are not to be removed. If this code is used in a product,
* Andrey A. Moiseenko should be given attribution as the author of the parts used.
* This can be in the form of a textual message at program startup or
* in documentation (online or textual) provided with the package.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by Andrey A. Moiseenko (support@maasoftware.ru)
*
* THIS SOFTWARE IS PROVIDED BY ANDREY A. MOISEENKO ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* The licence and distribution terms for any publically available version or
* derivative of this code cannot be changed. i.e. this code cannot simply be
* copied and put under another distribution licence
* [including the GNU Public Licence.]
*/

//#include "perm.h"
//#include "temp.h"


//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>

// Цифровое TRIE дерево v.14
// Author: Andrey Moiseenko (Андрей Моисеенко)
// Copyright (C) 2017 Andrey Moiseenko
// Licensed under GNU GPL v3
// www: http://maasoftware.ru
// e-mail: support@maasoftware.ru
// Can be commented: #define TRIE10_DEBUG
// Tested with compilers:
// g++ version 12.2.0
// Visual Studio 2022

//#define TRIE10_DEBUG
//#define TRIE10_DEBUG2

#ifdef TRIE10_DEBUG
extern bool gbDbgTrie10Nodes; // debug nodes
#endif

//#define TRIE10_OPT_BITMAP

#if 1

template < class Data > class CMaaTrie
{
protected:
struct Node
{
Node* m_Parent; // родительская вершина
char m_Value[sizeof(Data)]; // значение
int m_N; // число букв (вершин)
char* m_Letters; // отсортированные буквы
Node** m_Nodes; // вершины, соответствующие буквам
#ifdef TRIE10_OPT_BITMAP
unsigned char m_BitMap[256 / 8];
#endif
char m_Letter; // буква
bool m_bValue; // эта вершина - слово, m_Value имеет смысл

Node(Node* Parent, char Letter) noexcept
: m_Parent(Parent),
//m_Value(-1),
m_N(0),
m_Letters(nullptr),
m_Nodes(nullptr),
m_Letter(Letter),
m_bValue(false)
{
#ifdef TRIE10_OPT_BITMAP
memset(m_BitMap, 0, sizeof(m_BitMap));
#endif
//memset(m_Value, 0, sizeof(m_Value));
#ifdef __ALLOCATOR_FILL
memset(m_Value, __ALLOCATOR_FILL_INIT_CHAR, sizeof(m_Value));
#endif
}

~Node()
{
for (int i = 0; i < m_N; i++)
{
delete m_Nodes[i];
}
delete[] m_Letters;
delete[] m_Nodes;
if (m_bValue)
{
Data* d = (Data*)m_Value;
d->~Data();
#ifdef __ALLOCATOR_FILL
memset(m_Value, __ALLOCATOR_FILL_FREE_CHAR, sizeof(m_Value));
#endif
}
}

// Универсальная функция поиска/вставки/поиска следующей/предыдущей позиции по букве
template <bool bInsert /* = false */ > int Find (char c, int iNextPrev = 0, int* pPosNextPrev = nullptr) noexcept(!bInsert)
{
// бинарный поиск позиции символа c, возвращает -1 если символа нет и bInsert == false && iNextPrev == 0
// bInsert == true - вставка символа c, которого нет
// iNextPrev > 0 - позиция следующего символа записывается в *pPosNextPrev, c - нет
// iNextPrev < 0 - позиция предыдущего символа записывается в *pPosNextPrev, c - нет

#ifdef TRIE10_DEBUG
gbDbgTrie10Nodes&& printf("Find(%c, %s, %d), %d %d\n", c, bInsert ? "true" : "false", iNextPrev, m_N, m_Value);
#endif
#ifdef TRIE10_OPT_BITMAP
if (!bInsert && !iNextPrev && !(m_BitMap[((unsigned char)c) / 8] & (1 << (((unsigned char)c) & 0x7))))
{
return -1;
}
#endif

// бинарный поиск
int b = 0, e = m_N - 1;
while (b < e)
{
const int m = (b + e) / 2;

if (m_Letters[m] < c)
{
b = m + 1;
}
else
{
e = m;
}
}
#ifdef TRIE10_DEBUG
gbDbgTrie10Nodes&& printf("%d %d / %d\n", b, e, m_N);
#endif
if (b < m_N)
{
if (m_Letters[b] == c)
{
return b;
}
if (m_Letters[b] < c && (bInsert || iNextPrev > 0))
{
// корректировка позиции вставки и следующей буквы
b++;
}
else if (m_Letters[b] > c && (!bInsert && iNextPrev < 0))
{
// корректировка позиции предыдущей буквы
b--;
}
}
else if (!bInsert && iNextPrev < 0)
{
// m_N == 0 - корректировка позиции предыдущей буквы
b = -1;
}
if constexpr (bInsert)
{
// вставка c,nullptr в позицию b

char* l = nullptr;
Node** n = nullptr;
try
{
l = TL_NEW char[m_N + 1];
n = TL_NEW Handle[m_N + 1];
}
catch (...)
{
delete[] l;
throw; // TODO: eat New[] exceptions
}
if (!l || !n)
{
delete[] l;
delete[] n;
return -1;
}
memcpy(l, m_Letters, b);
l[b] = c;
memcpy(l + b + 1, m_Letters + b, m_N - b);

memcpy(n, m_Nodes, b * sizeof(Node*));
n[b] = nullptr;
memcpy(n + b + 1, m_Nodes + b, (m_N - b) * sizeof(Node*));

delete[] m_Letters; m_Letters = l;
delete[] m_Nodes; m_Nodes = n;
m_N++;
#ifdef TRIE10_OPT_BITMAP
m_BitMap[((unsigned char)c) / 8] |= (1 << (((unsigned char)c) & 0x7));
#endif
return b;
}
if (iNextPrev)
{
// если нет такой позиции, возвращаем -1
*pPosNextPrev = (iNextPrev < 0 || (iNextPrev > 0 && b < m_N)) ? b : -1;
}
return -1; // не найден при обычном поиске
}

// Удаление по индексу позиции
bool Remove(int pos) noexcept
{
if (pos >= 0)
{
#ifdef TRIE10_OPT_BITMAP
char c = m_Letters[pos];
m_BitMap[((unsigned char)c) / 8] &= ~(1 << (((unsigned char)c) & 0x7));
#endif
// обходимся без reallocation, pos < m_N
memmove(m_Letters + pos, m_Letters + pos + 1, m_N - (pos + 1));
memmove(m_Nodes + pos, m_Nodes + pos + 1, (m_N - (pos + 1)) * sizeof(Node*));
m_N--;
return true;
}
return false;
}

// Удаление с поиском по букве
bool Remove(char c) noexcept
{
return Remove(Find<false>(c));
}

// Поиск первой вершины относительно позиции
Node* FirstAtPos(int pos) const noexcept
{
Node* p = m_Nodes[pos];
while (!p->m_bValue && p->m_N > 0)
{
p = p->m_Nodes[0];
}
return p; // p->m_bValue == true по построению
}

// Поиск последней вершины относительно позиции
Node* LastAtPos(int pos) const noexcept
{
Node* p = m_Nodes[pos];
while (p->m_N > 0)
{
p = p->m_Nodes[p->m_N - 1];
}
return p; // p->m_bValue == true по построению
}

// Поиск следующей вершины через родителя
Node* NextAtTop() const noexcept
{
Node* p = (Node*)this;
while (p)
{
const Node* n = p;
p = p->m_Parent;
if (!p)
{
break;
}
const int pos = p->Find<false>(n->m_Letter);
if (pos + 1 < p->m_N)
{
return p->FirstAtPos(pos + 1);
}
}
return p;
}

// Поиск предыдущей вершины через родителя
Node* PrevAtTop() const noexcept
{
Node* p = (Node*)this;
while (p)
{
const Node* n = p;
p = p->m_Parent;
if (!p)
{
break;
}
const int pos = p->Find<false>(n->m_Letter);
if (pos > 0)
{
return p->LastAtPos(pos - 1);
}
if (p->m_bValue)
{
break;
}
}
return p;
}

// Получение имени ключа
bool GetKey(char* p, int Size, bool bAdd0 = true, int* pSizeRequired = nullptr, int* pLen = nullptr) const noexcept
{
const Node* n = this;
int len = 0;
while (n->m_Parent)
{
//int pos = n->m_Parent->Find<false>(n); // slow, use when there is no n->m_Letter; pos >= 0 && pos < n->m_Parent->m_N по построению
if (len < Size)
{
//p[len] = n->m_Parent->m_Letters[pos];
p[len] = n->m_Letter;
}
len++;
n = n->m_Parent;
}
int SizeRequired = len + (bAdd0 ? 1 : 0);
if (pSizeRequired)
{
*pSizeRequired = SizeRequired;
}
if (pLen)
{
*pLen = len;
}
if (Size < SizeRequired)
{
if (Size > 0 && bAdd0)
{
*p = 0;
}
return false;
}
for (int i = len / 2; i--;)
{
const char c = p[i];
p[i] = p[len - 1 - i];
p[len - 1 - i] = c;
}
if (bAdd0)
{
p[len] = 0;
}
return true;
}

// Получение имени ключа
CMaaString GetKey() const
{
char Buffer[TOOLSLIB_CS_4K];
CMaaConcatString c(Buffer, sizeof(Buffer));

const Node* n = this;
int len = 0;
while (n->m_Parent)
{
c += n->m_Letter;
len++;
n = n->m_Parent;
}
CMaaString r = c;
if (r.Length() != len)
{
r.Empty();
return r;
}
char* p = r.GetBuffer();
for (int i = len / 2; i--;)
{
char c = p[i];
p[i] = p[len - 1 - i];
p[len - 1 - i] = c;
}
return r;
}

private:
// Защита копирования
Node(const Node&);
Node& operator = (const Node&);
};

Node* m_Root;

#ifdef TRIE10_DEBUG
bool m_bDbg;
#endif

private:
// Защита копирования
CMaaTrie(const CMaaTrie&);
CMaaTrie& operator = (const CMaaTrie&);
public:
// Тип хандлера для пользователей
typedef Node* Handle;

class iterator
{
CMaaTrie* m_trie;
Handle m_Handle;
bool m_bDirect;
public:
iterator(CMaaTrie& t, Handle h, bool dir) noexcept
: m_trie(&t),
m_Handle(h),
m_bDirect(dir)
{
}
iterator(const iterator& That) noexcept
{
*this = That;
}
~iterator() noexcept
{
}
iterator& operator = (const iterator& That) noexcept
{
m_trie = That.m_trie;
m_Handle = That.m_Handle;
m_bDirect = That.m_bDirect;
return *this;
}
void Swap(iterator& That) noexcept
{
iterator tmp(*this);
*this = That;
That = tmp;
}
iterator operator++(int) noexcept
{
iterator tmp(*this);
++(*this);
return tmp;
}
iterator operator++() noexcept
{
m_Handle = m_bDirect ? m_trie->Next(m_Handle) : m_trie->Prev(m_Handle);
return *this;
}
iterator operator--(int) noexcept
{
iterator tmp(*this);
--(*this);
return tmp;
}
iterator operator--() noexcept
{
m_Handle = m_bDirect ? m_trie->Prev(m_Handle) : m_trie->Next(m_Handle);
return *this;
}
bool operator==(const iterator& That) const noexcept
{
return m_Handle == That.m_Handle && m_trie == That.m_trie && m_bDirect == That.m_bDirect;
}
bool operator!=(const iterator& That) const noexcept
{
return !(*this == That);
}
operator Handle() noexcept
{
return m_Handle;
}
bool GetKey(char* p, int Size, bool bAdd0 = true, int* pSizeRequired = nullptr, int* pLen = nullptr) const
{
return m_trie->GetKey(m_Handle, p, Size, bAdd0, pSizeRequired, pLen);
}
CMaaString GetKey() const
{
return m_trie->GetKey(m_Handle);
}
/*
const Key & ckey()
{
if (!IsValid())
{
throw 1;
}
return r->K;
}
Key key()
{
if (!IsValid())
{
throw 1;
}
return r->K;
}
*/
Data& rdata() noexcept(std::is_nothrow_move_constructible<Data>::value)
{
return m_trie->Value(m_Handle);
}
Data data() noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return m_trie->GetValue(m_Handle);
}
bool Remove(Data* pval = nullptr) noexcept(noexcept(*pval = *pval))
{
return m_trie->Remove(m_Handle, pval);
}
};

// Конструктор
CMaaTrie() noexcept
{
m_Root = nullptr;
#ifdef TRIE10_DEBUG
m_bDbg = false;
#endif
}

// Деструктор
virtual ~CMaaTrie()
{
delete m_Root;
}

// inline functions
// Добавить ключ str со значением val
bool Add(const char* str, const Data& val)
{
#ifdef TRIE10_DEBUG
m_bDbg&& printf("Add(%s, %d): ", str, val);
#endif
return Add(str, (int)strlen(str), val);
}

// Удалить ключ str, вернув значение в *pval
bool Remove(const char* str, Data* pval = nullptr) noexcept(noexcept(*pval=*pval))
{
#ifdef TRIE10_DEBUG
m_bDbg&& printf("Remove(%s): ", str);
#endif
return Remove(str, (int)strlen(str), pval);
}

// Не рекомендуем в api, упрощённый интерфейс для задания
Data Find(const char* str) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return Find(str, (int)strlen(str));
}

// Не рекомендуем в api, упрощённый интерфейс для задания
Data Find(const char* str, int len) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
Data v{};// = -1; // возвращаем -1, если слово не найдено
Find(str, len, &v);
return v;
}

// Рекомендуем в api, более удобная функция
bool Find(const char* str, Data* pval) const noexcept(noexcept(*pval=*pval))
{
#ifdef TRIE10_DEBUG
if (m_bDbg)
{
printf("Find(%s): ", str);
int v{};// = -1;
pval = pval ? pval : &v;
bool b = Find(str, (int)strlen(str), pval);
printf(b ? "%d " : "false ", *pval);
return b;
}
#endif
return Find(str, (int)strlen(str), pval);
}

// Поиск последующего слова > str или >= str, если bEqual = true
Handle FindGQ(const char* str, bool bEqual = false) const noexcept
{
#ifdef TRIE10_DEBUG
m_bDbg&& printf("FindGQ(%s, %s): ", str, bEqual ? "true" : "false");
#endif
return FindGQ(str, (int)strlen(str), bEqual);
}

// Поиск предшествующего слова < str или <= str, если bEqual = true
Handle FindLQ(const char* str, bool bEqual = false) const noexcept
{
#ifdef TRIE10_DEBUG
m_bDbg&& printf("FindLQ(%s, %s): ", str, bEqual ? "true" : "false");
#endif
return FindLQ(str, (int)strlen(str), bEqual);
}

// CMaaString - functions
//////////
// Добавить ключ str со значением val
bool AddS(CMaaString str, const Data& val)
{
return Add((const char*)str, str.Length(), val);
}
// Удалить ключ str, вернув значение в *pval
bool RemoveS(CMaaString str, Data* pval = nullptr) noexcept(noexcept(*pval=*pval))
{
return Remove((const char*)str, str.Length(), pval);
}
// Не рекомендуем в api, упрощённый интерфейс для задания
Data FindS(CMaaString str) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return Find((const char*)str, str.Length());
}
// Рекомендуем в api, более удобная функция
bool FindS(CMaaString str, Data* pval) const noexcept(noexcept(*pval=*pval))
{
return Find((const char*)str, str.Length(), pval);
}
// Поиск последующего слова > str или >= str, если bEqual = true
Handle FindGQS(CMaaString str, bool bEqual = false) const noexcept
{
return FindGQ((const char*)str, str.Length(), bEqual);
}
// Поиск предшествующего слова < str или <= str, если bEqual = true
Handle FindLQS(CMaaString str, bool bEqual = false) const noexcept
{
return FindLQ((const char*)str, str.Length(), bEqual);
}
//////////

// Поиск первого слова
Handle First() const noexcept
{
Node* x = m_Root;
if (x && x->m_bValue == false)
{
x = x->FirstAtPos(0);
}
return x;
}

// Поиск последнего слова
Handle Last() const noexcept
{
Node* x = m_Root;
if (x && x->m_N > 0)
{
x = x->LastAtPos(x->m_N - 1);
}
return x;
}

iterator begin() noexcept
{
iterator it(*this, First(), true);
return it;
}

iterator end() noexcept
{
iterator it(*this, nullptr, true);
return it;
}

iterator rbegin() noexcept
{
iterator it(*this, Last(), false);
return it;
}

iterator rend() noexcept
{
iterator it(*this, nullptr, false);
return it;
}

iterator it(Handle h, bool dir = true) noexcept
{
iterator it(*this, h, dir);
return it;
}

// Не рекомендуем в api, для задания
// Ссылка на значение по хандлеру
Data& Value(Handle h) noexcept(std::is_nothrow_move_constructible<Data>::value)
{
// не рекомендуется
static Data v0{};
return h ? *(Data*)h->m_Value : (v0);// = -1);
}

// Не рекомендуем в api, для задания
// Получение значение по хандлеру
Data GetValue(Handle h) noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return Value(h);
}

// Рекомендуем в api, для задания
// Получение значения по хандлеру, может вернуть false если h не слово
bool GetValue(Handle h, Data* pval) noexcept(noexcept(*pval=*pval))
{
if (h && h->m_bValue)
{
if (pval)
{
*pval = *(Data*)h->m_Value;
}
return true;
}
return false;
}

// Установка значения по хандлеру, может вернуть false если h не слово
bool SetValue(Handle h, const Data& v) noexcept(std::is_nothrow_move_assignable<Data>::value)
{
if (h && h->m_bValue)
{
*(Data*)h->m_Value = v;
return true;
}
return false;
}

// Поиск узла по ключу, ключ может быть не словом
Handle FindHandle(const char* str) const noexcept
{
return FindHandle(str, (int)strlen(str));
}

// Получить ключ без '\0' в конце
bool GetKey(Handle h, char* p, int Size, int* pSizeRequired, int* pLen) const noexcept
{
return GetKey(h, p, Size, false, pSizeRequired, pLen);
}

#ifdef TRIE10_DEBUG
void SetDbg(bool bSet) noexcept
{
m_bDbg = bSet;
}
#else
void SetDbg(bool) noexcept
{
}
#endif

// Основные функции для не null-terminated строк

// Добавить слово str длиной len со значением val
bool Add(const char* str, int len, const Data& val)
{
if (/*val < 0 ||*/ len <= 0)
{
return false; // недопустимое значение value или len
}
if (!m_Root)
{
m_Root = TL_NEW Node(nullptr, 0);
if (!m_Root)
{
return false;
}
}
Node* p = m_Root;
int i = 0, pos0 = -1;
try
{
for (; i < len; i++)
{
const char c = str[i];
int pos = p->Find<true>(c);
if (pos < 0)
{
break; // New [] error
}
if (!p->m_Nodes[pos])
{
pos0 = pos; // запоминаем позицию буквы с нулевым указателем
p->m_Nodes[pos] = TL_NEW Node(p, c);
if (!p->m_Nodes[pos])
{
//p->Remove(pos); // удалим [pos0==pos] вне цикла
break;
}
pos0 = -1; // забываем позицию
}
p = p->m_Nodes[pos];
}
if (i >= len)
{
Data* d = (Data*)p->m_Value;
if (!p->m_bValue)
{
#ifdef __ALLOCATOR_FILL
memset(p->m_Value, __ALLOCATOR_FILL_ALLOC_CHAR, sizeof(p->m_Value));
#endif
new_(d, Data(val));
}
else
{
*d = val;
}
p->m_bValue = true;
//return true;
}
}
catch (...)
{
// New [] error
if (pos0 >= 0)
{
p->Remove(pos0); // более быстро, чем p->Remove(nullptr);
}
RemoveUnused(p);
throw;
}
if (i < len)
{
// New [] error
if (pos0 >= 0)
{
p->Remove(pos0); // более быстро, чем p->Remove(nullptr);
}
RemoveUnused(p);
return false;
}
//p->m_Value = val;
//p->m_bValue = true;
return true;
}

// Удалить слово str длиной len, вернув значение в *pval
bool Remove(const char* str, int len, Data* pval = nullptr) noexcept(noexcept(*pval=*pval))
{
Node* p = FindHandle(str, len);
return Remove(p, pval);
}

// Удалить слово вершины p, вернув значение в *pval
bool Remove(Node* p, Data* pval = nullptr) noexcept(noexcept(*pval=*pval))
{
if (p && p->m_bValue)
{
Data* d = (Data*)p->m_Value;
if (pval)
{
*pval = *d;
}
d->~Data();
#ifdef __ALLOCATOR_FILL
memset(p->m_Value, __ALLOCATOR_FILL_FREE_CHAR, sizeof(p->m_Value));
#endif
p->m_bValue = false;
RemoveUnused(p);
return true;
}
return false;
}

// Поиск вершины по ключу, может вернуть вершину - не слово
Handle FindHandle(const char* str, int len) const noexcept
{
Node* p = m_Root;
for (int i = 0; i < len && p; i++)
{
const char c = str[i];
int pos = p->Find<false>(c);
if (pos < 0)
{
p = nullptr;
break;
}
p = p->m_Nodes[pos];
}
return p;
}

// Поиск слова, возврат значения в *pval, return true on success
bool Find(const char* str, int len, Data* pval) const noexcept(noexcept(*pval=*pval))
{
Node* x = FindHandle(str, len);
if (x && x->m_bValue == false)
{
// не слово
return false;
}
if (x && pval)
{
*pval = *(Data*)x->m_Value;
}
return x ? true : false;
}

// Поиск последующего слова > str или >= str, если bEqual = true
Handle FindGQ(const char* str, int len, bool bEqual = false) const noexcept
{
Node* p = m_Root;
for (int i = 0; i < len && p; i++)
{
const char c = str[i];
int pos_next = -1; // позиция для следующего символа, если c не найден
int pos = p->Find<false>(c, 1, &pos_next);
#ifdef TRIE10_DEBUG2
m_bDbg&& printf("%d\n", pos);
#endif
if (pos < 0)
{
#ifdef TRIE10_DEBUG2
m_bDbg&& printf("%d\n", pos_next);
#endif
if (pos_next >= 0)
{
return p->FirstAtPos(pos_next);
}
return p->NextAtTop();
}
p = p->m_Nodes[pos];
}
if (p && (!bEqual || p->m_bValue == false))
{
p = Next(p);
}
return p;
}

// Поиск предшествующего слова < str или <= str, если bEqual = true
Handle FindLQ(const char* str, int len, bool bEqual = false) const noexcept
{
Node* p = m_Root;
for (int i = 0; i < len && p; i++)
{
const char c = str[i];
int pos_prev = -1; // позиция для предыдущего символа, если c не найден
int pos = p->Find<false>(c, -1, &pos_prev);
#ifdef TRIE10_DEBUG2
m_bDbg&& printf("%d\n", pos);
#endif
if (pos < 0)
{
#ifdef TRIE10_DEBUG2
m_bDbg&& printf("%d\n", pos_prev);
#endif
if (pos_prev >= 0)
{
return p->LastAtPos(pos_prev);
}
return p->PrevAtTop();
}
p = p->m_Nodes[pos];
}
if (p && (!bEqual || p->m_bValue == false))
{
p = Prev(p);
}
return p;
}

// Определение максимального пути (слова/части слова)
Handle MaxPath(const char* str, int len, int* plen, int* pincompleteLen = nullptr, Data* pval = nullptr) const noexcept(noexcept(*pval=*pval))
{
int rlen = 0, inclen = 0;
Handle r = nullptr;

Node* p = m_Root;
for (int i = 0; i < len && p; i++)
{
const char c = str[i];
int pos = p->Find<false>(c);
if (pos < 0)
{
p = nullptr;
break;
}
p = p->m_Nodes[pos];
inclen++;
if (p->m_bValue)
{
rlen = inclen;
r = p;
}
}
if (plen)
{
*plen = rlen;
}
if (pincompleteLen)
{
*pincompleteLen = inclen;
}
if (r && pval)
{
*pval = *(Data*)r->m_Value;
}
return r;
}

// Определение первого пути (слова/части слова)
Handle FirstPath(const char* str, int len, int* plen, int* pincompleteLen = nullptr, Data* pval = nullptr) const noexcept(noexcept(*pval=*pval))
{
int rlen = 0, inclen = 0;
Handle r = nullptr;

Node* p = m_Root;
for (int i = 0; i < len && p; i++)
{
char c = str[i];
int pos = p->Find<false>(c);
if (pos < 0)
{
p = nullptr;
break;
}
p = p->m_Nodes[pos];
inclen++;
if (p->m_bValue)
{
rlen = inclen;
r = p;
break; // первое существующее слово
}
}
if (plen)
{
*plen = rlen;
}
if (pincompleteLen)
{
*pincompleteLen = inclen;
}
if (r && pval)
{
*pval = *(Data*)r->m_Value;
}
return r;
}

// Следующее слово
Handle Next(Handle p) const noexcept
{
if (p)
{
return p->m_N > 0 ? p->FirstAtPos(0) : p->NextAtTop();
}
return nullptr;
}

// Предшествующее слово
Handle Prev(Handle p) const noexcept
{
if (p)
{
return p->PrevAtTop();
}
return nullptr;
}

// Удалить вершины-не слова без дочерних, поднимаясь вверх
Node* RemoveUnused(Node* p) noexcept
{
while (p && p->m_bValue == false && p->m_N == 0)
{
// эту вершину можно удалить
Node* x = p;
p = p->m_Parent;
if (!p)
{
// делаем дерево пустым
m_Root = nullptr;
}
else
{
p->Remove(x->m_Letter); // более быстро, чем p->Remove(x);
}
delete x;
}
return p;
}

// Тестовая печать дерева, вызывается без параметров
void Print(char* str = nullptr, Node* x = nullptr, int pos = 0) const;
// Тестовая печать слов дерева, вызывается без параметров
int PrintWords(char* str = nullptr, Node* x = nullptr, int pos = 0) const;

// Получить имя ключа, универсально - с/без '\0' в конце
bool GetKey(Handle h, char* p, int Size, bool bAdd0 = true, int* pSizeRequired = nullptr, int* pLen = nullptr) const noexcept
{
if (h)
{
return h->GetKey(p, Size, bAdd0, pSizeRequired, pLen);
}
if (Size > 0 && bAdd0)
{
*p = 0;
}
if (pSizeRequired)
{
*pSizeRequired = 0; // or 1
}
if (pLen)
{
*pLen = 0;
}
return false;
}

// Получить имя ключа в CMaaString
CMaaString GetKey(Handle h) const
{
if (h)
{
return h->GetKey();
}
CMaaString tmp;
return tmp;
}
};

#endif

#if 2

template < class Data, char ch0 = '\0', int AlphabetSize = 256 > class CMaaTrie2
{
protected:
struct Node
{
Node * m_Parent; // родительская вершина
char m_Value[sizeof(Data)]; // значение
Node * m_Nodes[AlphabetSize]; // вершины, соответствующие буквам
char m_Letter; // буква
bool m_bValue; // эта вершина - слово, m_Value имеет смысл

Node(Node * Parent, char Letter) noexcept
: m_Parent(Parent),
m_Letter(Letter),
m_bValue(false)
{
memset(m_Nodes, 0, sizeof(m_Nodes));
#ifdef __ALLOCATOR_FILL
memset(m_Value, __ALLOCATOR_FILL_INIT_CHAR, sizeof(m_Value));
#endif
}

~Node() noexcept
{
for (int i = 0; i < AlphabetSize; i++)
{
delete m_Nodes[i];
}
if (m_bValue)
{
Data * d = (Data *)m_Value;
d->~Data();
#ifdef __ALLOCATOR_FILL
memset(m_Value, __ALLOCATOR_FILL_FREE_CHAR, sizeof(m_Value));
#endif
}
}

// Удаление с поиском по букве
/*
bool Remove(char c)
{
return Remove(Find<false>(c));
}
*/

// slow
int GetCount() const noexcept // slow
{
int N = 0;
for (int idx = 0; idx < AlphabetSize; idx++)
{
if (m_Nodes[idx])
{
N++;
}
}
return N;
}

Node* FindN1(int idx) const noexcept
{
while (++idx < AlphabetSize)
{
if (m_Nodes[idx])
{
return m_Nodes[idx];
}
}
return nullptr;
}

Node* FindP1(int idx) const noexcept
{
while (--idx >= 0)
{
if (m_Nodes[idx])
{
return m_Nodes[idx];
}
}
return nullptr;
}

// Поиск первой вершины относительно позиции
static Node* FirstAtPos(Node* p) noexcept
{
while (!p->m_bValue)
{
Node* n = p->FindN1(-1);
if (!n)
{
break;
}
p = n;
}
return p; // p->m_bValue == true по построению
}

// Поиск первой вершины относительно позиции
Node * FirstAtPos(int pos) const noexcept
{
return FirstAtPos(m_Nodes[pos]);
}

// Поиск последней вершины относительно позиции
static Node* LastAtPos(Node* p) noexcept
{
while (1)
{
Node* n = p->FindP1(AlphabetSize);
if (!n)
{
break;
}
p = n;
}
return p; // p->m_bValue == true по построению
}

// Поиск последней вершины относительно позиции
Node * LastAtPos(int pos) const noexcept
{
return LastAtPos(m_Nodes[pos]);
}

// Поиск следующей вершины через родителя
Node * NextAtTop() const noexcept
{
Node * p = (Node *)this;
while(p)
{
const int pos = (int)(unsigned char)p->m_Letter;
p = p->m_Parent;
if (!p)
{
break;
}
Node* n = p->FindN1(pos);
if (n)
{
return FirstAtPos(n);
}
}
return p;
}

// Поиск предыдущей вершины через родителя
Node* PrevAtTop() const noexcept
{
Node* p = (Node*)this;
while (p)
{
const int pos = (int)(unsigned char)p->m_Letter;
p = p->m_Parent;
if (!p)
{
break;
}
Node* n = p->FindP1(pos);
if (n)
{
return LastAtPos(n);
}
if (p->m_bValue)
{
break;
}
}
return p;
}

// Получение имени ключа
bool GetKey(char *p, int Size, bool bAdd0 = true, int *pSizeRequired = nullptr, int *pLen = nullptr) const noexcept
{
const Node * n = this;
int len = 0;
while(n->m_Parent)
{
//int pos = n->m_Parent->Find(n); // slow, use when there is no n->m_Letter; pos >= 0 && pos < n->m_Parent->m_N по построению
if (len < Size)
{
//p[len] = n->m_Parent->m_Letters[pos];
p[len] = n->m_Letter + ch0;
}
len++;
n = n->m_Parent;
}
int SizeRequired = len + (bAdd0 ? 1 : 0);
if (pSizeRequired)
{
*pSizeRequired = SizeRequired;
}
if (pLen)
{
*pLen = len;
}
if (Size < SizeRequired)
{
if (Size > 0 && bAdd0)
{
*p = 0;
}
return false;
}
for (int i = len / 2; i--;)
{
const char c = p[i];
p[i] = p[len - 1 - i];
p[len - 1 - i] = c;
}
if (bAdd0)
{
p[len] = 0;
}
return true;
}

// Получение имени ключа
CMaaString GetKey() const
{
char Buffer[TOOLSLIB_CS_4K];
CMaaConcatString c(Buffer, sizeof(Buffer));

const Node * n = this;
int len = 0;
while(n->m_Parent)
{
c += (char)(n->m_Letter + ch0);
len++;
n = n->m_Parent;
}
CMaaString r = c;
if (r.Length() != len)
{
r.Empty();
return r;
}
char *p = r.GetBuffer();
for (int i = len / 2; i--;)
{
char c = p[i];
p[i] = p[len - 1 - i];
p[len - 1 - i] = c;
}
return r;
}

private:
// Защита копирования
Node(const Node &);
Node & operator = (const Node &);
};

Node * m_Root;

private:
// Защита копирования
CMaaTrie2(const CMaaTrie2 &);
CMaaTrie2 & operator = (const CMaaTrie2 &);
public:
// Тип хандлера для пользователей
typedef Node * Handle;

class iterator
{
CMaaTrie2 * m_trie;
Handle m_Handle;
bool m_bDirect;
public:
iterator(CMaaTrie2 &t, Handle h, bool dir) noexcept
: m_trie(&t),
m_Handle(h),
m_bDirect(dir)
{
}
iterator(const iterator &That) noexcept
{
*this = That;
}
~iterator() noexcept
{
}
iterator & operator = (const iterator &That) noexcept
{
m_trie = That.m_trie;
m_Handle = That.m_Handle;
m_bDirect = That.m_bDirect;
return *this;
}
void Swap(iterator &That) noexcept
{
iterator tmp(*this);
*this = That;
That = tmp;
}
iterator operator++(int) noexcept
{
iterator tmp(*this);
++(*this);
return tmp;
}
iterator operator++() noexcept
{
m_Handle = m_bDirect ? m_trie->Next(m_Handle) : m_trie->Prev(m_Handle);
return *this;
}
iterator operator--(int) noexcept
{
iterator tmp(*this);
--(*this);
return tmp;
}
iterator operator--() noexcept
{
m_Handle = m_bDirect ? m_trie->Prev(m_Handle) : m_trie->Next(m_Handle);
return *this;
}
bool operator==(const iterator &That) const noexcept
{
return m_Handle == That.m_Handle && m_trie == That.m_trie && m_bDirect == That.m_bDirect;
}
bool operator!=(const iterator &That) const noexcept
{
return !(*this == That);
}
operator Handle() noexcept
{
return m_Handle;
}
bool GetKey(char *p, int Size, bool bAdd0 = true, int *pSizeRequired = nullptr, int *pLen = nullptr) const noexcept
{
return m_trie->GetKey(m_Handle, p, Size, bAdd0, pSizeRequired, pLen);
}
CMaaString GetKey() const
{
return m_trie->GetKey(m_Handle);
}
/*
const Key & ckey()
{
if (!IsValid())
{
throw 1;
}
return r->K;
}
Key key()
{
if (!IsValid())
{
throw 1;
}
return r->K;
}
*/
Data & rdata() noexcept(std::is_nothrow_move_constructible<Data>::value)
{
return m_trie->Value(m_Handle);
}
Data data() noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return m_trie->GetValue(m_Handle);
}
bool Remove(Data * pval = nullptr) noexcept(noexcept(*pval=*pval))
{
return m_trie->Remove(m_Handle, pval);
}
};

// Конструктор
CMaaTrie2() noexcept
{
m_Root = nullptr;
}

// Деструктор
virtual ~CMaaTrie2()
{
delete m_Root;
}

// inline functions
// Добавить ключ str со значением val
bool Add(const char * str, const Data &val)
{
return Add(str, (int)strlen(str), val);
}

// Удалить ключ str, вернув значение в *pval
bool Remove(const char * str, Data *pval = nullptr) noexcept(noexcept(*pval=*pval))
{
return Remove(str, (int)strlen(str), pval);
}

// Не рекомендуем в api, упрощённый интерфейс для задания
Data Find(const char * str) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return Find(str, (int)strlen(str));
}

// Не рекомендуем в api, упрощённый интерфейс для задания
Data Find(const char * str, int len) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
Data v{};// = -1; // возвращаем -1, если слово не найдено
Find(str, len, &v);
return v;
}

// Рекомендуем в api, более удобная функция
bool Find(const char * str, Data * pval) const noexcept(noexcept(*pval=*pval))
{
return Find(str, (int)strlen(str), pval);
}

// Поиск последующего слова > str или >= str, если bEqual = true
Handle FindGQ(const char * str, bool bEqual = false) const noexcept
{
return FindGQ(str, (int)strlen(str), bEqual);
}

// Поиск предшествующего слова < str или <= str, если bEqual = true
Handle FindLQ(const char * str, bool bEqual = false) const noexcept
{
return FindLQ(str, (int)strlen(str), bEqual);
}

// CMaaString - functions
//////////
// Добавить ключ str со значением val
bool AddS(CMaaString str, const Data &val) noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return Add((const char *)str, str.Length(), val);
}
// Удалить ключ str, вернув значение в *pval
bool RemoveS(CMaaString str, Data *pval = nullptr) noexcept(noexcept(*pval=*pval))
{
return Remove((const char *)str, str.Length(), pval);
}
// Не рекомендуем в api, упрощённый интерфейс для задания
Data FindS(CMaaString str) const noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return Find((const char *)str, str.Length());
}
// Рекомендуем в api, более удобная функция
bool FindS(CMaaString str, Data * pval) const noexcept(noexcept(*pval=*pval))
{
return Find((const char *)str, str.Length(), pval);
}
// Поиск последующего слова > str или >= str, если bEqual = true
Handle FindGQS(CMaaString str, bool bEqual = false) const noexcept
{
return FindGQ((const char *)str, str.Length(), bEqual);
}
// Поиск предшествующего слова < str или <= str, если bEqual = true
Handle FindLQS(CMaaString str, bool bEqual = false) const noexcept
{
return FindLQ((const char *)str, str.Length(), bEqual);
}
//////////

// Поиск первого слова
Handle First() const noexcept
{
Node * x = m_Root;
if (x && x->m_bValue == false)
{
x = x->FindN1(-1);
x = Node::FirstAtPos(x);
}
return x;
}

// Поиск последнего слова
Handle Last() const noexcept
{
Node * x = m_Root;
if (x)
{
x = x->FindP1(AlphabetSize);
x = Node::LastAtPos(x);
}
return x;
}

iterator begin() noexcept
{
iterator it(*this, First(), true);
return it;
}

iterator end() noexcept
{
iterator it(*this, nullptr, true);
return it;
}

iterator rbegin() noexcept
{
iterator it(*this, Last(), false);
return it;
}

iterator rend() noexcept
{
iterator it(*this, nullptr, false);
return it;
}

iterator it(Handle h, bool dir = true) noexcept
{
iterator it(*this, h, dir);
return it;
}

// Не рекомендуем в api, для задания
// Ссылка на значение по хандлеру
Data & Value(Handle h) noexcept(std::is_nothrow_move_constructible<Data>::value)
{
// не рекомендуется
static Data v0{};
return h ? *(Data *)h->m_Value : (v0);// = -1);
}

// Не рекомендуем в api, для задания
// Получение значение по хандлеру
Data GetValue(Handle h) noexcept(std::is_nothrow_move_constructible<Data>::value&& std::is_nothrow_move_assignable<Data>::value)
{
return Value(h);
}

// Рекомендуем в api, для задания
// Получение значения по хандлеру, может вернуть false если h не слово
bool GetValue(Handle h, Data *pval) noexcept(noexcept(*pval=*pval))
{
if (h && h->m_bValue)
{
if (pval)
{
*pval = *(Data *)h->m_Value;
}
return true;
}
return false;
}

// Установка значения по хандлеру, может вернуть false если h не слово
bool SetValue(Handle h, const Data &v) noexcept(std::is_nothrow_move_assignable<Data>::value)
{
if (h && h->m_bValue)
{
*(Data *)h->m_Value = v;
return true;
}
return false;
}

// Поиск узла по ключу, ключ может быть не словом
Handle FindHandle(const char * str) const noexcept
{
return FindHandle(str, (int)strlen(str));
}

// Получить ключ без '\0' в конце
bool GetKey(Handle h, char *p, int Size, int *pSizeRequired, int *pLen) const noexcept
{
return GetKey(h, p, Size, false, pSizeRequired, pLen);
}

// Основные функции для не null-terminated строк

// Добавить слово str длиной len со значением val
bool Add(const char * str, int len, const Data &val)
{
if (/*val < 0 ||*/ len <= 0)
{
return false; // недопустимое значение value или len
}
if (!m_Root)
{
m_Root = TL_NEW Node(nullptr, '\0');
if (!m_Root)
{
return false;
}
}
Node * p = m_Root;
int i = 0;
try
{
for (; i < len; i++)
{
const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
if (c < 0 || c >= AlphabetSize)
{
// break;
throw 1;
}
Node* n = p->m_Nodes[c];
if (!n)
{
n = p->m_Nodes[c] = TL_NEW Node(p, (char)c);
if (!n)
{
// break;
throw 1;
}
}
p = n;
}
if (i >= len)
{
Data * d = (Data *)p->m_Value;
if (!p->m_bValue)
{
#ifdef __ALLOCATOR_FILL
memset(p->m_Value, __ALLOCATOR_FILL_ALLOC_CHAR, sizeof(p->m_Value));
#endif
new_(d, Data(val));
}
else
{
*d = val;
}
p->m_bValue = true;
return true;
}
}
catch(...)
{
RemoveUnused(p);
throw;
}
if (i < len)
{
RemoveUnused(p);
return false;
}
return true;
}

// Удалить слово str длиной len, вернув значение в *pval
bool Remove(const char * str, int len, Data *pval = nullptr) noexcept(noexcept(*pval=*pval))
{
Node * p = FindHandle(str, len);
return Remove(p, pval);
}

// Удалить слово вершины p, вернув значение в *pval
bool Remove(Node * p, Data *pval = nullptr) noexcept(noexcept(*pval=*pval))
{
if (p && p->m_bValue)
{
Data * d = (Data *)p->m_Value;
if (pval)
{
*pval = *d;
}
d->~Data();
#ifdef __ALLOCATOR_FILL
memset(p->m_Value, __ALLOCATOR_FILL_FREE_CHAR, sizeof(p->m_Value));
#endif
p->m_bValue = false;
RemoveUnused(p);
return true;
}
return false;
}

// Поиск вершины по ключу, может вернуть вершину - не слово
Handle FindHandle(const char * str, int len) const noexcept
{
Node * p = m_Root;
for (int i = 0; i < len && p; i++)
{
const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
if (c < 0 || c >= AlphabetSize)
{
return nullptr;
}
p = p->m_Nodes[c];
}
return p;
}

// Поиск слова, возврат значения в *pval, return true on success
bool Find(const char * str, int len, Data *pval) const noexcept(noexcept(*pval=*pval))
{
Node * x = FindHandle(str, len);
if (x && x->m_bValue == false)
{
// не слово
return false;
}
if (x && pval)
{
*pval = *(Data *)x->m_Value;
}
return x ? true : false;
}

// Поиск последующего слова > str или >= str, если bEqual = true
Handle FindGQ(const char * str, int len, bool bEqual = false) const noexcept
{
Node * p = m_Root;
for (int i = 0; i < len && p; i++)
{
const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
if ((c < 0 || c >= AlphabetSize) || !p->m_Nodes[c])
{
Node* n = c < 0 ? p->FindN1(-1) : c >= AlphabetSize ? nullptr : p->FindN1(c);
if (n)
{
return Node::FirstAtPos(n);
}
return p->NextAtTop();
}
p = p->m_Nodes[c];
}
if (p && (!bEqual || p->m_bValue == false))
{
p = Next(p);
}
return p;
}

// Поиск предшествующего слова < str или <= str, если bEqual = true
Handle FindLQ(const char * str, int len, bool bEqual = false) const noexcept
{
Node * p = m_Root;
for (int i = 0; i < len && p; i++)
{
const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
if ((c < 0 || c >= AlphabetSize) || !p->m_Nodes[c])
{
Node* n = c >= AlphabetSize ? p->FindP1(AlphabetSize) : c < 0 ? nullptr : p->FindP1(c);
if (n)
{
return Node::LastAtPos(n);
}
return p->PrevAtTop();
}
p = p->m_Nodes[c];
}
if (p && (!bEqual || p->m_bValue == false))
{
p = Prev(p);
}
return p;
}

// Определение максимального пути (слова/части слова)
Handle MaxPath(const char * str, int len, int *plen, int *pincompleteLen = nullptr, Data *pval = nullptr) const noexcept(noexcept(*pval=*pval))
{
int rlen = 0, inclen = 0;
Handle r = nullptr;

Node * p = m_Root;
for (int i = 0; i < len && p; i++)
{
const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
if (c < 0 || c >= AlphabetSize)
{
break;
// throw 1;
}
p = p->m_Nodes[c];
if (!p)
{
break;
}
inclen++;
if (p->m_bValue)
{
rlen = inclen;
r = p;
}
}
if (plen)
{
*plen = rlen;
}
if (pincompleteLen)
{
*pincompleteLen = inclen;
}
if (r && pval)
{
*pval = *(Data *)r->m_Value;
}
return r;
}

// Определение первого пути (слова/части слова)
Handle FirstPath(const char * str, int len, int *plen, int *pincompleteLen = nullptr, Data *pval = nullptr) const noexcept(noexcept(*pval=*pval))
{
int rlen = 0, inclen = 0;
Handle r = nullptr;

Node * p = m_Root;
for (int i = 0; i < len && p; i++)
{
const int c = (int)(unsigned char)str[i] - (int)(unsigned char)ch0;
if (c < 0 || c >= AlphabetSize)
{
break;
//throw 1;
}
p = p->m_Nodes[c];
if (!p)
{
break;
}
inclen++;
if (p->m_bValue)
{
rlen = inclen;
r = p;
break; // первое существующее слово
}
}
if (plen)
{
*plen = rlen;
}
if (pincompleteLen)
{
*pincompleteLen = inclen;
}
if (r && pval)
{
*pval = *(Data *)r->m_Value;
}
return r;
}

// Следующее слово
Handle Next(Handle p) const noexcept
{
if (p)
{
Node* n = p->FindN1(-1);
if (n)
{
return Node::FirstAtPos(n);
}
return p->NextAtTop();
}
return nullptr;
}

// Предшествующее слово
Handle Prev(Handle p) const noexcept
{
if (p)
{
return p->PrevAtTop();
}
return nullptr;
}

// Удалить вершины-не слова без дочерних, поднимаясь вверх
Node * RemoveUnused(Node * p) noexcept
{
while (p && p->m_bValue == false)
{
if (p->FindN1(-1))
{
return p;
}

// эту вершину можно удалить
Node * x = p;
p = p->m_Parent;
if (!p)
{
// делаем дерево пустым
m_Root = nullptr;
}
else
{
const int c = (int)(unsigned char)x->m_Letter;
p->m_Nodes[c] = nullptr;
}
delete x;
}
return p;
}

// Тестовая печать дерева, вызывается без параметров
void Print(char * str = nullptr, Node * x = nullptr, int pos = 0) const;
// Тестовая печать слов дерева, вызывается без параметров
int PrintWords(char * str = nullptr, Node * x = nullptr, int pos = 0) const;

// Получить имя ключа, универсально - с/без '\0' в конце
bool GetKey(Handle h, char *p, int Size, bool bAdd0 = true, int *pSizeRequired = nullptr, int *pLen = nullptr) const noexcept
{
if (h)
{
return h->GetKey(p, Size, bAdd0, pSizeRequired, pLen);
}
if (Size > 0 && bAdd0)
{
*p = 0;
}
if (pSizeRequired)
{
*pSizeRequired = 0; // or 1
}
if (pLen)
{
*pLen = 0;
}
return false;
}

// Получить имя ключа в CMaaString
CMaaString GetKey(Handle h) const
{
if (h)
{
return h->GetKey();
}
CMaaString tmp;
return tmp;
}
};

#endif

#if 0
// Тестовая печать дерева, вызывается без параметров
template <> void CMaaTrie<int>::Print(char * str, Node * x, int pos) const
{
if (!x)
{
if (str)
{
printf("%s !null\n", str);
return;
}
printf("tree:\n"); fflush(stdout);
static CMaaString buff(nullptr, 10 * 1024 + 1);
str = (char *)(const char *)buff; *str = 0; pos = 0;
x = m_Root;
if (!x)
{
printf("empty\n"); fflush(stdout);
return;
}
}
if (x->m_bValue)
{
printf("%p %-15s v=%4d n=%4d ", x, str, *(int *)x->m_Value, x->m_N);
}
else
{
printf("%p %-15s v=%4s n=%4d ", x, str, "***", x->m_N);
}
for (int i = 0; i < x->m_N; i++)
{
printf("%c(%02x) ", x->m_Letters[i], (unsigned char)x->m_Letters[i]);
}
printf("\n");
char * str2 = str + pos;
if (str2 - str2 < 10 * 1024)
{
for (int i = 0; i < x->m_N; i++)
{
str2[0] = x->m_Letters[i];
str2[1] = 0;
Print(str, x->m_Nodes[i], pos + 1);
str2[0] = 0;
}
}
}

// Тестовая печать слов дерева, вызывается без параметров
template <> int CMaaTrie<int>::PrintWords(char * str, Node * x, int pos) const
{
int V = 0;
if (!x)
{
if (str)
{
#ifdef TRIE10_DEBUG
m_bDbg && printf("%s null\n", str);
#endif
return -1;
}
//printf("tree:\n");
static CMaaString buff(nullptr, 10 * 1024 + 1);
str = (char *)(const char *)buff; *str = 0; pos = 0;
x = m_Root;
if (!x)
{
//printf("empty\n");
return V;
}
}
if (x->m_bValue)
{
V += *(int *)x->m_Value;
printf("%05d %-15s\n", *(int *)x->m_Value, str);
}
char * str2 = str + pos;
if (str2 - str < 10 * 1024)
{
for (int i = 0; i < x->m_N; i++)
{
str2[0] = x->m_Letters[i];
str2[1] = 0;
V += PrintWords(str, x->m_Nodes[i], pos + 1);
str2[0] = 0;
}
}
return V;
}
#endif

#if 0

// Тестовая печать дерева, вызывается без параметров
template <> void CMaaTrie2<int, '\0', 256>::Print(char* str, Node* x, int pos) const
{
if (!x)
{
if (str)
{
printf("%s !null\n", str);
return;
}
printf("tree:\n"); fflush(stdout);
static CMaaString buff(nullptr, 10 * 1024 + 1);
str = (char*)(const char*)buff; *str = 0; pos = 0;
x = m_Root;
if (!x)
{
printf("empty\n"); fflush(stdout);
return;
}
}
if (x->m_bValue)
{
printf("%p %-15s v=%4d n=%4d ", x, str, *(int*)x->m_Value, x->GetCount());
}
else
{
printf("%p %-15s v=%4s n=%4d ", x, str, "***", x->GetCount());
}
//for (int i = 0; i < x->m_N; i++)
//{
// printf("%c(%02x) ", x->m_Letters[i], (unsigned char)x->m_Letters[i]);
//}
for (int i = 0; i < 256; i++)
{
if (x->m_Nodes[i])
{
printf("%c(%02x) ", (char)(i + 0), (i + 0));
}
}
printf("\n");
char* str2 = str + pos;
if (str2 - str2 < 10 * 1024)
{
/*
for (int i = 0; i < x->m_N; i++)
{
str2[0] = x->m_Letters[i];
str2[1] = 0;
Print(str, x->m_Nodes[i], pos + 1);
str2[0] = 0;
}
*/
for (int i = 0; i < 256; i++)
{
if (x->m_Nodes[i])
{
str2[0] = (char)(i + 0);
str2[1] = 0;
Print(str, x->m_Nodes[i], pos + 1);
str2[0] = 0;
}
}
}
}

// Тестовая печать слов дерева, вызывается без параметров
template <> int CMaaTrie2<int, '\0', 256>::PrintWords(char* str, Node* x, int pos) const
{
int V = 0;
if (!x)
{
if (str)
{
#ifdef TRIE10_DEBUG
m_bDbg&& printf("%s null\n", str);
#endif
return -1;
}
//printf("tree:\n");
static CMaaString buff(nullptr, 10 * 1024 + 1);
str = (char*)(const char*)buff; *str = 0; pos = 0;
x = m_Root;
if (!x)
{
//printf("empty\n");
return V;
}
}
if (x->m_bValue)
{
V += *(int*)x->m_Value;
printf("%05d %-15s\n", *(int*)x->m_Value, str);
}
char* str2 = str + pos;
if (str2 - str < 10 * 1024)
{
/*
for (int i = 0; i < x->m_N; i++)
{
str2[0] = x->m_Letters[i];
str2[1] = 0;
V += PrintWords(str, x->m_Nodes[i], pos + 1);
str2[0] = 0;
}
*/
for (int i = 0; i < 256; i++)
{
if (x->m_Nodes[i])
{
str2[0] = (char)(i + 0);
str2[1] = 0;
V += PrintWords(str, x->m_Nodes[i], pos + 1);
str2[0] = 0;
}
}
}
return V;
}

#endif


#if 0
// CMaaTrie<int> test function
int main_test_CMaaTrie(int argn, const char * args[])
{
printf("Tests:\n");
{
printf("Test1: empty tree: "); fflush(stdout);
CMaaTrie<int> a;
printf("."); fflush(stdout);
printf("%s", a.Find("a", 1) < 0 ? "." : " fail "); fflush(stdout);
printf("%s", a.Find("abc", 1) < 0 ? "." : " fail "); fflush(stdout);
CMaaTrie<int>::Handle h = a.FindHandle("ab");
printf("%s", !h ? "." : " fail "); fflush(stdout);
printf("%s", !a.Remove("a") ? "." : " fail "); fflush(stdout);
printf("."); fflush(stdout);
h = a.FindGQ("ab");
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.Next(h);
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.First();
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.Next(h);
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.Last();
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.Prev(h);
printf("%s", !h ? "." : " fail "); fflush(stdout);
printf("\n"); fflush(stdout);
a.Print(); fflush(stdout);
printf("~"); fflush(stdout);
}
printf(".\n"); fflush(stdout);
printf("\n"); fflush(stdout);
{
printf("Test2: задание:\n");
CMaaTrie<int> a;
//a.SetDbg(true);
/*
a.Add("abc", 100);
a.Add("abx", 10);
a.Add("def", 2);
a.Print();
printf("%d ", a.Find("abc"));
printf("%d ", a.Find("abx"));
printf("%d ", a.Find("def"));
printf("%d ", a.Find("klm"));
printf("%d\n", a.Find("abd"));
printf("%s\n", a.Remove("def") ? "true" : "false");
printf("%d ", a.Find("abc"));
printf("%d ", a.Find("def"));
printf("%d ", a.Find("klm"));
printf("%d\n", a.Find("abd"));
a.Print();
*/
const char * s[] = {"альфа", "бета", "гамма", "дельта", "эпсилон", "одна", "однаждыы", nullptr};
printf("Find(not existed): %d\n", a.Find("бета"));
printf("Remove(not existed): %s\n", a.Remove("бета") ? "true" : "false");
int i;
for (i = 0; s[i]; i++)
{
bool b = a.Add(s[i], i + 1);
printf("Add %s %d %s ", s[i], i + 1, b ? "true" : "false");
printf("//Find(\"бета\") = %d\n", a.Find("бета"));
}
{
CMaaString s = "однажды";
int v = -1, len = -1, ilen = -1;
a.MaxPath(s, s.Length(), &len, &ilen, &v);
CMaaString p = s.Left(len);
CMaaString ip = s.Left(ilen);
printf("%s: %d %d ('%s', '%s') %d\n", (const char *)s, len, ilen, (const char *)p, (const char *)ip, v);
}
{
CMaaString s = "однаждыыхх";
int v = -1, len = -1, ilen = -1;
a.MaxPath(s, s.Length(), &len, &ilen, &v);
CMaaString p = s.Left(len);
CMaaString ip = s.Left(ilen);
printf("%s: %d %d ('%s', '%s') %d\n", (const char *)s, len, ilen, (const char *)p, (const char *)ip, v);
//return 0;
}
if (0)
{
a.Print();
printf("LQ:\n");
CMaaTrie<int>::Handle hh = a.FindGQ("бета");
printf("%p\n", hh);
}
bool bEqual = false;
//bEqual = true;
printf("Test2: values for key %s \"бета\": ", bEqual ? ">=" : ">");
for (CMaaTrie<int>::Handle h = a.FindGQ("бета", bEqual); h; h = a.Next(h))
{
//printf("%p %d\n", h, a.GetValue(h));
printf("%d ", a.GetValue(h));
}
printf("\n");
}
printf("\n");
{
printf("Test3: similar words: ");
CMaaTrie<int> a;
a.SetDbg(true);
a.Add("zabc", 101);
a.Add("zabcd", 102);
a.Add("zabcde", 103);
a.Add("zabcf", 104);
a.Add("zabcfe", 105);
a.Add("ax", 99);
a.Remove("zabcf");
printf("\n");
a.Print();
//gbDbgTrie10Nodes=true;
for (CMaaTrie<int>::Handle h = a.FindGQ("zabc"); h; h = a.Next(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindGQ("za"); h; h = a.Next(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindGQ("AB"); h; h = a.Next(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindGQ("{"); h; h = a.Next(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindLQ("zabc"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindLQ("zabcd"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindLQ("zabce"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindLQ("zabcfg"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindLQ("Z"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie<int>::Handle h = a.FindLQ("{"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
a.SetDbg(false);
//for (CMaaTrie<int>::iterator it = a.begin(); it; ++it)
for (CMaaTrie<int>::iterator it = a.begin(); it != a.end(); ++it)
{
char key[1024 + 1];
it.GetKey(key, (int)sizeof(key), true);
printf("[%s]:%d ", key, it.data());
}
printf("\n");
for (CMaaTrie<int>::iterator it = a.rbegin(); it != a.rend(); ++it)
{
char key[1024 + 1];
it.GetKey(key, (int)sizeof(key), true);
printf("[%s]:%d ", key, it.data());
}
printf("\n");
for (CMaaTrie<int>::iterator it = a.begin(); it != a.end(); )
{
char key[1024 + 1];
it.GetKey(key, (int)sizeof(key), true);
printf("[%s]:%d ", key, it.data());
CMaaTrie<int>::iterator r = it++;
r.Remove();
}
printf("\n");
for (CMaaTrie<int>::Handle p = a.First(); p; )
{
char key[1024 + 1];
a.GetKey(p, key, (int)sizeof(key), true);
printf("[%s] ", key);
CMaaTrie<int>::Handle n = a.Next(p);
a.Remove(p);
p = n;
}
printf("\n");
a.Print();
}
printf("\n");
return 0;
}

bool gbDbgTrie10Nodes = false;
int main(int argn, const char * args[])
{
return main_test_CMaaTrie(argn, args);
//return main_test_CMaaTrie2(argn, args);
}
#endif

#if 0

// CMaaTrie2<int> test function
int main_test_CMaaTrie2(int argn, const char* args[])
{
printf("Tests:\n");
{
printf("Test1: empty tree: "); fflush(stdout);
CMaaTrie2<int> a;
printf("."); fflush(stdout);
printf("%s", a.Find("a", 1) < 0 ? "." : " fail "); fflush(stdout);
printf("%s", a.Find("abc", 1) < 0 ? "." : " fail "); fflush(stdout);
CMaaTrie2<int>::Handle h = a.FindHandle("ab");
printf("%s", !h ? "." : " fail "); fflush(stdout);
printf("%s", !a.Remove("a") ? "." : " fail "); fflush(stdout);
printf("."); fflush(stdout);
#if 1
h = a.FindGQ("ab");
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.Next(h);
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.First();
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.Next(h);
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.Last();
printf("%s", !h ? "." : " fail "); fflush(stdout);
h = a.Prev(h);
printf("%s", !h ? "." : " fail "); fflush(stdout);
#endif
printf("\n"); fflush(stdout);
a.Print(); fflush(stdout);
printf("~"); fflush(stdout);
}
printf(".\n"); fflush(stdout);
printf("\n"); fflush(stdout);
{
printf("Test2: задание:\n");
CMaaTrie2<int> a;
//a.SetDbg(true);
/*
a.Add("abc", 100);
a.Add("abx", 10);
a.Add("def", 2);
a.Print();
printf("%d ", a.Find("abc"));
printf("%d ", a.Find("abx"));
printf("%d ", a.Find("def"));
printf("%d ", a.Find("klm"));
printf("%d\n", a.Find("abd"));
printf("%s\n", a.Remove("def") ? "true" : "false");
printf("%d ", a.Find("abc"));
printf("%d ", a.Find("def"));
printf("%d ", a.Find("klm"));
printf("%d\n", a.Find("abd"));
a.Print();
*/
const char* s[] = { "альфа", "бета", "гамма", "дельта", "эпсилон", "одна", "однаждыы", nullptr };
printf("Find(not existed): %d\n", a.Find("бета"));
printf("Remove(not existed): %s\n", a.Remove("бета") ? "true" : "false");
int i;
for (i = 0; s[i]; i++)
{
const bool b = a.Add(s[i], i + 1);
printf("Add %s %d %s ", s[i], i + 1, b ? "true" : "false");
printf("//Find(\"бета\") = %d\n", a.Find("бета"));
}
{
CMaaString s = "однажды";
int v = -1, len = -1, ilen = -1;
a.MaxPath(s, s.Length(), &len, &ilen, &v);
CMaaString p = s.Left(len);
CMaaString ip = s.Left(ilen);
printf("%s: %d %d ('%s', '%s') %d\n", (const char*)s, len, ilen, (const char*)p, (const char*)ip, v);
}
{
CMaaString s = "однаждыыхх";
int v = -1, len = -1, ilen = -1;
a.MaxPath(s, s.Length(), &len, &ilen, &v);
CMaaString p = s.Left(len);
CMaaString ip = s.Left(ilen);
printf("%s: %d %d ('%s', '%s') %d\n", (const char*)s, len, ilen, (const char*)p, (const char*)ip, v);
//return 0;
}
#if 1
if (1)
{
a.Print();
printf("LQ:\n");
CMaaTrie2<int>::Handle hh = a.FindGQ("бета");
printf("%p\n", hh);
a.PrintWords();
}
bool bEqual = false;
//bEqual = true;
printf("Test2: values for key %s \"бета\": ", bEqual ? ">=" : ">");
for (CMaaTrie2<int>::Handle h = a.FindGQ("бета", bEqual); h; h = a.Next(h))
{
//printf("%p %d\n", h, a.GetValue(h));
printf("%d ", a.GetValue(h));
}
printf("\n");
#endif
}
printf("\n");
{
printf("Test3: similar words: ");
CMaaTrie2<int> a;
//a.SetDbg(true);
a.Add("zabc", 101);
a.Add("zabcd", 102);
a.Add("zabcde", 103);
a.Add("zabcf", 104);
a.Add("zabcfe", 105);
a.Add("ax", 99);
a.Remove("zabcf");
printf("\n");
a.Print();
//gbDbgTrie10Nodes=true;
#if 1
for (CMaaTrie2<int>::Handle h = a.FindGQ("zabc"); h; h = a.Next(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindGQ("za"); h; h = a.Next(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindGQ("AB"); h; h = a.Next(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindGQ("{"); h; h = a.Next(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindLQ("zabc"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindLQ("zabcd"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindLQ("zabce"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindLQ("zabcfg"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindLQ("Z"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
for (CMaaTrie2<int>::Handle h = a.FindLQ("{"); h; h = a.Prev(h))
{
printf("%d ", a.GetValue(h));
}
printf("\n");
#endif
//a.SetDbg(false);
//for (CMaaTrie2<int>::iterator it = a.begin(); it; ++it)
for (CMaaTrie2<int>::iterator it = a.begin(); it != a.end(); ++it)
{
char key[1024 + 1];
it.GetKey(key, (int)sizeof(key), true);
printf("[%s]:%d ", key, it.data());
}
printf("\n");
for (CMaaTrie2<int>::iterator it = a.rbegin(); it != a.rend(); ++it)
{
char key[1024 + 1];
it.GetKey(key, (int)sizeof(key), true);
printf("[%s]:%d ", key, it.data());
}
printf("\n");
for (CMaaTrie2<int>::iterator it = a.begin(); it != a.end(); )
{
char key[1024 + 1];
it.GetKey(key, (int)sizeof(key), true);
printf("[%s]:%d ", key, it.data());
CMaaTrie2<int>::iterator r = it++;
r.Remove();
}
printf("\n");
for (CMaaTrie2<int>::Handle p = a.First(); p; )
{
char key[1024 + 1];
a.GetKey(p, key, (int)sizeof(key), true);
printf("[%s] ", key);
CMaaTrie2<int>::Handle n = a.Next(p);
a.Remove(p);
p = n;
}
printf("\n");
a.Print();
}
printf("\n");
return 0;
}

int main(int argn, const char* args[])
{
//return main_test_CMaaTrie(argn, args);
return main_test_CMaaTrie2(argn, args);
}
#endif

#if 0

#define CMaaTrie_ver 1 // v.1 is the faster

#if CMaaTrie_ver == 1
#else
#define CMaaTrie CMaaTrie2
#endif

int main_pushkin(int argn, const char* args[])
{
//main_test_CMaaTrie(argn, args);
if (argn > 1)
{
CMaaTrie<int> a;
CMaaUnivHash<CMaaString, int> ht;
CMaaFile f(args[1], CMaaFile::eR_SrSw, false); // "pushkin_stihi.txt"
CMaaString txt;
CMaaString RussianAlphabet = "АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯабвгдежзийклмнопрстуфхцчшщъыьэюя";
RussianAlphabet = Utf8ToAnsi(RussianAlphabet);
CMaaString sp(NULL, 256);
for (int ch = 0; ch < 256; ch++)
{
sp[ch] = RussianAlphabet.Find((char)ch) < 0 ? (char)ch : ' ';
}
//sp += " \t\r\n";
CMaaString ut = "игр";
__utf8_printf("%S ", &ut);
CMaaString t = Utf8ToAnsi(ut);
int t0 = 0;// -1;
CHrtMultiTimer tmr;
tmr.Start();
while (txt.IsNotEmpty() || f.IsOpen())
{
if (txt.Length() < 1 * 1024 && f.IsOpen())
{
txt += f.Read(4 * 1024);
if (f.IsEOF())
{
f.Close();
}
}
CMaaString w = txt.GetWord(true, true, sp).ToLower(1251);
CMaaString u = UnicodeToUtf8(AnsiToUnicode(w));
int v = 0;
a.Find(w, w.Length(), &v);
v++;
if (v <= 0)
{
__utf8_printf("%-15S == %d\n", &u, v);
}
a.Add(w, w.Length(), v);
int v2 = a.Find(w, w.Length());
if (v2 != v)
{
__utf8_printf("%-15S %d <> %d\n", &u, v2, v);
}
else
{
//__utf8_printf("%-15S %d\n", &u, v2);
}
int vt = 0;
ht.Find(w, &vt);
vt++;
ht.AddOver(w, vt);
if (vt != v)
{
__utf8_printf("%-15S %d <> %d(ht)\n", &u, v, vt);
}
if (w == t)
{
if (!++t0)
{
t0++;
}
}
v = a.Find(t, t.Length());
if (t0 != v)
{
__utf8_printf("after %S #%d: %S = %d <> %d\n", &u, v2, &ut, v, t0);
}
}
tmr.Stop("Add/Find");
int V = a.PrintWords();
fflush(stdout);
__utf8_printf(" %d\n", V);

V = 0;
#if CMaaTrie_ver == 1
const char* p_min_1 = "\x80";
const char* p_max_12 = "\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7f";
#else
const char* p_min_1 = "\x00";
const char* p_max_12 = "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff";
#endif
const int p_max_len = (int)strlen(p_max_12);

int N = a.Find(p_min_1, 1, &V) ? 1 : 0;
//gbDbgTrie10Nodes = true;
CMaaTrie<int>::Handle h0 = NULL;
tmr.Start();
for (CMaaTrie<int>::Handle h = a.FindGQ(p_min_1, 1); h; h = a.Next(h))
{
if (!h0)
{
h0 = h;
__utf8_printf("%p ", h);
}
N++;
V += a.GetValue(h);
//__utf8_printf("%d\n", N);
}
tmr.Stop("Next");
__utf8_printf("%d %d >\n", N, V);

V = 0;
N = a.Find(p_max_12, p_max_len, &V) ? 1 : 0;
//gbDbgTrie10Nodes = true;
h0 = NULL;
tmr.Start();
for (CMaaTrie<int>::Handle h = a.FindLQ(p_max_12, p_max_len); h; h = a.Prev(h))
{
if (!h0)
{
h0 = h;
__utf8_printf("%p ", h);
}
N++;
V += a.GetValue(h);
//__utf8_printf("%d\n", N);
}
tmr.Stop("Prev");
__utf8_printf("%d %d <\n", N, V);
//__utf8_printf("%d\n", a.Find(t, t.Length()));

CMaaString res = tmr.GetResult("CMaaTrie<int>:\n");
__utf8_printf("%S\n", &res);

V = 0; N = 0;
CMaaUnivHash<CMaaString, int>::iterator it(ht);
for (; it; ++it)
{
N++;
V += it.data();
}
__utf8_printf("%d %d ht\n", N, V);

h0 = a.First(); __utf8_printf("%p ", h0);
h0 = a.Last(); __utf8_printf("%p\n", h0);

CMaaPtrAE<CMaaTrie<int>::Handle> m(N);
int idx = 0;
for (CMaaTrie<int>::Handle h = a.First(); h; h = a.Next(h))
{
m[idx] = h;
a.SetValue(h, idx);
idx++;
}
CMaaString w1, w2;
for (CMaaTrie<int>::Handle h = a.Last(); h; h = a.Prev(h))
{
--idx;
if (m[idx] != h)
{
__utf8_printf("%4d %p:%d <> %p:%d\n", idx, h, a.GetValue(h), (CMaaTrie<int>::Handle)m[idx], a.GetValue(m[idx]));
}
char k[256];
*k = 0;
a.GetKey(h, k, 256);
w2 = k;
if (w1 < w2)
{
__utf8_printf("%4d %p %4d %S < %S\n", idx, h, a.GetValue(h), &w1, &w2);
}
w1 = w2;
}

return 0;
}
return 0;
}

#endif