← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/carve/include/carve/djset.hpp

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/carve/include/carve/djset.hpp
 
1
// Begin License:
 
2
// Copyright (C) 2006-2011 Tobias Sargeant (tobias.sargeant@gmail.com).
 
3
// All rights reserved.
 
4
//
 
5
// This file is part of the Carve CSG Library (http://carve-csg.com/)
 
6
//
 
7
// This file may be used under the terms of the GNU General Public
 
8
// License version 2.0 as published by the Free Software Foundation
 
9
// and appearing in the file LICENSE.GPL2 included in the packaging of
 
10
// this file.
 
11
//
 
12
// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
 
13
// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
 
14
// A PARTICULAR PURPOSE.
 
15
// End:
 
16
 
 
17
 
 
18
#pragma once
 
19
 
 
20
#include <carve/carve.hpp>
 
21
#include <vector>
 
22
 
 
23
 
 
24
 
 
25
namespace carve {
 
26
namespace djset {
 
27
 
 
28
 
 
29
 
 
30
  class djset {
 
31
 
 
32
  protected:
 
33
    struct elem {
 
34
      size_t parent, rank;
 
35
      elem(size_t p, size_t r) : parent(p), rank(r) {}
 
36
      elem() {}
 
37
    };
 
38
 
 
39
    std::vector<elem> set;
 
40
    size_t n_sets;
 
41
 
 
42
  public:
 
43
    djset() : set(), n_sets(0) {
 
44
    }
 
45
 
 
46
    djset(size_t N) {
 
47
      n_sets = N;
 
48
      set.reserve(N);
 
49
      for (size_t i = 0; i < N; ++i) {
 
50
        set.push_back(elem(i,0));
 
51
      }
 
52
    }
 
53
 
 
54
    void init(size_t N) {
 
55
      if (N == set.size()) {
 
56
        for (size_t i = 0; i < N; ++i) {
 
57
          set[i] = elem(i,0);
 
58
        }
 
59
        n_sets = N;
 
60
      } else {
 
61
        djset temp(N);
 
62
        std::swap(set, temp.set);
 
63
        std::swap(n_sets, temp.n_sets);
 
64
      }
 
65
    }
 
66
 
 
67
    size_t count() const {
 
68
      return n_sets;
 
69
    }
 
70
 
 
71
    size_t find_set_head(size_t a) {
 
72
      if (a == set[a].parent) return a;
 
73
    
 
74
      size_t a_head = a;
 
75
      while (set[a_head].parent != a_head) a_head = set[a_head].parent;
 
76
      set[a].parent = a_head;
 
77
      return a_head;
 
78
    }
 
79
 
 
80
    bool same_set(size_t a, size_t b) {
 
81
      return find_set_head(a) == find_set_head(b);
 
82
    }
 
83
 
 
84
    void merge_sets(size_t a, size_t b) {
 
85
      a = find_set_head(a);
 
86
      b = find_set_head(b);
 
87
      if (a != b) {
 
88
        n_sets--;
 
89
        if (set[a].rank < set[b].rank) {
 
90
          set[a].parent = b;
 
91
        } else if (set[b].rank < set[a].rank) {
 
92
          set[b].parent = a;
 
93
        } else {
 
94
          set[a].rank++;
 
95
          set[b].parent = a;
 
96
        }
 
97
      }
 
98
    }
 
99
 
 
100
    void get_index_to_set(std::vector<size_t> &index_set, std::vector<size_t> &set_size) {
 
101
      index_set.clear();
 
102
      index_set.resize(set.size(), n_sets);
 
103
      set_size.clear();
 
104
      set_size.resize(n_sets, 0);
 
105
 
 
106
      size_t c = 0;
 
107
      for (size_t i = 0; i < set.size(); ++i) {
 
108
        size_t s = find_set_head(i);
 
109
        if (index_set[s] == n_sets) index_set[s] = c++;
 
110
        index_set[i] = index_set[s];
 
111
        set_size[index_set[s]]++;
 
112
      }
 
113
    }
 
114
 
 
115
    template<typename in_iter_t, typename out_collection_t>
 
116
    void collate(in_iter_t in, out_collection_t &out) {
 
117
      std::vector<size_t> set_id(set.size(), n_sets);
 
118
      out.clear();
 
119
      out.resize(n_sets);
 
120
      size_t c = 0;
 
121
      for (size_t i = 0; i < set.size(); ++i) {
 
122
        size_t s = find_set_head(i);
 
123
        if (set_id[s] == n_sets) set_id[s] = c++;
 
124
        s = set_id[s];
 
125
        std::insert_iterator<typename out_collection_t::value_type> j(out[s], out[s].end());
 
126
        *j = *in++;
 
127
      }
 
128
    }
 
129
  };
 
130
 
 
131
 
 
132
 
 
133
}
 
134
}