static int
descend_left(struct saucy *s)
{
	int target, lmin, rmin;

	/* Check that we ended at the right spot */
	if (s->nsplits != s->splitlev[s->lev]) return 0;

	/* Keep going until we're discrete */
	while (!at_terminal(s) && !zeta_fixed(s)) {

		/* We can pick any old target cell and element */
		select_decomposition(s, &target, &lmin, &rmin);

		/* Check if we need to refine on the left */
		s->match = 0;
		s->start[s->lev] = target;
		s->split = split_left;
		descend(s, &s->left, target, lmin);
		s->splitlev[s->lev] = s->nsplits;
		s->split = split_other;
		--s->lev;
		s->nsplits = s->splitlev[s->lev];

		/* Now refine on the right and ensure matching */
		s->specmin[s->lev] = s->right.lab[rmin];
		if (!descend(s, &s->right, target, rmin)) return 0;
		if (s->nsplits != s->splitlev[s->lev]) return 0;
	}
	return 1;
}

void
composite_box_rep::finalize () {
  int i, n= subnr ();
  lip= descend (ip, 0);
  rip= descend (ip, 1);
  for (i=0; i<n; i++) {
    path l= bs[i]->find_lip ();
    path r= bs[i]->find_rip ();
    /*
    cout << "  i  = " << i << "\n";
    cout << "  l  = " << l << "\n";
    cout << "  r  = " << r << "\n";
    */
    if (is_accessible (l) && is_accessible (r)) {
      if (is_decoration (lip) || path_less (reverse (l), reverse (lip)))
	lip= l;
      if (is_decoration (rip) || path_less (reverse (rip), reverse (r)))
	rip= r;
    }
  }
  /*
  cout << ((tree) (*((box_rep*) this))) << " " << ip << "\n";
  cout << "  lip= " << lip << "\n";
  cout << "  rip= " << rip << "\n";
  */
}

Obj_ptr quasiquoteMakeList(const ParseTree_ptr & tree, env_ptr & env)
{
	Obj_ptr obj;

	if (tree==nullptr)
	{
		obj = Obj_ptr( new PairObj(nullptr, nullptr) );
		return descend(obj);
	}

	std::string token = tree->getToken();

	if (token==".")
	{
		if (tree->getBrother() == nullptr || tree->getBrother()->getBrother() != nullptr)
			throw syntaxError("illegal use: \'.\'");
		return Quasiquote(tree->getBrother(), env);
	}
	else
	{
		Obj_ptr o1( Quasiquote(tree, env) );
		obj = Obj_ptr( new PairObj(o1, quasiquoteMakeList(tree->getBrother(), env)) );
	}
	return descend(obj);
}

void lex_output_visitor::visit(root const &r)
{
        out << "%{" << std::endl;
        out << "#include \"" << basename << "_cst.hpp\"" << std::endl;
        out << "#include \"" << basename << "_parse.hpp\"" << std::endl;
        out << "#define YY_USER_ACTION yylloc->first_line = yylloc->last_line = yylineno;" << std::endl;
        out << "%}" << std::endl;
        out << "" << std::endl;
        out << "%option nostdinit" << std::endl;
        out << "/*%option nodefault*/" << std::endl;
        out << "%option nounput" << std::endl;
        out << "%option noyywrap" << std::endl;
        out << "%option reentrant" << std::endl;
        out << "%option bison-bridge" << std::endl;
        out << "%option bison-locations" << std::endl;
        out << "%option yylineno" << std::endl;
        out << "%option prefix=\"" << basename << "_\"" << std::endl;
        out << "IDENT           [[:alpha:]_][[:alnum:]_]*" << std::endl;
        out << "" << std::endl;
        out << "%x COMMENT" << std::endl;
        out << "" << std::endl;
        out << "%%" << std::endl;
        out << "" << std::endl;
        out << "<INITIAL>\\/\\*   BEGIN(COMMENT);" << std::endl;
        out << "<COMMENT>\\*\\/   BEGIN(INITIAL);" << std::endl;
        out << "<COMMENT>.      /* ignore */" << std::endl;
        out << "" << std::endl;
        out << "\\               /* ignore */" << std::endl;
        out << "\\t              /* ignore */" << std::endl;
        out << "\\n              /* ignore */" << std::endl;
        descend(r.literals);
        descend(r.regexes);
}

