# LOOK UP A SYMBOL IN THE TABLE USING THE "MOVE TO FRONT" METHOD.  The
# table is a vector held in the global variable sym.table.  The table is 
# modified by moving the symbol found to the front, while symbols before it 
# move back one to make room.  The value returned is the index of the symbol 
# in the table (before it was moved to the front), which is a rough indication 
# of how long it took to find it.
#
# This function will work for symbols that are either character strings or
# integers (and some other things as well).
#
# This function considers it to be an error if the symbol isn't in the table.
# If this happens, the program is terminated with an error message.  (This
# probably isn't what one would want to do in a real application.)

mtf.lookup <- function (s)
{
  # Find where in the table the symbol is found.

  i <- 1
  while (sym.table[i]!=s) 
  { i <- i + 1
    if (i>length(sym.table))
    { stop("The symbol being looked for isn't in the table!")
    }
  }

  # Move symbols before the one found forward one position, and then put
  # the symbol found at the front of the table.

  j <- i
  while (j>1)
  { sym.table[j] <<- sym.table[j-1]
    j <- j - 1
  }
  sym.table[1] <<- s

  # Return the position of the symbol before it was moved to the front. 

  i
}


# LOOK UP A SYMBOL IN THE TABLE USING THE "MOVE ONE FORWARD" METHOD.  The
# table is a vector held in the global variable sym.table.  The table is 
# modified by moving the symbol found one position forward in the table, 
# swapping with the symbol before it.  The value returned is the index of 
# the symbol in the table (before it was moved forward), which is a rough 
# indication of how long it took to find it.
#
# This function will work for symbols that are either character strings or
# integers (and some other things as well).
#
# This function considers it to be an error if the symbol isn't in the table.
# If this happens, the program is terminated with an error message.  (This
# probably isn't what one would want to do in a real application.)

m1f.lookup <- function (s)
{
  # Find where in the table the symbol is found.

  i <- 1
  while (sym.table[i]!=s) 
  { i <- i + 1
    if (i>length(sym.table))
    { stop("The symbol being looked for isn't in the table!")
    }
  }

  # Move the symbol found one position forward, if it's not already at the front

  if (i>1)
  { sym.table[i] <<- sym.table[i-1]
    sym.table[i-1] <<- s;
  }

  # Return the position of the symbol before it was moved forward.

  i
}


# SIMULATE A SEQUENCE OF LOOKUP OPERATIONS, USING A GIVEN METHOD.  The 
# arguments are the lookup function to use, the size of the table, the
# vector of symbol probabilities to use when choosing a new symbol to
# look up, the probability that the symbol looked up will be on of the
# last 10 symbols looked up, and the number of lookups to simulate.
# The value returned is a vector containing the position in which the
# symbol was found for each lookup operation.  The symbol table is
# initialized to a random permutation of the symbols.

simulate.lookups <- function (lookup, table.size, sym.probs, last10.prob, 
                              n.lookups)
{
  # Create the symbol table, with symbols in random order.

  sym.table <<- sample(1:table.size)

  # Create vectors holding the symbol looked for and the position in which it
  # was found, for each of the n.lookups lookup operations that will be done.

  sym.looked.for <- rep(0,n.lookups)
  sym.position <- rep(0,n.lookups)

  # Main loop.  Lookups up a symbol each time around.
  
  for (i in 1:n.lookups)
  { 
    # Pick a symbol to look up:  Either one drawn randomly from the last 10, 
    # or one drawn from the full set according to the specified probabilities.

    if (i>10 && runif(1)<last10.prob)
    { s <- sym.looked.for[i-sample(10,1)]
    }
    else
    { s <- sample(table.size,1,prob=sym.probs)
    }

    # Look up this symbol, and record it and the in which it was found in.

    sym.looked.for[i] <- s
    sym.position[i] <- lookup(s)
  }

  # Return the vector of positions where symbols were found.

  sym.position
}


# DO WHAT'S ASKED FOR IN THE ASSIGNMENT.  Does eight simulations for the
# eight combinations of method, distribution, and last10.prob, producing
# plots and means and standard deviations.

do.it <- function()
{
  # Set table.size and n.lookups to the desired values.

  table.size <- 100
  n.lookups <- 8000

  # Compute the probabilities for the two distributions being used.

  uniform <- rep(1/table.size,table.size)
  zipf <- (1/(1:table.size)) / sum(1/(1:table.size))

  # Divert plots to a postscript file.

  postscript("plots.ps")

  # Do the eight simulations, producing plots and means and standard deviations.

  res <- simulate.lookups (mtf.lookup, table.size, uniform, 0, n.lookups)
  plot (res, xlab="mtf, uniform, p=0")
  cat("mtf, uniform, p=0:", mean(res), sqrt(var(res)),
            mean(res[4001:8000]), sqrt(var(res[4001:8000])),"\n")

  res <- simulate.lookups (m1f.lookup, table.size, uniform, 0, n.lookups)
  plot (res, xlab="m1f, uniform, p=0")
  cat("m1f, uniform, p=0:", mean(res), sqrt(var(res)),
            mean(res[4001:8000]), sqrt(var(res[4001:8000])),"\n")

  res <- simulate.lookups (mtf.lookup, table.size, uniform, 0.5, n.lookups)
  plot (res, xlab="mtf, uniform, p=0.5")
  cat("mtf, uniform, p=0.5:", mean(res), sqrt(var(res)),
            mean(res[4001:8000]), sqrt(var(res[4001:8000])),"\n")

  res <- simulate.lookups (m1f.lookup, table.size, uniform, 0.5, n.lookups)
  plot (res, xlab="m1f, uniform, p=0.5")
  cat("m1f, uniform, p=0.5:", mean(res), sqrt(var(res)),
            mean(res[4001:8000]), sqrt(var(res[4001:8000])),"\n")

  res <- simulate.lookups (mtf.lookup, table.size, zipf, 0, n.lookups)
  plot (res, xlab="mtf, zipf, p=0")
  cat("mtf, zipf, p=0:", mean(res), sqrt(var(res)),
            mean(res[4001:8000]), sqrt(var(res[4001:8000])),"\n")

  res <- simulate.lookups (m1f.lookup, table.size, zipf, 0, n.lookups)
  plot (res, xlab="m1f, zipf, p=0")
  cat("m1f, zipf, p=0:", mean(res), sqrt(var(res)),
            mean(res[4001:8000]), sqrt(var(res[4001:8000])),"\n")

  res <- simulate.lookups (mtf.lookup, table.size, zipf, 0.5, n.lookups)
  plot (res, xlab="mtf, zipf, p=0.5")
  cat("mtf, zipf, p=0.5:", mean(res), sqrt(var(res)),
            mean(res[4001:8000]), sqrt(var(res[4001:8000])),"\n")

  res <- simulate.lookups (m1f.lookup, table.size, zipf, 0.5, n.lookups)
  plot (res, xlab="m1f, zipf, p=0.5")
  cat("m1f, zipf, p=0.5:", mean(res), sqrt(var(res)),
            mean(res[4001:8000]), sqrt(var(res[4001:8000])),"\n")

  # Close postscript file containing plots.

  dev.off()
}