1 #ifndef LIBLAS_CHIPPER_H
2 #define LIBLAS_CHIPPER_H
3 
4 #include <liblas/liblas.hpp>
5 #include <liblas/export.hpp>
6 #include <liblas/detail/opt_allocator.hpp>
7 
8 #include <vector>
9 
10 namespace liblas
11 {
12 
13 namespace chipper
14 {
15 
16 enum Direction
17 {
18     DIR_X,
19     DIR_Y,
20     DIR_NONE
21 };
22 
23 class LAS_DLL PtRef
24 {
25 public:
26     double m_pos;
27     uint32_t m_ptindex;
28     uint32_t m_oindex;
29 
operator <(const PtRef & pt) const30     bool operator < (const PtRef& pt) const
31         { return m_pos < pt.m_pos; }
32 };
33 typedef std::vector<PtRef, detail::opt_allocator<PtRef> > PtRefVec;
34 
35 struct LAS_DLL RefList
36 {
37 public:
38     PtRefVec *m_vec_p;
39     Direction m_dir;
40 
RefListliblas::chipper::RefList41     RefList(Direction dir = DIR_NONE) : m_vec_p(NULL), m_dir(dir)
42         {}
~RefListliblas::chipper::RefList43     ~RefList()
44     {
45         delete m_vec_p;
46     }
47 
sizeliblas::chipper::RefList48     PtRefVec::size_type size() const
49         { return m_vec_p->size(); }
reserveliblas::chipper::RefList50     void reserve(PtRefVec::size_type n)
51         { m_vec_p->reserve(n); }
resizeliblas::chipper::RefList52     void resize(PtRefVec::size_type n)
53         { m_vec_p->resize(n); }
push_backliblas::chipper::RefList54     void push_back(const PtRef& ref)
55         { m_vec_p->push_back(ref); }
beginliblas::chipper::RefList56     PtRefVec::iterator begin()
57         { return m_vec_p->begin(); }
endliblas::chipper::RefList58     PtRefVec::iterator end()
59         { return m_vec_p->end(); }
operator []liblas::chipper::RefList60     PtRef& operator[](uint32_t pos)
61         { return (*m_vec_p)[pos]; }
Dirliblas::chipper::RefList62     std::string Dir()
63     {
64         if (m_dir == DIR_X)
65             return "X";
66         else if (m_dir == DIR_Y)
67             return "Y";
68         else
69             return "NONE";
70     }
71     void SortByOIndex(uint32_t left, uint32_t center,
72         uint32_t right);
SetAllocatorliblas::chipper::RefList73     void SetAllocator(detail::opt_allocator<PtRef> *alloc_p )
74     {
75         m_vec_p = new PtRefVec( *alloc_p );
76     }
77 };
78 
79 class LAS_DLL Chipper;
80 
81 class LAS_DLL Block
82 {
83     friend class Chipper;
84 
85 private:
86     RefList *m_list_p;
87     uint32_t m_left;
88     uint32_t m_right;
89     liblas::Bounds<double> m_bounds;
90 
91 public:
92     std::vector<uint32_t> GetIDs() const;
GetBounds() const93     Bounds<double> const& GetBounds() const
94         {return m_bounds;}
SetBounds(liblas::Bounds<double> const & bounds)95     void SetBounds(liblas::Bounds<double> const& bounds)
96         {m_bounds = bounds;}
97 };
98 
99 // Options that can be used to modify the behavior of the chipper.
100 class LAS_DLL Options
101 {
102 public:
Options()103     Options() : m_threshold( 1000 ), m_use_sort( false ),
104        m_use_maps( false )
105     {}
106 
107     // Maximum number of pointer per output block.
108     uint32_t m_threshold;
109     // If true, use sorting instead of copying to reduce memory.
110     bool m_use_sort;
111     // If true, use memory mapped files instead of main memory
112     bool m_use_maps;
113     // Map file to use if m_use_maps is true.
114     std::string m_map_file;
115 };
116 
117 class LAS_DLL Chipper
118 {
119 public:
120     Chipper(Reader *reader, Options *options );
Chipper(Reader * reader,uint32_t max_partition_size)121     Chipper(Reader *reader, uint32_t max_partition_size) :
122         m_reader(reader), m_xvec(DIR_X), m_yvec(DIR_Y), m_spare(DIR_NONE)
123     {
124         m_options.m_threshold = max_partition_size;
125     }
126 
127     void Chip();
GetBlockCount()128     std::vector<Block>::size_type GetBlockCount()
129         { return m_blocks.size(); }
GetBlock(std::vector<Block>::size_type i)130     const Block& GetBlock(std::vector<Block>::size_type i)
131         { return m_blocks[i]; }
132 
133 private:
134     int Allocate();
135     int Load();
136     void Partition(uint32_t size);
137     void Split(RefList& xvec, RefList& yvec, RefList& spare);
138     void DecideSplit(RefList& v1, RefList& v2, RefList& spare,
139         uint32_t left, uint32_t right);
140     void RearrangeNarrow(RefList& wide, RefList& narrow, RefList& spare,
141         uint32_t left, uint32_t center, uint32_t right);
142     void Split(RefList& wide, RefList& narrow, RefList& spare,
143         uint32_t left, uint32_t right);
144     void FinalSplit(RefList& wide, RefList& narrow,
145         uint32_t pleft, uint32_t pcenter);
146     void Emit(RefList& wide, uint32_t widemin, uint32_t widemax,
147         RefList& narrow, uint32_t narrowmin, uint32_t narrowmax);
148 
149     Reader *m_reader;
150     std::vector<Block> m_blocks;
151     std::vector<uint32_t> m_partitions;
152     // Note, order is important here, as the allocator must be destroyed
153     // after the RefLists.
154     boost::shared_ptr<detail::opt_allocator<PtRef> > m_allocator;
155     RefList m_xvec;
156     RefList m_yvec;
157     RefList m_spare;
158     Options m_options;
159 };
160 
161 } // namespace chipper
162 
163 } // namespace liblas
164 
165 #endif
166