/*
 * This writes out a char * string with attributes.
 */
void writeCharAttrib (WINDOW *window,
		      int xpos,
		      int ypos,
		      char *string,
		      chtype attr,
		      int align,
		      int start,
		      int end)
{
   int display = end - start;
   int x;

   if (align == HORIZONTAL)
   {
      /* Draw the message on a horizontal axis. */
      display = MINIMUM (display, getmaxx (window) - 1);
      for (x = 0; x < display; x++)
      {
	 mvwaddch (window, ypos, xpos + x, CharOf (string[x + start]) | attr);
      }
   }
   else
   {
      /* Draw the message on a vertical axis. */
      display = MINIMUM (display, getmaxy (window) - 1);
      for (x = 0; x < display; x++)
      {
	 mvwaddch (window, ypos + x, xpos, CharOf (string[x + start]) | attr);
      }
   }
}

void main()
{
  int a=10,b=20;

  #ifdef MAX
  printf ("the larger one is %d\n",MAXIMUM(a,b));
  #else
  printf ("the lower one is %d\n",MINIMUM(a,b));
  #endif

  #ifndef MIN
  printf ("the lower one is %d\n",MINIMUM(a,b));
  #else
  printf ("the larger one is %d\n",MAXIMUM(a,b));
  #endif

  #undef MAX
  #ifdef MAX
  printf ("the larger one is %d\n",MAXIMUM(a,b));
  #else
  printf ("the lower one is %d\n",MINIMUM(a,b));
  #endif

  #ifndef MIN
  printf ("the lower one is %d\n",MINIMUM(a,b));
  #else
  printf ("the larger one is %d\n",MAXIMUM(a,b));
  #endif
}

/*
 * Copy and nul-terminate a ringbuffer to a string.
 */
ssize_t
ringbuf_to_string(char *buf, size_t len, struct ringbuf *rb)
{
	size_t copy_len, n;

	if (buf == NULL || rb == NULL || len == 0)
		return (-1);

	copy_len = MINIMUM(len - 1, ringbuf_used(rb));

	if (copy_len == 0)
		return (copy_len);

	if (rb->start < rb->end)
		memcpy(buf, rb->buf + rb->start, copy_len);
	else {
		/* If the buffer is wrapped, copy each hunk separately */
		n = rb->len - rb->start;
		memcpy(buf, rb->buf + rb->start, MINIMUM(n, copy_len));
		if (copy_len > n)
			memcpy(buf + n, rb->buf,
			    MINIMUM(rb->end, copy_len - n));
	}
	buf[copy_len] = '\0';

	return (ringbuf_used(rb));
}

/*
 * This writes out a chtype * string * with the given attributes added.
 */
void writeChtypeAttrib (WINDOW *window,
			int xpos,
			int ypos,
			chtype *string,
			chtype attr,
			int align,
			int start,
			int end)
{
   /* *INDENT-EQLS* */
   int diff             = end - start;
   int display          = 0;
   int x                = 0;

   if (align == HORIZONTAL)
   {
      /* Draw the message on a horizontal axis. */
      display = MINIMUM (diff, getmaxx (window) - xpos);
      for (x = 0; x < display; x++)
      {
	 mvwaddch (window, ypos, xpos + x, string[x + start] | attr);
      }
   }
   else
   {
      /* Draw the message on a vertical axis. */
      display = MINIMUM (diff, getmaxy (window) - ypos);
      for (x = 0; x < display; x++)
      {
	 mvwaddch (window, ypos + x, xpos, string[x + start] | attr);
      }
   }
}

