tesseract  5.0.0
tesseract::CLIST Class Reference

#include <clst.h>

Inheritance diagram for tesseract::CLIST:
tesseract::X_CLIST< CLASSNAME >

Public Member Functions

 ~CLIST ()
 
void internal_deep_clear (void(*zapper)(void *))
 
void shallow_clear ()
 
bool empty () const
 
bool singleton () const
 
void shallow_copy (CLIST *from_list)
 
void assign_to_sublist (CLIST_ITERATOR *start_it, CLIST_ITERATOR *end_it)
 
int32_t length () const
 
void sort (int comparator(const void *, const void *))
 
bool add_sorted (int comparator(const void *, const void *), bool unique, void *new_data)
 
void set_subtract (int comparator(const void *, const void *), bool unique, CLIST *minuend, CLIST *subtrahend)
 

Friends

class CLIST_ITERATOR
 

Detailed Description

Definition at line 64 of file clst.h.

Constructor & Destructor Documentation

◆ ~CLIST()

tesseract::CLIST::~CLIST ( )
inline

Definition at line 79 of file clst.h.

79  { // destructor
80  shallow_clear();
81  }
void shallow_clear()
Definition: clst.cpp:60

Member Function Documentation

◆ add_sorted()

bool tesseract::CLIST::add_sorted ( int   comparatorconst void *, const void *,
bool  unique,
void *  new_data 
)

Definition at line 138 of file clst.cpp.

138  {
139  // Check for adding at the end.
140  if (last == nullptr || comparator(&last->data, &new_data) < 0) {
141  auto *new_element = new CLIST_LINK;
142  new_element->data = new_data;
143  if (last == nullptr) {
144  new_element->next = new_element;
145  } else {
146  new_element->next = last->next;
147  last->next = new_element;
148  }
149  last = new_element;
150  return true;
151  } else if (!unique || last->data != new_data) {
152  // Need to use an iterator.
153  CLIST_ITERATOR it(this);
154  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
155  void *data = it.data();
156  if (data == new_data && unique) {
157  return false;
158  }
159  if (comparator(&data, &new_data) > 0) {
160  break;
161  }
162  }
163  if (it.cycled_list()) {
164  it.add_to_end(new_data);
165  } else {
166  it.add_before_then_move(new_data);
167  }
168  return true;
169  }
170  return false;
171 }
friend class CLIST_ITERATOR
Definition: clst.h:65

◆ assign_to_sublist()

void tesseract::CLIST::assign_to_sublist ( CLIST_ITERATOR start_it,
CLIST_ITERATOR end_it 
)

Definition at line 86 of file clst.cpp.

88  { // from list end
89  constexpr ERRCODE LIST_NOT_EMPTY("Destination list must be empty before extracting a sublist");
90 
91  if (!empty()) {
92  LIST_NOT_EMPTY.error("CLIST.assign_to_sublist", ABORT, nullptr);
93  }
94 
95  last = start_it->extract_sublist(end_it);
96 }
@ ABORT
Definition: errcode.h:31
bool empty() const
Definition: clst.h:89

◆ empty()

bool tesseract::CLIST::empty ( ) const
inline

Definition at line 89 of file clst.h.

89  { // is list empty?
90  return !last;
91  }

◆ internal_deep_clear()

void tesseract::CLIST::internal_deep_clear ( void(*)(void *)  zapper)

Definition at line 36 of file clst.cpp.

37  { // ptr to zapper functn
38  if (!empty()) {
39  auto ptr = last->next; // set to first
40  last->next = nullptr; // break circle
41  last = nullptr; // set list empty
42  while (ptr) {
43  auto next = ptr->next;
44  zapper(ptr->data);
45  delete (ptr);
46  ptr = next;
47  }
48  }
49 }

◆ length()

int32_t tesseract::CLIST::length ( ) const
inline

Definition at line 106 of file clst.h.

106  { //# elements in list
107  int32_t count = 0;
108  if (last != nullptr) {
109  count = 1;
110  for (auto it = last->next; it != last; it = it->next) {
111  count++;
112  }
113  }
114  return count;
115  }

◆ set_subtract()

void tesseract::CLIST::set_subtract ( int   comparatorconst void *, const void *,
bool  unique,
CLIST minuend,
CLIST subtrahend 
)

Definition at line 178 of file clst.cpp.

179  {
180  shallow_clear();
181  CLIST_ITERATOR m_it(minuend);
182  CLIST_ITERATOR s_it(subtrahend);
183  // Since both lists are sorted, finding the subtras that are not
184  // minus is a case of a parallel iteration.
185  for (m_it.mark_cycle_pt(); !m_it.cycled_list(); m_it.forward()) {
186  void *minu = m_it.data();
187  void *subtra = nullptr;
188  if (!s_it.empty()) {
189  subtra = s_it.data();
190  while (!s_it.at_last() && comparator(&subtra, &minu) < 0) {
191  s_it.forward();
192  subtra = s_it.data();
193  }
194  }
195  if (subtra == nullptr || comparator(&subtra, &minu) != 0) {
196  add_sorted(comparator, unique, minu);
197  }
198  }
199 }
bool add_sorted(int comparator(const void *, const void *), bool unique, void *new_data)
Definition: clst.cpp:138

◆ shallow_clear()

void tesseract::CLIST::shallow_clear ( )

Definition at line 60 of file clst.cpp.

60  { // destroy all links
61  if (!empty()) {
62  auto ptr = last->next; // set to first
63  last->next = nullptr; // break circle
64  last = nullptr; // set list empty
65  while (ptr) {
66  auto next = ptr->next;
67  delete (ptr);
68  ptr = next;
69  }
70  }
71 }

◆ shallow_copy()

void tesseract::CLIST::shallow_copy ( CLIST from_list)
inline

Definition at line 97 of file clst.h.

98  { // beware destructors!!
99  last = from_list->last;
100  }

◆ singleton()

bool tesseract::CLIST::singleton ( ) const
inline

Definition at line 93 of file clst.h.

93  {
94  return last != nullptr ? (last == last->next) : false;
95  }

◆ sort()

void tesseract::CLIST::sort ( int   comparator const void *, const void *)

Definition at line 104 of file clst.cpp.

106  {
107  // Allocate an array of pointers, one per list element.
108  auto count = length();
109  if (count > 0) {
110  // ptr array to sort
111  std::vector<void *> base;
112  base.reserve(count);
113 
114  CLIST_ITERATOR it(this);
115 
116  // Extract all elements, putting the pointers in the array.
117  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
118  base.push_back(it.extract());
119  }
120 
121  // Sort the pointer array.
122  qsort(&base[0], count, sizeof(base[0]), comparator);
123 
124  // Rebuild the list from the sorted pointers.
125  for (auto current : base) {
126  it.add_to_end(current);
127  }
128  }
129 }
int32_t length() const
Definition: clst.h:106

Friends And Related Function Documentation

◆ CLIST_ITERATOR

friend class CLIST_ITERATOR
friend

Definition at line 65 of file clst.h.


The documentation for this class was generated from the following files: