dds-bridge-sys 2.1.1

/*
   DDS, a bridge double dummy solver.

   Copyright (C) 2006-2014 by Bo Haglund /
   2014-2018 by Bo Haglund & Soren Hein.

   See LICENSE and README.
*/

/*
   Explanation of full memory version:

   There are some constants that only need to be calculated
   once. In fact they are the same for all instances of the
   object. In order to save time and memory, they share a
   single memory.

   Each 13-bit number, aggr, represents a possible set of cards
   remaining in a suit. For example, 0x15a2 represents
   A(1) QT(5) 97(a) 3(2).

   TTlowestRank[aggr] gives the lowest relative rank that is in
   play in aggr. The ace is 14, the deuce is 2. A void counts as
   rank 15 ("not even the ace"). It would go horribly wrong
   if this rank were chosen to be 0, as might seem intuitive.
   This is not the same as lowestRank, the lowest absolute rank.

   maskBytes[aggr][suit] is a set of 4 32-bit integers,
   where suit is 0 ..3 (spades .. clubs). Each integer only
   has 8 of its 32 bits set, but these 8 bits could be either
   in the top byte (byte 0) or any of the others (bytes 1 ..3).
   The bytes are abbreviated as B0 .. B3 below.

                     int 0 int 1 int 2 int 3
   suit 0, spades B0 R0 B0 R1 B0 R2 B0 R3
   suit 1, hearts B1 R0 B1 R1 B1 R2 B1 R3
   suit 2, diamonds B2 R0 B2 R1 B2 R2 B2
   suit 3, clubs B3 R0 B3 R1 B3 R2 B3

   R0 .. R3 are explained now. The purpose of maskBytes is
   to generate 32-bit masks for later use with actual suits.
   As a card can be with either of 4 players, 2 bits are needed
   to encode the position of a card. Therefore the masks also
   need 2 bits per card, even though the 2 bits are identical.

   In the table, R0 means the top byte (8 bits = 4 cards) of
   a holding.

   R0 AKQJ
   R1 T987
   R2 6543
   R3 2

   For example, if the ace is held by North, the king by South, the
   queen and jack by West, then the top byte for that SUIT would be

   00(North) 10(South) 11(West) 11(West)

   The MASK for that holding would be 11 11 11 11, as all four
   cards are in play.

   If the jack were missing, because it had already been played,
   then the suit would be 00 10 11 00 (a missing card is also
   encoded as 00), and the mask would be 11 11 11 00.

   Later on, when we have a specific set of spades .. clubs,
   we want to check whether those cards are already in the
   transposition table. As far as the necessary masks is
   concerned, this is generated by an OR (|) of the four
   32-bit integers in a column of the table above.

   So the first column yields four bytes which are already
   shifted in place, all corresponding to R0. The mask
   corresponds to the AKQJ of the four suits in order.

   It's not really AKQJ, but the four highest cards still in
   play in that suit. So missing cards are always at the end
   of the list.
*/


#include <iomanip>
#include <sstream>
#include <math.h>

#include "TransTableL.h"
#include "debug.h"


extern unsigned char cardRank[16];
extern char relRank[8192][15];

static bool _constantsSet = false;
static int TTlowestRank[8192];
static unsigned maskBytes[8192][DDS_SUITS][TT_BYTES];

static vector<string> players =
{
  "North", "East", "South", "West"
};


TransTableL::TransTableL()
{
  if (! _constantsSet)
  {
    _constantsSet = true;
    TransTableL::SetConstants();
  }

  poolp = nullptr;
  pagesDefault = NUM_PAGES_DEFAULT;
  pagesMaximum = NUM_PAGES_MAXIMUM;
  pagesCurrent = 0;

  memState = FROM_POOL;
  harvestTrick = FIRST_HARVEST_TRICK;
  harvestHand = 0;

  harvested.nextBlockNo = 0;

  timestamp = 0;

  pageStats.numResets = 0;
  pageStats.numCallocs = 0;
  pageStats.numFrees = 0;
  pageStats.numHarvests = 0;
  pageStats.lastCurrent = 0;

  TTInUse = 0;
}


TransTableL::~TransTableL()
{
  TransTableL::ReturnAllMemory();
}


void TransTableL::SetConstants()
{
  unsigned int topBitRank = 1;
  TTlowestRank[0] = 15; // Void
  unsigned winMask[8192];
  winMask[0] = 0;

  for (unsigned ind = 1; ind < 8192; ind++)
  {
    if (ind >= (topBitRank + topBitRank)) /* Next top bit */
      topBitRank <<= 1;

    // winMask is a growing list of 11's. In the end it will
    // have 26 bits, so 13 groups of two bits. It always
    // consists of all 11's, then all 00's.

    winMask[ind] = (winMask[ind ^ topBitRank] >> 2) | (3 << 24);

    maskBytes[ind][0][0] = (winMask[ind] << 6) & 0xff000000;
    maskBytes[ind][0][1] = (winMask[ind] << 14) & 0xff000000;
    maskBytes[ind][0][2] = (winMask[ind] << 22) & 0xff000000;
    maskBytes[ind][0][3] = (winMask[ind] << 30) & 0xff000000;

    maskBytes[ind][1][0] = (winMask[ind] >> 2) & 0x00ff0000;
    maskBytes[ind][1][1] = (winMask[ind] << 6) & 0x00ff0000;
    maskBytes[ind][1][2] = (winMask[ind] << 14) & 0x00ff0000;
    maskBytes[ind][1][3] = (winMask[ind] << 22) & 0x00ff0000;

    maskBytes[ind][2][0] = (winMask[ind] >> 10) & 0x0000ff00;
    maskBytes[ind][2][1] = (winMask[ind] >> 2) & 0x0000ff00;
    maskBytes[ind][2][2] = (winMask[ind] << 6) & 0x0000ff00;
    maskBytes[ind][2][3] = (winMask[ind] << 14) & 0x0000ff00;

    maskBytes[ind][3][0] = (winMask[ind] >> 18) & 0x000000ff;
    maskBytes[ind][3][1] = (winMask[ind] >> 10) & 0x000000ff;
    maskBytes[ind][3][2] = (winMask[ind] >> 2) & 0x000000ff;
    maskBytes[ind][3][3] = (winMask[ind] << 6) & 0x000000ff;

    TTlowestRank[ind] = TTlowestRank[ind ^ topBitRank] - 1;
  }
}


void TransTableL::Init(const int handLookup[][15])
{
  // This is very similar to SetConstants, except that it
  // happens with actual cards. It also makes sense to
  // keep a record of aggrRanks for each suit. These are
  // only used later for xorSet.

  unsigned int topBitRank = 1;
  unsigned int topBitNo = 2;
  aggrType * ap;

  for (int s = 0; s < DDS_SUITS; s++)
  {
    aggr[0].aggrRanks[s] = 0;
    aggr[0].aggrBytes[s][0] = 0;
    aggr[0].aggrBytes[s][1] = 0;
    aggr[0].aggrBytes[s][2] = 0;
    aggr[0].aggrBytes[s][3] = 0;
  }

  for (unsigned ind = 1; ind < 8192; ind++)
  {
    if (ind >= (topBitRank << 1))
    {
      /* Next top bit */
      topBitRank <<= 1;
      topBitNo++;
    }

    aggr[ind] = aggr[ind ^ topBitRank];
    ap = &aggr[ind];

    for (int s = 0; s < DDS_SUITS; s++)
    {
      ap->aggrRanks[s] = ap->aggrRanks[s] >> 2 |
                          static_cast<unsigned>(handLookup[s][topBitNo] << 24);
    }

    ap->aggrBytes[0][0] = (ap->aggrRanks[0] << 6) & 0xff000000;
    ap->aggrBytes[0][1] = (ap->aggrRanks[0] << 14) & 0xff000000;
    ap->aggrBytes[0][2] = (ap->aggrRanks[0] << 22) & 0xff000000;
    ap->aggrBytes[0][3] = (ap->aggrRanks[0] << 30) & 0xff000000;

    ap->aggrBytes[1][0] = (ap->aggrRanks[1] >> 2) & 0x00ff0000;
    ap->aggrBytes[1][1] = (ap->aggrRanks[1] << 6) & 0x00ff0000;
    ap->aggrBytes[1][2] = (ap->aggrRanks[1] << 14) & 0x00ff0000;
    ap->aggrBytes[1][3] = (ap->aggrRanks[1] << 22) & 0x00ff0000;

    ap->aggrBytes[2][0] = (ap->aggrRanks[2] >> 10) & 0x0000ff00;
    ap->aggrBytes[2][1] = (ap->aggrRanks[2] >> 2) & 0x0000ff00;
    ap->aggrBytes[2][2] = (ap->aggrRanks[2] << 6) & 0x0000ff00;
    ap->aggrBytes[2][3] = (ap->aggrRanks[2] << 14) & 0x0000ff00;

    ap->aggrBytes[3][0] = (ap->aggrRanks[3] >> 18) & 0x000000ff;
    ap->aggrBytes[3][1] = (ap->aggrRanks[3] >> 10) & 0x000000ff;
    ap->aggrBytes[3][2] = (ap->aggrRanks[3] >> 2) & 0x000000ff;
    ap->aggrBytes[3][3] = (ap->aggrRanks[3] << 6) & 0x000000ff;
  }
}


void TransTableL::SetMemoryDefault(int megabytes)
{
  double blockMem = BLOCKS_PER_PAGE * sizeof(winBlockType) /
                    static_cast<double>(1024.);

  pagesDefault = static_cast<int>((1024 * megabytes) / blockMem);
}


void TransTableL::SetMemoryMaximum(int megabytes)
{
  double blockMem = BLOCKS_PER_PAGE * sizeof(winBlockType) /
                    static_cast<double>(1024.);

  pagesMaximum = static_cast<int>((1024 * megabytes) / blockMem);
}


/////////////////////////////////////////////////////////////
//                                                         //
// Full memory TT functions.                               //
//                                                         //
/////////////////////////////////////////////////////////////

void TransTableL::MakeTT()
{
  if (! TTInUse)
  {
    TTInUse = 1;

    for (int t = 0; t < TT_TRICKS; t++)
    {
      for (int h = 0; h < DDS_HANDS; h++)
      {
        TTroot[t][h] = static_cast<distHashType *>
                       (malloc(256 * sizeof(distHashType)));

        if (TTroot[t][h] == nullptr)
          exit(1);
      }
    }
  }

  TransTableL::InitTT();
}


void TransTableL::InitTT()
{
  for (int c = 0; c < TT_TRICKS; c++)
  {
    for (int h = 0; h < DDS_HANDS; h++)
    {
      for (int i = 0; i < 256; i++)
      {
        TTroot[c][h][i].nextNo = 0;
        TTroot[c][h][i].nextWriteNo = 0;

      }
      lastBlockSeen[c][h] = nullptr;
    }
  }
}


void TransTableL::ReleaseTT()
{
  if (! TTInUse)
    return;
  TTInUse = 0;

  for (int t = 0; t < TT_TRICKS; t++)
  {
    for (int h = 0; h < DDS_HANDS; h++)
    {
      if (TTroot[t][h] == nullptr)
        continue;

      free(TTroot[t][h]);
    }
  }
}


void TransTableL::ResetMemory(const TTresetReason reason)
{
  UNUSED(reason);
  if (poolp == nullptr)
    return;

  pageStats.numResets++;
  pageStats.numCallocs += pagesCurrent - pageStats.lastCurrent;
  pageStats.lastCurrent = pagesCurrent;

  while (pagesCurrent > pagesDefault)
  {
    free(poolp->list);
    poolp = poolp->prev;

    free(poolp->next);
    poolp->next = nullptr;

    pagesCurrent--;
  }

  pageStats.numFrees += pageStats.lastCurrent - pagesCurrent;
  pageStats.lastCurrent = pagesCurrent;

  while (poolp->prev)
    poolp = poolp->prev;

  poolp->nextBlockNo = 0;
  nextBlockp = poolp->list;

  TransTableL::InitTT();

  timestamp = 0;

  memState = FROM_POOL;

  return;
}


void TransTableL::ReturnAllMemory()
{
  poolType * tmp;

  if (poolp)
  {
    while (poolp->next)
      poolp = poolp->next;

    while (poolp)
    {
      free(poolp->list);
      tmp = poolp;
      poolp = poolp->prev;
      free(tmp);
    }
  }

  pagesCurrent = 0;

  pageStats.numResets = 0;
  pageStats.numCallocs = 0;
  pageStats.numFrees = 0;
  pageStats.numHarvests = 0;
  pageStats.lastCurrent = 0;

  TransTableL::ReleaseTT();

  return;
}


int TransTableL::BlocksInUse() const
{
  poolType * pp = poolp;
  int count = 0;

  do
  {
    count += pp->nextBlockNo;
    pp = pp->prev;
  }
  while (pp);

  return count;
}


double TransTableL::MemoryInUse() const
{
  int blockMem = BLOCKS_PER_PAGE * pagesCurrent *
                 static_cast<int>(sizeof(winBlockType));
  int aggrMem = 8192 * static_cast<int>(sizeof(aggrType));
  int rootMem = TT_TRICKS * DDS_HANDS * 256 *
                 static_cast<int>(sizeof(distHashType));

  return (blockMem + aggrMem + rootMem) / static_cast<double>(1024.);
}


TransTableL::winBlockType * TransTableL::GetNextCardBlock()
{
  /*
     Spaghetti code. The basic idea is that there is a pool of
     pages. When a page runs out, we get a next pool. But we're
     only allowed a certain maximum number, and calloc might also
     fail before then. We have a default number of pages that
     we don't give back voluntarily once we have acquired them,
     but we give back anything more than that at the end of each
     hand. If this overall mechanism fails, then we try to harvest
     old entries scattered throughout the TT memory. If we get
     enough for a "page", then we use that single page, and if
     that runs out later, we try to harvest some more, starting
     where we left off harvesting last time. If the harvesting also
     fails, then we reset whatever TT memory we do have, and we
     continue with that.
  */

  if (poolp == nullptr)
  {
    // Have to be able to get at least one pool.
    poolp = static_cast<poolType *>(calloc(1, sizeof(poolType)));
    if (poolp == nullptr)
      exit(1);

    poolp->list = static_cast<winBlockType *>
                  (malloc(BLOCKS_PER_PAGE * sizeof(winBlockType)));

    if (! poolp->list)
      exit(1);

    poolp->next = nullptr;
    poolp->prev = nullptr;
    poolp->nextBlockNo = 1;

    nextBlockp = poolp->list;

    pagesCurrent++;

    return nextBlockp++;
  }
  else if (memState == FROM_HARVEST)
  {
    // Not allowed to get more memory, so reuse old one.
    int n = harvested.nextBlockNo;
    if (n == BLOCKS_PER_PAGE)
    {
      if (! TransTableL::Harvest())
      {
        TransTableL::ResetMemory(TT_RESET_UNKNOWN);
        poolp->nextBlockNo++;
        return nextBlockp++;
      }
      n = 0;
    }

    harvested.nextBlockNo++;
    return harvested.list[n];
  }
  else if (poolp->nextBlockNo == BLOCKS_PER_PAGE)
  {
    if (poolp->next)
    {
      // Reuse a dormant block that has not been freed.
      poolp = poolp->next;
      poolp->nextBlockNo = 1;
      nextBlockp = poolp->list;

      return nextBlockp++;
    }
    else if (pagesCurrent == pagesMaximum)
    {
      // Have to try to reclaim memory.
      if (! TransTableL::Harvest())
      {
        TransTableL::ResetMemory(TT_RESET_UNKNOWN);
        poolp->nextBlockNo++;
        return nextBlockp++;
      }

      memState = FROM_HARVEST;
      harvested.nextBlockNo++;
      return harvested.list[0];
    }
    else
    {
      // Make a new pool.
      poolType * newpoolp = static_cast<poolType *>
        (calloc(1, sizeof(poolType)));

      if (newpoolp == nullptr)
      {
        // Unexpected, but try harvesting before we give up
        // and start over.
        if (! TransTableL::Harvest())
        {
          TransTableL::ResetMemory(TT_RESET_UNKNOWN);
          poolp->nextBlockNo++;
          return nextBlockp++;
        }

        memState = FROM_HARVEST;
        harvested.nextBlockNo++;
        return harvested.list[0];
      }

      newpoolp->list = static_cast<winBlockType *>
        (malloc(BLOCKS_PER_PAGE * sizeof(winBlockType)));

      if (! newpoolp->list)
      {
        if (! TransTableL::Harvest())
        {
          TransTableL::ResetMemory(TT_RESET_UNKNOWN);
          poolp->nextBlockNo++;
          return nextBlockp++;
        }

        memState = FROM_HARVEST;
        harvested.nextBlockNo++;
        return harvested.list[0];
      }

      newpoolp->nextBlockNo = 1;
      newpoolp->next = nullptr;
      newpoolp->prev = poolp;

      poolp->next = newpoolp;
      poolp = newpoolp;

      nextBlockp = newpoolp->list;

      pagesCurrent++;

      return nextBlockp++;
    }
  }

  poolp->nextBlockNo++;
  return nextBlockp++;
}


bool TransTableL::Harvest()
{
  distHashType * rootptr = TTroot[harvestTrick][harvestHand];
  distHashType * ptr;
  winBlockType * bp;

  int trick = harvestTrick;
  int hand = harvestHand;
  int hash, suit, hno = 0;

  while (1)
  {
    for (hash = 0; hash < 256; hash++)
    {
      ptr = &rootptr[hash];
      for (suit = ptr->nextNo - 1; suit >= 0; suit--)
      {
        bp = ptr->list[suit].posBlock;
        if (timestamp - bp->timestampRead > HARVEST_AGE)
        {
          bp->nextMatchNo = 0;
          bp->nextWriteNo = 0;
          bp->timestampRead = timestamp;
          harvested.list[hno] = bp;

          // Swap the last element down.
          if (suit != ptr->nextNo - 1)
            ptr->list[suit] = ptr->list[ ptr->nextNo - 1 ];

          ptr->nextNo--;
          ptr->nextWriteNo = ptr->nextNo;

          if (++hno == BLOCKS_PER_PAGE)
          {
            if (++harvestHand >= DDS_HANDS)
            {
              // Skip rest of this [trick][hand] for simplicity.
              harvestHand = 0;
              if (--harvestTrick < 0)
                harvestTrick = FIRST_HARVEST_TRICK;
            }

            harvested.nextBlockNo = 0;
            pageStats.numHarvests++;
            return true;
          }
        }
      }
    }

    if (++harvestHand >= DDS_HANDS)
    {
      harvestHand = 0;
      if (--harvestTrick < 0)
        harvestTrick = FIRST_HARVEST_TRICK;
    }

    if (harvestTrick == trick && harvestHand == hand)
      return false;

    rootptr = TTroot[harvestTrick][harvestHand];
  }
}


int TransTableL::hash8(const int handDist[]) const
{
  /*
     handDist is an array of hand distributions, North .. West.
     Each entry is a 12-bit number with 3 groups of 4 bits.
     Each group is the binary representation of the number of
     cards held in that suit. The suits are in order spades,
     hearts, diamonds. Clubs can be neglected, as the total
     number of cards in a hand is given by the trick number.

     For example, if handDist[1] equals 0x0433, then East holds
     4 spades, 3 hearts, 3 diamonds and the rest in clubs.
     If this is after the second trick, there are 11 cards, so
     East must hold 1 club.

     The hash function turns all 4 hand distributions into a
     single 8-bit number. The numbers should be spread as
     evenly as possible across the 256 possibilities. I've not
     done extensive research into finding the best hash function,
     but this one seems OK. It uses a small prime, 5, and its
     powers. The shift at the end is in order to get some use
     out of the bits above the first 8 ones.
  */

  int h =
    (handDist[0] ^
     ((handDist[1] * 5) ) ^
     ((handDist[2] * 25) ) ^
     ((handDist[3] * 125) ) );

  return (h ^ (h >> 5)) & 0xff;
}


nodeCardsType * TransTableL::Lookup(
  const int tricks,
  const int hand,
  const unsigned short aggrTarget[],
  const int handDist[],
  const int limit,
  bool& lowerFlag)
{
  // First look up distribution.
  long long suitLengths =
    (static_cast<long long>(handDist[0]) << 36) |
    (static_cast<long long>(handDist[1]) << 24) |
    (static_cast<long long>(handDist[2]) << 12) |
    (static_cast<long long>(handDist[3]) );

  int hashkey = hash8(handDist);

  bool empty;
  lastBlockSeen[tricks][hand] =
    LookupSuit(&TTroot[tricks][hand][hashkey], suitLengths, empty);
  if (empty)
    return nullptr;

  // If that worked, look up cards.
  unsigned * ab0 = aggr[ aggrTarget[0] ].aggrBytes[0];
  unsigned * ab1 = aggr[ aggrTarget[1] ].aggrBytes[1];
  unsigned * ab2 = aggr[ aggrTarget[2] ].aggrBytes[2];
  unsigned * ab3 = aggr[ aggrTarget[3] ].aggrBytes[3];

  winMatchType TTentry;
  TTentry.topSet1 = ab0[0] | ab1[0] | ab2[0] | ab3[0];
  TTentry.topSet2 = ab0[1] | ab1[1] | ab2[1] | ab3[1];
  TTentry.topSet3 = ab0[2] | ab1[2] | ab2[2] | ab3[2];
  TTentry.topSet4 = ab0[3] | ab1[3] | ab2[3] | ab3[3];

  return TransTableL::LookupCards(TTentry,
    lastBlockSeen[tricks][hand], limit, lowerFlag);
}


TransTableL::winBlockType * TransTableL::LookupSuit(
  distHashType * dp,
  const long long key,
  bool& empty)
{
  /*
     Always returns a valid winBlockType.
     If empty == true, there was no match, so there is
     no point in looking for a card match.
     If empty == false, there were entries already.
  */

  int n = dp->nextNo;
  for (int i = 0; i < n; i++)
  {
    if (dp->list[i].key == key)
    {
      empty = false;
      return dp->list[i].posBlock;
    }
  }

  empty = true;
  int m;

  if (n == DISTS_PER_ENTRY)
  {
    // No room for new exact suits at this hash position.
    // Have to reuse an existing posBlock.
    if (dp->nextWriteNo == DISTS_PER_ENTRY)
    {
      m = 0;
      dp->nextWriteNo = 1;
    }
    else
      m = dp->nextWriteNo++;
  }
  else
  {
    // Didn't find an exact match, but there is still room.
    // The following looks a bit odd because it is possible that
    // GetNextCardBlock wipes out the whole memory, so we
    // have to use the up-to-date location, not m from above.

    winBlockType * bp = GetNextCardBlock();
    m = dp->nextWriteNo++;
    dp->list[m].posBlock = bp;
    dp->list[m].posBlock->timestampRead = timestamp;
    dp->nextNo++;
  }

  // As long as the secondary Lookup loop in ABsearch exists,
  // it will cause spurious extra blocks to be created here
  // which are not useful, because nothing is ever Add'ed.
  // This is not a memory leak, as the memory is properly freed,
  // but it is also a small waste of about 0.5%. I don't mind.

  dp->list[m].key = key;
  dp->list[m].posBlock->nextMatchNo = 0;
  dp->list[m].posBlock->nextWriteNo = 0;

  return dp->list[m].posBlock;
}


nodeCardsType * TransTableL::LookupCards(
  const winMatchType& search,
  winBlockType * bp,
  const int limit,
  bool& lowerFlag)
{
  const int n = bp->nextWriteNo - 1;
  winMatchType * wp = &bp->list[n];

  // It may be a bit silly to duplicate the code like this.
  // It could be combined to one loop with a slight overhead.

  for (int i = n; i >= 0; i--, wp--)
  {
    if ((wp->topSet1 ^ search.topSet1) & wp->topMask1)
      continue;

    if (wp->lastMaskNo != 1)
    {
      if ((wp->topSet2 ^ search.topSet2) & wp->topMask2)
        continue;

      if (wp->lastMaskNo != 2)
      {
        if ((wp->topSet3 ^ search.topSet3) & wp->topMask3)
          continue;
      }
    }

    // Check bounds.
    nodeCardsType * nodep = &wp->first;
    if (nodep->lbound > limit)
    {
      bp->timestampRead = ++timestamp;
      lowerFlag = true;
      return nodep;
    }
    else if (nodep->ubound <= limit)
    {
      bp->timestampRead = ++timestamp;
      lowerFlag = false;
      return nodep;
    }
  }

  const int n2 = bp->nextMatchNo - 1;
  wp = &bp->list[n2];

  for (int i = n2; i > n; i--, wp--)
  {
    if ((wp->topSet1 ^ search.topSet1) & wp->topMask1)
      continue;

    if (wp->lastMaskNo != 1)
    {
      if ((wp->topSet2 ^ search.topSet2) & wp->topMask2)
        continue;

      if (wp->lastMaskNo != 2)
      {
        if ((wp->topSet3 ^ search.topSet3) & wp->topMask3)
          continue;
      }
    }

    nodeCardsType * nodep = &wp->first;
    if (nodep->lbound > limit)
    {
      lowerFlag = true;
      bp->timestampRead = ++timestamp;
      return nodep;
    }
    else if (nodep->ubound <= limit)
    {
      lowerFlag = false;
      bp->timestampRead = ++timestamp;
      return nodep;
    }
  }

  return nullptr;
}


void TransTableL::CreateOrUpdate(
  winBlockType * bp,
  const winMatchType& search,
  const bool flag)
{
  // Either updates an existing SOP or creates a new one.
  // A new one is created at the end of the bp list if this
  // is not already full, or the oldest one in the list is
  // overwritten.

  winMatchType * wp = bp->list;
  int n = bp->nextMatchNo;

  for (int i = 0; i < n; i++, wp++)
  {
    if (wp->xorSet != search.xorSet ) continue;
    if (wp->maskIndex != search.maskIndex) continue;
    if (wp->topSet1 != search.topSet1 ) continue;
    if (wp->topSet2 != search.topSet2 ) continue;
    if (wp->topSet3 != search.topSet3 ) continue;

    nodeCardsType& node = wp->first;
    if (search.first.lbound > node.lbound)
      node.lbound = search.first.lbound;
    if (search.first.ubound < node.ubound)
      node.ubound = search.first.ubound;

    node.bestMoveSuit = search.first.bestMoveSuit;
    node.bestMoveRank = search.first.bestMoveRank;
    return;
  }

  if (n == BLOCKS_PER_ENTRY)
  {
    if (bp->nextWriteNo >= BLOCKS_PER_ENTRY)
      bp->nextWriteNo = 0;
  }
  else
    bp->nextMatchNo++;


  wp = &bp->list[ bp->nextWriteNo++ ];
  *wp = search;

  if (!flag)
  {
    wp->first.bestMoveSuit = 0;
    wp->first.bestMoveRank = 0;
  }
}


void TransTableL::Add(
  const int tricks,
  const int hand,
  const unsigned short aggrTarget[],
  const unsigned short ourWinRanks[],
  const nodeCardsType& first,
  const bool flag)
{
  if (lastBlockSeen[tricks][hand] == nullptr)
  {
    // We have recently reset the entire memory, and we were
    // in the middle of a recursion. So we'll just have to
    // drop this entry that we were supposed to be adding.
    return;
  }

  unsigned * ab[DDS_SUITS];
  unsigned * mb[DDS_SUITS];
  char low[DDS_SUITS];
  unsigned short int ag;
  int w;
  winMatchType TTentry;

  // Inefficient, as it also copies leastWin.
  // In fact I'm not quite happy with the treatment of
  // leastWin in general.

  TTentry.first = first;

  TTentry.xorSet = 0;

  for (int ss = 0; ss < DDS_SUITS; ss++)
  {
    w = static_cast<int>(ourWinRanks[ss]);
    if (w == 0)
    {
      ab[ss] = aggr[0].aggrBytes[ss];
      mb[ss] = maskBytes[0][ss];
      low[ss] = 15;
      TTentry.first.leastWin[ss] = 0;
    }
    else
    {
      w = w & (-w); /* Only lowest win */
      ag = static_cast<unsigned short>(aggrTarget[ss] & (-w));

      ab[ss] = aggr[ag].aggrBytes[ss];
      mb[ss] = maskBytes[ag][ss];
      low[ss] = static_cast<char>(TTlowestRank[ag]);

      TTentry.first.leastWin[ss] = 15 - low[ss];
      TTentry.xorSet ^= aggr[ag].aggrRanks[ss];
    }
  }

  // It's a bit annoying that we may be regenerating these.
  // But winRanks can cause them to change after lookup().

  TTentry.topSet1 = ab[0][0] | ab[1][0] | ab[2][0] | ab[3][0];
  TTentry.topSet2 = ab[0][1] | ab[1][1] | ab[2][1] | ab[3][1];
  TTentry.topSet3 = ab[0][2] | ab[1][2] | ab[2][2] | ab[3][2];
  TTentry.topSet4 = ab[0][3] | ab[1][3] | ab[2][3] | ab[3][3];

  TTentry.topMask1 = mb[0][0] | mb[1][0] | mb[2][0] | mb[3][0];
  TTentry.topMask2 = mb[0][1] | mb[1][1] | mb[2][1] | mb[3][1];
  TTentry.topMask3 = mb[0][2] | mb[1][2] | mb[2][2] | mb[3][2];
  TTentry.topMask4 = mb[0][3] | mb[1][3] | mb[2][3] | mb[3][3];

  TTentry.maskIndex =
    (low[0] << 12) | (low[1] << 8) | (low[2] << 4) | low[3];

  if (TTentry.topMask2 == 0)
    TTentry.lastMaskNo = 1;
  else if (TTentry.topMask3 == 0)
    TTentry.lastMaskNo = 2;
  else if (TTentry.topMask4 == 0)
    TTentry.lastMaskNo = 3;
  else
    TTentry.lastMaskNo = 4;

  TransTableL::CreateOrUpdate(lastBlockSeen[tricks][hand],
    TTentry, flag);
}


void TransTableL::PrintMatch(
  ofstream& fout,
  const winMatchType& wp,
  const unsigned char lengths[DDS_HANDS][DDS_SUITS]) const
{
  vector<vector<string>> hands;
  hands.resize(DDS_HANDS);
  for (unsigned i = 0; i < DDS_HANDS; i++)
    hands[i].resize(DDS_SUITS);

  TransTableL::SetToPartialHands(wp.topSet1, wp.topMask1, 14, 4, hands);
  TransTableL::SetToPartialHands(wp.topSet2, wp.topMask2, 10, 4, hands);
  TransTableL::SetToPartialHands(wp.topSet3, wp.topMask3, 6, 4, hands);
  TransTableL::SetToPartialHands(wp.topSet4, wp.topMask4, 2, 1, hands);

  TransTableL::DumpHands(fout, hands, lengths);

  TransTableL::PrintNodeValues(fout, wp.first);
}


void TransTableL::PrintNodeValues(
  ofstream& fout,
  const nodeCardsType& np) const
{
  fout << setw(16) << left << "Lowest used" <<
    cardSuit[0] << cardRank[15-static_cast<int>(np.leastWin[0])] << ", " <<
    cardSuit[1] << cardRank[15-static_cast<int>(np.leastWin[1])] << ", " <<
    cardSuit[2] << cardRank[15-static_cast<int>(np.leastWin[2])] << ", " <<
    cardSuit[3] << cardRank[15-static_cast<int>(np.leastWin[3])] << "\n";

  fout << setw(16) << left << "Bounds" << 
    to_string(static_cast<int>(np.lbound)) << " to " <<
    to_string(static_cast<int>(np.ubound)) << " tricks\n";

  fout << setw(16) << left << "Best move" <<
    cardSuit[ static_cast<int>(np.bestMoveSuit) ] <<
    cardRank[ static_cast<int>(np.bestMoveRank) ] << "\n\n";
}


string TransTableL::MakeHolding(
  const string& high,
  const unsigned len) const
{
  const size_t l = high.size();
  if (l == 0)
    return "-";
  else if (l == len)
    return high;
  else
    return high.substr(0, l) + string(len-l, 'x');
}


void TransTableL::DumpHands(
  ofstream& fout,
  const vector<vector<string>>& hands,
  const unsigned char lengths[][DDS_SUITS]) const
{
  for (unsigned i = 0; i < DDS_SUITS; i++)
  {
    fout << setw(16) << "" << 
      TransTableL::MakeHolding(hands[0][i], lengths[0][i]) << "\n";
  }

  for (unsigned i = 0; i < DDS_SUITS; i++)
  {
    fout << setw(16) << left << 
      TransTableL::MakeHolding(hands[3][i], lengths[3][i]) <<
      setw(16) << "" <<
      setw(16) << 
        TransTableL::MakeHolding(hands[1][i], lengths[1][i]) << "\n";
  }

  for (unsigned i = 0; i < DDS_SUITS; i++)
  {
    fout << setw(16) << "" <<
      TransTableL::MakeHolding(hands[2][i], lengths[2][i]) << "\n";
  }
  fout << "\n";
}


void TransTableL::SetToPartialHands(
  const unsigned set,
  const unsigned mask,
  const int maxRank,
  const int numRanks,
  vector<vector<string>>& hands) const
{
  for (unsigned s = 0; s < DDS_SUITS; s++)
  {
    for (int rank = maxRank; rank > maxRank - numRanks; rank--)
    {
      int shift = 8 * static_cast<int>(3 - s) + 2 * (rank - maxRank + 3);
      unsigned maskCard = mask >> shift;

      if (maskCard & 3)
      {
        unsigned player = (set >> shift) & 3;
        hands[player][s] += static_cast<char>(cardRank[rank]);
      }
    }
  }
}


void TransTableL::KeyToDist(
  const long long key,
  int handDist[]) const
{
  handDist[0] = static_cast<int>((key >> 36) & 0x00000fff);
  handDist[1] = static_cast<int>((key >> 24) & 0x00000fff);
  handDist[2] = static_cast<int>((key >> 12) & 0x00000fff);
  handDist[3] = static_cast<int>((key ) & 0x00000fff);
}


void TransTableL::DistToLengths(
  const int trick,
  const int handDist[],
  unsigned char lengths[DDS_HANDS][DDS_SUITS]) const
{
  for (int h = 0; h < DDS_HANDS; h++)
  {
    lengths[h][0] = static_cast<unsigned char>((handDist[h] >> 8) & 0xf);
    lengths[h][1] = static_cast<unsigned char>((handDist[h] >> 4) & 0xf);
    lengths[h][2] = static_cast<unsigned char>((handDist[h] ) & 0xf);
    lengths[h][3] = static_cast<unsigned char>
      (trick + 1 - lengths[h][0] - lengths[h][1] - lengths[h][2]);
  }
}


string TransTableL::SingleLenToStr(const unsigned char len[]) const
{
  return to_string(static_cast<unsigned>(len[0])) + "=" + 
         to_string(static_cast<unsigned>(len[1])) + "=" +
         to_string(static_cast<unsigned>(len[2])) + "=" + 
         to_string(static_cast<unsigned>(len[3]));
}


string TransTableL::LenToStr(
  const unsigned char len[DDS_HANDS][DDS_SUITS]) const
{
  return TransTableL::SingleLenToStr(len[0]) + " " +
         TransTableL::SingleLenToStr(len[1]) + " " +
         TransTableL::SingleLenToStr(len[2]) + " " +
         TransTableL::SingleLenToStr(len[3]);
}


void TransTableL::PrintSuits(
  ofstream& fout,
  const int trick,
  const int hand) const
{
  distHashType * dp;
  int handDist[DDS_HANDS];
  unsigned char len[DDS_HANDS][DDS_SUITS];

  fout << setw(4) << left << "Key" <<
    setw(3) << right << "No" <<
    setw(8) << right << players[0] <<
    setw(8) << players[1] <<
    setw(8) << players[2] <<
    setw(8) << players[3] << "\n";

  for (int hashkey = 0; hashkey < 256; hashkey++)
  {
    dp = &TTroot[trick][hand][hashkey];
    if (dp->nextNo == 0)
      continue;

    for (int i = 0; i < dp->nextNo; i++)
    {
      if (i == 0)
        fout << "0x" << setw(2) << hex << hashkey <<
          setw(3) << right << dec << dp->nextNo << " ";
      else
        fout << setw(8) << "";

      TransTableL::KeyToDist(dp->list[i].key, handDist);
      TransTableL::DistToLengths(trick, handDist, len);

      fout << TransTableL::LenToStr(len) << "\n";
    }
  }
  fout << "\n";
}


void TransTableL::PrintAllSuits(ofstream& fout) const
{
  for (int trick = 11; trick >= 1; trick--)
  {
    for (int hand = 0; hand < DDS_HANDS; hand++)
    {
      fout << "Trick " << trick << ", hand " << 
        players[static_cast<unsigned>(hand)] << "\n";
      fout << string(20, '=') << "\n\n";

      TransTableL::PrintSuits(fout, trick, hand);
    }
  }
}


void TransTableL::MakeHistStats(
  const int hist[],
  int& count,
  int& prod_sum,
  int& prod_sumsq,
  int& max_len,
  const int last_index) const
{
  count = 0;
  prod_sum = 0;
  prod_sumsq = 0;
  max_len = 0;

  for (int i = 1; i <= last_index; i++)
  {
    if (hist[i])
    {
      prod_sum += i * hist[i];
      prod_sumsq += i * i * hist[i];
      count += hist[i];

      if (i > max_len)
        max_len = i;
    }
  }
}


int TransTableL::CalcPercentile(
  const int hist[],
  const double threshold,
  const int last_index) const
{
  int cum = 0;

  for (int i = 1; i <= last_index; i++)
  {
    cum += hist[i];
    if (cum >= threshold)
      return i;
  }
  return -1;
}


void TransTableL::PrintHist(
  ofstream& fout,
  const int hist[],
  const int num_wraps,
  const int last_index) const
{
  int count, prod_sum, prod_sumsq, max_len;

  TransTableL::MakeHistStats(hist,
    count, prod_sum, prod_sumsq, max_len, last_index);

  for (int i = 1; i <= last_index; i++)
    if (hist[i])
      fout << setw(7) << right << i << 
        setw(6) << right << hist[i] << "\n";

  fout << "\n";
  fout << setw(7) << left << "Entries" <<
    setw(6) << right << count << "\n";

  if (count > 1)
  {
    fout << setw(7) << left << "Full" <<
      setw(6) << right << num_wraps << "\n";

    double mean = prod_sum / static_cast<double>(count);
    fout << setw(7) << left << "Average" <<
      setw(6) << right << setprecision(2) << fixed << mean << "\n";

    double var = (prod_sumsq - count*mean*mean) /
      static_cast<double>(count-1);

    if (var >= 0.)
      fout << setw(7) << left << "Std.dev" <<
        setw(6) << right << setprecision(2) << fixed << sqrt(var) << "\n";

    fout << setw(7) << left << "Maximum" <<
      setw(6) << right << max_len << "\n";
  }
  fout << "\n";
}


void TransTableL::UpdateSuitHist(
  const int trick,
  const int hand,
  int hist[],
  int& num_wraps) const
{
  distHashType * dp;

  num_wraps = 0;
  for (int i = 0; i <= DISTS_PER_ENTRY; i++)
    hist[i] = 0;

  for (int hashkey = 0; hashkey < 256; hashkey++)
  {
    dp = &TTroot[trick][hand][hashkey];
    hist [ dp->nextNo ]++;

    if (dp->nextNo != dp->nextWriteNo)
      num_wraps++; // Not entirely correct
  }
}


void TransTableL::UpdateSuitHist(
  const int trick,
  const int hand,
  int hist[],
  int suitHist[],
  int& num_wraps,
  int& suitWraps) const
{
  distHashType * dp;

  num_wraps = 0;
  for (int i = 0; i <= DISTS_PER_ENTRY; i++)
    hist[i] = 0;

  for (int hashkey = 0; hashkey < 256; hashkey++)
  {
    dp = &TTroot[trick][hand][hashkey];
    hist [ dp->nextNo ]++;
    suitHist[ dp->nextNo ]++;

    if (dp->nextNo != dp->nextWriteNo)
    {
      num_wraps++; // Not entirely correct
      suitWraps++;
    }
  }
}


void TransTableL::PrintSuitStats(
  ofstream& fout,
  const int trick,
  const int hand) const
{
  int hist[DISTS_PER_ENTRY+1];
  int num_wraps;

  TransTableL::UpdateSuitHist(trick, hand, hist, num_wraps);

  fout << "Suit histogram for trick " << trick << ", hand " <<
    players[static_cast<unsigned>(hand)] << "\n";
  TransTableL::PrintHist(fout, hist, num_wraps, DISTS_PER_ENTRY);
}


void TransTableL::PrintAllSuitStats(ofstream& fout) const
{
  int num_wraps;
  int suitWraps = 0;

  // Really the maximum of BLOCKS_PER_ENTRY and DISTS_PER_ENTRY.
  int hist[DISTS_PER_ENTRY+1];
  int suitHist[DISTS_PER_ENTRY+1];

  for (int i = 0; i <= DISTS_PER_ENTRY; i++)
    suitHist[i] = 0;

  for (int trick = 11; trick >= 1; trick--)
  {
    for (int hand = 0; hand < DDS_HANDS; hand++)
    {
      TransTableL::UpdateSuitHist(trick, hand, hist, suitHist,
        num_wraps, suitWraps);

      fout << "Suit histogram for trick " << trick << ", hand " <<
        players[static_cast<unsigned>(hand)] << "\n";
      TransTableL::PrintHist(fout, hist, num_wraps, DISTS_PER_ENTRY);
    }
  }

  fout << "Overall suit histogram\n";
  TransTableL::PrintHist(fout, suitHist, suitWraps, DISTS_PER_ENTRY);
}


