← Back to branch summary

~ubuntu-branches/ubuntu/lucid/igraph/lucid

« back to all changes in this revision

Viewing changes to src/bliss_kstack.hh

  • Committer: Bazaar Package Importer
  • Author(s): Mathieu Malaterre
  • Date: 2009-11-16 18:12:42 UTC
  • Revision ID: james.westby@ubuntu.com-20091116181242-mzv9p5fz9uj57xd1
Tags: upstream-0.5.3
Import upstream version 0.5.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/bliss_kstack.hh
 
1
/*
 
2
Copyright (C) 2003-2006 Tommi Junttila
 
3
 
 
4
 This program is free software; you can redistribute it and/or modify
 
5
 it under the terms of the GNU General Public License version 2
 
6
 as published by the Free Software Foundation.
 
7
 
 
8
 This program is distributed in the hope that it will be useful,
 
9
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
 GNU General Public License for more details.
 
12
 
 
13
 You should have received a copy of the GNU General Public License
 
14
 along with this program; if not, write to the Free Software
 
15
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
 
16
*/
 
17
 
 
18
/* FSF address fixed in the above notice on 1 Oct 2009 by Tamas Nepusz */
 
19
 
 
20
#ifndef BLISS_KSTACK_H
 
21
#define BLISS_KSTACK_H
 
22
 
 
23
#include "bliss_defs.hh"
 
24
#include <cstdlib>              // malloc
 
25
 
 
26
namespace igraph {
 
27
 
 
28
/* 
 
29
 * A stack with fixed capacity
 
30
 */
 
31
template <class Type>
 
32
class KStack {
 
33
public:
 
34
  KStack();
 
35
  KStack(int k);
 
36
  ~KStack();
 
37
  void init(int k);
 
38
 
 
39
  bool is_empty() const {return(cursor == entries); }
 
40
  Type top() const {DEBUG_ASSERT(cursor > entries); return *cursor; }
 
41
  Type pop() {
 
42
    DEBUG_ASSERT(cursor > entries);
 
43
    Type obj = *cursor;
 
44
    cursor--;
 
45
    return obj;
 
46
  }
 
47
  void push(Type obj) {
 
48
    DEBUG_ASSERT(cursor < entries + kapacity);
 
49
    cursor++;
 
50
    *cursor = obj;
 
51
  }
 
52
  void clean() {cursor = entries; }
 
53
  unsigned int size() const {return(cursor - entries);
 
54
  }
 
55
  Type element_at(unsigned int i) {
 
56
    assert(i < size());
 
57
    return entries[i+1];
 
58
  }
 
59
  int capacity() {return kapacity; }
 
60
private:
 
61
  int kapacity;
 
62
  Type *entries;
 
63
  Type *cursor;
 
64
};
 
65
 
 
66
template <class Type>
 
67
KStack<Type>::KStack() {
 
68
  kapacity = 0;
 
69
  entries = 0;
 
70
  cursor = 0;
 
71
}
 
72
 
 
73
template <class Type>
 
74
KStack<Type>::KStack(int k) {
 
75
  assert(k > 0);
 
76
  kapacity = k;
 
77
  entries = (Type*)malloc((k+1) * sizeof(Type));
 
78
  cursor = entries;
 
79
}
 
80
 
 
81
template <class Type>
 
82
void KStack<Type>::init(int k) {
 
83
  assert(k > 0);
 
84
  if(entries)
 
85
    free(entries);
 
86
  kapacity = k;
 
87
  entries = (Type*)malloc((k+1) * sizeof(Type));
 
88
  cursor = entries;
 
89
}
 
90
 
 
91
template <class Type>
 
92
KStack<Type>::~KStack() {
 
93
  free(entries);
 
94
}
 
95
 
 
96
}
 
97
 
 
98
#endif