From 9f21b7f9adee7f803f04ea168b6d461f4baa37b2 Mon Sep 17 00:00:00 2001
From: Stefan Schimanski <sts@lyx.org>
Date: Mon, 25 Feb 2008 01:56:53 +0000
Subject: [PATCH] * high performance text completion with weighted btrees to
 get pseudo   random-access (i.e. O(log n)) to the n-th element in a list/set.
 Try   it with 1000000 keys ... no problem.

git-svn-id: svn://svn.lyx.org/lyx/lyx-devel/trunk@23213 a592a061-630c-0410-9148-cb99ea01b6c8
---
 development/scons/scons_manifest.py |  2 +
 src/Makefile.am                     |  8 +--
 src/WordList.cpp                    | 80 +++++++++++++++++++++++++++++
 src/WordList.h                      | 40 +++++++++++++++
 4 files changed, 127 insertions(+), 3 deletions(-)
 create mode 100644 src/WordList.cpp
 create mode 100644 src/WordList.h

diff --git a/development/scons/scons_manifest.py b/development/scons/scons_manifest.py
index e98ed90193..485d5ae27a 100644
--- a/development/scons/scons_manifest.py
+++ b/development/scons/scons_manifest.py
@@ -138,6 +138,7 @@ src_header_files = Split('''
     sgml.h
     update_flags.h
     version.h
+    WordList.h
 ''')
 
 
@@ -234,6 +235,7 @@ src_pre_files = Split('''
     rowpainter.cpp
     sgml.cpp
     version.cpp
+    WordList.cpp
 ''')
 
 
diff --git a/src/Makefile.am b/src/Makefile.am
index e30ac8fad6..dd76a4c2cc 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -127,6 +127,7 @@ SOURCEFILESCORE = \
 	lengthcommon.cpp \
 	Lexer.cpp \
 	LyX.cpp \
+	LyXAction.cpp
 	lyxfind.cpp \
 	LyXFunc.cpp \
 	LyXRC.cpp \
@@ -142,6 +143,7 @@ SOURCEFILESCORE = \
 	output_plaintext.cpp \
 	Paragraph.cpp \
 	paragraph_funcs.cpp \
+	ParagraphMetrics.cpp \
 	ParagraphParameters.cpp \
 	ParIterator.cpp \
 	PDFOptions.cpp \
@@ -165,8 +167,7 @@ SOURCEFILESCORE = \
 	VCBackend.cpp \
 	version.cpp \
 	VSpace.cpp \
-	ParagraphMetrics.cpp \
-	LyXAction.cpp
+	WordList.cpp
 
 HEADERFILESCORE = \
 	Author.h \
@@ -270,8 +271,9 @@ HEADERFILESCORE = \
 	update_flags.h \
 	VCBackend.h \
 	version.h \
+	VSpace.h \
 	WordLangTuple.h \
-	VSpace.h
+	WordList.h
 
 STANDALONEFILES = \
 	Layout.cpp \
diff --git a/src/WordList.cpp b/src/WordList.cpp
new file mode 100644
index 0000000000..0bb06624ae
--- /dev/null
+++ b/src/WordList.cpp
@@ -0,0 +1,80 @@
+/**
+ * \file GuiCompleter.cpp
+ * This file is part of LyX, the document processor.
+ * Licence details can be found in the file COPYING.
+ *
+ * \author Stefan Schimanski
+ *
+ * Full author contact details are available in file CREDITS.
+ */
+
+#include <config.h>
+
+#include <boost/assert.hpp>
+
+#include <support/convert.h>
+#include <support/debug.h>
+#include <support/docstring.h>
+#include <support/weighted_btree.h>
+
+#include <WordList.h>
+
+#include <algorithm>
+#include <map>
+#include <iostream>
+#include <set>
+
+namespace lyx {
+
+///
+struct WordList::Impl {
+	///
+	size_t c_;
+	///
+	typedef stx::weighted_btree<docstring, size_t> Words;
+	///
+	Words words_;
+};
+
+
+WordList::WordList()
+{
+	d = new Impl;
+	d->c_ = 0;
+
+#if 0
+	for (size_t i = 1000000; i > 0; --i) {
+		d->words_.insert("a" + convert<docstring>(i), size_t(1), stx::Void());
+	}
+#endif
+}
+
+
+WordList::~WordList()
+{
+	delete d;
+}
+
+
+docstring const & WordList::word(size_t idx) const
+{
+	Impl::Words::const_iterator it
+	= d->words_.find_summed_weight(idx);
+	BOOST_ASSERT(it != d->words_.end());
+	return it->first;
+}
+
+
+size_t WordList::size() const
+{
+	return d->words_.size();
+}
+
+
+void WordList::insert(docstring const & w)
+{
+	d->words_.insert(w, size_t(1), stx::Void());
+}
+
+	
+} // namespace lyx
\ No newline at end of file
diff --git a/src/WordList.h b/src/WordList.h
new file mode 100644
index 0000000000..b802cf098f
--- /dev/null
+++ b/src/WordList.h
@@ -0,0 +1,40 @@
+// -*- C++ -*-
+/**
+ * \file WordList.h
+ * This file is part of LyX, the document processor.
+ * Licence details can be found in the file COPYING.
+ *
+ * \author Stefan Schimanski
+ *
+ * Full author contact details are available in file CREDITS.
+ */
+
+#ifndef WORDLIST_H
+#define WORDLIST_H
+
+#include "support/docstring.h"
+
+namespace lyx {
+
+class WordList {
+public:
+	///
+	WordList();
+	///
+	~WordList();
+
+	///
+	docstring const & word(size_t idx) const;
+	///
+	size_t size() const;
+	///
+	void insert(docstring const & w);
+
+private:
+	class Impl;
+	Impl * d;
+};
+
+} // namespace lyx
+
+#endif // WORDLIST_H
-- 
2.39.5