static void
do_geometry(const char *name, const char *spec)
{
	double re_1, im_1;
	double re_2, im_2;
	char comma;
	char sg_1;
	char sg_2;
	char ii_1;
	char ii_2;
	char ch;

#define PLUS_OR_MINUS(c)  ((c) == '+' || (c) == '-')
#define IMAGINARY_UNIT(x) ((x) == 'i' || (x) == 'j')

	if (sscanf(spec, 
	           "%lf %c %lf %c %c %lf %c %lf %c %c", 
	           &re_1,
	           &sg_1,
	           &im_1,
	           &ii_1,
	           &comma,
	           &re_2,
	           &sg_2,
	           &im_2,
	           &ii_2,
	           &ch) != 9
	    || !PLUS_OR_MINUS(sg_1)
	    || !PLUS_OR_MINUS(sg_2)
	    || !IMAGINARY_UNIT(ii_1)
	    || !IMAGINARY_UNIT(ii_2)
	    || comma != ',') {
		fprintf(stderr, "invalid geometry specification.\n");
		exit(1);
	}

#define MINIMUM(x, y) ((x) <= (y) ? (x) : (y))
#define MAXIMUM(x, y) ((x) >= (y) ? (x) : (y))
#define SIGN(c) ((c) == '-' ? -1.0 : +1.0)

	/* Sign-adjust. */
	im_1 *= SIGN(sg_1);
	im_2 *= SIGN(sg_2);

	/*
	 * We have two edges of the rectangle. Now, find the upper-left 
	 * (i.e. the one with minimum real part and maximum imaginary
	 * part) and lower-right (maximum real part, minimum imaginary)
	 * corners of the rectangle.
	 */
	upper_left_re = MINIMUM(re_1, re_2);
	upper_left_im = MAXIMUM(im_1, im_2);
	lower_right_re = MAXIMUM(re_1, re_2);
	lower_right_im = MINIMUM(im_1, im_2);
}

dropout_result digibeta_dropout(YUV_frame* in_frame, int xOffset, int yOffset,
                                int* workSpace)
{
    int     h, w, y;
    BYTE*   inLine;
    int*    outLine;
    int*    work[2];

    work[0] = workSpace;
    work[1] = work[0] + (WIDTH * HEIGHT / 2);
    // high pass filter input to workspace
    memset(work[0], 0, sizeof(int) * WIDTH * HEIGHT / 2);
    inLine = in_frame->Y.buff;
    outLine = work[0];
    if (xOffset >= 0)
    {
        inLine += xOffset * in_frame->Y.pixelStride;
        w = MINIMUM(in_frame->Y.w - xOffset, WIDTH);
    }
    else
    {
        outLine -= xOffset;
        w = MINIMUM(in_frame->Y.w, WIDTH + xOffset);
    }
    if (yOffset >= 0)
    {
        inLine += yOffset * in_frame->Y.lineStride;
        h = MINIMUM(in_frame->Y.h - yOffset, HEIGHT);
    }
    else
    {
        h = in_frame->Y.h;
        if ((yOffset % 2) != 0)
        {
            inLine += in_frame->Y.lineStride;
            yOffset -= 1;
            h -= 1;
        }
        outLine -= (yOffset / 2) * WIDTH;
        h = MINIMUM(h, HEIGHT + yOffset);
    }
    for (y = 0; y < (h + 1) / 2; y++)
    {
        hpf_line(inLine, outLine, in_frame->Y.pixelStride, w);
        inLine += 2 * in_frame->Y.lineStride;
        outLine += WIDTH;
    }
    // block average high pass filtered input
    block_average(work[0], work[1]);
    // high pass filter it to isolate dropout spikes
    spatial_hpf(work[1], work[0]);
    // process data in workspace to find dropouts
    return detect_dropout(work[0]);
}