void
typesetter_rep::insert_marker (tree st, path ip) {
  (void) st;
  // if (!is_multi_paragraph (st)) {
  array<line_item> a2= typeset_marker (env, descend (ip, 0));
  array<line_item> b2= typeset_marker (env, descend (ip, 1));
  insert_surround (a2, b2);
  // }
}

void
bridge_surround_rep::initialize () {
  while (N(st)<3) // hack for temporarily incorrect situations (A-backspace)
    st= tree (SURROUND, "") * st;
  if (is_nil (body)) body= make_bridge (ttt, st[2], descend (ip, 2));
  else replace_bridge (body, st[2], descend (ip, 2));
  changes_before= hashmap<string,tree> (UNINIT);
  corrupted= true;
}

void header_output_visitor::visit(root const &r)
{
        descend(r.includes);
        out << "#include <list>" << std::endl;
        state = fwddecl;
        descend(r.global_namespace);
        state = decl;
        descend(r.global_namespace);
}

void kd_tree::descend(int root){

  if(tree[root][1]>=0)descend(tree[root][1]);
  if(tree[root][2]>=0)descend(tree[root][2]);
  
  reassign(root);  
    

}

static void
sinitsearch(SemBlock *b)
{
    int i;

    if(bsadd(sinitvisit, b->idx)) return;
    b->phi = mkblock(descend(b->phi, nil, sinitblock));
    b->cont = mkblock(descend(b->cont, nil, sinitblock));
    for(i = 0; i < b->nfrom; i++)
        sinitsearch(b->from[i]);
}

/* copy blocks and create definitions for the primed values as needed */
static void
makenext(void)
{
    SemBlock *b, *c;
    BitSet *copy;
    int i, j, ch;

    copy = bsnew(nblocks);
    for(i = 0; i < nblocks; i++) {
        b = blocks[i];
        if(descendsum(b->phi, countnext) + descendsum(b->cont, countnext) > 0)
            bsadd(copy, i);
    }
    do {
        ch = 0;
        for(i = -1; i = bsiter(copy, i), i >= 0; ) {
            b = blocks[i];
            for(j = 0; j < b->nto; j++)
                ch += bsadd(copy, b->to[j]->idx) == 0;
            for(j = 0; j < b->nfrom; j++)
                ch += bsadd(copy, b->from[j]->idx) == 0;
        }
    } while(ch != 0);
    dupl = emalloc(nblocks * sizeof(SemBlock *));
    for(i = -1; i = bsiter(copy, i), i >= 0; )
        dupl[i] = newblock();
    for(i = -1; i = bsiter(copy, i), i >= 0; ) {
        b = blocks[i];
        c = dupl[i];
        c->nto = b->nto;
        c->to = emalloc(sizeof(SemBlock *) * c->nto);
        c->nfrom = b->nfrom;
        c->from = emalloc(sizeof(SemBlock *) * c->nfrom);
        for(j = 0; j < b->nto; j++) {
            c->to[j] = dupl[b->to[j]->idx];
            assert(c->to[j] != nil);
        }
        for(j = 0; j < b->nfrom; j++) {
            c->from[j] = dupl[b->from[j]->idx];
            assert(c->from[j] != nil);
        }
        c->phi = mkblock(descend(b->phi, nil, makenext1));
        c->cont = mkblock(descend(b->cont, nil, makenext1));
        c->jump = mkblock(descend(b->jump, nil, makenext1));
    }
    for(i = 0; i < nblocks; i++) {
        b = blocks[i];
        b->phi = mkblock(descend(b->phi, nil, deldefs));
        b->cont = mkblock(descend(b->cont, nil, deldefs));
    }
    bsfree(copy);
}

