nlib
Louds.h
Go to the documentation of this file.
1 
2 /*--------------------------------------------------------------------------------*
3  Project: CrossRoad
4  Copyright (C)Nintendo All rights reserved.
5 
6  These coded instructions, statements, and computer programs contain proprietary
7  information of Nintendo and/or its licensed developers and are protected by
8  national and international copyright laws. They may not be disclosed to third
9  parties or copied or duplicated in any form, in whole or in part, without the
10  prior written consent of Nintendo.
11 
12  The content herein is highly confidential and should be handled accordingly.
13  *--------------------------------------------------------------------------------*/
14 
15 #pragma once
16 #ifndef INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
17 #define INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
18 
19 #include "nn/nlib/Swap.h"
20 #include "nn/nlib/succinct/Sbv.h"
21 
22 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
23 #undef NLIB_VIS_PUBLIC
24 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
25 #endif
26 
27 NLIB_NAMESPACE_BEGIN
28 namespace succinct {
29 
31  public:
34  NLIB_MOVE_MEMBER_HELPER_1(Louds, sbv_);
35  void swap(Louds& rhs) NLIB_NOEXCEPT { sbv_.swap(rhs.sbv_); }
36  template <class TREEITER>
37  bool Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT; // NOLINT
38 
39  bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
40  int ToNodeId(uint32_t pos) const NLIB_NOEXCEPT;
41  int ToPos(uint32_t nodeid) const NLIB_NOEXCEPT;
42  int FirstChild(uint32_t pos) const NLIB_NOEXCEPT;
43  int NextSibling(uint32_t pos) const NLIB_NOEXCEPT;
44  int PrevSibling(uint32_t pos) const NLIB_NOEXCEPT;
45  int Parent(uint32_t pos) const NLIB_NOEXCEPT;
46  bool IsLeaf(uint32_t pos) const NLIB_NOEXCEPT {
47  return this->FirstChild(pos) < 0;
48  }
49  size_t MemSize() const NLIB_NOEXCEPT { return sbv_.MemSize(); }
50  void Reset() NLIB_NOEXCEPT { sbv_.Reset(); }
51  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT { return sbv_.Export(w); }
52  bool Import(BinaryReader* r) NLIB_NOEXCEPT { return sbv_.Import(r); }
53 
54  private:
55  Sbv sbv_;
57 };
58 
59 template <class TREEITER>
60 bool Louds::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT { // NOLINT
61  // TREEITER has following methods:
62  // int GetNumChildren();
63  // bool BfsMoveNext(); // move to the next node by breadth first search
64  sbv_.Init(2 * num_nodes + 1);
65 
66  // diffrent from the Louds paper: reversed bits
67  sbv_.TurnOn(1);
68  uint32_t idx = 2; // consider super-root 01
69  do {
70  idx += iter.GetNumChildren();
71  sbv_.TurnOn(idx++);
72  } while (iter.BfsMoveNext());
73 
74  NLIB_ASSERT(idx == 2 * num_nodes + 1);
75  if (!sbv_.Build()) {
76  sbv_.Reset();
77  return false;
78  }
79  return true;
80 }
81 
82 } // namespace succinct
83 NLIB_NAMESPACE_END
84 
85 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
86 #undef NLIB_VIS_PUBLIC
87 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
88 #endif
89 
90 #endif // INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
Defines the basic classes that form the basis to Rank and Select operations.
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
Definition: Louds.h:51
Louds() noexcept
Instantiates the object.
Definition: Louds.h:32
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:163
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:77
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
Definition: Louds.h:49
bool Import(BinaryReader *r) noexcept
Reads the written object.
Definition: Louds.h:52
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:89
void swap(Louds &rhs) noexcept
Swaps the contents of an object.
Definition: Louds.h:35
~Louds() noexcept
Destructor.
Definition: Louds.h:33
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:99
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Definition: Louds.h:50
bool IsLeaf(uint32_t pos) const noexcept
Determines whether the specified node is a leaf (or external) node.
Definition: Louds.h:46
Provides a compact tree structure that can provide various operations in constant time...
Definition: Louds.h:30
The class for writing binary to streams (to OutputStream).
Definition: BinaryWriter.h:26
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:229
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:26