static int
input_kex_dh_gex_request(int type, u_int32_t seq, struct ssh *ssh)
{
	struct kex *kex = ssh->kex;
	int r;
	u_int min = 0, max = 0, nbits = 0;

	debug("SSH2_MSG_KEX_DH_GEX_REQUEST received");
	if ((r = sshpkt_get_u32(ssh, &min)) != 0 ||
	    (r = sshpkt_get_u32(ssh, &nbits)) != 0 ||
	    (r = sshpkt_get_u32(ssh, &max)) != 0 ||
	    (r = sshpkt_get_end(ssh)) != 0)
		goto out;
	kex->nbits = nbits;
	kex->min = min;
	kex->max = max;
	min = MAXIMUM(DH_GRP_MIN, min);
	max = MINIMUM(DH_GRP_MAX, max);
	nbits = MAXIMUM(DH_GRP_MIN, nbits);
	nbits = MINIMUM(DH_GRP_MAX, nbits);

	if (kex->max < kex->min || kex->nbits < kex->min ||
	    kex->max < kex->nbits || kex->max < DH_GRP_MIN) {
		r = SSH_ERR_DH_GEX_OUT_OF_RANGE;
		goto out;
	}

	/* Contact privileged parent */
	kex->dh = PRIVSEP(choose_dh(min, nbits, max));
	if (kex->dh == NULL) {
		sshpkt_disconnect(ssh, "no matching DH grp found");
		r = SSH_ERR_ALLOC_FAIL;
		goto out;
	}
	debug("SSH2_MSG_KEX_DH_GEX_GROUP sent");
	if ((r = sshpkt_start(ssh, SSH2_MSG_KEX_DH_GEX_GROUP)) != 0 ||
	    (r = sshpkt_put_bignum2(ssh, kex->dh->p)) != 0 ||
	    (r = sshpkt_put_bignum2(ssh, kex->dh->g)) != 0 ||
	    (r = sshpkt_send(ssh)) != 0)
		goto out;

	/* Compute our exchange value in parallel with the client */
	if ((r = dh_gen_key(kex->dh, kex->we_need * 8)) != 0)
		goto out;

	debug("expecting SSH2_MSG_KEX_DH_GEX_INIT");
	ssh_dispatch_set(ssh, SSH2_MSG_KEX_DH_GEX_INIT, &input_kex_dh_gex_init);
	r = 0;
 out:
	return r;
}

struct TREE_NODE* MINIMUM(struct TREE_NODE *N)
{
	if(N == NULL) return NULL;
	if(N->L == NULL && N->R == NULL) return N;
	int min = N->K;
	struct TREE_NODE *X = MINIMUM(N->L);
	struct TREE_NODE *Y = MINIMUM(N->R);
	if(X != NULL)
	{
		if(X->K < min) return X;
	}
	if(Y != NULL)
	{
		if(Y->K < min) return Y;
	}
}

const TreeNode<T>* BST<T>::predecessor (const T &v) const {
  const TreeNode<T> *n = search (v);
  if (n == NULL) 
   throw std::runtime_error ("the searched value does not exsit in the tree");

  //if the node has a left child, it's the predecessor
  if (n->left != NULL) 
    return n->left->v;

  //else find the ancestor such that the node is on the ancestor's RHS, find the minimum value rooted at the ancestor
  else {
    const TreeNode<T> *c = n;	//current node
    const TreeNode<T> *p = n->p;	//the parent of n
    while ((p!=NULL) && (p->right!=c)) {
      c = p;
      p = p->p;
    }

    if (p == NULL) {
      throw std::runtime_error ("the value is the minimum in the tree, node predecessor");
    }
    else {
      return MINIMUM(p);
    }
  }
}

void BST<T>::remove (const T &v) throw (std::runtime_error) {
  //find the node with the value 
  TreeNode<T> *n = search (v);
  if (n == NULL) {
    throw std::runtime_error("the deleted value does not exist in the BST");
  }
  //if both left and right are NULL, just delete n
  if ((n->left==NULL) && (n->right==NULL)) {
    if (n->p == NULL) {
      delete root;
      root = NULL;
    }
    else {
      if (n == n->p->left)
        n->p->left = NULL;
      else 
        n->p->right = NULL;
      delete n;
      n = NULL;
    }
  }
  //if n->right == NULL, lift n->left
  else {
    if (n->right == NULL) 
      TRANSPOSE (n, n->right);
  
    //else lift the minimum node on the right
    else {
      TreeNode<T> *r = MINIMUM(n->right);
      ////std::cout << "r: " << r->v << std::endl;
      TRANSPOSE (n, r);
    }
  }
}

int
kexgex_client(struct ssh *ssh)
{
	struct kex *kex = ssh->kex;
	int r;
	u_int nbits;

	nbits = dh_estimate(kex->dh_need * 8);

	kex->min = DH_GRP_MIN;
	kex->max = DH_GRP_MAX;
	kex->nbits = nbits;
	if (datafellows & SSH_BUG_DHGEX_LARGE)
		kex->nbits = MINIMUM(kex->nbits, 4096);
	/* New GEX request */
	if ((r = sshpkt_start(ssh, SSH2_MSG_KEX_DH_GEX_REQUEST)) != 0 ||
	    (r = sshpkt_put_u32(ssh, kex->min)) != 0 ||
	    (r = sshpkt_put_u32(ssh, kex->nbits)) != 0 ||
	    (r = sshpkt_put_u32(ssh, kex->max)) != 0 ||
	    (r = sshpkt_send(ssh)) != 0)
		goto out;
	debug("SSH2_MSG_KEX_DH_GEX_REQUEST(%u<%u<%u) sent",
	    kex->min, kex->nbits, kex->max);
#ifdef DEBUG_KEXDH
	fprintf(stderr, "\nmin = %d, nbits = %d, max = %d\n",
	    kex->min, kex->nbits, kex->max);
#endif
	ssh_dispatch_set(ssh, SSH2_MSG_KEX_DH_GEX_GROUP,
	    &input_kex_dh_gex_group);
	r = 0;
 out:
	return r;
}

static libcouchbase_ssize_t
read_common(lcb_luv_socket_t sock, void *buffer, libcouchbase_size_t len,
            int *errno_out)
{
    struct lcb_luv_evstate_st *evstate = sock->evstate + LCB_LUV_EV_READ;
    libcouchbase_ssize_t ret;
    size_t read_offset, toRead;

    log_read_debug("%d: Requested to read %d bytes. have %d",
                sock->idx, len, sock->read.nb);


    /* basic error checking */
    if (evstate->err) {
        *errno_out = evstate->err;
        evstate->err = 0;
        return -1;
    }

    if (sock->eof) {
        return 0;
    }

    /* Check how much data we can send back, and where do we read from */
    toRead = MINIMUM(len, sock->read.nb);
    read_offset = sock->read.pos;

    /* copy the data */
    if (toRead) {
        memcpy(buffer, sock->read.data + read_offset, toRead);
        ret = toRead;
        *errno_out = 0;
    } else {
        *errno_out = EWOULDBLOCK;
        ret = -1;
    }

    /**
     * Buffer positioning is somewhat complicated. If we are in middle of a partial
     * read (readahead is active), then the next bytes will still happen from within
     * the position of our current buffer, so we want to maintain our position.
     *
     * On the other hand, if readahead is not active, then the next read will begin
     * from the beginning of the buffer
     */
    sock->read.nb -= toRead;
    sock->read.pos += toRead;

    if (sock->read.nb == 0 && sock->read.readhead_active == 0) {
        sock->read.pos = 0;
    }


    if (toRead < len) {
        evstate->flags &= ~(LCB_LUV_EVf_PENDING);
        lcb_luv_read_nudge(sock);
    }

    return ret;
}

void ViewBase::set_viewport_dims(ushort2 dims, float scale) {
	view.dims.x = (unsigned short) (dims.x * scale);
	view.dims.y = (unsigned short) (dims.y * scale);
	pixel_ratio_rotation = 180.0f / (MINIMUM(dims.x, dims.y));	
	pixel_ratio_translation = (distance_limits.y - distance_limits.x) / (dims.y / 2);
	update_view();
}

static fpos_t
wmemstream_seek(void *v, fpos_t off, int whence)
{
	struct state	*st = v;
	ssize_t		 base = 0;

	switch (whence) {
	case SEEK_SET:
		break;
	case SEEK_CUR:
		base = st->pos;
		break;
	case SEEK_END:
		base = st->len;
		break;
	}

	if (off > (SIZE_MAX / sizeof(wchar_t)) - base || off < -base) {
		errno = EOVERFLOW;
		return (-1);
	}

	/*
	 * XXX Clearing mbs here invalidates shift state for state-
	 * dependent encodings, but they are not (yet) supported.
	 */
	bzero(&st->mbs, sizeof(st->mbs));

	st->pos = base + off;
	*st->psize = MINIMUM(st->pos, st->len);

	return (st->pos);
}

/*
 * This draws the widget.
 */
static void drawCDKDScaleField (CDKDSCALE *widget)
{
   char temp[256];

   werase (widget->fieldWin);

   /* Draw the value in the field. */
   {
      char format[256];
      int digits = MINIMUM(widget->digits, 30);
      sprintf (format, "%%.%if", digits);
      sprintf (temp, format, widget->current);
   }
   writeCharAttrib (widget->fieldWin,
		    widget->fieldWidth - (int)strlen(temp) - 1,
		    0,
		    temp,
		    widget->fieldAttr,
		    HORIZONTAL,
		    0,
		    (int)strlen(temp));

   moveToEditPosition(widget, widget->fieldEdit);
   wrefresh (widget->fieldWin);
}

void ViewBase::update_view() {										//biggest cube edge is 2 and center == [0,0,0]
    view.origin = vector_rotate(cam_pos, cam_matrix);
	view.direction = vector_normalize(-view.origin);	
	float step_px = virtual_view_size / MINIMUM(view.dims.x, view.dims.y);
	view.right_plane = vector_rotate(make_float4(1, 0, 0, 0), cam_matrix) * step_px;
    view.up_plane = vector_rotate(make_float4(0, 1, 0, 0), cam_matrix) * step_px;
}

static int formattedSize (CDKFSLIDER *widget, float value)
{
   char temp[256];
   char format[256];
   int digits = MINIMUM(widget->digits, 30);
   sprintf (format, "%%.%if", digits);
   sprintf (temp, format, value);
   return strlen (temp);
}

  void SkillSet::trajectory2D(const Vector2D<int>&   startPos,
                              const Vector2D<int>&   finalPos,
                              const Vector2D<float>& startVel,
                              const Vector2D<float>& finalVel,
                              const float            startAng,
                              const float            finalAng,
                              const float            startAngVel,
                              const float            finalAngVel,
                              const float            frameRate,
                              const float            maxAcc,
                              const float            maxVel,
                              const float            maxAngAcc,
                              const float            maxAngVel,
                              Vector2D<float>&       trajVel,
                              float&                 angVel)
  {
    Vector2D<float> acc;
    float timeX, timeY;
    Vector2D<int> delta = finalPos - startPos;

    float u = PI / 2;
    float du = -PI / 2;
    // Performing binary search for the optimum value of alpha which will result in
    for (int i = 0; i < 10; ++i)
    {
      float alpha = u + (du /= 2);
      Vector2D<float> aTransMax, vTransMax;
      aTransMax.fromPolar(maxAcc, alpha);
      vTransMax.fromPolar(maxVel, alpha);

      trajectory1D(delta.x, startVel.x, finalVel.x, frameRate, aTransMax.x, vTransMax.x, acc.x, timeX);
      trajectory1D(delta.y, startVel.y, finalVel.y, frameRate, aTransMax.y, vTransMax.y, acc.y, timeY);

      if (timeX <= timeY)
        u = alpha;
    }

    float trajTime = MAXIMUM(timeX, timeY);
    float deltaAng = MINIMUM(finalAng - startAng, 0); // forcing deltaAng to lie in (-pi, pi]

    float angAcc = 0 , timeAng = INFINITY;
    for (float factor = 0.1f; factor <= 1.05f; factor += 0.1f)   // using 1.05f instead of 1.0f to account for errors due to floating point precision
    {
      trajectory1D(deltaAng, startAngVel, finalAngVel, frameRate, maxAngAcc * factor, maxAngVel, angAcc, timeAng);
      if (timeAng < trajTime)
        break;
    }

    trajVel.x = startVel.x + acc.x / frameRate;
    trajVel.y = startVel.y + acc.y / frameRate;
    angVel = startAngVel + angAcc / frameRate;
  } // trajectory2D

