From e199707fef44317ad4beb7db81129f205465d682 Mon Sep 17 00:00:00 2001
From: hama <hama@siduction.net>
Date: Wed, 14 Jan 2015 00:18:44 +0100
Subject: [PATCH] Refactoring: ReSeqList to ReSeqArray, test of binarySearch()

---
 base/ReHashList.cpp                         |  20 ++--
 base/ReHashList.hpp                         |   8 +-
 base/{ReSeqList.cpp => ReSeqArray.cpp}      |  88 +++++++++-------
 base/{ReSeqList.hpp => ReSeqArray.hpp}      |  14 +--
 base/ReStringList.cpp                       |   8 +-
 base/ReStringList.hpp                       |   2 +-
 base/baselocations.hpp                      |   2 +-
 base/rebase.hpp                             |   2 +-
 cunit/basetest.cpp                          |   4 +-
 cunit/{cuReSeqList.cpp => cuReSeqArray.cpp} | 108 ++++++++++++++++----
 cunit/testall.cpp                           |   8 +-
 11 files changed, 171 insertions(+), 93 deletions(-)
 rename base/{ReSeqList.cpp => ReSeqArray.cpp} (87%)
 rename base/{ReSeqList.hpp => ReSeqArray.hpp} (92%)
 rename cunit/{cuReSeqList.cpp => cuReSeqArray.cpp} (65%)

diff --git a/base/ReHashList.cpp b/base/ReHashList.cpp
index abcfd02..1b32acc 100644
--- a/base/ReHashList.cpp
+++ b/base/ReHashList.cpp
@@ -25,14 +25,14 @@ ReArrayPosition::ReArrayPosition() :
  * Calling <code>ReHashList::prior() returns the last element.
  */
 void ReArrayPosition::behindLast(){
-	m_position = (ReSeqList::Index) -2;
+	m_position = (ReSeqArray::Index) -2;
 }
 /**
  * Sets the cursor behind the last position.
  * Calling <code>ReHashList::next() returns the first element.
  */
 void ReArrayPosition::priorFirst(){
-	m_position = (ReSeqList::Index) -1;
+	m_position = (ReSeqArray::Index) -1;
 }
 
 /** Constructor.
@@ -81,11 +81,11 @@ int ReHashList::find(const Byte* key, size_t length) const{
  */
 bool ReHashList::get(const Byte* key, size_t keyLength,
 		ReByteBuffer& value) const{
-	ReSeqList::Index index;
-	ReSeqList::Tag tag;
+	ReSeqArray::Index index;
+	ReSeqArray::Tag tag;
 	bool rc = m_keys.binarySearch(key, keyLength, index, &tag);
 	if (rc){
-		m_values.get(ReSeqList::Index(tag), value);
+		m_values.get(ReSeqArray::Index(tag), value);
 	}
 	return rc;
 }
