/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 */

#include "engines/glk/glulxe/glulxe.h"

namespace Glk {
namespace Glulxe {

enum serop {
	serop_KeyIndirect       = 0x01,
	serop_ZeroKeyTerminates = 0x02,
	serop_ReturnIndex       = 0x04
};

uint Glulxe::linear_search(uint key, uint keysize,  uint start, uint structsize, uint numstructs, 
		uint keyoffset, uint options) {
  unsigned char keybuf[4];
  uint count;
  uint ix;
  int retindex = ((options & serop_ReturnIndex) != 0);
  int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);

  fetchkey(keybuf, key, keysize, options);

  for (count=0; count<numstructs; count++, start+=structsize) {
    int match = true;
    if (keysize <= 4) {
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != keybuf[ix])
          match = false;
      }
    }
    else {
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
          match = false;
      }
    }

    if (match) {
      if (retindex)
        return count;
      else
        return start;
    }

    if (zeroterm) {
      match = true;
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != 0)
          match = false;
      }
      if (match) {
        break;
      }
    }
  }
  
  if (retindex)
    return (uint)-1;
  else
    return 0;
}


uint Glulxe::binary_search(uint key, uint keysize,  uint start, uint structsize, uint numstructs, 
		uint keyoffset, uint options) {
  byte keybuf[4];
  byte byte1, byte2;
  uint top, bot, val, addr;
  uint ix;
  int retindex = ((options & serop_ReturnIndex) != 0);

  fetchkey(keybuf, key, keysize, options);
  
  bot = 0;
  top = numstructs;
  while (bot < top) {
    int cmp = 0;
    val = (top+bot) / 2;
    addr = start + val * structsize;

    if (keysize <= 4) {
      for (ix=0; (!cmp) && ix<keysize; ix++) {
        byte1 = Mem1(addr + keyoffset + ix);
        byte2 = keybuf[ix];
        if (byte1 < byte2)
          cmp = -1;
        else if (byte1 > byte2)
          cmp = 1;
      }
    }
    else {
      for (ix=0; (!cmp) && ix<keysize; ix++) {
        byte1 = Mem1(addr + keyoffset + ix);
        byte2 = Mem1(key + ix);
        if (byte1 < byte2)
          cmp = -1;
        else if (byte1 > byte2)
          cmp = 1;
      }
    }

    if (!cmp) {
      if (retindex)
        return val;
      else
        return addr;
    }

    if (cmp < 0) {
      bot = val+1;
    }
    else {
      top = val;
    }
  }

  if (retindex)
    return (uint)-1;
  else
    return 0;
}

uint Glulxe::linked_search(uint key, uint keysize,  uint start, uint keyoffset, uint nextoffset, uint options) {
  unsigned char keybuf[4];
  uint ix;
  uint val;
  int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);

  fetchkey(keybuf, key, keysize, options);

  while (start != 0) {
    int match = true;
    if (keysize <= 4) {
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != keybuf[ix])
          match = false;
      }
    }
    else {
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
          match = false;
      }
    }

    if (match) {
      return start;
    }

    if (zeroterm) {
      match = true;
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != 0)
          match = false;
      }
      if (match) {
        break;
      }
    }
    
    val = start + nextoffset;
    start = Mem4(val);
  }

  return 0;
}

void Glulxe::fetchkey(unsigned char *keybuf, uint key, uint keysize,  uint options) {
  uint ix;

  if (options & serop_KeyIndirect) {
    if (keysize <= 4) {
      for (ix=0; ix<keysize; ix++)
        keybuf[ix] = Mem1(key+ix);
    }
  }
  else {
    switch (keysize) {
    case 4:
      Write4(keybuf, key);
      break;
    case 2:
      Write2(keybuf, key);
      break;
    case 1:
      Write1(keybuf, key);
      break;
    default:
      fatal_error("Direct search key must hold one, two, or four bytes.");
    }
  }
}

} // End of namespace Glulxe
} // End of namespace Glk