int
check_tree(rb_tree *tree, rb_node *node) {
    rb_node *nil = tree->nil;
    if (node == nil) {
        assert(!node->red);
        return 1;
    }
    if (node->left != nil) {
        assert(COMPARE(tree, node, node->left) >= 0);
        assert(node->left->parent == node);
    }
    if (node->right != nil) {
        assert(COMPARE(tree, node, node->right) <= 0);
        assert(node->right->parent == node);
    }
    if (node->red) {
        assert(!node->left->red && !node->right->red);
    }
    int hb_left = check_tree(tree, node->left);
    int hb_right = check_tree(tree, node->right);
    assert(hb_left == hb_right);
    int hb = hb_left;
    if (!node->red) {
        hb ++;
    }
    return hb;
}

static int
compare_IDEs(const void *ap, const void *bp)
{
    const XPTInterfaceDirectoryEntry *a = ap, *b = bp;
    const nsID *aid = &a->iid, *bid = &b->iid;
    const char *ans, *bns;

    int i;
#define COMPARE(field) if (aid->field > bid->field) return 1; \
                       if (bid->field > aid->field) return -1;
    COMPARE(m0);
    COMPARE(m1);
    COMPARE(m2);
    for (i = 0; i < 8; i++) {
        COMPARE(m3[i]);
    }

    /* defend against NULL name_space by using empty string. */
    ans = a->name_space ? a->name_space : "";
    bns = b->name_space ? b->name_space : "";

    if (a->name_space && b->name_space) {
        if ((i = strcmp(a->name_space, b->name_space)))
            return i;
    } else {
        if (a->name_space || b->name_space) {
            if (a->name_space)
                return -1;
            return 1;
        }
    }
    /* these had better not be NULL... */
    return strcmp(a->name, b->name);
#undef COMPARE
}

LEAFTYPE
radix_get(struct ROOTSTRUCT * tree, LEAFTYPE leaf, EXTRA_ARG aux) {
    LEAFTYPE result;
    struct _internal_node * node;
    uint32_t dir;

    if (tree->leafcount == 0) return NO_LEAF;
    if (tree->leafcount == 1) {
        result = tree->root.leaf;
        if (COMPARE(result, leaf) == -1) return result;
        else return NO_LEAF;
    } /* root points to a node */

    node = tree->root.node;
    while (1) {
        dir = DECIDE(leaf, node->critbit, aux);
        if (IS_LEAF(node, dir)) {
            result = node->child[dir].leaf;
            break;
        } else {
            node = node->child[dir].node;
        }
    }

    if (COMPARE(result, leaf) == -1) return result;
    else return NO_LEAF;
}

static PyObject *
html_Tag_compare(html_Tag *a, html_Tag *b, int op) {
    if (!PyObject_TypeCheck(a, &html_TagType) || !PyObject_TypeCheck(b, &html_TagType)) {
        switch (op) {
            case Py_EQ:
                Py_RETURN_FALSE;
            case Py_NE:
                Py_RETURN_TRUE;
            default:
                break;
        }
    } else {
        switch (op) {
            case Py_EQ:
                if (COMPARE(name, Py_EQ) && COMPARE(lang, Py_EQ)) Py_RETURN_TRUE;
                Py_RETURN_FALSE;
            case Py_NE:
                if (COMPARE(name, Py_NE) || COMPARE(lang, Py_NE)) Py_RETURN_TRUE;
                Py_RETURN_FALSE;
            default:
                break;
        }
    }
    PyErr_SetString(PyExc_TypeError, "Only equals comparison is supported for Tag objects");
    return NULL;
}

static int
testprim1_compare(PrimRequired* input, PrimRequired* output)
{
    COMPARE(input,output,int32);
    COMPARE(input,output,int64);
    COMPARE(input,output,uint32);
    COMPARE(input,output,uint64);
    COMPARE(input,output,sint32);
    COMPARE(input,output,sint64);
    COMPARE(input,output,fixed32);
    COMPARE(input,output,fixed64);
    COMPARE(input,output,sfixed32);
    COMPARE(input,output,sfixed64);
    COMPARE(input,output,double);
    COMPARE(input,output,float);
    if(input->f_int64 != output->f_int64) return 0;
    if(input->f_uint32 != output->f_uint32) return 0;
    if(input->f_uint64 != output->f_uint64) return 0;
    if(input->f_sint32 != output->f_sint32) return 0;
    if(input->f_sint64 != output->f_sint64) return 0;
    if(input->f_fixed32 != output->f_fixed32) return 0;
    if(input->f_fixed64 != output->f_fixed64) return 0;
    if(input->f_sfixed32 != output->f_sfixed32) return 0;
    if(input->f_sfixed64 != output->f_sfixed64) return 0;
    if(input->f_double != output->f_double) return 0;
    if(input->f_float != output->f_float) return 0;
    return 1;
}

	void readData()
	{
		scanf("%d%d", &toyNum, &compareTimes);
		vtxNum = toyNum + compareTimes + 2;
		source = vtxNum - 2, sink = vtxNum - 1;

		for(int i = 0; i < toyNum; i ++)
		{
			scanf("%d%d", &initLowerBound[i], &initUpperBound[i]);
			initLowerBound[i] = max(initLowerBound[i], 0);
			initUpperBound[i] = min(initUpperBound[i], 20000);
		}
		for(int i = 0, l, r, d; i < compareTimes; i ++)
		{
			scanf("%d%d%d", &l, &r, &d);
			if(d > 0)
				addEdge(COMPARE(i), sink, d, d);
			else if(d < 0)
				addEdge(source, COMPARE(i), -d, -d);
			int toyIdx;
			while(l --)
			{
				scanf("%d", &toyIdx);
				toyIdx --;
				addEdge(TOY(toyIdx), COMPARE(i), 0, INFINITY);
			}
			while(r --)
			{
				scanf("%d", &toyIdx);
				toyIdx --;
				addEdge(COMPARE(i), TOY(toyIdx), 0, INFINITY);
			}
		}
	}

/* Returns +ve number if ts1 > ts2, -ve if ts1 < ts2, 0 if ts1 == ts2. */
static int compare_ts(struct timespec *ts1, struct timespec *ts2)
{
    if (ts1->tv_sec == ts2->tv_sec)
        return COMPARE(ts1->tv_nsec, ts2->tv_nsec);
    else
        return COMPARE(ts1->tv_sec, ts2->tv_sec);
}

void minHeapify(int* A, int i){
    /*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  */
    /*  Inputs:                                                     */
    /*          A   :   int array    array of indices               */
    /*          i   :   int          index or current vertex        */
    /*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  */
    
    int leftChild = left(i);
    int rightChild = right(i);
    int smallest;
    
    if(leftChild <= heapSize && COMPARE(A[leftChild],A[i]) == 2){
        smallest = leftChild;
    }
    else{
        smallest = i;
    }
    
    if(rightChild <= heapSize && COMPARE(A[rightChild], A[smallest]) == 2 ){
        smallest = rightChild;
    }
    
    if(smallest != i){
        // we are not switching hidden, we are switching indices associated with it
        int temp = A[i];
        A[i] = A[smallest];
        A[smallest] = temp;
        
        minHeapify(A, smallest);
    }
}

void LoadScene(TiXmlElement *element)
{
    for ( TiXmlElement *child = element->FirstChildElement(); child!=NULL; child = child->NextSiblingElement() ) {
        
        if ( COMPARE( child->Value(), "background" ) ) {
            Color c(1,1,1);
            ReadColor( child, c );
            background.SetColor(c);
            printf("Background %f %f %f\n",c.r,c.g,c.b);
            background.SetTexture( ReadTexture(child) );
        } else if ( COMPARE( child->Value(), "environment" ) ) {
            Color c(1,1,1);
            ReadColor( child, c );
            environment.SetColor(c);
            printf("Environment %f %f %f\n",c.r,c.g,c.b);
            environment.SetTexture( ReadTexture(child) );
        } else if ( COMPARE( child->Value(), "object" ) ) {
            LoadNode( &rootNode, child );
        } else if ( COMPARE( child->Value(), "material" ) ) {
            LoadMaterial( child );
        } else if ( COMPARE( child->Value(), "light" ) ) {
            LoadLight( child );
        }
    }
}

