///****************************************************************************
// * KONOHA COPYRIGHT, LICENSE NOTICE, AND DISCRIMER  
// * 
// * Copyright (c) 2005-2008, Kimio Kuramitsu <kimio at ynu.ac.jp>
// *           (c) 2008-      Konoha Software Foundation  
// * All rights reserved.
// * 
// * You may choose one of the following two licenses when you use konoha. 
// * See www.konohaware.org/license.html for further information.
// * 
// * (1) GNU General Public License 2.0      (with    KONOHA_UNDER_GPL2)
// * (2) Konoha Software Foundation License 1.0
// * 
// * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// * "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 COPYRIGHT OWNER 
// * 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.
// *  
// ****************************************************************************/
//
///* ************************************************************************ */
//
//#include"commons.h"
//
///* ************************************************************************ */
//
//#ifdef __cplusplus 
//extern "C" {
//#endif
//
///* ======================================================================== */
///* [config] */
//
//static
//void knh_dictmap_finit(const knh_dictentry_t *e)
//{
//	KNH_INITv(e->key, KNH_NULL);
//	KNH_INITv(e->value, KNH_NULL);
//}
//
///* ------------------------------------------------------------------------ */
//
//static
//void knh_dictmap_ftraverse(Ctx *ctx, const knh_dictentry_t *e, f_traverse ftr)
//{
//	ftr(ctx, e->key);
//	ftr(ctx, e->value);
//}
//
///* ------------------------------------------------------------------------ */
//
//static
//void knh_dictset_finit(const knh_dictentry_t *e)
//{
//	KNH_INITv(e->key, KNH_NULL);
//	e->uvalue = 0;
//}
//
///* ------------------------------------------------------------------------ */
//
//static
//void knh_dictset_ftraverse(Ctx *ctx, const knh_dictentry_t *e, f_traverse ftr)
//{
//	ftr(ctx, e->key);
//}
//
///* ------------------------------------------------------------------------ */
//
//static
//int knh_dictentry_fcompareString(const knh_dictentry_t *e1, const knh_dictentry_t *e2)
//{
//	return knh_bytes_strcmp(knh_String_tobytes(e1->name), knh_String_tobytes(e2->name));
//}
//
///* ------------------------------------------------------------------------ */
//
//static
//int knh_dictentry_fcompareObject(const knh_dictentry_t *e1, const knh_dictentry_t *e2)
//{
//	return knh_Object_compareTo(e1->key, e2->key);
//}
//
///* ======================================================================== */
///* [constructors] */
//
//DictMap2* new_DictMap2(Ctx *ctx, knh_int_t capacity)
//{
//	//knh_class_t cid = knh_pmzclass(ctx, CLASS_DictMap2, p1, p2);
//	knh_DictMap2_t *o = (knh_DictMap2_t*)new_PObject(ctx, FLAG_DictMap2, CLASS_DictMap2, CLASS_DictMap2);
//	o->list = knh_array_malloc(ctx, capacity, sizeof(knh_dictentry_t), knh_dictmap_finit, knh_dictmap_ftraverse);
//	o->size = 0;
//	knh_array_set_opsize(o->list, 0);
//	knh_array_set_fcompare(o->list, knh_dictentry_fcompareString);
//	return o;
//}
//
///* ======================================================================== */
///* [dictentry] */
//
//#define LINER_SEARCH_LEN 8
//
//static 
//knh_index_t knh_dictentry_findb_between(knh_dictentry_t *a, knh_bytes_t kv, size_t sp, size_t ep)
//{
//	L_TAIL:;
//	if(ep - sp < LINER_SEARCH_LEN) {
//		knh_index_t i;
//		for(i = sp; i < ep; i++) {
//			if(knh_String_equals(a[i].name, kv)) return i;
//		}
//		return -1;
//	}
//	else {
//		size_t cp = KNH_MID(sp, ep);
//		knh_index_t i = knh_bytes_strcmp(kv, knh_String_tobytes(a[cp].name));
//		if(i == 0) {
//			return cp;
//		}
//		else if(i < 0) {
//			ep = cp;
//		}else {
//			sp = cp + 1;
//		}
//		goto L_TAIL;
//	}
//}
//
///* ------------------------------------------------------------------------ */
//
//static
//knh_index_t knh_dictentry_index_b(knh_dictentry_t *a, size_t size, knh_bytes_t kv)
//{
//	if(a == NULL) {
//		return -1;
//	}
//	else {
//		size_t sorted_size = knh_array_opsize(a);
//		if(size - sorted_size >= LINER_SEARCH_LEN) {
//			knh_array_sort(a);
//			knh_array_set_opsize(a, size);
//			return knh_dictentry_findb_between(a, kv, 0, size);
//		}
//		else {
//			knh_index_t loc = knh_dictentry_findb_between(a, kv, 0, sorted_size);
//			return (loc == -1) ? knh_dictentry_findb_between(a, kv, sorted_size, size) : loc;
//		}
//	}
//}
//
///* ======================================================================== */
///* [methods] */
//
//String* knh_DictMap2_nameAt(DictMap2 *o, size_t n)
//{
//	KNH_ASSERT(n < o->size);
//	return o->list[n].name;
////}
//
///* ------------------------------------------------------------------------ */
//
//Object* knh_DictMap2_valueAt(DictMap2 *o, size_t n)
//{
//	KNH_ASSERT(n < o->size);
//	return o->list[n].value;
//}
//
///* ------------------------------------------------------------------------ */
//
//String *new_String__DictMap2(Ctx *ctx, DictMap2 *o, knh_bytes_t key)
//{
//	knh_index_t loc = knh_dictentry_index_b(o->list, o->size, key);
//	if(loc == -1) {
//		return new_String(ctx, key, NULL);
//	}
//	else {
//		return o->list[loc].key;
//	}
//}
//
///* ------------------------------------------------------------------------ */
//
//Object *knh_DictMap2_get__b(Ctx *ctx, DictMap2 *o, knh_bytes_t key)
//{
//	knh_int_t loc = knh_dictentry_index_b(o->list, o->size, key);
//	return (loc == -1) ? KNH_NULL : o->list[loc].value;
//}
//
///* ------------------------------------------------------------------------ */
///* @method Any DictMap2.get(String! key) */
//
//Object *knh_DictMap2_get(Ctx *ctx, DictMap2 *o, String *key)
//{
//	knh_int_t loc = knh_dictentry_index_b(o->list, o->size, knh_String_tobytes(key));
//	return (loc == -1) ? KNH_NULL : o->list[loc].value;
//}
//
///* ------------------------------------------------------------------------ */
///* @method void DictMap2.append(String! key, Any! value) */
//
//void knh_DictMap2_append(Ctx *ctx, DictMap2 *o, String *key, Any *value)
//{
//	if(o->list == NULL) {
//		o->list = knh_array_malloc(ctx, 8, sizeof(knh_dictentry_t), knh_dictmap_finit, knh_dictmap_ftraverse);
//		o->size = 0;
//	}
//	else {
//		size_t capacity = knh_array_capacity(o->list);
//		o->list = knh_array_resize(ctx, o->list, capacity, knh_array_growsize(capacity));
//	}
//	KNH_SETv(ctx, o->list[o->size].key, key);
//	KNH_SETv(ctx, o->list[o->size].value, value);
//	o->size++;
//}
//
///* ------------------------------------------------------------------------ */
///* @method void DictMap2.set(String! key, Any value) */
//
//void knh_DictMap2_set(Ctx *ctx, DictMap2 *o, String *key, Any *v)
//{
//	knh_Object_t *value = v;
//	int loc = knh_dictentry_index_b(o->list, o->size, knh_String_tobytes(key));
//	if(loc != -1) {
//		KNH_SETv(ctx, o->list[loc].key, key);  /* To avoid losing key */
//		KNH_SETv(ctx, o->list[loc].value, value);
//	}
//	else {
//		knh_DictMap2_append(ctx, o, key, value);
//	}
//}
//
///* ------------------------------------------------------------------------ */
///* @method void DictMap2.remove(String! key) */
//
//void knh_DictMap2_remove(Ctx *ctx, DictMap2 *o, String *key)
//{
//	int loc = knh_dictentry_index_b(o->list, o->size, knh_String_tobytes(key));
//	if(loc != 1) {
//		KNH_SETv(ctx, o->list[loc].key, key);  /* To avoid losing key */
//		KNH_SETv(ctx, o->list[loc].value, KNH_NULL);
//	}
//}
//
///* ------------------------------------------------------------------------ */
///* @method void DictMap2.clear() */
//
//void knh_DictMap2_clear(Ctx *ctx, DictMap2 *o) 
//{
//	size_t i, capacity = knh_array_capacity(o->list);
//	for(i = 0; i < capacity; i++) {
//		KNH_SETv(ctx, o->list[i].key, KNH_NULL);
//		KNH_SETv(ctx, o->list[i].value, KNH_NULL);
//	}
//	o->size = 0;
//	knh_array_set_opsize(0);
//}
//
///* ======================================================================== */
///* [iterators] */
//
//Object *knh_DictMap2_key_next(Ctx *ctx, Iterator *it)
//{
//	DictMap2 *o = (DictMap2*)knh_Iterator_source(it);
//	size_t pos;  
//	for(pos = knh_Iterator_pos(it); pos < o->size; pos++) {
//		if(IS_NOTNULL(o->list[pos].value)) {
//			knh_Iterator_setpos(it,pos+1);
//			return (Object*)o->list[pos].key;
//		}
//	}
//	knh_Iterator_setpos(it,pos);
//	return (Object*)KNH_NULL;
//}
//
///* ------------------------------------------------------------------------ */
///* @map DictMap2 Iterator! */
///* @map DictMap2 String.. */
//
//Iterator* knh_DictMap2_Iterator(Ctx *ctx, DictMap2 *o, Mapper *map)
//{
//	knh_DictMap2_sort(o);
//	return new_Iterator(ctx, CLASS_String, o, knh_DictMap2_key_next);	
//}
//
//#define _knh_DictMap2_String__   knh_DictMap2_Iterator
//
//
///* ======================================================================== */
///* [movabletext] */
//
///* ------------------------------------------------------------------------ */
///* @method void DictMap2.%dump(OutputStream w, Any m) */
//
//void knh_DictMap2__dump(Ctx *ctx, DictMap2 *o, OutputStream *w, Any *m)
//{
//	knh_DictMap2_sort(o);
//	knh_putc(ctx, w, '{');
//	size_t c;
//	for(c = 0; c < o->size; c++) {
//		if(c > 0) {
//			knh_write_delim(ctx,w);
//		}
//		if(!knh_array_isdump(c)) {
//			knh_write_dots(ctx, w);
//			break;
//		}
//		knh_format(ctx, w, METHODN__s, (Object*)o->list[c].key, KNH_NULL);
//		knh_putc(ctx, w, ':');	knh_putc(ctx, w, ' ');
//		knh_format(ctx, w, METHODN__dump, o->list[c].value, KNH_NULL);
//	}
//	knh_putc(ctx, w, '}');
//}
//
///* ------------------------------------------------------------------------ */
//
//#ifdef __cplusplus
//}
//#endif