int effective_utilization(struct TASK_SET t,int task)	//get effective utilization given by f formula in slides
{							
int i;
int Hn=0;
int H1=0;
int N;
float Hn_sum=0.0;
float H1_sum=0.0;
float utilization=0.0;
	
		for(i=0;i<task;i++)
		{	
			if(t.task[i].period<=t.task[task].deadline)
			{
			Hn_sum+=(t.task[i].WCET/(MINIMUM(t.task[i].deadline,t.task[i].period)));
			Hn++;
			}
			else
			H1_sum+=t.task[i].WCET;
		}

	N=Hn+1;	//U(n)=num(Hn)+1

	utilization=Hn_sum+(t.task[task].WCET/(MINIMUM(t.task[task].deadline,t.task[task].period)))+(H1_sum/(MINIMUM(t.task[task].deadline,t.task[task].period)));

float root=1.0/N;
float utilization_bound=N*(pow(2.0,root)-1);	//the sufficient condition for the utilization

//	printf("\nFor task %d\n",task);	
//	printf("N=%d\n",N);
//	printf("Utilization=%f\n",utilization);
//	printf("Utilization bound=%f\n",utilization_bound);

		if(utilization>utilization_bound)	//We fail the sufficient condition
		return -FAILURE;

return SUCCESS;
		
}

static void
pap_response(pap *_this, int authok, const char *mes)
{
	int lpktp, lmes;
	u_char *pktp, *pktp1;
	const char *realm;

	pktp = ppp_packetbuf(_this->ppp, PPP_PROTO_PAP) + HEADERLEN;
	lpktp = _this->ppp->mru - HEADERLEN;
	realm = npppd_ppp_get_realm_name(_this->ppp->pppd, _this->ppp);

	pktp1 = pktp;
	if (mes == NULL)
		lmes = 0;
	else
		lmes = strlen(mes);
	lmes = MINIMUM(lmes, lpktp - 1);

	PUTCHAR(lmes, pktp1);
	if (lmes > 0)
		memcpy(pktp1, mes, lmes);
	lpktp = lmes + 1;

	if (authok)
		ppp_output(_this->ppp, PPP_PROTO_PAP, AUTHACK, _this->auth_id,
		    pktp, lpktp);
	else
		ppp_output(_this->ppp, PPP_PROTO_PAP, AUTHNAK, _this->auth_id,
		    pktp, lpktp);

	if (!authok) {
		pap_log(_this, LOG_ALERT,
		    "logtype=Failure username=\"%s\" realm=%s", _this->name,
		    realm);
		pap_stop(_this);
		ppp_set_disconnect_cause(_this->ppp, 
		    PPP_DISCON_AUTH_FAILED, PPP_PROTO_PAP, 1 /* peer */, NULL);
		ppp_stop(_this->ppp, "Authentication Required");
	} else {
		strlcpy(_this->ppp->username, _this->name,
		    sizeof(_this->ppp->username));
		pap_log(_this, LOG_INFO,
		    "logtype=Success username=\"%s\" realm=%s", _this->name,
		    realm);
		pap_stop(_this);
		ppp_auth_ok(_this->ppp);
		/* reset the state to response request of retransmision. */
		_this->state = PAP_STATE_SENT_RESPONSE;
	}
}