void LoadTransform( Transformation *trans, TiXmlElement *element, int level )
{
    for ( TiXmlElement *child = element->FirstChildElement(); child!=NULL; child = child->NextSiblingElement() ) {
        if ( COMPARE( child->Value(), "scale" ) ) {
            Point3 s(1,1,1);
            ReadVector( child, s );
            trans->Scale(s.x,s.y,s.z);
            PrintIndent(level);
            printf("   scale %f %f %f\n",s.x,s.y,s.z);
        } else if ( COMPARE( child->Value(), "rotate" ) ) {
            Point3 s(0,0,0);
            ReadVector( child, s );
            s.Normalize();
            float a;
            ReadFloat(child,a,"angle");
            trans->Rotate(s,a);
            PrintIndent(level);
            printf("   rotate %f degrees around %f %f %f\n", a, s.x, s.y, s.z);
        } else if ( COMPARE( child->Value(), "translate" ) ) {
            Point3 t(0,0,0);
            ReadVector(child,t);
            trans->Translate(t);
            PrintIndent(level);
            printf("   translate %f %f %f\n",t.x,t.y,t.z);
        }
    }
}

QString MultiModelPrinter::printMixers()
{
  QString str = printTitle(tr("Mixers"));
  MultiColumns columns(models.size());
  columns.append("<table cellspacing='0' cellpadding='1' width='100%' border='0' style='border-collapse:collapse'>");
  for (int i=0; i<firmware->getCapability(Outputs); i++) {
    int count = 0;
    for (int k=0; k<models.size(); k++) {
      count = std::max(count, models[k]->mixes(i).size());
    }
    if (count > 0) {
      columns.append("<tr><td width='20%'><b>");
      COMPARE(modelPrinter->printMixerName(i+1));
      columns.append("</b></td><td>");
      for (int j=0; j<count; j++) {
        if (j > 0)
          columns.append("<br/>");
        COMPARE((j < model->mixes(i).size()) ? modelPrinter->printMixerLine(*model->mixes(i)[j], (j>0)) : "&nbsp;");
      }
      columns.append("</td></tr>");
    }
  }
  str.append(columns.print());
  return str;
}

void simple_test()
{
    std::string expression = "4+3*(5-1)-8/2";
    COMPARE(evaluate(std::begin(expression), std::end(expression)), 12);

    expression = "((2-3)*3/3+5)/4";
    COMPARE(evaluate(std::begin(expression), std::end(expression)), 1);
}

static int sort_by_score_desc(const void *v1, const void *v2)
{
	const struct pair *p1 = v1;
	const struct pair *p2 = v2;
	if (p2->score == p1->score) {
		return COMPARE(p1->index, p2->index);
	}
	return COMPARE(p2->score, p1->score);
}

int main()
{
	printf("Testing subscriber database code.\n");
	osmo_init_logging(&log_info);

	if (db_init("hlr.sqlite3")) {
		printf("DB: Failed to init database. Please check the option settings.\n");
		return 1;
	}	 
	printf("DB: Database initialized.\n");

	if (db_prepare()) {
		printf("DB: Failed to prepare database.\n");
		return 1;
	}
	printf("DB: Database prepared.\n");

	struct gsm_subscriber *alice = NULL;
	struct gsm_subscriber *alice_db;

	char *alice_imsi = "3243245432345";
	alice = db_create_subscriber(NULL, alice_imsi);
	db_sync_subscriber(alice);
	alice_db = db_get_subscriber(NULL, GSM_SUBSCRIBER_IMSI, alice->imsi);
	COMPARE(alice, alice_db);
	SUBSCR_PUT(alice_db);
	SUBSCR_PUT(alice);

	alice_imsi = "3693245423445";
	alice = db_create_subscriber(NULL, alice_imsi);
	db_subscriber_assoc_imei(alice, "1234567890");
	db_subscriber_alloc_tmsi(alice);
	alice->lac=42;
	db_sync_subscriber(alice);
	alice_db = db_get_subscriber(NULL, GSM_SUBSCRIBER_IMSI, alice_imsi);
	COMPARE(alice, alice_db);
	SUBSCR_PUT(alice);
	SUBSCR_PUT(alice_db);

	alice_imsi = "9993245423445";
	alice = db_create_subscriber(NULL, alice_imsi);
	db_subscriber_alloc_tmsi(alice);
	alice->lac=42;
	db_sync_subscriber(alice);
	db_subscriber_assoc_imei(alice, "1234567890");
	db_subscriber_assoc_imei(alice, "6543560920");
	alice_db = db_get_subscriber(NULL, GSM_SUBSCRIBER_IMSI, alice_imsi);
	COMPARE(alice, alice_db);
	SUBSCR_PUT(alice);
	SUBSCR_PUT(alice_db);

	db_fini();

	printf("Done\n");
	return 0;
}

//²úÉú hash±í
int multi_hash(hash_paramiter *para)
{
int conflict,i,hashnum;
int *lp;
multi_hash_node *hash,*top,*hp,stack[para->key_count];

	if(!para) return -1;
	para->index=hash=(multi_hash_node *)malloc(para->key_count * sizeof(multi_hash_node));
	if(!hash) {
		return MEMERR;
	}

	top=stack;
	for(i=0;i<para->key_count;i++) {
		hash[i].rowno=-1;
		hash[i].link=-1;
		hash[i].count=0;
	}
//ShowLog(5,"multi_hash:data_count=%d,key_count=%d",para->data_count,para->key_count);
	for(i=0;i<para->data_count;i++) {
	    hashnum=para->do_hash(GETDATA(i),para->key_count);
	    hp=&hash[hashnum];
	    if(hp->rowno==-1) {	//ûÓÐÉ¢ÁгåÍ» 
		hp->rowno=i;
		hp->count=1;
	    } else if(!COMPARE(i,hp->rowno)) {	//¼ì²éÖØÂ룬¹¹½¨ÖØÂëÁ´
		hp->count++;
		continue;
	    } else {				//ÓÐÉ¢ÁгåÍ»£¬´æ´¢³åÍ»Á´
		if(top>stack&&!COMPARE(i,top[-1].rowno)) {
			top[-1].count++;
			continue;
		}
		top->rowno=i;
		top->link=hashnum;
		top->count=1;
		top++;
	    }
	}
	conflict=top-stack;
	if(top > stack) { //ÓÐÉ¢ÁгåÍ»£¬¹¹½¨³åÍ»Á´ 
		hp=hash;
		for(i=0;top>stack&&i<para->key_count;i++,hp++) {
			if(hp->rowno > -1) continue;
			top--;
//ÕÒµ½Ë÷Òý±íÀïµÄ¿ÕÏî 
			hp->rowno=top->rowno;
			hp->count=top->count;
			hp->link=-1;
			for(lp=&top->link;*lp != -1;lp=&hash[*lp].link)
				;
			*lp=i;
		}
	}
	return conflict;
}

  bool ProfileLimits::operator> (const ProfileLimits& other) const
  {
    int p1 = GetProfileOrdering (profile);
    int p2 = GetProfileOrdering (other.profile);
    if (p1 > p2) return true;
    if (p1 < p2) return false;
  
    if (vendor > other.vendor) return true;
    if (vendor < other.vendor) return false;
  
#define COMPARE(Limit) \
    if (Limit > other.Limit) return true; \
    if (Limit < other.Limit) return false;
    COMPARE (extensions); // @@@ Right?
    COMPARE (MaxInstructions);
    COMPARE (NumInstructionSlots);
    COMPARE (NumMathInstructionSlots);
    COMPARE (NumTexInstructionSlots);
    COMPARE (NumTemps);
    COMPARE (MaxLocalParams);
    COMPARE (MaxTexIndirections);
    COMPARE (MaxAddressRegs);
#undef COMPARE
    return false;
  }

    void
insert_heap(
        const sort_t* s,
        int index)
{
    int i;

    for (i = index; i < s->count; )
    {
        int index1 = i * 2 + 1;
        int index2 = index1 + 1;

        if (index2 < s->count)
        {
            char* item0 = s->head + i * s->size;
            char* item1 = s->head + index1 * s->size;
            char* item2 = item1 + s->size;

            if (COMPARE(s, item1, item2) > 0)
            {
                int index = index1;
                char* item = item1;
                index1 = index2;
                index2 = index;
                item1 = item2;
                item2 = item;
            }

            if (COMPARE(s, item0, item1) > 0)
            {
                SWAP(item0, item1, s->size);
                i = index1;
                continue;
            }
            else if (COMPARE(s, item0, item2) > 0)
            {
                SWAP(item0, item2, s->size);
                i = index2;
                continue;
            }
        }
        else if (index1 < s->count)
        {
            char* item0 = s->head + i * s->size;
            char* item1 = s->head + index1 * s->size;
            if (COMPARE(s, item0, item1) > 0)
            {
                SWAP(item0, item1, s->size);
            }
        }

        break;
    }
}

bool BackgroundDef::operator<( const BackgroundDef &other ) const
{
#define COMPARE(x) if( x < other.x ) return true; else if( x > other.x ) return false;
	COMPARE( m_sEffect );
	COMPARE( m_sFile1 );
	COMPARE( m_sFile2 );
	COMPARE( m_sColor1 );
	COMPARE( m_sColor2 );
#undef COMPARE
	return false;
}

/*
 * Mirror image to ldistribute: stably distribute a buffer of
 * "bufsize" elements from the _end_ of the sequence of "nmemb"
 * elements starting at "start" throughout the rest of the
 * sequence, assuming elements in the buffer to come _after_
 * things in the main sequence.
 *
 * Hideous clone-and-hack of ldistribute. I'd much rather have a
 * useful way of combining the two routines into one piece of
 * source code.
 */
static void rdistribute(void *base, size_t size, cmpfn compare CTXPARAM,
 			size_t start, size_t nmemb, size_t bufsize)
{
    size_t bufbot = start + nmemb - bufsize;

    while (bufsize > 0) {
	size_t buftop = bufbot + bufsize;
	/*
	 * Binary-search in the main array (or rather, that part
	 * of it from buftop upwards) to find where the element at
	 * buftop-1 should be placed. In the event of a tie,
	 * stability is preserved by treating bufbot as coming
	 * after any other indistinguishable element.
	 */
	size_t bot = start-1, top = bufbot, mid;

	while (top - bot > 1) {
	    mid = (top + bot) / 2;
	    if (COMPARE(buftop-1, mid) < 0)
		top = mid;
	    else
		bot = mid;
	}

	/*
	 * Now we have a piece of array looking like this:
	 *
	 *  top               bufbot     buftop
	 *   +------------------+--------+-+
	 *   |         B        |    A   |X|
	 *   +------------------+--------+-+
	 *
	 * and we need it to look like this:
	 *   +--------+-+------------------+
	 *   |    A   |X|         B        |
	 *   +--------+-+------------------+
	 *
	 * This is therefore a trivial block exchange: we move
	 * the whole buffer to after B, and then just stop
	 * considering element X to be part of the buffer.
	 */
	block_exchange(base, size, top, bufbot - top, bufsize);
	bufbot = top;
	buftop = bufbot + bufsize;
	/*
	 * As in ldistribute, we must skip over identical elements
	 * here, to preserve linear time complexity.
	 */
	do {
	    bufsize--;
	} while (bufsize > 0 && COMPARE(bufbot + bufsize-1, buftop-1) == 0);
    }
}

int SELECT2(int arr[], int n, int k)
{
	if(n<25)
	{
		return insertion_sort(arr, n, k);
	}

	int V = arr[random_int(0,n)];

	int *L = malloc(n * sizeof(*L));
	int *E = malloc(n * sizeof(*E));
	int *G = malloc(n * sizeof(*G));

	int i=0, l=0, e=0, g=0;

	while(i<n)
	{
		if(COMPARE(arr[i],V) == 2) //(arr[i]<V)
		{
			L[l] = arr[i];
			l++;
		}
		else if(COMPARE(arr[i], V) == 1) //(arr[i]==V)
		{
			E[e] = arr[i];
			e++;
		}
		else
		{
			G[g] = arr[i];
			g++;
		}
		i++;
	}

	if(k<=l)
	{
		SELECT2(L, l, k);
	}
	else if(k<=l+e)
	{
		return(V);
	}
	else
	{
		SELECT2(G, g, k - l - e);
	}
	
	


}