void TransTableL::PrintSummarySuitStats(ofstream& fout) const
{
  int hist[DISTS_PER_ENTRY+1];
  int count, prod_sum, prod_sumsq, max_len, num_wraps;

  fout << "Suit depth statistics\n\n";

  fout << setw(5) << right << "Trick" <<
    setw(7) << "Player" <<
    setw(8) << "Entries" <<
    setw(8) << "Full" <<
    setw(8) << "Average" <<
    setw(8) << "Std.dev" <<
    setw(8) << "Maximum" <<
    "   P" << setw(4) << setprecision(2) << fixed << TT_PERCENTILE << "\n";

  for (int trick = 11; trick >= 1; trick--)
  {
    for (int hand = 0; hand < DDS_HANDS; hand++)
    {
      TransTableL::UpdateSuitHist(trick, hand, hist, num_wraps);
      TransTableL::MakeHistStats(hist,
        count, prod_sum, prod_sumsq, max_len, DISTS_PER_ENTRY);

      double mean = 0., var = 0.;
      if (count > 1)
      {
        mean = prod_sum / static_cast<double>(count);

        var = (prod_sumsq - count*mean*mean) / 
          static_cast<double>(count-1);
        if (var < 0.)
          var = 0.;
      }

      const int percentile =
        TransTableL::CalcPercentile(hist,
          TT_PERCENTILE * count, DISTS_PER_ENTRY);

      fout << setw(5) << right << trick <<
        setw(7) << players[static_cast<unsigned>(hand)] <<
        setw(8) << count <<
        setw(8) << num_wraps;
      
      if (count > 0)
        fout << setw(8) << mean << 
          setw(8) << setprecision(2) << fixed << sqrt(var);
      else
        fout << setw(8) << '-' << setw(8) << '-';

      fout << setw(8) << max_len <<
        setw(8) << setprecision(2) << fixed << percentile << "\n";
    }
    fout << "\n";
  }
  fout << "\n";
}


TransTableL::winBlockType const * TransTableL::FindMatchingDist(
  const int trick,
  const int hand,
  const int handDistSought[]) const
{
  winBlockType * bp;
  distHashType * dp;
  int handDist[DDS_HANDS];

  for (int hashkey = 0; hashkey < 256; hashkey++)
  {
    dp = &TTroot[trick][hand][hashkey];
    for (int i = 0; i < dp->nextNo; i++)
    {
      bp = dp->list[i].posBlock;
      TransTableL::KeyToDist(dp->list[i].key, handDist);

      bool same = true;
      for (int h = 0; h < DDS_HANDS; h++)
      {
        if (handDist[h] != handDistSought[h])
        {
          same = false;
          break;
        }
      }
      if (same)
        return bp;
    }
  }
  return nullptr;
}


void TransTableL::PrintEntriesBlock(
  ofstream& fout,
  winBlockType const * bp,
  const unsigned char lengths[DDS_HANDS][DDS_SUITS]) const
{
  string st = to_string(bp->nextMatchNo) + 
    " matches for " + TransTableL::LenToStr(lengths);

  fout << st << "\n" << string(st.size(), '=') << "\n\n";

  for (int j = 0; j < bp->nextMatchNo; j++)
  {
    st = "Entry number " + to_string(j+1);
    fout << st << "\n";
    fout << string(st.size(), '-') << "\n\n";
    TransTableL::PrintMatch(fout, bp->list[j], lengths);
  }
}



void TransTableL::PrintEntriesDistAndCards(
  ofstream& fout,
  const int trick,
  const int hand,
  const unsigned short aggrTarget[],
  const int handDist[]) const
{
  unsigned char len[DDS_HANDS][DDS_SUITS];

  winBlockType const * bp =
    TransTableL::FindMatchingDist(trick, hand, handDist);

  TransTableL::DistToLengths(trick, handDist, len);

  fout << "Looking up entry for trick " << trick << ", hand " <<
    players[static_cast<unsigned>(hand)] << "\n";
  fout << TransTableL::LenToStr(len) << "\n\n";

  if (! bp)
  {
    fout << "Entry not found\n\n";
    return;
  }

  unsigned const * ab0 = aggr[ aggrTarget[0] ].aggrBytes[0];
  unsigned const * ab1 = aggr[ aggrTarget[1] ].aggrBytes[1];
  unsigned const * ab2 = aggr[ aggrTarget[2] ].aggrBytes[2];
  unsigned const * ab3 = aggr[ aggrTarget[3] ].aggrBytes[3];

  winMatchType TTentry;
  TTentry.topSet1 = ab0[0] | ab1[0] | ab2[0] | ab3[0];
  TTentry.topSet2 = ab0[1] | ab1[1] | ab2[1] | ab3[1];
  TTentry.topSet3 = ab0[2] | ab1[2] | ab2[2] | ab3[2];
  TTentry.topSet4 = ab0[3] | ab1[3] | ab2[3] | ab3[3];

  int matchNo = 1;
  int n = bp->nextMatchNo - 1;
  winMatchType const * wp = &bp->list[n];

  for (int i = n; i >= 0; i--, wp--)
  {
    if ((wp->topSet1 ^ TTentry.topSet1) & wp->topMask1)
      continue;

    if (wp->lastMaskNo != 1)
    {
      if ((wp->topSet2 ^ TTentry.topSet2) & wp->topMask2)
        continue;

      if (wp->lastMaskNo != 2)
      {
        if ((wp->topSet3 ^ TTentry.topSet3) & wp->topMask3)
          continue;
      }
    }

    fout << "Match number " << matchNo++ << "\n";
    fout << string(15, '-') << "\n";
    TransTableL::PrintMatch(fout, bp->list[i], len);
  }

  if (matchNo == 1)
    fout << n << " matches for suit, none for cards\n\n";
  else
    fout << "\n";
}


void TransTableL::PrintEntriesDist(
  ofstream& fout,
  const int trick,
  const int hand,
  const int handDist[]) const
{
  unsigned char len[DDS_HANDS][DDS_SUITS];

  winBlockType const * bp =
    TransTableL::FindMatchingDist(trick, hand, handDist);

  TransTableL::DistToLengths(trick, handDist, len);

  if (! bp)
  {
    fout << "Entry not found: Trick " << trick << ", hand " <<
      players[static_cast<unsigned>(hand)] << "\n";
    fout << TransTableL::LenToStr(len) << "\n\n";
    return;
  }

  TransTableL::PrintEntriesBlock(fout, bp, len);
}


void TransTableL::PrintEntries(
  ofstream& fout,
  const int trick,
  const int hand) const
{
  winBlockType * bp;
  distHashType * dp;
  int handDist[DDS_HANDS];
  unsigned char lengths[DDS_HANDS][DDS_SUITS];

  for (int hashkey = 0; hashkey < 256; hashkey++)
  {
    dp = &TTroot[trick][hand][hashkey];
    for (int i = 0; i < dp->nextNo; i++)
    {
      bp = dp->list[i].posBlock;
      TransTableL::KeyToDist(dp->list[i].key, handDist);
      TransTableL::DistToLengths(trick, handDist, lengths);

      TransTableL::PrintEntriesBlock(fout, bp, lengths);
    }
  }
}


