void
tmevtb_delete(TMEVTB *p_tmevtb)
{
	uint_t	index = p_tmevtb->index;
	uint_t	parent;
	EVTTIM	event_time = TMEVT_NODE(last_index).time;

	/*
	 *  last_index--
	 *  if last_index == 0
	 *  do nothing．
	 */
	if (--last_index == 0) {
		return;
	}

	/*
	 *
	 *  insert the last time event into the position of deleted time
	 *  event. In fact, the insert does not happened. The position of 
	 *  deleted time will be a empty node in time event heap. Then this
	 *  empty node will be moved to a right position which is the right
	 *  position of the last time event. 
	 * 
	 *  If the event time of the last time event is earlier than deleted
	 *  time event's parent, then search up, or search down.
	 *
	 */
	if (index > 1 && EVTTIM_LT(event_time,
								TMEVT_NODE(parent = PARENT(index)).time)) {
		/*
		 *  if deleted time event's parent is not earlier than last time event
		 *  in heap, change parent's position and update info.
		 * 
		 */
		TMEVT_NODE(index) = TMEVT_NODE(parent);
		TMEVT_NODE(index).p_tmevtb->index = index;

		/*
		 *  then search up to find the right position for the last time event in heap
		 *  from parent's position
		 */
		index = tmevt_up(parent, event_time);
	}
	else {
		/*
		 *  search down to find right position for last time event in heap．
		 */
		index = tmevt_down(index, event_time);
	}

	/*
	 * update the last time event's info
	 */ 
	TMEVT_NODE(index) = TMEVT_NODE(last_index + 1);
	TMEVT_NODE(index).p_tmevtb->index = index;
}

static void _sio_timer_adjust_heap(struct sio_timer_manager *st_mgr, struct sio_timer *timer)
{
    uint64_t parent = PARENT(timer);
    
    if (parent && timer->expire < st_mgr->heap_nodes[parent]->expire) 
        _sio_timer_upheap(st_mgr, timer);
    else
        _sio_timer_downheap(st_mgr, timer);
}

HWND bookSetup( ULONG idInitialPage )
{
    HWND hwndFrame;

    if( hwndBook )
    {
        hwndFrame = PARENT( hwndBook );

        // For some reason it is necessary to restore the notebook before
        // setting the frame as the active window if the frame is being
        // restored from a minimized state.

        WinSetWindowPos( hwndBook, NULLHANDLE, 0, 0, 0, 0,
                         SWP_SHOW | SWP_RESTORE );
        WinSetWindowPos( hwndFrame, NULLHANDLE, 0, 0, 0, 0,
                         SWP_SHOW | SWP_RESTORE | SWP_ACTIVATE );
    }
    else
    {
        FRAMECDATA fcdata;

        memset( &fcdata, 0, sizeof fcdata );
        fcdata.cb            = sizeof( FRAMECDATA );
        fcdata.flCreateFlags = FRAME_FLAGS;
        fcdata.idResources   = ID_NBFRAME;

        hwndFrame = WinCreateWindow( HWND_DESKTOP, WC_FRAME, NULL, WS_ANIMATE,
                                     0, 0, 0, 0, NULLHANDLE, HWND_TOP,
                                     ID_NBFRAME, &fcdata, NULL );
        if( hwndFrame )
        {
            pfnwpFrame = WinSubclassWindow( hwndFrame, wpNBFrame );
            if( pfnwpFrame )
                if( CreateNotebookWindow( hwndFrame ) )
                    WinSetWindowText( hwndFrame, BOOK_TITLE );
                else
                {
                    WinDestroyWindow( hwndFrame );
                    hwndFrame = NULLHANDLE;
                }
            else
            {
                WinDestroyWindow( hwndFrame );
                Msg( "bookSetup WinSubclassWindow RC(%X)", HWNDERR(hwndFrame) );
                hwndFrame = NULLHANDLE;
            }
        }
        else
            Msg( "bookSetup WinCreateWindow of frame window RC(%X)", HABERR(0));
    }

    if( hwndBook )
        TurnToPage( idInitialPage );

    return hwndFrame;
}

/*****************************************************************************
 * heap_build
 *
 * Build a heap from an unordered array.
 *****************************************************************************/
void heap_build( heap_t *heap )
{
    GLint	i;

    heap->size = heap->length;

    for ( i = PARENT( heap->length ) ; i >= 0 ; i-- ) {
	heapify( heap, i );
    }
}