void kd_tree::descend(int root){
    /*
    For use when removing a node from the tree.
    
    Wander down the specified branch until you find a terminal node.
    Reassign that terminal node to the new tree.
    */
    
    if(tree.get_data(root,1)>=0)descend(tree.get_data(root,1));
    if(tree.get_data(root,2)>=0)descend(tree.get_data(root,2));
  
    reassign(root);  
    

}

bool
descend(nltype *node, arctype **stkstart, arctype **stkp)
{
    arctype	*arcp;
    bool	ret;

    for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
#	ifdef DEBUG
	    visited++;
#	endif /* DEBUG */
	if ( arcp -> arc_childp -> cycleno != node -> cycleno
	    || ( arcp -> arc_childp -> flags & VISITED )
	    || ( arcp -> arc_flags & DEADARC ) )
	    continue;
#	ifdef DEBUG
	    viable++;
#	endif /* DEBUG */
	*stkp = arcp;
	if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
	    if ( addcycle( stkstart , stkp ) == FALSE )
		return( FALSE );
	    continue;
	}
	arcp -> arc_childp -> flags |= VISITED;
	ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
	arcp -> arc_childp -> flags &= ~VISITED;
	if ( ret == FALSE )
	    return( FALSE );
    }
    return( TRUE );
}

ProcessResult process(const char *iso, const char *output)
{
	BlockDevice *blockDevice = constructBlockDevice(iso);
	if (!blockDevice)
		return RESULT_INPUT_READ_FAIL;

	std::ofstream out;
	out.open(output);

	if (!out)
	{
		delete blockDevice;
		return RESULT_OUTPUT_WRITE_FAIL;
	}

	VolDescriptor desc;
	blockDevice->ReadBlock(16, (u8*)&desc);

	if (memcmp(desc.cd001, "CD001", 5))
	{
		fprintf(stderr, "ERROR: Block 16 does not start with CD001.\n");
		delete blockDevice;
		return RESULT_INPUT_PARSE_FAIL;
	}

	u32 rootSector = desc.root.firstDataSectorLE;
	u32 rootSize = desc.root.dataLengthLE;

	descend(blockDevice, rootSector, rootSize, out, "");

	delete blockDevice;
	return RESULT_SUCCESS;
}