void TransTableL::PrintAllEntries(ofstream& fout) const
{
  for (int trick = 11; trick >= 1; trick--)
  {
    for (int hand = 0; hand < DDS_HANDS; hand++)
    {
      const string st = "Entries, trick " + to_string(trick) +
        ", hand " + players[static_cast<unsigned>(hand)];
      fout << st << "\n";
      fout << string(st.size(), '=') << "\n\n";
      TransTableL::PrintEntries(fout, trick, hand);
    }
  }
  fout << "\n";
}


void TransTableL::UpdateEntryHist(
  const int trick,
  const int hand,
  int hist[],
  int& num_wraps) const
{
  distHashType * dp;

  num_wraps = 0;
  for (int i = 0; i <= BLOCKS_PER_ENTRY; i++)
    hist[i] = 0;

  for (int hashkey = 0; hashkey < 256; hashkey++)
  {
    dp = &TTroot[trick][hand][hashkey];
    for (int i = 0; i < dp->nextNo; i++)
    {
      int c = dp->list[i].posBlock->nextMatchNo;
      hist [c]++;

      if (c != dp->list[i].posBlock->nextWriteNo)
        num_wraps++; // Not entirely correct
    }
  }
}


void TransTableL::UpdateEntryHist(
  const int trick,
  const int hand,
  int hist[],
  int suitHist[],
  int& num_wraps,
  int& suitWraps) const
{
  distHashType * dp;

  num_wraps = 0;
  for (int i = 0; i <= BLOCKS_PER_ENTRY; i++)
    hist[i] = 0;

  for (int hashkey = 0; hashkey < 256; hashkey++)
  {
    dp = &TTroot[trick][hand][hashkey];
    for (int i = 0; i < dp->nextNo; i++)
    {
      int c = dp->list[i].posBlock->nextMatchNo;
      hist [c]++;
      suitHist[c]++;

      if (c != dp->list[i].posBlock->nextWriteNo)
      {
        num_wraps++; // Not entirely correct
        suitWraps++;
      }
    }
  }
}


void TransTableL::PrintEntryStats(
  ofstream& fout,
  const int trick,
  const int hand) const
{
  int hist[BLOCKS_PER_ENTRY+1];
  int num_wraps;

  TransTableL::UpdateEntryHist(trick, hand, hist, num_wraps);

  fout << "Entry histogram for trick " << trick << ", hands " <<
    players[static_cast<unsigned>(hand)] << "\n";
  TransTableL::PrintHist(fout, hist, num_wraps, BLOCKS_PER_ENTRY);
}


void TransTableL::PrintAllEntryStats(ofstream& fout) const
{
  int hist[BLOCKS_PER_ENTRY+1];
  int num_wraps;

  int suitWraps = 0;
  int suitHist[BLOCKS_PER_ENTRY+1];
  for (int i = 0; i <= BLOCKS_PER_ENTRY; i++)
    suitHist[i] = 0;

  for (int trick = 11; trick >= 1; trick--)
  {
    for (int hand = 0; hand < DDS_HANDS; hand++)
    {
      TransTableL::UpdateEntryHist(trick, hand, hist, suitHist,
        num_wraps, suitWraps);

      fout << "Entry histogram for trick " << trick << ", hands " <<
        players[static_cast<unsigned>(hand)] << "\n";
      TransTableL::PrintHist(fout, hist, num_wraps, BLOCKS_PER_ENTRY);
    }
  }

  fout << "Overall entry histogram\n";
  TransTableL::PrintHist(fout, suitHist, suitWraps, BLOCKS_PER_ENTRY);
}


int TransTableL::EffectOfBlockBound(
  const int hist[],
  const int size) const
{
  // Calculates the number of blocks used if the blocks
  // are divided up in units of size, rather than in units
  // of BLOCKS_PER_ENTRY. Only makes sense if size is less
  // than BLOCKS_PER_ENTRY, as we won't have statistics for
  // how many blocks above BLOCKS_PER_ENTRY would be created
  // if BLOCKS_PER_ENTRY were larger.

  int cum_memory = 0;
  int unit_size = 0;

  for (int i = 1; i <= BLOCKS_PER_ENTRY; i++)
  {
    if ((i - 1) % size == 0)
      unit_size += size;

    cum_memory += hist[i] * unit_size;
  }
  return cum_memory;
}


void TransTableL::PrintSummaryEntryStats(ofstream& fout) const
{
  int hist[BLOCKS_PER_ENTRY + 1];
  int count, prod_sum, prod_sumsq, max_len, num_wraps;

  int cumCount = 0;
  double cumProd = 0.;
  int cumMemory = 0;

  fout << "Entry depth statistics\n\n";

  fout << setw(5) << right << "Trick" <<
    setw(7) << "Player" <<
    setw(8) << "Entries" <<
    setw(8) << "Full" <<
    setw(8) << "Average" <<
    setw(8) << "Std.dev" <<
    setw(8) << "Maximum" <<
    "   P" << setw(4) << setprecision(2) << fixed << TT_PERCENTILE << "\n";

  for (int trick = 11; trick >= 1; trick--)
  {
    for (int hand = 0; hand < DDS_HANDS; hand++)
    {
      TransTableL::UpdateEntryHist(trick, hand, hist, num_wraps);
      TransTableL::MakeHistStats(hist,
        count, prod_sum, prod_sumsq, max_len, BLOCKS_PER_ENTRY);

      cumCount += count;
      cumProd += prod_sum;
      cumMemory += TransTableL::EffectOfBlockBound(hist, 20);

      double mean = prod_sum / static_cast<double>(count);
      double var = (count > 1 ?
        (prod_sumsq - count*mean*mean) / 
          static_cast<double>(count-1) : 0.);

      if (var < 0.)
        var = 0.;

      const int percentile = TransTableL::CalcPercentile(hist,
         TT_PERCENTILE * count, BLOCKS_PER_ENTRY);

      fout << setw(5) << right << trick <<
        setw(7) << players[static_cast<unsigned>(hand)] <<
        setw(8) << count <<
        setw(8) << num_wraps <<
        setw(8) << mean <<
        setw(8) << sqrt(var) <<
        setw(8) << max_len <<
        setw(8) << setprecision(2) << fixed << percentile << "\n";
    }
    fout << "\n";
  }
  fout << "\n";

  fout << setw(16) << left << "Blocks counted " <<
    setw(8) << right << cumCount << "\n";
  fout << setw(16) << left << "Blocks produced " <<
    setw(8) << right << TransTableL::BlocksInUse() << "\n";
  fout << setw(16) << left << "Mem scenario" <<
    setw(7) << right << setprecision(2) << fixed <<
      100. * cumMemory / 
        (static_cast<double>(BLOCKS_PER_ENTRY * cumCount)) << "%\n";

  if (cumCount)
    fout << setw(16) << left << "Fullness" <<
      setw(7) << right << setprecision(2) << fixed <<
        100. * cumProd / (BLOCKS_PER_ENTRY * cumCount) << "%\n";
  fout << "\n";
}