Method rehash

highs/util/HighsHashTree.h:207–255

    }

    void rehash(int hashPos) {
      // function needs to possibly reorder elements by a different hash value
      // chances are very high we are already ordered correctly as we use 16
      // bits of the hash and one level is uses 6 bits, so the new values
      // are guaranteed to be ordered correctly by their 10 most significant
      // bits if increasing the hash position by 1 and only if the 10 bits of
      // the hash had a collision the new 6 bits might break a tie differently.
      // It is, however, important to maintain the exact ordering as otherwise
      // elements may not be found.
      occupation = 0;
      for (int i = 0; i < size; ++i) {
        hashes[i] = get_hash_chunks16(compute_hash(entries[i].key()), hashPos);
        occupation.set(get_first_chunk16(hashes[i]));
      }

      int i = 0;
      while (i < size) {
        uint8_t hashChunk = get_first_chunk16(hashes[i]);
        int pos = occupation.num_set_until(hashChunk) - 1;

        // if the position is after i the element definitely comes later, so we
        // swap it to that position and proceed without increasing i until
        // eventually an element appears that comes at position i or before
        if (pos > i) {
          std::swap(hashes[pos], hashes[i]);
          std::swap(entries[pos], entries[i]);
          continue;
        }

        // the position is before or at i, now check where the exact location
        // should be for the ordering by hash so that the invariant is that all
        // elements up to i are properly sorted. Essentially insertion sort but
        // with the modification of having a high chance to guess the correct
        // position already using the occupation flags.
        while (pos < i && hashes[pos] >= hashes[i]) ++pos;

        // if the final position is before i we need to move elements to
        // make space at that position, otherwise nothing needs to be done but
        // incrementing i increasing the sorted range by 1.
        if (pos < i) {
          uint64_t hash = hashes[i];
          auto entry = std::move(entries[i]);
          move_backward(pos, i);
          hashes[pos] = hash;
          entries[pos] = std::move(entry);
        }
        ++i;
      }
    }

    void move_backward(const int& first, const int& last) {
      // move elements backwards