void priority(BinHeap *bh, int data, int newPriority){
    long i = 0, k;
    while (i < bh->size){
        if (bh->A[i].data == data){
            printf("sosi%d \n", newPriority);
            if (newPriority < bh->A[i].priority){
                bh->A[i].priority = newPriority;
                k = i;
                while(k && newPriority < bh->A[PARENT(k)].priority) {
                    bh->A[k] = bh->A[PARENT(k)];
                    k = PARENT(k);
                }
                bh->A[k].priority = newPriority;
                bh->A[k].data = data;
            }
        }
        i++;
    }
}

void insert_heap(puzzle b)
{
   puzzle tmp;
   int    index;

   if (heap_size == MAX_HEAP_SIZE) {
      printf ("Heap overflow\n");
      exit(-1);
   }
   heap[heap_size] = b;
   index = heap_size;
   heap_size++;
   while ((index > 0) && superior(index, PARENT(index))) {
      tmp = heap[index];
      heap[index] = heap[PARENT(index)];
      heap[PARENT(index)] = tmp;
      index = PARENT(index);
   }
}

void
pqueue_enqueue(pqueue_t *queue, const void *data) {
	size_t i;
	void *tmp = NULL;
	if (queue == NULL || queue->size >= queue->capacity)
		return;
	/* adds element last */
	queue->data[queue->size] = (void*)data;
	i = queue->size;
	queue->size++;

	/* the new element is swapped with its parent as long as its precedence is higher */
	while(i > 0 && queue->cmp(queue->data[i], queue->data[PARENT(i)]) > 0) {
		tmp = queue->data[i];
		queue->data[i] = queue->data[PARENT(i)];
		queue->data[PARENT(i)] = tmp;
		i = PARENT(i);
	}
}

static void
dvb_flush			(vbi_capture *		cap)
{
	vbi_capture_dvb *dvb = PARENT (cap, vbi_capture_dvb, capture);

	vbi_dvb_demux_reset (dvb->demux);

	dvb->bp = dvb->pes_buffer;
	dvb->b_left = 0;
}

void DominatorTree::debugPrint()
{
   for (int i = 0; i < count; ++i) {
      INFO("SEMI(%i) = %i\n", i, SEMI(i));
      INFO("ANCESTOR(%i) = %i\n", i, ANCESTOR(i));
      INFO("PARENT(%i) = %i\n", i, PARENT(i));
      INFO("LABEL(%i) = %i\n", i, LABEL(i));
      INFO("DOM(%i) = %i\n", i, DOM(i));
   }
}

void up(struct minheap * mh,int index) 
{
	int parent = PARENT(index);
	while(parent >= 1)
	{
		assert(mh->elts[index]);
		assert(mh->elts[parent]);
		if (mh->less(mh->ud,mh->elts[index],mh->elts[parent]))
		{
			swap(mh,index,parent);
			index = parent;
			parent = PARENT(index);
		}
		else 
		{
			break;
		}
	}
}

/* BSTreeDepth
 *  returns number of layers in b-tree
 *
 *  if "exact" is 1, then the maximum
 *  depth is returned. otherwise, the depth of
 *  an arbitrary leaf node is returned
 */
LIB_EXPORT uint32_t CC BSTreeDepth ( const BSTree *bt, bool exact )
{
    BSTNode *p;
    uint32_t depth;

    if ( bt == NULL || bt -> root == NULL )
        return 0;

    depth = 1;

    if ( exact )
    {
        for ( p = FirstNode ( bt ); p != NULL; p = BSTNodeNext ( p ) )
        {
            BSTNode *q;
            unsigned int ndepth;

            if ( p -> child [ 0 ] != NULL || p -> child [ 1 ] != NULL )
                continue;

            for ( ndepth = 1, q = PARENT ( p ); q != NULL; q = PARENT ( q ) )
                ++ ndepth;

            if ( ndepth > depth )
                depth = ndepth;
        }
    }
    else
    {
        for ( p = bt -> root;; ++ depth )
        {
            if ( p -> child [ 0 ] != NULL )
                p = p -> child [ 0 ];
            else if ( p -> child [ 1 ] != NULL )
                p = p -> child [ 1 ];
            else
                break;
        }
    }

    return depth;
}

static void
bubble_up(pq q, unsigned int k)
{
    int p;

    if (k == 0) return;
    p = PARENT(k);
    if (cmp(q, p, k) <= 0) return;
    swap(q, k, p);
    bubble_up(q, p);
}

