binary_log.hxx

Go to the documentation of this file.

/*===========================================================================================================
 *
 * SHA-L - Simple Hybesis Algorithm Logger
 *
 * Copyright (c) Michael Jeulin-Lagarrigue
 *
 *  Licensed under the MIT License, you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://github.com/michael-jeulinl/Simple-Hybesis-Algorithms-Logger/blob/master/LICENSE
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License is
 * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and limitations under the License.
 *
 * The above copyright notice and this permission notice shall be included in all copies or
 * substantial portions of the Software.
 *
 *=========================================================================================================*/
#ifndef MODULE_SEARCH_BINARY_LOG_HXX
#define MODULE_SEARCH_BINARY_LOG_HXX

#include <Logger/algorithm.hxx>
#include <Logger/array.hxx>
#include <Logger/comment.hxx>
#include <Logger/operation.hxx>
#include <Logger/typedef.hxx>
#include <Logger/value.hxx>

namespace SHA_Logger
{
  template <typename IT, typename T, typename IsEqualT>
  class BinaryLog
  {
    public:
    static const String GetName() { return "Binary_Sort"; }

      static bool WriteInfo(Writer& writer) { return true; }

      static bool WriteDoc(Writer& writer) { return true; }

      static bool WriteSrc(Writer& writer) { return true; }

      // Assert correct JSON construction.
      ~BinaryLog() { assert(this->writer->IsComplete()); }

      static Ostream& Build(Ostream& os, Options opts, const IT& begin, const IT& end, const T& key)
      {
        std::unique_ptr<BinaryLog> builder = std::unique_ptr<BinaryLog>(new BinaryLog(os));
        builder->Write(opts, begin, end, key);

        return os;
      }

      static Writer& Build(Writer& writer, Options opts, const IT& begin, const IT& end, const T& key)
      {
        Write(writer, opts, begin, end, key);

        return writer;
      }

    private:
      BinaryLog(Ostream& os) : stream(std::unique_ptr<Stream>(new Stream(os))),
                               writer(std::unique_ptr<Writer>(new Writer(*this->stream))) {}
      BinaryLog operator=(BinaryLog&) {} // Not Implemented

      bool Write(Options opts, const IT& begin, const IT& end, const T& key)
      { return Write(*this->writer, opts, begin, end, key); }

      static bool Write(Writer& writer, Options opts, const IT& begin, const IT& end, const T& key)
      {
        writer.StartObject();

        // Write description
        Algo_Traits<BinaryLog>::Build(writer, opts);

        // Write parameters
        WriteParameters(writer, begin, end, key);

        // Write computation
        WriteComputation(writer, begin, end, key);

        writer.EndObject();

        return true;
      }

      static bool WriteParameters(Writer& writer, const IT& begin, const IT& end, const T& key)
      {
        writer.Key("parameters");
        writer.StartArray();
        Array<IT>::Build(writer, kSeqName, "begin", begin, "end", end);
        Value<T>::Build(writer, "key", key);
        writer.EndArray();

        return true;
      }

      static bool WriteComputation(Writer& writer, const IT& begin, const IT& end, const T& key)
      {
        // Not part of the logs
        int _lowIdx = 0;

        // Local logged variables
        writer.Key("locals");
        writer.StartArray();
        auto index = Value<int>::BuildValue(writer, "index", -1);
        auto seqSize = Value<int>::BuildValue(writer, "seqSize", static_cast<int>(std::distance(begin, end)));
        auto lowIt = Iterator::BuildIt<IT>(writer, kSeqName, "lowIt", 0, begin);
        auto highIt = Iterator::BuildIt<IT>(writer, kSeqName, "highIt", seqSize + 1, end);
        auto middleIt = Iterator::BuildIt<IT>(writer, kSeqName, "middleIt", seqSize / 2,
          lowIt + seqSize / 2, "Initiate index on the middle element of the sequence");
        writer.EndArray();

        // Log algorithm operations
        writer.Key("logs");
        writer.StartArray();
        Comment::Build(writer, "Start Binary Search", 0);
        while (lowIt < highIt && index < 0)
        {
          if (IsEqualT()(key, *middleIt))
          {
            index = static_cast<int>(std::distance(begin, middleIt));

            Comment::Build(writer, "Found!", 1);
            Operation::Set<int>(writer, "index", index);
            break;
          }
          else if (key > *middleIt)
          {
            lowIt = middleIt + 1;
            _lowIdx += seqSize / 2 + 1;
            seqSize -= seqSize / 2 + 1;

            Comment::Build(writer, "(key > current): search upper sequence.", 1);
            Operation::Set<int>(writer, "lowIt", _lowIdx);
          }
          else
          {
            highIt = middleIt;

            Comment::Build(writer, "(key < current): search lower sequence.", 1);
            Operation::Set<int>(writer, "highIt", seqSize / 2);
            seqSize -= seqSize / 2;
          }

          middleIt = lowIt + seqSize / 2;
          Comment::Build(writer, "Select the middle element of the remaining sequence.", 1);
          Operation::Set<int>(writer, "middleIt", _lowIdx + seqSize / 2);
        }

        // Logs failure
        if (index < 0)
          Comment::Build(writer, "Key not found.", 0);

        Operation::Return<int>(writer, index);
        writer.EndArray();
        return true;
      }

      std::unique_ptr<Stream> stream; // Stream wrapper
      std::unique_ptr<Writer> writer; // Writer used to fill the stream
  };
}

#endif // MODULE_SEARCH_BINARY_LOG_HXX