API tools faq
paste
prestige

Untitled

prestige
Jan 11th, 2013
153
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.32 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <queue>
  5. #include <set>
  6.  
  7. using std::cerr;
  8. using std::cin;
  9. using std::endl;
  10. using std::cout;
  11. using std::set;
  12. using std::pair;
  13. using std::list;
  14. using std::vector;
  15. using std::make_pair;
  16. using std::priority_queue;
  17.  
  18. const int SIZE = 10;
  19.  
  20. class Segment {
  21. public:
  22. int length;
  23. int end_time;
  24. bool used_segment;
  25. int start_coordinate;
  26. Segment(int start = 0, int end = 0, int len = 0, bool used = false) : start_coordinate(start),
  27. end_time(end),
  28. length(len),
  29. used_segment(used) {}
  30.  
  31. };
  32.  
  33. typedef list<Segment>::iterator lSi;
  34. typedef pair<Segment, lSi> pSlS;
  35.  
  36. struct FreeSegmentsCompare {
  37. bool operator() (const pSlS& first, const pSlS& second) {
  38. return make_pair(first.first.length, first.first.start_coordinate) <
  39. make_pair(second.first.length, second.first.start_coordinate);
  40. }
  41. };
  42.  
  43. struct ProcessingTaskCompare {
  44. bool operator() (const pSlS& first, const pSlS& second) {
  45. if (first.first.end_time != second.first.end_time)
  46. return first.first.end_time > second.first.end_time;
  47. return first.first.length < second.first.length;
  48. }
  49. };
  50.  
  51. struct SegmentQueueCompare {
  52. bool operator() (const pSlS& first, const pSlS& second) {
  53. if (first.first.end_time != second.first.end_time)
  54. return first.first.end_time > second.first.end_time;
  55. return first.first.length < second.first.length;
  56. }
  57. };
  58.  
  59. class MemoryMenager {
  60. int memory_length;
  61. list<Segment> segments;
  62. set<pSlS, FreeSegmentsCompare > free_segments;
  63. priority_queue<pSlS, vector<pSlS>, ProcessingTaskCompare> processing_tasks;
  64. int PopTask() {
  65. if (processing_tasks.empty())
  66. throw std::logic_error("Try to erase empty tasks.");
  67.  
  68. pSlS task = processing_tasks.top();
  69. processing_tasks.pop();
  70.  
  71. lSi it = task.second;
  72. int free_segment_size = it->length;
  73. int segment_start = it->start_coordinate;
  74. int time = it->end_time;
  75. if (it != segments.begin()) {
  76. --it;
  77. if (!it->used_segment) {
  78. free_segment_size += it->length;
  79. segment_start = it->start_coordinate;
  80. free_segments.erase(free_segments.lower_bound(
  81. make_pair(Segment(it->start_coordinate, 0, it->length, false), segments.begin())));
  82.  
  83. lSi tmp = it;
  84. ++it;
  85. segments.erase(tmp);
  86. } else
  87. ++it;
  88. }
  89. ++it;
  90. if (it != segments.end()) {
  91. if (!it->used_segment) {
  92. free_segment_size += it->length;
  93. free_segments.erase(free_segments.lower_bound(
  94. make_pair(Segment(it->start_coordinate, 0, it->length, false), segments.begin())));
  95.  
  96. lSi tmp = it;
  97. --it;
  98. segments.erase(tmp);
  99. } else
  100. --it;
  101. } else
  102. --it;
  103.  
  104. *it = Segment(segment_start, 0, free_segment_size, false);
  105. free_segments.insert(make_pair(Segment(segment_start, 0, free_segment_size, false), it));
  106. return time;
  107. }
  108. public:
  109. MemoryMenager(int memory_size) : memory_length(memory_size) {
  110. Segment free_segment = Segment(0, 0, memory_size, false);
  111. segments.push_back(Segment(0, 0, memory_size, false));
  112. free_segments.insert(make_pair(free_segment, segments.begin()));
  113. }
  114. int AddTask(int length, int duration, int time) {
  115. if (memory_length < length)
  116. throw std::logic_error("Size of task bigger then all memory.");
  117. while(free_segments.lower_bound(make_pair(Segment(0, 0, length, false), segments.begin())) == free_segments.end()) {
  118. time = PopTask();
  119. }
  120.  
  121. auto it = free_segments.lower_bound(make_pair(Segment(0, 0, length, false), segments.begin()));
  122. pSlS free_segment = *it;
  123. free_segments.erase(it);
  124. if (free_segment.first.length == length) {
  125. free_segment.second->used_segment = true;
  126. free_segment.second->end_time = time + duration;
  127. processing_tasks.push(make_pair(Segment(free_segment.first.start_coordinate, time + duration, length, true), free_segment.second));
  128. return time;
  129. }
  130. free_segments.insert(make_pair(Segment(free_segment.first.start_coordinate, 0, free_segment.first.length - length, true), free_segment.second));
  131. free_segment.second->length = free_segment.first.length - length;
  132. Segment segment = Segment(free_segment.first.start_coordinate + free_segment.second->length,
  133. time + duration,
  134. length,
  135. true);
  136.  
  137. auto increased = free_segment.second;
  138. ++increased;
  139. auto fs = segments.insert(increased, segment);
  140. processing_tasks.push(make_pair(segment, fs));
  141. return time;
  142. }
  143. };
  144.  
  145. //firstfit
  146. list<Segment> ram;
  147. priority_queue<pSlS, vector<pSlS>, SegmentQueueCompare> q;
  148. int gl_time = 0;
  149. void initialize() {
  150. ram.push_front(Segment(0, -1, SIZE, false));
  151. }
  152. void Remove() {
  153. int rez = 0;
  154. pSlS top = q.top();
  155. lSi it = top.second;
  156. lSi pit = it;
  157. lSi nit = it;
  158. //проверять есть ли пред и след
  159. if (it != ram.begin() && it != ram.end()) {
  160. pit--;
  161. nit++;
  162. gl_time = top.first.end_time;
  163. if (it == ram.begin()) {
  164. if((nit)->used_segment) {
  165. ram.erase(ram.begin());
  166. } else {
  167. it->length += nit->length;
  168. ram.erase(nit);
  169. }
  170. } else if(it == ram.end()) {
  171. if((pit)->used_segment) {
  172. ram.erase(ram.end());
  173. } else {
  174. pit->length += it->length;
  175. ram.erase(it);
  176. }
  177. } else {
  178. if(pit->used_segment && nit->used_segment) {
  179. it->used_segment = false;
  180. } else if (!pit->used_segment && !nit->used_segment) {
  181. it->used_segment = false;
  182. it->length += pit->length + nit->length;
  183. ram.erase(pit);
  184. ram.erase(nit);
  185. } else if(pit->used_segment && !nit->used_segment) {
  186. it->length += nit->length;
  187. it->used_segment = false;
  188. ram.erase(nit);
  189. } else if(!pit->used_segment && nit->used_segment) {
  190. it->length += pit->length;
  191. it->used_segment = false;
  192. ram.erase(pit);
  193. }
  194. }
  195. } else if (it == ram.begin()) {
  196. nit++;
  197. if (!nit->used_segment)
  198. it->length += nit->length;
  199. it->used_segment = false;
  200. if (!nit->used_segment)
  201. ram.erase(nit);
  202. } else if (it == ram.end()) {
  203. pit--;
  204. if (!pit->used_segment)
  205. pit->length += it->length;
  206. pit->used_segment = false;
  207. if (!pit->used_segment)
  208. ram.erase(it);
  209. }
  210. q.pop();
  211. }
  212. void insert2(int size, int time) {
  213. bool flag = 0;
  214. for (list<Segment>::iterator it = ram.begin(); it != ram.end(); ++it) {
  215. if (it->used_segment == false && it->length >= size) {
  216. it->start_coordinate += size;
  217. it->length -= size;
  218. auto temp = ram.insert(it, Segment(it->start_coordinate - size, time + gl_time, size, true));
  219. q.push(make_pair(Segment(it->start_coordinate - size, time + gl_time, size, true), temp));
  220. flag = 1;
  221. }
  222. }
  223. if (!flag) {
  224. Remove();
  225. insert2(size, time);
  226. return ;
  227. }
  228. }
  229. int main() {
  230. MemoryMenager memory_menager(SIZE);
  231. int last_added = 0;
  232. int algo = 0;
  233. cin >> algo;
  234. cout << "1 - bestfit\n";
  235. cout << "2 - firstfit\n";
  236. vector<pair<int, int> > ans;
  237. if (algo == 1) {
  238. for (int index = 0; index < 10; ++index) {
  239. last_added = memory_menager.AddTask(10 + rand() % 20, 5 + rand() % 10, last_added);
  240. ans.push_back(make_pair(10 + rand() % 20, 5 + rand() % 10));
  241. }
  242. cout << last_added << endl;
  243. } else {
  244. initialize();
  245. ans.push_back(make_pair(6, 10));
  246. ans.push_back(make_pair(3, 3));
  247. ans.push_back(make_pair(5, 1));
  248. for (int index = 0; index < SIZE; ++index) {
  249. //ans.push_back(make_pair(rand() % SIZE, rand() % SIZE));
  250. insert2(ans[index].first,ans[index].second);
  251. }
  252.  
  253. }
  254. return 0;
  255. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!