@@ -117,7 +117,7 @@ bool ReHashList::next(ReArrayPosition& position, ReByteBuffer* key,
 	bool rc = position.m_position < m_keys.count();
 	if (rc){
 		ReByteBuffer dummy;
-		ReSeqList::Tag tag;
+		ReSeqArray::Tag tag;
 		if (key == NULL)
 			key = &dummy;
 		if (! m_keys.get(++position.m_position, *key, &tag)){
@@ -146,14 +146,14 @@ void ReHashList::put(const Byte* key, size_t keyLength,
 		keyLength = strlen(key);
 	if (valueLength == (size_t) -1)
 		valueLength = strlen(value);
-	ReSeqList::Index index;
-	ReSeqList::Tag tag;
+	ReSeqArray::Index index;
+	ReSeqArray::Tag tag;
 	if (m_keys.binarySearch(key, keyLength, index, &tag)){
 		// replace the value:
-		m_values.set((ReSeqList::Index) tag, value, valueLength, 0);
+		m_values.set((ReSeqArray::Index) tag, value, valueLength, 0);
 	} else {
 		// insert a new value.
-		tag = (ReSeqList::Tag) m_values.count();
+		tag = (ReSeqArray::Tag) m_values.count();
 		m_values.add(-1, value, valueLength);
 		m_keys.add(index, key, keyLength, tag);
 	}
diff --git a/base/ReHashList.hpp b/base/ReHashList.hpp
index 719f519..9eaf36c 100644
--- a/base/ReHashList.hpp
+++ b/base/ReHashList.hpp
@@ -15,7 +15,7 @@ public:
 	void behindLast();
 	void priorFirst();
 public:
-	ReSeqList::Index m_position;
+	ReSeqArray::Index m_position;
 	bool m_forward;
 };
 /** @brief A simple associative array.
@@ -27,7 +27,7 @@ public:
 class ReHashList {
 public:
 	typedef char Byte;
-	typedef ReSeqList::Sequence Sequence;
+	typedef ReSeqArray::Sequence Sequence;
 public:
 	ReHashList(bool ignoreCase = false, int keyTagSize = 1,
 			int contentLengthSize = 1, int keyLengthSize = 1);
@@ -45,10 +45,10 @@ protected:
 
 protected:
 	//@ Containing an array of keys.
-	ReSeqList m_keys;
+	ReSeqArray m_keys;
 	//@ Containing the values. The tag of <code>m_key</code> is the index
 	//@ in <code>m_values</code>.
-	ReSeqList m_values;
+	ReSeqArray m_values;
 };
 
 #endif /* REHASHLIST_H_ */
diff --git a/base/ReSeqList.cpp b/base/ReSeqArray.cpp
similarity index 87%
rename from base/ReSeqList.cpp
rename to base/ReSeqArray.cpp
index bc9457a..e266dcd 100644
--- a/base/ReSeqList.cpp
+++ b/base/ReSeqArray.cpp
@@ -1,5 +1,5 @@
 /*
- * ReSeqList.cpp
+ * ReSeqArray.cpp
  *
  *  Created on: 19.05.2010
  *      Author: wk
@@ -7,14 +7,15 @@
 
 #include "base/rebase.hpp"
 
-enum RELOC_SEQLIST {
-	LC_SET_SIZES_1 	= LC_SEQLIST + 1, // 50201
+enum RELOC_SEQARRAY {
+	LC_SET_SIZES_1 	= LC_SEQARRAY + 1, // 50201
 	LC_SET_SIZES_2,  	// 50202
 	LC_SET_SIZES_3, 	// 50203
 };
 /**
+ * @file
  * Implementation:
- * <b>ReSeqList</b> is a storage for byte sequences.
+ * <b>ReSeqArray</b> is a storage for byte sequences.
  * Each stored element is accessible by its index.
  *
  * A <b>Sequence</b> is a tuple (m_index, m_length, m_tag).
@@ -29,7 +30,7 @@ enum RELOC_SEQLIST {
  * The tag can be omitted if there is no need. This is controlled by
  * <code>m_sequSize</code>.
  *
- * ReSeqList contains a content buffer (<code>m_content</code>) and a table of
+ * ReSeqArray contains a content buffer (<code>m_content</code>) and a table of
  * content (<code>m_list</code>).
  * <ul>
  * <li>m_content stores a sequences of byte sequences. No separator is used.
@@ -49,8 +50,7 @@ enum RELOC_SEQLIST {
  * @param deltaList		If there is not enough space in the content buffer
  * 						this amount of bytes is the minimum to reserve.
  */
-ReSeqList::ReSeqList(size_t deltaList, int deltaBuffer)
-	:
+ReSeqArray::ReSeqArray(size_t deltaList, int deltaBuffer) :
 	m_content(deltaBuffer),
 	m_list(deltaList),
 	m_lost(0),
@@ -66,13 +66,13 @@ ReSeqList::ReSeqList(size_t deltaList, int deltaBuffer)
 }
 /** @brief Destructor.
  */
-ReSeqList::~ReSeqList() {
+ReSeqArray::~ReSeqArray() {
 }
 /** @brief Copy constructor.
  *
  * @param source	This instance will be copied.
  */
-ReSeqList::ReSeqList(const ReSeqList& source)
+ReSeqArray::ReSeqArray(const ReSeqArray& source)
 	:
 	m_content(source.m_content),
 	m_list(source.m_list),
@@ -93,7 +93,7 @@ ReSeqList::ReSeqList(const ReSeqList& source)
  *
  * @result	The instance itself.
  */
-ReSeqList& ReSeqList::operator = (const ReSeqList& source){
+ReSeqArray& ReSeqArray::operator = (const ReSeqArray& source){
 	m_content = source.m_content;
 	m_list = source.m_list;
 	m_lost = source.m_lost;
@@ -109,27 +109,36 @@ ReSeqList& ReSeqList::operator = (const ReSeqList& source){
 }
 /** @brief Adds an element to the list.
  *
- * @param index			The index of the new entry. If greater than the list length it will be appended.
- * @param source		The pointer of the byte sequence to insert.
- * @param sourceLength	The length of the byte sequence to insert.
- * @param tag			An item stored with the byte sequence. We know nothing about this.
+ * @param index			the index of the new entry. If greater than the list length
+ * 						it will be appended.<br>
+ *						For sorted arrays and this value is -1 the index position will
+ *						be automatically found. If sorted and not -1 the index must be
+ *						correct or the array will be unsorted
+ * @param source		the pointer of the byte sequence to insert
+ * @param sourceLength	the length of the byte sequence to insert
+ * @param tag			an item stored with the byte sequence. We know nothing about this
+ * @return 				the index of the element
  */
-void ReSeqList::add(Index index, const Byte* source, size_t sourceLength, Tag tag){
-	Sequence seq;
+ReSeqArray::Index ReSeqArray::add(Index index, const Byte* source,
+		size_t sourceLength, Tag tag){
 	if (sourceLength == (size_t) -1)
 		sourceLength = strlen(source);
+	Sequence seq;
 	setSequence(&seq, m_content.length(), sourceLength, tag);
 	m_content.append(source, sourceLength);
-	if (m_sorted){
-		//@ToDo
-		assert(false);
+	Index rc = index;
+	if (m_sorted && index == (Index) -1){
+		binarySearch(source, sourceLength, rc);
+		m_list.insert(rc * m_entrySize, (Byte*) &seq, m_entrySize);
 	} else {
 		if (index >= count()){
+			rc = m_content.length();
 			m_list.append((Byte*) &seq, m_entrySize);
 		}else{
 			m_list.insert(index * m_entrySize, (Byte*) &seq, m_entrySize);
 		}
 	}
+	return rc;
 }
 
 /**
@@ -143,16 +152,17 @@ void ReSeqList::add(Index index, const Byte* source, size_t sourceLength, Tag ta
  * 					May be NULL
  * @return			-1: the key has been found.
  */
-bool ReSeqList::binarySearch(const Byte* toFind, int length, Index& index,
+bool ReSeqArray::binarySearch(const Byte* toFind, int length, Index& index,
 			Tag* tag) const
 {
 	assert(m_sorted);
 	if (length < 0)
 		length = strlen(toFind);
-	Index rc = (Index) -1;
+	bool rc = false;
    int lbound = 0;
 	int theCount = count();
     int ubound = theCount;
+	int compareRc = 0;
     // binary search over the sorted vector:
     while(lbound <= ubound){
         int half = (ubound + lbound) / 2;
@@ -161,7 +171,7 @@ bool ReSeqList::binarySearch(const Byte* toFind, int length, Index& index,
         int currentLength = getLength(seq);
 		int minLength = currentLength < length ? currentLength : length;
 		const char* current = m_content.str() + seq->m_index;
-		int compareRc = m_ignoreCase
+		compareRc = m_ignoreCase
 			? _memicmp(toFind, current, minLength)
 			: _memcmp(toFind, current, minLength);
         if (compareRc == 0 && currentLength != length)
@@ -177,13 +187,13 @@ bool ReSeqList::binarySearch(const Byte* toFind, int length, Index& index,
         }
     }
     if (! rc)
-		index = ubound;
+		index = ubound > lbound ? ubound : lbound > theCount ? theCount : lbound;
     return rc;
 }
 
 /** @brief Deletes all entries in the list.
  */
-void ReSeqList::clear(){
+void ReSeqArray::clear(){
 	m_content.setLength(0);
 	m_list.setLength(0);
 }
@@ -197,7 +207,7 @@ void ReSeqList::clear(){
  * 					< 0: element1 < element2<br>
  * 					> 0: element1 > element2
  */
-int ReSeqList::compare(Index index1, Index index2){
+int ReSeqArray::compare(Index index1, Index index2){
 	Sequence* seq1 = getInfo(index1);
 	Sequence* seq2 = getInfo(index2);
 	size_t length1 = getLength(seq1);
@@ -217,7 +227,7 @@ int ReSeqList::compare(Index index1, Index index2){
  *
  * @param fp	target file pointer
  */
-void ReSeqList::dump(FILE* fp) const{
+void ReSeqArray::dump(FILE* fp) const{
 	ReByteBuffer buffer;
 	Tag tag;
 	for (int ix = 0; ix < (int) count(); ix++){
@@ -234,14 +244,14 @@ void ReSeqList::dump(FILE* fp) const{
  *
  * @return: -1: The key was not found. Otherwise: The index of the key in the key sequence array.
  */
-ReSeqList::Index ReSeqList::find(const Byte* toFind, size_t length,
+ReSeqArray::Index ReSeqArray::find(const Byte* toFind, size_t length,
 			Tag* tag) const{
 	if (length == (size_t) -1)
 		length = strlen(toFind);
 	int rc = -1;
 	int theCount = count();
 	for (int ix = 0; ix < theCount; ix++){
-		const ReSeqList::Sequence* seq = getInfo(ix);
+		const ReSeqArray::Sequence* seq = getInfo(ix);
 		Tag currentTag;
 		size_t currentLength = getLengthAndTag(seq, currentTag);
 		if (currentLength == length){
@@ -269,7 +279,7 @@ ReSeqList::Index ReSeqList::find(const Byte* toFind, size_t length,
  * @param 	true: The index is ok, the sequence is in the output buffer.
  * 			false: No copy has been done.
  */
-bool ReSeqList::get(Index index, ReByteBuffer& value, Tag* tag) const{
+bool ReSeqArray::get(Index index, ReByteBuffer& value, Tag* tag) const{
 	bool rc = false;
 	if (index < count()){
 		const Sequence* seq = getInfo(index);
@@ -283,7 +293,7 @@ bool ReSeqList::get(Index index, ReByteBuffer& value, Tag* tag) const{
  *
  * @return	the length of the element described in the Sequence seq
  */
-size_t ReSeqList::getLength(const Sequence* seq) const{
+size_t ReSeqArray::getLength(const Sequence* seq) const{
 	size_t rc;
 	if (m_commonSize != INDIVIDUAL_SIZE)
 		rc = m_commonSize;
@@ -319,7 +329,7 @@ size_t ReSeqList::getLength(const Sequence* seq) const{
  * @param tag	OUT: the tag of the element.
  * @return		the byte sequence length of the element
  */
-size_t ReSeqList::getLengthAndTag(const Sequence* seq, Tag& tag) const{
+size_t ReSeqArray::getLengthAndTag(const Sequence* seq, Tag& tag) const{
 	size_t rc;
 	if (m_commonSize != INDIVIDUAL_SIZE)
 		rc = m_commonSize;
@@ -386,7 +396,7 @@ size_t ReSeqList::getLengthAndTag(const Sequence* seq, Tag& tag) const{
  *
  * @param index The index of the entry to remove.
  */
-void ReSeqList::remove(Index index){
+void ReSeqArray::remove(Index index){
 	if (index <= count()){
 		Sequence* seq = getInfo(index);
 		size_t currentLength = getLength(seq);
@@ -408,7 +418,7 @@ void ReSeqList::remove(Index index){
  * @param sourceLength	The length of the new value.
  * @param tag			An additional info associated to the source.
  */
-void ReSeqList::set(Index index, const Byte* source,
+void ReSeqArray::set(Index index, const Byte* source,
 			size_t sourceLength, Tag tag){
 	if (index >= count())
 		add(index, source, sourceLength, tag);
@@ -439,7 +449,7 @@ void ReSeqList::set(Index index, const Byte* source,
  * @param length	the length of the content
  * @param tag		the tag of the element
  */
-void ReSeqList::setSequence(Sequence* seq, Index index, size_t length, Tag tag){
+void ReSeqArray::setSequence(Sequence* seq, Index index, size_t length, Tag tag){
 	seq->m_index = index;
 	if (m_commonSize == INDIVIDUAL_SIZE){
 		uint8_t* ptr = reinterpret_cast<uint8_t*>(seq) + m_offsetOfLength;
@@ -523,7 +533,7 @@ void ReSeqList::setSequence(Sequence* seq, Index index, size_t length, Tag tag){
  *
  * @param onNotOff	<code>true</code>: the comparison will be case insensitive
  */
-void ReSeqList::setIgnoreCase(bool onNotOff){
+void ReSeqArray::setIgnoreCase(bool onNotOff){
 	if (m_ignoreCase != onNotOff){
 		m_ignoreCase = onNotOff;
 		if (m_sorted)
@@ -535,7 +545,7 @@ void ReSeqList::setIgnoreCase(bool onNotOff){
  *
  * @param onNotOff	<code>true</code>: the list will be sorted
  */
-void ReSeqList::setSorted(bool onNotOff){
+void ReSeqArray::setSorted(bool onNotOff){
 	if (m_sorted != onNotOff){
 		m_sorted = onNotOff;
 		if (m_sorted)
@@ -555,7 +565,7 @@ void ReSeqList::setSorted(bool onNotOff){
  * 							indiviually stored. <br>
  * 							If > 0 <code>sizeOfLength</code>must be 0!
  */
-void ReSeqList::setSizes(int sizeOfTag, int sizeOfLength, int constantSize){
+void ReSeqArray::setSizes(int sizeOfTag, int sizeOfLength, int constantSize){
 	switch(m_sizeOfLength = sizeOfLength){
 	case 0:
 	case 1:
@@ -598,7 +608,7 @@ void ReSeqList::setSizes(int sizeOfTag, int sizeOfLength, int constantSize){
 /** @brief Sorts the list.
  * Note: the comparison is controlled by <code>m_ignoreCase</code>.
  */
-void ReSeqList::sort(){
+void ReSeqArray::sort(){
 	// Build the heap in array so that largest value is at the root:
 	int theCount = (int) count();
 	for (int start = (theCount - 2) / 2; start >= 0; start--) {
@@ -625,7 +635,7 @@ void ReSeqList::sort(){
  * @param start		the lower bound of the interval to inspect
  * @param endEnd	the upper bound of the interval to inspect
  */
-void ReSeqList::shiftDown(int start, int end){
+void ReSeqArray::shiftDown(int start, int end){
    int root = start;
 	Sequence seq;
 	// while the root has at least one child:
diff --git a/base/ReSeqList.hpp b/base/ReSeqArray.hpp
similarity index 92%
rename from base/ReSeqList.hpp
rename to base/ReSeqArray.hpp
index 3cdbd8f..92aec3b 100644
--- a/base/ReSeqList.hpp
+++ b/base/ReSeqArray.hpp
@@ -1,5 +1,5 @@
 /*
- * ReSeqList.h
+ * ReSeqArray.h
  *
  *  Created on: 19.05.2010
  *      Author: wk
@@ -19,7 +19,7 @@
  * The byte sequences may have different lengths.
  * This implies the handling of C string arrays too.
  */
-class ReSeqList {
+class ReSeqArray {
 public:
 	typedef char Byte;
 	typedef unsigned int Index;
@@ -30,12 +30,12 @@ public:
 		Tag		m_tag;
 	} Sequence;
 public:
-	ReSeqList(size_t deltaList = 128, int deltaBuffer = 1024);
-	virtual ~ReSeqList();
-	ReSeqList(const ReSeqList& source);
-	ReSeqList& operator = (const ReSeqList& source);
+	ReSeqArray(size_t deltaList = 128, int deltaBuffer = 1024);
+	virtual ~ReSeqArray();
+	ReSeqArray(const ReSeqArray& source);
+	ReSeqArray& operator = (const ReSeqArray& source);
 public:
-	void add(Index index, const Byte* source, size_t sourceLength, Tag tag = 0);
+	Index add(Index index, const Byte* source, size_t sourceLength, Tag tag = 0);
 	bool binarySearch(const Byte* toFind, int length, Index& index,
 				Tag* tag = NULL) const;
 	void clear();
diff --git a/base/ReStringList.cpp b/base/ReStringList.cpp
index 71fb641..08e0caf 100644
--- a/base/ReStringList.cpp
+++ b/base/ReStringList.cpp
@@ -13,7 +13,7 @@
  * @param deltaBuffer	buffer reservation will be incremented by this amount
  */
 ReStringList::ReStringList(int deltaList, int deltaBuffer)	:
-	ReSeqList(deltaList, deltaBuffer)
+	ReSeqArray(deltaList, deltaBuffer)
 {
 }
 
@@ -125,7 +125,7 @@ const char* ReStringList::strOf(Index index) const{
  * @return 	-1: The index is too large.
  * 			Otherwise: The wanted tagOf.
  */
-ReSeqList::Tag ReStringList::tagOf(Index index) const{
+ReSeqArray::Tag ReStringList::tagOf(Index index) const{
 	Tag rc = -1;
 	if (index < count()){
 		Sequence* seq = getInfo(index);
@@ -200,7 +200,7 @@ size_t ReStringList::sumOfStrLengths() const{
  *
  * @return -1: The string was not found. Otherwise: The index of the string.
  */
-ReSeqList::Index ReStringList::indexOf(const char* toFind,
+ReSeqArray::Index ReStringList::indexOf(const char* toFind,
 		bool ignoreCase, Index start) const{
 	Index rc = (Index) -1;
 	Index theCount = count();
@@ -226,7 +226,7 @@ ReSeqList::Index ReStringList::indexOf(const char* toFind,
  *
  * @return -1: The string was not found. Otherwise: The index of the string.
  */
-ReSeqList::Index ReStringList::nextStartingWith(Index start,
+ReSeqArray::Index ReStringList::nextStartingWith(Index start,
 		const char* prefix, bool ignoreCase){
 	Index rc = (Index) -1;
 	Index theCount = count();
diff --git a/base/ReStringList.hpp b/base/ReStringList.hpp
index a12b2db..2807d4c 100644
--- a/base/ReStringList.hpp
+++ b/base/ReStringList.hpp
@@ -28,7 +28,7 @@
  * listOut.writeToFile("abc.csv");
  * </code></pre>
  */
-class ReStringList : public ReSeqList {
+class ReStringList : public ReSeqArray {
 public:
 	ReStringList(int deltaList = 1024, int deltaBuffer = 1024);
 	virtual ~ReStringList();
diff --git a/base/baselocations.hpp b/base/baselocations.hpp
index e132b1a..86a839a 100644
--- a/base/baselocations.hpp
+++ b/base/baselocations.hpp
@@ -13,7 +13,7 @@
 enum RELOC_LIB {
 	LC_CONFIGFILE	= 50000,
 	LC_DIRTOOLS		= 50100,
-	LC_SEQLIST		= 50200,
+	LC_SEQARRAY		= 50200,
 	LC_HASHLIST		= 50300,
 };
 enum RELOC_UDPCONNECTION {
diff --git a/base/rebase.hpp b/base/rebase.hpp
index 0ac19fc..19251d2 100644
--- a/base/rebase.hpp
+++ b/base/rebase.hpp
@@ -53,7 +53,7 @@
 #include "base/ReException.hpp"
 #include "base/ReStringUtils.hpp"
 #include "base/ReDirectory.hpp"
-#include "base/ReSeqList.hpp"
+#include "base/ReSeqArray.hpp"
 #include "base/ReStringList.hpp"
 #include "base/ReHashList.hpp"
 #include "base/ReConfigFile.hpp"
diff --git a/cunit/basetest.cpp b/cunit/basetest.cpp
index a04a4f0..2a7d7ed 100644
--- a/cunit/basetest.cpp
+++ b/cunit/basetest.cpp
@@ -15,8 +15,8 @@ void testReBase(void){
 		testReI18N();
 		extern void testReStringList(void);
 		testReStringList();
-		extern void testReSeqList(void);
-		testReSeqList();
+		extern void testReSeqArray(void);
+		testReSeqArray();
 		extern void testReHashList(void);
 		testReHashList();
 		void testReException(void);
diff --git a/cunit/cuReSeqList.cpp b/cunit/cuReSeqArray.cpp
similarity index 65%
rename from cunit/cuReSeqList.cpp
rename to cunit/cuReSeqArray.cpp
index 8217068..16a08e8 100644
--- a/cunit/cuReSeqList.cpp
+++ b/cunit/cuReSeqArray.cpp
@@ -2,11 +2,13 @@
 
 class TestReSeqList : public ReTestUnit {
 public:
-	TestReSeqList() : ReTestUnit("ReSeqList", __FILE__){
+	TestReSeqList() : ReTestUnit("ReSeqArray", __FILE__){
 		run();
 	}
 private:
 	void run(){
+		testBinSearch2();
+		testBinSearch();
 		testSorted();
 		testIgnoreCase();
 		testFind();
@@ -14,15 +16,81 @@ private:
 		testBase();
 		testRemove();
 	}
-	void checkElement(ReSeqList& list, ReSeqList::Index index, const char* value, ReSeqList::Tag expectedTag){
+	void checkElement(ReSeqArray& list, ReSeqArray::Index index, const char* value, ReSeqArray::Tag expectedTag){
 		ReByteBuffer buffer;
-		ReSeqList::Tag tag;
+		ReSeqArray::Tag tag;
 		checkT(list.get(index, buffer, &tag));
 		checkIEqu(value, buffer.str());
 		checkEqu(expectedTag, tag);
 	}
+	void testBinSearch(){
+		ReSeqArray list;
+		list.setIgnoreCase(true);
+		ReByteBuffer value, expectedValue;
+		list.add(-1, "abc", -1, 300);
+		list.add(-1, "abc", -1, 350);
+		list.add(-1, "abce", -1, 100);
+		list.add(-1, "bcd", -1, 200);
+		list.add(-1, "cde", -1, 400);
+		list.setSorted(true);
+		ReSeqArray::Index index;
+
+		checkF(list.binarySearch("cee", -1, index, NULL));
+		checkEqu(5ll, index);
+
+		checkF(list.binarySearch("ab", 2, index, NULL));
+		checkEqu(0ll, index);
+		checkF(list.binarySearch("ab", -1, index, NULL));
+		checkEqu(0ll, index);
+		checkF(list.binarySearch("abcd", -1, index, NULL));
+		checkEqu(2ll, index);
+		checkF(list.binarySearch("bbd", -1, index, NULL));
+		checkEqu(3ll, index);
+		checkF(list.binarySearch("bbd", -1, index, NULL));
+		checkEqu(3ll, index);
+		checkF(list.binarySearch("bc", -1, index, NULL));
+		checkEqu(3ll, index);
+		checkF(list.binarySearch("bcd0", -1, index, NULL));
+		checkEqu(4ll, index);
+		checkF(list.binarySearch("cdex", -1, index, NULL));
+		checkEqu(5ll, index);
+		checkF(list.binarySearch("cee", -1, index, NULL));
+		checkEqu(5ll, index);
+	}
+	void testBinSearch2(){
+		ReSeqArray list;
+		ReSeqArray::Tag tag;
+		ReSeqArray::Index index;
+		ReByteBuffer value;
+		list.setSorted(true);
+		value = "ab";
+		for (int count = 2; count < 16; count++){
+			list.clear();
+			for (int ix = 0; ix < count; ix++){
+				value.setLength(2);
+				value.buffer()[0] = 'a' + ix;
+				list.add(ix, value.str(), -1, (ReSeqArray::Tag) ix*10);
+			}
+			for (int ix = 0; ix <= count; ix++){
+				value.setLength(2);
+				value.buffer()[0] = 'a' + ix;
+				value.buffer()[1] = 'a';
+				checkF(list.binarySearch(value.str(), -1, index));
+				checkEqu(ReSeqArray::Index(ix), index);
+				if (ix > 0){
+					value.setLength(3);
+					value.buffer()[0] = 'a' + ix - 1;
+					value.buffer()[1] = 'b';
+					value.buffer()[2] = '0';
+					bool rc = list.binarySearch(value.str(), -1, index);
+					checkF(rc);
+					checkEqu(ReSeqArray::Index(ix), index);
+				}
+			}
+		}
+	}
 	void testSorted(){
-		ReSeqList list;
+		ReSeqArray list;
 		list.setIgnoreCase(true);
 		ReByteBuffer value, expectedValue;
 		list.add(-1, "bcd", -1, 200);
@@ -40,8 +108,8 @@ private:
 		checkElement(list, 2U, "AbCd", 100);
 		checkElement(list, 3U, "bCd", 200);
 		checkElement(list, 4U, "cde", 400);
-		ReSeqList::Index index;
-		ReSeqList::Tag tag;
+		ReSeqArray::Index index;
+		ReSeqArray::Tag tag;
 		checkT(list.binarySearch("Abc", -1, index, &tag));
 		checkEqu(0u, index);
 		checkT(list.binarySearch("AbcD", -1, index, &tag));
@@ -52,7 +120,7 @@ private:
 		checkEqu(4u, index);
 	}
 	void testIgnoreCase(){
-		ReSeqList list;
+		ReSeqArray list;
 		list.setIgnoreCase(true);
 		ReByteBuffer value, expectedValue;
 		list.add(-1, "bcd", -1, 200);
@@ -62,10 +130,10 @@ private:
 		checkEqu(1U, list.find("BCD", -1));
 	}
 	void testAdd(){
-		ReSeqList list;
+		ReSeqArray list;
 		ReByteBuffer value, expectedValue;
-		ReSeqList::Tag tag = 0;
-		ReSeqList::Tag expectedTag = 0;
+		ReSeqArray::Tag tag = 0;
+		ReSeqArray::Tag expectedTag = 0;
 		size_t maxIx = 64;
 		for (size_t ix = 0; ix < maxIx; ix++){
 			expectedTag = (1ll << ix);
@@ -88,10 +156,10 @@ private:
 
 	}
 	void testFind(){
-		ReSeqList list;
+		ReSeqArray list;
 		ReByteBuffer value, expectedValue;
-		ReSeqList::Tag tag = 0;
-		ReSeqList::Tag expectedTag = 0;
+		ReSeqArray::Tag tag = 0;
+		ReSeqArray::Tag expectedTag = 0;
 		size_t maxIx = 13;
 		for (size_t ix = 0; ix < maxIx; ix++){
 			expectedTag = 10*ix;
@@ -115,11 +183,11 @@ private:
 		}
 	}
 	void testBase(){
-		ReSeqList list;
+		ReSeqArray list;
 		ReByteBuffer value;
-		ReSeqList::Tag tag = 0;
+		ReSeqArray::Tag tag = 0;
 
-		list.add(-1, "xxx", -1, ReSeqList::Tag(1l) << 31);
+		list.add(-1, "xxx", -1, ReSeqArray::Tag(1l) << 31);
 		checkT(list.get(0, value, &tag));
 		checkEqu(1ll << 31, tag);
 		checkEqu("xxx", value.str());
@@ -166,9 +234,9 @@ private:
 		checkF(list.get(0, value));
 	}
 	void testRemove(){
-		ReSeqList list;
+		ReSeqArray list;
 		ReByteBuffer value;
-		ReSeqList::Tag tag = 0;
+		ReSeqArray::Tag tag = 0;
 
 		list.add(-1, "abc", -1, 100);
 		list.add(-1, "def12", -1, 200);
@@ -205,8 +273,8 @@ private:
 
 	}
 };
-extern void testReSeqList(void);
+extern void testReSeqArray(void);
 
-void testReSeqList(void){
+void testReSeqArray(void){
 	TestReSeqList unit;
 }
diff --git a/cunit/testall.cpp b/cunit/testall.cpp
index 18ac15a..d181b88 100644
--- a/cunit/testall.cpp
+++ b/cunit/testall.cpp
@@ -13,14 +13,14 @@
 void testBase(){
 	extern void testReHashList(void);
 	//testReHashList();
-	extern void testReSeqList();
-	testReSeqList();
+	extern void testReSeqArray();
+	testReSeqArray();
 	extern void testReTestUnit();
 	// testReTestUnit();
 	extern void testReByteBuffer();
 	testReByteBuffer();
-	extern void testReSeqList(void);
-	testReSeqList();
+	extern void testReSeqArray(void);
+	testReSeqArray();
 	extern void testReHashList(void);
 	testReHashList();
 	void testReException(void);
-- 
2.39.5