void DominatorTree::buildDFS(Graph::Node *node)
{
   SEMI(node->tag) = node->tag;

   for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) {
      if (SEMI(ei.getNode()->tag) < 0) {
         buildDFS(ei.getNode());
         PARENT(ei.getNode()->tag) = node->tag;
      }
   }
}

static
bool CC BSTreeContains ( const BSTNode *root, const BSTNode *n )
{
    while ( n != NULL )
    {
        if ( n == root )
            return true;
        n = PARENT ( n );
    }
    return false;
}

// Adds a timer to the heap, using timer_node data. Passed
// timer_node is first unused element in timer_heap array.
__forceinline void TimerAddNode(timer_node *t)
{
   if (numActiveTimers == 0 || timer_heap[0]->time > t->time)
   {
      // We're making a new first-timer, so the time main loop should wait might
      // have changed, so have it break out of loop and recalibrate
      MessagePost(main_thread_id, WM_BLAK_MAIN_RECALIBRATE, 0, 0);
   }

   // Start node off at end of heap.
   int i = numActiveTimers++;
   timer_heap[i]->heap_index = i;

   // Push node up if necessary.
   while (i > 0 && timer_heap[i]->time < timer_heap[PARENT(i)]->time)
   {
      TimerSwapIndex(i, PARENT(i));
      i = PARENT(i);
   }
}

void TasNoeud_monter(TasNoeud *tas, int k) {
    int mincout, parent;
    if (k > 0) { // Condition de terminaison
        parent = PARENT(k);
        mincout = parent;
        if (tas->noeuds[k].cout < tas->noeuds[mincout].cout) { // Autre condition de terminaison
            ECHANGER(tas, k, mincout);
            TasNoeud_monter(tas, mincout); // Continuer tant que le tas n'est pas ordonné
        }
    }
}

Node *malloc_node(Interval key)
{
	Node *n = (Node *)malloc(sizeof(Node));
	assert(n);
	KEY(n) = key;
	SET_RED(n);
	PARENT(n) = LEFT(n) = RIGHT(n) = &NIL_NODE;
	n->max = HIGH(key);

	return n;
}

bool
insert(Any_Type a, struct Heap *h)
{
	u_long          i;

	if (is_heap_full(h))
		return false;

	i = ++h->num_elements;

	/*
	 * find the correct place to insert
	 */
	while ((i > 1) && (*h->compare) (h->storage[PARENT(i)], a)) {
		h->storage[i] = h->storage[PARENT(i)];
		i = PARENT(i);
	}
	h->storage[i] = a;
	return true;
}

/* create_block_tree:
 * Construct block tree by peeling nodes from block list in state.
 * When done, return root. The block list is empty
 * FIX: use largest block as root
 */
block_t *createBlocktree(Agraph_t * g, circ_state * state)
{
    block_t *bp;
    block_t *next;
    block_t *root;
    int min;
    /* int        ordercnt; */

    find_blocks(g, state);

    bp = state->bl.first;	/* if root chosen, will be first */
    /* Otherwise, just pick first as root */
    root = bp;

    /* Find node with minimum VAL value to find parent block */
    /* FIX: Should be some way to avoid search below.               */
    /* ordercnt = state->orderCount;  */
    for (bp = bp->next; bp; bp = next) {
	Agnode_t *n;
	Agnode_t *parent;
	Agnode_t *child;
	Agraph_t *subg = bp->sub_graph;

	child = n = agfstnode(subg);
	min = VAL(n);
	parent = PARENT(n);
	for (n = agnxtnode(subg, n); n; n = agnxtnode(subg, n)) {
	    if (VAL(n) < min) {
		child = n;
		min = VAL(n);
		parent = PARENT(n);
	    }
	}
	SET_PARENT(parent);
	CHILD(bp) = child;
	next = bp->next;	/* save next since list insertion destroys it */
	appendBlock(&(BLOCK(parent)->children), bp);
    }
    initBlocklist(&state->bl);	/* zero out list */
    return root;
}

int bstree_right_rotate( bstree_t *tree_in, long idx_in )
{
	long x,y;
	x = idx_in;
	y = tree_in->start[idx_in].left;
	if( PARENT(x) != -1 )
	{
		if( PARENT_LEFT(x) == x )
			PARENT_LEFT(x) = y;
		else
			PARENT_RIGHT(x) = y;
	}
	else
		tree_in->root = y;
	PARENT(y) = PARENT(x);
	PARENT(x) = y;
	LEFT(x) = RIGHT(y);
	if( RIGHT(y) != -1 )
		RIGHT_PARENT(y) = x;
	RIGHT(y) = x;
}