box
typeset_as_atomic (edit_env env, tree t, path ip) {
  if (is_func (t, WITH)) {
    int i, n= N(t), k= (n-1)>>1; // is k=0 allowed ?
    if ((n&1) != 1) return empty_box (ip);

    STACK_NEW_ARRAY(vars,string,k);
    STACK_NEW_ARRAY(oldv,tree,k);
    STACK_NEW_ARRAY(newv,tree,k);
    for (i=0; i<k; i++) {
      tree var_t= env->exec (t[i<<1]);
      if (is_atomic (var_t)) {
	string var= var_t->label;
	vars[i]= var;
	oldv[i]= env->read (var);
	newv[i]= env->exec (t[(i<<1)+1]);
      }
      else {
	STACK_DELETE_ARRAY(vars);
	STACK_DELETE_ARRAY(oldv);
	STACK_DELETE_ARRAY(newv);
	return empty_box (ip);
      }
    }

    // for (i=0; i<k; i++) env->monitored_write_update (vars[i], newv[i]);
    for (i=0; i<k; i++) env->write_update (vars[i], newv[i]);
    box b= typeset_as_atomic (env, t[n-1], descend (ip, n-1));
    for (i=k-1; i>=0; i--) env->write_update (vars[i], oldv[i]);
    STACK_DELETE_ARRAY(vars);
    STACK_DELETE_ARRAY(oldv);
    STACK_DELETE_ARRAY(newv);
    return b;
  }
  else if (is_func (t, LOCUS) && N(t) != 0) {

void
bridge_document_rep::notify_insert (path p, tree u) {
  //cout << "Insert " << p << ", " << u << " in " << st << "\n";
  ASSERT (!is_nil (p), "nil path");
  if (is_atom (p)) {
    int i, j, n= N(brs), pos= p->item, nr= N(u);
    array<bridge> brs2 (n+nr);
    if (pos>0) brs[pos-1]->notify_change (); // touch in case of surroundings
    if (pos<n) brs[pos  ]->notify_change (); // touch in case of surroundings
    for (i=0; i<pos; i++) brs2[i]= brs[i];
    for (j=0; j<nr ; j++) brs2[i+j]= make_bridge (ttt, u[j], descend (ip,i+j));
    for (; i<n; i++) {
      brs2[i+nr]= brs[i];
      brs2[i+nr]->ip->item += nr;
    }
    brs= brs2;
    st = (st (0, p->item) * u) * st (p->item, N(st));
    if (!is_nil (acc)) acc->notify_insert (p, u);
    // initialize_acc ();
  }
  else {
    brs[p->item]->notify_insert (p->next, u);
    st= substitute (st, p->item, brs[p->item]->st);
    if (!is_nil (acc)) acc->notify_assign (p->item, st[p->item]);
  }
  status= CORRUPTED;
}

Condition * Condition::parseCondition(const string& desc)
{
	const char * ptr = desc.c_str();
	const char * end = ptr + desc.size();

	return descend(0, ptr, end);
}

void
concater_rep::typeset_anim_repeat (tree t, path ip) {
  if (N(t) != 1) { typeset_error (t, ip); return; }
  player pl= get_player (env->get_animation_ip (ip));
  box b= typeset_as_concat (env, t[0], descend (ip, 0));
  print (anim_repeat_box (ip, b, pl));
}

/* t is not NULL, and may or may not have children.  ibuf holds
 * instructions for parent nodes through level-1.  For each of t's
 * children, determine whether to emit an instruction sequence here
 * (if the count of child is lower than the count of t) or to continue
 * descending.  Only emit once.
 */
void descend(trie_t *t, int level)
{
    trie_t *t2, *t3;

    for ( t2=t ; t2 != NULL ; t2 = t2->right_sibling) {
	int emitted = 0;

	ibuf[level] = t2->opcode;
	operand1[level] = t2->opd1;
	operand2[level] = t2->opd2;

	if (t2->left_child == NULL) {
	    emit(level+1, t2->count);
	    continue;
	}

	for ( t3=t2->left_child ; t3 != NULL ; t3 = t3->right_sibling ) {
	    if (t3->count < t2->count && !emitted) {
		emitted = 1;
		emit(level+1, t2->count);
	    }
	}

	descend(t2->left_child, level+1);
    }
}

void ControlSystem::update(Controls control)
{
  if (player_health_->is_dead) {
    return;
  }
  switch (control) {
  case UP:
  case DOWN:
  case LEFT:
  case RIGHT:
    move(control);
    break;
  case PICK_UP_ITEM:
    pickUpItem();
    break;
  case DESCEND:
    descend();
    break;
  case PAUSE_TURN:
    player_turn_->turn_taken = true;
    break;
  default:
    break;
  }
}

static inode_t*
resolve_path (inode_t* inode,
	      const char* path_begin,
	      const char* path_end)
{
  if (inode == 0) {
    return 0;
  }

  if (path_begin == 0) {
    return inode;
  }

  while (path_begin != path_end && inode != 0) {
    if (*path_begin == '/') {
      ++path_begin;
    }
    else {
      /* Find the separator. */
      const char* end = memchr (path_begin, '/', path_end - path_begin);
      if (end == 0) {
	end = path_end;
      }
      /* Found a separator. */
      inode = descend (inode, path_begin, end);
      path_begin = end;
    }
  }

  return inode;
}